Towards Understanding Why Lookahead Generalizes Better Than SGD and Beyond
Authors: Pan Zhou
Hanshu YAN
Xiaotong Yuan
Jiashi Feng
Shuicheng YAN
Venue: NeurIPS 2021 Poster (2021)
Keywords: lookahead
excess risk error
deep learning optimization
deep learning generalization

Abstract: To train networks, lookahead algorithm~\cite{zhang2019lookahead} updates its fast weights $k$ times via  an  inner-loop   optimizer before updating its slow weights once by using the latest  fast weights. Any optimizer, e.g. SGD,  can serve as the inner-loop optimizer, and the derived lookahead  generally enjoys remarkable test performance improvement over the vanilla optimizer.  But theoretical understandings on the test performance improvement   of lookahead remain absent yet. To solve this issue, we theoretically justify  the advantages of lookahead  in terms of the excess risk error which measures the test performance. Specifically, we prove that lookahead using  SGD as its inner-loop optimizer can better balance the optimization error and generalization error to achieve smaller excess risk error than vanilla SGD  on (strongly) convex problems and nonconvex problems with Polyak-{\L}ojasiewicz condition which has been observed/proved in neural networks.   Moreover,  we show the stagewise optimization strategy~\cite{barshan2015stage} which decays learning rate several times during training can also benefit lookahead in  improving  its optimization and generalization errors on strongly convex problems. Finally, we propose a  stagewise locally-regularized lookahead (SLRLA) algorithm which sums up the vanilla objective and a local regularizer to minimize at each stage and  provably enjoys optimization and generalization improvement  over the conventional (stagewise) lookahead.    Experimental results on   CIFAR10/100 and ImageNet  testify its  advantages. Codes is available at  \url{https://github.com/sail-sg/SLRLA-optimizer}. 

Towards Understanding Why Lookahead Generalizes Better Than SGD and Beyond
Pan Zhou'
Hanshu Yan*
Xiao-Tong Yuan
Jiashi Feng"
Shuicheng Yan"
Sea Al Lab, Singapore
Nanjing University of Information Science & Technology. Nanjing, China {zhoupan, yanhanshu, fengjs, yanse) @ sea.com xtyuan @ nuist.edu.cn
Abstract
To train networks, lookahead algorithm [1] updates its fast weights & times via an inner-loop optimizer before updating its slow weights once by using the latest fast weights. Any optimizer, e-g. SGD, can serve as the inner-loop optimizer, and the derived lookahead generally enjoys remarkable test performance improvement over the vanilla optimizer. But theoretical understandings improvement of lookahead remain absent yet. To solve this issue, we theoretically justify the advantages of lookahead in terms of the excess risk eгror which mea- sures the test performance. Specifically, we prove that lookahead using SGD as its inner-loop optimizer can better balance the optimization error and generalization error to achieve smaller excess risk error than vanilla SGD on (strongly) convex problems and nonconvex problems with Volyak-Lojasien been observed/proved in neural networks. Moreover, we show the stagewise op- timization strategy [2] which decays learning rate several times during training can also benefit lookahead in improving its optimization and generalization errors on strongly convex problems. Finally, we propose a stagewise locally-regulariv lookahead (SLRLA) algorithm which sums up the vanilla objective and local regularizer to minimize at each stage and provably enjoys optimization and gener- alization improvement over the conventional (stagewise) lookahead. Experimental results on CIFARIO/ 10/100 and ImageNet testify its advantages. Codes available at https: gi thub. cww/coo////oo/oc commsaallee will-a saail-sg//ii SLRLA-optimize.
the test performance
condition which has
Introduction
Deep neural networks (DNNs) have been successfully applied to various applications, such as image classification [3-8], speech recognition [9-11], and classic games [12, 13]. Typically, their training models can be formally formulated as a finite-sum optimization problem:
ming Fs (0)
Σ :=1 L(f ();;0). v:),
(I)
where (ax y) is sample pair from an unknown distribution D, the loss (xx 0), y) measures the discrepancy between the prediction fæx; 0) parameterized by 0 and the target y, and n is the training sample number. Besides DNNs, the formulation (1) also encapsulates a large body of other problems, e.g., least square regression and logistic regression. Though many algorithms, e.g., variance-reduced algorithms [14-17] and adaptive gradient algorithms [ [18, 19], can solve problem (1), SGD [20, 21] is one of the most preferable algorithms because of its efficiency and good generalization [22].
In this work, we are particularly interested in the lookahead algorithm [1] for solving (1), Its core idea is to maintain two kinds of network parameters, i.e. "fast weights" and "slow weights" 0, and update them in turn. Specifically, in the inner loop, takes the slow weights 0 as warm-start
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

initialization and updates the fast weights k times to obtain iy using any vanilla optimizer; for the
outer loop, updates the slow weights as 0 (1 a) + av,, where a E (0. 1]. Any standard optimizer, e.g. SGD, Adam [18] and RAdam [23]. can serve as the inner-loop optimizer, and the derived lookahead algorithm generally enjoys remarkable test performance improvement than the standard optimizer [1]. Because of its simplicity and strong compatibility, lookahead has been widely used [24-29]. However, the theoretical reasons for the superiority in test performance of lookahead are rarely investigated, though heavily desired. Moreover, in practice, to train faster and generalize better, one often uses the stagewise optimization strategy [2], namely running a large learning rate at the beginning and geometrically decaying it several times during the following training. But for lookahead, the theoretical benefits of the stagewise optimization strategy still remain unclear.
Our Contributions. In this work, we provide theoretical viewpoint to understand the test perfor- mance improvement of lookahead, and also show the benefits of stagewise optimization strategy in lookahead. Moreover, we further propose new stagewise locally-regularin lookahead algo- rithm which provably enjoys faster convergence speed, smaller generalization error, and better test performance than conventional (stagewise) lookahead. Our contributions are highlighted below.
Firstly, we prove that on convex problems, lookahead using SGD as its inner-loop optimizer has optimization error ( ((=nk
am 7), where T and k respectively denote the outer- and inner-loop iteration numbers, and is the learning rate for the inner-loop optimizer, i.c. SGD. Then we prove that lookahead has generalization error bound O (mnAT) on convex problems with training samples. Since the excess risk error can well measure the test performance of an algorithm and is upper bounded by the sum of optimization and generalization errors, we can bound the excess risk error of lookahead with O annkT + 17 omkTT) ). When a 1, lookahead degenerates to vanilla SGD and has
excess risk error O WHT + + nkT Since the optimum of a in lookahead to optimally balance the optimization and generalization errors is often not one, lookahead can enjoy a smaller excess risk error than vanilla SGD. Similarly, on strongly convex problems and class of nonconvex problems that obey optimization and generalization errors and achieve smaller excess risk error than vanilla SGD. For PE. condition, it is observed /proved for deep learning models in [30-34] and our empirical results. These results well explain the better test performance of lookahead than SGD.
(PE) condition, our results also show that lookahead can better trade-oft off
Secondly, we propose a Stagewise its advantages over lookahead and stagewise lookahead in terms of excess risk error. SLRLA first divides the optimization into several stages. Then at each stage, it minimizes a locally-regularized function that contains the vanilla loss (0) in (1) and local regularizer 2 | - 0,ll² with the output 0g of the previous stage. A similar stagewise strategy is commonly used in practice, but does not has the local regularizer. Our results show two advantages of SIRLA over lookahead and stagewise lookahead. (i) On strongly convex problems and weakly quasi convex problems (a class of nonconvex problems including convex problems as a special case), SLRLA achieves faster convergence rates (i.e. smaller optimization error), and enjoys smaller generalization error than lookahead and its stagewise variant. (ii) On nonconvex problems under PL condition, when the problems are not heavily nonconvex (the smallest eigenvalue of (0) is not very small), SLRLA achieves linear convergence rate, and greatly improves optimization and generalization errors in lookahead, while stagewise lookahead cannot enjoy the linear convergence rate and the improvement.
LookAhead (SLRLA) algorithm, and prove
8
Finally, when / = 0, SLRLA degenerates to conventional stagewise lookahead, and our results show the advantages of stagewise lookahead over lookahead in terms of excess risk error on strongly convex problems, explaining the benefits of the stagewise strategy in lookahead.
2 Related Work
Optimization Algorithms. When problem (1) involves deep networks, SGD and adaptive gradient algorithms, e.g. Adam [18] and AdaGrad [19], are more preferable than other algorithms, such as variance-reduced SGD [14, 15, 35, 36], because of their high efficiency and good generalization. Moreover, SGD generally enjoys better generalization performance than adaptive gradient algorithms,, since SGD tends to converge to flat minima while adaptive gradient algorithms approach sharp minima [22, 37-41]. To further boost the generalization performance of SGD and adaptive gradient algorithms, Zhang et al. [1] proposed lookahead which can employ any standard optimizer as its

---

inner-loop optimizer and brings remarkable generalization improvement. Recently, a few works analyze lookahed but focus on optimization performance, e.g. small gradient noise variance on least square problems [1] and sublinear convergence rate on nonconvex problems [42]. In contrast, we analyze the intrinsic theoretical reasons for the superiority of lookahead terms of test performance.
Generalization Analysis of Algorithms. Uniform stability [43] is a classical tool to analyze generalization error of an algorithm. For instance, Hardt et al. [44] and Zhang et al. [45] analyzed the generalization of SGD via uniform stability. We also utilize stability to analyze generalization but target at analyzing the test performance, including optimization error and generalization error, of an algorithm and its lookahead variant, which is of more practical interest especially in deep learning, Yuan et al. [46] analyzed the test performance of SGD and stagewise SGD and showed advantages of the statewised strategy. Differently, we show that lookahead can well balance the optimization and generalization errors, and thus enjoys better test performance than its vanilla inner-loop optimizer.
3 Notations and Preliminaries
Convexity, Lipschitz Continuity, and Smoothness. For analysis, we first introduce necessary defimitions, i.e. convexity, Lipschitz continuity and smoothness. These definitions are commonly used in the convergence and generalization analysis of optimization algorithms, c.g. [47-51].
Definition 1 (Convexity, Lipschitz Continuity and Smoothness). We say a function (0) is >-strongly
convex if 101 02. f(01) 2 f(0)) (V 01 02) + 2 110] - 021 If A = 0, then we say f()) convex. Moreover, we say f(0) is G-Lipschitz continuous if (l - [(02]]l2 S Gi|0, - 0g 22 f(0) is said to be I--smooth if its gradient obeys [V((0)) V f(02)]l 2 S T.|01 02112 (vO,, 02).
Polyak-L.off Lojasiewizz (PL.) Condition and Weakly two conditions establish the relation between the gradient norm and the loss distance at two points. Definition 2 (PL Condition & Weakly Quasi-Convexity). Let 0* E Eargming f()). We say a function f() satisfies p-PL condition if it satisfies ()( f())) S ( 11 (VO) with universal constant p. {0) is said to be p-weakly- aweakkl--uasiicome conve- if it obeys (V e 0*) 2))2(((())
For nonconvex problems, such
f(0)))
Excess Risk Error Decomposition. Given a dataset S = ((x:, } where (æ;; y:) is drawn from an unknown distribution D, one often minimizes the empirical risk Iss in (1) via a randomized algorithm A. e.g. SGD, to find an estimated optimum A RJ argming (0). However, this empirical solution A differs from the desired optimum 0% of the population risk
>>= {(f(;;; y:)
0% E argming F(0)= A ((Ex)))~(((( (e;[(;;; 0), y)}-
This raises a particularly important question: what performance of the estimated optimum OA.S can achieve on the test data (æ, D? To answer this question, we analyze the test error EAAs (F(AAs)(0A.s))) of A.s via investigating the well-known excess risk error Sex defined as Eexc - -EA.S (FA.( -E
[FA.s[F(OA.s) (AAS
Fss (03) (2)
where 03 E argming (0) is the optimum of empirical risk F's. Generally, one can expect very small (Fss(FF((8))) since by selecting a powerful model, e.g., a deep network, one can well one only needs to upper bound the right side of Eqn. (2). The optimization error Eape - A. (Fs((AA - F0s())) denotes the difference between the exact optimum 0's and the estimated solution A the generalization error 6gen A (f - (Oss)) measures the effects of minimizing empirical risk instead of population risk. So one often analyzes Sopt and Egea to compare test performance of different algorithms.
fit the data. So to bound the test loss
Uniform Stability and Generalization. One popular approach to analyze generalization error Egen of a randomized algorithm A is uniform stability [44, 45]. This is because as shown in following lemma, for an algorithm A, if it is e-uniformly stable, its generalization error is upper bounded by c. In the following, we also analyze the uniform stability of lookahead to bound its generalization error.
Lemma (Uniform Stability and Generalization Error). [44] We say a randomized algorithm A is c-uniformly stable if for all datasets S ~ D and S' D where S and St differ in at most one sample,
u E (=;; (. - E(f( O (.s:): S.
Moreover, if A is e-uniformly stable, then its generalization error Egen which is defined as Egen = [FA.((((AA..) Fs(OA satisfies Egen Se. e.
3

---

Algorithm 1: Lookahead Optimization Procedure (Fs(O), T, 10. A,
Input :Objective (0), dataset S, inner-loop optimizer A, inner-loop step number ls and
learning rate {(1 (1) k-117
1==0 outer-loop learning rate (0, 1), initialization Og-
for t 1,2,.... ...,. T'do do
00 = 0:11:
for r 1,2, ..., k do
(8) (0) (0) ((Fs((),
17-1: S);
end
0, (1 a 10
end
Output:0A.s A.s = Or for strongly convex problem; 0,.s = nonconvex problems.
for convex and Σi= Σt-1 vt Tk
1
4 Excess Risk Analysis of Lookahead Algorithm
The lookahead algorithm [1] to solve problem (1) described in Algorithm maintains (i) slow weights 0 updated in the outer loop, and (ii) fast weights updated in the inner loop. For the inner loop, one can run any standard optimizer A, c.g. SGD or Adam used in deep learning, & steps via an operator A(Fs(O), 1 1/ 1, to update the fast weights v, where k is often small, e.g. k = 5 in [1]. Here the operator A(Fs(O): ",",, 1, denotes a minibatch gradient descent step in SGD or Adam, given the loss (O))), current solution vith learning rate n/--1- and dataset S. Next, lookahead uses the fast weights e to update the slow weights outer-loop learning rate E [0, 1j.
(e) (c)
0 + a(v - 0) with an
Because of its effectiveness and compatibility, lookahead has been widely used boost the perfor- mance of SGD [1], Adam [1, 52], RAdam [23, 24] and natural gradient algorithm [25]. and sets new state-of-the-ann in image classification and generation, and machine translation [1, 26-29]. However, there is no theoretical analysis that explicitly justifies the performance improvement of lookahead over the vanilla inner optimizer A. hindering the development of new and more advanced optimizers in principle way. The following sections aim to solve this problem by comparing the optimization and generalization errors of lookahead with its vanilla inner optimizer A. For analysis, we choose SGD as A, as SGD is widely used in deep learning. In this way, the inner-loop updating becomes
( A(Fs(O), (C)
(C)
S)
0 -0 7, -
(2)
(t) (c)
where 9 1 iteration. In the following, investigate the optimization and generalization errors of lookahead, and combine these two errors to upper bound its excess risk error which measures the test performance.
[ () ve(f(z; u v) Here B is the sampled minibatch at the (t, r-thh
(8)
4.1 Results on Strongly Convex Problems
To begin with, we first investigate the convergence performance of lookahead when its inner optimizer A is SGD. Our main results are summarized Theorem See proof in Appendix D.
Theorem 1. Suppose that ((( is X-strongly convex, and each individual loss l(f(x; 0), y) is G-Liscchitz and L-smooth w.r.t 6. Let 0 argming Fs(0). By setting the inner learning rate (0))
X+L the optimization error of the output A.s of lookahead satisfies
>L((--I)++++2)
El - 13 + 2((++))k22)2
3L(k+2)
16LG
0<a<
Eapt - (Fs==AA
3LIk+2)
-
16L 16L
a= 1
2(T+1)443
PFTT+11442
1L(k+2) -3100-001111 + X2 ()Tk+2)) [[7+1)k+2]=
90LG2
<
Theorem 1 shows that lookahead using SGD as its inner optimizer can converge on the strongly convex problems. The optimization error Exps has two terms: the first bias term characterizes the effect of initialization 0,; the second term reveals the impact of the stochastic gradient noise. For

---

the outer-loop learning rate a, it can be observed that with the increase of a, Eopt becomes smaller. So when = 1, lookahead degenerates vanilla SGD and achieves the smallest optimization error O TT X2TE/ ). This rate matches the one O X of SGD in [53] under the same assumptions, as ke is often much smaller than iteration number 7, e.g. = 5 [1]. So lookahead indeed does not benefit the convergence of SGD. It can be intuitively understood: for every l steps, lookahead
updates 0 as 0, 1 + a (t) 0t-1) = 0:-1 a Σ
==0 17 g- and goes forward slowly due h
--1 (e) (t)
to < 1, while SGD updates 0 as O, 0,1 -r= 7F g and runs faster, where (t) denotes the stochastic gradient.
Next, to bound the excess risk error, we investigate the generalization enror of lookahead by analyzing its stability, since as shown in Lemma 1, the uniform stability can upper bound generalization error.
Theorem 2. Suppose the assumptions and parameter setting in Theorem I hold. The general- ization error of the output 0 A.S of lookahead satisfies E yon = EA.s(F - (5 A.s)l 1 16G (1k+1)--1 Dd (1+1))+2
See its proof in Appendix D.2. Theorem 2 shows that when a + O, the generalization error Egen of lookahead using SGD as its inner optimizer can be upper bounded by O G2 Particularly, for a a=0, Egen becomes zero. This is because a a=0 0 means no updating, namely 0, = Ou (Vt), and thus (0 F (F(()) (0.)-Fss((
- For the effects of on Eyen, one can find that when a increases, Egen also becomes larger. This can be intuitively understood: larger a means quick updating of 0g. Accordingly, the empirical risk (0.) quickly decreases, while the population risk F(O,) may not due to possible overfiting. Interestingly, when a= indicating lookahead becomes vanilla SGD, our generalization error bound matches the previous bound O (²) of vanilla SGD in [44], even though Hardt et al. [44] used constant learning rate while we use decaying learning rate.
Based on Theorems and 2, we can derive the excess risk error bound in Corollary 1.
Corollary 1. With the same assumptions and parameter setting in Theorem I, the excess risk error Sew in (2) of the output A, of lookahead obeys Eex S Eopt + Egen where Copt and Egen are given in Theorems and 2, respectively.
See its proof in Appendix D.3. Corollary shows that the excess risk error Eexe of lookahead using SGD as its inner optimizer satisfies Eex Copt + gen- guarantecing good test performance of the estimated solution A,s by lookahead. In this work, we are particularly interested in the effects of a
on Eesc. When a (0, })) Eexe is of the order O 7d.. x27 (1- )). As in most cases, G² LG is much larger than nx especially for ill-conditioned problems where the strongly the factor X²
LG²
convex parameter is very small, increasing or the total training iteration number Tkk will decrease L Eexc. When E (3. 1), Eexc is of the order (c((a)) where e(a)= = T X=(2o-1yTk G² In(Tk)
LG G2
nx (1 T=ka
Then we have e'(a)=
ln
1122-1)7TT nX T=k= There are two common cases that lead
2L.
to e((a) < 0: (i) the problem is large-scale but not ill-conditioned, and thus the iteration number T is not large since the problem is easy, leading to 2 G² In(Th),
T23 nλ Tog (ii) the problem is heavily ill-conditioned, but iteration number 7' is moderate due to the moderate precision requirement, giving 2LG²
G² (n(TR) For both cases, increasing a can decrease Exx- For other cases, in theory, X²(2a 1)77% nx Take
by choosing a proper E (0, 1), one can expect better balance between the optimization error and generalization error, and could achieve a smaller excess risk error than vanilla SGD which corresponds to 1. As Sec. 3 shows that the excess risk error can well measure the test performance of an algorithm, our results explain the better lest performance of lookahead than SGD. Moreover, though in practice, it is hard to precisely decide whether e' (a) is positive not, from the above discussion, at least we know that a should be selected from the range [ 1]. providing some guidance to set a. Finally, our result is the first one that uses the same learning rate strategy to analyze both optimization and generalization errors, and matches the lower bounds of optimization error [53] and generalization error [45] of SGD.
4.2 Results on Convex Problems
Now we analyze lookahead using SGD as its inner optimizer A on the convex problems. Our main results are summarized in Theorem 3 with proof in Appendix D.4.
5

---

Theorem 3. Suppose that (( is convex, and each loss {(f(=;)), ;) 4) is G-Lipschitz w.r.t. 0. By
setting the inner learning rate Tï (t) 7, we have following properties.
(1) The optimization error Eopt of the output A. of lookahead satisfies Eaps = E...s
Fis Fs(())] S 20nkT + n/G²"
2 whhere 0's E aagminn F)) and A = 0 03
(2) The generalization ervor Eyon of the output A.S obeys Egen A.S. F((AAs) (sssl TT
(3) The excess risk error Eexc of the output A,s of lookahead satisfies Eee I Eopt Egen-
To begin with, Theorem 3 guarantees the convergence of lookahead on the convex problems. By A
setting ? sgs.gos70... lookahead achieves the optimization error O GA when a increases, the optimization error Eapt decreases. This accords with analysis results on the strongly convex problems that large can reduce Copt- When === lookahead degenerates to vanilla
quu.3gu.37000 Moreover,
SGD and its optimization error matches the one of vanilla SGD in [54] under the same assumptions.
The second part of Theorem 3 shows that the generalization error Egen of lookahead is bounded by ((anG*kT). When 1, this error bound is consistent with the lower bound O kT of SGD with a constant learning rate v in [45]. Moreover, one can find that smaller a can lead to a smaller generalization error, which also accords with the results the strongly convex problems.
O( a
Finally, by combining the optimization error Eopt and generalization error Egens we can bound the excess risk error Eexc of lookahead by O A
n 2agker + 2 + anGG*KT). ). So when fixing the learning rate,
" tuning & E (0, 1] can yield smaller excess risk error. It means that a proper a can benefit lookahead
in terms of excess risk error, explaining the better test performance of lookahead than SGD.
4.3 Results on Nonconvex Problems
For general nonconvex problems, one often uses the gradient norm F[[[Vss(O)]l) instead of the loss distance (() - Fs(("))) [ to measure whether 0 is stationary point. This is because many stationary points may exist nonconvex problem. But as shown in Sec. 3, to bound the excess risk error, one needs to bound the loss distance. To solve this issue, we follow [46] and are particularly interested in nonconvex problems under PL condition which allows us to bound the loss distance, since PE condition in Definition 2 establishes the relation between gradient norm and loss distance. Moreover, as observed/proved in [30-34] and our empirical results in Sec. 6.2, deep learning models often satisfy PL condition. We summarize main results in Theorem with proof in Appendix D.5.
Theorem 4. Assume each loss {(f(a: (e; 0), y) is G-Lipschitz and L-smooth w.r.l. O. Suppose that i++r+I and a > 1.. we have following properties.
Fs(O (0) obeys the p-PL condition. By setting n (1) The optimization error of the output A.S produced by lookahead satisfies
4A'
20 (a + 2(1 - a)) 1)) 12 1)20-1
Eapt EAS EEA.SFFs(OA.. Fs(03))
+
where 0's- E argming (0) and A' = E (Fs(
- Fs (03)].
(2) The generalization error of the output A produced by lookahead satisfies
Egen EAs(F((As)) Fs (s(OA)))
E
a (Tk)
where 7 = (1 (1 aL and - = Emax " in which Emax maxo((..)) {( {(f(x; 0), y). (3) The excess risk error Eexc of the output A of lookahead satisfies Sexe Eopt + Egen-
1) n
2
For the optimization error Eupt of lookahead on nonconvex problems, it is of the order O (TR)a w ). The same as (strongly) convex problems, larger a benefits the convergence of lookahead, for which we have discussed the reasons in Sec.
4.1. When a = 1, lookahead degenerates to SGD and pPTk) which matches the one of SGD in [55]. achieves the smallest optimization error O [TK)=
For the generalization error Egens it is of the order O O + (Tk)==r) which accords with the one of SGD in [44]. The sublinear dependence on kT and the inverse linear dependence on also match the

---

Algorithm 2: Stagewise Locally-Regularizn LookAhead (SLRLA)
Input :oss (O) constant { inner-loop iteration number )
g and learning rate
{Mp g= learning rate {ara) {a inner optimizer A, dataset S, initialization
8g-
for q = 1,
Q do
(0)
Ps () +
110 - 0g 0-1
0,-
(0), Mg. Tq. ag kgg A,
end
Output: :0 A.S = 0Q.
lower bound in [45]. Similarly, to achieve smaller generalization error, one should use small For the excess risk error Texc, it is bounded by O (Eopt + Egen). . So similar to (strongly) convex problems, when a is well chosen, the optimization error Eapt and generalization error Egen can be balanced well, giving smaller excess risk error and better test performance than SGD which corresponds to a = 1.
Regarding the lookahead method with inner optimizers other than SGD, we believe that one could still expect similar performance trade-off between optimization and generation with respect to the choice of a. Intuitively, for any inner optimizer, let 9 denote the "gradient" (or any descent direction) at the (t, (-th) iteration. After the l inner-steps, lookahead updates parameter as
(t) - 0.-1) 0,-1 -a -=== 1/7 gr Obviously, a R 1 is preferable for preserving the optimization speed of the inner optimizer. When it comes to the generalization error, obviously the best possible performance occurs at the initialization point as it is not dependent on the training data. Along with more training iterations, the network will gradually fit the training data and thus could give larger and larger prediction discrepancy between training data and test data. Therefore, it is desirable to have a < 1 as opposed to a R for generalization. Overall, for generic lnner-loop optimizers, lookahead is still expected to be able to balance the optimization and generalization performances with proper choices of a.
O, 0,-1 + a(1)
k-1 (t)
Stagewise Lecally-Regularizee Lookahead
We introduce the Stagewise Locally-Regularizze Regularized LookAhead (SLRLA) algorithm in Algorithm 2. SLRLA divides the optimization into Q stages. For the q-th stage, it first combines the vanilla loss
(0)
_ 110 1-00-- 0 to construct locally regularized loss (0 (0) e. 110 0 I12. Here 0-- the output of the 14-1)-th stage, and 8gg is a constant. The intuition 2
and a local regularizer
behind this local regularizer is that (i) it improves the convexity of the loss, e.g. converting ill- conditioned loss to a well-conditioned one, accelerating convergence; (ii) may avoid overfitting by preventing current solution A having extreme values and far from 0g- Theoretically, for X-strongly- convex problems, as shown in Thcorems & 2 that both optimization and generalization errors depend on ()) For nonconvex problems under y-PE condition, Theorem 4 also shows that both optimization and generalization error scale with (1/p). So on strongly convex problems, adding regularization the vanilla loss can enhance the convexity and thus reduces both optimization and generalization errors; on nonconvex problems, regularization can also increase the PL condition parameter y and thus helps optimization and generalization. We use 0 0 0 instead of ||e OII2 or 10-00p 01... This is because compared with O and Oo. O, is closer to the optimum 03 of (0) and thus allows to use larger By. improving the convexity of a loss more and benefiting convergence and generalization more (see discussion below). Next, SLRLA uses lookahead, i.c. Algorithm 1, to minimize (O), where constant inner- and outer-loop learning rates TJy and ag are used. A similar conventional stagewise optimization strategy which however does not regularize Fs(() is widely used in SGD. But it is theoretically unclear whether conventional stagewise strategy benefits lookahead.
In the following sections, we investigate two questions: (i) whether the conventional stagewise strategy improves lookahead; (ii) what advantages SLRLA has over the conventional (stagewise) lookahead. For (i), we show the advantages of stagewise lookahead over vanilla lookahead in terms of the optimization error. For (ii), we prove that SI.RAA can improve the optimization and generalization of conventional (stagewise) lookahead because of the local regularizer in SLRLA.
7

---

5.1 Results on Strongly Convex Problems
We analyze the optimization and generalization errors of SIRLA in Theorem 5 with proof in Appendix E.I, and then analyze the aforementioned two questions.
Theorem 5. Suppose that Fs( is X-strongly convex, and each loss {({ 0), is G-Lipschitz and L-smooth w.r.t O. By setting Eq 2t Bg = B aA [0, 1/ 1 S 382, Nakk, Tq 2 Xa, A -P and 0's E argming Fs)(O), the following properties hold.
A
6
(I) The optimization error Eopt of the output A. of SLRLA satisfies Eapt SS 24. Moreover, to achieve
Eppt c. Q @sttisfies& Q 2log A' and the stochastic gradient complexity is Σ Tggh Aue
36G
(2) The generalization error Egon of the output A.S of SIRIA satisfies Egen S 21 (
AL
(1
a X+L
+
exp ))1)), where " 2G (1 exp (xxII))
(3) The excess risk error Eerc of the output A.S of lookahead satisfies Sexc S Eopt + Egen-
By Theorem 5, we here show the advantages of the Stagewise LookAhead (SLA for short) [1] over lookahead, and also discuss the superiority of SLRLA over SLA. When Bg =0 and the learning rate is geometrically decayed as SLRLA after each stage, SLRLA degenerates to SLA, and Theorem 5 still holds. Theorem 5 shows the linear convergence of both SLRLA and SLA w.r.t the stage number Q For both SIRLA and SLA, to achieve optimization error e, i.e. Eapt = E Fs (f Fs(0 Se. is of the order O (log 2) and the stochastic gradient complexity (evaluation number) is E Tigh
0( (C With the optimization error c, Theorem shows that vanilla lookahead needs stochastic L.G
gradient complexity 0 ((4) 2 (1-2ajAA
Za for a E (0, 22) O LGG log X²E
for a = 1. and
LG (2x- 1)X=c for E ($, 1]. By comparison, both SLA and SLRLA improve the dependences on two important factors, i.e. À and a, in vanilla lookahead. Specifically, for factor X, SLA and SLRLA rely on (+)), while lookahead depends on at least O ) For factor a, SLA and SLRLA only linearly depend on (1)) In contrast, when a E (0, 2) lookahead exponentially depends on 1 due to the term ((2) x ). For a 2. SLL and SLRLA improve lookahead by removing the logarithm factor log When (2. 1], SLA and SLRLA also enjoy smaller dependence on a than lookahead, as the factor (5 2) in SLAA and SLRLA often smaller than the factor 2a-1 lookahead.
0(
For generalization error, by comparing Theorems 5 and 2, SLA and lookahead enjoy the same generalization error bound O (xx while SLRLA has superior one O x( especially for small
G²)
G²
a. This is because 33 can be at the same order of À in Theorem 5. By combining the optimization and generalization errors together, SLRLA enjoys smaller excess risk error than SLA which however
outperforms lookahead, when the computational budget (stochastic gradient complexity) is the same.
5.2 Results on Nonconvex Problems
Now we analyze SLRLA on two classes of nonconvex problems. The first one requires the smallest
eigenvalue (-o) of the Hessian V (0) to satisfy < j.u. where is the parameter in μ-Pt condition in Definition 2. It actually means the function is not heavily nonconvex. The second one satisfies the weakky--uuss-convvx assumption which guarantees that any local minimizer of the loss is also a global minimizer. Indeed, any convex function is weeakly-quasi-conver but the converse is generally not true. We use these two classes of nonconvex problems as examples to investigate the aforemennioned two problems. Theorem 6 with proof in Appendix E.2 summarizes the main results.
Theorem 6. Assume each ((f(x;;) 0). y) is G-Lipschitz and L-smooth w.r. O, and (0) satisfies p-PL condition. Let A' E[)((n) - F(03)] and Eg A where 0' E argming F0) (1) When < tu where (0) (V0), by setting a S Bg = B < t My S 3t. 11 Kig 2
pay" , the output A,S of SIRLA satisfies
72 - 0
PL -1 (1
exp (- --ee
(-62L)
6QL ))
Eopt S
E gen
<
(
Eexo S Eopt + Egens
2Q
n
11
L
8

---

Ioatabead 0.5
Inokahead
[train loss- tend loc4
Iookabeed (r- 0.20
Irokahead (1-03)
Inokahaad
train loss
Hookaheer' by Selee--iin
Irokahoad
DOSE 1O5S
Irokahead
tosz sccuing
(2)
(2w02))
(2
Sio (5-0.5)
66.6 (5-0
SLILA to..
51A (2
SLA (am 030
SLA (.50
SIALA to (0:-
SLA fo-10 stepemodd0n)
(2 slagsmaasGoo
SURLA CC
SIRLA to
0.
epech
opoch
epech
epach
(b)
Figure Investigation of lookahead, SLA and SLRLA on a softmax problem with MNIST. (a)
reveals the effects of a on convergence, generalization and test performance of lookahead and SLA. (b) shows the impact of a on test performance of SLRLA, and further compares the test performance.
where 72 2G2 (1 exp ( (- (l )+ Moreover, achieve Copt S 6, tte lotal stage number Q
(-+ft)
satisfies Q2 2 log and the total stochastic gradient complexity is Σ Tigh
36G
pae
(2) When O0) is
by setting Ba S B 11 S 3G ka Ta 2
peg
6
pppoa
S 2 L. the output A of SLRLA sutisfies
A
?2 - I.) (1-cxppp cxp 65 aT.) )
Copt S
Egen I n
Eexc S Copt + Egens
20'
ppa
where 1/2 = 2G / exp (- b(8-al)))) Moreover, to achieve Eppt S E, the total stage number Q
satisfies Q 2 log A and the total stochastic gradient complexity is Σ T Taky
36G ppaac
Here we discuss the advantages of SLRLA over SLA and lookahead. Theorem 6 shows that for the nonconvex loss Fs( which obeys FFFs()) JII, SLRLA enjoys linear convergence rate and has stochastic gradient complexity O to achieve Eopt S E. Compared with lookahead
which has complexity O(( (((44)) SLRLA improves the factor 22/0 in lookahead to 1 and also reduces its exponential dependence on 1 to linear dependence. These improvements accord with the ones on the strongly convex problems. For generalization error Egen SLRLA has an upper bound (1/((2=== that does not reply on the total iteration number Tk. In contrast, Theorem 4 shows that lookahead has generalization error bound O (1 (Tk) (Tk))TT sublinearly relying on Tk. So SLRLA enjoys smaller excess risk error than lookahead. For SLA, Theorem 6 cannot guarantee its linear convergence and small generalization error, as Theorem requires B, 20 > 0 but SLA needs 3, = 0. It is because the regularizer E 110-0 112 in SLRLA transforms the nonconvex loss (() into strongly convex one and greatly accelerates the convergence. This shows the advantage of SLRLA over SLA.
On weakly-quasi-cone
problems, SLRLA has stochastic gradient complexity O( 0pGFac to achieve
(Appac)
Eape S. 6, and has generalization error O [ ( & - L)). When viewing p as a constant, then same as the above case, SLRLA makes improvements on vanilla lookahead in terms of both stochastic complexity and generalization error. Moreover, the results on SLRLA also do not hold for SLA, since Theorem needs 3, 2 aL > while SLA sets 3, 0. Thus, all these results show the advantages of SLRLA over SLA and lookahead on achieving smaller excess risk error and thus enjoying better test performance.
(
Limitation Discussion. As explained in Sec. 4.3, one cannot bound the loss distance E (0)) (0)) for general nonconvex probems (GNP). So our main limitation is that our analysis is not applicable GNP. But analyze lookahead on GNP under PE condition which is observed/proved for deep networks [30-34] and our empirical results. See more discussions in Appendix A.
Societal Impact. This work analyzes the intrinsic theoretical reasons for the superiority of lookahead in terms of test performance, and further proposes a general and more advanced deep learning optimizer with provable improvement over lookahead which could advance deep network training. For the negative social impact of this work, it is mainly determined by which applications the developed optimizer is applied to.
6 Experiments

---

Table Classification accuracy (%). : *, f. are respectively reported in [1], [23], [61], [62].
optimizer
CIFARIO VGGI6
CIFARI00 VGGI6
ImageNet
ResNer18
WRN-16-10
ResNet18
WRN-16-10
ResNet18
Adam [18]
94,84
91.08
93.54
76,88
64.07
74,81
66.54*
Adabound [63]
92.56
91.35
91.68
71.43
64.74
71.64
68. 131
RAdam [23]
93,85
90.84
94.16
74.30
63,99
75.92
67.62*
AdamW [64]]
94.95
90.75
95.95
77.30
63.40
79.63
67.931
AdaBclicf [62]
95.204
92.25
95.71
77.024
68.63
77.93
70.08
Stagewise SGD [20)
95.23 19
92.13
95.51
78.24
60.97.10.02
18.05
70,23t
SLA
95.27=+0006
02.08+00002
95.73-0002
7..34=0.055
70.20++0.04
79 0.002
70. 70.30-20009
SLRLA
95.47:0..00
92.6310.03 9..08-0007
78.5810.15
70.63:10.02
79.85
70.47:10.1
6.1 Results on Strongly Convex Problems
Here we investigate the effects of a on the performance of lookahead, stagewise lookahead [1] (SLA) and SLRLA regularized softmax problem with MNIST [56]. The regularized softmax problem is strongly convex, as its regularization constant is set to 5 x 10 10-6 Following our theory. we use a linearly decayed learning rate (LR) for lookahead, and multi-step decayed LRs for SLA/SLRLA. See more details in Appendix B. Fig. (a) shows that when a increases, for lookahead & SLA, (i) their training loss reflecting the optimization error Eape decreases faster; (ii) the distance between their training and test losses reflecting the generalization error Egen becomes larger; (iii) their test loss first decreases and then increases which indicates the balance of a. Fig. 1 (b) shows the balance impact of on test accuracy of SLRLA, and also testifies the superiority of SLRLA over lookahead and SLA.
6.2 Results on Nonconvex Problems
Assumption Investigation. We investigate the key assump-
J 5:7e-0 (SLA on ResNet11)
tion, PL assumption on the nonconvex problems, for networks.
IinPL Assumption
2=2:le-01 (SL WRN-16-10)
6.000-- ISALLA on ResNet18)
We train ResNet18 [4] and wide-ReseNet-16- 10 (WRN) [57]
2e SULLA on WRN-16-10)
via SLA/SLARA, and report μ _ F|V (0.) (0.) /
70
Fs((0)) We estimate the optimum 0r of (0) as the so- lution found by SLA/SLARA after 200 epochs which gives small objective value ( 10-$) and is almost an optimum. Fig. 2 shows that y in SLA & SLARA is larger than 10 So on
networks. PL condition holds at least along the optimization tra-
epoch
jectory. This accords with the observations/theoric in [30-34]. Figure 2: Investigation of PE. Assp.
Classification Results. We evaluate SLA and SLRLA on CIFAR10/100 [58] and ImageNet [59] using different network architectures, i.e. ResNet18 [4], VGG16 [60] and WRN-16-10 [57]. For all experiments, SLRLA and SLA set k= 5, a momentum of 0.9, and a multi-stage learning rate (LR) decay at the (0.3S, 0.6S, -t epoch with total epoch number S. On CIFAR10/100, 200 epochs with a 0.8, a weight decay of 10-3, and set LR decay rate as 0.2. On Imagenet, we 100 epochs using a = 0.5, a weight decay of 10-4 and an LR decay rate of 0.1. These settings follow [1, 61, 62]. For regularization constant B. SIRLA selects it from {0.02, 0.2, 2.0, 20} via cross validation, and finally sets as 0.2 on CIFAR 10/100 and 20 on ImageNet.
train
Table reports the average accuracy and variance of 5 random seeds. SLRLA achieves the highest accuracy on CIFAR10/100 and ImageNet. This because (i) our theories in Sec. 5 show the advantages of SLRLA over SGD/SLA to achieve small excess risk error, indicating better test performance; (ii) as observed/proved in [22, 37-41], compared with adaptive algorithms, e.g. Adam and its variants, SGD-alin -aikelike algorithms, e.g. SLA/SLARA, often converge to flatter minima and thus generalize better. The results in Appendix B show the stable performance of SLARA on ImageNet when tuning the regularization constant B, in a large range, testifying the robustness of SLARA.
7 Conclusion
In this work, for the first time we theoretically show the advantages of lookahead in terms of the excess risk error, explaining its better test performance than its vanilla inner optimizer. Moreover, we prove that the stagewise optimization strategy can benefit lookahead in improving its excess risk error. Finally, we propose SIRLA which locally regularizes the vanilla objective to further improve the excess risk error of stagewise lookahead. Experimental results validated the advantages of SLRLA.
10

---

Acknowledgements
The authors sincerely thank the anonymous reviewers for their constructive comments on this work.
1. Funding. Pan Zhou, Hanshu Yan, Jiashi Feng and Shuicheng Yan are supported by Sea AI Lab, mainly for their GPU resource support. Xiao-Tong Yuan is supported in part by the National Key Research and Development Program of China under Grant No. 2018AAA01000 and in part by the Natural Science Foundation of China (NSFC) under Grant N0.61876090 and No.61936005.
2. Competing Interests. Pan Zhou, Jiashi Feng and Shuicheng Yan are staffs in Sea Al Lab. Hanshu Yan is an intern in Sea AI Lab, and is also Ph.D. student in National University of Singapore. Xiao-Tong Yuan works as professor in Nanjing University of Information Science & Technology. Nanjing, China
References
[1] M. Zhang, J. Lucas, G. Hinton, and J. Ba. Lookahead optimizer: k steps forward, step back. In Proc. Conf. Neural Information Processing Systems, pages 9597-9608, 2019.
[2] E. Barshan and P. Fieguth. Stage-wise training: An improved feature learning strategy for deep models. In Feature Extraction: Modern Questions and Challenges, pages 49-59. PMLR, 2015.
[3] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages 1-9, 2015.
[4] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages 770-778, 2016.
[5] P. Zhou, C. Xiong, R. Socher, and S. Hoi. architecture search. In Proc. Conf. Neural Information Processing Systems, 2020.
path-regularized differential network
[6] J. Li, P. Zhou, C. Xiong, R. Socher, and S. CH Hoi. Prototypical contrastive learning of unsupervised representations. In Int'l Conf. Learning Representations, 2021.
[7] Zhou, Xiong, X. Yuan, and Hoi. A theory- self- self-labeling refinement method for contrastive representation learning. In Proc. Conf. Neural Information Processing Systems, 2021.
[8] Zhou, Y. Zou, X. Yuan, J. Feng, C. Xiong, and S Hoi. Task similarity aware meta learning: Theory-inspired improvement on maml. In Conf. Uncertainty in Artificial Intelligence, 2021.
[9] T. Sainath, Mohamed, B. Kingsbury, and Ramabhadran. Deep convolutional neural networks for LVCSR. In Int'l Conf. acoustics, speech and signal processing, pages 8614-8618. IEEE, 2013.
[10] O. Abdel-Hamid, A. Mohamed, H. Jiang, L. Deng, G. Penn, and D. Yu. Convolutional neural networks for speech recognition. IEEE Trans. on audio, speech, and language processing, 22(10):5533-145 2014.
[11] G. Zheng, Y. Xiao, K. Gong. P. Zhou, X. Liang, and L. Lin. Wav-bert: Cooperative acoustic and linguistic representation learning for low-resource speech recognition. In Conf. Empirical Methods in Natural Language Processing, 2021.
[12] D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, D. Van Den, J. Schrittwieser, L. Antonoglou, V. Panneershelvam, and M. Lanctot. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
[13] N. Brown and T. Sandholm. Safe and nested subgame solving for imperfecttinfformation games. arXiv preprint arXiv: 2017.
[14] Shalev--hwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. J. of Machine Learning Research, 14(2), 2013.
11

---

[15] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proc. Conf. Neural Information Processing Systems, pages 315-323, 2013.
[16] P. Zhou and X. Yuan. Hybrid stochastic-determinssti minibatch proximal gradient: Less- faan-singl--pas optimization with nearly optimal generalization. In Proc. Int'l Conf. Machine Learning, 2020.
[17] Zhou, X. Yuan, and J. Feng. New insight into hybrid stochastic gradient descent: Beyond with-replacement sampling and convexity. In Proc. Conf. Neural Information Processing Systems, 2018.
[18] D. Kingma and J. Ba. Adam: A method for stochastic optimization. In Int'l Conf. Learning Representations, 2014.
[19] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. of Machine Learning Research, 12(7), 2011.
[20] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[21] D. Saad. Online algorithms and stochastic approximations. Online Learning, 5:6-3, 1998.
[22] P. Zhou, J. Feng, C. Ma, C. Xiong, S. Hoi, and W. E. Towards theoretically understanding why sgd generalizes better than adam in deep learning. In Proc. Conf. Neural Information Processing Systems, 2020.
[23] L. Liu, H. Jiang, P. He, W. Chen, X. Liu, Gao, and J. Han. On the variance of the adaptive learning rate and beyond. arXiv preprint
2019.
[24] L. Wright. Ranger Optimizer, 2019.
synergistic optimizer. https://ggtthb..co///lsss//
Ranger- Langer-Deep-Lese Deep- haap--Laannnnn-ptiizzeeee
[25] Z. Tang, F. Jiang. J. Song. M. Gong, H. Li, F. Yu, Z. Wang, and M. Wang. Asymptoticng: A regularized natural gradient optimization algorithm with look-ahead strategy. arXiv preprins arXiv:2012.13077 2020.
[26] T. Wei, D. Chen, W. Zhou, Liao, W. Zhang, L. Yuan, G. Hua, and N. Yu. A simple baseline for stylegan inversion. arXiv preprint 2171:
2021. 2021.
[27] G. Huang, S. Huang, L. Huangfu, and D. Yang. Weakly supervised patch label inference network with image pyramid for pavement diseases recognition in the wild. In Int'l Conf. acoustics, speech and signal processing, pages 7978-7982, 2021.
[28] D. Samuel, A. Ganeshan, and J. Naradowsky. Meta-learning extractors for music source separation. In Int'l Conf. acoustics, speech and signal processing, pages 816-820, 2020.
[29] T. Chavdarova, M. Pagliardini, S. Stich, F. Fleuret, and M. Jaggi. Taming gans with lookahead- minmax. arXiv preprint arXiv:2006. 14567, 2020.
[30] M. Hardt and T. Ma. Identity matters in deep learning. arXiv preprint arXiv:1611.04231, 2016.
[31] B. Xie, Y. Liang, and L. Song. Diverse neural network learns true target functions. In Int'l Conf. Artificial Intelligence and Statistics pages 1216-1224. PMLR, 2017.
[32] Z. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation. In Proc. Conf. Neural Information Processing Systems, 2017.
[33] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Proc. Int'l Conf. Machine Learning, pages 745-754. PMLR, 2018.
[34] Y. Zhou and Y. Liang. Characterization of gradient dominance and regularity conditions for neural networks. In Int'l Conf. Learning Representations, 2018.
12

---

[35] P. Zhou, X. Yuan, and J. Feng. Efficient stochastic gradient hard thresholding. In Proc. Conf. Neural Information Processing Systems, 2018
[36] Zhou, X. Yuan, S. Yan, and J. Feng. Faster first-order methods for stochastic non-convex optimization on riemannian manifolds. 2019.
[37] N. Keskar and R. Socher. Improving generalization performance by switching from Adam to SGD. arXiv preprint arXiv: 2017.
[38] A. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht. The marginal value of adaptive gradient methods in machine learning. In Proc. Conf. Neural Information Processing Systems, pages 4148-4158 2017.
[39] S. Merity, N. Keskar, and R. Socher. Regularizing and optimizing LSTM language models. arXiv preprint 1rXii::708.021688 2017.
[40] H. He, G. Huang, and Y. Yuan. Asymmetric valleys: Beyond sharp and flat local minima. In Proc. Conf. Neural Information Processing Systems, 2019.
[41] U. Simsekli, L. Sagun, and M. Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In Proc. Int'l Conf. Machine Learning, 2019.
[42] J. Wang, V. Tantia, N. Ballas, and M. Rabbat. Lookahead converges to stationary points of smooth non-convex functions. In Int'l Conf. acousties, speech and signal processing, pages 1604-8608. IEEF, 2020.
[43] O. Bousquet and A. Elisseeff. Stability and generalization. J. of Machine Learning Research, 2:499-526, 2002.
[44] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. Proc. Int'l Conf. Machine Learning, pages 1225-1234. PMLR, 2016.
[45] Y. Zhang, W. Zhang, S. Bald, V. Pingali, C. Chen, and M. Goswami. Stability of sgd: Tightness analysis and improved bounds. arXiv preprint arXiv:2102.05274, 2021.
[46] Z. Yuan, Y. Yan, R. Jin, and T. Yang. Stagewise training accelerates convergence of testing error over SGD. In Proc. Conf. Neural Information Processing Systems, 2018.
[47] O. Shamir. Making gradient descent optimal for strongly convex stochastic optimization. CoRR abs/l 109.5647, 2011.
[48] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proc. Conf. Neural Information Processing Systems, pages 315-323, 2013,
[49] P. Zhou and J. Feng. Empirical risk landscape analysis for understanding deep neural networks. In Int't II Conf. Learning Representations, 2018.
[50] P. Zhou and J. Feng. Understanding generalization and optimization performance of deep enns.
In Proc. Int'l Conf. Machine Learning, 2018.
[51] Zhou, X. Yuan, H. Xu, S. Yan, and Feng. Efficient meta learning via minibatch proximal update. In Proc. Conf. Neural Information Processing Systems, 2019.
[52] A. Zhu, Y. Meng, and C. Zhang. An improved adam algorithm using look-ahead. In Int'l Conf. Deep Learning Technologies, pages 19-22, 2017.
[53] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. Proc. Int'l Conf. Machine Learning, pages 1571-1578, 2012.
[54] L. Lei and M. Jordan. Less than a single pass: Stochastically controlled stochastic gradient. In Artificial Intelligence and Statistics, pages 148-156. 2017.
[55] S. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. In Proc. Int'l Conf. Machine Learning, pages 314-323, PMLR, 2016.
13

---

[56] Y. LeCun, L. Bottou. Y. Bengio, and P. Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-233 -3244, 1998.
[57] S. Zagoruyko and N. Komodakis. Wide residual networks. arXiv preprint arXiv: 2016.
[58] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.
[59] J. Deng, W. Dong, R. Socher, L. Li, K. Li, and F. Li. Imagenet: A large-scale hierarchical image database. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages 248-255, 2009.
[60] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1555: 2014.
[61] J. Chen, D. Zhou, Y. Tang, Z. Yang, Y. Cao, and Q. Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.06763. 2018.
[62] Zhuang, T. Tang, Ding, S. Tatikonda, N. Dvorekk, X. Papademetris, and Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. arXiv preprint arXiv:2010.07468, 2020.
[63] L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: 2019.
[64] L. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.0500122000 2017.
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] We have briefly discussed the main limitations our work at the end of Sec. 5.2. Moreover, we discuss more in Appendix A.
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(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] Please see the assumptions made in each theorem and corollary.
(b) Did you include complete proofs of all theoretical results? [Yes] We provide the complete proofs of all theories in Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please see the experimental settings in Sec. and Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Please Table 1.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We use two A100 GPUs on ImageNet, and use single 100 GPU for all remaining experiments. Please see Appendix B.
4. If you using existing assets (c.g., code, data, models) or curating/releasnng assets...
14

---

(a) If your work uses existing assets, did you cite the creators? [Yes] We analyze existing lookahead algorithm and cite it already. Our codes are implemented based on lookahead and also mentioned it in Appendix B.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
In Appendix, we only provide more experimental results, more experimental settings, and proofs of all theories.
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A] We use standard public datasets, including MNIST, CIFARI0/100 and ImageNet which allow researchers to use.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We use standard public datasets, including MNIST, CIFARI0/100 and ImageNet which consist of objectives/views.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "ZpxArXsftE8", "reviewer": "Reviewer_bSD7", "summary": "The paper provides the excessive risk rounds for the lookahead algorithms on (strongly) convex and non-convex problems with PL condition. The theoretical results are obtained via (1) convergence analysis (2) the uniform stability analysis. From the excessive risk bounds, the authors provide justification for the performance of the lookahead algorithms. Finally, the paper proposes a stagewise locally-regularized lookahead algorithm called SLRLA, which adds a L2 regularizer and decays the learning rate for each stage. ", "questions": "", "limitations": "", "rating": 6, "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": "## Originality\n\nThe convergence analysis and the uniform stability analysis of the lookahead algorithms are new and interesting.\n\n## Quality\n\nThe theoretical part of the paper is sound.\n\n- The authors provide convergence analysis for lookahead algorithms under different settings, e.g., (strongly) convex and PL-condition. For the generalization part, the authors derive the uniform stability bounds for lookahead algorithms. By combing two parts, the authors show that there is an optimal choice for $\\alpha$ which balances optimization error and generalization error.\n\nThe empirical result is strong.\n\n- The authors test their proposed algorithm in three commonly used datasets. They show that SLRLA is better than other baseline algorithms.\n\nSome concerns for the theory part:\n\n- One caveat of the uniform stability analysis is that for general convex problem (not strongly convex), the generalization depends badly on $T$. Therefore if we calculate the optimal $\\alpha$ we found that $\\alpha$ scales with $1/T$, which means for small excessive risk we might need to restrict the effective learning rate. \n\n- Line 163: In [41], actually the optimal rate for SGD is $O(1/\\lambda T)$. Also in Line 291: The dependency for $\\lambda$ is optimal for SLA and SLRLA, but I think the $O(1/\\lambda^2)$ bound for lookahead algorithms is due to your analysis techniques. The comparison may be unfair.\n\n## Clarity\n\nThe paper is well-written.", "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": "1.5"}, "extra_text": {}}, {"review_id": "MDFmuUmjjCG", "reviewer": "Reviewer_3SmH", "summary": "The authors analyze the Lookahead optimizer (Zhang et al.) algorithm, showing that it has nice bounds on the excess risk error compared to SGD on strongly convex problems and noncovex problems which satisfy the PL condition. They also propose a locally-regularized version of the Lookahead algorithm which has some better theoretical properties and performs well on empirical evaluations.", "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": "Strengths\n- The theoretical results are novel and useful for understanding the lookahead algorithm and how it compares to SGD. Theorem 1 provides bounds on the optimization error of lookahead(SGD); Theorem 2 bounds the generalization error.\n- The authors do a good job of offering intuition for the their theoretical results and discussing implications.\n- Stagewise locally-regularized lookahead is well-motivated and the proof is technically sound. It is impressive to improve on an existing, popular algorithm.\n- While most of the results are theoretical, the empirical evaluations are strong and performance on CIFAR and ImageNet exceeds the performance on the original Lookahead algorithm across 5 seeds.\n\nWeaknesses\n- Writing can be a bit choppy at points and would benefit from careful proofreading.\n\nQuestions\n- Does stagewise lookahead refer to conventional lookahead (Zhang et al.) with a stagewise learning rate (geometric) decay? If so, I believe it would be better to make this point more explicit and mention that it is the learning rate schedule typically used.\n- Could you say anything about lookahead with other inner optimizers?\n\nMinor\n- 83: the sharp minima story is a bit more nuanced (as mentioned in some of your references) or \"Sharp Minima Can Generalize For Deep Nets\" (Dinh et al.)\n- 86: typo in lookahead\n- In algorithm 1, it would improve clarity if the order of the description of the inputs matches that of the function arguments\n\nPost-rebuttal: I have read the other reviewer comments and responses and am maintaining my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are sufficiently discussed throughout the paper and in the appendix. The authors do not directly address societal impact (\"This is not applicable to a theoretical work\"), though I believe it is worth some further thought e.g. see the AdaBelief paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "B1n5ysdlErM", "reviewer": "Reviewer_bbpy", "summary": "Lookahead is a relatively recent algorithm that has shown great performances in both single-objective and two-objective training, but it is not well understood theoretically why it improves training particularly in the former case. This paper aims to elaborate why Lookahead improves test accuracy using excess risk error which is decomposed into optimization and generalization terms. Interestingly, the authors show that the extra hyperparameters in Lookahead when combined with SGD allow for a better trade-off between the two terms relative to SGD. Moreover, they propose a new \"stagewise\" variant algorithm that: (i) uses constant step sizes for Lookahead, but changes/decreases these at each stage, and (ii) adds regularization term that enforces doing more \"conservative\" steps (the term penalizes high distance between predicted iterate and last iterate of the previous stage, see Alg.2). ", "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": "In my opinion, this paper does a nice balance between theoretical discussions and experiments, and I find it very well written. Regarding the latter, the authors introduce the necessary definitions, list theoretical results, but it is nice that they also discuss the results. \n\nWhile I enjoyed reading the first part discussing the original Lookahead (LA), I have several questions/concerns for the newly proposed algorithm called SLRLA.\n\n\n--- Questions ---\n\n1. Following your analysis on LA, could you elaborate on how SLRLA is motivated? While I understand that given its formulation you obtain a small excess risk error, my question is towards understanding how your LA analysis guided finding new algorithms,  and it might be useful adding such a comment to also connect the two parts. \n\n2. Is introducing the stage-wise step-size strategy necessary for SLRLA, or alternatively, is the excess risk error worse in that case? In contrast, if I understand well, for LA you used decaying learning rate in the analysis. I am not sure I understand, could a stage-wise step-size strategy provide better excess risk error for LA than the one provided?\n\n3. While SLRLA has better excess risk error, it also introduces two additional hyper-parameters making it harder to tune ($Q$ and $\\beta_q$). Could you comment from the analysis perspective whether the obtained results require optimal hyperparameters? Also, is $\\beta_q$ easy to select in your experiments, and do the performances vary across the values you used in the cross-validation?\n\n4. Regarding the empirical setup, seems like only the $\\beta_q$ hyperparameter of SLRLA is cross-validated, and the rest are fixed. This might give an advantage to SLRLA. \n\n5. Figure 1. Surprisingly, LA in (b) performs poorly (for MNIST). How are the hyperparameters selected for it, and what are the performances of SGD? Also, as test accuracy is not used in both a.3 and b, it is harder to compare the performances of SLRLA and SLA with varying hyperparameters. \n\n\n6. As a comment, in my opinion, the nested version of Lookahead proposed in [21] -- which applies  LA recursively -- is related to SLRLA as both push the current iterate toward a past \"anchored\" iterate, but they are yet different methods. It would be interesting to explore how the two differ (in terms of the error trade-off).\n\n\n--- Minor/typos ---\n\n\nln.67: has->have\n\nFig.2: maybe ensure legend text does not overlap much,  and improve caption\n\n--- Recommendation ---\n\n\nIn summary, I find the result/analysis on the original Lookahead interesting and intuitive, and in my opinion, the paper is well-written. In terms of novelty,  (i) the analysis used in this paper is not novel, (ii) while the paper shows how LA hyperparameters influence the trade-off between the two errors terms, it is not clear how these can be selected -- thus several questions still remain open for LA (how to select the hyperparameters of LA in practice and deriving tighter rates for it).\nHowever, I would be glad to raise my score if the authors address some of the above questions.\n\n--- Update after discussion ---\n\nThe authors addressed most of my concerns, and I increased my score.", "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": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A well written paper with solid theoretical contributions; well received by the reviewers. The authors also did a very good job of giving long and detailed responses to any questions and concerns.
Decision: Accept (Poster)