A Variant of Anderson Mixing with Minimal Memory Size
Authors: Fuchao Wei
Chenglong Bao
Yang Liu
Guangwen Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Anderson mixing
unconstrained optimization
stochastic optimization

Abstract: Anderson mixing (AM) is a useful method that can accelerate fixed-point iterations by exploring the information from historical iterations. Despite its numerical success in various applications, the memory requirement in AM remains a bottleneck when solving large-scale optimization problems in a resource-limited machine. To address this problem, we propose a novel variant of AM method, called Min-AM, by storing only one vector pair, that is the minimal memory size requirement in AM. Our method forms a symmetric approximation to the inverse Hessian matrix and is proved to be equivalent to the full-memory Type-I AM for solving strongly convex quadratic optimization. Moreover, for general nonlinear optimization problems, we establish the convergence properties of Min-AM under reasonable assumptions and show that the mixing parameters can be adaptively chosen by estimating the eigenvalues of the Hessian. Finally, we extend Min-AM to solve stochastic programming problems. Experimental results on logistic regression and network training problems validate the effectiveness of the proposed Min-AM.

A Variant of Anderson Mixing with Minimal Memory Size
Fuchao Wei', Chenglong Bao Yang Liu Guangwen Yang'
Department of Computer Science and Technology. Tsinghua University, China
2 Institute for AI Industry Research (AIR), Tsinghua University, China Yau Mathematical Sciences Center, Tsinghua University, China 'Yanii Lake Beijing Institute of Mathematical Sciences and Applications
Abstract
Anderson mixing (AM) is a useful method that can accelerate fixed-point iterations by exploring the information from historical iterations. Despite its numerical suc- cess in various applications, the memory requirement in AM remains a bottleneck when solving large-scale optimization problems in limited machine. To address this problem, we propose a novel variant of AM method, called Min-AM, by storing only one vector pair, that is the minimal memory size requirement in AM. Our method forms a symmetric approximation to the inverse Hessian matrix and is proved to be equivalent the full-ment uoll-memory Type-I AM for solving strongly convex quadratic optimization. Moreover, for general nonlinear optimization problems, we establish the convergence properties of Min-AM under reasonable assump- tions and show that the mixing parameters can be adaptively chosen by estimating the eigenvalues of the Hessian. Finally, we extend Min-AM to solve stochastic programming problems. Experimental results on logistic regression and network training problems validate the effectiveness of the proposed Min-AM.
Introduction
Anderson mixing (AM) (2) is powerful method for accelerating fixed point iterations, and has been widely used in scientific computing 5 [7] and machine learning [31] [8] 29]. In each iteration, AM
extrapolates new iterate that satisfies certain optimality property by using the historical iterations, and exhibits empirical acceleration over classical fixed-poin iterations [60]. Thus, AM can reduce the computation cost when evaluating the fixed-poii map time-consumine consumnnn process. Also, the inspiring connections of AM with GMRES (60 48) and multisecant quasi-Newton methods [22] provide some explanations for the acceleration benefit from AM. In recent years, there have been many works applying AM to solve various optimization problems [56] 62 41. Their promising
results in different tasks suggest that these AM-based methods are very competitive while being more economical than Newton's ' method. However, the existing convergence theory of AM is still unsatisfactory 3 and AM can diverge some case [1I. Consequently, the applications of AM and its variants for machine learning problems and the corresponding theories deserve deep research.
One major concern of AM is the heavier memory overhead compared with the fixed- point iteration. In AM(m), it has to store vector pairs about historical information from the m previous iterations, where is the memory size. Specifically. AM(m) is called as the mimitey-memory AM if m oc, and full-memory AM m = oc. The AM(() is the simple fixed-point iteration. In practice choosing proper memory size is heuristic and it is observed in [47 that small
deteriorate the efficacy. However, for practical applications, a large m can lead to memory issue for solving large-scale and nigh-dimensional problems when the memory resource is limited.
CCoresponding author. clbao waw..mailliiiiiiii tsnihilsiinhu..euuccmm
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we address the memory issue of AM for solving optimization problems by proposing Min-AM, a novel variant of A1( that has minimal memory size in AM. Min-AM is built upon the Type-I AM 122 60] a variant of AM. Let (M-I(m) denote the Type-I AM with memory size m. Using a projection wrojection-mixing framework of AM-I, the Min-AM retains a recursively modified vector pair and adds one extra projection step in each step of AM-I(1). Compared to AM(1), Min-AM forms symmetric approximations to the Hessian and is equivalent to AM-I(o0) when the objective function is strongly convex quadratic. By incorporating the restarting strategy, the restarted Min-AM has faster convergence rate than AM(1) for general nonlinear optimization and the spectrum of Hessian can be cheaply estimated that leads to adaptive choices of the mixing parameters. Min-AM is also extended to stochastic optimization. In summary, we highlight the main contributions of this work as follows.
We propose Min-AM, a variant of AM(I) that achieves the minimal memory size in AM, for solving optimization problems. Compared to AM(1), Min-AM forms symmetric approx- imations to the Hessian and incorporates more historical information to obtain the update. Thus, Min-AM can significantly reduce the memory requirement and computational cost of AM while maintaining the fast convergence property.
We show that the local convergence rate of the restarted Min-AM has optimal dependence the condition number of the objective function. We provide adaptive choices of the mixing parameters by estimating the spectrum of the Hessian economically in each iteration. Also, we give the convergence and complexity analysis of a stochastic extension of Min-AM for solving nonconvex stochastic optimization.
We verify the properties of Min-AM, and apply the restarted Min-AM to logistic regression and the stochastic Min-AM to train neural networks. The experimental results are consistent with our theoretical analysis and show that the Min-AM is competitive with the limited- memory quasi-Newton methods with large memory size in deterministic optimization and achieves promising results in training neural networks.
Related work. Fixed-point problems can be recast as solving systems of (non)linear equations. AM is practical alternate for Newton's method when the Jacobian is unavailable or difficult to compute 35 In the linear case, it is established in [60 48] that the full-memory AM is equivalent to GMRES 551 a classical Krylov subspace method for linear systems. In the nonlinear case, AM is recognized as a multisecant quasi-Newton method and a variant, called Type-I AM, has been proposed in [22]. From the perspective of convergence analysis, it proved that the local convergence rate of the limited-memory AM is no worse than that of fixed-point iteration [59 16 and the potential
improvement depends on the quality of extrapolation 21 46) However, counter example 41
shows the divergence behaviour of AM(1) and the recent review
B indicates the need of further
research on the theoretical properties of AM.
The inspiring performance and the easy implementation of AM motivate many new variants of AM for various applications in machine learning. In (35), a regularized variant of AM is proposed to accelerate gradient descent for unconstrained optimization, which is adapted in 23 for nonsmooth convex optimization and in (58] for reinforcement learning. In [62] a stochastic version of AM is developed and has convergence guarantee for stochastic optimization. The Type-I AM is modified in 67 to solve nonsmooth fixed-point problems. A more recent work, the short-term recurrence AM (ST-AM) [3 stores two vector pairs to reduce the memory cost of AM. Our Min-AM method achieves the minimal memory size, i.c. m = 1, further reducing the memory size of ST-AM.
The memory overhead is a common issue of quasi-Newton methods. It is desirable to keep memory size as small possible without sacrificing the efficacy of the algorithm. Some works (37 9
study the choice of memory size in L-BFGS (3), but the performance with minimal memory size unsatisfactory. In stochastic programming, the sublinear convergence rate is optimal when only stochastic gradients can be accessed 43 Thus the heavier memory and computational cost makes
quasi-Newton methods [2 27
10 less appealing than the more economical first-order methods 49 36). In this work, our proposed Min-A.M method exhibits the fast convergence as quasi-Newton methods while the memory cost close to first-order methods.
61
Notations. Let A denote the forward difference operator, e.g. Ar = I - -g. range(X) (X) denotes the subspace spanned by the columns of a matrix X. For every matrix A E ddxd the Krylov subspace Kr, (,,(A, v) = span(u, Av...., Am-luy, and ||>]|| = (a 1/2 denotes the A-norm when A is symmetric positive definite (SPD). "un is the Penrose-Moore inverse.

---

2 The Anderson mixing scheme
In this work, consider the minimization problem
min f(x), x E Rd
(1)
where f _2 + IR is continously differentiable. The first-order optimality condition of ① is equivalent to x - g(x), where g(x) I
Vz(x). describe the Anderson mixing scheme with g(xx))
the projection-mixing framework 62] Define
-Vf(a)) to be the residual.
AM(m) maintains m (m S min(d, k)) vector pairs stored in Xx. R E Rdx";
X = [A#kmm m. A
A R A Ark A
Ark-1l.
(2)
Each update can be decoupled into two steps, namely the projection step and the mixing step:
Ft = X (Projection step), Ih++1 3x + BETK, (Mixing step),
(3)
where Fs R. 8g > 0 is the mixing parameter, and F arg minreR" ||ra RRT
12- It
easy to know that the Galerkin's 's projection condition F rango (Rç) holds. Assuming R R2:
nonsingular, the resulting one-step update of AM(m) is #k+1 = 2 + HεTE where
H 3 (X& + 3g R& (R. R
The AM-I 22 60 falls into the same projection-mixxt
framework, and the only difference lies in the choice of L.. The Pa of AM-I is determined by another Galerkin's condition:
F (r&- RT Xx = O.
(5)
Substituting the solution of ( into the approximated inverse Hessian matrix H3 of AM-I is
H 3 I (X + 3x Rs ( xx
by assuming X R3 is nonsingular. AM-I has a close relation to Newton's 's method and an alternative interpretation of AM-I is given in Appendix [..1
H T S.I. H Rs B₁ T/ s.t. B = - -Rx- Thus, both AM and AM-I are multisecant methods. Besides, from and (6), the approximated inverse Hessian matrices Hy are generally not symmetric.
Remark 1. established [22] that the H3 of AM solves mins,
-X, and the H3 of AM-I satisfies H3 B where Bę solves min
3 The Min-AM methods
In each iteration, AM(m) has to store two matrices Xg. Rs E Rdxmm which dramatically increases the memory burden in large-scale problems. To reduce the memory requirement, we consider the minimal memory case, i.e. m 1. The proposed Min-AM is a variant of AM(1) and the convergence of Min-AM established this section.
3.1 The basic Min-AM
In this section, we consider the simple case of (T]: the objective function f(x) 1TT Ax 8T where A is SPD. Let 8 = A inverse Hessian of AM(1) is H₃ = 3& - (8k + (v) yke) - which is non-symmetric. However, the Hessian matrix f is naturally symmetric. To achieve a better approximation of V first recursively modify the vector pair 8k, yk to incorporate more information from the previous iterations. Let P1 = Ato, q1 = Aro E Rdd For 2
Ark-1, and choose
in 4 The approximated
2, we construct Py and qs by
Pk = A 14-1 qk = Ark-1 qk-1Sk>
where S& = (pT 9k-1) pT Ark assuming pT_19k-1 1h-1 * 0. Then, inspired by the Two-Grid
Cycle method 153 Algorithm 13.2] in the multigrid techniques 11, add an extra projection step
to 3 and the resulting scheme is
(1)
Eb - Ph
(1) k
(1)
(Projection step)
(8a)
(2) (1) B,r
(1)
(Mixing step)
(8h)
JK+1 = I Pk (2)
(2)
(2)
(Projection step)
(8c)
3

---

where (1) = r Uk 1 and Bx > 0. Define r. = kk= 3x Arg
(2)
(2)
(2) and rk = =
(2) Ts k It
can be verified that rx (1) (2) and rk are equal to the residuals at o (1) (2) and F respectively.
The coefficients 1 and [(2) are determined by applying the Galerkin's is condition of AM-I:
= rk - T 1
Pk:
(2)
T
(2)
T Pk-
(9)
Assume Pl: 9k + The scheme formulated by 8a (c)) gives the Fx++ by
PkPP
pagk P 0k
(1
(1-
g&PR
I In + HATK Hss
+ Brs
(10)
P 9k
P Pk 9k
leading to the basic Min-AM. The derivation of (T)) is in Appendix B.
It is worth mentioning
that the approximated inverse Hessian H3 in TO) symmetric. Due to the space limit, give the
details of the basic Min-AM in Algorithm 2 in Appendix [ Define Pk (P1, Pp..P...... ,k), Qs =
(g1, 001.92....0 ,............................... 9k), we summarize the properties of the basic Min-AM in the next theorem.
Theorem 1. Let f(x) = 1x= Ar - buxx where A is SPD and { J be the sequence generated by the
basic Min-AM for solving []. x² is the exact solution. Then, the following properties hold:
(i) || 22 > 0, range( Pk.) = KC (A, range( Q1) AK,((A,
(ii) Qk APk: Pi (1 S J k);
(iti) (1) 1 range(Ps) Pb)) and Fk xo + 2g., where 24 arg KKg 10o x² lA
(1)
Moreover, if [|rk (1) ||2 0, then F&+1 = x².
The proof is deferred to Appendix B.2 The property (i) ensures p qh * 0 during the iterations, so
Sk and the update (T) are well defined. The property (iii) indicates 2.11 = where 2x is the
k-th iterate of the conjugate gradient (CG) method 32] Also, due to Proposition [ Appendix B.2 the intermediate iterate ã of AM-I(cc) satisfies 3g = #t so the basic Min-AM essentially equivalent to the full-memory AM-I when solving unconstrained strongly convex quadratic problems. In this sense, Min-AM can incorporate more historical information than AM(1).
Remark 2. Although Min-AM and CG equivalent for solving SPD linear systems, their numerical performance has large difference for general nonlinear programming as shown in our experiments. Remark 3. The Hg in (TO) is reminiscent of the memoryless BFGS method [4], but the key difference lies in the construction of ps and qu in (7). In memoryless BFGS, there are no correction terms (Cx 0), and it is generally not equivalent BFGS (45) and CG. See Appendix A. for more details.
3.2 The restarted Min-AM
For general nonlinear optimization, since global convergence may be unavailable for Min-AM as counter example exists for AM [41, we introduce the restarting strategy to the basic Min-AM and establish the local convergence analysis. Our purpose to prove the faster convergence of the restarted Min-AM than that of gradient descent (GD), and sharpen the existing results of AM [59] 21
Restarting Strategy. Let m& be the number of iterations from the last restart. Min-AM restarts, i...
setting my = 0 and Pk = qb = O. when any of the following conditions is violated:
m& m,
(1la)
q Ph 2 1/4h- 11--ma+PPP--- 1Pk-m
(11b)
[ ll2 nl (f ll2,
(11c)
where m is constant positive integer, and < T 1, > are constants. In the interval between two successive restarts, the iterations are the basic Min-AM iterations.
The check
a is limit the number of high-order terms of errors accumulated during iterations.
The check 1Tb is for the numerical stability of Min-AM since Pt q appears in the denominators in 11p.. The check (Tc) is to control divergence. The algorithm is shown in Algorithm [I] Let
æ|12 S P} denote the ball centered at with radius We impose the following assumptions on that are standard in the convergence analysis of quasi-Newton methods 45 and the regularized nonlinear acceleration method [56].
[z) = {y E IR
Assumption 1. f: Rd - R is twice Lipschitz continuously differentiable in a local region of local minimizer x", and the Hessian matrix A : V²f(x") is SPD.

---

Algorithm Restarted Min-AM for general nonlinear optimization
Input: zu E IR .k > 0, m > 0, r E (0, 11,
1: Po. qu
Rd me =0 0
2: for = 0. 0.1...., until convergence do
3: rk (zxk
4: if m& > m or | > x then
5:
my
6:
end if
7:
if my then
8:
= Ih 2b-1, 9. Tk Tk
9:
ÇA ( Pk 19
10:
Ps = Ph P
-5-1
IP qel Tlpk my +1 m1+ then
12:
my =0 0 end if
14:
end if
if mi then
16:
Ph Uj = 0 E Rd
17:
end if
18:
Za+1 2ạ (x)) PKPHTR + 3k (1 (pk (m (1 (p (
19:
m++1 = my
20:
end for
21:
return 2*
From Assumption
there exist positive constants P. μ, and i such that for all x Ba(x").
a S y V f(xyy S L, for all y E Rd and y * O;
(12a)
yFy [V)(2) f² x²) ~ 211
(12b)
Here, μ is the strong convexity constant, and T., are Lipschitz constants of f and 5 respectively.
With the restarting strategy, we apply a multi-step analysis and has the following convergence theory: Theorem 2. Suppose that the Assumption [ holds. Ler { be the sequence generated by the restarted Min-AM for solving (T) and 02 max (|1 Br L1, B&pl] S 0 for constant E (0, 1).
Then there exists positive constant
such that for any vn E Bp(x²), we have
VV//u-1
me
| --=-==1 11 5 20s
|k
x² 11 R. O 2k- - =2))
(13)
VL/u+1
Moreover, if then |,04 xx 1 : 11))
The proof is in Appendix C.1 where a more general theorem (Theorem 6 given. The result from Theorem 2 suggests that the restarted Min-AM method has a local linear quadratu convergence rate, and the rate has optimal dependence on the condition number. Compared to the existing results that show the local linear convergence rate of AM is no worse than that of gradient descent (GD) method (59 16), the bound (3) clearly improves the convergence rate of GD.
Remark 4. Classical nonlinear CG methods [ are also memory-eficiint with recursively modified searching directions, but the step size relies on line-searde or Hessian-vecton products which can be time-consuming for solving large-scale optimization problems.
Remark 5. The momentum based methods, e.g. Nesterov's 's accelerated gradient (NAG) method [44), also achieve the optimal convergence rate if the parameters μ. and L are known. In restarted Min-AM, we give an economical method that approximates the best step size 2/ (L + μ1) in the next subsection.
3.3 Eigenvalue estimates and the choice of mixing parameter
The mixing parameter Bg is critical for AM and AM-I, and an improper choice of 3r can lead to divergence (22.. Fortunately, the spectrum of the Hessian can be economically estimated
5

---

by-product of Min-AM. To better explain the idea, we consider min f(z) 2= Ax - bbx where A is SPD. We apply a projection method [54] to estimate the eigenvalues:
V E ro)
(A A 1 (A,
(14)
where u E Rd is the approximate eigenvector sought in the Krylov subspace KCx ro), and X E IR an eigenvalue estimate, which is known as generalized Ritz value [42]. Our goal is to compute Since range Px) = KA (A, ro) as shown in Theorem I
we can select PaY, y E I Then the
projection condition [14) leads to
PK AAP - APT APay-
(15)
From the construction of Pa and Qu. we can derive the three-term recurrence relations (see details in Appendix D.I there exists tridiagonal matrix Tp (((+1)x such that
APx Pk+1 TR,
AQ: QK+ITE-
(16)
Then, have AAP.P P AP Tv. By Theorem I PK Apx+1
QTPp+11 = 0. Thus,
AP Th = PK AP&TE,
(17)
obtain Tay Xy, which indicates that the generalized eigenvalue problem (15) is reduced to solving the eigenvalues of
where T5 E R is obtained from Ty by deleting its last row. By 15 and
a tridiagonal matrix Tk. Moreover, the three elements of the k-th column of T7 are easy to obtain
from the coefficients (1)) r(2)
k B and 8x on the fly (see details in Appendix D.1
(2) BK-1(1 1
(k) #
1
1
(2)
K
(k+1)
(18)
(1)
32-1
BE
3x (
where r(2) : For solving general nonlinear optimization with the restarted Min-AM, suppose that ma 2 1. We can also construct a tridiagonal matrix Tj E R starting from the (k - m )-th
iteration with the nonzero elements defined using the coefficients during the iterations (see Definition in Appendix D.2). We use the eigenvalues of 7 as the eigenvalue estimates of the Hessian.
Theorem 3. Suppose that Assumption holds, and {a } is the sequence generated by the restarted Min-AM for solving (1. Assume that 33 E [3, 3r) (vj 2 0) for some positive constants B and B',
and there are positive constants fJo To such that [|V](x))) S ((oo)((( ll (0 S j S k + 1),
[1 1 To (1 S k): X is eigenvalue of TT constructed by restarted Min-AM. Ler ((m2) denote the set of Ritz values computed by an my-step A-norm based Lanczos algorüthm (Algorithm) 3
Appendix (22)) for fx²)=") with starting vector V2 f ffx"((")) (x* Fk xk-ma)) Then there is a positive
constant p S. p such that for any E BB(x²), ) we have
min (m)(m)))
A A| RO(1 - x 12))
(19)
The proof in Appendix D.2 Since the Ritz value Á approximates a true eigenvalue of f((())
54
Theorem 3 suggests that the restarted Min-AM can give reliable eigenvalue estimates if | x is sufficiently small. At the k-th iteration, where m, > 2, let e and L be the eigenvalues of TT- with the smallest absolute value and the largest absolute value, respectively. We use [ and |ž] to estimate y and L. Then
take the mixing parameter as 3x = 2/ + (7.1) estimate the optimal value 2/(n + L). The total computational cost is O(m flops as it requires solving the eigenvalues of T [24] Since my & d in practice. this strategy can be a useful and economical option.
Remark 6. The spectrum of Hessian is imporiant for determining the step sizes. Once we obtain the estimates of μ and L by Min-AM, we can apply them to many first-order methods.
3.4 The stochastic Min-AM
For many applications in deep learning, the large data size prohibits the evaluation of the full gradient, and the stochastic optimization stands out as a solution. Specifically, we consider developing proble.
stochastic version of Min-AM to solve the nonconvex optimization problem:
T
min f(x) = T Σ f((z), #ERd
(20)

---

where f: R - I may be nonconvex. Since T can be extremely large, we sample mini-batch St S [T] == (1.2..... , and use fs, (Ix) == 1 Lies, fz(z) to estimate the full gradient Ai
Vf(a)). where ny : |S is the batch size. Then, T == Vs, (Ix) is an estimate of -V (zxx)
Due to the noise in the gradient estimates and the nonconvexity of f, direct application of the deterministic Min-AM (20) may be problematic. For example, the searching direction may be not a descent direction since H2 can be indefinite. Hence, we should introduce some fundamental modifications to the basic Min-AM.
Regularization. Inspired by 23 we define the function
+ ( p²q 8(1pl1 + 11
q,
(21)
Let 4 == + (px- 9k (22) for some 5(2)
> 0. We substitute 4y for the P Uu appeared in (10 and define Pk: 4 i.. Pk if 42 and pk $ 1 if the o O. The resulting regularized Min-AM
update is Fk+11 3k + H rk. where
H PRPEPE + B PMPAO (( PL4)PP)
(22)
Damping. We propose specialized damping technique for Min-AM, which interpolates the updates of stochastic gradient descent (50) (SGD) and Min-AM, and is described as
zx 26 + BArK, o 24 + H HTT #k+1 = (1 ax)= + ag
(23a)
where 2f is the SGD update, =4 is the Min-AM update, and og is the damping parameter. It can be seen that SGD and Min-AM serve as the predicted step, and xx+1 is weighted average of them. Moreover, the inverse Hessian approximation
HA (1 Ork 3 - on H 2 (1 on or) 0
(24)
provided that ag e 10, and H& 2 O.
By incorporating damping and regularization, we obtain the stochastic Min-AM (sMin-AM), and the in
algorithm is summarized in Algorithm in Appendix [E] To analyze the convergence properties, first impose the following assumptions on the objective function f. which are the same as [6 62]
Assumption 2. f Id + continuously differentiable, and f(x) is lower bounded by real number flow for Vx E Rd. f is globally L--Lipscitz continuous.
Assumption 3. At each iteration k. the gradient estimate fe (Ix) satisfies Ex [V (xx)] = fxx)), Eg Se, (ax) - (x+)) I o², where a > O, and & E [T) = 0, 0. are independent samples, and the random variable εk (for a given k) is independent of (z, 1k
The diminishing condition about By is
+oc
+o0
Σ By = t00, Om
Σ km0
82 <
+00.
(25)
With chosen Se, we choose the on and ((2) of Min--M meet the following conditions:
Assumption 4. Given constants μ E (0, C2 > O, and C2 > O, we have Og E [0, min 11]], Pk: S 0, and - (px/ P - 2px 11 + & 1 < Cz.
2//2
We establish the convergence results of sMin-AM for nonconvex stochastic optimization and the proofs can be found in Appendix E.2 and Appendix E.
Theorem 4. Suppose that Assumptions
24 hold and (ax) is the sequence generated by sMin-AM with batch size ni n < T. If Ba (0, e0(3+ and satisfies (25), then
lim inf (*x))l = 0 with probability 1, k
(26)
and for all k. there exists My such that B[f(xx)) My-
Eç, fc. (xx) < Mg. vk where M, > 0 is constant, we have
lim /
with probability
(27)
k
7

---

107
10
101
Numn of grndiient
10
MAC
of
ROD
10:71
0PP:2: -PP-----PP
AZ54jA indallall dbl
10
44 apve
10
10
Mivedt
Moxil
10
20
30
40
20
190
40
60
50
100
Beniion
Bicrations
Dteistionss
(a) Quadratic optimization
(b) Test madelon
Test on a9a
digemake MixAM
Lassoedk
bd44
MixAMM
0.04
MinAM
5/07
Imaginury part
0.00
0.00
Imagitsryy
0.00
-004
-300
-0.04
300
2001
1000
0:75
1.30
0.4
Real part
Real
Real
(d) Eigenvalue estimates
(e) Eigenvalue estimates (madelon)
(f) Eigenvalue estimates (a9a)
Figure 1: Left (strongly convex quadratic optimization): (a) curves about residuals and intermediate residuals; (d) exact eigenvalues, and eigenvalue estimates from Min-AM. Middle and right (regular- ized logistic regression on madelon and a9a datasets): (b)(c) [ of each method; (e)(f) Ritz values of 2 fxx*) by k-step Lanczos algorithm, and eigenvalue estimates from Min-AM.
Theorem 5. Suppose that Assumptions 2 4 hold. { N-1 are the first N iterations generated
by sMin-AM with batch size n1. = T, and 3x = min( 21(1+057 oVN ~ J. where D is problem-independee constant. R is random variable following Pn(k) Prob (R k} 1/N, O,.... Then
D
E [ L(1 + C2)
(4Ds PVN
2( 2 + +(1+ C2)3
(28)
2u
where Dj = - and the expectation is taken with respect to R and (5, To ensure B[lV f (xx))1] S the number of iterations is (11/²).
Remark 7. The Theorem Aatoremmestalliinn esstablishes the global convergence of sMin-AM for solving the problem (0). and Theorem 5 indicates that sMin-AM attains the O(1/²²) iteration complexity which is asymptotically optimal for optimization methods based on a stochastic first-order oracle (43)
4 Experiments
We first tested the basic Min-AM in solving strongly convex quadratic optimization (cf. Theorem D and the restarted Min-AM on logistic regression (cf. Theorem 2). Then, we applied the sMin-AM train deep neural networks on CIFAR (8] and ImageNet
Details about the experimental
settings and more numerical results can be found in Appendix
Strongly convex quadratic optimization. As shown in Fi the first intermediate residual T Min-AM exactly matches the k-th residual of CG, which verifies Theorem Since X R2 can be ill-conditioned when & is large, it is found that AM-I(co) fails to coincide with CG and Min-AM in the later iterations. The eigenvalue estimates computed by Min-AM also well approximate the true eigenvalues of the Hessian matrix, which is consistent with analysis in Section 33.] In Appendix F.I we also give a discussion about the cost of the eigenvalue estimation procedure.
Regularized logistic regression. We conducted the regularized logistic regression the datasets "madelon" and "a9a" from LIBSVM [14] The compared methods were GD, nonlinear CG (NCG) with line-searchh Nesterov's accelerated gradient (NAG), L-BFGS(m)) AM(m), and the ST-AM. We

---

applied the standard k-step Lanczos algorithm 224 to compute 100 Ritz values of f(="), ) in which the smallest and largest ones were used for the setting of p. in NAG. The results in Figure T show that Min-AM is competitive with AM(20). It converges much faster than AM(1), L--FGG((1) (i.e. memoryless BFGS), NCG, and NAG, and outperforms ST-AM. Also, in both datasets, the eigenvalue estimates from Min-AM are accurate enough to approximate the largest and the smallest Ritz values, even though the objective function is non-quadratic. More results including the effect of 3g. can be found in Appendix F2
Table
Experiments on CIFAR-IOCIFAR-ION "_" means failing complete the test in our device,
(a) Final TOPI test accuracy (mean + standard deviation) (%) on CEFAR-IOCIIAR --00OO
CIFAR-10
CIFAR-100
Method
VGGI6
ResNet18
ResNer20
ResNer44
ResNer56
WRNI64
ResNet18
ResNeXi
DenseNet
SGDM
93.524
85
92.03=.16
93.10=.23
93.47=.28
94.90:109
77.274.09
78.412.54
78.49 12
Adam
92.29:
93.03+.07
91.17=.13
92. 92.28:6.22
92.39-223
92.45
12.
73.574.17
70.80
AdaHessian
93.42--11
94.
91.92+332
92.74+.11
92.40-006
94.044-12
76.59+.42
SAM(1)
93.35.1.12
94.95.1110
92.101.05
93.151..3
93.441.19
95.02.132
77.061.48
79.12...4
79.58...9
SAM(10)
93.592.11
95.172.10
92.43=.19
93.57=.14
93.77=.12
95.23:1.07
78.132.14
79.31#.27
80.09=.52
ST-AM
93.67.1.25
95.27.1.04
92.399.11
93.52.1.02
93.691.18
95.2111.99
7..91
79.53.1.34
80.36..25
SMin-AM
94.091.12
95.282.04
92.42=116
93.72=.27
93.82=.10
95.134.03
78.262.18
79.642.19
79.88=.09
(b) The memory and computation cost compared with SGDM. The notations "m","te"" and "t" are abbreviations of memory, per-epoch time, and total training time, respectively.
Cost
88
CIFAR- 10/A-1
CIFAR- 1FFAR-100/DensNee1211
(x SGDM)
de
m
t/c
t/c
t/c
SGDM
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1,00
1.00
SAM(1
1.73
1.78
2.51
2.59
0.58
1.19
0.60
ST-AM
1.05
1.46
0.82
1.55
1.91
1.67
1.04
1.07
0.54
1.01
1.11
0.55
sMin-AM
1.01
1.15
0.64
1.35
1.25
0.78
1.03
1.00
0.50
1.01
1.09
0.55
S0I0M 455 AM
SCDM
SKIM
70
.Nix-AM
.MMxAM
Ten Accusce %
-0
Trit Actimee
Tean
Spochs
Epocis
Epocts
(a) Training loss
(b) Train accuracy
(c) Test accuracy
Figure 2: Experiment of training ResNet50 on ImageNet.
Experiments on CIFAR. We applied sMin-AM to train VGG16 (57]. ResNet1
[0)
WideResNet16-
66 (abbr. WRN16-4) on CIFAR-10, and train ResNet18, ResNeXt50 64
DenseNet121
34 on CIFAR-100. The compared optimizers were SGDM [49], Adam (36], Ada-
Hessian 665 stochastic AM (SAM) (62,, and ST-AM 63 Since the experimental setting was the
same 162 633. their results were used for reference. Table I(a) reports the final test accuracy of
each optimizer for training 160 epochs. shows sMin-AM improves SAM(1) and has comparable accuracy to SAM(10). sMin-AM can also use fewer epochs for the training. By setting the accuracy of SGDM as baseline, Table [(b] shows the memory, per-epoch time, and the total time for an optimizer to achieve comparable accuracy to SGDM (more details about the number of epochs and final test accuracy can be found in Table Suble in Appendix F.3.2.. sMin-AM AM significantly reduces the memory cost of SAM(10) and the total training time is less than SGDM.
Experiments on ImageNet. We trained ResNet50 on ImageNet with SGDM and sMin-AM. Figure 2 shows that the training process of sMin-AM is faster than SGDM. sMin-AM can achieve both higher train accuracy and higher test accuracy fewer epochs. In our test, we found the memory cost of sMin-AM was 1.04 times that of SGDM, and the per-epoch training time of sMin-AM was 1.01 times that SGDM. Hence, for neural network training on larger dataset, sMin-AM can still be competitive with SGDM.

---

Conclusion
In this paper, we propose Min-AM, a variant of AM(I) with minimal memory size. Min-AM only stores one recursively modified vector pair and is essentially equivalent the full-memory Type-I AM strongly convex quadratic optimization.
establish the convergence properties of Min-AM under deterministic and stochastic settings. For deterministic optimization, we also propose an economical method to estimate the spectrum Hessian, which can be used to adaptively choose the mixing parameters. The experimental results validate the effectiveness of our methods.
Acknowledgments and Disclosure of Funding
This work supported by the National Key R&D Program of China (No. 2021YFA1001300) National Natural Science Foundation of China (No.61925601), National Key Basic Research Program of China F2000YB02048000, Tsinghua University Initiative Scientific Research Program, National Natural Science Foundation of China (No. 1901338), and Huawei Noah's 's Ark Lab. We thank all anonymous reviewers for their valuable comments and suggestions on this work.
References
[1] Hengbin An, Xiaowei Jia, and Homer F Walker. Anderson acceleration and application to three-temperature energy equations. Journal of Computational Physics, 347:1-19, 2017.
[2] Donald G Anderson. Iterative procedures for nonlinear integral equations. Journal of the ACM (JACM), 12(4):547-560, 1965.
[3] Donald GM Anderson. Comments on "Anderson acceleration, mixing and extrapolation". Numerical Algorithms, 80(1):135 (03)44,3-33,,10 2019.
[4] Neculai Andrei. A note on memory-less SR1 and memory-less BFGS methods for large-scale unconstrained optimization. Numerical Algorithms, pages 1-18, 2021.
[5] Akash Arora, David C Morse, Frank S Bates, and Kevin Dorfman. Accelerating self- consistent field theory of block polymers in variable unit cell. The Journal of Chemical Physics, 146(24):244002, 2017.
[6] Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk der Vorst. Templates for the solution of algebraic eigenvalue problems: A practical guide. SIAM, 2000.
[7] Stephen Becker, Jalal Fadili, and Peter Ochs. On quasi-Newton forward-backward splitting: Proximal calculus and convergence. SIAM Journal on Oplimization, 2944):2445-2481, 2019.
[8] Albert S Berahas, Frank E Curtis, and Baoyu Zhou. Linited-memory BFGS with displacement aggregation. Mathematical Programming, pages 1-37, 2021.
[9] Paul T Boggs and Richard H Byrd. Adaptive, Limited-memory BFGS algorithms for uncon- strained optimization. SIAM Journal on Optimization, 1282):1282-1299 2019.
[10] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Pe- ter Tang. A progressive batching L-BFGS method for machine learning. In International Conference on Machine Learning, pages 620-629, PMLR, 2018.
[11] William L Briggs, Van Emden Henson, and Steve F McCormick. A multigrid nutorial. SIAM, 2000.
[12] Richard H Byrd, Samantha L Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi- Newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):0088-1011 2016.
[13] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks, In
2017 IEEE Symposium Security and Privacy (SP), pages 39-57. IEEE, 2017.
10

---

[14] Chib-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1-27. 2011.
[15] Xiaojun Chen and Masao Fukushima. Proximal quasi-Newton methods for nondifferentiable convex optimization. Mathematical Programming. 85(2):313-334, 1999.
[16] Xiaojun Chen and Carl T Kelley, Convergence of the EDIIS algorithm for nonlinear equations. SIAM Journal on Scientific Computing, 41()):A365-A379, 2019.
[17] Arthur Cohen. Rate of convergence of several conjugate gradient algorithms. SIAM Journal on Numerical Analysis, 9 1972.
[18] Yu-Hong Dai, William W Hager, Klaus Schittkowski, and Hongchao Zhang. The cyclic Barzilai- Borwein method for unconstrained optimization. IMA Journal of Numerical Analysis, 26(3): 604 627, 2006.
[19] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large- scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255 IEEE, 2009.
[20] Rick Durrett. Probability: theory and examples, volume 49, Cambridge University Press, 2019.
[21] Claire Evans, Sara Pollock, Leo G Rebholz, and Mengying Xiao. A proof that Anderson acceleration improves the convergence rate in linearly converging fixed-point methods (but not in those converging quadratically). SIAM Journal on Numerical Analysis, 38(1):788-81)) 2020.
[22] Haw-ren Fang and Yousef Saad. Two classes of multisecant methods for nonlinear acceleration. Numerical Linear Algebra with Applications, 16(3):197-221, 2009.
[23] Anqi Fu, Junzi Zhang, and Stephen Boyd. Anderson accelerated Douglas-Rachford splitting. SIAM Journal on Scientific Computing, 42(6):A3560-43558 2020.
[24] Gene H Golub and Charles F Van Loan. Matrix computations, 4th. Johns Hopkins, 2013.
[25] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint 1rXXiv:412.66777 2014.
[26) Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03593, 2020.
[27] Robert Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block BFGS: Squeezing more curvature out of data. In International Conference on Machine Learning, pages 1869-1878. 2016.
[28] Anne Greenbaum. Iterative methods for solving linear systems. SIAM, 1997.
[29] Huan He, Shifan Zhao, Yuanzhe Xi, Joyce Ho, and Yousef Saad. GDA-AM: On the effectiveness of solving min-imax optimization via Anderson mixing. In International Conference on Learning Representations, 2022.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[31] Nicholas C Henderson and Ravi Varadhan. Damped Anderson acceleration with restarts and monotonicity control for accelerating EM and EM-like algorithms. Journal of Computational and Graphical Statistics, 28(4):334 846, 2019.
[32] Magnus R Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6), 1952.
[33] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge University Press, 2012.
11

---

[34] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4700-4708, 2017.
[35] Carl T Kelley, Numerical methods for nonlinear equations. Acta Numerica, 27:207-287, 2018.
[36] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[37] Tamara G Kolda, Dianne P O'leary, and Larry Nazareth. BFGS with update skipping and varying memory. SIAM Journal on Optimization, 8(4):1060-1083, 1998.
[38] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
[39] Dong Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimiza- tion. Mathematical Programming. 45(1):503,528, 1989.
[40] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.
Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018.
[41] Vien Mai and Mikael Johansson. Anderson acceleration of proximal gradient methods. In International Conference on Machine Learning. pages 8620-6629, PMLR, 2020.
[42] Thomas A Manteuffel and James S Otto. On the roots of the orthogonal polynomials and residual polynomials associated with conjugate gradient method. Numerical Linear Algebra with Applications, 1(5):449-475, 1994.
[43] Arkadij Semenovič Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[44] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[45] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science Business Media, 2006.
[46] Sara Pollock and Leo G Rebholz. Anderson acceleration for contractive and noncontractive operators. IMA Journal of Numerical Analysis, 41(4):2841-2872, 2021.
[47] Sara Pollock, Leo G Rebholz, and Mengying Xiao. Anderson-accellerated convergence of Picard iterations for incompressible Navier-Stokes equations. SIAM Journal on Numerical Analysis, 57(2):615-637 2019.
[48] Florian A Potra and Hans Engler. characterization the behavior of the Anderson acceleration on linear problems. Linear Algebra and Its Applications, 438(3))1002-1011, 2013.
[49] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural Networks, 12(1):145-151, 1999.
[50] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[51] Youcef Saad and Martin Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing, (3)8856-66, 1986.
[52] Yousef Saad. Krylov subspace methods for solving large unsymmetric linear systems. Mathe- matics of Computation, 105551) 1981.
[53] Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
[54] Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
12

---

[55] Damien Scieur, Alexandre d' Aspremont, and Francis Bach. Regularized nonlinear acceleration. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 712-720, 2016.
[56] Damien Scieur, Alexandre d' Aspremont, and Francis Bach. Regularized nonlinear acceleration. Mathematical Programming, 179(1):47-88) 83, 2020.
[57] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409. 2014.
[58] Ke Sun, Yafei Wang, Yi Liu, Bo Pan, Shangling Jui, Bei Jiang, and Linglong Kong. Damped Anderson mixing for deep reinforcement learning: Acceleration, convergence, and stabilization. Advances in Neural Information Processing Systems, 34, 2021.
[59] Alex Toth and Carl T Kelley. Convergence analysis for Anderson acceleration. SIAM Journal on Numerical Analysis, 53(2))805--3) 819, 2015.
[60] Homer F Walker and Peng Ni. Anderson acceleration for fixed-point iterations. SIAM Journal on Numerical Analysis, 4944)11715-17335 2011.
[61] Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-Newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2)927--956, 2017.
[62] Fuchao Wei, Chenglong Bao, and Yang Liu. Stochastic Anderson mixing for nonconvex stochastic optimization. Advances in Neural Information Processing Systems, 34, 2021.
[63] Fuchao Wei, Chenglong Bao, and Yang Liu. A class of short-term recurrence Anderson mixing methods and their applications. In International Conference on Learning Representations, 2022.
[64] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 1492-1500, 2017.
[65] Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney, Adahessian: An adaptive second order optimizer for machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10665-10673, 2021.
[66] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
[67] Junzi Zhang, Brendan O' D'Doooguue, and Stephen Boyd. Globally convergent type-I Anderson acceleration for nonsmooth fixed-point iterations. SIAM Journal Optimization, 30(4):3170- 3197, 2020.
[68] Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix Appendix[[] Appendix D and Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as a URL)? [Yes] See the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix | and the supplemental material.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [No] We reported standard deviation instead.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [No] The assets publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "VhUzln4WAOK", "reviewer": "Reviewer_tRei", "summary": "In this article, the authors introduce a new Anderson mixing method called Min-AM (with restarted and stochastic variants). \nThe Min-AM method aims at solving the problem of memory required by other Anderson mixing algorithms in the large-scale setting.\nIt iteratively approximates the inverse of the Hessian by only storing a vector pair $(p_k, q_k)$ capturing the increment in the iterates and in the residuals at previous step. This is why their algorithm achieves minimal memory: $m=1$. \nThe authors provide \n- strong theoretical guarantees concerning the linear-quadratic convergence of the Restarted Min-AM version in Theorem 1\n- and convergence guarantees for the stochastic version leading to a $\\mathcal{O} (1/ \\epsilon^2)$ iteration complexity \n\nFinally, the authors perform 3 sets of experiments on \n- quadratic strongly convex synthetic problem : to test the performance of the basic Min-AM algorithm versus other methods (first order or quasi-Newton) and the online eigenvalue estimation (with Lanczos algorithm) required to compute the mixing parameter $\\beta_k$\n- 2 regularized logistic regression problems on real datasets (a9a and madelon) to compare against other methods as before monitor the spectrum evaluation\n- 3 image (large scale) datasets CIFAR10/100 and Imagenet on multiple deep architecture to prove the comparable efficiency of Min-AM with SGD with momentum\n\n~~~~~~~\nScore updated after rebuttal (see discussion with the authors), new score: 7", "questions": "I'll start with minor comments and typos and then present my questions to the authors:\n\nMinor comments:\n- A.1) Notations: I recommend placing real number before vectors in eq (7), that is moving coefficients such as $p_k = \\Delta x_{k-1} - \\zeta_k p_{k-1}$, same for $q_k$\n- A.2) Typo: line 142 \"Min-AM and CG are\" instead of \"is\"\n- A.3) Algorithm 1: remove \"Output: $x \\in \\mathbb{R}^d$, we don't know what is x and it is redundant with line 21 of the Algorithm \n- A.4) line 164 : I think it's good to give names to these 4 quantities $\\mu, L, \\hat{\\rho}$ and $\\hat{\\kappa}$, What is $\\hat{\\kappa}$ ?\n- A.5) Assumption 2: what is $f^{\\text{low}}$?\n- A.6) The end of Assumption 3 is strangely written. Again I suggest removing the $\\xi_i$  \n- A.7) Assumption 4, line 248: typo: \"are\" instead of \"is\"\n\nModerate importance comments:\n- B.1) In the definition of $r_k^2$ there is an $A$ matrix (line 124) which I find strange as it does not appear in eq (10). I tried to redo the computations and I think there is a mistake here\n- B.2) Very strange notations for the Empirical Risk Minimization problem formulation: canonical writing is $f(x) = \\frac{1}{n} \\sum_{i=1}^n f_i$. I don't think the $\\xi_i$ notation is useful, it looks like a random variable but it is not the case.\n- B.3) Notations: again, use $T$ iterations instead of $N$\n- B.4) line 257: what are the possible values of $k$?\n\nMajor comments: \n- C.1) Remark 5: I find it unfair to say that NAG requires the knowledge of $\\mu$ and $L$ without even mentioning that Min-AM does (through $\\theta_k$) and in a more than NAG (as the knowledge of $L$ suffices in practice)\n- C.2) line 207: what are $\\tilde{\\mu}$ and $\\tilde{L}$ ?\n- C.3) All the plots are in iterations or epochs. Not a single one shows a result in flops or time. Here the compared methods are very different with very different grid-searching schemes and initialization steps. I really wonder what is the performance of Min-AM when the knowledge of the spectrum is not given. I suspect two things: (i) that this initialization computing the spectrum is very costly and (ii) that it is hard to fine-tune the 4 hyperparameters of Stochastic Min-AM\n- C.4) There is no explanation, no analysis, no comment of Theorem 4 and 5. The reader directly jumps from one to the other \n\n\nQuestions:\n- D.1) Could you please give an intuition about why $H_k$ defined in eq (10) is a (good ?) estimate of the inverse of the Hessian ?\n- D.2) Remark 3, line 147: which kind of equivalence are you referring to when you say \"it has no equivalence to the fully-memory methods\" ? Is this a mistake ?\n- D.3) Why do you use pseudo inverse at line 18 of the Algorithm 1 instead of inverse as these quantities are real numbers ?\n- D.4) How is the regularization in eq (21) combined with Min-AM. Is it which the basic Min-AM or the restarted one ?\n- D.5) How is it possible to have larger time per epoch and smaller total running time for sMin-AM in multiple case of Table 1(b) ?\n- D.6) Appendix: Figure 4 : how is it possible to have a condition number smaller than 1 ? By definition, $L > \\mu$, so $L/\\mu > 1$ and thus cannot equal $10 ^{-2}$ or $10 ^{-8}$.\n\n", "limitations": "Overall, I am very enthusiastic by the results of the paper, arithmetically and numerically (even though I would like to have more information about practical usage of such methods, especially regarding the initialization and the computation of hyperparameters, sensitivity to them etc)\n\nYet, I find that the writing and moreover the conference format is degrading the authors' messages. Every result is touched on very quickly (eg the basic and stochastic version of the algorithm are not in the main text, neither the deep comparison with other methods done instead in Appendix A) and thus many explanations are deferred to the appendix (which is ... 33 pages). I would recommend this work to be reorganized and submitted to a journal. \n\nNote that the paper being to dense, I could not go through many proofs.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- this paper provides a valid solution to the memory problem of AM methods which usually require to store large matrices of previous forward differences between past iterates and residuals\n- the authors suggest a method to choosing the mixing parameters $\\beta_k$ which are based on spectral knowledge of the Hessian\n- The restarted and the stochastic variants of the introduced algorithm come with solid convergences proofs.\n- The Min-AM method is clearly extended to the stochastic setting making it a valid candidate for training deep architectures\n- Experiments, especially on deep net, are very convincing as they show that Stochastic Min-AM competes with SGD + Momentum to train models on CIFAR10, CIFAR100 and Imagenet.\n\nWeaknesses\n- Many hyperparameters: the stochastic version for instance method relies on 4 hyperparameters $\\alpha_k, \\beta_k, \\delta_k^{(1)} and \\delta_k^{(2)}$ which is not underlined in the paper. \n- All the experiments are showing iterations/epochs plots and thus omit many computations required for the evaluation of the spectrum of the Hessian, which is very important as this knowledge is at the core of the setting of the mixing parameters and guarantees good convergence whereas SGD + Momentum would not require this knowledge. Clear time plots with initialization time would have been more informative especially when comparing first order and quasi-Newton methods\n- There is no step back taken by authors (even in the conclusion) about weakness or limits or their method (neither theoretically nor numerically) ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3iyOgR5uoIF", "reviewer": "Reviewer_3SM6", "summary": "This paper proposes a new variant of the Anderson mixing algorithm with minimal memory size. ", "questions": "1. Page 9, upper panel of Table 1: Compared to ST-AM, the numerical results presented in Table 1 are not  statistically significant (except for the case of VGG16).  It is hard to justify the significance of the method in test accuracy improvement. \n\n2. Page 9, lower panel of Table 1: It seems that the improvement is marginal for large-scale problems such as CIFAR100. Please comment on how the performance of the algorithm changes with the scale of the problem. ", "limitations": "Yes. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theoretical development for the proposed algorithm seems solid, but the numerical improvement seems incremental. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "17TaCjGk4BQ", "reviewer": "Reviewer_wR7v", "summary": "The authors present the Min-AM method - an Anderson acceleration technique whose memory is one. The procedure takes advantage of extra projection steps that prevent the loss of some information. The authors show the algorithm's effectiveness by showing its link to conjugate gradient when applied to quadratic functions and its connection with BFGS when looking at the update. Some heuristics are presented to extend the algorithm to nonlinear or stochastic functions, such as restarts, regularization, or adaptive step size.", "questions": "I have a few questions concerning the results and conclusion of this paper.\n1) After looking at the algorithm and the Conjugate Residual method, it seems there is a connection between those schemes. I wanted to have the authors' opinion about that.\n2) In the analysis of the rate of convergence of Theorem 2, you claim that the bound (13) improves on GD. I believe this may not always be the case as a) we do not know how far m_k can go, b) the constant sqrt(L/mu) is larger than one, and c) there is the quadratic factor?", "limitations": "See Strengths and weaknesses.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper tackles a critical problem of the Anderson Acceleration technique: the memory required to perform an acceleration step. In particular, when solving large-scale optimization problems in a resource-limited machine, the memory requirement may be the bottleneck. The small memory also enables a better analysis of the rate of convergence of the algorithm - as in min-AM, we only have one stored vector rather than a matrix.\n\nFrom a technical point of view, the paper is solid. It proposes a novel method, makes a connection with classical algorithms, and shows rates of convergence. Moreover, the assumptions made in this paper are rather classical and nonrestrictive.\n\nI have more concerns about the clarity of the paper. \nI think some parts could have been improved, especially section 3.1. The section is very dense, and the algorithm's derivation is unintuitive. I suggest the authors spend more time introducing the notations and explaining the purpose of all those modifications (why do 8a, 8b, and 8c help to incorporate more historical information?).\nMoreover, the proofs in the appendix are also quite dense. I suggest the author split the big theorem into smaller chunks of lemma to help the reader understand the proofs.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0vhGVLsavZ", "reviewer": "Reviewer_R1xQ", "summary": "The contribution proposes Min-AM, which is the minimum memory variant of Anderson Mixing/acceleration well-known in fixed-point recursions.  ", "questions": "+ Is it possible to clarify some figures as commented above? In particular, the authors may want to plot the error between the corresponding pairs of eigenvalues to show the results more clearly.\n\n+ What is/are the limitation(s) of the proposed method?", "limitations": "I did not find any discussion on this.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The main ideas and results are well-organized and presented with clarity.\n\n+ In this reviewer's understanding, the main/novel contribution of this work are contained in Sections 3.2 and 3.3.\n\n+ The Appendix is very detailed and provides the technical support behind the statements in the main text.\n\n+ Fig. 1(d),(e),(f) are illegible due to the lack of correspondence info between the pluses and circles.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept