Linear Convergence and Implicit Regularization of Generalized Mirror Descent with Time-Dependent Mirrors
Authors: Adityanarayanan Radhakrishnan
Mikhail Belkin
Caroline Uhler
Venue:  (2021)
Keywords: Generalized Mirror Descent
Linear Convergence
Implicit Regularization

Abstract:  The following questions are fundamental to understanding the properties of over-parameterization in modern machine learning: (1) Under what conditions and at what rate does training converge to a global minimum? (2) What form of implicit regularization occurs through training? While significant progress has been made in answering both of these questions for gradient descent, they have yet to be answered more completely for general optimization methods. In this work, we establish sufficient conditions for linear convergence and obtain approximate implicit regularization results for generalized mirror descent (GMD), a generalization of mirror descent with a possibly time-dependent mirror. GMD subsumes popular first order optimization methods including gradient descent, mirror descent, and preconditioned gradient descent methods such as Adagrad. By using the Polyak-Lojasiewicz inequality, we first present a simple analysis under which non-stochastic GMD converges linearly to a global minimum. We then present a novel, Taylor-series based analysis to establish sufficient conditions for linear convergence of stochastic GMD. As a corollary, our result establishes sufficient conditions and provides learning rates for linear convergence of stochastic mirror descent and Adagrad. Lastly, we obtain approximate implicit regularization results for GMD by proving that GMD converges to an interpolating solution that is approximately the closest interpolating solution to the initialization in l2-norm in the dual space, thereby generalizing the result of Azizan, Lale, and Hassibi (2019) in the full batch setting. 

Under review as a conference paper at ICLR 2021
LINEAR CONVERGENCE AND IMPLICIT REGULAR- IZATION OF GENERALIZED MIRROR DESCENT WITH TIME-DEPENDENT MIRRORS
Anonymous authors Paper under double-blind review
ABSTRACT
The following questions are fundamental to understanding the properties of over- parameterization in modern machine learning: (1) Under what conditions and at what rate does training converge to a global minimum?
(2) What form of im- plicit regularization occurs through training? While significant progress has been made in answering both of these questions for gradient descent, they have yet to be answered more completely for general optimization methods. In this work, we establish sufficient conditions for linear convergence and obtain approximate implicit regularization results for generalized mirror descen! (GMD), general- ization of mirror descent with a possibly time-dependent mirror. GMD subsumes popular first order optimization methods including gradient descent, mirror de- scent, and preconditioned gradient descent methods such as Adagrad. By using the Polyak-Lojasiewiez inequality, we first present simple analysis under which non-stochastic GMD converges linearly to global minimum. We then present a novel, Taylor-series based analysis to establish sufficient conditions for linear convergence of stochastic GMD. As corollary, result establishes sufficient conditions and provides learning rates for linear convergence of stochastic mirror descent and Adagrad. Lastly, we obtain approximate implicit regularization re- sults for GMD by proving that GMD) converges to an interpolating solution that is approximately the closest interpolating solution the initialization in f--norm in the dual space.
INTRODUCTION
Recent work has established the optimization and generalization benefits of over-paramettrrzzaion
in machine learning (Belkin et al. 2019 Liu et al. 20200 Zhang al. 2017). ). In particular, several works including Vaswani et al. (2019); Du et al. 20188; Liu et al. (2020); ; Li & Liang (2018) have global minimum when trained using stochastic gradient descent and that such convergence can occur at a linear rate. Independently, other work, such Gunasekar et al. (2018), have characterized implicit regularization of over- parameterized models, i.e., the properties of the solution selected by a given optimization method, without proving convergence.
demonstrated that perrtparameterized models converge
Recently, Azizan & Hassibi 2019); Azizan al. (019)) simultaneously proved convergence and an- alyzed approximate implicit regularization for mirror descent (Beck & Teboulle 2003 Nemirovsky & Yudin 1983). In particular, by using the fundamental identity of stochastic mirror descent (SMD), they proved that SMD converges to an interpolating solution that is approximately the closest one to the initialization in Bregman divergence. However, these works do not provide a rate of convergence for SMD and assume that there exists an interpolating solution within in Bregman divergence from the initialization. In this work, we provide sufficient conditions for linear convergence and ob- tain approximate implicit regularization results for generalized mirror descent (GMD), an extension of mirror descent that introduces (1) potential free update rule and (2) time-dependent mirror; namely, GMD with invertible Φ Rd - Rd and learning rate y is used to minimize real valued loss function, f. according to the update rule:
(0 (wi(t+)) 6000 -()(())))((((())))

---

Under review as a conference paper at ICLR 2021
We discuss the stochastic version of GMD (SGMD) in Section descent and preconditioning methods. Namely, if for all 4, 20 Vip for some strictly convex function e, then GMD corresponds to mirror descent with potential vx if g(t) = G for some
GMD generalizes both mirror
invertible matrix G E IRdxd, then the update rule in equation reduces to
w (1+1) w n) (w=
and hence represents applying pre-conditioner to gradient updates. The following is summary of our results:
1. We provide simple proof for linear convergence of GMD under the Polyak-LLojasewiie inequality (Theorem D
2. We provide sufficient conditions under which SGMD converges linearly under an adaptive learning rate (Theorems 2 and
3. As corollaries to Theorems and in Section we provide sufficient conditions for linear convergence of stochastic mirror descent as well as stochastic preconditioner methods such as Adagrad (Duchi et al. 2011).
4. We prove the existence of an interpolating solution and linear convergence of GMD to this solution for non-negative loss functions that locally satisfy the PL" inequality (Liu et al., 2020). This result (Theorem 4 provides approximate implicit regularization results for GMD: GMD converges linearly to interpolating solution that is approximately the closest interpolating solution to the initialization in &g norm in the dual space induced by d(')
2 RELATED WORK
Recent work (Azizan et al. 2019 established convergence of stochastic mirror descent (SMD) for nonlinear optimization problems. It characterized the implicit bias of mirror descent by demon- strating that SMD converges global minimum that is within epsilon of the closest interpolating solution in Bregman divergence. The analysis in Azizan et al.] (2019) relies on the fundamental identity of SMD and does not provide explicit learning rates or establish rate of convergence for SMD in the nonlinear setting. The work in (Azizznn & Hassibi (2019) provided explicit learning rates for the convergence SMD in the linear setting under strongly convex potential, again without a rate of convergence. While these works established convergence of SMD, prior work by Gunasekar ct al. 2018) analyzed the implicit bias of SMD without proving convergence.
A potential-base version of generalized mirror descent with time-varying regularizes was presented for online problems in Orabona et al. (2013). That work is primarily concerned with establishing regret bounds for the online learning setting, which differs from our setting of minimizing loss function given a set of known data points. A potential-fre free formulation of GMD for the flow was presented in Gunasekar et al. 2020).
The Polyak-LLojssewiczz (PI.) inequality (Lojasiewiez. 1963 Polyak
1963) serves simple condi- tion for linear convergence in non-convex optimization problems and is satisfied in a number of set- tings including weer-earamterrize neural networks (Liu et al. (2020). Work by Karimi et al. (2016) demonstrated linear convergence of a number of descent methods (including gradient descent) under the PL inequality. Similarly, Vaswani et al. (2019) proved linear convergence of stochastic gradient descent (SGD) under the PL inequality and the strong growth condition (SGC). and BBsssly et al. (2018) established the same rate for SGD under just the PL inequality. [Soltanolkotabi et al. (2019) also used the PI. inequality to establish local linear convergence result for gradient descent on hiddden layer ever-parameterizer neural networks.
Recently, Xie et al. (2020) established linear convergence for norm version of Adagrad (Adagrad- Norm) using the PL inequality, while Wu et al. (2019) established linear convergence for Adagrad- Norm in the particular setting of over- per-paaameterized neural networks with one hidden layer. An alternate analysis for Adagrad-Nor for smooth, non-convex functions was presented in Ward et al. (0199) resulting in a sub-linear convergence rate.
We also provide fixed learning rate for monotonically decreasing gradients (z
2

---

Under review as a conference paper at ICLR 2021
Instead of focusing on specific method, the goal of this work is to establish sufficient conditions for linear convergence by applying the PL inequality to a more general setting (SGMD). We arrive at linear convergence for specific methods such mirror descent and preconditioned gradient descent methods as corollaries. Moreover, our local convergence results provide an intuitive formulation of approximate implicit regularization for GMD and thus mirror descent. Namely, instead of sorting to Bregman divergence, we prove that GMD converges to an interpolating solution that is approximately the closest interpolating solution the initialization in & norm in the dual space induced by ()())
ALGORITHM DESCRIPTION AND PRELIMINARIES
We begin with a formal description of SGMD. Let E2 R denote real-valued, differentiable
loss functions and let f(z) E== f((z). In addition. let σL F + R be invertible function for all non-negative integers t. We solve the optimization problem
arg min f(x #ER*
using stochastic generalized mirror descent with learning rate
(w)((+) (w(*) V (w()),
(2)
where is E [n] is chosen uniformly at random. As descrihed in the introduction, the above algorithm
generalizes both gradient descent (where <xx) = x)) and mirror descent (where ()*( (x) = Vip(z)
for some strictly convex potential function ()). In the case where (())()) = G(O)z for an invertible
matrix ((t) E dRd the update rule in equation 2 reduces to:
w w r)(*() (og(())''vuo V. (wl
Hence, when (f is an invertible linear transformation, Equation 2 is equivalent to pre-conditioned gradient descent. We now present the Polyak-Lojasiewiie inequality and lemmas from optimization theory that will be used in our proof
Polyak-Lojasiewiez (PL) Inequality. A function f: R: - is p-PL for some μ >> O:
|V[(>)| ((t=)) ((x))) Vo R2
where x² E TR.d is a global minimizer for f-
A useful variation of the PL inequality is the PL. inequality introduced in Liu et al. 2020 which does not require knowledge of f(x").
Definition. A function Rd IR is p-PL" for some μ 0:
[][()) uf(x) Vo E Rd
function that is p-PL" is also p-PL when f is non nog-negative. Additionally, we will typically assume that f is L-smooth (with L-Lipschitz continuous derivative).
Definition. A function f Rdd > IR is L-smooth for L, > 0 for all x, E Rd:
[V)()) - f L||x w|l-
If (1(0 (z) x for any and x E Rd then SGMD reduces to SGD. If f is L-smooth and satisfies the PL-Inequality, then SGD converges linearly to global minimum (Bassily et al. 2018 Karimi cet al., 2016 Vaswani et al. 2019). Moreover, the following lemma (proven in Appendix A shows that the PL condition implies the existence of global minimum x" for non-negative, L-smooth f-
Lemma 1. ff Rd + R is μ-PL", L-smooth and f(x) 2 0 for all x E Rd. then gradient descent with learning rate 7 T/2 converges linearly to x" satisfying f(x*)
The framework also allows for adaptive leamning rates by using (7() to denote a time-dependent step size. We assume all norms the 2-norm unless stated otherwise.
3

---

Under review as a conference paper at ICLR 2021
Hence, in cases where the loss function is nonnegative (for example the squared loss), move the usual assumption about the existence of a global minimum, xx, and instead assume that f satisfies the PL inequality. We now reference standard properties of L-smooth functions (Zhou 2018), which will be used in our proofs.
Lemma 2. If R2d
IR is L-smooth, then for all 2, RR::
(a) (w) s (x)) + (V/(x),) + 2211 lly - x
(b) |V (L( ((x)))
The following lemma relates y and L (the proof is in Appendix B
Lemma 3. If R2 IR is p-PL and L-smooth, then S L.
yields slightly different learning rates when establishing convergence of stochastic descent methods (as is apparent from the different learning rates between Bassily et al. (2018) and Vaswani et al. (2019). The following simple lemma will be used in the proof of Theorem
plVVf(>) Using Lemma 2p in place of the strong growth condition (i.e. E. ((
Lemma 4. If (()) = - fi(x) where Si IRd + IR are L.-smooth, then f is sup, Lm-ohhthh.
Note that there could exist some other constant L' sup; L, for which f is L'-smooth, but this upper bound suffices for our proof of Theorem Lastly, we define and reference standard properties of strongly convex functions (Zhou 2018), which will be useful in demonstrating how our GMD results generalize those for mirror descent.
Definition. For > O, a difserentiable function, vb : IRd - R. is a-strongly convex for all x, y.
(vv) 2 ((x) + (Vv(z), z) + E1ll x1
a
Lemma S. bbb Rd + I is a-strongly convex, then for all x. y:
(vy) S v (V 2) + 1 2a
(V)(s)) V=((2)1
With these preliminaries in hand, we now present our proofs for linear convergence of SGMD using
the PL-Inequality.
SUFFICIENT CONDITIONS FOR LINEAR CONVERGENCE OF SGMD
In this section, we provide sufficient conditions to establish (expected) linear convergence for (stochastic) GMD. We first provide simple conditions under which GMD converges linearly by extending the proof strategy from Karimi al. (2016). We then present alternate conditions for linear convergence of GMD, which can be naturally extended to the stochastic setting.
4.1 SIMPLE CONDITIONS FOR LINEAR CONVERGENCE OF GMD
We begin with simple set of conditions under which soo--stochastic GMD converges linearly (the full proof presented Appendix C The main benefit of this analysis that it a straightforward extension of the proof of linear convergence for gradient descent under the PI.-Inequality presented Karimi et ( (016))
Theorem 1. Suppose f Rd - IR is L-smooth and p-PL and el Rd - Rd is invertible, On Lipschitz
( fonschit,functin function where lim (1)) co. for all x. y E Red and for all timesteps there exist t-000
( such that
ai
(1)) 4) 2 a 10 yl1
and lim ai
(t) > O, then generalized mirror descent converges linearly to a global minimum for any
1-y00
2n (e)
(1)
4

---

Under review as a conference paper at ICLR 2021
Remark. Theorem yields fixed learning rate provided that oj is uniformly bounded. In ad- dition, note that Theorem [ applies also under weaker assumptions, namely when Φ( is locally Lipschitz. Finally, the provided learning rate can be computed exactly for settings such as linear regression, since it only requires knowledge of L and aj (t) (sce Section 7 When 1j ai and given
(0)
w" a minimizer of f, the proof of Theorem | iimplis that:
pay (t)2
f(w
- f(w") =
(f(w!)) ff(")).
(2)
Lov
[0
Letting (0)
pai mzz thus generalizes the condition number introduced in Definition 4.1 of Liu
et al. 2020) for gradient descent. Provided that K lirm (0()) > O, then Theorem guarantees
t1000
linear convergence to global minimum. When oi is decreasing the rate is given by:
6+1 f( - [(ww)(()))))))))( S (1-
-
16
4.2 TAYLOR SERIES ANALYSIS FOR LINEAR CONVERGENCE IN GMD)
Although the proof of Theorem is succinct, it is nontrivial to extend to the stochastic setting" In order develop convergence result for the stochastic setting, turn to alternate set of conditions for linear convergence by using the Taylor expansion of o- We use Jg to denote the Jacobian of Φ. For case of notation, we consider to--iime-eeeedent an, ay, but our results are trivially extendable to the setting when these quantities are time-depent time-dependent.
Theorem 2. Suppose f Rdd + R L-smooth and μ-PL and é Fd - R an infinitely differentiable, analytic function with analytic inverse, & there exist au, Cu > 0 such that
(a) ag JØ $ anl,
k! 20,
(b) 0 (x)1s
Yo E
E j j [d], 2
then generalized mirror descent converges linearly for any (1 min
4a
The full proof is provided in Appendix D Importantly, the adaptive component of the learning rate only used to ensure that the sum of the higher order terms for the Taylor expansion converges. In particular, if (1)) is linear function, then our learning rate no longer needs to be adaptive. Note that alternatively, we can establish linear convergence for a fixed learning rate given that the gradients monotonically decrease or if f is non-negative and p-PL", We analyze this case in Appendix E and provide an explicit condition on l and under which this holds.
4.3 TAYLOR SERIES ANALYSIS FOR LINEAR CONVERGENCE IN STOCHASTIC GMD
The main benefit of the above Taylor series analysis is that naturally extends to the stochastic setting as demonstrated in the following result (with proof presented in Appendix F).
Theorem 3. Suppose f(x) E f((x) where fs Rdd - are non-negative. L.-smooth functions with I. suPie(n] 142 and f pl. Let & Rd -> RRd be an infinitely differentiable, analytic function with analytic inverse, --1 SGMD is used to minimize I according to the updates:
((w(1+1)) = )(w(() 1 V fú, (wl!)),
where [n] chosen uniformly at random and 1p is an adaptive step size. If there exist ai, Ou > 0 such that:
(a) on 5 J & a
kd 20
(b) 1 oJ (1)15
Vo E Rd RR,,,,...in i E [d,5 [d, 2,
then SGMD with (t) min
4ua aaa. (
converges linearly global minimum.
*The main difficulty relating wn ((+1) (1) the gradient timestep
5

---

Under review as a conference paper at ICLR 2021
Remark. Note that there is slight difference between the learning rate in Theorem and Theorem due to a multiplicative factor of μ. Consistent with the difference in learning rates between Bassily et al. (2018) and Vaswani et al. (2019), we make the learning rate between the two theorems match if we assume the strong growth condition (i.e. Fa(IIV((>)) S [ with = instead of using Lemma 2p. Moreover, as max, V fio( v (2LLf(w(0)) we establish linear
4pai
convergence for fixed step size 17 < min 5L 2//2da1. as well.
5 COROLLARIES OF LINEAR CONVERGENCE IN SGMD
We now present how the linear convergence results established by Theorems and apply to commonly used optimization algorithms including mirror descent and Adagrad. In this section, we primarily extend the analysis from Theorem [ for the non-stochastic case. However, our results can be extended analogously to give expected linear convergence in the stochastic case by using the extension provided in Theorem
Gradient Descent. For the case of gradient descent, d(x) = and so On = 1. Hence, we see that gradient descent converges linearly under the conditions of Theorem with v < 1. which is consistent with the analysis in Karimi et al. (2016).
Mirror Descent. Let Rd + R be a strictly convex potential. Thus, o(x) = Vτ((z) is an invertible function. If v is ay-Strongly convex and (locally) au -Liischii and f is L-smooth and p-PL,, then the conditions of Theorem [ are satisfied. Moreover, since the au -Liischhi condition holds locally for most potentials considered in practice, our result implies linear convergence for mirror descent with at-stroy convex potential dh.
Adagrad. Let eit) g(t)+ where (()) is diagonal matrix such that
0
(8)
Then GMD corresponds to Adagrad. this case, we can apply Theorem establish linear conver- gence of Adagrad under the PL-Inequality provided that @( satisfies the condition of Theorem | The following corollary proves that this condition holds and hence that Adagrad converges linearly.
(1) Corollary 1. Let f Rdd T.. be I-smooth function that is p-PI. Let dj
minte(4] 9
(0 (1) = =max/e|d] -.0 If lim Si 0,, then Adagrad converges linearly for adaptive step size and Olu
()))) -
The proof is presented in Appendix H While Corollary [ can be extended to the stochastic setting via Theorem it requires knowledge of j to setup the learning rate, and the resulting learning rate provided is typically smaller than what we can use in practice. We analyze this case further
in Section Additionally, since the condition lim 20
* 0 is difficult to verify in practice, Appendix which presents a verifiable condition under which Adagrad
at
we provide Corollary 2
converges linearly.
LOCAL CONVERGENCE AND IMPLICIT REGULARIZATION IN GMD
In the previous sections, we established linear convergence for GMD for real-valued loss, f Rd R. that is p-PL for all æ E Rd. In this section, we show that f need only satisfy the PL inequality locally (i.e. within a ball of fixed radius around the initialization) in order to establish linear conver- gence. The following theorem (proof in Appendix G extends Theorem 4.2 from Liu al. (2020) to GMD and uses the PL" condition to establish both the existence of global minimum and linear convergence this global minimum under GML We use B(x, R) {=; E Rdd || 21|25 R) to denote the ball of radius R centered at T.
'We require additional assumptions on (0) for the of time-dependent mirrors (see Appendix G

---

Under review as a conference paper at ICLR 2021
Theorem 4. Suppose R + Bd is an invertible. au-Lipschitz function and that f Rdd IR is non-negative, I-smooth, and y-PI." on B = {x ((x) E (( R}} with
R H( for all z, y E Id there exists og > 0 such that agu
(Ø(x) oly). x y) 2 ail2 -yl?,
then.
(1) There exists global minimum w [0()))= E B.
(2) GMD converges linearly to w (mx) for L
a1
(3) If ffw"
arg min ll (( then, ll@(w") - 2R. wEB; f(w)=D
Approximate Implicit Regularization in GMD. When R is small, we can view the result of Theo- rem 4as characterization of the solution selected by GMD, thereby obtaining approximate implicit regularization results for GMD. Namely, for 8 = 2" we have [[ø(w") 6(wx) ]| 8. Hence pro-
vided that R is small (which holds for small f(w ())) D) GMD selects an interpolating solution that is
close to w" in 2--norm in the dual space induced by o. This view is consistent with the characteri- zation of approximate implicit regularization Azizan et al. (2019), is shown by Corollary 3 in Appendix[] Dp. In particular, Corollary 3 implies the assumptions used in Azizan et al. (2019) for the
full batch case by proving (1) the existence of such a (x)), (2) linear convergence of w to (=0), and (3) providing explicit forms for (where
R²2 above). Importantly, the approximate implicit regularization result for mirror descent does not need to be stated in terms of Bregman divergence, but can be viewed more naturally as ([(b(((())) - Vvb(w") ")l2 being small.
7 EXPERIMENTAL VERIFICATION OF OUR THEORETICAL RESULTS
We now present simple set of experiments under which we can explicitly compute the learning rates in our theorems. We will show that in accordance with our theory, both fixed and adaptive versions of these learning rates yield linear convergence. We focus on computing learning rates for Adagrad in the noiseless regression setting used in Xie et al., (2020). Namely, we are given (X, y) Raxd x I" such that there exists w" E Ra such that Xw" the system is over-parameterized, and 2 d, the system sufficiently parameterized and has a unique solution.
If n < d, then
In this setting, the squared loss (MSE) L-smooth with = (Xax ) and it is μ-PL with Amin (XX") where Xmaz and Amin refer to the largest and smallest non-zero eigenvalues, respectively Moreover, for Adagrad, we can compute a, = min (E (w(*))) and ( maxie(d (Eio ())) at each timestep. Hence for Adagrad in the noiseless linear re- gression setting, we can explicitly compute the learning rate provided in Theorem 3 for the stochastic setting and Corollary for the full batch setting.
Figure T demonstrates that in both, the over- wee-pparameeerized and sufficiently parameterized settings, our provided learning rates yield linear convergence. In the stochastic setting, the theory for fixed learning rates suggests very small rate (se 10 for Figure [d] and hence chose only present the more reasonable adaptive step size as a comparison. In the full batch setting, the learning rate obtained from our theorems out-performs using the standard fixed learning rate of 0.1, while per- formance is comparable for the stochastic setting. Interestingly, our theory suggests an adaptive learning rate that increasing (in contrast the usual decreasing learning rate schedules). In par- ticular, while the suggested learning rate for Figure Ta starts at 0.99, it increases to 1.56 at the end of training.
In Appendix J we present experiments on over- parametrattri neural networks. While the PL- condition holds in this setting (Liu et al. 22200) can be difficult to compute the smoothness pa- rameter L (which was the motivation for developing Adagrad-Norm Interestingly, our experiments
We take j as the smallest non-zero eigenvalue since Adagrad updates keep parameters in the span of the data.
7

---

Under review as a conference paper at ICLR 2021
Noiseless Regression
Convergence ofAdagrad
Convergence Stochastio Adagrad
Our Siep (Adaplivel
5.0-
Meart (Log)
Meen Squareed Entor (Log)
-2.5
-20-
Size (Adaptivel Size (Thed))
-32
Size
-15-
-10.0
-92-
500
1200
1500
2000
2500
3200
2550
5200
7500
10000
12500
17500 20000
Numberof Epochs
Number of Epochs
Noiseless Regression (Over-parameterized)
Convergance Adagrad
Converganca Stochasdic Adagrad
15.0
Step Size wee1
Size (Adeptive)
16-
Stop blac of 0.1
Our Siep (Adlettiv)
Shep Size of 0
Moan Squaned Enor (Log)
12.5
Mean Squared Emor (Log)
10.0
0.0
-25
300
1000
1500
2002
2300
2002
20003
42003
50000
30020
100000
Numberof Epochs
Number of Epochs
Figure I: Using the rates provided by Corollary [ leads to linear convergence for (Stochastic) Ada- grad in the noiseless linear regression setting also considered in Xie et al. (2020). (a, b) Noiscless linear regression on 2000 examples in 20 dimensions. (c, d) Noiseless linear regression on 200 examples in 1000 dimensions.
demonstrate that our increasing adaptive learning rate from Theorem L. provides convergence for Adagrad in over- wer-parameterize networks. The link to the code is pro- vided in Appendix !
! using an approximation for
8 CONCLUSION
In this work, we presented stochastic generalized mirror descent, which generalizes both mirror descent and pre-conditioner methods. By using the PL-condition and a Taylor-series based analysis, we provided sufficient conditions for linear convergence SGMD in the non-convex setting. As corollary, we obtained sufficient conditions for linear convergence of both mirror descent and pre- conditioner methods such as Adagrad. Lastly, we prove the existence of an interpolating solution and linear convergence of GMD to this solution for non-negative loss functions that are locally PI.". Importantly, our local convergence results allow us to obtain approximate implicit regularization results for GMD. Namely, we prove that GMD linearly converges an interpolating solution that is approximately the closest interpolating solution to the initialization in b norm in the dual space. For the full batch setting, this result provides more natural characterization of implicit regularization in terms of &g norm in the dual space, as opposed to Bregman divergence.
Looking ahead, envision that the generality of analysis (and the PL-condition) could pro- vide useful in the analysis of other commonly used adaptive methods such as Adam (Kingma & Baj 2015). Moreover, since the PL-condition holds in varied settings including parameeemeeeii neu- ral networks (Liu et al. 2020), it would be interesting to analyze whether the learning rates obtained here provide an improvement for convergence in these modern settings.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Navid R. Azizan and Babak Hassibi. Stochastic Gradient/Mirror Descent: Minimax Optimality and
Implicit Regularization. In International Conference on Learning Representations (ICLR), 2019.
Navid R. Azizan, Sahin Lale, and Babak Hassibi. Stochastic Mirror Descent Overparameterized Nonlinear Models. In International Conference on Machine Learning (ICML) Generalization Workshop, 2019.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprini arXiv: 2018.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinne trade-off. Proceedings of the National Academy of Sciences, 1 116(32):15849) 15854, 2019.
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks, 2018. arXiv:1810002054
John Duchi, Elad Hazan, and Yoram Singer. Adaptive Subgradient Methods forOnline Learning and Stochastic Optimization. Journal of Machine Learning Research (JMLR), 12:2121-2159, 2011.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in
terms of optimization geometry. In International Conference Machine Learning (ICML), 2018.
Suriya Gunasekar, Blake Woodworth, and Nathan Srebro. Mirrorless Mirror Descent: A More Natural Discretization of Riemannian Gradient Flow. arXiv preprint arXiv:2004001055, 2020.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear Convergence of Gradient and Proximal- Gradient Methods Under the folyak-Lojasiewier Condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representutions (ICLR), 2015.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems (NeurIPS), pp. 8157-8166, 2018.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Toward theory of optimization for over- parameterized systems of non-linear equations: the lessons of deep learning. arXiv preprint arXiv:2003.00307, 2020.
Stanislaw Lojasiewicz. A topological property of real analytic subsets (in French). Les équations aux dérivées partielles., 117:87-89, 1963.
Arkadi S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Opti- mization. SIAM, 27(2):264-265, 1983.
Francesco Orabona, Koby Crammer, and Nicolò BisacBianchi. Mirror descent and nonlinear pro-
jected subgradient methodsfor convex optimization. Machine Learning, 99:411 1-55, 2015.
Boris Polyak. Gradient methods for minimizing functionals (in Russian). Zh. Vychisl. Mat. Mat. Fiz., 3(4):643-653 1963.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D. Lee. Theoretical insights into the optimiza- tion landscape of parametreeee shallow neural networks. IEEE transaction on Information Theory (2018), 65(2):742 769, 2019.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and Faster Convergence of SGD for Over- Parameterized Models and an Accelerated Perceptron. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.

---

Under review as a conference paper at ICLR 2021
Rachel Ward, Xiaoxia Wu, and Léon Bottou. AdaGrad Stepsizes: Sharp Convergence Over Non-
convex Landscapes. In International Conference on Machine Learning (ICML), 2019.
Xiaoxia Wu, Simon S Du, and Rachel Ward. Global convergence of adaptive gradient methods for an over-parameterizee neural network. arXiv preprint arXiv:1902.07111 2019.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear Convergence of Adaptive Stochastic Gradient
Descent. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in
convolution network, 2015. arXiv:1505.008:
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations (ICLR), 2017.
Xingyu Zhou. On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradi- ent. arXiv preprint (50::880006777 2018.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
A PROOF OF LEMMA 1 We restate the lemma below.
Lemma. I Rd R is y-PL,, L-smooth and f(x) 2 0 for all Rd, then gradient descent with learning rate < converges linearly to x" satisfying f(x") = 0.
Proof. The proof follows exactly from Theorem of Karimi al. (2016). Since f is L-smooth, by Lemma 2a it holds that:
f(wl(t1)) f(((()) - (Vf(w(!)), wl(+1) - (0)) + L - -
-
L f(w((+1) f(w(()) <-nl [nll(f((( - 1|+ ((x()))
f(u((1)) f(w(()) s ( (-77 +
I
2u 2uf(w!0)
2
s(w((t1) S (1 2 + أدم²² L) sw
Hence, if 1 3. then C (1 - 2pm + f 1. Thus, we have f(u(t+1)) Cf(w()) for C' < Thus, as is bounded below by and the sequence (f(w(()) monotonically decreases with infimum 0, the monotone convergence theorem implies lim fw(()) O.
B PROOF OF LEMMA 3
Proof. From Lemma and from the PL condition, we have:
2x([(x) s(x))) |VV[()) 21 s(x))) (4() = ust
PROOF OF THEOREM
Proof. Since f is L-smooth, by Lemma 2 holds that:
f(w((+1)) - f(w < (V)(w())), (((11) (0))) + - 11.
(5)
Now by the condition on (()) in Theorem we bound the first term on the right as follows:
(6)1 (w((()) - (w)(t) (o - (1) 2
oz (0) ([ - (1)
V (0+11 (()))) 2 a, (1) 1111 w( 12 using Equation
(V)((())), (0(1)) w0(1) < aj (t)
(1+1)) 1
Substituting this bound back into the inequality in 5 obtain
(t) 1
f(w(++))) f(wo(())
a
[ - 10
17 2

---

Under review as a conference paper at ICLR 2021
Since the learning rate is selected that the coefficient of - on the right is negative, we obtain
(9)
L
f(ultt))) )((w(()
2
9
L
1
l (w)(t()))
-ol" (w(
2
(1)
L
-n [[((() using Equation
1
2
(1)
L
172
211
(s(wo()) -((w)) as f is p-PL.
2
(1)
au
Laj²
= ((o(tt)) f(w") <
1 2p
(f(wl f(w")),
(1)2
(1)
an
On
where the second inequality follows since (10) is au -ipsschitz For linear convergence, we need.
(9
0 < 2p na
(t)
Lnp
<1
(6)
(2)
(0)
aa
From Lemma p always holds and implies that the left inequality in satisfied for all
(tt)), The right inequality holds by our assumption that (7
2a
which completes the proof. m
D PROOF OF THEOREM
We repeat the theorem below for convenience.
Theorem. Suppose f Idd + R is L-smooth and μ-PL and à Rd - RR is an infinitely differen- tiable, analytic function with analytic inverse, a-1. If there exist on, Oaa > such that:
(a) a & J $ a.I,
k! 20d
(b) 0 0, (
Vx E R a1........ ii...... in E [d].j [d], k 2
then generalized mirror descent converges linearly for (7()) min
4a 5La, (
Proof. Since f is L-smooth, it holds by Lemma that 2
(ww(++)) (w) s (VS(w(()) (o+1)) vo(()) + L (tt - (o(())12
Next, we want to bound the two quantities on the right hand side by multiple of [1) We do so by expanding wn(++1) - (t) using the Taylor series for ś as follows:
((+++) (t) = xb (9( 1/ (VS(w(()) (e)
= (6( V(
El b1 1 ( vf(w(()))))
The quantity in brackets column vector where we only wrote out the jth coordinate for j e [d]. Now we bound the term (V (wo(t())), (((+1) w(()):
(V (W((())) w (1+1))
(1))
-/ ( (w (((((())
d
(V)(
Σ L11
O ( ((
vf(w())
12

---

Under review as a conference paper at ICLR 2021
We have separated the first order term from the other orders because we will bound them separately using conditions (a) and (b) respectively. Namely, we first have:
fw (1) (w) V - 2
(1)
Next, we use the Cauchy-Schee Schwarz inequality on inner products to bound the inner product of Vf(wltt) and the higher order terms. In the following, we use a to denote 2ond'
()(
(-n) 0 O 0f (o(w (
hs!
<(V](w())
11 ( 11
... Vs(wo(())
ak!
< <[Vf((()))
k! (n)* 4 21
/ (((()(()))))))))
- (I
V (
()(((())) )2l
=
=|VVf(
vak
11)*
V (
V
vdn (
Hence we can select 17 2v
such that:
2v2 ((w](
al 1- Vdnl ((
(( ((v
donl [ V 110
V
Thus, we have established the following bound:
()) (1+1)) - (0) S (-"" " au
+ dan) [[) (- 71
|| [V((((()))
20
Proceeding analogously as above, we establish a bound on [[o(++1] - w(())
- dr +o'd (1]
112 +
112
\V
af
a?
4a
Putting the bounds together we obtain:
Tap
Lap²
f(w(t+2)- - f(w(()) -(w())) <
11
+
+
| (w)(t))
20u
207
Sa
We select our learning rate to make the coefficient of (w inequality (4) we have:
negative, and thus by the PL-
((w(t+1))- - ((1) <
27
Lni
LiT²) - (
+
20x
207
80
μLn1
= =((((t)))) - f(w²) 5
(f(w(() f(w))).
af
4a
13

---

L. Under review as a conference paper at ICLR 2021
Hence, w(t) converges linearly when:
nTmzz af
nTn 4ay
0<1
+
+
<1
au
To show that the left hand side is true, we analyze when the discriminant is negative, Namely, we have that the left side holds if:
42
4uL
μL
<
0
07
2
a²
11
41.
L
<
+
0
2
4La 2
of
4o
Since < by Lemma this always true. The right hand side holds when 7y holds by the assumption of the theorem, thereby completing the proof.
which
5T.w
Note that if f is non-negative and p-PL.", then we have:
(7
1/2Td//(ww))) 2/2LdV
2v 2vd V
1af 5Lo
Hence, we can use a fixed learning rate of 1) min
in this setting.
2/2Ld//(wwo))
E CONDITIONS FOR MONOTONICALLY DECREASING GRADIENTS
As discussed in the remarks after Theorem 2, we can provide fixed learning rate for linear conver- gence provided that the gradients are monotonically decreasing. As we show below, this requires special conditions on the PL constant, and the smoothness constant, L, for f.
Rd + IR L-smooth and μ-PL and à 12d Ed is an infinitely differentiable, analytic function with analytic inverse, o If there exist an Cu 0 such that:
Proposition Suppose
(a) ai 55 J $ a.I,
kd 20,
(b) 1 07 (x)ls
Vx R.i....... [d].j [d]. 2
/ 4 + o²
(c)
L
4 20²
4n 5Lay
then generalized mirror descent converges linearly for any < min
2 v V( (
We follow exactly the proof of Theorem 2 except that at each timestep need C & (which is less than by Lemma 3) in order for the gradients to converge monotonically since:
Proof. Let C - - Hill au
أوn²
ala²
4a
|| (vo((tt < (L(((w()+1) f(w")) See Lemma 2
< 22LC(f(w(() f(ww))
I LC [V As f is J-PL.
P
Hence in order for (t rate such that:
(1 need C サ. Thus, select our learning
mm
0 <
ag
of
4a
L
14

---

Under review as a conference paper at ICLR 2021
Now, in order to have solution to this system, must ensure that the discriminant of the quadratic equation in 7) when considering the right hand side inequality is larger than zero. In particular we require:
1
(1
14 L
μL aj
μ. 1a
+
a
11
40 + of
4a
+ 20 2'
which completes the proof.
PROOF OF THEOREM 3
We repeat the theorem below for convenience.
Theorem. Suppose f(x) = -. f((x) where fi Rd + IR are non-negative, Li-smooth func- tions with L = supre[n] L, and is u-PL.. Let Φ R2 - R be an infinitely differentiable, analytic function with analytic inverse, o=1. SGMD is used minimize according to the updates:
)(w = )(w f.
where is E [n] is chosen uniformly at random and 11()) is an adaptive step size. If there exist 01, On O such that:
(a) a. J aut,
fa 20,
(b) 1 of (x)15
Vx E RR.,...... E [d], E [d] 2 2,
then
SGMD)
converges
linearly
to
global
minimum
for any 17(0)
Apo
min
5L
2vd max, V [[
Proof.
We follow the proof of Theorem
Namely, Lemma implies that f is L-smooth and hence
(t+1) w())) + L (t 11
< (Vf(w())), f(w(t))
As before, we want to bound the two quantities on the right by V ff Following the bounds from the proof of Theorem provided (7()) 2v2 we have
(w)
d 2n =1 (-1) 0r . 0j (o(w((0)) (1((0_)))))((((() (W VSs (w(())))
k!
10
(t.
20
To remove the dependence of (7()) i, take r7(1) fa is non-negative for all E [n), [[ (2. Thus, we can take
2 max V [w Since f is P-LL" and
( 2v2nL / f(w(tt) 2 max, maxx
This implies the following bounds:
1110p (Vf(w())), (((+1) w(t)) (t ( JJ (w((t) (wo(t))
[v]((())))]] /l, (w0(0))l
I.
(t)
?(1)2
[1o()+ - w1))
V fi, (w((t)))
af
4a
15

---

Under review as a conference paper at ICLR 2021
Putting the bounds together obtain:
1100
1( f(w(+)) S (n V ((wl1)² (e Vii, +
| ( Vii (w)())
20
7000
+ 7010²)
|V (1
of
4a
1100
S <n f(((l)) T
JØ
+
2 f(w((t)) (i.(tt))) (wi())
20,L
1/112 + 4o
1/11)22
(w]()))
Now taking expectation over it, we obtain
Elf [[f(w((+1))] f(w(() s ( (-1%)
1)(0)
[
(n/(²)
/ V(woOo))
V /oscee))
au
au
ln
Tn)(0)
+
+
E fi
207
Sa?
()
| (/
f(w((t)
0n
auu
Ln(t)²
+
E EI[V (w) 119]
2077
802
111011 f(w(l)
f(w(1)+ +
au
Lnnlt)?
+ Lnp(t)
+
(12L(Ji((w0)) - Sz. (w)
207
80
(t)(()
L2n
(f(wl0)).
+
af
4a
where the second inequality follows from Jensen's inequality and the third inequality follows from Lemma[] Hence, we have:
(1)(())
I22,(1022
(1)
Blf [[f(w((+1))] S
1
+
(f(w)
ag
af
4a
Now let C' = (- (-un(" yields
(1)
(1) ot
12, 1a?
Then taking expectation with respect to in, in Iy....i di,
Cx
E [f(((++)))]
S ((0))5(110)))) (1+C)(T.
=11 i (Ejsjie- [f( II)
= (1+C) 1.. I (w)(0))).
Hence, we can proceed inductively conclude that
E, ((w(()))) s (1 (1+ CT (f(x
Thus 0 < 1+0 < 1, we establish linear convergence. The left hand side satisfied since μ < L, Apaî
which holds by the theorem's assumption, and the right hand side is satisfied for 17()) sLPa.? thereby completing the proof.
G PROOF OF THEOREM
We restate the theorem below.
16

---

Under review as a conference paper at ICLR 2021
Theorem. Suppose R - R is invertible. au-Lipschitz function and that R R is non-negative, I-smooth, and p-PI." on B {Ir Φ(x) E (( R)} with R
2 W//2T/// f(wlo)) jo" for all z, E R² there exists on > 0 such that
(0(x) - o(y), x 5) 2 ar11 - -
then,
(1) There exists a global minimum (00) E
(2) GMD converges linearly to (o())) for 17 = 0q
L
(3) Ifw*=
arg min [1ō(w) x(w then, (1x((w)) o(w(x))]] 2R. wEB; ; f(w)=0
Proof. The proof follows from the proofs of Lemma Theorem I and Theorem 4.2 from Liu et al. 2020 Namely, we will proceed by strong induction. Let pai At timestep 0, trivially have that w(()) E B and f(w(()) S f(w(0)). At timestep t, we assume that (0),, w()),.. wit e B and that f(w(1)) < (1 x===) ( for i E [t]. Then at timestep + 1, from the proofs of Lemma Tand Theorem I we have:
fl 5 (1-x5 (f(x=))(((()
Next, we need to show that (((1)) E B. We have that:
((((w(t11)) (
Σ 7 V (()
S 1
l [w (1)
By the Triangle Inequality
La
S 11
[1ol1) - (wil++1)
2=0
Lo2
V /flwlo)
Σ
11
aj
i=0
$ 21 a1
(1 (1-x~1ji f(w(o))
n 21/2f
22 aN
1
S mn 2L1(w(()
00
V1
K
$ 7/ 2L)(w(())
au
a1 K
On 2 0g L
(L)(w(())
T,
01 01
2/2T.
(w
)a
app
17

---

* 0, then Adagrad converges linearly for adaptive step size Under review as a conference paper at ICLR 2021
The identity in follows from the proof of f(ult+!)) (1 -1- (1-x=))f(w()) Namely,
f(ulltll) - -((w(0) 1
| (
20
[VV V
20
/ ((wwitt) f(w((+t)
L
2La ffw(()) - f(w(t+1))
[V "
af
Hence conclude that (((+1) B and so induction is complete.
In the case that ((t)) is time-dependent, we establish similar convergence result by assuming that
(w((t) 1)t-1 (w)()) = 5 < co. Additionally if af has uniform upper bound and a (0)
has a uniform lower bound, then:
( (w (1+ 60 (w) = (w) - (w) + (w(()) - -0(1-1 (2)(1) 11(-1) (w)(t) 1lt-1) (t-1t)
1000 (w) 16 (zo
1 (w(++1)) 21 (v(())))))
Σ 2 (w(( 1i (.
+
R
Hence we would conclude that 25(0) (w+++1) E (w))))
PROOF OF COROLLARY AND COROLLARY We repeat Corollary below.
Corollary. Let f Rd - IR be an L-smooth function that is p-PL. Let 0i (0) (0)2
mingera as) 9% and
Qg maxield] G If lim ( to ou
(1))) c0
Proof. By definition of g(), we have that:
(1) aj ( min 9 (1)
sE|d]
(2) a (0) max
sE|d]
From the proof of Theorem
using learning rate (t)
= at timestep t gives:
(1)
((wtt)))-ffee s Hay
(f(w()) - (((()))))ww))
La (0)
Let (t) pat" (t) (1
(0)= Although have that (1 k())) < 1 for all t, need to ensure that
(eyz.
()) (otherwise would not get convergence global minimum). Using the
assumption that lim # O. let lim (1 - k²))) = 1 - < 1. Then using the definition of 1-000
10000 (0)
the limit, for G, there exists N such that for t. > N. |x(0) - cl Hence, letting
18

---

Under review as a conference paper at ICLR 2021
5"
min (c-6, rE (0,
min
x10)
implies that (1-
c* for timesteps t. Thus, we
have that:
II
()) < II -1)
1=0
1=0
Thus, Adagrad converges linearly to global minimum.
We present Corollary beloow.
Corollary 2. Let f Rdd + T. be an L-smooth function that is p-PL. Let (1) = min (tt)
9,1
Then Adagrad converges linearly for adaptive step size v/(t) oj or fixed step size yl + if (0)2
4
2L( 1(
Proof. By definition of G(t), we have that:
(1) ai (0) min g
:E[d]
(t) max 9
(2) ag sE|d]
In particular, can choose aj aj (0)
uniformly. We need to now ensure that a does not diverge.
We prove this by using strong induction to show that Oa (t) base case holds by Lemma since have:
< S uniformly for some S > The
(0)
S (0) S
(1)
Now assume that au
S for E {0, 10,1,.. 10.. 1}. Then we have:
(1)
V )10
0m0
2L(f(w(()) f(w")) by Lemma 2
1=0
(1)
Hay
< <2L(((w(0) f(w)))
(i)
1=0
1-1
ioiii (0)2
< 22T(((w(1)) f(w"))
Σ
LS
1=0
j=0
1
< 2l((( f(ww))
pa (0)2
LS
LS
(T(()( f(w)))
<
by assumption
(0)2
pay
Hence, by induction, ax
( is bounded uniformly for all timesteps f.
19

---

Under review as a conference paper at ICLR 2021
I PROOF OF COROLLARY 3
We present the corollary below.
Corollary 3. Suppose db an on-strongly convex function and that Vib is ax-Lipschitz Let (e(T, y) = ((xx) - (yy) Vib(y)² (x y) denote the Bregman divergence for 2,y E RR. If f: I2d + I is non-negative, L-smooth, and u-PL" on B =xx; Vv((x) B(Vv(w!!)), R)} with
R (V then:
ouu
R
(1) There exists global minimum w/(o) e B such that (w w000) -
201
(2) Mirror descent with potential vb converges linearly to (=0) for
04
L
R² R²
(3) If
arg min (w w then D(w", w (20) : [(w)=0}
of
ai
Proof. The proof of existence and linear convergence follow immediately from Theorem 4 remains to show that (w wll))
All that
R²
As up is aq ay-strongly convex, we have:
2n
(((()))) s )lw + (Vbb(n) w((= - (!!)) + [Vb(((()) V (11 By Lemma 5
1
200
1 Vel - -Ve
R²
De(wloo) ( (0)) <
201
201
Now let wt arg min(w f(w)= (w w( Hence D& (w=, w(l))
R² by definition. Then 2mr
have:
1 [iiw") - (1)))))
Dylw", w((0))= -
20q
(2(()((("))
V (
20
0u ||0* - 11
R²
01
ai
0u 2
R²
(w""" w ) +
By Definition
0i aD
ad
ag R²
3 + R2
ai
J EXPERIMENTS ON OVER-PARAMETERIE NEURAL NETWORKS
Below, we present experiments which we apply the learning rate given by Corollary to over- parameterized neural networks. Since the main difficulty is estimating the parameter L in neural
networks, we instead provide crude approximation for L by setting [ .99 fw 2f(w00] The intuition for this approximation comes from Lemma 2 While there are no guarantees that this approximation yields linear convergence according to our theory, Figure suggesss empirically that this approximation provides convergence. Moreover, this approximation allows us to compute our adaptive learning rate in practice.
Code for all experiments is available at:
ht https: anw.ymousnmmmmms...oa/../ 4open. htt.://wwww.....o.oo///////////. oag.00a---...--1l------------aad
20

---

Under review as a conference paper at ICLR 2021
Convergence Adagrad in Over-parameterized Neural Networks
Hidden Layer, Leaky Rel. U Activation
Hiddon Layer, x sin(x) Activation
10.5
Our Stop Size (6dastive) Shop Sice 0.1
Our Suaa Sis (Adaption)
7.5
Mean Squared Emar
0.8
Meen Squared
-15
-20
-20.-
2010
20003
2000
6200
15000
Number Epochs
Number of Epochs
Figure 2: Using the adaptive rate provided by Corollary 1 with L. approximated by I(() .99 ((
(f(1) leads to convergence for Adagrad in the noisy linear regression setting (60 exam- ples in 50 dimensions with uniform noise applied to the labels). (a) I hidden layer network with Leaky ReLU activation Xu et al. (201) and 100 hidden units. (b) hidden layer network with + sin(x) activation with 100 hidden units. All networks were trained using single Titan Xp. but can be trained on a laptop as well.
21


Reviews:
[{"review_id": "wH7TRZRVkvV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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]\nThis paper studies the interesting property of generalized mirror descent (GMD) and its stochastic variant for nonconvex optimization problems. First, for GMD this paper shows the linear convergence under PL* condition (in Lemma 1) and finds out a new sufficient condition for the linear convergence (in Theorem 2). Next, this work tried to extend this result to a stochastic setting (in Theorem 3). Moreover, the implicit regularization of GMD is studied, which is an extension of the previous studies by [Azizan et al.].\n\n[Strength]\nThis paper is easy to read. I think this line of research is very interesting and important to explain the reason why the overparameterized models work well. \n\n[Weakness]\nA major concern is the correctness of the statement. There seems to be a technical flaw in the proof of Theorem 3 which is one of main contributions. Indeed, since learning rates $\\eta^{(t)}$ depend on $\\|f_{i_t}(w^{(t)})\\|$, $\\eta^{(t)}$ should be also random variable depending on $i_t$. Hence, the equation $E_{i_t}[ \\eta^{(t)} \\|\\nabla f_{i_t}(w^{(t)})\\|] =\\eta^{(t)} E_{i_t}[\\|\\nabla f_{i_t}(w^{(t)})\\|]$ is invalid. However, this equation is used in the first expression in page 16 in supplementary.\nMoreover, it would be better to specify the explicit convergence rate in the main theorems to verify certain linear convergence.\n\nAnother concern is the significance of Theorem 4. The property of implicit regularization of GMD is stated in Theorem 4, but this theorem seems not to be a proper extension of the result obtained in [Azizan et al. (2019)].\n- The orders wrt R of the ball $\\tilde{\\mathcal{B}}$ and $\\| \\phi(w^*)- \\phi(w^{(\\infty)})\\|$ are the same, hence, the convergence of the order $o(R)$ as shown in [Azizan et al. (2019)] does not hold.\n- The domain of $w^*$ is restricted in $\\tilde{\\mathcal{B}}$, but there is no such restriction in [Azizan et al. (2019)].\n- If we consider $\\phi(w)=w$ which corresponds to the gradient descent, the result (3) is obvious from the triangle inequality. Hence, I am concerned about the importance of this result.\n\n[Improvement]\nIt would be nice if the authors could mention the above weakness.", "extra_scores": {}, "extra_text": {}}, {"review_id": "uuqsJUpG2Ks", "reviewer": "AnonReviewer3", "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 studied an algorithm for solving unconstrained smooth finite-sum optimization, called stochastic generalized mirror descent (SGMD). The algorithm SGMD is a generalization of several existing, popular algorithms, including stochastic gradient descent, mirror descent and Adagrad. \n\nThe main contribution lies in the convergence rate analysis of the algorithm SGMD based on the Polyak-Lojasiewicz (PL) inequality, which in turn yields linear convergence rate results for some existing methods such as Adagrad. Specifically, the author(s) showed in Theorem 3 that if the objective function satisfies the PL inequality and has a Lipschitz gradient and if the potential function (or called the mirror function) satisfies certain technical assumptions, then SGMD converges linearly to a global minimum. If the PL inequality is satisfied only locally, then local linear convergence result for the GMP (the deterministic version) was also proved. As another contribution, the paper showed that the GMD exhibits an implicit regularization phenomenon in the sense that it converges to a particular optimizers among others. \n\nThe Taylor-series-based analysis for stochastic algorithms seems to be new and deserves some merits. However, I do have some doubts about the main results. \n\nFirst, I'm not sure if one can obtain new, useful algorithms from the general algorithmic framework in the paper and/or deduce new convergence rate results for existing algorithms. If yes, the paper should point it out explicitly, discuss such consequences and compare with the related algorithms/theoretical results. These are not clear from the current presentation of the paper.\n\nThe practical implication of the implicit regularization result is also not clear. More efforts should be spent on discussing the meaning or interpretation of the interpolating optimal solution SGMD prioritizes, especially in the context of machine learning problems (e.g., when the optimization problem is the training of neural network or some supervised learning tasks).", "extra_scores": {}, "extra_text": {}}, {"review_id": "ksMpYH615LX", "reviewer": "AnonReviewer4", "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": "The paper studies 1) the convergence rate; and 2) the implicit regularization of (stochastic)GMD, a generalization of (stochastic) mirror descent where mirror maps can be time dependent. The contributions are as follows: 1) Theorem 1: for PL+smooth functions, the paper presents a linear convergence result for GMD; 2) Theorem 2, 3: they provide sufficient conditions on the Jacobian of the mirror map, under which (stochastic)GMD converges linearly; 3) Theorem 4: argues for an “approximate implicit regularization” effect of GMD, by showing that GMD converges to a point, “close” to the initialization, where closeness is measured in terms of the \\ell_2 distance in the mirrored space.\n\n- Correctness: I have a problem understanding the proof of Theorem 3. In the fifth line of the proof of theorem 3, page 15 of the appendix, I’m not sure how you upper bound the quantity - < \\nabla f(w^(t)), J_\\phi^-1 \\nabla f_{i_t}(w^(t)) > by the right hand side. Of course, the Jacobian is assumed to be positive definite, but how does this upper bound follow? Besides, I found the claim in Theorem 3 quite interesting, and even surprising. It seems to me that SGD, which is SGMD with mirror maps equal to identity, satisfies the conditions of Theorem 3, simply because the mirror map is the identity. Then, the result claims an exponential convergence rate for SGD to the global optima. Can you clarify this, in light of the minimax lower bounds for SGD in smooth and strongly convex setting, e.g. the recent work: https://papers.nips.cc/paper/8624-tight-dimension-independent-lower-bound-on-the-expected-convergence-rate-for-diminishing-step-sizes-in-sgd.pdf\n\n- Novelty/Significance of the results: Theorem 3 is novel and seems very interesting, if the authors clarify the issue above, as well as clarify the generality of the assumption, i.e. the conditions required for the Jacobian of the mirror map. Can you clarify what are the technical challenges in proving Theorem 1, and what are the novelties with respect to several related work, including the work of Karimi et al., 2016?\n\n- Clarity: In my humble opinion, Theorem 4 cannot be interpreted as an “approximate implicit regularization” effect, simply because the distance to the optimum measured in the mirrored space can be very large, and the authors do not provide examples when this can actually be small. In the remarks, you point out “Hence provided that R is small (which holds for small f(w(0))), GMD selects an interpolating solution that is close to w*  in \\ell_2-norm in the dual space”. But why should one expect f(.) to be small at the initialization? Specifically, this theorem is proved under the assumption that f(.) is non-negative, therefore, f(w^(0)) being small simply means that w^(0) is already an approximate global optimum.\n\n- Presentation: I think there is room for improving the writeup. Here are some examples:\n   + The presentation of MD-type updates in Equation (1) is quite abrupt, without providing the motivation/context.\n   + All of the main theorems guarantee linear convergence without actually characterizing the rate of convergence. I found it very confusing as it hides the dependence on important parameters.\n   + The presentation of the PL* condition in section 3 is very confusing as none of the main results (Theorems 1-3) requires this condition. What is the motivation? It seems that this condition is not preserved under simple transformations such as translation, i.e. if f(X) satisfy PL* then f(x) + 1 will not. What are some interesting function classes that satisfy this property?\n   + Do the assumptions of Lemma1 (PL*, smoothness, non-negativity) imply existence of x* such that f(x*) = 0?\n   + Can the monotonicity condition in Theorem 4 be restated in terms of strong/strict convexity of the potential function associated with the mirror map?\n   + The sufficient conditions in theorems 2 and 3 are not discussed at all. What are some examples of interesting potential functions / Bregman divergences that satisfy these conditions?\n\nFor the reasons listed above, I don’t think this paper is ready to be published at ICLR. Of course, I will happily reconsider my evaluation and increase my score if the authors clarify the issues raised above.\n\n****************************************Post-rebuttal comments****************************************\n***************************************************************************************************\nAfter reading authors feedback, I've increased my score from 3 to 5; however, the paper in its current form is still a borderline. \n***************************************************************************************************\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "79EuzKbXaQk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "##########################################################################\n\n\nSummary:\n\nThis paper shows a “generalized mirror descent“ converges linearly if the objective function is smooth and satisfies the Polyak-Lojaciewicz condition. \n\n\n##########################################################################\n\n\nReasons for score: \n \n\nThe novelty seems to be very limited. This paper does not actually show the benefit of replacing the gradient of the Bregman function by a general mapping in mirror descent. The analyses are standard and do not actually get more difficult with the generalization. The theorems require the derivatives of the Bregman function to be bounded, making the result not even applicable to entropic mirror descent, arguably the most notable instance of mirror descent. \n\n\n##########################################################################Pros: \n \n\nPros: \n\n1. None. I have not seen a proof showing mirror descent converges linearly with the Polyak-Lojaciewicz condition in literature, so this could be a novelty. But the analyses in this paper are just standard and very restrictive because they require the Bregman functions to have bounded derivatives. \n \n\n##########################################################################\n\nCons: \n\n1. I do not see the benefit of replacing the gradient of the Bregman function by a general mapping \\phi. The authors use gradient descent, mirror descent, and AdaGrad as examples of the “generalized mirror descent” in Section 5. However, it is already known that gradient descent is a special case of mirror descent and AdaGrad is mirror descent with a time-varying Bregman function. All three do not need the notion of a “generalized mirror descent.” \n\n2. The proposed “generalized mirror descent” is not actually more general than mirror descent. The assumption on \\phi in Theorem 1, for example, coincides with the standard assumption in mirror descent literature that the Bregman divergence is strongly convex. Moreover, the condition that \\phi is Lipschitz is restrictive (for example, it does not hold for entropic mirror descent) and does not appear in standard mirror descent literature. The conditions on the derives of \\phi are even more restrictive in Theorem 2 and Theorem 3.  \n\n3. The theorems in this paper only states that the algorithms converge linearly. Please make an optimal choice of the step sizes and make the dependence of the convergence rate on the problem and algorithm parameters explicit. Also please make sure that the exponent in the linear convergence rate does not depend on the iteration counter, as opposed to those shown in the appendix.  \n\n4. The paper starts with a discussion on overparameterization. However, I do not see the connection of this paper with explaining the benefit of overparameterization. Indeed, the analyses in this paper has nothing to do with overparameterization, unless the authors connects the PL condition with overparameterization.  \n\n5. Isn’t the PL^* condition simply the PL condition with the objective function shifted by -f(x^*)? As long as f(x^*) is finite, without loss of generality, one can always do such a shifting and the sequence of iterates does not change. I do not think PL^* is a new condition. \n \n\n##########################################################################\n\nAfter reading the rebuttal: \n\nI keep the score. \n\n- In my view, the Taylor-series analysis is a very straightforward approach such that existing frameworks apply to the setup considered in this paper. Such a straightforward approach renders the results restrictive and hence I do not consider it a significant novelty. \n\nThe proof of Theorem 1 just rewrites the existing proof with minor modifications for the considered setup and hence do not require any additional restriction. Emphasizing Theorem 1 is not very appropriate for the rebuttal. \n\n- The \"generalization\" I mentioned is for the \\phi function. There are already several works on mirror descent/FTRL with a time-varying regularizer (Orabona et al. (2015) is for FTRL, as clarified in Orabona's lecture notes on online learning). Without an example where the \\phi function is not the gradient of a potential function, I do not see the necessity of this generalization. \n\nFor the same reason above, emphasizing Theorem 1 is not very appropriate for the rebuttal. \n\n- My point is to clarify the dependence of the convergence rate on the problem parameters. I do not think the proofs in the appendices provide explicit characterizations of such dependence. To make such explicit characterizations, I think specifying *a* step size instead of *a range* of step sizes is perhaps necessary. \n\n- I suggest the authors rewrite the first two paragraphs to make the motivation of the problem setup clearer there. Section 2 is OK. \n \n\n#########################################################################", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows linear convergence for generalized mirror descent on smooth function under the PL assumption. It extends the result to stochastic generalized mirror descent under an additional assumption on the Jacobian of the mirror map. Reviewers pointed out several technical issues with the submission. While some of the problems have since been resolved in the updated version, the paper still lacks sufficient novelty, and some concerns regarding the correctness/clarity of the claims remain. Unfortunately, I can not recommend acceptance at this time. 
Decision: Reject