Stochastic Anderson Mixing for Nonconvex Stochastic Optimization
Authors: Fuchao Wei
Chenglong Bao
Yang Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Anderson mixing
nonconvex stochastic optimization
neural network

Abstract: Anderson mixing (AM) is an acceleration method for fixed-point iterations. Despite its success and wide usage in scientific computing, the convergence theory of AM remains unclear, and its applications to machine learning problems are not well explored. In this paper, by introducing damped projection and adaptive regularization to the classical AM, we propose a Stochastic Anderson Mixing (SAM) scheme to solve nonconvex stochastic optimization problems. Under mild assumptions, we establish the convergence theory of SAM, including the almost sure convergence to stationary points and the worst-case iteration complexity. Moreover, the complexity bound can be improved when randomly choosing an iterate as the output. To further accelerate the convergence, we incorporate a variance reduction technique into the proposed SAM. We also propose a preconditioned mixing strategy for SAM which can empirically achieve faster convergence or better generalization ability. Finally, we apply the SAM method to train various neural networks including the vanilla CNN, ResNets, WideResNet, ResNeXt, DenseNet and LSTM. Experimental results on image classification and language model demonstrate the advantages of our method.

Stochastic Anderson Mixing for Nonconvex Stochastic Optimization
Fuchao Wei', Chenglong Bao Yang Liu
Department of Computer Science and Technology, Tsinghua University
Institute for AI Industry Research, Tsinghua University
3 Yau Mathematical Sciences Center, Tsinghua University
Yanqi Lake Beijing Institute of Mathematical Sciences and Applications
Abstract
Anderson mixing (AM) is acceleration method for fixed-point iterations. Despite success and wide usage in scientific computing, the convergence theory AM remains unclear, and its applications to machine learning problems are not well ex- plored. In this paper, by introducing damped projection and adaptive regularization to the classical AM, propose Stochastic Anderson Mixing (SAM) scheme solve nonconvex stochastic optimization problems. Under mild assumptions, we establish the convergence theory of SAM, including the almost sure convergence stationary points and the worst-case iteration complexity. Moreover, the complexity bound can be improved when randomly choosing iterate the output. To further accelerate the convergence, we incorporate a variance reduction technique into the proposed SAM. We also propose preconditioned mixing strategy for SAM which can empirically achieve faster convergence or better generalization ability. Finally, we apply the SAM method to train various neural networks including the vanilla CNN, ResNets, WideResNet, ResNeXt, DenseNet and LSTM. Experimental results on image classification and language model demonstrate the advantages of our method.
Introduction
Stochastic optimization is important in various areas such as statistics 15 and power systems 25 In this paper, we consider the following stochastic optimization problem:
machine learning 4
54
min f(z) Eg [F(x;
(1)
zER
where F Rd E R is continuously differentiable and possibly nonconvex and the random variable & E 3 may follow an unknown probability distribution. information about the gradient of f is available through calls to some stochastic first-order oracle (SFO). One special case (I) is the empirical risk minimization problem:
assumed that only noisy
T
min rEBd
f(x)
def
Σ (z), T
where fe. Rd + IR is the loss function corresponding to the i-th data sample and T denotes the number data samples. T can be extremely large such that prohibits the computation of the full gradient Vf. Thus designing efficient and effective numerical algorithms for solving problem [ or (2) with rigorous theoretical analysis challenging task.
Corresponding author. mailo@mal.nee wsi.hiilssinguu..u....
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

One classical approach for solving ① is the stochastic gradient descent (SGD) method [45]. It mimics the gradient descent (GD) method with noisy gradients and exhibits optimal convergence
rate for some strongly convex stochastic problems [10
48 Some early related works of SGD in
convex optimization can be found in
38
39
40]
For nonconvex cases, Ghadimi and Lan 17
proposed a randomized stochastic gradient (RSG) method that randomly selects solution T from previous iterates. To ensure I satisfying E |II V f I c, the total number of SFO- needed by RSG is O (E . For training neural networks, adaptive learning rate methods were proposed to accelerate SGD, c.g. Adagrad [[2], RMSprop [55] and Adam [29]. though their theoretical
properties in nonconvex optimization were unknown until recently 9 Regarding second-order
optimization methods [49 36 37], one notable work is the framework of stochastic quasi-Newton (SQN) methods proposed by Wang al. [60), which covers class of SQN methods and has theoretical guarantees in nonconvex stochastic optimization. However, these second-order methods usually demand more gradient evaluations in every iteration and less noisy gradient information to achieve actual acceleration 4 There are also some recent works inspired from the dynamics perspective, such as the Langevin dynamics based algorithms 66 33 M. but many of them focus on the theory and their applications in deep learning are still under-explored.
In practice, the choices of optimizers vary for different applications [63 and their practical performances are still unsatisfactory in terms of convergence rate or generalization ability [66]. For these reasons, we develop novel second-order method based on Anderson mixing (AM) [2] Our analysis and experiments show the proposed method is competent from both theoretical and practical perspectives and performs well in training various neural networks in different tasks.
AM a sequence acceleration method scientific computing [5) It is widely used to accelerate the slow convergence of nonlinear fixed-point iterations arising in computational physics and quantum chemistry, c.g. the self-consistent field iteration in electronic structure calculations [16] 8), where the function evaluation is costly. It turns out that AM is closely related to multisecant quasi-Newton methods in nonlinear problems [4] 5 or the GMRES method [46] in linear problems [59 41]
Inspired by the great success of AM in accelerating fixed-point iterations, it is natural to ask whether AM can be applied to accelerate nonlinear optimization since the gradient descent with constant stepsize is fixed-point iteration. This idea has been explored in [1), but the proposed Regularized Nonlinear Acceleration (RNA) method built on the minimal polynomial extrapolation (MPE) approach (5) a sequence transformation method that has subtle difference from AM. Also, their methods rely heavily on the contraction assumption of the exed-point map and the strong convexity. For AM, although current research has proved local linear convergence of AM for fixed- exed-pointt iterations under some conditions [56 3), there exists no version of AM that guarantees convergence for nonconvex optimization, let alone stochastic optimization.
In this paper, we develop stochastic version of AM. Due to the nonconvexity and noise inside the problems and lack of line search or trust-region, a straightforward migration of AM to nonconvex stochastic optimization is infeasible. As a result, we make several fundamental modifications to AM. We highlight the main contributions of our works as follows:
1. We develop a stochastic version of AM, namely Stochastic Anderson Mixing (SAM), by introducing damped projection and adaptive regularization. We prove its almost sure convergence to a stationary point and analyze its work complexity. When a randomly chosen iterate za is returned as the output of SAM, we prove that the worst-case S.F--calls complexity to guarantee E (z < i O (c (c.). (See Theorems
2. We give a variance reduced extension of SAM by borrowing the stochastic variance reduced gradient (SVRG) (28 technique and analyze its SFF--calls complexity. (See Theorem 5 We also propose a preconditioned mixing strategy for AM and obtain the preconditioned SAM method which can empirically converge faster or generalize better. (See Section 2.3
3. Extensive experiments on training Convolutional Neural Network (CNN), ResNet, WideRes- Net, ResNeXt, DenseNet, and LSTM on different tasks and datasets show the faster con- vergence or better generalization ability of our method compared with the state-of -fhthe-rtt methods. (See Section
Onne call to the SFO in evaluation of fE. (z) in is counted one SFF--all..

---

2 Methodology
2.1 Anderson Mixing
AM is proposed for acceleration of fixed-point -oint iterations. We assume the fixed-point iteration is def [(xx)) Then g(*x) Ik = rk- Here, we adopt the
Ik+1 g(xx)) def description of AM in [94. Let A denote the forward difference operator, say, Ark Ik+1 Tk- Let X3 and R3 record the most recent mmmm S k) iterations:
Tik + rk. where т
X Azk-m Ark-m+1. Az R = AArk-m, Ark-m+1," Ark-1l.
(3)
AM can be decoupled into two steps. We call them the projection step and the mixing step:
ã = Ik X.T'As
(Projection step)
(4a)
1k+ Ix + BETRS
(Mixing step)
(4b)
where 5% is the mixing parameter, and Fg def
Fh
R&T k is reminiscent of extragradient 30 L' is
determined by solving
Ie arg min Ir R12
(5)
TER
Combining
4aa and 4b), we obtain the full form of AM 14
42
Tk-1 I& + BATE (Xx + 3r Ru) ls.
(6)
Remark 1. To see the rationality of AM, we assume f is twice continuously differentiable. Then quadratic approximation of f implies f (xz z)-1) 2 V ([f,,)-((zjj-i) in a local small region around so it is reasonable to assume R& ~ f(x)( X Thus we see ||r: - R 2|2 z I|r + V2 xx,x) Hence, we can recognize (5) as solving V f(x))p= = [f(x) in a least- squares sense, where ps: X. When the quadratic approximation is exact, solving ( is minimal residual procedure, thus being verified as a residual projection method 147.. Moreover, let H₁ be the solution to the constrained optimization problem [14]
min || -3x subject to H = -X.,
1.++1 = Ig HyTK, which indeed a multisecant quasi-Newtor method. Note that a key simplification in AM using differences of historical gradients Rg to approximate V22 (Ix)
then iterate (6
which reduces the heavy cost to compute recstrr products 7 19 26
2.2 Stochastic Anderson Mixing
We describe our method Stochastic Anderson Mixing (SAM) in this section. the k-th iteration, let Sk C [7] (1,2,.... .., T} be the sampled mini-batch and the corresponding objective function value is Ss. (xx)
EiEs. (Tx). Then тą Ss,, (ar) and the noisy R& is defined correspondingly (ef. (3)). Due to the instability and inaccurate estimation of Rą, stabilize the projection step by proposing damped projection and adaptive regularization techniques. Algorithm sketch of method. Now, we elaborate the mechanism of this algorithm.
Damped projection. From Remark 1
we see the determination of T& in (5) relies on the local quadratic approximation of (2). which can be rather inexact in general nonlinear optimization. To improve the stability, we propose damped projection method for (4a). Let og be the damping parameter, we obtain In via
T3 = (1 og) + ax(xx XxT+)) = Ik XTTx
(8)
Combining and (4b) and noting that i = Tkk or Rs k. the new iterate 2x41 given by
F&+1 = 3t + BRrK - as (X₁ + Rx l'g-
is worth noting that Bn and og in 9 behave like stepsize or learning rate in SGD, and the extra term (a + 3. Rx) I' can be viewed as generalized momentum term.

---

Algorithm Stochastic Anderson Mixing (SAM)
Input: zu E R m 10, 04 = 1, = 1, E (0, 1), mar
mar_iter _iterrrrrrr > 0.
Output: x E Rdd
1: for = 0. 0.1..... max iter do
2:
1 fs, (mx)
3:
if k = 0 then
4:
26+1 2k + Bark
5:
else
6:
my min(m {m, k}
7:
X = - Ark
A
8:
R2 [rr-ma - m Ark-1
9:
Check Condition (4 and use smaller og if (4 is violated.
2k++1 2g Bark Xx + ag R&) (RE Rx. + on x Xx) RETx
11: end if'
Apply learning rate schedule of or. 3k
13: end for
return 2*
Adaptive regularization. Since R& may be rank deficient and safeguard method is used in AM,
the least squares problem (5) can be unstable. A remedy is to add regularization [6] to (5). One well-known choice is the constant regularization introduced in [50 [53] which can be viewed as forcing [T&lll2 to be small [53]. leading to a penalty term to (5):
I' arg min ||r TER
R + 8
(10)
where 5 > O is the penalty constant. The solution of TO is r (Ri Rg + 87)² RI rk, where "f" denotes the Penrose-Moort inverse. This regularized variant of AM is named as RAM and serves as baseline in the experiments.
Here, we propose new regularization, namely adaptive regularization, to better suit the stochastic optimization. Since - - k Σg 2Ą denotes the update from to Eg. large magnitude of ||X&T&ll2 tends to make the intermediate step Fg overshoot the trust region around rg. Thus is more reasonable to force | rather than | to be small. We formulate this idea as
min
||r R 1 6x 1
(11)
where 6g 0 is variable determined in each iteration. Explicitly solving leads
F& (R. R4 6xXX R rk.
(12)
We call AM with this regularization and damped projection as SAM, i.c. the prototype algorithm given Algorithm !
Positive definiteness. From 9 and 12 the SAM update is Øk+1 = 2 + HĄTK. where Hd 3 - og Y ng. n. Yg X + 3x Rs. Z RH R& + og X Xg. Hy is generally not symmetric. A critical condition for the convergence analysis of SAM is the positive definiteness of Hg, i.c.
Pk H&PE 2 Berllea Vpk E Rd.
(13)
where μ E (0, is constant. Next, give approach to guarantee it.
Let Amin() (.) denote the smallest eigenvalue, Amaz() (.) denote the largest eigenvalue. Since Po HEPE PP (H& H )pk. Condition 13 equivalent Amin (2 (H₂ HT)) Z BaJl. With some simple
algebraic operations, we obtain Xmin (1 (H + HF))
8x 2 Am (Y: Z RÊ
R
def Let A Xmax R. RYZ ), then Condition
13 is cquivalent to
Ax < 28 4).
(14)
To check Condition
14p. note that
d = Amaz
(Ko
Rs)
z
0
z
0
pT
k
= Amaz
RT
(Yu
R
z!
0
2
) (15)
0

---

Algorithm 2 Stochastic Anderson Mixing with variance reduction (SAM-VR)
Input: uy E Rd; Br at; o6 for SAM 1AM_update(Ht) gf); Batch size n 2 1.
Output: x E Rdd
1: for = 0...., N do
2:
z6 8g
Vf(5x) = T Σ (āx)
3:
4:
for = O,...... U,....9-- do
5:
Sample subset K. S [2] with |K] =
6:
of v.(((at)) (+x Vfxx) where Vfc(=,)= IN) Eiex (xf)
7:
of41 SAM Luddutedaaaa
8:
end for
9:
Set #x+1 x
10:
end for
return Iterate chosen uniformly random from ((x))==0 N-1
0
z 0
Since Y Ra),
2 2m and m < d, A can be computed efficiently,
%
say, using an eigenvalue decomposition algorithm with the time complexity of O(m²). This cost negligible compared with those form X Xg, R Rg. After that, to guarantee the positive definiteness, we check if og satisfies (14) and use smaller if necessary.
AdaSAM method. We choose the 8% 111 as
6% max
C2
(16)
|ate
where Ci,02,e e constants. Such choice reflects the curvature change in the vicinity of .r. A large ||x ll indicates potential dramatic change in landscape, suggesting using a precautious tiny stepsize. The denominator in (16) behaves like annealingg which can measure the noise in gradients like that in secant penalized BFGS (7)..
2.3 Enhancement of Stochastic Anderson Mixing
We introduce the variance reduction and preconditioned mixing techniques to further enhance SAM.
Variance reduction. Variance reduction techniques turn to be effective if
the full dataset is feasible [4]. Similar to GdLBFGS-VR proposed in [60], we also incorporate SVRG SAM, which we call SAM-VR (Algorithm 2}. for solving ( To simplify the description, denote one iteration of SAM in Algorithm as SAM update (hh gk), i.c. one update of In given
the gradient estimate 9k-
Preconditioned mixing. Motivated by the great success of preconditioning in solving linear systems and eigenvalue computation [18), present preconditioned version of SAM. The key modification
is the mixing step 4b).. We replace the simple mixing FK+1 Th + 3y7e with #&+1 Ty
M Fxk
where Mj approximates the Hessian. Combining with (8) and (12) we obtain
Zk+1 I& [M ag (Xx M R&) RR R4 + 8 Xx)
R Tk.
(17)
Setting O&k = and 6% = 0. reduces to preconditioned AM update, which can recast as the solution the constrained optimization problem: min || M, '1 subject HyR, -X,,
a direct extension of 7 This preconditioned version of AM related to quasi-Newton updates 20 We also point out that the action of M can be implicitly done via an update of any optimizer at hand, i.e. 11+1 optimn(Tx. -Fx), ), where optèm updates Zs given the extragradient -Fx. If Rs = - [xx( Xx, which the case deterministic quadratic optimization, the projection step in preconditioned AM is still a minimal residual procedure.
Remark 2. The same as SdLBFGS (60), SAM needs another 2md space to store X₃ and RR- The extra main computational cost for SAM compared with SGD is O(m² d) O(m²), ) which accounts for the matrix multiplications (IR mB nxd x [dxmm) and matrix decomposition of small mmxm matrix.
5

---

Since dense matrix multiplicatiin can be ideally parallelized and the cost of gradient evaluations often dominates the computing, the benefit from SAM pays for this extra cost. Also, this cost can be further reduced to ((md) + Omm²) (see Appendix B.2g. In our implementation, we incorporate sanity check of the positive definiteness, alternating iteration and moving average, and the details are given in the supplementary materials.
3 Theory
In this section, we analyze the convergence and complexity of SAM. All the proofs are deferred to the Appendix A.1 We first give two assumptions about the objective function f that are widely used
in stochastic programming 17 60 44).
Assumption 1. / Rd TR is continuously differentiable. f(x) 2 flow 00 for any x TR.. f is globally L- L-Lipschitz continuous; namely [[V ff())ll L||x y112 for any 2, Rd.
Assumption 2. For any iteration k, the stochastic gradient fea (mx) satisfies Ess, fex (a+)] = f(xx), Eg, [Il fę. (mx) - fxx))] S o², where a > 0, and Êk, k = 0, 1, l..... are independent samples that are independent of {x,}}=>
Throughout analysis, we always assume both Assumptions I and 2 hold. Moreover, state the following conditions about the three parameters ag Bb, 6₁ of SAM.
+00
BR +00,
+00
(18a)
5% 2 CB as E [0, min 82 }] and statisfies (14),
(18b)
where C' > 0 is a constant.
Convergence and complexity. We give the convergence of SAM by analyzing the iterations {xx} generated by Algorithm
Theorem 1. Let { be the sequence generated by Algorithum with fixed batchsize n. Given positive constant C, if 8k E (0, 41<144-11)) then under the conditions (1aa) and (8b)), it has
lim [[V]())) with probability 1.
(19)
Moreover, there exists a positive constant M, such that
[[f())) S M, Vk.
(20)
Theorem 2. Under the same conditions as Theorem 7 if we require that the noisy gradient is bounded, i.e.,
Ege (1) V Sc. (1x) S Mg
(21)
where Mg > O is a constant, we have
lim Vf(xx) with probability 100
(22)
Now, we give the iteration complexity of SAM.
Theorem 3. Let {ax} be the sequence generated by Algorithm with batchsize n. Given constants
C> 0 and r E (0.5, 1), choose By A111-C 17 (ks + 1) Under the condition (18b), it has
N
16L(1 + C - plow)
N +1+1 1- (N- rN-1)
E [
N
12
r)n
k=
(23)
where n the batchsize, and N is the iteration number. Moreover, for given c E (0, 1), to guarantee that 1/4 -N BlV < the number of iterations N needed is at most O(E 1-r).
If the output R randomly chosen from previous iterates according to the certain probability distribution, SAM has the same complexity (2) as RSG [7] and SQN [60].

---

Theorem 4. Let { be the sequence generated by Algorithum D with batchsize n and xR be the random output of the first N iterations where the random variable R follows the uniform distribution
(R(k) def Prob k} 1/N. Given constant C O, we choose 3y: 41((+C-1] and assume condition T8b holds. For any c > O, there exist some n. and N = O/n such that we have E [ S 6, where the expectation is taken with respect to R and {
In fact, from the proof of Theorem 4 can find the explicit choice of the batchsize. Define Dj def f(xo) flow and D is problem-independent positive constant. The batchsize n can be
chosen as n min N,, max 1, 1 A 3111 where N is the total number of SFO-calls satisfying
[
N max
Ci 4C2 a² and C1 32D, HDVD
+I+ D. 32D,L(1+C"))
1.7
#²
Thus, to ensure E [(x))]) Se. the total number of SFO-callss is O(E (c)-)). Moreover, we give the SFO-calls complexity of the variance reduced version of SAM.
Theorem 5. Let x be the output of Algorithm 2 with batchsize n. Given positive constant C, suppose v. μuu E (0,1) 1) to be two constants satisfying
2po + 10 1)m
Pol
2pmn
2 v
2(1 2(1+C-1J10
L
where is the Euler's number. Set BC B:= M(+C and satisfies
171777773 8 CB-2, 2, of E (0, min (1, [t
(14) and the number of iteration q
T
where do = 6 + 111-0-1117 Then,
Mondo
T2/3 (f(zo) - plow)
E [
(24)
qNnv
To ensure E [ [IV S e, the total number of SFO-calls is O(T + (T2/3
Remark 3. It is worth noting that the approximated Hessian Hy in SAM depends on the data samples (EihiEs, of the current mini-batch, which violates the assumption AS.4 in (60).
Analysis of AdaSAM. All the results in Theorems 55 are applicable for AdaSAM as (6 satisfies
the condition (8b). We further discuss the rationality of the first term in (16). Since rg HArK 2
Buul|ral1 and Hark ll < 2 (B) og ||rx112 < 2 (1 (1+ C || 12 if or I 1, 2 O
(see Corollary D in Appendix A.Ip. it is sensible to suppose || 2k-1 |l2 2 | - 2xl12 =
|Harrll2 hg [12ll22 where he E (0, h) (h- < +00) is related Hy. Therefore.
Ci ||x
Ci I
2 h 3
(25)
| z
which coincides with the requirement that 8, 2 Cp 2, A further discussion is in Appendix D.3
4 Experiments
We used AdaSAM (AdaSAM-VR) for the experiments, which is a special case of SAM (SAM-VR) with du specified as (6)). The pscudocodes are given in Appendix B. To evaluate the effectiveness of
our methods, we compared them with several first-order and second-order optimizers for mini-batch training of neural networks on different machine learning tasks. The datasets were MNIST [32].
-EFAR-10/CIFAR 100 [31 for image classification and Penn Treebank [35) for language model.
The experimental details and hyper-
hyper-paramedt parameter tuning are referred to Appendix C
Experiments MNIST. We trained a simple convolutional neural network (CNN) on MNIST, for which we were only concerned about the minimization of the empirical risk ( i.e. the training loss, with large batch sizes. The training dataset was preprocessed by randomly selecting 12k images from the total 60k images to facilitate large mini-batch training. Neither weight-decay nor dropout was used, We compared AdaSAM with SGDM 4K (SGD with momentum), Adam [29]. SdLBFGS 60)
and RAM (cf. (TO). ). The learning rate was tuned and fixed for each optimizer. The historical lengths
for SdLBFGS, RAM and AdaSAM were set as 20. 10 for RAM and e₁ = 10-4 for AdaSAM.
Based on the official PyTorch hoppeeattttttoeeoooooooooooooood
7

---

Than Lon
ABIGAA-4
(a) Batchsize=6K
(b) Batchsize=3K
(c) Variance reduction
(d) Preconditioning
Figure I: Experiments on MNIST. (a) Train Loss using batchsize 6K; (b) Train Loss using batchsize
3K; (c) AdaSAM with variance reduction; (d) Preconditioned AdaSAM with batchsize 3K.
Figure [ (a) and (b) show the curves of training loss when training 100 epochs with batch sizes of 6K and 3K, which indicate that AdaSAM can significantly minimize the empirical risk in large mini-batch training. The comparison with RAM verifies the benefit of adaptive regularization. We notice that there hardly exists any oscillation in AdaSAM during training except for the first few epochs, which suggests that AdaSAM is tolerant noise. We also tested the effectiveness of variance reduction and preconditioning introduced in Section 2.3 The variance reduced extension AdaSAM VR was compared with AdaSAM for different batch sizes. The variants of AdaSAM preconditioned by Adagrad [12] and RMSprop [55] are denoted as Adagrad-Adaz AdaSAM and
respectively. Though AdaSAM-Va VR more costly per iteration and the preconditioned variants seem to deteriorate the final training loss, we point out that AdaSAM-VE AM-VR can achieve lower training loss (10 9) and the preconditioned variants converge faster an acceptable training loss (e.g. 10 10-3).
Table 1: Final TOPI test accuracy (mean + standard deviation) (%) on CIFARIO/CIFARIO, The bold numbers highlight the best results. WideResNet abbreviated as WResNet.
CIFARIO
CIFARIOD
Method
ResNet18
ResNet20
ResNet32
ResNet44
ResNet56
WResNet
ResNet18
ResNeXt
DenseNet
SGDM
94,82.1.15
92.031.16
92.86.1.15
93. 93.1011.33
93.47.1.28
94,90..09
71.271.09
78.411.54
78.491.112
Adam
93.03+-07
91.17+.13
92.034-28
92.28+-62
92.394-23
92.45+-11
7241--17
73.574-17
70.80-223
AdaBelief
94.65+.13
01.15+21
92.15
92.79+.24
93.30-1.7
94,46t.13
76.25=.06
78.274..1
78.83=.15
I Lookahend
94.92++.55
92.07+044
92.864-15
93.26+.24
93.36++.13
94.90+-15
77.63-.35
78.934-12
79.37+.16
AdaHession
94.36+t.9 09
91.92.322
92.184.18
92.744.11
92.40-1.06
94.04+.12
76.59=.42
RNA
93.45:121
90.732.122
91.081.51
91.612.37
91.23:1.4
93.85..24
75.12=.39
75.70..49 40
RAM
95. 10:
02.21
93.05:t.33
93.42t.13
93.76-t.16 16
95.044.09
16.19-
78.65: 20
78 28
AdaSAM
95.171.10
92.432.19
93.224.32
93.57:.14
93.77..112
95.231.07
78.13=.14
79.311:27
80.09
Experiments on CIFAR. For CIFAR-10 and CIFAR- 100, both datasets have 50K images for training and 10K images for test. The test accuracy at the final epoch was reported as the evaluation metric. We trained 8/203//1//0033//444/5 [21] and WideResNet16 [64
SGDM: asodh-do
SGDM 120
SCDM
109
Lostahradt:
Lookahred:: epach-1.20
Lookahead:: epoch-1ec
on CIFAR-10, and ResNet18, Rt5NeXt50 61 and
Test Loss
AduSAM spoch-dd
DenseNet121 24 on CUFAR-100. The baseline op-
AdaSAM c2och-120
AdwGAM
timizers were SGDM, Adam, AdaBelief (66), Looka-
633 and RNA (52). The hyper- parameters were kept unchanged across different tests. We trained 160 epochs with batch size of 128 and de- cayed the learning rate at the 80th and 120th epoch. For AdaSAM/RAM, ag and 3r were decayed at the 80th and 120th epoch.
head 65 AdaHessian
23
80
300
1200
3.52
epochs
Table I demonstrates the generalization ability of AdaSAM (AdaHessian ran out of memory for training ResNeXt50 and DenseNet121). It shows AdaSAM con- sistently outperforms other optimizers for various neural networks CIFAR 10/CIFAR 100. Compared with quadratic model extrapolate historical iterates more elaborately, which may account for its effec- shows tiveness. We also conducted tests training for 120 epochs and 80 epochs. Figure shows AdaSAM
Figure 2: Test loss of training ResNet18 on CIFAR-10.
AdaSAM is built on a noisy

---

Table 2:
The memory and computation cost compared with SGDM and AdaHessian. Memory, per-epoch time and total running time are abbreviated as "m", "u"e" and "t", respectively.
Cost
CIFARTO/WRan (1F
CIFAR N0150
CIFAR 21
(x SGDM)
m
tlc
m
t/c
1
m
t/e
m
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
AdaHessian
1.78
3.59
3.59
2.35
5.97
5.97
>1.
518
AdaSAM
1.14
1.34
0.83
1.26
1.28
0.80
1.30
1.16
0.58
1.16
1.19
0.60
can achieve comparable or even lower test loss than SGDM/Lookahead when training with fewer epochs, thus saving a large number of iterations. More results can be found in Appendix C.3
To compare the total training time, we SGDM the baseline and terminated the training of AdaSAM when the accuracy difference AdaSAM - SGDM > -0.05%. The memory, per-epoch computational cost and total training time of training ResNee20/VideeeeNeel11 (abbr. WResNet) on CIFARIO 10 and ResNeX(55/DenseNee12 on CIFAR 100 are reported in Table 2 It shows AdaSAM is more efficient than AdaHessian and saves more than 15% training time than SGDM these models.
110-
Valiaaiion
45
50
25
50
100
:25
150
175
200
25
50
500
125
150
335
200
30
25
50
389
125
150
175
200
(a) 1-Layer LSTM
(b) 2-Layer LSTM
(c) 3-Layer LSTM
Figure 3: Experiments on Penn Treebank. Validation perplexity training 1,2,3-Layer LSTM.
Experiments on Penn Treebank. We trained LSTM [22] on Penn Treebank and reported the perplexity the validation set in Figure and perplexity on the test set in Table where
Table 3: Test perplexity on Penn Treebank for 1,2,3- layer LSTM. Lower is better.
PAdaSAM denotes the variant of AdaSAM preconditioned by Adam. The experimental setting the same that in AdaBelief [66]. In our practice, we found that the vanilla AdaSAM with default hyperparameter setting is not suitable for this task. Nevertheless, a suitable preconditioner (e.g. Adam) largely
Method
I-Layer
2-Layer
3-Layer
SGDM
85.211..6
67.12
61.561.144
Adam
80.88:1.15
64.541.18
60.341.22
AdaHelief
82.41+.46
65.07+.02
60.64+.14
Lookahead
82.01
66.4311.3
61.80
pAdaSAM
79.34:1.09
63.18:1.22
59.471.008
improve the behaviour of AdaSAM. Conversely, AdaSAM can also enhance optimizer when the latter is used as preconditioner.
Discussion
In this section, we provide discussions that compare SAM with SQN 660 and SGD.
SAM versus SQN. Our theoretical results are similar to those of SQN 60 but there are some fundamental differences:
(i) The basic assumptions different. (a) Recall that the update is 26+1 I& H&gs. where Sk-1) denote the random samplings in the first & iterations. key assumption in [60] that H₃ depends only on Sj--1]- which guarantees EJ S. Spp-1l = H& V (xx) that can simplify the proof. In contrast, in our methods SAM and SAM-VR, H₃ depends on Sş since гą -9t participates in constructing H2, thus violating this assumption and complicating our analysis. (b) The proposed algorithm SdIBBFGS (60) needs twice continuously differentiable assumption of f and the boundedness of 2 which not required in our algorithm.
fk V fss (It)). Let Si--1 ==

---

(ii) The ways to construct the secant equations are different. In the deterministic case, secant equation is H yk- where Sj: Ih 2k-1 and yk = 9t 9k-1. 1. In the stochastic case, various choices exist in forming yk- For SAM, the choice of ys is the same as that of the deterministic case, thus making H₂ depend on Sg. For the SQN methods in [60]. y = Vis... (xx²) V ( which ensures H₃ is independent of Sg. Such choice can reduce variance of noise in secant equations but demands evaluating gradients on the same mini-batch S twice. Some other SQN methods 7 use subsampled Hessian-vector products to form y/s- V fa (2t Ik-1), where Sj denotes the data samples independent of Sk, which also ensures H& is independent of Sy.
SAM versus SGD. We compare SAM with SGD from theoretical and practical perspectives.
(i) Theoretical perspective. (a) For general nonconvex stochastic optimization, SAM achieves the same worst-case complexity O(1/E*) e² SGD. (b) There are some specific cases that SAM can be theoretically better than SGD. For strongly convex quadratic minimization, we prove that SAM is essentially equivalent to GMRES (see Appendix A.2)) that can exhibit superlinear convergence [58] For nonlinear optimization, SAM can also have superlinear convergence rate some cases as is closely related to the multisecant quasi-Nees quasi-Newton method [14). as also pointed out in Remark T
(ii) Practical perspective. (a) With the same number of epochs as SGD,
shown in Table I and
Table 3 that our method has better generalization performance than SGD in both image classification and language tasks. (b) Our method can largely reduce the number of epochs to achieve a comparable solution as SGD,, as shown in Figure 2 in Section | and Figure g in Appendix C.3 The total running time can reduce correspondingly. as shown Table (c) SAM needs additional memory and computational cost, but it is still much more efficient and economical than other second-order optimizers, as shown Table in Section 4 and Figure 22 in Appendix D.8
Table 4: Comparison between SAM and SGD. '+' (+-) means SAM is better (worse) than SGD, and means SAM is similar to SGD.
Criterion
general
specific
memory
time/epochs
epochs
time
generalization
SAM vs. SGD
Based on the above analysis, we summarize the comparisons of our method and SGD in Table There 7 types of criterion. "general": the worse-case complexity in nonconvex stochastic optimization: "specific": some specific problems; "memory": memory usage; "time/epochs"; per-epoch running time; "epochs" and "time": the total epochs and running time achieve comparable test performance as SGD: "generalization" test performance with the same number of epochs as SGD.
6 Conclusion
In this paper, we develop extension of Anderson mixing, namely Stochastic Anderson Mixing, for nonconvex stochastic optimization. By introducing damped projection and adaptive regularization, establish the convergence theory of our method. We also analyze its work complexity in terms of SFO-calls and show it can achieve the O(1/e²) complexity for an e-accurate solution. We also give specific form of adaptive regularization. Then propose enhance our method. One is the variance reduction technique, which can further improve the work complexity of our method theoretically and help achieve lower empirical risk in experiments. The other one is the preconditioned mixing strategy that directly extends Anderson mixing. Experiments show encouraging results of our method and its enhanced versions in terms of convergence rate or generalization ability in training different neural networks in different machine learning tasks. These results confirm the suitability of Anderson mixing for nonconvex stochastic optimization.
techniques to further
Acknowledgments and Disclosure of Funding
This work was supported by the National Key R&D Program of China (No. 2018YFB 1005103), Technology and Innovation Major Project (No. 2020AAA0108440) National Natural Science Foun- dation of China N196619,,,,,, No. 61772302, No. 119013388 338) and Huawei Noah's Ark Lab. We thank all anonymous reviewers for their valuable comments and suggestions on this work.
10

---

References
[1] Zeyuan Ahu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference machine learning, pages 699-707. PMLR, 2016.
[2] Donald G Anderson. Iterative procedures for nonlinear integral equations. Journal of the ACM (JACM), 12(4):547-560, 1965.
[3] Wei Bian, Xiaojun Chen, and CT Kelley. Anderson acceleration for class of nonsmooth fixed-point problems. SIAM Journal on Scientific Computing, (0):S1-S20, 2021.
[4] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-3) 2018. doi: 10.1137/16M10001173. URL
https://doi. 1ttg//....o 1137 1137/16M10888777
[5] Claude Brezinski, Michela Redivo-Zaglia, and Yousef Saad. Shanks sequence transformations and Anderson acceleration. SIAM Review, 60(3))646 (63)6,66666, 2018.
[6] Claude Brezinski, Stefano Cipolla, Michela Redivo-Zaglia, and Yousef Saad. Shanks and Anderson-type acceleration techniques for systems of nonlinear equations. arXiv preprint arXiv:2007.05716, 2020.
[7] Richard H Byrd, Samantha Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi- Newton method for large-scale optimization. SIAM Journal Optimization, 26(2):1008-1031, 2016.
[8] Eric Cancès and Claude Le Bris. Can we outperform the DIIS approach for electronic structure calculations? International Journal of Quantum Chemistry, 79(2):82 90, 2000.
[9] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. In International Conference Learning Representations, 2018.
[10] Kai Lai Chung. On stochastic approximation method. The Annals of Mathematical Statistics, pages 463-483, 1954.
[11] Jing Dong and Xin T Tong. Replica exchange for non-convex optimization. Journal of Machine Learning Research, 22(173):1-59, 2021.
[12] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[13] Rick Durrett. Probability: Theory and examples, volume 49. Cambridge university press, 2019.
[14] Haw-ren Fang and Yousef Saad. Two classes multisecant methods for nonlinear acceleration. Numerical Linear Algebra with Applications, 16(3):197-221, 2009.
[15] Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning, volume 1. Springer series in statistics New York, 2001.
[16] Alejandro J Garza and Gustavo E Scuseria. Comparison of self-consistent field convergence acceleration techniques. The Journal of chemical physics, 137(5):0541 10, 2012.
[17] Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[18] Gene H Golub and Charles F Van Loan. Matrix computations. 4th. Johns Hopkins, 2013.
[19] Robert Gower, Dmitry Kovalex, Felix Lieder, and Peter Richtárik. RSN: Randomized subspace Newton. In Conference on Neural Information Processing Systems, 2019.
[20] Robert M Gower and Peter Richtárik, Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. SIAM Journal on Matrix Analysis and Applications, 38(4):1380- 1409, 2017.

---

[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[22] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8); 1735-1780, 1997.
[23] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[24] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 4700-4708, 2017.
[25] Shaojun Huang, Yuanzhang Sun, and Qiuwei Wu. Stochastic economic dispatch with wind using versatile probability distribution and L-BFGS-B based dual decomposition. IEEE Transactions on Power Systems, 3366)6655-6663.3 2018.
[26] Xunpeng Huang. Xianfeng Liang. Zhengyang Liu, Lei Li, Yue Yu, and Yitan Li. SPAN: A stochastic projected approximate Newton method. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1520-1527, 2020.
[27] Brian Irwin and Eldad Haber. Secant penalized BFGS: A noise robust quasi-Newton method via penalizing the secant condition. arXiv preprint arXiv:2010.01225, 2020.
[28] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-323, 2013.
[29] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
[30] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[31] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[32] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 96(11):2278-23) 1998.
[33] Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2019.
[34] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in Neural Information Processing Systems, 32:1 1167--11685 2019.
[35] Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building large annotated corpus of English: The penn treebank. Computational Linguistics, 19(2):313-330, 1993.
[36] James Martens. Deep learning via Hessian-free optimization. In Proceedings of the 27th International Conference on Machine Learning, pages 735-742, 2010.
[37] Aryan Mokhtari and Alejandro Ribeiro. Stochastic quasi-Newton methods. Proceedings of the IEEE, 199611)9906-1922 2020.
[38] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4): 1574-1609, 2009.
[39] Boris T Polyak. New stochastic approximation type procedures. Automat. Teleemeh, 7(98-107):
2, 1990.
[40] Boris T Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging.
SIAM journal control and optimization, 30(4):838 -555, 1992.
12

---

[41] Florian A Potra and Hans Engler. A characterization of the behavior of the Anderson acceleration on linear problems. Linear Algebra and its Applications, 13003)1100221011, 2013.
[42] Phanisri P Pratapa, Phanish Suryanarayana, and John E Pask. Anderson acceleration of the Jacobi iterative method: An efficient alternative Krylov methods for large, sparse linear systems. Journal of Computational Physics, 306:43-54, 2016.
[43] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12(1):145-151, 1999.
[44] Sashank J Reddi, Ahmed Hcfny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pages 314-323, PMLR, 2016.
[45] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[46] Youcef Saad and Martin Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientific and statistical computing, 7 (3)8856-86,, 1986.
[47] Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
[48] Jerome Sacks. Asymptotic distribution of stochastic approximation procedures. The Annals of Mathematical Statistics, 29(2):373-405, 1958.
[49] Nicol N Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-Newton method for online convex optimization. In Artificial intelligence and statistics, pages 436 443, 2007.
[50] 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.
[51] Damien Scieur, Francis Bach, and Alexandre d' Aspremont. Nonlinear acceleration of stochas- tic algorithms. Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3985-3994, 2017.
[52] Damien Scieur, Edouard Oyallon, Alexandre d' AAppremont, and Francis Bach. Nonlincar acceleration of CNNs. ICLR Workshop track, 2018
[53] Damien Scieur, Alexandre d' Aspremont, and Francis Bach. Regularized nonlinear acceleration. Mathematical Programming, 179(1):47-833 2020.
[54] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algorithums. Cambridge university press, 2014.
[55] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2): 26-31, 2012.
[56] Alex Toth and CT Kelley. Convergence analysis for Anderson acceleration. SIAM Journal on Numerical Analysis, 53(2))805-819, 2015.
[57] Alex Toth, J Austin Ellis, Tom Evans, Steven Hamilton, CT Kelley, Roger Pawlowski, and Stuart Slattery, Local improvement results for Anderson acceleration with inaccurate function evaluations. SIAM Journal on Scientific Computing, 39(5):847-665, 2017.
[58] Henk A Van der Vorst and Vuik. The superlinear convergence behaviour of GMRES. Journal of computational and applied mathematics, (8(3):3377331) 1993.
[59] Homer F Walker and Peng Ni. Anderson acceleration for fixed-point iterations. SIAM Journal on Numerical Analysis, 1954):1715-1735, 2011.
[60] Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-Newton methods for nonconvex stochastic optimization. SIAM Journal Optimization, 27(2):27-9966, 2017.
13

---

[61] 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 on computer vision and pattern recognition, pages 1492-1500, 2017.
[62] Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of Langevin dynam- ics based algorithms for nonconvex optimization. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 3126-3112 3137, 2018.
[63] 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.
[64] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. British Machine Vision Conference 2016. British Machine Vision Association, 2016.
[65] Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey E. Hinton. Lookahead optimizer: steps forward, step back. In Advances Neural Information Processing Systems, pages 9597-9608, 2019.
[66] Juntang Zhuang. Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan. Adabelicf optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33, 2020.
14


Reviews:
[{"review_id": "qPeFhVztp4S", "reviewer": "Reviewer_wnT6", "summary": "In this manuscript, the authors proposes a Stochastic Anderson Mixing (SAM) scheme to solve nonconvex optimization problems. Under the smoothness, unbiased gradient estimate with bounded variance assumptions, the authors show different variants of the scheme (SAM, SAM with variance reduction, Ada-SAM) have asymptotic and non-asymptotic convergence. Experiments on MNIST, CIFAR and Penn Treebank seem to show the superior performance over other baselines. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: \nTo the best my knowledge, the nonconvex Anderson mixing for nonconvex optimization does not appear in the previous literature.\n\nClarity:\nThe paper clearly states its contributions. I would also suggest the authors to create a table to compare the SAM-based approach with existing approaches in stochastic nonconvex optimization.\n\nSignificance:\nThis is my concern about this paper. \n\n1. The motivation of this paper is vague. What are the limitations of SGD and SVRG for nonconvex optimization that make Anderson-Mixing approach important?\n\n2. In my view, the SAM method (Algorithm 1) is worse than nonconvex SGD from every aspect. First, the convergence of nonconvex SGD does not require a large minibatch but it is required for SAM (Theorem 4). Second, Although SAM has the same iteration complexity compared with SGD, SAM has higher per-iteration time complexity (line 9 and line 10) and more memory (line 7 and line 8). I also doubt that it works better than SGD if the authors report running time in the experiments section (in section 4, only the loss versus epochs results are reported).\n\n3. For Algorithm 2 (SAM-VR), it basically mimics the result of [Reddi et al. 2016], but again, the per-iteration complexity is still worse than nonconvex SVRG, since SAM-VR calls SAM as a subroutine. Also the number of SFO calls should be $O(T+T^{2/3}/\\epsilon)$ in Theorem 5.\n\n4. In section 3.2, it is important to have a formal theorem describing the convergence of AdaSAM. The current description of this section is vague and I am not sure if it is correct.\n\nExperiments:\n\n1. As I mentioned, since SAM-based approach has high per-iteration complexity and requires more memory, I would suggest the authors to report the running time comparison. \n\n2. Only training loss results are reported. I understand the theory is only for the training loss, but test loss is also important for practitioners.\n\n3. In Figure 1, only large batch size experiments are reported. I understand that the goal is to make it somehow consistent with the large batch requirement in the theory. However, it is known that large batch ends up with worse generalization in machine learning. What is the performance of this algorithm if small batch size is used?\n\n4. In Figure 1(c), why AdaSAM-VR is used? What about the performance of SAM-VR? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "joAo40cSyhb", "reviewer": "Reviewer_bi9T", "summary": "The paper proposes a variant of Anderson mixing applied to a stochastic optimization problem. Convergence analysis is carried out and experiments show good results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The proposed method relies on damping and regularization. These techniques are very common in Anderson mixing (AM) methods due to the potential divergence of AM and the numerical instability when solving its subproblems. \n\nIn this paper, the positive definiteness of a matrix, acting like an approximate Hessian, is checked at every step. This allows the author(s) to obtain convergence guarantees, which are otherwise impossible for AM. The damping condition enforces the method to stay close to a stochastic descent method; when alpha_k is small (to satisfy condition (15)), we essentially take an SGD step. \n\nMy concerns are that:\n\n(i) since the stepsize beta is very small and is often reduced further as the algorithm proceeds, condition (15) enforces that alpha should tend to zero too. So, effectively we are just running SGD most of the time. It would be interesting to profile and see how often the Anderson step are performed compared to SGD.\n\n(ii) the rate does not show the benefit over SGD type methods that require much less memory footprint. I am not concerning the extra computations as they are just some matrix-matrix multiplications and GPUs are super efficient at this. However, the memory footprint is extremely important when it comes to training large models on GPUs. GPU's memory is very small compared to CPUs, and a single model would contain millions if not billions of parameters. The ADM method stores two extra matrices that would need 2*m times the memory required to store one model, which would be otherwise used to increase the mini-batch size and hence reduce the runtime.\n\nSome other comments:\n\nIn Algorithm 1, it is stated that beta_k = alpha_k = 1, but the conditions on Theorem 1, 2, 3 require beta_k -> 0. I believe it shoud be beta_0 = 1??\n\nTheorem 2 needs smoothness and boundedness of f + bounded variance and second moment of the gradients, which seems not very standard.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "59VXYdNbVlP", "reviewer": "Reviewer_v7Hn", "summary": "The paper proposes a stochastic Anderson mixing (SAM) scheme and its variance reduction version to solve nonconvex stochastic optimization problems. Extensive experiments are conducted to verify the efficacy of the proposed methods. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper provides promising results and the idea of using damped projection combined with adaptive regularization is new. I'm impressed with the experiments. \n\n1. Provide the (approximate) formula of $M_f$ in (20). This constant is important to visualize the rate of $1/N \\sum E || \\nabla f(x_k) ||^2$, see (23).\n\n2. How is the batch size $n_k$ in Theorem 4 estimated (see line 205) when $\\sigma$ in Assumption 2 is not easy to determine? \n\n3. Is the batch size in the experiments chosen following the theory? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "3DPYtc-zzaU", "reviewer": "Reviewer_TNM1", "summary": "The main idea of this paper is to introduce a stochastic Anderson mixing method which leads to faster convergence, accelerating the training. The main contribution of the paper is the convergence analysis part which gives the theoretical analysis of the proposed method. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Slow convergence is a notable and annoying problem during training, especially when training some nets with high complexity, such as GAN. The idea of using Anderson acceleration to improve the performance of the optimisation method is not novel, but I’m still impressed by the good performance of the AdaSAM. Actually, the core algorithm, using the damped projection and the adaptive regularisation, are not innovative enough. However, the convergence analysis and the abundant experiments shown the effectiveness of SAM, which gives me confidence.\nHere are some questions that I had during the reading:\nLine 41 - Why SAM is a second-order method? \nThe convergence analysis based on the assumption that f is continuously differentiable. Is it a realistic assumption? \nLine 86 Remark 1 - The fixed point assumption is necessary actually, promising the equation in line 87 holds when j,k->\\infinity.\nLine 184 - Why the eq. 19 promises the convergence of the original problem? Is it possible to be stucked in a local minimal?\nFigure 2: What is the training loss goes like when compared with Lookahead on CIFAR? \nFigure 7 in appendix: It seems that the training loss of AdaSAM fell behind that of SGDM, does it means that AdaSAM cannot saving training time in some cases?\nIt seems that the cases shown here only needs hundreds epochs to converge. How well does the SAM perform in the more time-consuming cases?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author(s) could extend the limitation part. Are there any situations where the convergence speed of SAM lags behind SGD? Could you please provide some specific analysis? So that readers can understand when to switch to SAM after reading.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The direction is novel and interesting, the analysis of a stochastic version of AM could be independently interesting. Even though the practical aspects are not the strongest, I recommend acceptance; in my opinion the results are of interest to the community.

The authors did generally a good job responding to reviewers questions resulting to one reviewer raising their score. 

There are legitimate arguments by one reviewer saying that there are no theoretical benefits of SAM over SGD (both achieve theoretical optimal, with SGD being simpler, less memory and computation-intensive). And I encourage the authors to include relevant discussion. 

Decision: Accept (Poster)