The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods
Authors: Wei Tao
Sheng Long
Gaowei Wu
Qing Tao
Venue: ICLR 2021 Poster (2021)
Keywords: Deep learning
convex optimization
momentum methods
adaptive heavy-ball methods
optimal convergence

Abstract: The adaptive stochastic gradient descent (SGD) with momentum has been widely adopted in deep learning as well as convex optimization. In practice, the last iterate is commonly used as the final solution. However, the available regret analysis and the setting of constant momentum parameters only guarantee the optimal convergence of the averaged solution. In this paper, we fill this theory-practice gap by investigating the convergence of the last iterate (referred to as {\it individual convergence}), which is a more difficult task than convergence analysis of the averaged solution. Specifically, in the constrained convex cases, we prove that the adaptive Polyak's Heavy-ball (HB) method, in which the step size is only updated using the exponential moving average strategy, attains an individual convergence rate of $O(\frac{1}{\sqrt{t}})$, as opposed to that of $O(\frac{\log t}{\sqrt {t}})$ of SGD, where $t$ is the number of iterations. Our new analysis not only shows how the HB momentum and its time-varying weight help us to achieve the acceleration in convex optimization but also gives valuable hints how the momentum parameters should be scheduled in deep learning. Empirical results validate the correctness of our convergence analysis in optimizing convex functions and demonstrate the improved performance of the adaptive HB methods in training deep networks.

Published as a conference paper at ICLR 2021
THE ROLE OF MOMENTUM PARAMETERS IN THE OPTIMAL CONVERGENCE OF ADAPTIVE POLYAK'S
HEAVY-BALL METHODS
Wei Tao
Sheng Long
Institute of Evaluation and Assessment Research Academy of Military Science Beijing, China wtao plaust@1 63. com
Department of Information Engineering
Army Academy of Artillery and Air Defense Hefei, China
1s1518632234981 ...499911..omm
Gaowei Wu
Qing Tao f
Institute of Automation CAS School of Artificial Intelligence University of CAS Beijing, China gaowei wue ia ac. cn
Department of Information Engineering
Army Academy of Artillery and Air Defense
Hefei, China qi tann a ac
ABSTRACT
The adaptive stochastic gradient descent (SGD) with momentum has been widely adopted in deep learning as well as convex optimization. In practice, the last iterate is commonly used the final solution. However, the available regret anal- ysis and the setting of constant momentum parameters only guarantee the optimal convergence of the averaged solution. In this paper, we fill this poooy-pect gap by investigating the convergence of the last iterate (referred to as individual convergence), which is more diffieult task than convergence analysis of the av- eraged solution. Specifically, in the constrained convex cases, we prove that the adaptive Polyak's Heavy-ball (HB) method, in which the step size is only updated using the exponential moving average strategy, attains an individual convergence rate of O (z). as opposed to that of O (logt) ) of SGD, where is the number of iterations. Our analysis not only shows how the HB momentum and its time- varying weight help us to achieve the acceleration in convex optimization but also gives valuable hints how the momentum parameters should be scheduled in deep learning. Empirical results validate the correctness of our convergence analysis in optimizing convex functions and demonstrate the improved performance of the adaptive HB methods in training deep networks.
INTRODUCTION
One of the most popular optimization algorithms in deep learning is the momentum method (Krizhessky et al. (0122). The first momentum can be traced back to the pioneering work of Polyak's heavy-ball (HB) method (Polyak 1964), which helps accelerate stochastic gradient descent (SGD) in the relevant direction and dampens oscillations (Ruder) (016). Recent studies also find that the HB momentum has the potential to escape from the local minimum and saddle points (Ochs et al.) 2014 Sun et al. 2019a). From the perspective of theoretical analysis, HB enjoys a smaller conver- gence factor than SGD when the objective function is twice continuously differentiable and strongly convex (Ghadimi et al. 2015). In nonsmooth convex cases, with suitably chosen step size, HB attains optimal convergence rate of O ( in terms of the averaged output (Yang et al. 2016 where is the number of iterations.
"qqual contribution
1 "orresponning author

---

Published as a conference paper at ICLR 2021
To overcome the data- iata-independent limitation of predetermined step size rules, some adaptive gra- dient methods have been proposed to exploit the geometry of historical data. The first algorithm in this line is AdaGrad (Duchi et all] 201T). The intuition behind AdaGrad is that the seldom-updated weights should be updated with a larger step size than the frequently-updated weights. Typically, AdaGrad rescales each coordinate and estimates the predetermined step size by sum of squared past gradient values. As a result, AdaGrad has the same convergence rate as vanilla SGD but enjoys smaller factor especially in sparse learning problems. The detailed analysis of AdaGrad (Mukka- mala & Hein, 2017) implies that one can derive similar convergence rates for the adaptive variants of the predetermined step size methods without additional difficulties.
Unfortunately, experimental results illustrate that AdaGrad under- pedfo-performed when applied to train- ing deep neural newtworks (Wilson et al., 2017). Practical experience has led to the development of adaptive methods that is able to emphasize the more recent gradients. Specifically, an exponential moving average (EMA) strategy was proposed in RMSProp to replace the cumulative sum operation TTeleman & Hinton 2012). Adam (Kingma & Ba, 2014), which remains one of the most popular optimization algorithms in deep learning till today, built upon RMSProp together with updating the search directions via the HB momentum. Generally speaking, the gradient-based momentum algo- rithms that simultaneously update the search directions and learning rates using the past gradients referred to the Adam-type methods (Chen et al., 2019). These kinds of methods have achieved several state-of-the-an ahe- results on various learning tasks (Sutskever et al. 2013).
Compared with HB and AdaGrad, the main novelty of Adam lies in applying EMA gradient estimate (first-order) and to wiement-wise square-of-gradients (second-orden) with the momentum parameter BI, and step size parameter B2r (see (6) (Alacaoglu et al., 2020). However, the use of EMA causes a lot of complexities to the convergence analysis. For example, in the online setting, (Kingma & Ba 2014) offered proof that Adam would converge the optimum. Despite its re- markable practicality, Adam suffers from the non- convergeee issue. To overcome its advantages, several variants such as AMSGrad and AdamNC were proposed (Reddi et al. 2018). Unfortunately, the regret bound of AMSGrad in Reeddi et al. 2018) is O(Vlog tvt) for nonsmooth convex prob- lems, as opposed to that of O ((VE) of SGD. On the other hand, EMA uses the current step size in exponential moving averaging while the original HB can use the previous information (Zou et al.) 2018). This will lead the update to stagnate when 31, is very close to I. Fortunately, such a dilemma will not appear in Polyak's 's HB method and a simple proof on the convergence of this kind of Adams in smooth cases has been provided (Dffossez et al.] 2020).
In this paper, we will focus on the adaptive Polyak's 's HB method, in which the step size is only updated using EMA. Despite various reported practical performance for the Adam-type methods, there still exist some gaps between theoretical guarantees and empirical success.
First of all, some important regret bounds have been established to guarantee the perfor- mance of online Adam-type algorithms. Nevertheless, the online-to-bate conversion can inevitably lead the solution of the induced stochastic algorithm to take the form of averag- ing of all the past iterates. In practice, the last iterate is popularly used as the final solution, which has the advantage of readily enforcing the learning structure (Chen et al. 2012). For SGD, the convergence of the last iterate, which is referred to individual convergence in (Tao et al.] (020b), was posed as an open problem (Shamir) 2012). Only recently, its optimal individual convergence rate is proved to be O
log and O Togt)
((or)) for general and
vt
t
strongly convex problems respectively (Harvey et al., 2019 Jain al., 2019). Despite
enjoying the optimal averaging convergence (Yang et al.) 2016), as far as we know, the individual convergence about the adaptive HB has not been discussed.
Secondly, the momentum technique is often claimed as accelerated strategy in machine learning community. However, almost all the theoretical analysis is only limited to the Nes- terov's accelerated gradient (NAG) (Nesterov) 1983) method especially in smooth cases (Hu et al. 2009 Liu & Belkin 2020), which accelerates the rate of SGD from O( ) to O. While the individual convergence of HB is also concerned in some papers (Seb- bouh et al., 22200] Sun et al., (019b),, the considered problem is limited to smooth and the derived rate is not optimal in convex cases. It is discovered that NAG is capable of ac-
celerating the rate of individual convergence of SGD from O log! to O (1) (Too et al. Vt
2

---

Published as a conference paper at ICLR 2021
2020a) in nonsmooth convex cases. Nevertheless, there is still lack of the report about the acceleration of the adaptive HB.
Finally, in practice, almost all the momentum and Adam-type algorithms are often used with constant momentum parameter 31 (typically between 0.9 and 0.99). In theory, re- gret guarantees in the online Adam require a rapidly decaying B1. + schedule, which is also considered in (Sutskever et al. 2013; Orvieto et al., 2019). This gap is recently bridged by getting the same regret bounds as that in (Reddi et al. 2018) with a constant 31c (Alacaoglu al. 2020). In each kate-of-the-aa art deep learning library (c.g. TensorFlow, PyTorch, and Keras), HB is named as SGD with momentum and 31 is empirically set to 0.9 [Ruder] 2016). Despite its intuition in controlling the number of forgotten past gradi- ents and guarantee optimal averaging convergence (Yang et al. 2016), how B1 affects individual convergence has not been discussed (Gitman al. 2019).
The goal of this paper is to close a theory-practice gap when using HB to train the deep neural networks as well as optimize the convex objective functions. Specifically,
By setting Bi 2+2 we prove that the adaptive HB attains individual convergence rate of O ) (Theorem as opposed to that of O logt) vi ) of SGD. Our proof different
from all the existing analysis of averaging convergence. It not only provides a theoretical guarantee for the acceleration of HB but also clarifies how the momentum and its parameter
31 help us to achieve the optimal individual convergence.
I E Bie = B < 1, we prove that the adaptive HB attains optimal averaging convergence (Theorem 6p. To guarantee the optimal individual convergence, Theorem suggests that time-varying 31r can be adopted. Note 31, = E+2 + 1, thus our new convergence analysis not only offers an interesting explanation why we usually restrict B1c + 1 but also gives valuable hints how the momentum parameters should be scheduled in deep learning.
+
We mainly focus on the proof of individual convergence of HB (Theorem 3 Appendix A.1). The analysis of averaging convergence (Theorem 4 is simpler. Their extensions adaptive cases are slightly more complex (Theorem and but it is similar to the proof of AdaGrad (Mukkamala & Hein 2017) and the details can be found in the supplementary material.
PROBLEM STATEMENT AND RELATED WORK
Consider the following optimization problem,
min f(w), s.t. w E Q.
(1)
where C Rd is closed convex set and f f(w) is convex function. Denote that w" is optimal solution and the projection operator on Q. Generally, the averaging convergence is defined as
(w)) f(w") I e(t),
(2)
where w. = D w, and E(!) is the convergence bound about f. By contrast, the individual convergence is described as
-
f(w) < e(t).
Throughout this paper, we use g(w.) ) to denote the subgradient of f at w.. Projected subgradient descent (PSG) is one of the most fundamental algorithms for solving problem (I) (Dimitri P. al., 2003), and the iteration of which
W P(w, agg(w:)),
where a; > is the step size. To analyze the convergence, we need the following assumption.
Assumption 1. Assume that there exists number M 0 such that
Ig(w) || S M, Vw E Q
is known that the optimal bound for the nonsmooth convex problem is O Nemirovsky & Yudin 1983). PSG can attain this optimal convergence rate in terms of the averaged output while its optimal individual rate is only O (ogg) (Harvey et al. 2019 Jain et al. 2019
3

---

Published as a conference paper at ICLR 2021
When Q RN, the regular HB for solving the unconstrained problem D
Wi+1 W, Ogg(w,) + (,(w, w,-1).
(4)
1 < B. = 3 < 1, the key property of HB is that it can be reformulated as (Ghadimi et al. 2015
at
Wx+1 + P++1 Wt + P:
1 g wr), where p:.
(wr Wr-1).
(5)
Thus its convergence analysis makes almost no difference to that of PSG. Especially, if oz _ its
vT
averaging convergence rate is O + Yang al. 2016). where 7 is the total number of iterations.
Simply speaking, the regular Adam (Kiggma & Ba
2014 takes the form of
W(+1 Wt v8
gc:
where g(w.) is unbiased estimation of g(w,) and
g :108:-11 + (1 Bl))g(w)), V₂ B2t V2- + (1 - 320 diag [g(w:)
(6)
3 INDIVIDUAL CONVERGENCE OF HB
To solve the constrained problem ① HB can naturally reformulated as
W++1 Po w. a.g(w,) Be(w; wt-1)].
We first prove a key lemma, which extends 5 to the constrained and varying cases.
Lemma 1. Dimitri et al. 2003) For w E Rd Wo E Q
(w Wo: u wo) S 0, for all Q and only wo P(w).
Lemma 2. Let {we]ee be generated by HB 77. Let
1
Pt = t(w, Wt-1), 3r t+2
at (t 2)
Then HB can be reformulated as
Wi+1 + P++
PQ. w. + Pt B(ww))
(8)
Proof. The projection operation be rewritten
optimization problem (Duchil 2018). i.e.,
We+1 = /o/W::- o:g(w,) + 3e(w; - wr-1)] is equivalent to
Wo+1 = arg min (as (g((:), w) + 5 !| - w. - -3c(w: -
(9)
weQ
Then, Vw Q, have
(W141 W. Be(w: wt-1) ang(w:). We+1 w) S
This is
(Wi-1 + - (w+ +P) + g(ws), We+1 - -w) $ 0.
(10)
v
Specifically,
(We+1 + (w, + Pi) + / g(ww)) We+1 - w.) 00.
(11)
From
10
and
(We+1 + P++1 - -W)+Pp)++ / g(w)) W - w -
(t+ we)) s O.
i...
(We+1 + Pi+1 - (w: + p.) (((w), wzt1 P++ w) 50.
Using Lemma Lemma is proved.
Due to the non non-expansive property of Pq (Dimirri et al. 2003). Cemma2implinn that the conver- gence analysis for unconstrained problems be applied to analyze the constrained problems.
4

---

Published as a conference paper at ICLR 2021
Theorem 3. Assume that Q is bounded. Let {wike= be generated by HB 7 Ser
a
Bt = ++2
and az =
(t + 2)vE
Then
s(w.) - ((w)) 0 (
Proof. According Lemma 2
1| - (We+1 + P(t1)ll || - (w. Po) + v,B(w:))?
|w" (we + Pr)
Vt g(w)))l
||w" - -(w: + p1)11 + / ((,)))l 7 w + 2 at (8((s)) (1())+((1))))) W
a
-we)
Note
(B(W)),w"- w S s(w")
-
Then
(t + 1)(f((w)) - f(ww)]
$ -[f((w-1)) -fad)-f((a f[(w)]] + Vt /|=" (we + p:)l1
(Werr + P141)ll+++ a Vt w
2 lls(w:))l
2a
2a
Summing this inequality from & 1 obtain
(t + ().f f(w")]
V (l/w* - (wx + pa)ll - 1|w* - (Wa+1 + 13)4))13)]
f(wo) f(w") + Σ, (l(
R= 2
2a
k=
Note
[[(())]l VIM? sVMM
24
k=1
and
k
2 - [|w--(ww
+ Px)12 - l|w -(w++1 + PA+1))13)]
k=1
1 ||w" - (W1 + P1)l
Vi || (We+1 2(
vT
Vk:
)//w"
-(w: +px)ll
2
2
2
2
k=
Since Q is bounded set, there exists positive number Mg > 0 such that
|| - (W1+1 + +P++1)l1 < Mo. 1t 20. 0.
Therefore
(t + = f(wo) f(w") aVEM aVtM2+ + Vt
Mo.
2a
This completes the proof of Theorem 3
is necessary to give some remarks about Theorem
In nonsmooth convex cases, Theorem 3 shows that the individual convergence rate of SGD can be accelerated from O lug to O v via the HB momentum. The proof here clarifies
vt
how the HB-type momentum w, w,-1 and its time-varying weight B3 help us to derive
the optimal individual convergence.
5

---

Published as a conference paper at ICLR 2021
The convergence analysis in Theorem is obviously different from the regret analysis in all the available papers, this is because the connection between f(w)) - f(w") and f(w,-1) f f(w") should be established here. It can be seen that sceking an optimal individual convergence is more difficult than the analysis of averaging convergence in many papers such (Zinkevich 2003) and (Yang al. (2016).
We can get stochastic HB by replacing the subgradient g( ((w)) in 7 with its unbiased estimation g(w.). Such substitution will not influence our convergence analysis. This
means that we can get (w,, f(w")] I 0 (+)) under the same assumptions.
If 3. remains a constant, we can get the averaging convergence rate, in which the proof of the first part is similar to Lemma and that of the second part is similar to online PSG (Zinkevich) 2003).
Theorem 4. Assume that Q bounded and 3e B < Let {weken be generated by HB Set
3 (W: w:-1) and az = Vt
P: 1 1 3-3
Then we have
1 at g( (ww)) f( Σ Wx) - f(ww)('w"")) - 0 Vt
W+41 + P1+1 = Palw, + P.
If Q is not bounded, the boundness of sequence || (w.+1 + P++1)]l can not be ensured, which may lead to the failure of Theorem 4 Fortunately, like that in (Yang et al. 2016).
E Ex Wk) - f[w"][]]=]))) < O (++)) still holds, but we need to set a = VT
4 EXTENSION TO ADAPTIVE CASES
is easy to find that HB is in fact gradient-based algorithm with predetermined step size Vi Thus its adaptive variant with EMA can be naturally formulated as
aB V. $ $g(w)) + Bie(we - We-1)]- tvB
W4+1 = Palw:
(12)
where
1
B1 2+2
V4 B + (1 82x ddaa ( (B(:)))(w.))]
The detailed steps of the adaptive HB are shown in Algorithm
Algorithm Adaptive HB
Input: momentum parameters Bic, 3z,, constant 8 > the total number of iterations T
1: Initialize Wo 0, Vo Oaxd
2: repeat
3: gr (w(w)) V.((W)))
4: Vi 3z1 V- + (1 Bee (w.))
5: V/ V + 6
aBu Ve "g(w)) + 3ie(w: w2-1)),
6: W Palwa, tvt
7: until t T
Output: WT
Theorem 5. Assume that bounded set. Let {wi] be generated by the adaptive HB (Algo-
rithm 7). Denote p: = t(w, w,-1). Suppose that B1 742 and 1 - < B2r S 7 for some
0<> 1. Then
W + P++1 = Pqlw, +p:
V. g((w))
(13)
V
E[f(w:) - f(w")] < 0 7

---

Published as a conference paper at ICLR 2021
The proof of (33 is identical that of Lemma] It is easy find that 13) is adaptive variant of This implies that the proof of the second part is similar to that of AdaGrad (Mukkamala & When 0 I S1e 3 < 1, the adaptive variant of HB 77) is
Hei 2017).
a V. $ *g(w.) + ((w. wi-1)l.
W++1 = Palwa
(14)
V
where
= B2 + (1 -
Similar to the proof of Theorem 5 we can get the following averaging convergence.
Theorem 6. Assume that Q is bounded and 0 S 31 = 3 1 in Algorithm Let {w, [w,]i=] be
generated by the adaptive HB (Algorithml) 7). Suppose that S $2r S 7 for some 057 $ 1.
Denote P: 1-8 (e We-1). Then
We+1 + P++1 Polw, + Pt (1- V1 g(w,)), B[f(
Σ wx) f(w S
is necessary to give some remarks about Theorem 5 and Theorem
The adaptive HB is usually used with a constant 61r in deep learning. However, accord- ing Theorem 6 the constant Bic only guarantees the optimal data-dependent averaging convergence. The convergence property of the last iterate still remains unknown.
In order assure the optimal individual convergence, according Theorem 31, has to be time-varying 31 142 can explain why we usually restrict B1 - in practice. It also offers a new schedule about the selection of momentum parameters in deep learning.
EXPERIMENTS
In this section, we present some empirical results. The first two experiments are to validate the correctness of our convergence analysis and investigate the performance of the suggested parameters schedule. For fair comparison, we independently repeat the experiments five times and report the averaged results. The last experiment (Appendix A.4) is to show the effective acceleration HB over GD in terms of the individual convergence.
5.1 EXPERIMENTS ON OPTIMIZING GENERAL CONVEX FUNCTIONS
This experiment is to optimize hinge loss with the -ball constraints. Let denotes the radius of the ball, For implementation of the l projection operation, we use SLEP package
min f(w), s.l. w E {w ||w/|, T..
(15)
Datasets: A9a, W8a, Covtype, Ijennl, Rcv1, Realsim (available at LibSVM website).
Algorithms: PSG (a, H.. HB (a: (1+2)V Br = NAG Tao al. 2020al and adaptive HB
12 (B1e= = ).
The relative function value f(w.) f(w.) epoch is illustrated in Figure I As expected, the
individual convergence the adaptive HB has almost the same behavior as the averaging output of PSG, and the individual output of HB and NAG. Since the three stochastic methods have the optimal convergence for general convex problems, we conclude that the stochastic adaptive HB attains the optimal individual convergence.
http://www.ciie.muu...i. on//s//ttooi/////oooootooo s/dataset.s)

---

Published as a conference paper at ICLR 2021
(a) Coviype (T = 50)
(b) Realsim (T = 60)
(c) A9a (T 20)
(d) W8a (T 30)
(e) Iiennl (r = 10)
(I Revl (T = 80)
Figure 1: Convergence on different LibSVM datasets
5.2 TRAINING DEEP NEURAL NETWORKS
These experiments are conducted on 4-layer CNN and ResNet-18 using a server with 2 NVIDIA 2080Ti GPUs
Datasets: MNIST (60000 training samples, 10000 test samples), CIFARIO (50000 training samples, 10000 test samples), and CIFAR 100 (50000 training samples, 10000 test samples).
Algorithms: Adam (a, B1: 0.9. 32 = 0.999, e = 10-8) (Kingma Ba 2014), SGD (a, = o),
SGD-momeettm (ag, = 0t B = 0.9). AdaGrad (o: a:) (Duchi et al. 201 1j. RMSprop (a: = a,
32. = 0.9, e = 10-8) 8) (Telleman & Hinton, 2012). For our adaptive HB, 7 0.1 and 10
Different from the existing methods, we set B 2+2 each epoch, 31c and 32r remain unchanged.
and 8o =
in Algorithm Within
Note that all methods have only one adjustable parameter a, we choose a from the set of {0.1. 0.01,
0.001, 0.0001} } for all experiments. Following (Mukkamala & Hein (017) and (Wang et al. 2020
we design a simple 4-layer CNN architecture that consists two convolutional layers (32 filters of size 3 x 3), one max-pooling layer (2 x 2 window and 0.25 dropout) and one fully connected layer (128 hidden units and 0.5 dropout). We also use weight decay and batch normalization to reduce over-fitting The optimal rate is always chosen for each algorithm separately that one achieves either best training objective or best test performance after a fixed number of epochs.
The loss function is the cross-entropy. The training loss results are illustrated in Figure 2 and 4 and the test accuracy results are presented in Figure 3 and 5 As can be seen, the adaptive HB achieves the improved training loss. Moreover, this improvement also leads good performance on test accuracy. The experimental results show that our suggested schedule about the momentum parameters could gain improved practical performance even in deep learning tasks.
6 CONCLUSION
In this paper, prove that the adaptive HB method attains optimal data-dependent individual convergence rate in the constrained convex cases, which bridges a theory-practice gap in using momentum methods train the deep neural networks as well as optimize the convex functions. 1 Our new analysis not only clarifies how the HB momentum and its time-varying weight 61c = सनद help us to achieve the acceleration but also gives valuable hints how its momentum parameters should be scheduled in deep learning. Empirical results on optimizing convex functions validate the
8

---

Published as a conference paper at ICLR 2021
236
1125
1.25
Teoleggoon
3.00
0:48
042
080
Figure 2: Training loss v.s. number of epochs on 4-layer CNN: CIFAR1O, CIFAR100, MNIST
0.20
6.73
Adspien 10
Adhaggat
090
Figure 3: Test accuracy v.s. number of epochs on 4-layer CNN: CIFARTO, CIFARIOO, MNIST
1.5
67330
0.10
0.2
0.5
6005
103
Figure 4: Training loss number of epochs ResNet- 18: CIFARIO, CIFARIO0, MNIST
Figure 5: Test accuracy v.s. number of epochs ResNet-18: CIFARIO, CIFAR100, MNIST
correctness of convergence analysis and several typical deep learning experiments demonstrate the improved performance of the adaptive HB.
7 ACKNOWLEDGEMENTS
This work was supported in part by National Natural Science Foundation of China under Grants (62076252, 61673394, 61976213) and in part by Beijing Advanced Discipline Fund.

---

Published as a conference paper at ICLR 2021
REFERENCES
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. new regret analy- sis for adam-type algorithms. In Proceedings of the International Conference on Machine Learn- ing, 2020.
Xi Chen, Qihang Lin, and Javier Pena. Optimal regularized dual averaging methods for stochastic optimization. In Advances in Neural Information Processing Systems, pp. 395-403, 2012.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In International Conference Leurning Representa- lions, 2019.
Alexandre Défossez, L. Bottou, Francis Bach, and Nicolas Usunier. On the convergence of adam and adagrad. ArXiv, abs/2003.02393 2020.
Bertsekas Dimitri P., Nedić Angelia., and Ozdaglar Asuman E. Convex analysis and optimization. Athena Scientific, 2003.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7),
John C Duchi. Introductory lectures on stochastic optimization. The mathematics of data, 25:99, 2018.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European Control Conference (ECC), pp. 310-315. IEEE, 2015.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. In Advances Neural Information Processing Systems, pp. 9630- 9640, 2019.
Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non- smooth stochastic gradient descent. In Annual Conference on Learning Theory, pp. 1579-1613, 2019.
Chonghai Hu, Weike Pan, and James T Kwok. Accelerated gradient methods for stochastic optimiza- tion and online learning. In Advances in Neural Information Processing Systems, pp. 781-789, 2009.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Annual Conference on Learning Theory, pp. 1752-1755, 2019.
Diederik P Kingma and Jimmy Ba. The unusual effectiveness of averaging in gan training. In International Conference on Learning Representations, 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over-parameterized learn- ing. In International Conference on Learning Representations, 2020.
Mahesh Chandra Mukkamala and Matthis Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. International Conference on Machine Learning, 2017.
Arkadi Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. John Wiley & Sons, 1983.
Yu Nesterov. A method of solving convex programming problem with convergence rate o(1/k²). Soviet Mathematics Doklady, 27(2):372-376, 1983.
Peter Ochs, Yunjin Chen, Thomas Brox, and Thomas Pock. ipiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences, 7(2):1388-144) 2014.
10

---

Published as a conference paper at ICLR 2021
Antonio Orvieto, Jonas Köhler, and A. Lucchi. The role of memory in stochastic optimization. ArXiv, abs/1900.00178,, 2019.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Com- putational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv: 109.5647, 2011.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint UrXiv:1609.044 047477 2016.
Othmane Sebbouh, Robert Mansel Gower, and Aaron Defazio. On the convergence of the stochastic heavy ball method. ArXiv, abs/2006.07867, 2020.
Ohad Shamir. Open problem: Is averaging needed for strongly convex stochastic gradient descent? In Anual Conference on Learning Theory, pp. 1-3, 2012.
Tao Sun, Dongsheng Li, Zhe Quan, Hao Jiang, Shengguo Li, and Yong Dou. Heavy-ball algorithms 2019a.
always escape saddle points. arXiv preprint arXiv:
Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, L. Guan, and Hao Jiang. Non-ergodic con- vergence analysis of heavy-ball algorithms, In AAAI, 2019b.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum deep learning. In International Conference on Machine Learning, pp- 2013.
Wei Tao, Zhisong Pan, Gaowei Wu, and Qing Tao. The strength of nesterov's extrapolation in the individual convergence of nonsmooth optimization. IEEE Transactions on Neural Networks and Learning Systems, 31(7):2557-2568 2020a.
Wei Tao, Zhisong Pan, Gaowei Wu, and Qing Tao. Primal averaging: A new gradient evaluation step to attain the optimal individual convergence. IEEE Transactions on Cybernetics, 50(2):835-88) 845, 2020b.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop, coursera: Neural networks for machine learning. University of Toronto, Technical Report, 2012.
Guanghui Wang. Shiyin Lu, Weiwei Tu, and Lijun Zhang. Sadam: A variant of adam for strongly
convex functions. In International Conference on Learning Representations, 2020.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances neural information pro- cessing systems, pp. 4148-4158 4158, 2017.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint arXiv:1604.03257, 2016.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the International Conference on Machine Learning, pp. 928-936. 2003.
Fangyu Zou, Li Shen, Zequn Jie, Sun, and Wei Liu. Weighted adagrad with unified momentum. arXiv preprint arXiv: 1808, 03408, 2018
11

---

Published as a conference paper at ICLR 2021
A SUPPLEMENTARY MATERIAL
A.1 PROOF FOR THEOREM 4
Let {we]e=1 be generated by HB Set
Pr 8 (w, w.-1) and az = a
Vi
Then, Vw E Q, according to Lemma 1 we have
(We+1 - W. 3(w, we-1) + arg(w:)) We+1 - w) S.
This is
1 B (We+1 -w)) - P: +
at
g((w) (W:))) We+1 w) S.
1
i.e.
(Wz41 Pr+1 - (wr pp) + a4
B g( (Wo), We+1 w) 00
(16)
Specifically,
3(Wz+] wo)
(We+1 + Pt+1 (W; Pc) +
1 B 8(we);
ar
(17)
1 1-
From
16 and
(We+1 + PA+1 - (W, Pc) + at
g B(w.). We+1 +P++1 - -w) $O.
Using Lemma
we have
We+1 + P++1
Palws + Pt 1 3 g(w))).
at
Then
|w - -(W+11 + 1|
</|w" - (w, + +p:) + 1 g g(,)))
0z
=||w" - (wr + pt) + - 1--g((v g(( )12 + 2( at
( w- w.)
+2( 008
B)z (w:)), Wi-1 w.)
Note
(g(w:), w - -() S - f(w))) (g(w.), wi-1- - we) S f((w-1) - f(w.).
Then
w -(w++1 + 11+1)112
of
</|w" (w. + +P)+p)1++ + (1 (1- (1=)))ll((ww)))
204 [f(((W)-- f(w))] + (1- g)2 1f (f(WW-1) f(w.)).
20,3
Rearrange the inequality, we have
20t
2013
- [J(w:) - f(w")] < (1 - B32 [[(W--1) [((w)) )] + || - -ww, + p:)
a?
l|ww -we+1 + P=+1)11 + (1- 1-3 (g(()))12.
12

---

Published as a conference paper at ICLR 2021
ie.,
f(wi) - f(w")= 1 1 (f(w - [(ws)] + 1 3 l//w" - (we + P:)l
20x
-Iww" (W141 + Pt+1))l9 +
2(1 - 3) |g((;)]l?.
a4
Summing this inequality from & = 1 to obtain
(f(w) - f[(w)]
B (S(w)) -[(w,)] 1 3
|w"
w-"-(w ((w1 +p)ll
201
1 - B 1| - (We+1 + 1l+1)ll
0
g(())ll
20t
2(1 3) k=
1 B
1
Iw (wx + (
20%
20 1
i.c.
[f(w)) - f[ww)]
R=1
B (f(wo) - -[(we)]
+ 1- || - -(w1- + P:)l1
B
2a
(18)
(1 B)Vk (1- 3)vKv
l|w" - -(wx + 22)
2xx
2a
k=2
+
a
B) k Bl
2(1
k=1
Note
Σ 2/h
I()))) VIM2
(19)
and since Q is bounded set, there exists a positive number Mo > 0 such that
||w" - (W++1 + P++1)ll < Mo, Vt 2 0.
(20)
From 18
20
we have,
Σls(wa S(w") 1- 1--BU(n) (((w))-((ww)) S(w:)] + (1 3)VLM
aVIM²
+
2a
1-3
A=1 By convexity of f(w). we obtain
Ws) f(w") 5 (1 Btt (s(wo) - [(wi)] + (1- 3)Mo
B
aM2
+
2047
(1-B)vh
This completes the proof of Theorem 4
A.2 PROOF FOR THEOREM 5
Notation. For a positive definite matrix Rdxdd the weighted f2-norm is defined by ||x| Hx. The H H-weighted projection PHj (x) of x onto Q is defined by Pd (x) = arg minyeq lly X We use g(wx) to denote the subgradient of fx(:) at w For the diagonal matrix sequence my, denote the i-th element in the diagonal of Mg. We introduce the notation,
(Ms)] ye j-
Mi.ki (91,5, 92 "k.) where ge.i is the i-th element of g(wa).
13

---

Published as a conference paper at ICLR 2021
Lemma 7. t 2 1. then
(Mukkamala & Hein 2017 Suppose that
- 1 B21 S for some Ocy S and
Lh.t kuk +
2(2 - 7) (vbor, + +0).
Proof for Theorem Without loss of generality, only prove Theorem in the full gradient setting. It can be extended to stochastic cases using the regular technique in (Rakhlin et al. 2011).
Note that the projection operation be rewritten
optimization problem Ducchi 2018 i.e.
Wt+1 Polw, 0g V g( (W2) Bie(W, w.-1)] equivalent
Wi+1 = arg min far (V, WEQ
(V.VVVVVVVW g(w)), w) + 1 I We -Br(W, wi-1))
2
(21)
2
Then, Vu Q, we have
(We+1 W: - - w.-1) az gg W
- w0
This is
(Wi-1 P1+1 - (wr + Pt)
Vt V/ g(w:),, Wi+1 w) S 0.
(22)
Specifically,
(We1 + Pi+1 (w, Pi) + v. g(w,). We+1 wi) w)) 5..
(23)
Vt
From
22
and 23
(W++1 + P1+1 (Wa++ + Pt) + a V (((:)) W - we + (t ()(((1)((w))) - -w)) s O.
Vt
i.e.,
(We+1 + Pi+1 - (w, + Pt) + a V g((w), we+1 + P wi) $o.
Vt
Using Lemma
we have
We+1 + Pc+1 P8i (w + Pa Vt
v. (/-g((ws))
Then
||w- - (We+1 + P.+1)lle; S /|w - -(w, + p:) + a
1 g(
(l?)
Vt
=||w" -(w, + +p=)ll3 + || g(
Vt
a
w.
1/2
2 V (((()) w- - -w) 2 at
/ g( (w)) g(())
w.-1 -we).
Note
(g(w,), w- - w.) $ f(w") - f(w.). (g(w)). - w.) - f(w..1) - f(w.).
Then
Vt 2a
(t ()[[())(.)) f(w")] <t(f(w:-1) f(ww))
l| (we + p:).
Vt
||w" -W2++ + 1)+1
+ a
(IB(w:)ll3
2a
25
Summing this inequality from & = 1 to t, we obtain
(t 1)(f(w.) f(w S f(wo) f(w")
a
(l(()))l
k=1 2
(I|w* - (wx + px)1 - -|w--
--"-(wap -(we+1 + Px+1))l?+)
2a
14

---

Published as a conference paper at ICLR 2021
Using Lemma have
a(2 - 7) d Σ
Σ k=1
gg(
((())))
(vter, + o).
2
7
1=1
Note
V (l/w" (W* palll,
-llw (Wi+1 (P++))l(,))
2x
U1dd (w: - +.V.i+P1...)) Σ vtuu (w; - (W1+1,1 + +
(24)
20x
2a
(Viek, vk 1,) (Wa.) + Pk..))².
20
1=1 2=
Since Q is a bounded set, there exists positive number M1 > 0 such that
(w, (Wi+1,i P)+1,))) < M1, Vt 2 0, i 1,2, d.
and Uk.s 12, (1 32x)92, well as 82k 2 1 : which implies k:2x get
Vkūn. = /kUR, +
1:B2nRo-11 1,8 + 1s1 )g, + 8
1. 6 (I: 11
k 164-1,4-
Therefore
(||w*
(W* + pb)ll - -llw" - -WwK+ + 11+1))12 )]
20
01.
M1
(Vieky Vk 10x- M1
20x
2a
k=
(25)
0
20
20
2a
1=1
1=1
M₁
V tul, + 6).
2a
1=1
Since Vtr,a = 11 therefore
Mi d
d
a(2 -
(t ()])(w).,) f(w*) <f(wo) - f(ww) +
Σ ( tu,, + +5) + Σ
(VEet, + 8)
2a
7
i=1
iml
M1 +
al2 7)
=f(wo) s(w")
Σ (1 ill + 8).
This proves
f(wi)- - f(m)) V
A.3 PROOF FOR THEOREM 6
Let [wr) be generated by the adaptive HB (Algorithm) D. Set
9
(w: W.-1) and a; = a
1- 3
Vt
15

---

Published as a conference paper at ICLR 2021
Then, Vu Q, according Lemma | have
(Wi+1* -(w, w + +
g(we), (
- -w)
This is
1 (1 1 (W+11 wi) - Pt + ar VeV; g(wi). W(+1 w) 0.
1 1 3
i.e.,
(W++1 + - (w, + 04 V
- g Wi W++1 w) 0
(26)
Specifically,
Wa+1 + Pi+1 (We Pı) + a2 V
1 1- B(wi), B(W++1 wt),
1-3 S
(27)
From
26
and 27
(W; + Pt) + a.V;-1
(We1 + P++1
1 g(w:), W+41 + Pr+1 w) S.
Using Lemma
we have
W++1 + P1+1
plc W: + Pt
g( [W)))
1 B
According to Lemma
|w" (Wi+1 + 1
S lw" (w: + Pt) + at V.V.
1 3 g 1 Ps
1|w" (w, + pt))l + g( (w:))l?
+2( - 3 g(ww)) w- we) + 2( a,
at
w w w -w.)
(1 - B)2
Note
(g(w)), w" wi) S f(ww) - f(w)). (g(w)), Wi-1 ww) s f(w(-) - f(w)).
Then
1| (w + 11
at
< <l|w² - (w, p:)lf
8)2 (-)))>lB(ww))) (g(l(w)))) w: )
(1-3)²
204
2013
- + (1- 8)2 (f(w(-1) f(w.)].
1 1 3
Rearrange the inequality, have
2a
(s(w:) [(w")]
1 3
3
<
(1 B)2 [S(We-1) - [[(w)] + ||w" - -(w, + -p))l?
of
1 - (We+1 + Pi+1)ll,, + (1- B)² Ilg( (g(w:))l?_
ie.,
f(wi) - -f(w")
< 3
[f((w-1) - f(w.)] + 1- [| -(we + p.)
2a,
l|w" -(we+1 + + +
2(1 - 3) llg(w (l((:))l?, 1.
at
16

---

Published as a conference paper at ICLR 2021
Summing this inequality from & = 1 to obtain
[f(w) - f(ww)]
1 3 [s(wo) -[(w))] + 1 3
B
1|w* (W1 +Pi)ll
201
1 1 3 1| -(w++1 + Pi+1)ll
04
|g[ ((Ww)) I1
20
2(1 (3)
k=1
(1 3)rx..
(1 1)
+
(w) (Wh.s + PA.)))
2cx
2
k=2
i.c.
[f(w)) - [[ww)]
k=1
1-3
[f(wo) -f(we)] +
||w" (WI + +1)lli
2a
(28)
2 1-1 (Vkōv. Vk 1,i)
(w; (Wa, + Pk,
2a
k=2
2(1 B)Vk [B(w=))l
k=1
Using Lemma 7 we have
2vR(1 - B)) Il S Σ a(2 - 7)
7(1 3) (yter, + + a(2 7) 7(1 B) Σ
(1192...il + 5). (29)
and since Q is bounded set, there exists a positive number Mo > 0 such that
||w" (Wz+1 + (P+1)ll < Mo, V1 2 0.
(30)
From 28 29
30
we have,
> (f(w)) - f(w")]
B 8 (f(wo) -[(w)]
d (1 B)
a(2 -2) d
Σ (11 +0)
+
2a
7(1 33)
1=1
1=1
(1 - SVMoo
(1 M0
20
2a
1=1
ie.,
t [((()) s(w*)]
1- [(W
8
a(2-7) d
Σ
(11g,,,11+0) 1l+)+++++++++++) (1 -1- B)Mb
Σ (l))
7(1
2x
By convexity of f(W*). we obtain
B Σ w1) www (1 01t (1
a(2-7) -7) d
(1 (1 - B)
Σ
Σ
(11gaa +ll)).
7(1 3)t 1=1
2at
This completes the proof of Theorem 6
17

---

Published as a conference paper at ICLR 2021
A.4 EXPERIMENTS ON OPTIMIZING SYNTHETIC CONVEX FUNCTION
constrained convex optimization problem was constructed in (Harvey et al. 2019 to show that the optimal individual convergence rate SGD is O loge) ). We will use example to illustrate the acceleration of HB.
vt
Let Q unit ball R For E (T) and 2 define the positive scalar parameters
1
Vi
b;
8c(T - + 1)
2CVT
Define f Q > and h; E RD for i [T by
aj 13j<t <i
f(w) = max h. w iE[T]
where
bag
bj. i=j<T
0, i<jsT
684
500
Figure 6: Convergence of the function value when T 1000 and T = 5000
Obviously, the minimum value f on the unit ball is non-positive because ʃ(0) = 0. can be proved f f(rr) 2 log 32c//T. Set = 2, the function value f(w,) v.s. iteration is illustrated in Figure 6
where the step size of GD is v and the parameters of the constrained HB (7) (a 8) and AdaHB
12) (a = 0.08, 7 = 0.9, = 10 8) are selected according to Theorem 3 and Theorem 5 As expected, the individual convergence of HB is much faster than that of PSG. We thus conclude that
HB is an effective acceleration of GD in terms of the individual convergence.
18


Reviews:
[{"review_id": "x2cHXCgddCd", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe convergence of Momentum methods has been widely studied but most of existing works consider the average convergence. In this work the author considers the individual convergence of the last iteration. The accelerated convergence rate O(1/sqrt(t)) is established.\n\nPros:\n1. The individual convergence of momentum methods is pretty interesting. It is very valuable to established the accelerated convergence rate, which is missing in the existing litterature.\n\n2. The paper overall is well written but need to reword some statement for rigorousness.\n\nCons:\n1. This paper only consider convex optimization. This limits its effectiveness to explain the good performance of momentum method in training deep neural networks.\n\n2. I suggest the authors to reword their statement of the third contribution on page 3 \"However, in order to get the optimal individual convergence, β1t has to be time-varying\". Theorem 4 only shows that adaptive momentum can achieve individual convergence. Theorem 5 shows that constant momentum can achieve average convergence. These two results cannot lead to the conclusion that constant moment does not have individual convergence. In fact, we have observed it in practice. Moreover, the author should add more discussion on the difficulty of establish constant convergence for constant momentum\n\n3. There is a large gap between the numerical and theoretical results. In the theoretical result, the authors consider convex optimization which is quite different from training deep neural networks. Moreover, when training DNN, the algorithm used is SGD with momentum but not GD with momentum. Note that M-SGD and M-GD has significantly difference, I am not sure how the theoretical results can provide useful hints to practice.\n\nMinor Comments:\n1. The abstract mentions that the numerical result on convex optimization is included. However, I don't find this result. Please add it.\n2. I hope the authors can provide more proof sketch to help the reader understand the proof.", "extra_scores": {}, "extra_text": {}}, {"review_id": "dIYYegEuAi", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors investigate the convergence of the projected Heavy-ball method (and an adaptive variant) for convex problems with convex constraints. The authors prove 4 results: 2 individual (last iterate) convergence rates and 2 rates using averaging. Notably, in their proofs they require an increasing (from 1/2 to 1) momentum parameter and a decreasing stepsize. Finally, the authors present some experimental results.\n\nThe paper is overall a nice and pleasant read, with no major typos and a nice introduction. Also, to the best of my knowledge, the individual convergence rates proved by the authors are novel.\nHowever, I do not think the paper is ready for publication, for the following reasons (in order of importance, the last points are easy-to-fix)\n\n1) The paper is short – the main section is only 2 pages and the proof (in the appendix) does not exceed one page. I am not particularly blown away by the results or the proof technique – I think the authors should try to extend their study. For instance, an easy way to make the result more general is to extend it to momentum parameters of the form t/(t+r) for r>2 (it should work the same).\n\n2) Reading the paper, it seems the authors are the first to provide an individual convergence rate for HB. This is not true, indeed Ghadimi 2015 also has a rate of O(1/t) for the last iterate of HB under momentum t/(t+2)  and stepsize 1/t. Here, the authors add a projection, hence have to also reduce the stepsize to 1/t^3/2.. @authors is this the only novelty? Also, an increasing momentum is considered in Orvieto et al. 2019 (Role of memory in stochastic optimization).\n\n3) Even though the authors claim to have convex empirical results in the abstract, the experiments are for non convex problems (a CNN model). This in my view does not make much sense since (a) the authors only study convex problems with convex constraints (where are the constraints here?), (b) no experiment has a decreasing stepsize (c) a momentum of k/(k+2) was shown already in Sutskever et al. 2013 not to be optimal in the non convex case. In essence, I think the experiments do not back up the theory: the authors should at least compare with a fixed-momentum method.\n\n4) I am seriously not convinced that O(1/t) compared to O(log(t)/t ) motivates the so-called “acceleration” of Heavy ball. I think the authors should rephrase that. Btw @authors can you actually see this log difference in experiments on convex objectives? Also, it would be great to cite and compare your result/proof technique with Defossez et al. 2019 (On the convergence of Adam and Adagrad).\n\n5) Many results are presented without proof, such as the ones for the stochastic case.\n\nI think the authors should take some time to work on their interesting direction and resubmit to ICML. I think the results are interesting, just they need to be discussed/complemented/verified a bit better.\n\n------------------------------------------\n\nScore updated after rebuttal, please see comment below", "extra_scores": {}, "extra_text": {}}, {"review_id": "XWUCRxcKD60", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper's major contribution is analyzing the HB method for non-smooth objectives functions and showing the last iterate convergence for it. Comparing to existing results, they show a tighter upper bound by dropping a log(t) term from the\nsuboptimality's upper bound. It also analysis an adaptive variant of the HB and show similar results. All the proofs are clear and straightforward.\n\nComments: \n\n1- This paper needs major rewriting and restructuring and in its current format is not ready to be published. \nThe abstract talks about a specific parameter and its value, which the reader has no idea about it. \n\n a)- When an acronym is used, its full name should appear once before.\n\n b)- Typos exist in their proof. For example, in the proof of Lemma 1, and in the last equation, there is no u, but the line above reads for all u in Q. Also, in the paragraph for the paper's 3rd contribution, it says decaying \\beta_1,t goes to 1. It is not a decaying but increasing parameter. \n\nc)- There are two appendices, one at the end of the main part, and the other part is in a separate file. \n\nd)- Two related works which haven’t been considered in related work \n      Sebbouh O., et.al. On the convergence of the Stochastic Heavy Ball Method\n      Sun, T. et. la., Non-Ergodic Convergence Analysis of Heavy-Ball Algorithms\n\n2- In terms of contributions: \n\na)- I don’t think dropping a log(t) terms in an analysis of a method means acceleration. Usually, Log(t) term appears due to some technical difficulties in the analysis and also in practice when training a model is not a large value. \n\nb)- Since you compare the HB method with SGD, I suggest putting the proof for stochastic HB instead of the deterministic case. \n\nc)- In the experimental section, it would be nice to see the results on bigger datasets like Imagenet and also different tasks such as NLP models. Moreover, for SGD you set the step size \\alpha_t to be fixed, which theoretically SGD won’t converge in this situation. To be fair, similar to your sep-size, which is decreasing \\alpha_t for SGD should be decreasing with an appropriate rate. Finally, since you run the experiments for 5 runs, it would be useful to add the error bar to your graphs. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0E4RZoVI_cl", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper provides the convergence analysis of the Heavy-ball method with the individual convergence and provides the convergence of its adaptive version. \n\nPros: \n\n1. The motivation is interesting, most of time we use the last iteration while most of theorem can only provide convergence result for the average output. I am glad to see that the theoretical proof of the individual convergence for stochastic Heavy-ball method is studied in this paper,  \n\n2. The convergence result of HB methods achieved in this paper is 1/\\sqrt(t) which is better the optimal result of SGD. This demonstrate the advantage of momentum-based methods.\n\n3. Their proof is different form all the existing analysis of averaging convergence.\n\nCons:\n\n1. It will be much better if the author can explain more on the difference between the current proof and the existing proof. \n\n\nOverall, I tend to accept this paper. However I am not an expert on this area and I will not be sad if this paper is rejected by others.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the *last iterate* convergence of the projected Heavy-ball method (and an adaptive variant) for convex problems, and propose a specific coefficient schedule. All reviewers thought that looking at the last-iterate convergence of the HB method was interesting and that the proofs, while simple, were interestingly novel. Several concerns were raised by the quality of the writing. Several were addressed in a revision and the rebuttal. While R1 did not update their score, the AC thinks that the rebuttal has addressed appropriately their initial concerns. The AC recommends the paper for acceptance, *but* it is important that the authors make an appropriate careful pass over their paper for the camera ready version.

### comments about the write-up

- The paper still contains many typos (e.g. missing $1/t$ term in the average after equation (2); many misspelled words, etc.), please carefully proofread your paper again.
- The AC agrees with R1 that the quality of presentation still needs improvement. $\beta_{1t}$ is still used in the introduction without being defined -- please define it properly first e.g. 
- The word "optimal" and "optimality" is usually misused in the manuscript. To refer to the convergence rate of an optimization algorithm, the standard terminology is to talk about the "suboptimality" or the "error" (e.g. see the terminology used by the cited [Harvey et al. 2019, Jain et al. 2019] papers). For example, one would say that the error or suboptimality of SGD has a $O(1/\sqrt{t})$ convergence rate. Saying "optimality of" or "optimal individual convergence rate" is quite confusing, and should be corrected. The adjective "optimal" (when talking about a convergence rate) should be restricted to when a matching lower bound exists.
- Finally, the text introducing the experimental section should be fixed to clarify the actual results and motivation. Specifically, the "validate the correctness of our convergence analysis" only applies in the convex setting. I recommend that a high level description of the convex experiment and the main message of the results is moved from the appendix to the main paper there (there is space). And then, the deep learning experiments can be introduced as just investigating the practical performance of the suggested coefficient schedule for HB.
Decision: Accept (Poster)