Non-convex online learning via algorithmic equivalence
Authors: Udaya Ghai
Zhou Lu
Elad Hazan
Venue: NeurIPS 2022 Accept (2022)

Abstract: We study an algorithmic equivalence technique between non-convex gradient descent and convex mirror descent. We start by looking at a harder problem of regret minimization in online non-convex optimization. We show that under certain geometric and smoothness conditions, online gradient descent applied to  non-convex  functions is an approximation of online mirror descent applied to convex functions under reparameterization. In continuous time, the gradient flow with this reparameterization was shown to be \emph{exactly} equivalent to continuous-time mirror descent by Amid and Warmuth, but theory for the analogous discrete time algorithms is left as an open problem. We prove an $O(T^{\frac{2}{3}})$ regret bound for non-convex online gradient descent in this setting, answering this open problem. Our analysis is based on a new and simple algorithmic equivalence method. 

Non-convex online learning via algorithmic equivalence
Udaya Ghai
+
Zhou Lu
Elad Hazan
Abstract
We study an algorithmic equivalence technique between non-convex gradient descent and convex mirror descent. We start by looking harder problem of regret minimization in online non-convex optimization. We show that under certain geometric and smoothness conditions, online gradient descent applied to non- convex functions is an approximation of online mirror descent applied to convex functions under reparameterization. In continuous time, the gradient flow with this reparameterization was shown to be exactly equivalent to continuous time mirror descent by Amid and Warmuth [4], but theory for the analogous discrete time algorithms left as an open problem. We prove an O regret bound for non-convex online gradient descent in this setting, answering this open problem. Our analysis is based on new and simple algorithmic equivalence method.
Introduction
Gradient descent is probably the simplest and most popular algorithm in convex optimization, with numerous and extensive studies on its convergence properties. For non-convex objectives, is known that gradient descent does not necessarily converge the global optimum, which is in general NP hard. Thus recent research focuses alternate objectives, such as finding first-order stationary points efficiently, or the importance of higher order stationary points, c.g. [19, 22, 1].
However, the study of global convergence of gradient descent for non-convex objectives is increasingly important due to the fact that in practice, gradient descent and its variants achieve error highly non-convex loss function of a deep neural network.
To explain the success of modern deep learning it is thus important to understand why gradient descent can converge global minimum for some highly non-convex functions. Several important research directions have stemmed from this motivation, including the study of optimization for deep linear networks [20, 21, 6], non-convex matrix factorization [7], provable convergence for neural networks in the linearization regime of the neural tangent kernel [26, 12, 13, 2, 32, 18, 9], and more.
recent promising approach, proposed in [4, 3], is to consider reparameterizing mirror descent as gradient descent. In particular, [4] shows that continuous-ting time online mirror descent with a convex loss can be written in an equivalent form of a continuous isn't 't necessarily convex after reparameterization, but has significant structure. [3] further explores this idea, showing that after reparameterization. online gradient descent has the same worst-case regret bound as the exponentiated gradient algorithm. Both [4] and [3] provide new prospect on understanding the convergence of non-convex gradient descent. More recently, [23] provides more general result, tightly characterizing when gradient flow can be written mirror flow by introducing the notion commuting parameterization.
online gradient descent whose loss
GGogle AI Princeton
Prinneeoon University
"Correspondence to: caaaai@ccspiinceoo..dd
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 The Amid-Warmune question
The works of [4, 3] are limited in two respects: either they are restricted to the continuous-time gradient-flow setting, which is impractical, or they address specific algorithms (Winnow, Hedge, EG for linear regression) with a relative entropy divergence. Amid and Warmuth pose the question of extending the reparameterization idea to the general online convex optimization as well as the conditions where this can be obtained. Solving the question from [4] would give an answer to realistic scenarios and algorithms, with precise regret and running time bounds, for certain non-convex optimization problems that can be solved to global optimality using gradient descent.
1.2 Statement of results
Our study starts from the more general problem of regret minimization in online convex optimization. Specifically, we study the reparametetization of online mirror descent (OMD) as online gradient descent (OGD) [30] for general online convex optimization. We show that under certain geometric and smoothness conditions, a non-convex reparameterized OGD algorithm closely match the original convex OMD algorithm. Quantitative bounds on this matching allow us to prove that the OGD algorithm after reparameterization achieves an O ) regret bound. This bound is discrete-time and fairly general, applying broadly to smooth, bounded mirror descent regularizers rather than anything more specific. We also provide sufficient conditions for non-convex losses such that OGD implicitly has an equivalent mirror descent regularizer and hence will have O(T3) regret.
Our analysis relies on a simple and new algorithmic equivalence technique, which may be of independent interest. The key step is to show that the outputs of OMD and reparameterized OGD are very close to each other when initialized from the same point. Considering the OGD update perturbed version of OMD along with the fact that OMD can tolerate bounded (adversarial) perturbation per trial allows to prove (T regret bound for the OGD update.
This answers the open question raised in [4], generalizing from continuous-timm gradient flow and specialized algorithms, to general online convex optimization. The regularization term of MD is also generalized from relative entropy to any strongly convex function. Further, for discrete-time reparameterization, our results extend to arbitrary Lipschitz convex loss functions, as opposed to custom analysis for specific settings of expert prediction, linear prediction, and linear regression [3].
1.3 Paper structure
Section introduces the setting and sketches out background work the continuous setting. Section provides our main result, which is subsequently proven in Section 4. Section 5 provides analysis in the opposite direction, showing the existence an equivalent mirror descent regularizer for some non-convex gradient descent problems. Some analysis is deferred to the Appendix.
1.4 Related works
Gradient descent is the simplest and one of the most popular algorithms in convex optimization. Extensive studies have been conducted show the convergence of GD the global minimizer in both the stochastic optimization setting [24], and the online convex optimization setting [31]. For the non-convex setting, however, finding the global minimum NP-hard and most work focuses on convergence to first-order stationary points instead. The well-known descent lemma guarantees the convergence of non-convex GD when the objective is smooth, and dropping smoothness is possible other conditions are introduced [10]. Many works consider avoiding saddle points; [22] shows that
GD converges to local minimizers a.s. if all saddle points are strict while [19] proposes perturbed gradient descent to escape saddle points. It's also shown that even in the online setting, chasing first-order stationary points is possible [17].
Mirror descent, first introduced by [25], generalizes the gradient descent method in the sense that it can adapt to the 'geometry' of the optimization problem [11]. Its analogue the online setting, online mirror descent also achieves tight regret bounds [27] and without projection is shown to be equivalent to the classical regularized follow-the-leader (RFTL) method with constant step-size. Though it's natural to think of mirror descent as changing the geometry of the optimization objective in gradient

---

descent [15], the idea to explain non-convex GD by a corresponding convex MD is explored only recently.
The most relevant works to ours are [4] and [3], which prove the equivalence between continuous time OMD and OGD after reparameterization, and special discrete-time algorithms when the regularization is the relative entropy, respectively. Our results extend [4] and [3] to general discrete-time OCO with general regularization.
Preliminaries
2.1 Notation
For function f IR > Id, we use the notation Jf(x) Rd + Rd to denote the Jacobian of f at We the notaion @ represents element wise product of vectors. Given strictly convex function R: Rd + Rd we denote the Bregman divergence as
DR(œlly) R(x) R(v) vR(y) (x -)
For a convex set K. and strictly convex regularizer R, we use [x)x)) == arg min (R(vllz) to denote Bregman projection, with shorthand II II!"" for Euclidean projection. Given positive-definite matrix M Rdddd, we define the norm ||||| M == Vx Mæ. We use the notation, Bр == fa E Fd ||>||p S 1} for lp ball and B denote the intersection of the lp ball and the positive orthant.
2.2 Online convex optimization
We consider the online convex optimization (OCO) problem. At each round the player A chooses K. where K. C Rd is some convex domain, then the adversary reveals loss function ft(x) and player suffers loss [x()). The goal is to minimize regret:
T
T
Regret (A) = Σ f((s)) - min Σ f((z) zek
1=1
1=1
The player is allowed to get access to the (sub-)gradient (zfi(z;) well.
2.3 Reparameterizing continuous-time mirror flow gradient flow
In the continuous-timg time setting, we have exact conditions from [4] where the trajectory of mirror-flow exactly coincides with that of gradient descent in reparameterized space. Concretely, mirror flow f: IRd + R. is defined by the following ordinary differential equation (ODE):
i vB(x(1)= = (()((()))
(1)
at
In Theorem 2 of [4], this update shown to equivalent the following gradient flow ODE with xxf) = q(((t)):
du -V((((())))))
(2)
at
if the mirror descent regularizer R and reparameterization function g satisfy [V Ju(u),,(u)) This relationship between the Hessian of the OMD regularizer and the reparameteriza- tion function assures that, up to second order factors in ||u v|12
1 Dnlg(w))la(v)) 2
v1
(3)
so the geometry induced by R is approximately transformed into Euclidean geometry by y g-1 Because higher order factors vanish in continuous time, this assures that mirror flow and this reparameterized gradient flow coincide as desired.

---

2.4 Discretizing the updates
Unfortunately, continuous-time updates cannot be implemented in practice must rely discretization. Using the forward Euler scheme for discretization of (1), yields the mirror descent algorithm. After discretization, the exact equivalence of mirror descent and reparameterized gradient descent no longer holds as higher order factors in (3) are relevant. This motivates the open problem of [4] of finding general conditions under which the discretizations of these continuous time trajectories closely track each other. We tackle extending these results through the online setting described above.
The Online Mirror Descent (OMD) algorithm has the following update on
Vi((++1) = VR(x,) - (x+(
T++1 = arg min Dn(sellu++1) xEK
where R K. -> IR is 1-strongly convex regularization over the domain", Dn is the Bregman divergence, and y1 is initialized to satisfy VR((n) = 0.
Another equivalent interpretation of OMD is
Tt+1 arg min Vfe(<r)) (x xx)) + -n(xllaae) aEK
1)
The most important special case is online gradient descent (OGD): #1+1 (x< - which is OMD with (R(z]lar [x)) = | 11. In this paper we consider reparameterizing general OMD update simple OGD update. We introduce assumptions of the regularizer, reparameteriza- tion, and losses in the sequel.
2.5 Assumptions
Assumption 1. There exists a convex domain K' C Rd and a bijective reparameterizzation function q: K' + K. satisfying [V)( (y( with qu).
We also make the following smoothness/Lipscheee assumptions:
Let G 1 be a constant. We assume q is G-Lipschitz, and the 1- strongly convex regularization R is smooth with its first and third derivatives upper bounded by some constant G. The first and second derivatives of q are bounded by G. Furthermore, assume that for all x E K. Du(x)l-) is G- G-Lipschitz over K.
Assumption 2.
Finally, assume loss functions have bounded gradients and the convex domain has bounded diameter with respect to the Bregman divergence.
Assumption 3. The loss functions fe have gradients bounded by [[Vf((>)lla S GF for all K. The diameter of K. suPa.yeK Dı((<ll)= < D.
3 Algorithm
We now provide our main result, regret bound for Algorithm 2. We note, Algorithm and Algorithm 2 are the (projected) forward euler discretizations (1) and (2). It's tempting directly analyze the regret of OGD with losses fe( fi(g()). The main barrier in doing so that f isn't 'n't necessarily convex. However, we show that the OMD and OGD updates are in fact On --loss to each other, therefore the OGD update still suffers only sublinear regret.
'Usually, the strong convexity of a mirror descent regularizer is with respect to some norm that is not necessarily the l2 norm. In this work, the focus is on the dependence the regret on I', so for simplicity we consider just the f2 strong convexity, which will worsen constants, but does affect the dependence on Z'.

---

Algorithm Online Mirror Descent
Algorithm Online Gradient Descent
1: Input: Initialization E K, regularizer R.
Input: Initialization i1 K' =q (K).
2: for / -,.,.., , do
2: for = ,, do
3: Predict
Predict u,
4: Observe (z+)
4: Observe (f, V[((((u))))
5: Update
Update
Ut+1 (VR())
U++1 = d4 - (V(((m)) uz+1 (V++1)
2i+1 (1(+1)
6: end for
6: end for
Remark 1. The gradient oracle ff. can also be calculated from an oracle of Vf. if we know the reparameterization function q.
The reparameterized gradient descent uses Euclidean projection rather than Bregman projection. This can potentially be an advantage if Euclidean projection can be computed efficiently on q (KC) (eg. via method like (29]), while Bregman projection less efficient on K.
Remark 2.
Theorem Under Assumptions 1-3, by setting 17 2/3 10/3Gp D the regret of Algorithm
2 is upper bounded by 2 D /11331/3
Proof of the theorem is in Section 4.
3.1 Examples
We now provide a few example settings. Note that in all three settings, @ are such that f(u) = f(a(w) be nonconvex for convex f.
Exponentiated gradient using quadratic reparameterization One of the most popular algorithms for online learning over the filled-in simplex IC = BJ is the Exponentiated Gradient (EG) [8]. In this case, show that OGD with quadratic reparameterization q(u) 1/2 u. has vanishing average regret. We empirically verify that reparameterized GD iterates and EG iterates stay close on a toy problem in Figure 1. In [3] custom analysis is provided for linear losses that achieves optimal regret, but our approach has simpler and more general analysis. If R(x) Σi= x, log(:;) then OMD is EG. In this case, if r q(u). then
Jg (T) = diag( (///uu/))duuu/// diag(u @ u/4) = diag(a(u)) = diag(r) = R(=)]-
K' =¹= {u R
Σ u 11}
2B 2
We note that for this example, Assumptions will not hold as relative entropy not sufficiently behaved near the boundary of the simplex. This be handled by modifying K. to be the smoothed simplex where all weights are at least & for some e. This is fairly standard technique. e can be chosen such that the full regret in sublinear (see App. B).
Log barrier with exponential reparameterization Consider the case of log- barrierrier regularization R(z) = - log(z;) with K. = [s, 1]d It can readily be shown that the box constraint maps to box constraint. Consider r = q(v) exp(u), where the exponential elementwise. We see Assumption is satisfied as
(u) T = diag(exp(u))dia((xpp/// = diag(g(u)?) - diag(=²) R(x()
Tempered Bregman divergences with power reparameterization A more recently studied family of mirror descent regularizers interpolate between l2 regularization and negative entropy regularization [5]. Regularization for this family uses link function VR(x) log, (x) (x1-T
Onne drawback of our approach is that the current analysis does not work for the true simplex like [3] because (JC) is the positive part of the unit sphere, which is not convex set.
5

---

Loss
Iterate Distance
0.18
0.0020
0.14
0.12
0.0015
0.08
0.0010
0.06
0.0005
0.04
0.0000
100
150
200
50
100
150
200
Figure 1: Gradient Descent using reparameterization g(u) = 1 @ u produces iterates that closely track Exponential Gradient for simple fixed quadratic loss example.
1), where is temperature that range between O and As r approaches the link function approaches the natural logarithm, and hence the update approaches EG, while r = 0 corresponds to & regularization. Such divergences are amenable to reparameterization when K. B
To see this, ignoring constant factors | R(x))~1 = xx for r E [0. 1). Now if q(u) u - where the power is elementwise, then (u) diag(u=-) diag(g(u)>/3) diag(x*/2) as desired. Now, we note that the reparameterization is power, so B would get mapped to the B which is
convex long
7/2.
3.2 Challenges
In some situations, do not have closed form solution the differential equation described by Jq- For example with the 8-hypentropy regularizer of [14], the reparameterization involves q (z) (z) f(2 + 3 dz, and this integral does not have known closed form. Furthermore. other cases of interest, like Neumann Entropy regularization for Matrix Multiplicative Weights (28) seem difficult to fit into this framework as Assumption is challenging to use with spectral functions.
Reparameterization analysis
We now move on to the proof Theorem The proof idea is to show that the OMD and OGD iterates are close to each other after single update step starting from the same initial point. Then we can view the OGD update perturbed version of OMD, and combine it with the fact that the OMD algorithm can tolerate bounded noise per trial.
We begin with the following key lemma showing that the updates dr+11 and g( created by OMD and OGD respectively, are close to each other from the same initial point 2z q(wx). ) To do this, we carefully analyze the errors that occur due to the approximation in (3) starting from a proximal formulation of mirror descent. We can show that the two updates are solutions to approximately the same strongly-conve objective, hence the solutions must be close.
Lemma 4. Suppose Assumptions 1-3 hold and æt = g(we), then we have that || g(ue+1)lla O 1/2)).

---

Proof. We consider the following forms of Algorithms 1 and 2.
I++1 arg min (f(( T (x 10-x- xxe++ + Dn((<lar))
#E
1
arg min (u,) (u u4) + 2m
Us uBl12
U++1
We observe that both objectives we minimizing can be written the sum of linear function plus a strongly convex function. In particular, if || xx ||2 > 2n p, then the objective takes positive value which can't be minimal because taking then the OMD iterate ft-1 E K2 == K2nGr .. Likewise, ue+1 E K2. := K2
I gives O. Define Kr,s. =Kn far || xell2 r).
Using Taylor expansion with Assumption 2, for Det(o) with || xea l2 S 2r we rewrite it as
Dn(=[[=,) = R(x) R(xx)) - vR(x,) Tx (x-xx,) 2.)
(x -xa) 42 (x))) - x4) + O G 1 zz ((.)) + E(x),
where e(r) = O(G D[G-G)m") for r E K, And the OMD update becomes
T++1 = arg min (z(( - xz) + 2n
||:- - xe ( + +
zEK.
We now use Taylor expansion to relate (f(()))(C (u- - ui) to (f(((z)) (x- - xz). Let x q(u) for
E KY, hence R₁ K2nGr-GP... then we have
Vfr (u) we) Vf(((a)) Jq(u)((- u)
Vfe(xz) Ja(E))))(( - (x:))
= Vfe(xe)) (1( - -x1) + E(x))
Vfe(az)) (z 21) + +(()),
where E(x) = O
Using the above approximation, we can rewrite the OGD update as
1
q(u++1) 1) = arg min V[(())) (x - xx)) + 114 (x)
(x:))
aek,
21
On the other hand, we can rewrite 1 (x) - q (x=) )12
1 [o) (x))) |J - xz) [a) +
| x 11 (o.) (x.) + O(G
Then by Assumption 1, V J (T 1 (x=) so we conclude that Bn(x((z)) and 2y l1q (x) - q (z:) are
We can then rewrite the OGD update as
q(u-1)) arg min (z( xz) 1 |- Z(R + +E(x)
ZER,
2n
where E(x) = G(G* for E R, We note that K, C R, as needed.
Comparing both OMD and OGD updates, the objective functions are only off by an O term, therefore the minimizers are also O n cclose since the objective functions are both (()) strongly convex.
7

---

It can be shown that if projection is not required, || qust ll2 = (n))) in Lemma 4. Furthermore, if the projection operation that Algorithms and perform are the same, the distance only gets closer. Such a bound would result in an O(VT) regret bound. For the case of EG over the simplex, the projection operations in both are the same weight scaling operations, so this could be part of making (vT)) regret possible, though this still requires a better approach for handling exploding Lipsehitz constants (see App. B).
Remark 5.
Next, we show that the OMD algorithm is actually robust to noise: with (potentially non-stochastic) bounded perturbation on the output 2 per round, we can still get vanishing regret.
Lemma 6. Suppose Assumptions and 3 hold and Algorithm A does the following update:
J++1 = T2 + arg argmin Vf(( (T - x4) + Dn((2l)re)) zER
17
where ||rala S C. The regret of Algorithm A can be upper bounded by
CTG
D
1
Regret(A)
"1
17
2
This follows from slightly modified analysis of OMD from [16], where the effect of the perturbation is bounded due to the Bregman divergence being Lipschitz. In particular, we end up with the standard regret bound for mirror descent that follows from a telescoping argument with additional error term
Dn(w"11a (1x)) Dz(a" 1x+? S CTG
where x. is the counterfactual mirror descent iterate with r2
Full proof of Lemma can be found in Appendix A. Combining both lemmas, we complete our proof of Theorem 3:
Proof. Algorithm 2 gives perturbed version of OMD with perturbation bounded by C' = 0(7²) into the bound of Lemma 6, the regret is upper bounded by G v nT' + 2) ignoring the lower order term. Optimizing this and all constants gives the choice of 17 = T 2/3 G Gp and regret bound 0/T233))/)
due Lemma Plugging C'
Implicit OMD reparameterization
We have shown that general convex OMD can be reparameterized (potentially) non-convex OGD, with vanishing (Tá) regret. The other direction from OGD to OMD is even more interesting: given a non-convex OGD, can we show its global convergence by showing the existence of a convex OMD which corresponds to OGD implicitly?
In other words, given a convex and compact domain K", what do we need to know about the domain K' and the (not necessarily convex) loss Ft to ensure the existence of such equivalence? Fully characterizing the necessary and sufficient condition seems hard, and provide here simple sufficient condition which covers some known scenarios.
Assumption 4. We assume the following properties about Q.
There exists a function such that f((u) can be written as fe(g(u)) where fc convex.
q is a CC-diiffemorrphism and (u is diagonal.
q(K') convex and compact.
We argue that once the conditions above are satisfied, there exists a regularization R and corre- sponding OMD with the desired equivalence. The only thing we need verify is the existence of strongly convex regularization R which satisfies Assumption 1. We first show that Jg (u) always has

---

non-zero (in fact, with the same sign because of continuity) determinant due to the fact that is diffeomorphism. Then R can be reconstructed by integrating twice its Hessians which we compute from the equation in Assumption 1. R is also strongly convex as the Hessians are strictly PSD. We note that such conditions may not be tight, but are general, succinct and may cover some interesting examples.
Theorem 7. Given a convex and compact domain K', and not necessarily convex loss ft satisfying Assumption 3. When Assumption 4 is met, there exists OMD object with convex loss St. convex domain and a strongly convex regularization R satisfying Assumption 1. As a result, running Algorithm 2 on loss fi(u) has regret upper bound Ō
Proof. The first two properties are satisfied by the assumption. We verify the third property by constructing regularization R. which is strongly convex and satisfies Assumption 1. The rest follows Theorem 3. By the fact that g is a diffeomorphism, J,(u) is an invertible matrix. The fact that T is invertible, and further (z) > 0.
(u) is an invertible matrix implies that (u)
Denote (()) (T
0 which is well defined by the above argument, we want to (u)). By the assumption that Jg (u) is diagonal,
construct R such that q(u) as
write
q(u)= = (4l (u1), (, (2(uu), qa(ua))
where each qi a scalar function, such that H (u) diagonal with H H(u) = (/(((( which only depends on ut We set H(((())) = Σi= R2 (q: (u:()) and denote the function Ru(u,) = R;(g: with variable u; then by the chain rule we have that
R (u:) ((s.)
R R,,(u)) - ((,) + (d((u,)) (x;)) Plugging the first formula into the second one, we eliminate the (x;))) term:
(u,) (u, (ux) + (g(((=))² R2 (x:) g((44)
Recall, we want to find R such that R. (x;; = 1/ (d.))) Plugging it back to the equation above, the problem is reduced to find Rg such that satisfies the ODE
((u)) (u.)
(u.) - B.
d((u)) =0.
It's known that there exists a solution to any linear and continuous second-order ODE. In fact, using the standard variation of constant method, one example solution Ri (u;) can be
R (w.) (((4)) ("" 1 du cıg((1:). ((())
where c₁. C₁ are constants and C min 0; It's well-defined because o' (u:) always has the same sign. To verify the correctness, we calculate that
R (w:) = (ux) 1Th Lhy du + 1 + (us)
d((u)
which solves the ODE together with the solution of Ri (m:)-
Next, plugging (u,) = J Rg (u)du and u = -x) into the expression of R gives a solution
of the regularization. Its strong-convexity is implied by the fact that V (x) H(u) 0 and is continuous over a compact domain, thus there exists a constant c > 0 such that (x > cI.
Finally, q being 8 di-ifffeomorphism means that both q and y are 3 times continuously differen- tiable. By the compactness of domains and the continuity of the derivatives, there exists a constant G satisfying Assumption 2. A similar argument holds for R.

---

Conclusion
We study the convergence non-convex gradient descent in this paper, by showing (approximate) algorithmic equivalence between gradient descent and mirror descent in the discrete setting. We prove that under certain geometric and smoothness conditions, running OGD on non-convex losses obtained by reparameterizing a convex OMD has regret bound O(Tă), answering an open problem in [4]. Our analysis is based on a new algorithmic equivalence technique, combining the one-step closeness between OMD and the reparameterized OGD and the robustness OMD. We further extend our result to the other direction, providing sufficient conditions for non-convex OGD to have an implicit corresponding OMD and thus converge well. We leave several questions as future directions.
1.
Is the O(T3) regret bound improvable to O(vT) in general? The decay in the bound in this work seems to be caused by differences projection the reparameterized space and the original Bregman projection. Perhaps different analysis technique can produce optimal bounds.
2. Can assumptions for reparameterization be relaxed? For example, is clear that Assumption is necessary condition. In the implicit mirror descent direction, it may be possible to lift the diagonal (n(u) assumption Theorem 7 with more refined conditions on PDEs. Perhaps the commuting parameterization conditions from [23] can be adapted from the continuous to the discrete setting.
10

---

References
[1] Naman Agarwal, Zeyuan Aluen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1195-1199, 2017.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameteriration,, 2019.
[3] Ehsan Amid and Manfred Warmuth. Winnowing with gradient descent, In Conference on Learning Theory, pages 163-182. PMLR, 2020.
[4] Ehsan Amid and Manfred KK Warmuth, Reparameterizing mirror descent as gradient descent. Advances in Neural Information Processing Systems, 33:8430-8439, 2020.
[5] Ehsan Amid, Manfred KK Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic loss based on bregman divergences. Advances in Neural Information Processing Systems, 32, 2019.
[6] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pages 244-253, PMLR, 2018.
[7] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[8] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicatiie weights update method: meta-algorithm and applications. Theory of computing, 8(1):121-164) 2012.
[9] Yu Bai and Jason D Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv:1910.01619 2019.
[10] Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):33--348, 2017.
[11] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[12] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint 1.00804 2018
[13] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks, arXiv preprint arXiv:1810.02054. 2018.
[14] Udaya Ghai, Elad Hazan, and Yoram Singer. Exponentiated gradient meets gradient descent. In Algorithmic Learning Theory, pages 386-407 4074 PMLR, 2020.
[15] Suriya Gunasekar, Blake Woodworth, and Nathan Srebro. Mirrorless mirror descent: natural derivation of mirror descent. In International Conference on Artificial Intelligence and Statistics, pages -30552331.. PMLR, 2021.
[16] Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv: 1909.05077 2019.
[17] Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games. In International Conference on Machine Learning, pages 1433-1441. PMLR, 2017.
[18] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnel: Convergence and generalization in neural networks. arXiv preprint / 2018.
[19] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
11

---

[20] Kenji Kawaguchi. Deep learning without poor local minima. Advances in neural information processing systems, 29, 2016.
[21] Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International conference machine learning, pages 2902-2907. PMLR, 2018.
[22] Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on learning theory, pages 1246-1257. PMLR, 2016.
[23] Zhiyuan Li, Tianhao Wang, JasonD) Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence mirror descent. arXiv preprint arXiv:2207.04000 2022.
[24] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[25] Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. SIAM Review, 1983.
[26] Mahdi Soltanolkotabi, Adel Javanmard, and Jason Lee. Theoretical insights into the op- timization landscape of wee-parameteriieed shallow neural networks. IEEE Transactions on Information Theory, 2018.
[27] Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent. Advances neural information processing systems, 24, 2011.
[28] Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. Journal of Machine Learning Research, 6(34):995-
1018, 2005.
[29] Ilnura Usmanova, Maryam Kamgarpour, Andreas Krause, and Kfir Levy. Fast projection onto convex smooth constraints. In International Conference Machine Learning, pages 10476-10486. PMLR, 2021.
[30] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference International Conference on Machine Learning, ICML' '03, page 928-935,20 2003.
[31] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pages 928-934 2003.
[32] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- wwrrperraeterrized deep ReLU networks. arXiv preprint 1xXiv:1811.08888 2018
12


Reviews:
[{"review_id": "iHnW-aoBPbm", "reviewer": "Reviewer_x2pL", "summary": "This paper shows that under several assumptions, online mirror descent for convex losses can be written as a perturbed version of online gradient descent for possibly non-convex losses with an $O( T^{2/3} )$ regret, up to a reparameterization. By a similar understanding, this paper also discusses when online gradient descent for non-convex losses is provably no-regret by the reparameterization argument. ", "questions": "1. Please check the correctness of the first example in Section 3.1. \n2. Is there any relevant application of Theorem 7 in Section 5? ", "limitations": "Assumption 2 basically assumes that everything should be Lipschitz. This assumption is violated for exponentiated gradient descent and online mirror descent with self-concordant barriers, for example. The authors also noticed that the matrix version of exponentiated gradient \"is difficult to fit into this framework.\" The self concordance of the regularizers in these examples may a useful property to replace the Lipschitz assumption. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The argument is very simple yet reasonable and actually novel, as far as I know. \n\n**Weaknesses**\n1. The first example in Section 3.1 seems to be wrong. That example considers online exponentiated gradient descent on the probability simplex, arguably the most representative instance of online mirror descent. As relative entropy is not Lipschitz on the probability simplex, violating Assumption 2, the smoothed simplex is proposed to be a fix. However, then points close enough to the origin should be removed from the set $\\mathcal{K}'$, meaning that $\\mathcal{K}'$ is non-convex and the theory in the paper does not apply. \n2. The other two examples in Section 3.1, online mirror descent with the log barrier and the tempered Bregman divergence, are much less representative compared to exponentiated gradient descent. \n2. Section 5, which provides conditions when online gradient on non-convex losses may be viewed as online mirror descent on convex losses and hence is no-regret, should be the most useful part. Unfortunately, no relevant example is provided. \n2. There are some typos. \n    - Ln. 95: $\\Vert x \\Vert_p$ instead of $\\Vert x \\Vert p$\n    - Ln. 105: $\\nabla^2 R$ instead of $\\nabla^2_R$\n    - The equality following Ln. 205: $\\nabla f_t ( x_t )$ instead of $\\nabla f_t$\n    - The article \"the\" is missing in several places. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LKJiHm-8mdK", "reviewer": "Reviewer_NwoT", "summary": "The paper studies an approximate equivalence between online gradient\ndescent (OGD) on non-convex losses with online mirror descent (OMD) on\nconvex reparametrizations of the losses. Special cases of this\nequivalence were already known from [3] and [4], but the present paper\nattempts to set up a general theory. Its main results are:\n- Theorem 3, which gives sufficient general conditions for the\n  approximate equivalence to go through, leading to an O(T^{2/3}) regret\n  bound for OGD on the non-convex losses.\n- Section 3.1, which provides example instances of OMD on convex losses\n  which can be approximated this way by OGD on non-convex losses.\n- Theorem 7 goes in the other direction: it gives sufficient conditions\n  for OGD on non-convex losses to be approximated by OMD on convex\n  losses.\n\n", "questions": "* Could you indicate how the G that appears in Theorem 3 scales with T,\n  and verify that R is 1-strongly convex for all three examples in\n  Section 3.1?\n* Could you answer the remark above about the proof of Theorem 7? \n\n", "limitations": "Section 3.2 provides a very good discussion of some of the limitations\nof the approach.\n\nThe limitations in footnotes 1 and 2 seem sufficiently important to put\nthem somewhere in the main text.\n", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper is very well written, especially the introduction.\n* The approximate equivalence between non-convex and convex online\n  optimization is an exciting new direction, for which few results are\n  yet available. It would be great to have a general theory that\n  describes when such equivalences are possible.\n\nWeaknesses:\n* It is not clear that the general theory covers any interesting cases:\n  1. It does not recover the previous results from [3] and [4].\n  2. I do not consider the examples provided in Section 3.1 to be very\n  convincing. In the first two examples, it would seem that G could be\n  as large as T, so then Theorem 3 would be vacuous. For the last\n  example, I am not sure how the constants play out.\n  3. Theorem 7 does not quantify how the strong convexity parameter c>0\n  of the regularizer R that is constructed, depends on the properties of\n  q and tilde{f}. It could therefore be \n\nIn spite of these weaknesses, the overall proof approach does seem like\nthe natural way forward, by quantifying the approximation error in the\nequivalence. If my questions below can be answered satisfactorily, I am\ntherefore still mildly in favor of acceptance, even if there are no\nstrong examples.\n\nRemarks:\n* Theorem 3 assumes that R is 1-strongly convex. This should be stated\n  explicitly in its conditions. I am also concerned that this is not\n  verified in the examples from Section 3.1, so do they really satisfy\n  this condition?\n* In the Proof of Theorem 7: I don't understand how you get from the\n  displayed equations above \"solving the above formulas\" to the ODE\n  below.\n\nMinor Comments:\n* Line 80: equivalence between OMD and FTRL requires constant step size.\n* \"Euclidean\" should be capitalized throughout the paper\n* Line 95: p should be a subscript in p-norm\n* The square on the Hessian appears to overlap with the nabla symbol\n  throughout the paper.\n* Line 108: Shouldn't q^{-1} be q? (Maybe I was just confused here.)\n* Assumption 1: Should the Hessian be interpreted as the Hessian of R or\n  the Hessian of R(q(.))\n* Algorithm 1: f_t -> f_t(x_t)\n* Line 147: \"cab\" -> \"can\"\n* Line 205: f_t -> f_t(x_t)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A-6bJ3iWq_h", "reviewer": "Reviewer_ARJZ", "summary": "This paper shows that for a certain class of non-convex problems, online gradient descent has a O(T^{2/3}) regret. Previous works by Amid and Warmuth show that gradient flow for minimizing a reparametrized function is equivalent to mirror flow for minimizing the original function. This work takes a step forward by showing in discrete-time, online gradient descent on a reparametrized objective has a sublinear regret.\n\nThe high-level idea is that the discrete-time online mirror descent has a O(\\sqrt{T}) for the same class of problems. By carefully bounding the discrepancy between online mirror descent for the original problem and online gradient descent (OGD) for the non-convex re-parametrization, a sublinear regret of OGD can be obtained.\n\n\n", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While the corresponding continuous-time result has been established in the previous work, the discrete-time setting seems to be left open. This work fills the gap.\n\nIn my opinion, this paper is pretty much borderline for the following reasons:\n\n1. While I appreciate the theoretical result, I think it will be more helpful if the authors can discuss the advantage of conducting discrete-time online learning on the reprametrized functions, since the regret gets worse, i.e., one could simply use OMD for the convex problems.\n\n2. Following the first point, I think the title should be modified and be more specific, since the technique seems only applicable to a certain class of problems and critically relies on the particular connection between OGD and OMD that has been established in the prior work by Amid and Warmuth.\n\n\n\n\nMinor:\n1. I don't quite understand Line 200-202. Perhaps a more detailed derivation would be helpful?\n2. Line 215: \"both both\".\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept