Continuized Acceleration for Quasar Convex Functions  in Non-Convex Optimization
Authors: Jun-Kun Wang
Andre Wibisono
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Quasar convexity is a condition that allows some first-order methods to efficiently minimize a function even when the optimization landscape is non-convex. Previous works develop near-optimal accelerated algorithms for minimizing this class of functions, however, they require a subroutine of binary search which results in multiple calls to gradient evaluations in each iteration, and consequently the total number of gradient evaluations does not match a known lower bound. In this work, we show that a recently proposed continuized Nesterov acceleration can be applied to minimizing quasar convex functions and achieves the optimal bound with a high probability. Furthermore, we find that the objective functions of training generalized linear models (GLMs) satisfy quasar convexity, which broadens the applicability of the relevant algorithms, while known practical examples of quasar convexity in non-convex learning are sparse in the literature. We also show that if a smooth and one-point strongly convex, Polyak-Lojasiewicz, or quadratic-growth function satisfies quasar convexity, then attaining an accelerated linear rate for minimizing the function is possible under certain conditions, while acceleration is not known in general for these classes of functions.


Published as a conference paper at ICLR 2023
CONTINUIZED ACCELERATION FOR QUASAR CONVEX FUNCTIONS IN NON-CONVEX OPTIMIZATION
Jun-Kun Wang and Andre Wibisono
Department of Computer Science, Yale University (jun-kun. wang, andre. wibi sonisoooollllll @yaleeddl
ABSTRACT
Quasar convexity is a condition that allows some first-order methods to efficiently minimize function even when the optimization landscape non-convex. Previous works develop near-optimal accelerated algorithms for minimizing this class of functions, however, they require subroutine of binary search which results multiple calls to gradient evaluations in each iteration, and consequently the total number of gradient evaluations does not match a known lower bound. In this work, we show that a recently proposed continuized Nesterov acceleration can be applied to minimizing quasar convex functions and achieves the optimal bound with a high probability. Furthermore, generalized linear models (GLMs) satisfy quasar convexity, which broadens the applicability of the relevant algorithms, while known practical examples of quasar convexity in non-convex learning are sparse in the literature. We also show that if a smooth and one-point strongly convex, Polyak Eojasiewizz, or quadratic quadratic-growth function satisfies quasar convexity, then attaining an accelerated linear rate for minimizing the function is possible under certain conditions, while acceleration is not known in general for these classes of functions.
find that the objective functions of training
INTRODUCTION
Momentum has been the main workhorse for training machine learning models (Kingma & Ba 2015
Wilson et al., 2017 Loshchilov & Hutter 2019 Reddi et al. 2018 He al. [016)] Simonyan &
Zisserman 2015 Krizhevsky et al. 2012)) In convex learning and optimization, several momentum
methods have been developed under different machineries, which include the ones built on Nesterov's estimate sequence (Nesterov) 1983 2013). methods derived from ordinary differential equations and
continuous time techniques, Krichene et al. |015|Sccieur al., 2017 Attouch et al., 20018] [Su et al.,
2014: Wibisono et al. 2016 Shi et al. 2018 Diakonikolas & Orecchia 2019), approaches based on dynamical systems and control (Hu & Lessard Wilson et al.) 202 algorithms generated from
game via no-regret learning strategies (Wang al.) [202aa] Wang & Abermethy| 2018)) Cohen et al.) (02I). and a recently introduced continuized accelcration (Even et al. 2021). On the other hand, in the non-convex world, despite numerous empirical evidence confirms that momentum methods converge faster than gradient descent (GD) in several applications, see e.g., Sutskever et al. (2013); Leelere & Madry (2020), first-order accelerated methods that provably find a global optimal point are sparse in the literature. Indeed, there are just few results showing acceleration over GD that we are aware. Waan et al. (2021b) show Heavy Ball has an accelerated linear rate for training an over- over-paramnn parametrizedd ReLU network and a deep linear network, where the accelerated linear rate has square root dependency on the condition number of a neural tangent kernel matrix at initialization, while the linear rate of GD depends linearly on the condition number. follow-up work of Wang et al. (2022) shows that Heavy Ball has an acceleration for minimizing a class of Polyak-Lojasiewiic. functions (Polyak) 1963). When the goal is not finding global optimal point but a first-order stationary point, some benefits of incorporating the dynamic of momentum can be shown (Cutkosky & Orabonal 2019; Cutkosky & Mehta 2021 Levy et al. 2021 Nevertheless, theoretical-gronndee momentum methods in non-convex optimization are still less investigated to our knowledge.
playing two- two-player zero
With the goal of advancing the progress of momentum methods in non-convex optimization in mind, we study efficiently solving min,, [ww,, where the function f(-) satisfies quasar-convexity (Hinder

---

Published as a conference paper at ICLR 2023
et al. 2020 Hardt et al.) 2018 Nesterov et al. 2019 Guminov & Gasnikov 2017 Bu & Mesbahi
2020). which is defined in the following. Under quasar convexity, it can be shown that GD or certain momentum methods can globally minimize function even when the optimization landscape is non-convex.
Definition 1. (Quasar convexity) Let p p> 0. Denote w, a global minimizer of f() R + R. The function f()) is p-quasar convex for all w E R,, one has:
f(w.) 2 f(w) _ ff(w), w. -w).
(1)
P
For μ > O, the function f(-) is (p. μ.) stt-nngyyy quasar corvex for all is E R., one has:
f(w.) 2 f(w) + - (V w) + H ||,, wll?
(2)
2
For more characterizations of quasar convexity, we refer the reader to Hinder et al. (2020) (Appendix D in the paper), where thorough discussion provided. Recall that a function f(-) L-smooth if
f()) S f(y) + (Vf(y), x y) + 1/2 || y/1² for any and y. where L 0 is the smoothness constant. For minimizing L-smooth and p-quasar convex functions, the algorithm of Hinder et al. (2000) takes (1 w.ll number of iterations and O ( of function and gradient evaluations for getting an e-optimality gap. For L-smooth and (p, (s)-tronglly
(L [ [ log
1 total number (E
pc!!2
quasar convex functions, the algorithm of Hinder et al. (2020) takes O ( (VE/" log (*) number of iterations and O
VL/H log
( log
number of function and gradient evaluations, where L/R
: f(wo)
/ |z0 w. 1|2, and wo and zo are some initial points. Both results of 2020 improve those in the previous works of Nesterov et al. (2019) and Guminov
(ww)
Hinder et al.
& Gasnikov
2017) for minimizing quasar and strongly quasar convex functions. A lower bound
Ω
L [0gg w.
the number of gradient evaluations for minimizing quasar convex functions
pc
via any first-order deterministic methods is also established in Hinder et al. (2020). The additional logarithmic factors the (upper bounds of the) number of gradient evaluations, compared to the iteration complexity. result from binary- subroutine that is executed in each iteration to determine the value of a specific parameter of the algorithm. A similar concern applies to Bu Mesbahi (2020), where the algorithm assumes an oracle is available but its implementation needs a subroutine which demands multiple function and gradient evaluations in each iteration. Hence, the open questions are whether the additional logarithmic factors in the total number of gradient evaluations can be removed and whether function evaluations are necessary for an accelerated method to minimize quasar convex functions.
We answer them by showing an accelerated randomized algorithm that avoids the subroutine, makes only one gradient call per iteration, and does not need function evaluations. Consequently, the complexity of gradient calls does not incur the additional logarithmic factors as the previous works, and, perhaps more importantly, the computational cost per iteration is significantly reduced. The proposed algorithms are built on the continuized discretization technique that is recently introduced by [ven et al.] (202I) to the optimization community, which offers a nice way to implement continuous-time dynamic as a discrete-time algorithm. Specifically, the technique allows one to use differential calculus to design and analyze an algorithm in continuous time, while the discretization of the continuized process does not suffer any discretization error thanks to the fact that the Poisson process can be simulated exactly. Our acceleration results in this paper champion the approach, and provably showcase the advantage of momentum over GD for minimizing quasar convex functions.
While previous works of quasar convexity are theoretically interesting, lingering issue is that few examples are known in non-convex machine learning. While some synthetic functions are shown in previous works (Hinder et al. 2020; Nesterov et al., 2019 Guminov & Gasnikov (017)), the only practical non-convex learning applications that we are aware are given by Hardt et al. (2018 8), where they show that for learning a class of linear dynamical systems, a relevant objective function over convex constraint set satisfies quasar convexity, and by Foster et al. (018), where they show that a robust linear regression with Tukey's 's biweight loss and a GLM with an increasing link function satisfy quasar convexity, under the assumption that the link function has bounded
2

---

Published as a conference paper at ICLR 2023
second derivative (which excludes the of Leaky- Leakk--eLUU.. In this work, we find that the objective functions of learning GLMs with link functions being logistic, quadratic, ReLU, or Leaky-Rela satisfy (strong) quasar convexity, under mild assumptions the data distribution. We also establish connections between strong quasar convexity and one-point convexity (Guille-Fscuret et al. 2022
Kleinberg al. 2018), the Polyak-E.ojasiewice (PL.) condition (Polyak (663,Karimi al. 2016),
and the quadratic-growth (QG) condition (Drusvyatskiy & Lewis] 2018). Our findings suggest that investigating minimizing quasar convex functions is not only theoretically interesting, but is also practical for certain non-convex learning applications.
To summarize, our contributions include:
For minimizing functions satisfying quasar convexity or strong quasar convexity, we show that the continuized Nesterov acceleration not only has the optimal iteration complexity, but also makes the same number of gradient calls required get expected e-optimality gap or an 6-gap with high probability. The continuized Nesterov acceleration avoids multiple gradient calls in each iteration, in contrast the previous works. We also propose an accelerated algorithm that uses stochastic pscudo-gradients for learning a class of GLMs.
We find that GLMs with various link functions satisfy quasar convexity. Moreover, we show that if smooth one-point convex, PL, or QG function satisfies quasar convexity, then acceleration for minimizing the function is possible under certain conditions, while acceleration over GD is not known for these classes of functions in general in the literature.
PRELIMINARIES
Related works of gradient-based algorithms for structured non-convex optimization:
Studying gradient-basee algorithms under some relaxed notions of convexity has seen a growing interest in non-convex optimization, e.g., (Gower et al.)
202T Vaswani al. 2019:
2022 Tin 2020).
These variegated notions include one-point convexity (Guile Eecuuee et al. 2022 Kleinberg et al.
2018). the PL condition (Polyak] [963] Karimi al.)
2016). the QG condition (Drusvyatskiy &
Lewis 2018), the error bound condition (Luo & Tsengg 1993 Drusvyatskiy & Lewis] 2018). 8), local
quasi convexity (Hazan et al., 2016), the regularity condition (Chi et al.| (2099), variational coherence
(Zhou et al. (017)) and quasar convexity (Hinder et al. 2020 Hardt et al., 2018; Nesterov et al.)
2019|Guminoo Guminov & Gasnikov 2017
Bu & Mesbbhii] 2020). For more details, we refer the reader to
the references therein.
The continuized technique of designing optimization algorithms:
The continuized technique was introduced in Aldous & Fill (2002) under the subject of Markov chain and was recently used in optimization by Even et al. (202 b. where they consider the following
random process and build connection to Nesterov's 's acceleration (Nesterov) 1983 2013):
dw; = m7 (2 wt)dt 76 V ff(www (t))
(3)
dz = n/ (w, 21 - (
in which Th, 1/.5 Yt, 7/ are parameters to be chosen and dtN is the Poisson point measure. More precisely, one has dN (t) = Ee òτ, (dt), where the random times Ti, T,,...,TTT.......... are such that the increments Ti, T2 Ti, Ta T2,... follow i.i.d. from the exponential distribution with mean 1 (so [T[T]] k)). Between the random times, the continuized process (3) reduces to a system of ordinary differential equations:
dw, n) (=+ )dt
(4)
dz, ny. (w: - 2, )dt.
(5)
At the random time Ti, the dynamic
is equivalent to taking GD steps:
WT. WT,, - YT, v((nn))
(6)
2r. 2T m/ (wr,,).
A nice feature of this continuized technique is that one implement the dynamic without causing any discretization error, thanks to the fact that the Poisson process can simulated exactly.
In contrast, other continuous-tima approaches (Krichene et al. 2015) Scieur al. 2017 Attouch
3

---

Published as a conference paper at ICLR 2023
al. 2018 Su et al., 2014; Wibisono et al. 2016 Shi et al. 2018 Diakonikolas & Orecchia 2019) do not enjoy such a benefit. The formal statement the continuized discretization is replicated as follows.
Lemma 1. (Theorem 3 in Even el al. [202] ) The discrelization of the continuized Nesterov accelera- tion (3) can be implemented as wk == WT. 2q = WTx+1--- 2k == 2Ty. Furthermore, the update of
the discretized process is in the following form:
Uy Ww + (āk wk)
(8)
xk+1 = ük - FR+1 f(x)
(9)
k = Ek + T εx) 7/+1 ((x));
(10)
where Tke The Pike Re are random parameters that are functions of Tt. T/ Tr. and %
We replicate the proof of Lemma in Appendix B Using the continuized technique, Even al. (2021) analyze the continuized Nesterov acceleration 3 for minimizing smooth convex functions
and smooth strongly convex functions with application in asynchronous distributed optimization.
MAIN RESULTS: APPLICATION ASPECTS
3.1 EXAMPLES OF QUASAR CONVEXITY
We start by identifying class of functions that satisfy quasar convexity. To get the ball rolling, need to introduce two notions first.
Definition (Cr-generalized variational coherence w.r.t. a function h((,-)) Denote w. E TRd global minimizer of a function f(-). We say that the function f(.) is generalized variational coherent with the parameter C2 > 0 if for all w E RR, one has: (V((w) w w.) 2 C,h(w, w.), where funectiov
h(w, w.): R x Rd R is non-negative function whose imputs are and W..
Observe that if a function is generalized variational coherent, then it is variational coherent, i.e., (V)( w - w.) > O. which is condition that allows an almost-sure convergence to w, via mirror descent /hou et al. 2017). Also, when the non-negative function luw, w., ) is squared lz norm, i.e., hw,, w..) 0C w- [23. becomes one-point convexity, i.e., { [w), w w.. 2 C C. - w. 113. In the literature, few non-convex learning problems have been shown exhibit one- me--ointt convexity, see e.g., Yehudai & Shamir (2020); Sattar & Oymak (2022): Li Yuan (2017); Kleinberg et al. (2018). However, GuuilleEscuret Escuret al. (2022) recently show that for minimizing the class of functions that are one-pointe convex w.r.t. a global minimizer w. and have gradient Lipschitzness
the sense that VV) f (w.wwll < L|IW w., l|2 for any Rd (which is called the upper enror bound condition in their terminology). GD is optimal among any first-order methods, which suggests that a different condition than the upper error bound condition might be necessary show acceleration over GD for functions satisfying one-point convexity.
Definition 3. (Cr-generalized smoothness w.r.t. function .)(,,)) Denote w. E TRd a global minimizer of a function f()) We say that the function f(-) is generalized smooth with the parameter G > 0 for all w e Rd, one has: f(w)= f(w)) < Crh(w, wa), where h(w, w.) 12d x Rd + R. non-negative function whose inputs are and W..
We see that if function f(-) is L-smooth w.r.t. norm square norm, i.e., h(w, w.) ||w
|| then is --generalized smooth w.r.t. the
w -.]l=
Lemma 2. If (()) is Co-generalized variational coherent and Ce-generalized smooth w.r.t the same non-negative function h(.,)), then the function satisfies p-quasar convexity with
C. C.
Proof. Using the definitions, have f(w) f(w.) S C.h(w,w.) W.) Ci (Vf(w), W.).
Lemma could be viewed as a modified result of Lemma 5 in Foster et al. 2018 where the authors show that GLM with the link function having bounded second derivative and positive first derivative satisfies quasar convexity. In the following, we provide three more examples of quasar convexity, while the proofs are deferred to Appendix C For these examples, assume that each
4

---

Published as a conference paper at ICLR 2023
sample
IR is i..d. from a distribution D, and that there exists w, E R such that its label is generated as y = aww_ 2),, where a(-) : RR + R is the link function of a GLM. We consider minimizing the square loss function:
f(w) == EEWD (a x) - =)²
(11)
3.1.1 EXAMPLE 1: (GLMS WITH INCREASING LINK FUNCTIONS)
Lemma 3. Suppose that the link function a ) is Lo-Lipschitz and a-increasingg ie.,, d' 2 0 (2)
for all 2 >> R. Then, the loss function /1) is o² ---enerllized variational coherent and L ---generllized smooth w.r.t. h(w, w.) = =EgDD [[[ - w.) ).) Therefore, it is 2n LG
-quasar convex.
An example of the link functions that satisfy the assumption is the Leaky-ReLU, i.e., ((2) max(az, 2), where
O. If further assume that the models w. w., and the features æ in 11 have finite length so that the input to the link function o.) is bounded, then the logistic link function, i... (z) (1 + exp(-=)) -1, is another example.
3.1.2 EXAMPLE 2: (PHASE RETRIEVAL.)
When the link function is quadratic. i.e., o =2 22, the objective function becomes that of phase retrieval, see e.g., Yonel Yazici (2020); Chi al. (2019). |Wite et al. (0166), Yonel & Yazici (2020) show that in the neighborhood of the global minimizers =w,, the function satisfies one-point convexity terms of the ln norm when the data distribution DD follows a Gaussian distribution, for which specialized initialization technique called the spectral initialization finds a point in the neighborhood (Ma et al. 2020). As discussed carlier, one- one-point convexity is equivalent to generalized coherence w.r.t. the square norm, i.e., h(w, w.) w|l w. I13- Therefore, by Lemma show quasar convexity for w in the neighborhood of +w., remains to show that the objective function generalized smooth w.r.t. the square norm ||w - w.ll..
Lemma 4. Assume that there exists a finite constant Cn > such that all w RRd the balls of radius R centered at =w, satisfy EEND [(w w.,) ) | I Cr. Then, the loss function 11 generrlrdl smooth w.r.l. h(w, w..) || w.
An example of the distribution D that satisfies the assumption in Lemma is Gaussian distribution.
3.1.3 EXAMPLE 3: (LEARNING A SINGLE RELU)
When the link function is ReLU, i.e., (2)) = (0, =), Theorem 4.2 in Yehudai & Shamir (020 shows that under mild assumptions of the data distribution, e-g., D Gaussian, the objective function is one-point convex in terms of the l2 norm. Therefore, as the case of phase retrieval, it remains to show generalized smoothness w.r.t. the square norm || w.113 112 for showing quasar convexity.
Lemma 5. When the link function is ReLU, the loss function 11 smooth w.rdt fuw,, w.) w| w. w.1l2
1 EE [l-e
3.2
EXAMPLES OF STRONG QUASAR CONVEXITY
In this subsection, we switch to investigate strong quasar convexity. We establish its connections to one-point convexity, the PL condition, and the QG condition.
3.2.1 ONE-POINT CONVEX FUNCTIONS WITH QUASAR CONVEXITY
It turns out that if a Co-one-point convex function f(-) satisfies p-quasar convexity, then it also satisfies strong quasar convexity. Specifically, we have the following lemma.
Lemma 6. Suppose that the function f(-) satisfies C.-one-pon point convexity and p-quasar convexity.
Then, it is also (p à (0-(1-1) -strongly quasar convex for any 0 > 1.
The proof is deferred to Appendix C.4 By Lemma 6, phase retrieval and ReLU regression illustrated in the previous subsection can also be strongly quasar convex.
5

---

Published as a conference paper at ICLR 2023
3.2.2 POLYAK-LOJASIEVICZ (PL) OR QUADRATIC-GROWTI (QG) FUNCTIONS WITH QUASAR CONVEXITY
Recall that function f(-) satisfies y-QG w.r.t. a global minimizer w. E
Rd if f(w) f(w.
2llw 1 w, for some v > and all w R (Drusvyatskiy & Lewis 2018 Karimi al. 2016). Recall also that function f(-) satisfies v-PI. 2v(J(w) - f(w))) S
[W(") for some
and all w IRu (Karimi et al. 2016). It is known that v-PL. function satisfies z-QG, see e.g..
Appendix in Karimi et al. (2016). The notion of PL. has been discovered in various non-convex
problems recently (Altschuler al. 2021 Oymak & Soltanolkotabi 2019 Chizat 2021 Merigot ct al. 2021). ) We show in Lemma 7 below that if v-QG function f(+) satisfies quasar convexity, then also satisfies strong quasar convexity.
Lemma 7. Suppose that the function f(+) v-QG and p-quasar convex w.r.t. global minimizer w., Then, it is also (p 1 p0, 14
u(I=9) >sstrngly quasar convex any < 1.
Lemma 8 in the following shows that GLMs with increasing link functions satisfy QG under certain distributions D, e.g., Gaussian, and hence they are strongly quasar convex by Lemma and Lemma Lemma 8. Following the setting of Lemma 3 assume that the smallest eigenvalue of the matrix
EgnD [xx' satisfies Amin (LE [x: ']) > Then, the function [1 is a² Amin (LE I)-QG
The proofs of Lemma 7 and Lemma are available Appendix
MAIN RESULTS: ALGORITHMIC ASPECTS
We first analyze the continuized Nesterov acceleration 33) and its discrete-time version minimizing quasar convex functions.
(8010) for
Theorem 1. Assume that the function f(-) is L-smooth and p-quasar convex. Let v/e satisfies
P 1/
0 2. and % 2L'
pt. Then, the update we of the continuized algorithm 3
Bls(w.) - [(w.)] 2T w.
8²(²²
Furthermore, for the update wh of the discrete-time algorithm
10
if the parameters are chosen
2/p
as = =1
Tv
0, t = +. and 7/22
0Tx
then
Te+1
2L
T (f(w)) - f(. E
2L 2L
is noted that the expectation with respect to the Poisson process, which is the only source of randomness in the continuized Nesterov acceleration. By applying some concentration inequalities, we can get a bound on the optimal gap with a high probability from Theorem]] [
The update wk of the algorithu 8 10- with the same parameters indicated in Theorem satisfies f(ix) - f(w.)= s 2cgLi]
Corollary 1.
with probability at least 1 2
1 for any
(1-o)
E (0, 1) and co > 1.
112//21100 -0011
Corollary implies that = O
number of gradient calls is sufficient for the discrete- time algorithm to get an e-optimality gap with a high probability, since the discrete-ting algorithm only queries one gradient in each iteration
pe
Next we analyze the convergence rate for minimizing (p, (u)-stoongly quasar-convex functions.
Theorem 2. Assume that the function S(-) is L-smooth and (p, po--toonyy quasar convex, where J O. Let 7t-
+, 7/- VEL. 1 v/c PV and TJ. TT. Then, the update wa of the continuized
algorithm 3 satisfies
Blf(w,)) - f(w.)l S (f(wo) - f(..) + 1| - w.ll²) exp (-PVHtt)
Furthermore, for the update ir of the discrete-time algorithm -7), if the paramelers chosen as
The = I+p exp (- P) Tk))) T = p(1 e11expp (1+p)) (TT+1-TT.)
ptesp( -1++)) (T=-I-T2) 7t = 1 7.
and 2/2 VKI. then
E.
[exp (p TT)) (f(wk) (0000-((wws ((w))) S S( S(w.) $1 w. w.

---

Published as a conference paper at ICLR 2023
Corollary 2. The update Wk of the algorithm
18 -0 with the same parameters indicated in (11(1-))
Theorem 2 with probability at least 1 - टह 1 for any c E (0. 1) and co > L.
satisfies f((xx) - (w..) ) I co (f(w)) - f(w=) + 2 11 - w. exp (1VE(11))))
The proof of the above theorems and corollaries are available in Appendix D Denote V f(āo) - f(w.)= + E1lã00 - =w,1 1|2. Theorem 2 and Corollary 2 show that the proposed algorithm takes
VLIH log (1) number of iterations with the same number of gradient evaluations to get an
e-expected optimality gap and an e-optimality gap with high probability respectively. Together with Theorem I and Corollary [1, these theoretical results show that the continuized Nesterov accel- cration has an advantage compared to the existing algorithms of minimizing quasar and strongly quasar-convex functions (Hinder et al., 2020 Bu & Mcsbahi] 2020; Nesterov et al., 2019] Guminoy & Gasnikov 2017), as it avoids multiple gradient calls in each iteration and does not need function evaluations to have an c-gap with high probability. On the other hand, it should be emphasized that the guarantees in the aforementioned works are deterministic bounds, while ours is an expected one or high-probability bound.
Recall Lemma 2 suggests that Ce-one-point convexity and L-smoothness implies p= 20, convexity. Furthermore, Lemma 6 states that quasar convexity and Co-one-point convexity actually
L quasar
implies /. (C.(0-1) strongly quasar convex for any 0 1. By combining Lemma 2 and
Lemma
6 we find that C--one-point convexity and L-smoothness implies (p- 2C,
L 1 L( 1))-
strong quasar convexity, for any 0 > 1. By substituting (p L م = L(B - 1)) into the complexity
o ( WiLL log (*) indicated by Corollary 2. we see that the required number of iterations to get an c @gap with high probability for minimizing functions that satisfy C.-one-poin poinppoint convexity and L-smoothness via the proposed algorithm is 0 C. - log (*) - L log ))) where we simply let 0 = 2. On the other hand, Guille-Escuret et al. (2022) consider minimizing a class of functions that satisfies Co-one-point convexity and a condition called the L-upper error bound condition (L-EB+), A function satisfies L-EB+ if | f(w) V ((ww))ll S L||w - w. ll for a
0
Co
fixed minimizer wx and any w E FA. Guille et al. (2022) show that the optimal iteration complexity & to have
[|w--w-l. 11 è for minimizing the class of functions via any first-order algorithm
[ -w.
is k = ((t)² log (:) and that the optimal complexity is simply attained by GD. Our result
does not contradict to this lower bound result, because L-smoothness and L-EB are different. L-EB+ is about gradient Lipschitzness between minimizer w. and any w, not for any pair of points in Rdd, and hence does not imply L-smoothness. Also, L-smoothness does not imply L-EB+.
Lastly, is noted that both theorems (and corollaries) require the L-smoothness condition. The reader might raise a question whether the smoothness holds for the case when a GLM with the link function ReLU or Leaky-ReLU.. For this case, it has been shown that the objective (TT) satisfies smoothness when the data distribution is Gaussian distribution, e.g., Lemma 5.2 in Zhang et al. (2018).
We also propose a stochastic algorithm to recover an unknown GLM w. E Rd that generates the label y of sample x E Id viay = (w, z). where ((.) is the link function. A natural metric for this task is the distance to the unknown target Ws, i..., f(w) := 1 || - w lI2. However, since we do not have access to W., we cannot use the gradients of f()) for the update. Instead, let us consider using stochastic pseuto-gradients, defined as g(w; E) == (a(wTz) x) - y) x, where & := (I, 3) represents a random sample drawn from the data distribution. Assume that the first derivative of the link function is positive, i.e., o'(.) 2 > O. Then, the expectation of the dot product between the pseudo-gradient and the gradient V (u) over the data distribution satisfies
Continuized accelerated algorithm with stochastic pseudo-gradient for GLMs:
Egl(o(w; (w; E), [[(W))] = (o x)- - 4) x, w w.>] = Ex (lolw x) - o (w.. x)) x. w w.)l
= E2
(a(w" T Tx) [w)) (lw -ww-w,)T w.) wzww x
2 aB ((w ---www) Tx))
xx) 27
(12)

---

Published as a conference paper at ICLR 2023
which implies that taking a negative of aseudo-gradien step should make progress on minimizing the distance 2 w|l - w.,12 112 on expectation when w has not converged to w. That is, the update W/++1 = Wt - Ti
nngg-ggeee (w:; 5) could be shown to converge to the target w, E R under certain conditions, where
y > is the step size. fact, this algorithm called (stochastic) GLMtrrn the literature (Kakade et al. 2011). We introduce a continuized acceleration of it in the following. But before that, let us provide some necessary ingredients first.
Denote a matrix (ww) == Ex (v x, w. x)xx J. where ((a, := a(a)-a(() a-b When the data
matrix satisfies Ex [xx = Ola for some A >> 0 and when the derivative of the link function a--) satisfies d'(- 2 a > O, one has H(w) = pla > O, where μ == at. We assume that for any w E RR it holds that Eg [ub(w x, w. <>>||==] [|]111rr
R (w)) for some constant R² > 0, and
also that 1E, [w(ww 2, w. x (10)
3 R for some constant R > O, where we denote | (w))- = x. Hww) tu and H(w) is the inverse of H(w). Define x == R². Then, have R S K. because Er ubwwT x, w. x) | xx |
=
م Bz [Nw x. w x)) [[=[[|]a=]]]] =
R² H ((w) kH (w). The assumptions can be viewed as a generalization of the assumptions made in Jain et al. 2018) : Even et al. (2021) for the standard least-square regression, in which case one has (2) and hence ( 1.
Our continuized acceleration with stochastic
steps can be formulated as:
du, (z: we)dl 7/ J= Iww; (1,
(13)
dæg = r/f [w: 21)dt - S2 (ww: E)dN (t. E),
where 77, n/- Te, 1 are parameters, ş E represents an i.i.d. random variable associated with sample used to compute a stochastic pseudo-gradient g(w; <), and dt E) Σn>1 (8cTv.es) ()) (dt, dE) is the Poisson point measure on R2z x E. We have Theorem 3 in the following, and its proof is available in Appendix E. where we also provide a convergence guarantee of the discrete-time algorithm.
Theorem 3. (Contimuized algorithm 13) for GLMs) Choose T/
RIt ne
RIC
R22
and %/ VIRRe Then, the update w; of 11 satisfies
E 1 - w. S [1w0 w.11 + ul|z0 w. (.1l2((00)-1) exp (-V -
EXPERIMENTS
We compare the proposed continuized acceleration with GD and the accelerated method of Hin- der et al. (2020) (AGD). For the method of Hinder et al. (2020), we use their implementation available online (Hinder et al., (202I). Our first set of experiments consider optimizing the empirical risks of GLMs with link functions being logistic, ReLU, and quadratic, i.c., solving min 1 ET
(a(w" x.) - "/² where n is the number of samples. Each data point x, is sam- pled from the normal distribution N(0 T2) and the label y: is generated as yi = (wo x;)), where w. (N, la) is the true vector and a--) is the link function. In the experiments, we the number of samples n 1000 and the dimension d = 50. The initial point of all the algorithms wy E IRd is close-to-zero point, and is sampled as wh 10 10-2c. where < N (0, Ia). Since the continuized acceleration has randomness due to the Poisson process, it was replicated 10 runs in the experiments, and the averaged results over these runs are reported. Both the continuized acceleration and AGD Hinder et al. (202T) need the knowledge of I., p. and for setting their parameters theoretically. We instead use the grid search and report the result under the best configuration of these parameters for each method. More precisely, we search L and μ over {.... 10a, 5 x 10a, 10s+1 ,.... with the constraint that L > μ. where g É (-2, -1, I,..., 4), and search E (0.01, 0.1, 0.53.
Figure I shows the results, where we compare the performance of the algorithms in terms of the function value versus iteration, the number of gradient calls, and CPU time (seconds). From the first column of the figure, one AGD of Hinder et al.) (2020) in terms of the number of iterations. From the middle and the last column, the continuized acceleration shows its promising results over AGD and GD when they
that the proposed continuized acceleration is competitive with
8

---

Published as a conference paper at ICLR 2023
function HIMESSG Decrddtr
Turctin WEACYS gEadETTT.
Suscion Vol tine 1Sed
AGD
200
(a) Logistic link (x: iteration).
(b) Logistic link (x: # calls).
(c) Logistic link (x: time).
turetion va LA Voa Iteration
Iuretion calte spacient calls
Suncrion cen valceme time ISee.
AGD
2.50
9.05
0.00
026
(d) ReL.U link (x: iteration).
(c) ReLU link (x: calls).
(f) ReLU link (x: time).
turetion us va tenator
f.retion valte gpacient cale
Suretion valce time
10
20-10
10-1
AGD
126
0.08 o225 0050 nets 2.30 p:t0 8:30 a1re 3
(g) Quadratic link (x: iteration).
(h) Quadratic link (x: # calls).
(i) Quadratic link (x: time).
Figure 1: Comparison of the continuized Nesterov acceleration, GD, and AGD Hinder al. 2020
distance 4.S. Re stion
sistance vis. Htredo
distance u5. Rerstion
12-1
Stathette GUPPNC
20"
Sepchantc G4/9
Stacwatc SUrence
10-11
30'1
1019
2006 KE2
2008 1003 2003
2003
6006
0500
10030
1000
150 2013 300 400 150 203 NE1 0000 3600
(a) Leaky-ReLU link (a = 0.01). (b) Leaky-ReLU link (a 0.1)
(c) Leaky-ReLU link (a = 0.5)
Figure Distance ||wk - w.|l v.s. iteration
measured in terms of the number of gradient calls and CPU time, which confirms that the cost of AGD per iteration is indeed higher than the continuized acceleration and showcases the advantage of the continuized acceleration. Our second set of experiments compare stochastic GLMtron and the proposed continuized acceleration of it (accelcrated stochastic GLMtron), in which both algorithms randomly select a sample to compute a stochastic aseudo-gradient at each step of the update. We consider learning GLM with a Leaky-ReLU, i.e., a22) = max (az, 2) under different values of a. Figure 2 shows the effectiveness of accelerated stochastic GLMtron, is significantly faster than stochastic GI Mtron for recovering the true vector W..
6 CONCLUSION
We show that the continuized Nesterov acceleration outperforms the previous accelerated methods for minimizing quasar convex functions. Compared to the previous approaches, the continuized discretization technique provides relatively easy way to design and analyze an accelerated algorithm for quasar convex functions. Hence, would be interesting to check whether this technique could offer any other benefits in non-convex optimization. Specifically, can the technique help design fast algorithms for minimizing other classes of non-conved functions? On the other hand, while examples of quasar convex functions are provided in this paper, natural question is if this property holds more broadly in modern machine learning applications. Exploring the possibilities might be another interesting direction.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank the reviewers for constructive feedback, which helps improve the quality of this paper.
REFERENCES
David Aldous and James Allen Fill. Reversible Markov chains and random walks on graphs. Unfinished monograph, 2002.
Jason Altschuler, Sinho Chewi, Patrik Gerber, and Austin Stromme. Averaging on the Bures- Wasserstein manifold: dimension-free convergence of gradient descent. NeurIPS, 2021.
Hedy Attouch, Zaki Chbani, Juan Peypouquet, and Patrick Redont. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming, 2018.
Jingjing Bu and Mehran Mesbahi. A note Nesterov's accelerated method in nonconvex optimiza- tion: a weak estimate sequence approach. arXiv:2006.08544 2020.
Yuejie Chi, Yue M. Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization:
An overview. IEEE Trans. on Signal Processing, 2019.
Lenaic Chizat. Sparse optimization on measures with wver-parameterized gradient descent. Mathe- matical Programming. 2021.
Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative Lipschitzness in extragradient methods and a direct recipe for acceleration. ITCS, 2021.
Ashok Cutkosky and Harsh Mehta. High-iiobabillty bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD, NeurlPS, 2019.
Jelena Diakonikolas and Lorenzo Orecchia. The approximate duality gap technique: A unified theory of first-order methods. SIAM Journal on Optimization, 2019.
Dmitriy Drusvyatskiy and Adrian S. Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 2018.
Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié, and Adrien Taylor. A continuized view on Nesterov acceleration for stochastic gradient descent and randomized gossip. NeurlPS, 2021.
Dylan Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non-convex learning and optimization. NeurIPS, 2018.
Robert M. Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. AISTATS, 2021.
Charles Guille-Fscures Escuret, Baptiste Goujaud, Adam Ibrahim, and Ioannis Mitliagkas. Gradient descent is optimal under lower restricted secant inequality and upper error bound. arX1v:2203.003342, 2022.
Sergey Guminov and Alexander Gasnikov. Accelerated methods for a- c-wwakly-quasi-convee problems. problem. arXiv:1710.00797. 2017.
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. JMLR, 2018.
Elad Hazan, Kfrr Y. Levy, and Shai Shalev-Shwartz. On graduated optimization for stochastic non-convex problems. ICML, 2016.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Conference Computer Vision and Pattern Recognition (CVPR), 2016.
10

---

Published as a conference paper at ICLR 2023
Oliver Hinder, Aaron Sidford, and Nimit S. Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. COLT, 2020.
Oliver Hinder, Aaron Sidford, and Nimit S. Sohoni.
httpp:://gtthbb.comm//
plaaa--convex-accelerttti. 2021.
Bin Hu and Laurent Lessard. Dissipativity theory for Nesterov's 's accelerated method. ICML, 2017.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. COLT, 2018.
Jikai Jin. On the convergence of first order methods for quasar-convex optimization. Sat1:20010004937, 2020.
Sham M. Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of generalized linear and single index models with isotonic regression? NeurIPS, 2011.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-lojasiewier condition. ECMI., 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Robert Kleinherg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local minima? ICML, 2018.
Walid Krichene, Alexandre Bayen, and Peter L Bartlett. Accelerated mirror descent in continuous and discrete time. NeurlPS, 2015.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton, Imagenet classification with deep convolu- tional neural networks. NeurlPS, 2012.
Guillaume Leclere and Aleksander Madry. The two regimes of deep network training. arXiv:2002.10376. 2020.
Kfir Yehuda Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive SGD with recursive momentum for nonconvex optimization. NeurlPS, 2021.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. NeurIPS, 2017.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, ICLR, 2019.
Zhi- Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: A general approach, Annals of Operations Research, 1993.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Muthematics, 2020.
Quentin Merigot, Filippo Santambrogio, and Clement Sarrazin. Non-asymptotic convergence bounds for wasserstein approximation using point clouds. NeurIPS, 2021.
Yuri Nesterov. A method of solving a convex programming problem with convergence rate (11/²²).
Soviet Mathematics Doklady, 27:372-376, 1983.
Yurii Nesterov. Introductory lectures convex optimization: basic course. Springer, 2013.
Yurii Nesterov, Alexander Gasnikov, Sergey Guminovand, and Pavel Dvurechensky. Primal-dual
accelerated gradient descent with line search for convex and nonconvex optimization problems. Proceedings of the Russian Academy of Sciences, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Overparameteriized nonlinear learning: Gradient descent takes the shortest path? ICML, 2019.
Boris Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki i Matematicheskoi Fiziki, 1963.
11

---

Published as a conference paper at ICLR 2023
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. ICLR, 2018.
Yahya Sattar and Samet Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems. JMLR, 2022.
Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d' Aspremont, Integration methods and optimization algorithms. NeurIPS, 2017.
Bin Shi, Simon S. Du, Michael I. Jordan, and Weijie J. Su. Understanding the acceleration phe- nomenon via high-resolution differential equations. arXiv:1810.08907, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
Weijie Su, Stephen Boyd, and Emmanuel Candes. differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. NeurlPS, 2014.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. ICML, 2013.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for overpa- rameterized models and accelerated perceptron. AISTATS, 2019.
Sharan Vaswani, Benjamin Dubois-Taing and Reza Babanezhad. Towards noise-adaptive, problem- adaptive (accelerated) stochastic gradient descent. ICML, 2022.
Jun Wang and Jacob Abernethy, Acceleration through optimistic no-regret dynamics. NeurIPS, 2018.
Kun Wang. Jacob Abernethy, and Kfir Y. Levy. No-regret dynamics in the Fenchel game: A unified framework for algorithmic convex optimization. arXiv:2111.11309, 2021a.
Jun-Kun Wang, Chi-Heng Lin, and Jacob Abernethy. A modular analysis of provable acceleration via polyak's momentum: Training a wide relu network and a deep linear network. ICML, 202
Jun-Kun Wang. Chi-Heng Lin, Andre Wibisono, and Bin Hu. Provable Acceleration of Heavy Ball beyond Quadratics for Class of Lojsake--ojasiewiez Functions when the Non-Convexity Averaged-Out. ICML, 2022.
Chris D. White, Sujay Sanghavi, and Rachel Ward. The local convexity of solving systems of quadratic equations. Results in Mathematics, 2016.
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113(47):E755- 2016.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods machine learning. NIPS, 2017.
Ashia C Wilson, Ben Recht, and Michael Jordan. A Iyapunov analysis of accelerated methods in optimization. JMLR, 2021.
Gilad Ychudai and Ohad Shamir. Learning single neuron with gradient methods. COLT, 2020.
Bariscan Yonel and Birsen Yazici. deterministic theory for exact non-convex phase retrieval. arXiv:2001.02855, 2020.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer ReLU networks via gradient descent. 0rXiv:1806.07808. 2018
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W. Glynn. Stochastic mirror descent in variationally coherent optimization problems. NewrIPS, 2017.
12

---

Published as a conference paper at ICLR 2023
A ALGORITHMS OF HINDER ET AL. (2200)
We replicate the algorithms in Hinder et al. (020)) using our notations for the reader's reference.
Their algorithms use subroutine of binary search determine the "mixing" parameter Tk-
Algorithm 1: AGD for (p. -ttrongly quasar convex function minimization in Hinder et al. (2020)
1: Set T. = PV II La 8 L. and 2/2
VAL
2: for 0,,,... K do
ag < BINARYLINESEARCH (J.WK, =k, PK ,
(228-0)
3:
4: Th 1 Ot-
5:
wk + (2): 16k))
6:
Wh+11 Up ik+1 (
7: 2k+1 2k + Tx( Ukk 2k) 7/+1 Vf(ux).
8:
end
9:
return WK
Algorithm 2: AGD for p-quasar convex function minimization in Hinder et al. (2020)
1: Set Th = 0, 7tk- t. and 7% Los where 02 = P--1 (V(Ok-1) + 4 0x-1 for k 2 0 and
8
2: for -0,1.... K do
3: as - BINARYLINESEARCII (f. wk, 2x, 0, p
(( -
4:
1- ak.
5: U2 = wk + Th (xk wp..
6:
Wk+1 uk 7k+1 V f(vk).
7: 2641 = 2k + Tuk 2k) 7 (((()))
8:
end
9: return WK
Algorithm 3: BINARY w, x, b, c. ([guues]] (Hinder et al. 2020
1: Assumptions: f L-smooth, w, 2 E Rd: b, c, ē 2 0; "guess" (optional) in [0, 1] if provided.
2: Define g(a) := fla (1 a)2) and = bllw 2112.
3: if guess provided and cg(guess) + guess(g/ (uess(g(guuess) (guess) - guess p) S cg(1) + then return
guess;
4: if g'() E p then return 1;
5: else if = or g(0) & g(1) + then return 0;
6: + 1 č+p
-|
7: lo <- 0, 7,0-7
8: while cg(a) aag'(a) ap) > c1) + do
+Ioo+ hi)/2
if ((a) < g(T) then
hi - og
else
lo ac
end
9: return o.
13

---

Published as a conference paper at ICLR 2023
B PROOF OF LEMMA 1
Lemmal (Theorem in Even et al. (2021)) The discretization of the continuized Nesterov accelera-
tion (3) be implemented Wk WT. the discretized process in the following form:
WT ok == 2Tg. Furthermore, the update of
Up = wk + Tāk wx))
(14)
Wk+1 Ük 7R+1 f((x)
(15)
Ek+1 3k + ( mạ) - V ((x)); where The Tik Ry are random parameters that are functions of nu Tee and 7
(16)
Proof. We replicate the proof (Even et al. 2021 for completeness. Recall between random times, we have the ODEs
du: (2 weldt
(17)
dz, (w - 2t)
(18)
Integrating from T3 to Th -1--
0 = Wh++1 = wr, + Tx(22, - -wT.) = Tb + Tx - ixk 2T = 2Tx + = (WTx - 2T,) = En + (2xx - 2x),
(19)
(20)
where 7h and o/c depend on 7)t and 1// respectively. Combing the above two equations, we have
Th+11 mΦ *'e 1
Tk (ūx TK Σx) āx + 7/( Σn),
(21)
where 7/ I-TE"
Furthermore, from (6) and 7 have
Wk+1 WT+41 = WT++1- TTh+ f(WT
Ük - YTe-1 V f((ū)),
(22)
Ōk-1 TT++1 2Tx+1 M/A (f(WTE)))) + ( Σx) Meees f(())).
(23)
Hence, 78+11 = YTEt1 and 7/441 Tarr"
C MISSING PROOFS IN SECTION 3
C. PROOF LEMMA 3
Lemma 3
Suppose that the link function a(2) (z) is LipLipschitz and cx-incresinng, i.e., d'(2) 2 0
for all = >> R. Then, the loss function 17 is o2 --gnneralized variational coherent and Lā generullizd
smooth w.r.t. l(w, w.) = EEED [[(w w.) s))]. Therefore, the function 11 is p I convex.
20²
quasar
Proof. We first show generalized variational coherence. We have
f(w),, w.) (g) EzwD [[oww] z) oww 2)) o'ww x)(w w., w/) d' (w [))( w.) xx)
EgaD [( (olw (olwTs)-o(uTa) -
(24)
(6)
2 a E [[(w - w.) Tx)
= a h(w, w.),
where (a) that y = (w x), (b) uses that olw aw)Ta)oolw]a switch to show generalized smoothness. We have wo x--xx----
0 oas O. Now let us
f(w) f(w.) = EAND { (a(wT - -(w x)
(25)
La ExnD [(w - (olu--w.TTo x) h(w, w.), La
< 2
14

---

Published as a conference paper at ICLR 2023
where the inequality is due Lu Lu-Lipschitzness of a(-). We can now invoke Lemma conclude that the objective function is
2a quasar convex.
1.g
C.2 PROOF OF LEMMA
4
Lemma Assume that there exists a finite constant Cn >> 0 Ouch that all w E TRd in the balls of
radius R. centered at =w satisfy EgnD [(w + w.) T 2) | S Cr. Then, the loss function 11
gegnerallee smooth w.r.t. h(w, h(w.w.) = || - nc 11.
Proof. We have
f(w) - f(w.) ExnD D (wwTx)
- [w] x2]
2 ((w [uuz)) - (wIx)) x)) ((w x) + (w] x)) 2
ExnD
(26)
2 |l0 w. w..1EEED
[(w + w.) w x) |,<1|]]
Cullw w.112
2
C.3 PROOF OF LEMMA 5
Lemma When the link function is ReLU,, the loss function smooth w.r.t. h(w, w.) = || w. w.112. 113.
11
2
Proof. We have
f(w) - f(ww) Eg
(o(w 2) o(wTx))) x:))
$ Ex
(w w. x)²)
1
$ Eg
|l w. 111
(27)
|21
w. I.
where the first inequality uses that ReLU is 1-Lipschitz.
C.4 PROOF OF LEMMA 6
Lemma Suppose that the function f()) satisfies Co--ne-poine convexity and p-quasar convexity.
Then, it is also (p L 2C.( -strongly quasar convex for any 0 1.
Proof. We have
s(w) f(w)) < (V[(w) w -.) / (V](w) -ww)
0-1 (V](w), w -we)
(28)
(V (w), -w-) 0-1 CCllww w. 1
where the last inequality uses the definition of C--one-point convexity. Rearranging the above inequality, we get (ww)) 2 f(w) + (V))), w. - w) 20. 1)/2
Iw, w|l2.
C.5 PROOF OF LEMMA AND LEMMA 8
Lemma 7 Suppose that the function f(-) is v-QG and p-quasar convex w.E.t. a global minimizer w..
Then, it is also (p .00, v(1-0) )-strongly quasar convex for any 1.
15

---

et. Published as a conference paper at ICLR 2023
Proof. By p-quasar convexity, have
(V[(w), w - w.) 2 (([(w) - f(ww))= = -i([(w) - f(w,)) + M( ((1-0)(((w) ()([ww - [(ww))
(29)
2 / - f(w.)) A( ((1 w| w. 11.
2
where the last inequality uses the definition of v-QG. Rearranging the above inequality, get f(w.) 2 f(w) + de (V (w)),, w. w) 211 v(1-0)/0 l|.. w|l?, which shows the result.
2
Lemma 8
Following the setting of Lemma assume that the smallest eigenvalue of the matrix satisfies Amin (Ex (x:x I]) > Then, the function (11) is a² Amin (D D 1)-QG
EgnD xx
Proof. We have
[(w) - [(ww) = EUND
(a(w x) - o[ x))²
2
1 fo(w" T x)) o(w] x) (w x w2, x))
27
ENND
2 w w
(30)
a BEnD I(w (wwTx- w x)
2
1
- a ww) EEED [x [ (w ww)
2
2 2
Amin (En~ [z, ')o w=ll?
where the second-tor last inequality uses that the derivative of the link function satisfies o d'()) 2
D PROOF OF THEOREM AND THEOREM
Theorem Assume that the function f(-) is L-smooth and p-quasar convex. Let n pt:
2 n/
0, Tt +, and 7/2 2T. Then, the update Wi of the continuized algorithm 3
satisfies
B(f(w:)) - f(w.)) 2L w+|l
p²t²
Furthermore, for the update We of the discrete-time algorithm
-
10
if the parameters are chosen
2/p
as Tk =
Tx TET1
The = O, ns = +, and 7/2
4Th
2T.
then
2L/1a0 w.ll
BIT (f(w)) [(w))) <
p²
Theorem 2 Assume that the function f(.) is L-smooth and (p, pt--trlyyly quasar convex, where O. Let 7/ VEL. T/- Pv and πT. v TTE Then, the update we of the continuized
algorithm satisfies
B[f(w:) - f(w.)l < (f(wo)- f(w.) + レー Il - w. w.. exp (-PV/.)
Furthermore, for the update ūi of the discrete-time algorithum
-1-1 the parameters are chosen as Tk -Itp exp (-(1 + P) Tk))) . p( p(1-expí (1+p)) (((e+1-T)))
ptexpl (1+0) E(Th.-TTT) -
and 7/2 VUL: then
Elexp (oV Th (f((W) -
- f(w.) + 11 - w.,1?
16

---

Published as a conference paper at ICLR 2023
The proof follows that of Theorem 2 in Even et al. (022)) with some modifications to account for (strong) quasar convexity. We will consider Lyapunov function for the continuized process ( defined as:
Φ A. (f(wr) f(w.)) ))- + _ || w.1l
B
(31)
2
We will show that the is super-martingale under certain choices parameters T)t, Vh nh, Th A., and By Let us first denote the process W, : (1, we; =e), whose dynamic is:
0
dw; = b(w,)dt + ((w))dN()) b(w))
m1( we) Lu)(wr zc)
G(wr) = 76 f(rr)
(32)
Then, by Proposition 2 of Even et al. 2021 we have
Φ. = Φ0 + (Vo(w.), ((ss)) + / (0(w, G(w,)) - ((w)) ds + Mr.
(33)
where M, is martingale. Therefore, to show o: is supermartingale, it suffices to show:
4 == (Vo(w.), b(ū.)) + o(w, + G(w.)) - ((w,) S O.
(34)
For the first term of L. we have (Vo(w)), b(wt)) = 0,6(0)) + (0w n1 mi(2 - wi)) + o n/(wer - 22))
dA. (f(w.) - f.) + 2 dt
1 dBc
2 w.
(35)
dt
+ ( - w/) + BeTl (2r Wx. 21 we)-
By (p, pt)-stonglly quasar-convexity, we have
[wx)) s(w.) < _ (V(xx), - -w.)
1 |luce wa
(36)
P
2
Furthermore, the following inequality holds,
(=e= W.: xx) S 2 (112e= - wall" - || - w=,l2))
(37)
because (z: - w.: W³- =1) (2+ w.. We
- wall 1 < || - w. ||
w. 1| 1| w.ll
(11ur - w.,12 -1ze= - 1. Combining
35
37
gives
(Vo(1))), b(1rr)) < dAA
dA.
1
dt Aone (V we w.) + Bell dt 14 2 || w.ll
+ ( dt Both) -1120- wall2 + Aene (V (wr), 2t - -w.)-
dB..
(38)
For the second term of It, have
o(w, + G(w:)) ((w)) = At (f(w; 7/. ((w))) - (a)
B. (1|z /(V)( w. + 7o [[x:))) || 10--w -ww.l" ww.l (39)
Since by smoothness, we have
f(w, ((w--7 ( ((w))) < (VI(u) /uli: -20 L 2
(40)
So the second term can be bounded as
p(w. + G(wx)) - (ww)) E (Bx(1))² Arr(2 - Ine) 2 [[([))]] - Wa, Vf(w))).
(41)
17

---

Published as a conference paper at ICLR 2023
Combining 34
38
41
have
1 dAA.
+ Berh dA:
w.) ) 4 - p dt AoTi.) (VS(ws), -w-)
db
dt (1) 2 1/uee
wall
dBB,
Beth) 2 2 |2 -w.ll (Am Ben)( wa)
1
(42)
dt
(Bi(T/)2 Arr(2 Ln)) _ [V
Now let us determine the parameters Th, The no, Ve As and B, We start by taking L.
Since we
need I S O, we want to satisfy
1 dA: dt Aetis
dB:
dA
A
Boll.
ArT = Bohs.
Boll = di H, Be(11)² =
(43)
dt
L
Let us choose
At
Bry
B
dA, P PAmT dt B. B, PPV LB,
A
Tp
(44)
LB,
A
V
LA
which ensures that the last three conditions of (43) are satisfied. It remains to show that the first two hold:
ddA,
dB.
A.B.
= A dt
= Bol = PHV
(45)
dt
L
We have
( At)
dA (a)
P
B
Bi)
1 dB. (b)
PH
A
(46)
2/Ar Ar
dl
2
T
dl.
2v
B
dl.
2
T
where (a) uses that dA, dt
pho = pAi V LA,
B
from 455, and (b) uses
A.
from (45)
dt
The equations
46
imply that
d²
p211
2/L. d
Ad
VAL,
VB,
p dt (VA)).
(47)
dt
4L
D.1 D-QUASAR-CONVEX
Proof. (of Theorem !
For the case of = 0, we choose Ao = and Bp = 1. From 46). we have _ (vB.) = 0 so that
_ 2VL' consequently, VA,- P2ỘI From (44), conclude %t t. 7/6 2T v/ = 0, and T1- 2 Therefore, as oe is super-martingale, we get
B. 1 and that d (VAt)
[[AT([(WT) [.)] < [[(r]] Φn |1=0 w. 1|
(48)
So we have
- 4L| =0 - w. w.ll2
(49)
p²t²
This proves the first part of Theorem
The ODEs become
2
du- 7e(2 W/4 )dt
(2.
we wetd
(50)
pt
dz, = (e - 2e dtt = 0.
(51)
Integrating the ODEs from time to
2/P (wro 2x0)
Wt 2to +
(52)
21 2to
(53)
18

---

Published as a conference paper at ICLR 2023
Using Lemma I with to Tk. t Tk+1-+
(2) becomes
(1
Tk
2/0
Ts
2/p
uk 2x
+ Wk
(54)
Th-
T
2/p
This together with (8) implies that 7k
while comparing (00 and leads to
Te+1
* = 0 and 7 Th the second part of Theorem
Moreover, we have 7t mm 7. and % = 7/.
eT
This proves
2r
D.2 (p, -STRONGLY QUASAR-CONVEX
Proof. (of Theorem
From
44 we choose Y b. 71
VEL. The = PVE.
1
I. ni V We have
VA. Ao exp
221 T.
VB. VoVVTiex
P 1
T.7
(55)
Then, conclude that
(()r()(wr)) - f-)l s Biarl S $00 = Ao (f(wo) - f(w.)) + A0 7 ||20
w.
(56)
2
So we have
[[[(WT) - fa] (If(wo) - f(w.)) + 1"1 $1:00 - woll3) exp (-pp/ 41))
(57)
This proves the first part of Theorem
The ODEs
(4 become
dw, 11(2 wr)dt / (zr wi)dt
(58)
de, n/(we 2t) pV /1 (wo 21)dt.
(59)
The solutions
pioto + 2to +
Wio - 2o exp
((1 +(1+p))] pVy/ (t(tt to)
Wi
(60)
1 1+1 p
1 1+p
1
11 (1-))
-1o)) (2to -weo)
-to
exp
(11+ p)
(61)
1+p p
pioto
+ 2to
2to Wto
(-(1+ p) ([1-)))
2,
+ p
exp
(62)
1 1+1
1 ++ P
P.
1 exp (-(1+ p) V (wro 250))
zta + 1 + P
(63)
Taking to = Thi = Tk+1-s , the above becomes
1
1 (1 + p)
-Ta) Taa)) (3x wxx)
Ūk Wk +
exp
I. (TT+1 -
(64)
1+p
TTHI1- = Zn +
P
1 11-exp
exp
((11+ p)
"
H. [Tk+1 - -Th) (1a)) (wix - 5x)
(65)
+ p
Comparing equation (64) and 14 know that Th I+p exp
exp p) Tw)))
Furthermore, by using (64). we get
WR
Zk
p) (TTx+ Tw))) (ūx -xx)
(66)
Itp (1
exp (-(1 ex-
19

---

Published as a conference paper at ICLR 2023
Based 665, (66). and (21 have 7 7 and kk Vr.
we conclude that Th p+exp(-(L+o) =(Tx+1-Tx))
Moreover, we
This proves the second part of Theorem VpL"
D.3 PROOF OF COROLLARY AND COROLLARY
2
Corollary T
The update uk of the algorithm
8 10 with the same parameters indicated in for any
Theorem satisfies f((ix) - f(w.)= S 20a C (0, 1) and Co > 1.
(1-0)20"k with probability at least
c
Proof. Using Markov's 's inequality and Theorem [ we get
Pr T (f(x)) - f(w.)) )) 2 Col v =(TE(((.)-((w.))
2L 10--w, 1F
(67)
Co
Co
Let Co = 2T w.113 /p², where > 1 is universal constant. Then, with probability 1
1
(S(in) f(w-)) < 200
(68)
By Chebyshev's inequality, we have Pr ([7 BTT.] > cB(TT.) S
" where 0 is
Var(Ts)
universal constant. Hence, we have T3 2 (1 cT] -1 -1-c)k with probability at least = where we used the fact that B[Tx] Var[Th] with mean 1. Combining this lower bound of Th and (68) leads to the result.
as Tp is the sum of k Poisson random variables
Corollary 2:
The update We of the algorithm
70 with the same parameters indicated in f (w.) + $ = w-113) exp (-Pv c)k).
Theorem 2 satisfies f((xx) f(w.) < co (f
with probability at least
oa for any (0, and cp 1.
Proof. Using Markov's inequality and Theorem
2 get
Pr [exp (IVE (f(wx) - f f(w+)) 2 Col s elexpeev (m)))
f(Wa) f(wo_)+ 4 11 w.
Co
Co
(69)
Let Co == ca (s(w)) fw.) + =11 w. 13). where co is universal constant. Then, with probability 1 :.
exp (PV TT) (f(wx) - f(w+)) s c ((f(wo) - f(w.)) + 1 20-0 - w=
(70)
By Chebyshev's inequality, we have Pr ([T E 2 <B(TT))
マ where 0 is
Var(Tt)
universal constant. Hence, we have T3 2 -1- c)E = (1 - k) with probability at least 1 - 24 where we used the fact that E[Ta] Var [Tp] with mean 1. Combining this lower bound of Ti and (70) leads to the result.
Tk the sum of & Poisson random variables
E PROOF OF THEOREM 3
Theorem (Continuized algorithm 13 for GLMs) Choose Th = /
RR
T
and %/2
1
Then, the update wi of 13 satisfies
VanRz
E
w:: well
< 2
(ww0 w.112 + ul|z0 w. w.ll7r(mo) exp
(-V
1
RR
Proof. Let us denote H, = H (w)) = Ex [v. æ, w. "o)xxxx)) " and consider Lyapunov function for the continuized process defined as:
A
Br 1| - w. w|ll
Φi =
||we - w.
(71)
2
20

---

Published as a conference paper at ICLR 2023
We first show that di is super-martingale under certain values of parameters ne. M/ nt %, Au, and By. Let us denote the process Vy == (t, We, 2t), which satisfies the following equation:
1
dw, = b( + / ((M,E))N(t,E) b(wr) = me(E - w[) Inllus 24)
G(w = -ng((m E
(72)
Then, by Proposition 2 of Even et al. (2021) we have
Φ 0 + ( 1,ds Mr
(73)
where M, is martingale and 4 is (Vo(w,), b(w,)) + EglØ(u: + G(w)::) x(wxa)
(74)
For the first term of 4, we have
(V((w)), = 0, +
ne(z - wx)) + (W=(( - zx)
1 dAi | ww.12 + 2 dt
dB
1| - w. 1 + Arnetur - wa, 2t - we) + Beth - wa Hi - 21)).
2 dt
(75)
Since H, E. (w)) a, T x) x. 11 = pld. we have
We w. wallir,- S sll. -w.ll 11.12.
(76)
2
Using
76
we have
1 |l0c |w, w.1l2 S |lece wal1
w- 11 H.
(77)
2
Furthermore, the following inequalities hold,
(2t W,, H₂, (w: z1)) S 7 [1110g W2 11,11 H.1 11 -w wul12,
1
(78)
This because (Ee- - W.: H1 (we - 21)) (2t - Wa, H (w,, wa)) - 1| - w. wall?
S
(Iuu - wollH,, - 1| - w. well?,," 11
Combining -75
78 we get
dAi 1lwe - w. 112 +
dAe
(V(()))) I dt
Betk dt 11 2 |w4 - w. 100--w+lll
(79)
dB.
1 E1121 w. 11? + Acn - Was 24 - ww)-
Berh)
+
dl
For the second term of Le we have
Eg (e((1 + G( ()) - ((w)))
A (Ilwe- - -n:(w:: {) - w.ll2 - 11 - w.1lz) +
B.
(12a (hl(w;)) -w.ll? - -11ze
w. w.l?? mr ) Biyl(E wa, H₁ g E))
2
2
A 2 [1a(w;;))) 2 Acre(ue We, ((wrg {)) +
Be(11)²
Ee
2
2
(80)
Let us upper-bound the first two terms in (8). We have
Eg (llo((:::))]
Ez (w x) - y) x. (a(w, x) y) x>}
=
Ex (wT x, w. (0)2((((( - w.) x)2 |
(81)
(wy - w. E, [w( x, w. 2) [ w. w.)
< (we w.. E. [w x. w x:)rr
we w.>] ] = R?Il
w. 10..
21

---

Published as a conference paper at ICLR 2023
where in the last inequality used
Ex (wv x; w 2)]1|==|/>xx "] I R²E, [tb x, w w))rr [ R.H,
(82)
Furthermore, we have
Eg (e 6), wi ww)] Ex ( x) olw, ((,,.)) x)) x, we - ww-ll
(wr w.) En (ww(w Jax, w x)xr [[wr w.) - 1 w. w.l.H. (83)
Therefore, the first two terms in (80) can be bounded as
Ar la(w:: E)1l Aer (w, w. Iwws E)) - A R?
18g 2
A17e) 110x w- 19.. (84)
2
Now let us switch to upper-bound the last two terms We have
Eclllg(w; e) = Ex (ow x)) v) x, H. (a(w) x) v) x²)
Ex [e(w]] n, w x)) w.) "=>211=<11? H,
(85)
= (we - w. Ex (ww) x, w x² || 11
10x [] ,20, w.)
I REz|(wu Wa (w, x, w x)xr (we w.))l kllwu w. 117,
where in the last inequality, we used the assumption that
Ex (www xc w. 2/) axx ] 3 RE (1b(w) x. w x))x) J = -HH..
(86)
We also have
Eg [1 - w. (T-'g(wr,C = EEg [1/(2z - Wo, H (a(w, x) ow. x)) x²)
Be (76(2x W., H₂ " 2. w. x)xx (wi w-))
(87)
76/2e Wa, we w.).
So the last two terms in (80) can be bounded as
Be(1
Eg
[1 Oll
Brll w.s H, 1 E))
<
|/uce w. w-11.,,
Br
w.. wT w.).
2
(88)
Therefore, combining
84
88 and (0).
we have
Eg(ö(wr (w + G( {)) c(w,)]
And R
2
(89)
Ary
|wee w.ll Br/l(z
Wa, we w.)
2
Combining 79p. and 89
we have:
dA,
dAA, 1
4 <
AoTe)
||we -wall++ +
Benh
dt 11
5 Ill -w.111,,
dt
dB
Bith
111
18:s-wllig woll?, (ArTh - Brrl) (wo Was -w-) (90)
di
2
Arri R?
Be(r))²R)
Acti
||we -wallae-
2
Now let us determine Ths 1/s Yt, 76. A., and B,, We start by taking 7t gz. We want I, S 0, so we want to satisfy
dA.
dB.
dA, 41
A
Amm.
Betl-
Acn = Boyh
Bon dt
Bill
(91)
dt
dt
RR²
22

---

Published as a conference paper at ICLR 2023
Let us choose
A
BBn
B
d.A. /
A
B
A
R
1/
dt B. B,
PV
RR
(92)
which ensures that the last three conditions of 91) are satisfied. It remains to show that the first two hold:
dA,
dBt
A,Br
= BoTl = "V
(93)
dt
di
k
We have
(1)
A1)
1 dA, (a)
B.
d
(VB)) = 2 B dt
dB,
(b) P
A,
(94)
dt
A dt 2
RR
dt
2
R
where (a) uses that dA. Amp: A / AR and (b) uses that
B,
dB, dt
Bunk PV
A
from
KR
and
93 The equations on (94) imply that
d
VA)
V A
VB, = 2VRR2 (VAo).
(95)
df2
dt
Let us choose 7/- = R 7/2
VURiZ'
T// =
RHE Tte
v R.?
We have
1
1 VB. VAv/R exp
VA.- = Ao exp
2 RRRE"
(96)
2
Then, we can conclude that
[1 < [ld s 00 = ( I1l0 w.ll 12112
Bn
|[A,2 lu., w.
1120
w. wall
(97)
2
So we have
Ao
Bu 2
E
2
|0,, w-
11] 5
Ag
2
[wo
w. 112
=0 wc (12))))))
exp
R.R2
(98)
and we have
Bg Ao
from
96
and we can choose Au 1. This proves Theorem
3
Now let us switch to determine the corresponding parameters of the discrete-time algorithm
(8)
10
where the gradient V(w;) now replaced with the stochastic pseudo-gradient (() The ODEs (4)(55) become
dw:- = ne(== -w:)dt
RR.P (Et wx)dd
(99)
dæ. n/(rr 2()
V
11. R.R
(w: 22 22)
(100)
The solutions are
We
W't
2to
+
Wta
2ta
exp
(-2
kIR2 to)
M
(101)
2
2
Wto
+
1-exp
1 -
exp
-2
(t - -to))
(zeo - Wio)
(102)
2
21
Wto
+
2to
7to
Who
exp
-22 R.R2
1
to)
(103)
2
2
Z1o
+
exp
-2
H RR
(1 10)
(wic =x0))
(104)
Taking to Tk. T +1 the above becomes
P RRR (Tet1 Tk) )) (2x - -wx)
üy = 2b + 2
1 exp
2
(105)
1 exp
(-2
RRR (Tk+1 -Tx) )) (ixz Ex)-
(106)
23

---

Published as a conference paper at ICLR 2023
Comparing equation (105) and (14 we know 76 (1 exp (-2
(T++1 Tw))) and
R
Th exp (-2v (Tx+1 k++ Tx))) Furthermore, by using 105).
we get
wkk 2k (1 exp (-2v R (T&+1 Tx))
(ūx kk).
(107)
1-exp(
2
(Th Tc) (7 +1 Tc)
Based on 106), 107 and (21). we conclude that Ty have 7/k
RR Rे
Moreover, we
1+exp(
TT
R and 7 Tr.
V WARRE"
We can now conclude that the corresponding
discrete-time algorithm under the above choice of parameters satisfies
E
exp
(V
11
Tx
1
w.1l"]
2 0u
w.ll w1112
|| w. 11 (12(((0)))
(108)
RR
2
24


Reviews:
[{"review_id": "kD7saERU9H", "reviewer": "Reviewer_deQT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied minimizing quasar convex functions. Authors studied the relationship between quasar convexity and many common structure assumptions in nonconvex optimization, and verify that GLM satisfies quasar convexity under mild conditions. Then they proposed a new algorithm based on the continuized discretization technique in literature, the continuized Nesterov acceleration improves over existing algorithms and achieves the optimal complexity.", "summary_of_the_review": "Generally I am satisfied with this work. My main concern lies in that:\n\n1. How do you choose $T_k$ in Theorem 1, you mentioned that $T_k$ are random times. Are you referring it as a \"stochastic stepsize\", or you will predefine the $T_k$ (or the total iteration number as in many classical optimization literature) before running the algorithm?\n2. When comparing to Hinder's work, you mentioned they need an extra log complexity in the function evaluations. First I feel that such logarithmic difference is a bit incremental; second for me such binary search subroutine seems to be more toward a practical preference, if we just follow their \"General AGD Framework\" (Algorithm 1 therein), then the results in your work and Hinder's work should be basically the same.\n\nThank you for the effort.", "strength_and_weaknesses": "Strength:\n1. Connect quasar convexity with many existing structural nonconvex assumptions, and real application GLM\n2. Provide a complexity result which is claimed to outperform existing works.\n\nWeakness:\n1. The comparison with existing works is a little confused to me.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KcHkY0el_4", "reviewer": "Reviewer_YMJ7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "In this paper, the authors propose a randomized acceleration method based on the continuized scheme proposed in [1]. The method targets the nonconvex optimization problems  with quasar convex structure, and obtains the optimal complexity rate in expectation. The authors also illustrate that for a class of generalized linear models the quasar property holds and provides theoretical analysis to estimate the quasar convexity constants.\n\n\n\n\n[1] Even, Mathieu, et al. \"A continuized view on Nesterov acceleration for stochastic gradient descent and randomized gossip.\" arXiv preprint arXiv:2106.07644 (2021).", "summary_of_the_review": "The paper is of good quality, it provided a unified and justified quasar convex framework for many important nonconvex functions, and developed a novel accelerated method with improved complexity rate. While there is some limitation in the application, the theoretical contribution of this paper is sufficient, which has great potential to the development of nonconvex optimization. ", "strength_and_weaknesses": "Strength:\nThis paper not only improves the complexity of first-order methods for quasar convex optimization, but also identifies a large class of problems satisfying quasar convexity. It shows the great potential of developing algorithms in continuous time and I believe it will have growing impact to the community\n\n\nWeakness\n\nI am a bit curious whether quasar convexity is useful beyond the setting discussed in this paper. \nGLM is a motivating application for the proposed continuized method. However, it looks like the quasar convexity assumption relies on the fact that there is a perfect $w_*$ that interpolate all the data (i.e. the overparameterized setting), this seems to suggest some limitation of in real applications. \n\nIn example 3, the relu link function is not differentiable at z=0. Can you still apply the gradient based algorithm for such setting?\n\nTypo\n\nPage 4\n\nOn the last line: there exists a $w_*\\in\\mathbb{R}^d$\n\n\nNotations are inconsistent: Both $\\|\\cdot\\|$ and $\\|\\cdot\\|_2$ stands for Euclidean norm; they should be unified.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AL_sPbnSMzv", "reviewer": "Reviewer_8aev", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper found a simple (but effective) variant of the continuized Nesterov acceleration (Even et al., 2021) that achieves the optimal complexity (with high probability) under the quasar convex condition for the first time. (Quasar convexity is a non-convex condition that some gradient methods are known to find a global solution.) Previous results, built upon the standard (discrete) Nesterov acceleration, required multiple gradient evaluations at each iteration, and thus only had the near-optimal complexity. This paper then provides several quasar convex examples, such as generalized linear models (GLM), to support the importance of studying the quasar convexity.", "summary_of_the_review": "Finding an optimal first-order method for the (strong) quasar convex minimization has been an open question in the optimization community, and this paper has resolved it. Momentum has been the main workhorse for training \"non-convex\" machine learning models, and this work provides a nice contribution on expanding our knowledge on accelerated non-convex minimization.", "strength_and_weaknesses": "- This is the first first-order method that has the optimal complexity for quasar convex minimization.\n- Various examples satisfying the (strong) quasar convex condition are provided.\n---\n- One might view this as a simple modification of the continuized Nesterov acceleration.\n- An intuition behind the success of the proposed randomized method over the existing method for quasar convex minimization is not clearly given (other than the final proof), and this could be of interest to some readers.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6T3slFXYecs", "reviewer": "Reviewer_ZBaY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper has three main contributions.\n\nFirstly, under quasar convexity (an assumption weaker than convexity that still guarantees local minima are global minima) and smoothness, authors develop an optimization algorithm using the continuized framework of Even et al 2021 and obtain optimal rates with high probability, in contrast with Hinder et al. 2020 that have an extra log factor (although their convergence was deterministic).  They note that the convexity inequality in the analysis of Even et al is only used once and can be easily replaced by the quasar convexity inequality which leads to their result. \n\nThe second contribution is extending the GLMtron paper (Kakade et al) to use this framework as well for Generalized Linear Models. Some empirical comparisons are provided for algorithms in both contributions.\n\nThirdly, contribution is showing that certain classes of functions that had been used before satisfy quasar convexity, expanding the set of applications of this framework.", "summary_of_the_review": "The paper contains a nice idea that was well developed to show algorithms and their convergence in some quasar-convex frameworks and also adds new examples of quasar convex functions to the literature, which is another nice contribution.", "strength_and_weaknesses": "This is a nice paper. Realizing that the continuized framework of Even et al. does not require the progress-regret balancing step that leads to needing the binary search of Hinder et al. is a nice result. I would phrase the \"our contributions include\" and would not say that you \"improve\" over Hinder et al., since this result is in high probability (or with this E[T_k^2 * gap] result) and their result is deterministic\n\nI found really interesting that with this framework one can show that for the class of functions in Gille-Escuret et al. 2022, for which gradient descent is optimal, if you substitute the gradient Lipschitzness condition by smoothness then you can accelerate.\n\nOn the other hand, there is a small error/typo in your interpretation. You say that \"$L$-smoothness implies the $L$-Lipschitness of the gradients\". But it is the other way around. $L$-Lipschitness of the gradients implies smoothness. \nEDIT: I think I got confused and concluded that despite of this fact, what you said made sense to me. But now that I read it again it does not make sense. Since $L$-Lipschitness of the gradients implies smoothness, the class of smooth functions is larger. So it seems to me you are not getting any improvement under any additional assumptions. You are just showing \"better rates\" but because it is a different optimization metric (i.e., additive error in function value instead of multiplicative error in iterates, and also your result only holds with high probability). I would appreciate a clarification. \n\nIt would be better if you had error bars in the plots of your experiments.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%