Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
Authors: Michael Crawshaw
Mingrui Liu
Venue: ICLR 2025 Poster (2025)
Keywords: optimization
nonconvex optimization
stochastic optimization
adaptive optimization
relaxed smoothness
lower bounds
adagrad
Primary area: optimization
TL;DR: We provide lower bounds for several variants of AdaGrad in the nonconvex, stochasic, relaxed smooth setting.

Abstract: Recent results in non-convex stochastic optimization demonstrate the convergence of popular adaptive algorithms (e.g., AdaGrad) under the $(L_0, L_1)$-smoothness condition, but the rate of convergence is a higher-order polynomial in terms of problem parameters like the smoothness constants. The complexity guaranteed by such algorithms to find an $\epsilon$-stationary point may be significantly larger than the optimal complexity of $\Theta \left( \Delta L \sigma^2 \epsilon^{-4} \right)$ achieved by SGD in the $L$-smooth setting, where $\Delta$ is the initial optimality gap, $\sigma^2$ is the variance of stochastic gradient. However, it is currently not known whether these higher-order dependencies can be tightened. To answer this question, we investigate complexity lower bounds for several adaptive optimization algorithms in the $(L_0, L_1)$-smooth setting, with a focus on the dependence in terms of problem parameters $\Delta, L_0, L_1$. We provide complexity bounds for three variations of AdaGrad, which show at least a quadratic dependence on problem parameters $\Delta, L_0, L_1$. Notably, we show that the decorrelated variant of AdaGrad-Norm requires at least $\Omega \left( \Delta^2 L_1^2 \sigma^2 \epsilon^{-4} \right)$ stochastic gradient queries to find an $\epsilon$-stationary point. We also provide a lower bound for SGD with a broad class of adaptive stepsizes. Our results show that, for certain adaptive algorithms, the $(L_0, L_1)$-smooth setting is fundamentally more difficult than the standard smooth setting, in terms of the initial optimality gap and the smoothness constants.

Published as a conference paper at ICLR 2025
COMPLEXITY LOWER BOUNDS OF ADAPTIVE GRADI- ENT ALGORITHMS FOR NON-CONVEX STOCHASTIC OP- TIMIZATION UNDER RELAXED SMOOTHNESS
Michael Crawshaw
Mingrui Liu
Department of Computer Science
Department of Computer Science George Mason University Fairfax, VA 22030, USA mi mingrui 1 gmu edu
George Mason University Fairfax, VA 22030, USA mcrawsha@ gmu. edu
ABSTRACT
Recent results in non-convex stochastic optimization demonstrate the convergence popular adaptive algorithms (e.g., AdaGrad) under the (T.g I. -ssoohntsssss condition, but the rate of convergence is higher-order polynomial in terms of problem parameters like the smoothness constants. The complexity guaranteed by such algorithms to find e-stationary point may be significantly larger than the optimal complexity of θ (ALoRc achieved by SGD in the L-smooth setting, where A is the initial optimality gap, o² the variance of stochastic gradient. However, it is currently not known whether these higher-order dependencies be tightened. To answer this question, we investigate complexity lower bounds for several adaptive optimization algorithms in the (Lo, L1) -mm-sh setting, with a focus on the dependence in terms of problem parameters A, Lo, L1. We pro- vide complexity bounds for three variations of AdaGrad, which show at least a quadratic dependence on problem parameters A, Lo, L1. Notably, we show that the decorrelated variant of AdaGrad-Noma requires at least Q (A [f -4) stochastic gradient queries to find an e-stationary point. We also provide lower bound for SGD with a broad class adaptive stepsizes. Our results show that, for certain adaptive algorithms, the (Lo, L1 -smooth setting fundamentally more difficult than the standard smooth setting, terms of the initial optimality gap and the smoothness constants.
INTRODUCTION
The best performing optimization algorithms for modern deep learning are gradient- basee optimizers with adaptive step sizes. For today's large-scale deep learning tasks, such as training Large Language Models (LLMs), classical non-adaptive optimizers like SGD perform significantly worse than their adaptive counterparts, such as Adam (Kingma & Ba 2014) and AdamW (Loshchilov & Hutter] 2018)) However, remains open to theoretically characterize the efficiency of adaptive gradient algorithms for non-convex optimization.
An increasingly popular framework for describing optimization in deep learning is (La, L1)- smoothness, also known as relaxed smoothness (Zhang et al., (2020b). The conventional smoothness condition asserts that the norm of the objective's Hessian upper bounded by constant, while the weaker relaxed smoothness enforces only that the Hessian norm is upper bounded by affine function of the gradient norm (see Assumption
T). Empirical evidence suggests that this condition may characterize neural network training (for certain architectures) more accurately than conventional smoothness (Zhang et al. 2020b Crawshaw et al. 2022).
Several recent works analyze the efficiency of adaptive algorithms for non-convex optimization, particularly AdaGrad-N -orm (Li & Orabona 2019: Ward et al. 2020; Wang et al. 2023 Attia & Koren 2023 Faw al. 2023) and AdaGrad (Wang al. (022).. Indeed, adaptive algorithms for relaxed smoothness, since the local curvature of a relaxed smooth objective can be determined from gradient information, and adaptive algorithms adjust their step size based gradients. Existing
suited

---

Published as a conference paper at ICLR 2025
Table 1: Iteration complexity to find an e-stationary point in non-convex stochastic optimization. A is the initial optimality gap, L and (La, L1) are the smoothness constants for the smooth and relaxed smooth cases, respectively. a and (01, are constants bounding the stochastic gradient noise, depending on the stochastic assumption. See Assumptions I and for the full definitions. is the stabilization constant of AdaGrad. denotes a high-probability guarantee with failure probability 8 71, 72, 73 are defined and discussed in Section 6
Complexity
Stochasticity
L-smooth
0 ((Ata" i (z)) (((Ate 4 (I+ alyo") + vaugiton ò 8(sL+ A'Pottot)
SGD (Ghadimi & Lan 2013
(Bounded-Vaie Var)
Decoriclated AdaGrad Norm
(Subgaussian)
& Orabona 2019))
AdaGrud-Nori
(Affine-Var)
(Wang ct al.
2023
AdaGrad-Norm
ALot(o++)) + A 24(1103)
(Affine-nnise)
Attia & Koren
2023
AdaGrad-Noni Norm
AltovaI
(Bounded-Vary
(Yang et al.
2024)
(Lo, L1 smooth
SGD [Li ct al. 2024
An Mil
(Atol
(Atalla de
(Bounded-Var)
Mipt
Gradient Clipping
0 ((Ata)")
(Bounded-Noise)
Zhang et 202Ub
Gradient Clpping
( (1++) (Lo Voole+ + Let)
(Bounded- Var)
Koloskova et al. (203
AdaGrad-Ne -orm
((A2)7(L+ oz) + ALo (A fi
(Affine-Var)
Wang et al. (2023)
Devorrelaled Adaa AdaGrad-Noore
1 Li | Alyn" + 2467)
(Bounded-Noise)
[Theorem []
Decorrelated AdaGrad
(Theorem 2
12
(Bounded-Noise)
AdaGrad (Thcorem
(Bounded-Noisc)
Single-step Adaptive SGD
á Arani
(Afine-Noise)
(Theorem 4)
works demonstrate that AdaGrad can find an c-stationary point with iteration complexity that scales as - in terms of e, which matches the complexity of SGD in the stochastic, non-convex setting, However, these guarantees also show that the complexity of AdaGrad (and some variants) is upper bounded by a higher-order polynomial (i.e., at least quadratic) in terms of problem parameters such as A (initial optimality gap), o² (variance of stochastic gradient), and the smoothness constants. See Table T for a summary of these guarantees. This suggests the following question:
Can AdaGrad-type algorithms converge under relaxed smoothness without a higher-order polynomial complexity in terms of problem parameters?
In this paper, we answer this question negatively for several variants of the AdaGrad algorithm by providing complexity lower bounds that scale quadratically in terms of the problem parameters
A, Lo. L1. Our results are summarized in Table This shows that, in the non-convex, stochastic, relaxed smooth settings, the variants of AdaGrad considered here cannot recover the A complexity from the Lo-smooth case; in this sense, these algorithms suffer fundamental difficulty in the relaxed smooth setting. comparison, SGD with gradient clipping does achieve the classical complexity of A under the same setting as investigated in our lower bounds (Zhang et al. 2020a), which shows the surprising consequence that SGD with gradient clipping outperforms AdaGrad in this setting. Additionally, we give lower bound for adaptive SGD with broad class of adaptive step sizes, in a setting where stochastic gradient noise scales linearly with the gradient norm.
We emphasize that the complexity's dependence problem parameters be important for dis- tinguishing the relative performance of optimization algorithms. classic example is the case of smooth, strongly convex functions, where both gradient descent and Nesterov's Accelerated Gradient
2

---

Published as a conference paper at ICLR 2025
(NAG) exhibit linear convergence, but the iteration complexity of NAG is faster than GD by factor of vK, where A is the condition number of the objective function (Nesterov) 2013).
Our contributions can be summarized as follows:
1. In Theorem | we provide complexity lower bound of 52 (A2 for Decorrelated AdaGrad-Norm (which uses decorrelated step sizes and a shared learning rate for all coordinates) under (1 (smo)ssmtthessss and almost surely bounded gradient noise. The proof uses a novel construction of a difficult objective for which Decorrelated AdaGrad- Norm may diverge (depending on the choice of hyperparameter), combined with high- dimensional objective (adapted from Drorí & Shamir (2020)). This lower bound matches the upper bound of AdaGrad-Norm in two out of three dominating terms, and only differs in terms of a. See Section 4 for a comparison between these upper and lower bounds.
2. In Theorem 2 we lower bound the complexity of Decorrelated AdaGraa by Ω (APL3o²> *)= where 7 is hyperparameter. The proof uses novel high- high-dimensional objective for which the algorithm diverges when 2 (())(Lio)). Theorem extends this result for the original AdaGrad algorithm, achieving lower bound of S2 (A LA- While our lower bound for AdaGrad is weaker than for its decorrelated counterpart, this complexity is still larger than the optimal smooth rate in regimes when A or the smoothness constants are large compared σ.
3. In Theorem we consider the setting of (Ly, L1) -mmooohhsssss and gradient noise bounded by affine function of the gradient norm. For SGD with broad class of adaptive step sizes, we show a lower bound that is nearly quadratic in the problem parameters A, L1. This is proven by showing that of the following must hold: (1) adaptive SGD can be forced into biased random walk with a constant probability of divergence, or (2) the adaptive step size is O (1/(AL))) when optimizing function with gradient magnitude equal to e, which leads to slow convergence.
The remainder of the paper is structured as follows. We discuss related work in Section 2 then give the formal problem statement in Section 3 We then present our complexity lower bounds for Decorrelated AdaGrad-Norm (Section 4.. Decorrelated AdaGrad and the original AdaGrad (Section
5). and adaptive SGD (Section 6). We conclude with Section 7
2 RELATED WORK
Relaxed Smoothness. Relaxed smoothness was introduced by Zhang et al.
2020b), who showed
that GD with normalization converges faster than GD under this condition. This inspired line of work focusing on efficient algorithms under this condition. Zhang et al. (220a) showed an improved
analysis of gradient clipping, and et al. (202T) considered a non-convex distributionally robust op-
timization satisfying this condition. Several recent works (Liu et al. 2022; Crawshaw et al. 2023a b) designed communication efffciinnneffiinntt federated learning algorithms under relaxed smoothness. Li et al.
(2024) analyzed gradient-based methods without gradient clipping under generalized smoothness. Crawshaw et al. 2022) studied a coordinate-ve
version of relaxed smoothness, empirically showed that transformers satisfy this condition, and designed a generalized signSGD algorithm with conver- gence guarantees. CChnn et al. (2023) proposed a new notion of a-symmetric generalized smoothness and analyzed class normalized GD algorithms. More recently, few works have investigated momentum and variance reduction techniques within the framework of individual relaxed smooth conditions (Liu et al. 2023) on average relaxed smooth conditions (Reisizadeh et al. 2023).
Adaptive Gradient Methods. Adaptive gradient optimization algorithms automatically adjust the step size for each coordinate based on gradient information, and have become very important in machine learning. Examples include Adagrad (Duchi et al.) 2011 McMahan & Streeter (2010).
Adam (Kingma Ba. 2014), RMSProp (Tieleman & Hinton 2012). and other variants (Loshchilov & Hutter, 2018 Shazeer & Stern 2018). Most theoretical analyses of adaptive optimization methods
are based on the assumptions of smoothness or convexity (Reddi et al. 2018 Chen et al.) 2018 Guo et all 2021). Recently, some works established convergence results for AdaGrad Norm (Faw et al. 2023: Wang et al. 2223)) and Adam (Li et al. 2023) under the relaxed smoothness condition, and all of the convergence rates in these works exhibit higher order polynomial dependence LT.
3

---

Published as a conference paper at ICLR 2025
Lower Bounds. Lower bounds for first-order convex optimization are well studied (Nemirovskil
at 1983] Nesterov] 2013; Woodworth & Srebro, 2017] 2016). The lower bounds of nonconvex
smooth optimization were studied in the deterministic setting (Cartis al. 2010; Carmon et al. 2020
2021). finite-sum setting (Fang et al. 2018) and stochastic setting Drroii & Shamir 2020; Arjevani
a 2023). For relaxed smooth problems, ZZang al. (2020b) and Crawssaw et al. (2022) derived
a lower bound for GD and showed that its complexity depends on the maximum magnitude of the
gradient in sublevel set. Faw et al. (2023) considered the lower bound for normalized SGD, clipped SGD, and signSGD with momentum in the affine noise setting, and showed that these algorithms cannot converge under certain parameter regimes. Crawshaw et al. (2023b) showed lower bound for minibatch SGD with gradient clipping in the affine noise setting.
PROBLEM STATEMENT
3.1 OPTIMIZATION OBJECTIVES
We consider the problem of finding an approximate stationary point of a nonconvex, relaxed smooth function with access to a stochastic gradient. Let A, Lo, L1, 01, 02, o > O. We will denote the objective function as f : Rd R. the stochastic gradient as g Rd = - Rd, and the noise distribution as D, which is a distribution over E. We then consider the set of problem instances (f.g, D) satisfying the following conditions:
Assumption 1. (I) f is bounded from below and f(0) inf f(x) s A. (2) f is continuously differentiable and (Lo, L1) smooohh: For every x, y E Rd with x yll S 1/L::
[V5(z) - vf(w))l S (Lo + L [ - all-
(3) (1,,, E)] = Vf())) for all a E Rd. Assumption 2. For all Rd:
(Bounded-Noise) (0) vf(z)) S almost surely over & ~ D.
(Affine-Noise) 11g(x, f(()))] o + Vf(l) almost surely over & D.
(Bounded-Var) EEWD [1l <) - [/ 0² (Affine-Var) Var) EE-D [1lg(z, {) [ < < + +2
(Subgaussian) BEND [exp(Ilg(2r [) 1
We will denote by Far Lu, L) the set of problems (f.g. g. D) satisfying Assumption and (Bounded-Noise), and by Fanl (A, Lg, L1, d2) 02) those satisfying Assumption Jand and (Affine-ooise.
In this paper, we present new results under (Bounded-Noisee and Affiie-NNoise) though we state the other assumptions for discussion with related work. It is important to note that (Bounded-Noise) is strictly stronger than (Bounded-Var) Therefore, the lower bounds that we prove for Fax also hold for the class of problems satisfying Assumption T and (Bounded-Vayy This is because any difficult problem instance in the former class is also in the latter. An analogous statement for LAffine-Noise and (Affine-Vatt holds by the same reasoning. Our primary focus for stochasticity in this work is (Bounded-Noiss) since this is the standard assumption used by early work on relaxed smoothness (Zhang et al. 2020bla) a).
3.2
OPTIMIZATION ALGORITIMS
We will consider four optimization algorithms Decorrelated AdaGrad -Nomm, Decorrelated Ada- Grad, AdaGrad, and single-step adaptive SGD and their behavior for problems in Fas and Fun.
Decorrelated AdaGrad-Norm We first consider variant of AdaGrad that we refer to as Decorrelated -laGrrd--Nomm.
Dt.
9:>
22 + Σ == 1g.1
4

---

Published as a conference paper at ICLR 2025
where 17 0 is step size coefficient, 9: =c) and & D is independent over t. Notice that the denominator contains the sum of squared gradient norms, as opposed to the coordinate-wel wise operations used in the original AdaGrad. This type of denominator is used in
whose convergence was studied under various conditions in Ward et al. (2020); Faw et al. (2022); Attia Koren (2023); Wang et al. (023)); Yang al. (2024). Further, the
of squared gradients in the denominator ranges from i = -oi=t- 1,, meaning that it does not contain the most recent stochastic gradient gt- This type of decorrelated step size was considered in Li Orabona (2019).
which provided convergence guarantees in the smooth setting (see Table I
AdaGrad and Decorrelated AdaGrad Next, consider two coordinate- wise variants of AdaGrad. including the original AdaGrad and a variation with a decorrelated step size. The original AdaGrad (Duchi et al.
201
defined as follows:
F+++1
J1.
Σ i=
9
where the squaring of is performed element-wise. Decorrelated AdaGrad (Li & Orabona 2019 is similarly defined
L++1 = 2t
g
the only difference from AdaGrad being that the sum in the denominator does not contain the gradient from the current step, so the step size at step t is independent of the stochastic gradient noise at step t.
Single-Step Adaptive SGD Last, we consider class of algorithms that implement stochastic gradient descent with an adaptive step size, but whose step size function only depends on the current gradient. For Rd R, single-step adaptive SGD is defined as:
T++1 2t (gg))
where again g: = g( Ex) and & ~ D is independent over t. At each step t, the update xt+1 x determined completely by the stochastic gradient sampled at step t, hence the name "single-step" However, the step size in the direction gi is computed as an arbitrary function a of the stochastic gradient. This class of algorithms includes SGD with constant step size, SGD with gradient clipping, and normalized SGD; it does not include Adam or AdaGrad.
3.3 COMPLEXITY
Given a problem (f.g. D) and > O, the goal of an optimization algorithm is find an approximate stationary point of f, that is, a point E Rd such that [[V](=)] < We want to characterize the number of gradient calls required by an algorithm to find such point. Since an algorithm can only gain information about the objective f through stochastic gradients, it cannot necessarily guarantee to find an e-stationary point, but it may find one in expectation or with high probability. Denote by }x,} the sequence of points at which the stochastic gradient is queried by A when given (f D) as input. We then define the worst-case complexity of A on problem class F as
F(),F sup min t 2 (La.D)EF
min [ <c) s<t
To summarize, the worst-case complexity T()FF.c) measures the number of gradient calls required by A to find an e-approximate stationary point in expectation, for any problem F.. We also consider the worst-case complexity for finding an e-stationary point with high probability:
Pr min [V][(=))] <c) > 1 16-
T(A,F,C,)
sup min 1 1211 (F..D)EF
Following Arjevani al. 2023), most of our results (Theorems) 22 will provide in in-expectation lower bounds, that is, lower bounds for ((A, Our last result (Theorem 4) will provide lower bounds for T(A, F, e, 6) for any given 8, i.c., high-probability lower bounds. Throughout the paper, ((-) and ((-) omit universal constants, and (c), 22-)) and é-) omit universal constants and factors logarithmic in terms of problem parameters A, Lo, I,,, 31, F2 a, and target gradient norm
5

---

Published as a conference paper at ICLR 2025
4 DECORRELATED ADAGRAD-NORM
Our first result gives a lower bound for Decorrelated AdaGrad-Norm, which shows that the complexity has quadratic dependence in terms of problem parameters A, L1.
Theorem 1. Denote F
(A, Lo, L), and let algorithm ADaN denote Decorrelated
AdaGrad-Nora (Equation with paramelers v > 0 and 0 < S (AL1). Let 0 < S
O min { (VLLo. VALrY, AL1)) 1f IfAL 2 Lo. then
AA ALgo² log(1 + 0² 022/79)
+ A
T(ADNN ([ADNN.Fee)) F, Ω
el
The proof is given in Appendix A Before giving a sketch of the proof, we make a few observations about the result. (1) The lower bound contains the term A which is the optimal complexity for a first-order algorithm in the sm-sohhhh non-convex, stochastic setting (Arjevani et al., 2023). This means that Decorrelated AdaGrad-Norm requires at least many iterations to solve the current problem as any first order algorithm requires to solve the smooth counterpart. (2) The dominating term cannot
quadratic in A, L1_ Therefore, under relaxed smoothness, Decorrelated AdaGrad- recover the optimal complexity of the smooth case, as one might hope. (3) In the deterministic case (i.e., 0 0), the complexity is A 1 -2, which is still quadratic in the problem parameters A, Ia and does not match the complexity achieved by deterministic GD in the Lg-smooth case, i.e., Agge 2, (4) This lower bound for Decorrelated AdaGrad-Norm matches the upper bound of AdaGrad-Norm in two out of three dominating terms. The dominating terms of the upper bound of AdaGrad-Norm from Wang al. (2023) (see Table 1) are
A A2
ALoo²
6
+
72
(5)
The first two terms of this upper bound match our lower bound up log terms. Note that this result (Theorem 8 from Wang et al. (2023)) uses (Bounded- -oounded-Var), whereas we use (Bounded-Noise)) However, their upper bound still applies for the stronger (Bounded-Noiss) and our lower bound still applies for the weaker (Bounded-Vai)
The gap between our lower bound and this upper bound is the third term (due to the noise o), which means that either (a) the upper bound can be decreased; (b) the lower bound can be increased; (c) Decorrelated AdaGrad- differs from AdaGrad-Norm in its dependence on the noise o; or (d) the gap is caused by the difference in noise assumptions.
Lastly, the condition AL? > Lo for Theorem 1 Jensures that (Lo, 11)- -smoothnees does not degenerate to L-smoothness, Indeed, Lemma 3.5 of et al. (2024) implics that [[Vf(z)] < O(AL,) for every with f(x) I f0), so [()] S Lo + La V S O (Io + ATR). Therefore, if the condition ALद 2 Lo fails, then any objective ʃ which is (Lo, Li)-smooth is also ((L)--smoohh in a sublevel set containing the initial point. We also require upper bound on the stabilization constant:
7 I O(L))) which covers all practical regimes in which 7 is chosen a small constant. In Appendix we show that this condition can be removed in the deterministic setting while recovering the complexity lower-bound ε A(AaLee -2).
4.1 PROOF OUTLINE
The proof of Theorem I follows two cases, depending on the choice of the parameter n, If 2 1/L1, then the algorithm can diverge on a fast growing function. On the other hand, if S L1L then the algorithm converges slowly on function with small gradient. This proof structure is similar to previous lower bounds under relaxed smoothness (Zhang et al., 2020b Crawshaw et al., (022). but our result requires significantly different constructions due to the structure of AdaGrad updates, and since previous bounds only achieve e dependence, whereas we show e dependence.
Divergence when 7) 2 1/L1 We want the update size || - æ; to be lower bounded by a constant, but the step size decreases over t due to the sum of squared gradients in the denominator. Intuitively, this means that the gradient magnitude ||gell should increase with to offset the decreasing step size. However, faster growth of [|g, causes faster decrease in the effective step size. We can balance these two effects and force the trajectory to diverge with a properly constructed objective function and a sequence of gradients satisfying ||g:|| θ ((t log I)'), which is executed in Lemmal

---

Published as a conference paper at ICLR 2025
SA
X0
X1
X2
X3
X4
w (m))=Al
(a) Graph of (xx) = Lg (exp(L<[>=)) [1|2a 1). (b) Trajectory from Lemma
Figure 1: Objectives from Lemma m (v') (6')) - log (1 (1+ A47
Lo
Lemma Suppose that AT, 2 Lo, 1j L. and S ((1ATT)) Then there exists a problem instance (f.g.D) (A, Lo. L1,0) such that [Vf(=)]] 2 for all t 2 0.
The trajectory of the algorithm analyzed Lemma is informally pictured in Figure lb
The objective
function is piecewise combination of copies of the function ei(x:) Lg
2 (exp(L1 [ L1 |a 1).
which is shown in Figure la v is constructed to satisfy |v) Lo + L 1 (x)) for all so it
grows as quickly as possible under (Lo, L )smoothtsssss. As shown Figure Tb at each step the algorithm receives gradient 9r and "jumps"
valley to reach new point with gradient g++1-
In order to achieve this jump, we need the sequence of gradicnts to satisfy
nggel
4
T. I119++1)) log
1+
V22 E1= K4
L1
Lo
This recurrent inequality is tricky since the magnitude of each !gel is constrained not just by the history flas1tice. but also by the future 91-1. We show that this requirement is satisfied if gr
(((1+) [ log(1 Lo 1)))* ALi). and that this sequence of gradients can be realized by an objective function Fas Lo, L1,
Slow convergence when y < 1/L1 In this case, previous lower bounds (Zhang et al. 2020b Crawshaw et al.) 2022) consider one-dimensional function with deterministic gradients to show complexity of 92 LA 2). To achieve e dependence, we consider a nigh-dimensional function with stochastic gradients (adapted from Drori & Shamir (2020)) for which the first partial derivative V, has magnitude and the stochastic gradient noise affects coordinates with index greater than 1. Since the same learning rate shared by all coordinates, the noise later coordinates will decrease the learning rate for the first coordinate. Combining with v S 1/L1 leads to the desired complexity.
Lemma Let T O (A2 -4 ALgoge A L and suppose d 2 T and S O (min { (VA V A ). Ifn S 1. then there exists some (J.g. Fas (A, Lo, In,a) such that (x;)) = for all 0 t
See Appendix for details on the objective function, stochastic gradient oracle, and analysis of the trajectory. The theorem is then proved by combining Lemmas and No matter the choice of the parameter 7), the algorithm will find e-stationary point within the first T steps.
ADAGRAD AND DECORRELATED ADAGRAD
Here present lower bounds for Decorrelated AdaGrad (Theorem 2 and the original AdaGrad (Theorem 3) Both lower bounds are quadratic in A, Lo. but our result for Decorrelated AdaGrad has stronger dependence than that of AdaGrad. This discrepancy is further discussed below.
7

---

Published as a conference paper at ICLR 2025
Theorem 2. Denote F Fa, Lo, o). and let Apa denote Decorrelated AdaGrad (Equation) 2 with parameters 7, > O. Suppose 0 6 < Ö 0min {AT1, VAI.o))) Then
L2
A²L30²
F,t) 20
7P61
7p log2
AL. (1+
To
Theorem 3. Denote F= = Far Lo, L1, O), and let Auda denote AdaGrad (Equation with
parameters B, > O. Suppose 0 < c Ö (min {AL1, VDL10}) 18 S o, then
A
A
T(Auda; F,6) 20
e² log
2
(1+
AL; Lo
The proofs of both theorems above are given in Appendix B The results above exhibit several important properties. (1) As in Theorem | the dominating term A L of the lower bound in Theorem 2 is greater than the optimal complexity ALooRe of the smooth case (up to the choice of %f, which is usually a small constant). In fact, the dominating term is quadratic A and Lo, so the complexity of Decorrelated AdaGrad in this setting is fundamentally larger than the optimal complexity of the smooth counterpart. Unlike Theorem [ Ln does not appear in the dominating term of this bound. (2) Compared to Decorrelated AdaGrad, our bound for AdaGrad loses factor of o²/ 0//n. This arises in our construction from the fact that, at step f, any noise present in gr will also appear in the denominator of the update, that the update size of AdaGrad is not as sensitive to noise as the decorrelated counterpart. Still, in regimes where A, Lg are large compared to o, our complexity lower bound of L is larger than the optimal complexity of the smooth case. This shows that AdaGrad cannot recover the optimal complexity of the smooth case in all relaxed smooth regimes. (3) The lower bound of Theorem D
diverges to do when the 7 goes to O, which confirms the conventional wisdom that non-zero stabilization constant is necessary in practice.
5.1 PROOF OUTLINE
The structure of the proof is similar to Theorem T (outlined in Section 4. but we can achieve di- vergence for Decorrelated AdaGrad under the weaker condition 1) 2 O mmin (T/(Taa), (e/(Tor)) using a novel high-dimensional construction that takes advantage of the coordinate-wise learning rates of Decorrelated AdaGrad by injecting noise into one coordinate per timestep. When 1j is smaller than this threshold, convergence is slow for a oineeinmnsional, linear function with slope c.
(e/(Lio),ne/(LLor)) Divergence when 7 θ (min (t/(Lro), (L)orr)) For any d 2 1, we consider the objec-
tive function fxx Ad Ei=1 ((2,,c)) where is as defined in Section 4.1 Letting m 1, (0))-(()= = 1 log [1 Lic
Tio consider the initialization ay = mc1, which by construction satisfies [[V[()))]| For the initialization, all of the coordinates besides the first one already their optimal values, and the partial gradient for these coordinates is zero; the stochastic gradient injects noise into the second coordinate, so that go = (=0) + 0e2 = Ee) + reg. Based on the magnitude of this guarantees [æ1 e2)l 2 m, and consequently ff(x1) > | e2)) 2 & (m) c. another point whose partial derivative is larger than c. This process continues with f: at each step f. the stochastic gradient noise affects the coordinate indexed (t + 2), so that this coordinate of the iterate jumps from 0 to point with magnitude at least m. This guarantees that the algorithm does not reach a stationary point for d steps, and d can be arbitrarily large. An important detail of this process is that the wordinate-wiist learning rates ensure that the length of each "jump" (i.e.. the per-coordinate update size) does not decrease with t. This argument is made formal in the following lemma.
Intuitively, the size 17 causes the second coordinate to "jump" from the minimum at
Lemma 3. Let 0 < E < O(LL)). In 2 Ω 1 log 1 + 4x) 4n then any T 2 1, there exists some f E F such that Decorrelated AdaGrad satisfies V f 2 efr all 0 < t T
Similarly, in 2 2 ( log (1+ 4,r and γ S a, then for any T 2 there exists some F such that AdaGrad satisfies [[V for all 0 < S15T-1
8

---

Published as a conference paper at ICLR 2025
Notice that the requirement for AdaGrad in Lemma ils stronger than that of Decorrelated AdaGrad. As previously mentioned, this happens because the size of AdaGrad's 's update is less sensitive to stochastic gradient noise than Decorrelated AdaGrad.
Slow convergence when rj S θ (min { ye/ (L) In this case, the desired complexity follows by analyzing the trajectory of each algorithm one-dimensional, linear function with slope equal to e, similarly to existing lower bounds (Zhang et al. 2020b] Crawshaw et al.) 2022).
Lemma 4. Let O
O (min {AL,, ALLT))) If some (J,9, D) E (A,
L2n L,d log 1 Le then there exists
(A,LLn Lo, O) such that Decorrelated AdaGrad satisfies VV (xx))) 2 for all t 2A2L 2 + A L2 2).
Li log (1 Lo ) then there exists some (f,g, D) Far Lo, In, such
Similarly, if O that AdaGrad satisfies || f (2+))l 2 e for all S (AALiE + A²
Theorems and can then be proven by combining Lemmas and
SINGLE-STEP ADAPTIVE SGD
In this section, consider single-step adaptive SGD (Equation 4 Our lower bound shows that, due to relaxed smoothness and affine noise, any algorithm of this type will incur a higher-order dependence on A, L1 The results below are stated in terms of constants 7 and a function which are defined in terms of 5 and 02 (see Appendix C.I for the definitions). In the discussion following the theorem statement,
specify the limiting behavior of these constants in terms of 02 6.
Theorem 4. Denote = b()))) and suppose G 2 01. Ler 0 < e min { [1: 2 "2-1' V2
G G-oi VALo
Let algorithm Asingle denote single-step adaptive SGD (Equation + with any step size function
Rd IR for sufficiently large d, and let F = Far (A, Lo, I,, 1 02). Ifo2 2 3, then
ALoo? + (AL1) o 7a
T(Asingie: F,c,8) 20)20
2-2
Otherwise, if1 02 < 3, then
(A Aooo? +
70770-74
T(Asingle, F, c, 2 5
2-74 (02 - 1)2
02 -
The proof is given in Appendix Below, we specify the terms 7t in regimes of 02-
Large d2 For 02 > 3, the error terms 71, 72, 73 satisfy: 71.33 θ (log (1 + ((2/3,))) and
1/2 = θ (oz)). where ((p,5) is defined in Equation 25| Lemma 15 shows that lim, ((, 6) =
for all p E (0, 1). so when + O, the lower bound approaches
ALoo²
A
8(1/22)
Ω
e2log (1+
AL?
AL
Lo
In this limiting case, the complexity has nearly quadratic dependence on A, L1, but only in the non-dominating term. Still, we emphasize the generality of our result, which applies for any adaptive SGD algorithm whose learning rate only depends the current gradient, and shows that adaptivity based on the current gradient alone will incur higher-order dependencies on A, L,-
Small d2 Existing lower bounds that utilize similar constructions of biased random walk under affine noise (Faw et al. 2023 Crawshaw et al. 2023b) require that d2 be bounded away from 1. Our Theorem
4 covers the case that 02 > 1, albeit with lower bound that approaches 0 when 02 - 1. The error terms 74, Yo, depend only on ó, σ2 and satisfy: lims lim 76 O, lims 7o 0. Note that 7o does not depend on 8, and 75 1. Therefore.
O, limog--11 =
letting 5 + 0 yields lower bound of
ALoo2
AL101(02 - -1)
Aln((2 -1) 1-76
e² eoog 11
AKi
σ1
L

---

Published as a conference paper at ICLR 2025
Since 1 1 7 0 as 02 - 1, the second term in the lower bound goes to 0 when 02 - 1. This shows that our construction relies on 02 bounded away from 1, and raises the question whether a single-step adaptive SGD algorithm can converge without quadratic dependence on A, L in the regime d2 < 1.
6.1 PROOF OUTLINE
The full proof of Theorem 4 can be found in Appendix C and we provide a sketch of the main ideas
here. The proof of Theorem has three main steps:
Step the step size function a does not satisfy S a(g) - (1/( for every g with
|g|| [e, 01 + (02 + 1) then Asingle will diverge for some exponential fexp. proven in Lemma The difficult objective is constructed similarly as in Lemma] T pictured in Figure 1b
9
Step 2 If there exist gl, 92 E IR such that g2 cgi for some < O, and || < ( I]. but
(g1) 1l || 2 ((a(g2))lgg))) (i.e,, a "tricky pair", see Definition 1 in Appendix C.I. then there is some (f.g. D) F for which Asingle will diverge. The construction is based on the idea that gı and g2 are stochastic gradients at a given point, where 92 points towards the minimum and 9i points away from the minimum, but (g)) is close enough to agg)) that Asingl has nearly equal expected movement in each direction. In this case, the sequence {m²} follows a biased random walk that will diverge with probability least 6. This argument is made formal in Lemma
I0
Step 3 If neither of the above cases hold, then (g)) S (1/ ([gl)) and there do not exist any tricky pairs. The non-existence of tricky pairs means that (x(g) |gg] grows sufficiently fast in terms of |لوا| when |g||| E [E,01 + (02 + 1) 11] also growing quickly, must be that (g)) is small whenever ||g| is small. Lemma 11 formalizes this idea to show an upper bound for (g) whenever |[9|| The final bound follows by analyzing
]. In order for to respect a<g) I Ô (1/(Li]))))) while
the trajectory of Asingl for a piecewise linear objective with gradient g satisfying ||g| = e, since the
convergence rate is inversely proportional to (gg).. (Lemma 12
7 DISCUSSION AND CONCLUSION
It has been stated in the optimization literature (Woodworth et al. 2018 2021) that a complexity lower bound should not be interpreted as an unquestionable limit of performance, but rather as a tool to examine the assumptions that led to the bound and explore alternatives. In this spirit, we consider the implications of our choice of problem formulation.
First, the optimization problem investigated in this paper (i.e., problem instances satisfying Assump- tions [ and 2 may not be a sufficient theoretical framework to explain the behavior of adaptive optimization algorithms in deep learning. A complete explanation of this type may require addi- tional assumptions about the structure of the objective functions, such as enforcing a neural network architecture or particular data distribution.
Also, the negative results presented in this paper may be bypassed by algorithms other than those we have considered. In particular, it is possible that higher-order polynomial dependence on problem parameters can be avoided by more practical algorithms such as Adam and Adam W. Presently, it is unknown whether these algorithms can recover the optimal complexity of the smooth case (as does SGD with clipping), or if they behave more like the AdaGrad variants considered in this paper.
Limitations The most important limitation of our work is that our strongest lower bounds (Theorem 2 are obtained for decorrelated variants of AdaGrad, which are not commonly used in practice. We view these decorrelated methods as starting point for lower bounds of adaptive algorithms under relaxed smoothness, similarly to early [i & Orabona (2019) showing upper bounds for decorrelated versions of adaptive algorithms. Also, our result for the original AdaGrad (Theorem 3 is weaker in terms of the dependence on It remains open whether this result can be improved, and whether there is a fundamental difference in the complexity of AdaGrad compared to the decorrelated variants. Further, even if the same complexity can be achieved by the original AdaGrad, the existing upper bounds do not exactly match our lower bounds. Therefore. remains to exactly characterize the complexity of AdaGrad (and its variants) by providing matching upper and lower bounds.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like thank the anonymous reviewers for their helpful comments. This work is supported by the Institute for Digital Innovation fellowship, a ORIEI seed funding, an IDIA P3 fellowship from George Mason University. Cisco Faculty Research Award, and NSF award #2436217, #2425687.
REFERENCES
Yossi Arjevani, Yair Carmon, John Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathemalical Progrumming, 199(1-2): 165-214, 2023.
Amit Attia and Tomer Koren. SGD with AdaGrad stepsizes: Full adaptivity with high proba- bility to unknown parameters, unbounded gradients and affine variance. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp- 1147-1171. PMLR, 23-29 Jul 2023. URL Dttps://procecingg www.oeeeeddngg.....ee.........ee www.ss....rrppppmmmmmmmmmmm wttpp/ppeeee//////ttta222222
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1-2):71-120, 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, (55112)::15-3555 2021.
Coralia Cartis, Nicholas IM Gould, and Ph L Toint. On the complexity of steepest descent, newton's and regularized newton's methods for nonconvex unconstrained optimization problems. Siam journal on optimization, 20(6):2833
2010.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint 1rXiv:1808 2018.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smen nonconvex optimization is as efficient smooth nonconvex optimization. arXiv preprint arXiv:2303.0285: 0285444 2023.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35:9955-9968, 2022.
Michael Crawshaw, Yajie Bao, and Mingrui Liu. Episode: Episodic gradient clipping with periodic resampled corrections for federated learning with heterogeneous data. In The Eleventh International Conference on Learning Representations, 2023a.
Michael Crawshaw, Yajie Bao, and Mingrui Liu. Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. In Thirty-seventh Conference on Neural Information Processing Systems, 2023b. URL https::/
net/ Nia.mmmo1oY__GGGG33000
Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Leurning, pp. 2658-2661 PMLR, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Rick Durrett. Probability: theory and examples, volume 49, Cambridge university press, 2019,
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non non-convex optimization via stochastic path- inteerrtttrr differential estimator. Advances in neural information processing systems, 31, 2018
Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pp. 313-355. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2025
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. arXiv preprint arX1w:23022006570, 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341-236) 2013.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianhao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint arXiv:21/2.03452 2021.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2014.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 77343-17366 PMLR, 2023.
Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of adam under relaxed assumptions. arXiv preprint arXiv:2304. 13972, 2023.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd international conference on artificial intelligence and statistics, pp. 983-992.
PMLR, 2019.
Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication- efficiinn distributed gradient clipping algorithm for training deep neural networks. Advances in Neural Information Processing Systemx, 35:26204-26217, 2022.
Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou, Near-optimal non-convex stochastic opti- mization under generalized smoothness. arXiv preprint arXiv:2302.0603, 2023.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, In International Confer- ence on Learning Representations, 2018.
Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. arXiv preprint arXiv:1002.4990 1002.4908, 2010.
Arkadii Nemirovskii, David Borisovich Yudin, and Edgar Ronald Dawson. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. International Conference on Learning Representations, 2018.
Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprini Stti:2303300888.. 2023.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pp. 4596-4604. PMLR, 2018
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5 6.5-rmsprop, coursera: Neural networks for machine learning. University of Toronto, Technical Report, 6, 2012.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 161-190. PMLR, 2023.
12

---

Published as a conference paper at ICLR 2025
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes. Journal of Machine Learning Research, 21(219):1-30, 2020.
Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex optimization. 2017.
arXiv preprint
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication, arXiv preprint wrxiv:2/02.01583, 2021.
Blake Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in neural information processing systems, 29, 2016.
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models. lower bounds, and gaps for parallel stochastic optimization. Advances in neural information processing systems, 31, 2018.
Junchi Yang. Xiang Li, Ilyas Farkhullin, and Niao He, Two sides one coin: the limits of untuned sgd and the power of adaptive methods. Advances in Neural Information Processing Systems, 36, 2024.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511-152211 2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: theoretical justification for adaptivity. International Conference on Learning Represen- tations, 2020b.
13

---

Published as a conference paper at ICLR 2025
A
PROOF OF THEOREM [
Lemma (Restatement of Lemma
Suppose that A 2 Lo, and 11 2 t.2 and
n
(6)
8 log [ 48
ALI T/p
Then there exists problem instance () Far Lo, In, 0) such that [V ATa for all t 2 O.
Proof. The difficult function f will be piecewise linear and exponential, and constructed in such a way that the gradients V (ax) increase at rate of z t'. The rapid growth rate of the gradients ensures, even with the update normalization, that the update size | æz increases every step.
Recall the function &b R + R defined as
Lo vbxx) (exp(Tn]<o)) Tn 1),
I
with
Lo (exp(L1|x() 1).
(x) sign(2 (r)
L1
straightforward to verify that & bounded from below by 0, continuously differentiable, and (Lo, Li -smothh.
The difficult function I will be constructed in terms of the following:
(1 + +)))
gt 576(1+ + 1)
1+
AL
To
(1+
L19h
m4
log
L
Lo
n9t
l
7>2 ,2 + 21-0
01:00 96
d, = Σ 4
1=0
For cach t 2 0, define de : R + IR as:
bbs - m²)
I S m + +1++1
(x()) = g0
m2+1) + (mm++))
E (m: + m4+1. bs 2m(41)
-- 4 + m441) 20b(m++1) + ge 3m m.)
l, 2m4+1
These functions constructed satisfy (0( 15 (-m+) - gr and (b((e) v/ ( 9-+1- To see that this definition makes sense, we should show that l 2m4+1 2 my + Mc+1, that the boundary of the first piece is smaller than the boundary of the third piece. This is equivalent to: & 2 my + 3m Using AL; 2 Lo. the sequence is increasing, and consequently so is m.- Therefore suffices to prove
4 2 4ma+1
79c
4 log
L1gh+1 La
[
22 + Σ ==
L
We will prove Equation 7 separately for the cases
0 and 2 1.
14

---

Published as a conference paper at ICLR 2025
Case t= 0. In this case, the desired condition is
79o
log
[1+
Ligi
L1
Lo
The RHS of the above inequality can be bounded as
4
Lig1
L1
Ali
log
1
4
log
1 +
1152 log
1
Ahn
L1
Lo
Lu
Lo
4
AL
AL7
log
+ 1152
log
1 +
L1
Lo
Lo
(1)
ALZ
2
S L
log
+ 2304
Lo
(18)
AL2
log
+ 48
T.1
To
(18)
AT1
where (i) uses log < for x > 0, (ii) uses log(1 + x") log((1 + +))) S n log(1 + x))
for all x >> 0, and (iii) uses the assumed condition on (Equation 6
This concludes the first case.
Case 1 1. We first simplify the denominator y (Equation implies that 7 S nAL2 7L1900
722+ 1 g. First, the assumed condition on
1-1
Σ
9 1 + Σ o s (1 1
Σ
9 S 2n
1
Σ
9
==
1=0
1=0
1=1
Also,
t-2 2
Σ 1=0
c < (t - 1)gk
AL?
-1)1
2(t-2)
= (t - 1) 576(t - 1) log
1+
(t
2
Lo
(1+ ALP
2(1-2)
S (t - 1) 576t log
2217
Lo
2(t-1)
576t log
1
))
A
Lu
-2-1.
Therefore 72 + Σ 1
ot < 4n² Li So the LHS of Equation 7 can be bounded
i=
1/9b
gr.
2L 2L19t-1
72
1= g4
(576(L- + 1) log
1
AL?
(1+ 13)
AL
Lo
2L1
(576t log
[ (1
A6R ))
t-1
ALI
576(t + 1) log
(1+
A17
(t
+ +))
1-1
288(1 + 1)
AL? (1. (1++1)
Lo
log
+
L
Lo
576/ log 1
4L9/)
288(1 + 1)
AL? (1 + 1)
log
1
(8)
T1
Lo
15

---

Published as a conference paper at ICLR 2025
The RHS of Equation 7 can be bounded as
4
log 1
Ligh-1
)
4
log
1
ALi Lu
577(t (0 log
1+
Al2
(t 2) )) (t7)
)
L
Lo
L1
Lu
( 1(t + 1)
AL?
1/(++1
ALi (t 2)
log
1 + 576
(t+ 20g
1+
L1
Lo
Lo
(58) 4(1 + 1)
AT
141/((+1)
log
1 576
(t 2)²
1
Lu
(10) 4(t +
$
log
+ 576
(t (t+2)²
11
Lo
(00)
8(1+1) +11 1)
AL
log
1 + 24
(t + 2)
L1
Lo
2 8(t +1
AL3
log
1 36
(t + 1)
I
Lo
where (i) uses log(1 + x²) < log((1 + x)") n log(1 + r) for x > 0, (ti) uses log(1 + +x) S x
for all x > O, (iti) uses AL7 2 Lo, (tv) again uses log(1 + x²) S n nlog(1 + r), and (v) uses
++ 2 < 2 + 1) since 2 1. Further,
4
log
++
Lise11 Lo
8(1 +1)
log
1+
AL?
(t + (t) + 1lgg(37)
11
L1
Lo
8(t +
AL3
log
11
(t+ 1)
+ 8lggg + 1)
L
Lo
(3) 8(1 + log(33))) +1)
1+ AL3 (t (t+11)
log
L1
Lo
288(t + 1)
AL? (t + +1)
log 1+
(9)
L1
Lo
where (i) uses log(1 + ab) < loog((1 + + + b)) < log(1 + a) + log (1 + b) for all a. > 0, and
(ii) uses ALद 2 Lo and t 1. Combining Equation 8 and Equation 9 proves Equation 7
This proves that the definition of o, makes sense for all l. We can finally define the difficult objective follows:
i(x)
f(x) = 03(x( - dr(s)) +
Σ
di(li).
1=0
where
max (t 2 0 de I x
x 220
j(x)
00
I < 0
With this definition, f essentially piece-wisd wise function, where each piece is an interval [d,, de+1] whose function value is a translation of d, f is informally pictured in Figure of the main text. Notice that f is continuous and differentiable within each piece. At the boundary of each piece.
t-1
lim f(x)= = lim de(x - dz) + Σ (1(4.) x-44
1=0
t-1
1-1
= :di(de+1 - de) + Σ
(bi) =b((E))
+ Σ
(1(l)) = Σ (G))
1=0
1=0
1=0
lim f(x) = lim
00+1(x - de+1) +
Σ
di(ls) (0) + Σ dells) = Σ ((())).
z-
z-1di-
1=0
1=0
16

---

Published as a conference paper at ICLR 2025
Also
lim (x(x) = lim 61( - de) = 0/(d++1 - -d) - oi(,,) = -4++ 2-24 x-
lim (z) lim 0441(00 (or d(+1) (0) 91+1-
2-20++1 x=
Therefore / is differentiable everyyher.. Also.
[-1 + Σ du((b))
inf [(x)
inf 120
inf =c(O.t)
(c(x)
inf inf (x(x) O.
#
1m0
The initial point z0 0 satisfies
f(xo) = 6o = (b(--o)) = 90
Lo
L100 Lo
90
log
1+
5
L1 L
L
Therefore ((xo) inf, f(x) < A. Since each Φi. is (Lo, Li >smomhhhh, so is
We will use a stochastic gradient g. D for this function which always equal to the true gradient, so that the noise conditions trivially satisfied. Therefore ( D) (A, Tap, I1, 0)-
Now, consider the trajectory when starting from the initial point To = O. We claim that 3; = de for all & 0, which we will prove by induction. The base case 0 holds by construction. So suppose that V; = di for all 0 < i < t. Then f'(x;) = (',,) = -9: for all i. So
2+ Zt
(x))
d, +
n9t
de 4, dr+1.
2 + E.D (f(x))))
722
9
This completes the induction.
Therefore, for all t 2 O, we have (xx 9: 90 = ALI
The following lemma uses a difficult objective which is adapted from Theorem 2 of Drori & Shamir (2020).
Lemma (Restatement of Lemma
Let
A2
ALood (og@loog(11 + 0² 2/72)
A
T = 1=1+
144c4
24c
14422
and suppose d 2 T and S min
VLL 1 ALI j. If < +
then there exists some
3
(f,g, D) E Fal Lo, L1, o) such that [V for all 0 s TT--1
Proof. Let d 2 T, and define f: + R as:
f(z) clz, Σ h1(( e)),
where
La 2
x
h₂(x)
(r a,)) + La a
x [g a.
La
4 a²
[x] > a;
0; = 0,0
1
a,
7g² + 2) 02)
17

---

Published as a conference paper at ICLR 2025
To that f is (Lu, L1)-L1ssoolll smooth, notice that each h, is sm-sth..h. Therefore, for any 2, y R
[V(x) - [ -vi(y)) +
Σ (M)) -(((xi))
2 Σ (x) y:)
L x - y11..
Therefore f is smooth, and consequently is also (Lo, smoothh We will also define the following stochastic gradient for f:
F(x,E) (v)()) + (2C
1))e(()))
where
(T j(z) (min (2sis (2x, e.) 0}
(x, ex) # 0 for all i with siisd d otherwise
This oracle is defined so that the stochastic gradient noise at step & only affects coordinate t + 2 (this will be shown later). Let be the distribution of ç, defined as P(g = 0) P( 1) With this definition, the stochastic gradient F satisfies
E[F(w, <)] V f())
[f <) Vf(=)]] S a (almost surely).
Therefore, all of the conditions for (f. F, E (A, Lo, L1, a) are satisfied other than the condition
that f is bounded from below and f(x)) inf f (xx) I A. This condition will be addressed the end of this lemma's 's proof.
Now consider the trajectory when optimizing from the starting point 3% We claim that, for each 0 < L < - 1, the iterate æ, satisfies the following conditions:
(x), e1)
Σ 1=2
(10)
(ax,, eş)l új for all 2 < S1+1 (xx,e))
(11)
for all j 1+
(12)
We will prove this claim by induction. The base case the claim holds for all 0 < < t. Then for each such i,
holds since Tp = 0. So suppose that for
some 0 < t < T
V Vif()))=
V,f(x;) = (1, o,) (1) (a
(385)
for all 2 S 1i+1
fx,( (,, e,) (0
for all ii+1,
where (i) uses Equation 11 from the inductive hypothesis together with the fact that Kz(a;) = (-j;) = 0, (ii) uses Equation 12 from the inductive hypothesis, and both (iii) and (iv) use the definition of hy. Therefore fz. ce1. Also, j(x) = -i+2 2. From the definition of the stochastic gradient oracle,
F(x,, {.) ((x + (25, - 1)
cei (2E, 1)0e
Therefore, the update from I, to Itzz only affects coordinates with index and index t + Further, the above implies (x)). e" a² Therefore, the effective learning rate of the algorithm at step t is
7h
322 + i(e2 + ac+2.
1/2 + 1/-0 F( 12
18

---

Published as a conference paper at ICLR 2025
We then verify the inductive hypothesis for step 1 by considering the coordinates of 2
(1) = (1r 1/t Et)), Et),
(at, e1) (1(F((rr: Er), e1)
(Bt, e1) 504+2
++1
Σ
0t
604+2
E=2
[+2
where (i) uses Equation 10 from the inductive hypothesis, and this completes the inductive step for separately consider j S t + and j = + For j t 1,
Equation 10 For Equation
(zt, e,) - (F k.), e = (xx e;)r ,x,,,, " aj.
[x ey>l
where (i) uses Equation
11 from the inductive hypothesis. For = 1.
( e442)
(Ii, ex+2) - ne (F Et), e(+2)l
aH = a4+20 = a++2
where (x) uses Equation
12 from the inductive hypothesis. This completes the inductive step for 2 we consider j > 1
Equation
For Equation
(g)+1, = (xx,, - -m (F)F =0
where the last equality uses Equation 12 This completes the inductive step for Equation 12 and consequently completes the induction. As a result, we have that fz,)), = for all 0 S t - 1.
The only remaining detail is whether the objective f satisfies the condition f(x0) inf f(x) S A. Actually, f does not satisfy this condition because f is not even lower bounded, due to the linear term c/x, c1). Similarly Drori & Shamir (2020), we instead argue that there exists a lower bounded function f that has the same first-order information as f at all of the points æ, for 0 < t $ 1. this happens, then the behavior of A when optimizing f is the same as that of A when optimizing f. so the conclusion fxx))l = still holds. Specifically, we need f which is lower bounded and that satisfies:
v((.)) (s()),, f(x:) (ax)
for all S t S T. The existence of such an f follows immediately from Lemma of Drori & Shamir (200)), and this satisfies
3c²
inf f(x)
min f(z:) 0StST-1
2Lo'
so that
3e²
f(xo) inf f(x) S
max -f(x)).
(13)
2Lo
0S1ST
-1
Recall that ((x)) For all 1 12, can write each -(x)) as:
-f(x)) -E(x, e1)
Σ h 11 ei))
++
++1
i
Σ
h4(a;)
Σ h2(0)
i=++
1+1
Lo
[+1
4 1=2
122
L00
=1
2
(14)
2 + i(22 + σ2)
4
-2
ile2
+ 0z)
i=0
S
S2
19

---

Published as a conference paper at ICLR 2025
where (t) uses Equation 10 Equation
11 and Equation 12 and (ti) uses the definition of h4 We can
bound S1 as follows:
1
1
1
S E
+
V + i(e2 +
7
V>
+ iie² +
1=
i=
1-1
1
dr 1
1
1)
< 7
+
du
0
1/2 x +
E² 02
Vu
1
2
(v + (6- 1)(e2 + 0z) -?)
+
2
o
(t + 1)(2 + 02) +7
=
+
2 0
(V (t 1)(62 +
122 + (1- 1)(e² + oz) +7
1
2
(1-1)(e+ 000
1
2(t -1-
+
2 + 0² V72 + 1)( + 02) +7
?
V22+ + (t 1) + 02) +
1
2(t - 1)
1 2
< + - 1) +
(15)
7 ve +
where (1) uses the substitution u 72 + xx2² + 0²). Similarly for S2:
E-1
2 1"
S2 S = Σ 72 + i(e2 + 02)
dx
Jn +
+ +x(e2 + +02)
1
)++((+++0"))
1
1
12+ + 1(62 + 02)
du 2² 02 log
2 + 0 42
u
72
1(62 + +02)
l02
log
1+
2
log
1
(16)
2 0
72
2² 0
72
where (i) uses the substitution u =2 + x(c + 0²). Plugging Equation 15 and Equation 16 into
Equation| 14
Loo² log
(1 [1 lo? 73
(1
2/1 -
-f(x)) 5 2
172
17 4(E2 +2)
7
V2 0²
Loo2 1 1
82
2/T
7z
S 2
Ve
1(62 + 02) 1
"1
We can decompose 7 1 + T2, where
221302
A
A log(1 + 0² 2//2)
Ti
T2 =
144c4
144
24c
Then -1- < [ + so so
Loo log (1+ g2)
TTT
202
-f(x)) 562
Ve + d2
7
Vea 402 "
4(e2 +
(17)
D
D2
20

---

Published as a conference paper at ICLR 2025
We can bound D2 and D2 separately:
2
2c 2
D1
Ve V22
6
/T2
+
21
live +
(
A
VT
11 Live +
26
221302
L LIVE+to' 0²
144c4
144
(10)
2
AALO
AL1
6
Live + +
12e2
12c
A
Aa
Ae
6
6V
2
+
0²
6V
o²
A
A
A
A
6
where (i) uses the condition 1/ S 1/L,, (ti) uses the condition < 78 VaVaS (tit) uses the
definition of Ti, and (iv) uses Va + V Vb. Notice that D2 quadratic function of n with negative leading coefficient. so D2 is upper bounded by the vertex of the corresponding parabola, i.c.
ax² br -b>/22 /2a when 0. Therefore
2c VT
2
2(c²
+
D2 <
V2 + 0²
Lno log 1
0² 7.
8ct
T2
Loo log
1 +
0²
Sc1
A 2 log(1 + 02//2)
Lao2 log 1 1
02
24c
3
7z
where (1) uses the definition of T2.
Finally, plugging back to Equation 17 yields -(( <
2A
and plugging this back into Equation 13
3
3c2
2A
f(xo) inf f(xx) <
+
2Lo
3
(
2A
A
3
3
where (i) uses the condition < ALg. Therefore ff satisfies all conditions of (A, Lo. LI,
Theorem 5. |Restatement of Theorem 7 Let A Lo, L1, > O, and let F F= == L1, 0). Let algorithm Apan denote Decorrelated AdaGrad-Norm with parameters 1j and
ALi
0 0<75
AL7 To
8log
+ 48
Let < min v2 VAa,
VAL1%, ALI
If > Lus then
v3
121302
ALoo² log (1 + 0² 02/22)
A
T(ADAN,
F1
144g4
24ct
144
21

---

Published as a conference paper at ICLR 2025
Proof. We only need combine Lemmas
| and
2
If
then
2
AL
ALi
Snj log 1 48
ALE Lo
8log 1 48
A/A La
so the conditions of and 77 in Lemma D are satisfied. Therefore, by Lemma there exists problem instance (f. g, D)
for which [V 2 ALo e for all 2 0. If n S Li then by Lemma [ there exists problem instance (f.g, D) E F for which |/ [xx))l 2 for all A a
]
t I T == 1+ 144, + ALod" dog(L+o//>3) + "T4,.t In both cases, ADAN requires at least T gradient 24c
queries to find an c-approximate stationary point.
B PROOFS OF T AND 3
Lemma 7 (Restatement of Lemma
Br. Ler 0 < E < 1L Ife parameters of Decorrelated AdaGrad
satisfy 2 v2% log + L Lio
then for any 2 1, there exists some F (A, Lo: IA. a) such
Lo
that [xx)ll 2 efor all T
Similarly, if the parameters of AdaGrad satisfy nj 2 Y log [1+ 21) and 7 S then for any T 1 there exists some f E Lo, L1, σ) such that f(x))] 2 for all 0 S t -
Proof. First, recall the definition of th:
Lo (exp (L1|zl) L1 |x|| - 1).
xxx) = L
Then define
f(x) = Σ (l c.))
To that / is (To, L1 Lm)-mmotth, let x. y Red Denoting x .TT and (y1, -.., yr),
[Vf())-V(()] (Vi((x) vif(x))?
Σ (V(xx)) +((11))
(Lo Lu (xx))())))) - 91)-
(Lo + -[IV\(=)II) (x, y²
(La (=) 3 Σ (x. -2))
= (Lo + <[]V((>)I1 | - y
where (i) uses the fact that 1a is (Lo. L1) smooth and (ii) uses (x:)) < || Therefore f is
(Lo, -mmoohh. Also, define m +.2 log + 1u so that ('(m) Consider the initial point
22

---

Published as a conference paper at ICLR 2025
To me1. Then
f(x0)
inf f(x) ((m)
Lo
(expl (Lmm) Lim - 1)
Lo
LIE 1
-log I+ LIE
-
Lo
Lo
La
1 Lie
log
L1
I
Lo
E (8)
S
A
T
where (i) uses the condition S ALI.
We also define a stochastic gradient for f as follows:
F(x, vf((x) + (25 - 1)00)(m))
where
0
(x. e.) # for all IisT otherwise
j(x) =
min (1 < i sissi ex) 0
and the distribution D of = is defined as P(g 0) P(E 1) 0.5. Then [x E)] (= and [[x, 5) - f=))] I almost surely. Therefore, (f.g. D) E Fis(A, Lo, o).
Now consider the trajectory of Decorrelated AdaGrad when optimizing (J,g, D) from the initial point Dy = me1. We claim that for all $ t T
Ke er+1)| 1 2 (x),e,) = for all 1 11
(18)
(19)
which we will prove by induction on t. The base case t 0 holds from the choice of the initial point Tp. So suppose that Equation 18 and Equation 19 hold for all 0 < i S for some s S T
Then j(x,) = + so
(F &.), e(42) (Vf(x;), e.42) + ((25 1)oee e142)
(0((,, Cx42) + +25 - 1)
@ (0) (2f - 1)0
= (2g 1 1)0.
where (i) uses Equation 19 from the inductive hypothesis. Therefore, for Decorrelated AdaGrad:
(x141, = (æt, C(42)
"
(2 1)o
22 Ei- ((F(xi, Ei), e(42))
7
(2E: 1)0
72 + D1 ((F(2),
(2, Ei), 01))))
(
1
(25, 1)o
122 + Ei- (1))))))
11 (25, 1)0,
7
where both (i) and (ti) use Equation 19 from the inductive hypothesis. Therefore
(x+41, 2242))
a 2 m,
23

---

Published as a conference paper at ICLR 2025
where the inequality uses the condition 17 2 for Decorrelated AdaGrad. Similarly for AdaGrad:
(142)))422) (Eer ec+2)
(2 1)
12 Ei (1),
"
(26: 1)0
722 + +E ((F(2), ex+2))
(8)
(2E, 1)
22 + Σ (v)( - (0))
" (2), 1)0.
72 02
where both (1) and (tt) use Equation 19 from the inductive hypothesis. Therefore
(0 ex22) = +
17
(6)
2 2 m,
11
2
V
where (i) uses the assumed condition 7 S a and (ti) uses the condition 17 2 /2m. This proves
inductive step for Equation] 18, for both Decorrelated AdaGrad and AdaGrad. The inductive step
for Equation| 19 follows immediately from the inductive hypothesis (Equation [9) together with the stochastic gradient definition and j(x,) t + 2. This completes the induction.
For all < <ts the conclusion the lemma follows from Equation 18
[v [V)(),,, e.+1) v'' ((xr, ez+1)) (m) = E,
where (i) uses Equation
18 together with the fact that (/x(x) increases with |z/].
Lemma 8 (Restatement of Lemma 4. Let
AL
AL1o
<<< e < min
LV2log
1+
Al.
Lo
the parameters of Decorrelated AdaGrad satisfy 1) S
122 log
(
then there exists some
Lio
to
(f,g.D) Fal Lo, L1, o) such that [Vf(x;)) for all
22
L21302
1 1. 25 250-2e2 log² (1+
+
AL? Lp
Similarly, the parameters of AdaGrad satisfy 17 5 L log
y2
1 L1 ) then there exists some
(f,g D) FalA, Lo, L1,0) o) such that [V for all
A
2
<
128c4 +
128 log"
AL7 [1+
Lao
Proof. Define m = 1. log (1
Lıs Ln
and consider the objective
Li
-elx x + m) + (m)
-m m, m]
[(x)
(bxx)
e(x m) + (m))
x > m
24

---

Published as a conference paper at ICLR 2025
This function is differentiable everywhere since v/ (m) and (-m)) smooth, so is f. Also, m satisfies
Since ai is (Lu, L1)-
Lo
(m))
(exp(Lim) - Lim -1
T.1
Lo
L1
1+ LI
-1)
1+
log
Lo
Lo
6
Lo
Inc
log
1+
L1
Lo
(
A
L
where (i) uses the condition satisfies
S 1/4 A1. Therefore, with the initial point To m + A the objective
f(x0) - inf f(x) = c(00 - m) + {p(m)
A +
A
=6
2
2
A.
We will define the stochastic gradient with noise distribution D as equal to the true gradient, i.e. g(x, = (x) for every z, 5. Therefore (f.g. (A, Lo, L). Now consider the trajectory of Decorrelated AdaGrad when optimizing (J,g, D) from the initial point = m + A Let to = max (t 2 0 I 2 m]. Then f'(x;) = for all t S to. so that
2e
7/e
T/E
Ee+1 = It
Ft
722 + Σ Di 2
72 to
and unrolling yields
176 Σ
F++1
To
1/2 +
ic
1=0
97c
1
20
T/C
7
V22 + i
1/6
2
00
T/6
dr
7
JU
Vip + xt
166
21
[V> xx?
7
TE
2n
(T7 + 1E -7)
250
7
7/6
21
16"
250
7
722 + t + t
1/6
211e
2 80
7
7/2 + t
Plugging to then yields
THE
217toe
11o+1
2 20
7
V72 + 2002
(20)
On the other hand,
Fog m.
(21)
25

---

Published as a conference paper at ICLR 2025
Combining Equation 20 and Equation 21
1/E
211l0e
2 20
7
72 + toc
2ntte
T/c
20
722 + toE
7
2ntoe
(1)
A
n
722 + loe2
2c
7
to
A
6
(22)
V/2 + LoeE
27
where (1) uses the definition of zo. The last term in Equation 22 can be bounded as
A 4npe
v
27
8mp
A
A de 22 log
Lie
1
SME
A L1
Lo
A 4v2c2
1 L1c
log
SnE
AL10
Lo
A 4v2c2
1+ AL?
log
Size
ALIO
Lo
(m))
A
8IJ
where (i) uses the condition
v27
log
Le Lo
(ii)
uses the condition S Al,, and (ii)
Lio
uses the condition
S
ALia
Plugging back Equation 22 yields
4v log
T.p
444
t0
A
7/2 2 +
t
8nc²
40
Vt
811c2
A
Vta²
SMJ
A
to
(23)
64r222
From the assumed upper bound on 17,
22y
Tne
(8)
22
AL3
1 S
log
1+
<
log
1+
Lio
Lo
Lio
Lo
and
2 log
Lie
(8)
227e
17
1
Lig
Lo
Loo
where (1) uses the condition < AT, and (ii) uses log( (1 x.) S a. Therefore
Liσ
Lng
2 max
/27 log
1 +
AL?
V2ye
too
Li00
L2
Li
Li02
2 max
?72
AL?
2g2
4-2 log² (1+ AL?
4-262
2- log
[ [1
Lon
26

---

Published as a conference paper at ICLR 2025
Plugging back to Equation 23 yields
22
A2
to 2 25
25 log"
(1+
Ar1
Lo
Since (z+) for all I to. this completes the proof for Decorrelated AdaGrad.
The corresponding proof for AdaGrad is nearly identical, so we list only the key steps here. For all t < to.
7/ 2 Tt
7
F++1 Tt +1+
V++1
After unrolling and applying the same bound for E: J/2 in the decorrelated case, then choosing
t lo. we have
Bco+1 2 20 20/22tt 11
From +1 S m, we have
2 20 2 to
2
to +1
16
The assumed upper bound 17 yields
1
L3
L
4 4log2
(1
A1
4.2
Lo
so that
A
A
64c
64c² log"
(1+
AL1
Lo
Since 2tg 2 to 1 for all to 2 1, this means
2
A
to z
128e
128c 1og2
(1+
A47
Lo
Theorem 6. [Restatement of Theorem 2 Let A, Lo, > 0 and let F Fa(A,, Lo, Lı, 0). Let Apa and Anda denote Decorrelated AdaGrad and AdaGrad (respectively) with parameters 1) " Suppose
ALI
ALio
0 < min
4V2
11
+41) Lo
AL7
Then
22
A2
Fee
256
256 log
AL? (1+
Lo
Also, y S a. then
A 128ca log 2
T(Adda, F, F,
128c
A17 T.o
(1+
We first consider Decorrelated AdaGrad. If 2 Fnd log [ [1 12s)) then by Lemma there exists a problem instance for which Decorrelated AdaGrad will never find an e-approximate stationary point. Otherwise, by Lemma there exists problem instance for which Decorrelated AdaGraa requires number of steps at least as large as
Proof. We only have combine Lemmas and
v2x
2
22
+
25
256 log? (1 +
AL3
27

---

Published as a conference paper at ICLR 2025
Therefore in either case, have
A2L 25 256 log" (1
220
+
AL3
To
The corresponding proof for AdaGrad (Theorem) is nearly identical, omit it.
C PROOF OF THEOREM
C.I PRELIMINARY DEFINITIONS
We first provide definitions of constants and objects that will be used throughout the proof.
For 10, and À 0, consider the random walk parameterized by (p, A):
Xo = 1
P(X + =p P(X =X, -1 p.
(24)
Then we can define
pp P(t > 0: X; 5)
Xo(p, = inf (A 2 0: 2p, $ 1 - 8}
6(p.6) oo 6) \o(p, 0).
(25)
Informally, Zp.A the probability that the random walk reaches a non-positive value, and Ao 8) is the smallest required to ensure that the chance of never reaching non-positive value is at least 6.
For d2 2 3, define the following constants:
h1 log (1 + 12((233,) 6))
log 2
log (1 + +(((233)))
log2
7/2
log 2 + 02-2
7/3
log
+
6
(26)
02-2
For 02 E (1,3), define the following constants:
log 21+2((111 (02 5),
log
-7247
7/4
75 =
log
-02+7 -1 -1
12
log 18
-1)
072
log (1 + 2 (02 5), 6))
76
log
18
02-1
Also, we will denote:
Ala
G
(27)
AL?
+ 4 log 1 Ln
which will be used in the following definition.
28

---

Published as a conference paper at ICLR 2025
Definition 1. For p 2/2 o; and ô E (0, 1), we say that 91, 92 E R forms a (p, 6t-rricy pair
with respect to the stepsize function if all of the following conditions hold:
91 = cig.
and
c2g for some g E R with [lg|| =
(28)
sign(e:
c1) + sign(c2)
(29)
ccl 2 and
102| ZE
(30)
1 1 P P_-0-= 02 - 11 G
|al
- p
+
(31)
plaitte
|a| S 1- P
1 P02 - 1
|02| 2 (ost1lplalla
p
(32)
|a| > 1-B 01
1- 02 - 1 c
(02+1)[1-1-1
p/c1 +G
|02| v
(33)
1 1-p
a || (gg²) |922 2 (p.
(34)
Notice that the lower bound of |ey| for the second case of Equation 32 is positive, since < The significance of a tricky pair, as shown in Lemma 10 is that it can be used to construct an instance (f,g, D) Farr (A, Lo, L1, 01, 02) for which A diverges with probability least d.
Finally, let Py = the difference from the common notation Pa (y(x)
(z. so that Py (x) denotes the component æ in the direction of y T>lll
M
Note
(a.y) 1l a.
C.2 PROOFS
We now provide proofs of the lemmas mentioned in Section 6.1 Lemma 9, Suppose that there exists some g Rd with lI9ll (c,0, (02 + 1)Ab] and
4
log (1+ L1 Shminn(les (min(1lgll- AL1)
ag)) 0, or alg) 2 Lilggl
Lo
Then there exists (fexps 9exp, Desp) E Fatl(,, Lo, L1, 01, σ2) such that fexp((x)) 2 efrr all
Proof.
We will construct RRd E piecewise with linear and exponential pieces that [xx(( = mig(] AL1) 2 for all t O.
First, define ğ == min(l]gl] 1 Mلll m = +. log (1+ L.ll@ll defined as
Recall the function : R
Lo
Lo (exp(L,<x)) | - 1). I
(xx)
is straightforward to verify that vi bounded from below by 0, continuously diffcrentiable, (Lo, L1)- smooth, and satisfies
||ğ|| Lo
(1 1+
Li |l@||
ALa
s m) = (mm)
log
SA
L1 L
Lo
L
L
|x| < = 1z'(z)) S lاl 1 ALI
1/ (-m -Iløll
// (m) [ |-
The condition in the lemma statement gives two cases: a(g) < 0 ((g) cases separately below.
4m
We handle the two
T
29

---

Published as a conference paper at ICLR 2025
a(g) S 0. This case is easy: the algorithm A is essentially employing a negative learning rate! For a piecewise linear function that has a piece with gradient equal to g. the trajectory {zy} moves away from the minimum indefinitely. To handle the case that glg > AL1, we instead use a gradient of ğ = min
Case 1:
11) [للll A T and construct a stochastic gradient that always returns either g O, so that each updated iterate 2141 either moves further from the minimum than 2t. or doesn't move at all.
Define the objective
- -I0il((p((x) +m) + (m))
Pz(2)) < m
(a))
(2))
Pa(x)) E [-m,m]
[ m) + (m))
Pg(x) > m
Notice that f is bounded from below by (0) = 0. Since (mm) = [ and (-(m)) = - -l then f is continuously differentiable. Since 10 is (Lu, smoothh, is f. Consider the initial point
Zp = mg. From the properties of &i from above, f satisfies
f(zu) - fx = (i(m)= s A.
and for all æ with f(x)= S f(o)), it must be that Pg(x) E [-m, ml, so
[V[[())] w/ (Pg (x) )1 - ALL
(35)
Define stochastic gradient F for f as follows:
Vf(x) 6 0 F(x, { (11g11/1l Vf(x))
0
{=1, 1,
where & E {0, 1} has distribution D. defined as P / Then Eg [x(, E)] = (xx)
To see that this stochastic gradient satisfies the noise condition: If ggll I AL,, then ğ g and P(E = 0) = 1. so F(x; E) v f()) almost surely. Otherwise,
|
[[((;;)) 0) v((=)]]
[[V[(x))
|
|لو||
LL -1 [|V)(())
01 + (02 + 1) -1) [[*f())]
AL1
A2LL1
[V
ALI
V [(())l
+ 02 [v{()]
ALI
(0)
- + 02 [((x))
where (i) uses the assumption ||و|| < 0-
(02 + 1) and (ii) uses Equation 35 Also
|F(æ;; 1) V [=) || [=))] ` + 02 f<x)],
which uses the assumption 02 > 1. So the noise condition satisfied, and therefore FF, e Fan A, Lo, 01,
Now consider the trajectory of A from the initial point 3p = mg. We claim that æ; cg for some e 2 m for all t > 0. Clearly this holds for = 0. Suppose it holds for some 2 0. Then [[V = g. The stochastic gradient has two cases: if g 0, then
F(Zr, { (1]g) / = /
so
xt+1 = σ; - a(g) = (c: - a(g))) = 4
and Ct+1 2 C m since ag < 0. If & 1, then F( 0, .z+1 2, c.g.
Either way, Zt+1 C++19 holds for some c++1 2 m, which completes the induction. Therefore
[V>())] [ for all / 2 0.
30

---

Published as a conference paper at ICLR 2025
Case 2: a(g) 2 Am In this case, the learning rate a(g) is large enough ensure that f( 2 f(xx) for an exponentially increasing f. By creating f that only depends on (æ. g) and which is piecewise linear and exponential in (æ, g). this increase of the objective function continues indefinitely.
lggl
Define m' = aag))ll |I and Φ [0, mm] as
1b m) | (z 2m) (m))
E [0, 2m)
(xx)
(2m, m' 2m)
s0(x (m' m)) + ll@l(mm 4m) 2m)(m) x (m' 2m, ml]
Note that the above definition makes since assumed that m' a(g)ll)) 2 4m, so m' - 2m 2 2m. Again, ø is continuously differentiable, bounded from below, (Lo, L1 )-m-shothh, and satisfies
[d'(x)) S |g s AT for all E [0, m²]
<xx) 2 0
o'(0) = الواا-
o' d'(m') = - -llا|l-
Now, can define the objective f as follows:
- -1))l (0)) (xx)mm)) (
Pg(x) 50 Pg >0
f(x)
((p(()) m
+ g(m' 4m)
f is continuous inside each "piece" (i.e. each region with Py (x) E (km' (k 1)m²) for Zzu). Also, using p(0) 0, f is continuous the boundary of each piece. Similarly, f is continuously differentiable inside each piece, and using the fact that p'(0) = - |وا|| = o' ('mm), is continuously differentiable the boundary of each piece. Also, f is bounded below by min d(x)
min, (x)) 0. So with the initial point To 0, f satisfies
f(xo) - f. = (0))
((-m) S..
Since & is (Lo, L1 smooth, so is f. Also, [ - (m)) = |lğ|| I AL1 for every x.
Now can define stochastic gradient F for f as follows:
(11g)) (lll fx()))
{ { 0
F(x; {) = [
where& & E {0, 1} has distribution D, defined as P( = | /ll... This is the same stochastic gradient that we used in Case 1, and an identical argument shows that the noise conditions are satisfied. Therefore (f, F,F,) E Far( (A, Lo, 01,)).
=
Consider the execution of A on (f, from the initial point 2g 0. We claim that æ; is an integer multiple of m' T for all t 2 0, which we will show by induction. The base case t = 0 holds by construction. If x; km g for some 2 O. then there are two outcomes of the stochastic
gl
gradient. If & 1, then :1+11
km
9 T
Otherwise & = 0, so
a( F F(.,, 0)) Fx.,, 0)
0t-1
|||||
||g| v ((x)
km
v (ax))
[gl
||@|
|
g
km
(gg)
|
g
km
(g))
|gg||
[g]|
kml
g
m'
g
|gll
[gg|
-(k
1 1)m
[g]]]
31

---

Published as a conference paper at ICLR 2025
where (t) uses the fact that 2; -km' g
Vf(x))
|l 16-
This completes the induction.
ll
Therefore [[=))) = || (-kmi
Toll
o
|gو|| 2 for all t.
Lemma 10. Suppose that
log (1+
Li min min(llgl,, (L1)
(((g) < Lng
(36)
Lo
for all g E R with |Ig|| E (e, + (02 + 1) and suppose that there exist 91, 92 E R which is (p, 8) --tricky pair with respect a. Then there exists (J, D) Fan A Lo; 01, 02) such that [[](())] 2 6 for all t 2 with probability at least 6.
Proof. We will construct (S.g, D) such that / is a piecewise linear function, where one piece has stochastic gradient equal to gi with probability p and ge with probability 1 - Using the properties of a (p. - pair, this instance is a member of Fan (A, Lo, L1, 01, σ2), and will diverge with probability at least å when optimizing this instance.
From the tricky pair definition, gi = cig and g2 = c2g for a unit vector g. Without loss of generality, assume that c < 0 and 02 0. The following argument applies in the excluded case
a 0, C2 < 0 by replacing the objective (ar) below with f(-x). Denote = pei + (1 plc₂ and
+, log (1 4ı and define f: IRd R as
- (P)())) + + x(a)
Pa(x) s -a
f(x)
vi (((g(z)) (Pg(a)) -a) + v(a)
Pg(x) E (-a,,), (x))
where eb is as defined in Lemma] by f. 0, and (Lo. L1) smooth..
1 Notice that f is continuously differentiable, bounded from below
Next, set E = {0, 1} and define F: Rd x E + Rd as
(x( < a and & 0
91
92
PΔ(x) S a and &
(x
(x)
Pg(x) E (-a, a)
Pg(m) 2 and & = 0
Py(ar) and &
92
and define the distribution D over E as
E = {i
0
with probability p
with probability 1
for E ~ D. Notice that F(x, {) = (x) for x with Py(x) E (-a,a) a). Also, (F =
Pg: + (1 p)g2 Eg = V (z) for æ with Pa (a(a)) 2 a, and similarly for Py(a)) -a. Using the fact that 91 92 is a p-tricky pair, we have for all æ:
(plal (plal++) = G. (37)
[f(()]] < pal -laa
-pop|+(1-p)
where (i) uses Equation 33
We can also use the tricky pair properties to show that (f. g, D) satisfies L 2 and the noise condition, depending the two cases in Equation 32 In the first case,
le1l <
1 -
01 +
( p
1 (L-Po -
- 1)
(38)
p
1c2| > plc1| +e
(39)
1- p
SO
(1
p)1c21
p(-la1))
32

---

Published as a conference paper at ICLR 2025
and
l1g2
Egll l02 [|lll
C2
P (E - c1)
(
P P
p
- P 01 +
I 1- p
02 - 1)
S
+
1-p
1-p
P
P f+01
P
02
c
1-P
1-p
(8)
$ 1
P
l l+o +
P
1
=0 + +26,
where (i) uses Equation 38 and (ii) uses E 2 E. Also,
- Egg |c1 - Allg|| = 0 - P -02-1)
1-P P
(ar + 022)) S +
P
where the last inequality uses 2" Therefore (f,g, D) satisfies 2 and the noise condition in the first case. In the second case,
1 P
- 02 -1)
1)
|aa
01 +
(40)
p
(02 1)plca
-01
102l 2
(41)
(02 + 1)(1 - p) -1'
8o
22 2 (02 + 1)p(-cc) 01
(0z + p)
((02 + 1) p) 1)02 (02+1)((-a) -0
02
+ (0z + 1)(1 - p)cz
2 20o+ {
22 - 1
and
(02 1)p/c1| 01
C2
(02 + 1)(1 p) 11
+1
1
lei
pla
1 p
(02 1)(1 -p) -1 1-p)
(02 + 1)(1 p)
P
1
01
|||| +
((02 1)(1 p) 1)(1 p/c1l
1
(02 1)(1 p)
(
P
(1- pp + ((1 p)02 p)
|c1l
p
((02 1) -)) 1)(1 pp)
(02 + 1)(1 (1-1p) p)
lal
+
1-
1-p'
where (i) uses Equation
40
Therefore E pcl + (1 p)e2 2 in the first case. Also as in the
first case, |c] 2 < 02 e.. Therefore (f D) satisfies e 2 and the noise condition in the second
case.
Consider the initial point 2o = (a + (g lg. Recall that
(w) |g2l | = Jozl < ee l02 f S (02 + 1)e $ a (o2+1)G & a + (02 1)Ah,
33

---

Published as a conference paper at ICLR 2025
where (i) uses Equation 37 and (ti) uses the definition of G (Equation 27 Also, by the tricky pair
definition, ||gall = 02 2 c. Therefore || [e,01 + (02 + 1)L so we can use Equation 36 to
conclude that
4
ALI
0 < agg2)
log 1+
L11g22
Lo
Therefore, satisfies
f(zo) - = vba) + {a(g2)1()))
Lo
1+ L1 1n)
) + la(g2))992)
log
L1
L
Lo
L
$
+ Ea(g2)llg21
L1
48
AL.
$
+
log
1+
L1
L1
Lo
AL7
+
4l0g
1
T1
To
Al.
1
[ 4.og
1+
1 4 log
1
A17
La
Li
Lo
A
where (1) uses Equation 37 This shows that (J,9, D) E Far(A, Lo, I1, 02).
We claim that (x;)) || for all 2 0 with probability ō when is initialized with To = (a + (g)))) g2 gg. To see this, consider the sequence
(z:)
y/2 0022)l99 ((z g) a) (z, g) 2 for all st
otherwise
As long as (z, g) > a, the sequence Yt follows the exact same distribution as the random walk
in Equation 24 with À = a(g) 91 > 0. Since 91 is (p, 5)-tricky pair, À 2 (u 6), so that a(92)l9
pp.A I 1 by the tricky pair definition. Therefore
(IIV [(x))) 2 e for all / 2 0) 2 P ((aig)) > a for all / 2 0)
P (s: 0 for all 2 0)
pp,
L
Lemma 11.
Suppose that
log (1 1
L min(
[ (L,)
0 0< a())
(42)
Li
Lo
for all g E Rd with [[g|| E [e, + (02 + 1)LLi}, and that there do not exist any (p. 8))tricky pairs with respect to a. Suppose g Rdd with [g If 00 2 3, then
a(g) <ō Ō
Li(AL)) vo me o
On the other hand, of E (1, then
1
alg) S δ (o2 1)2 1 L, (AL, 70-70
Proof. Different from the proof sketch Section 6.1 in our actual construction below, we use
two sequences (æx) and (y:) instead of one sequence [2)). Every in the sequence (æ.) satisfies
34

---

Published as a conference paper at ICLR 2025
[a(())] [e, + (02-1)c) and every y in {3.} satisfies Pa(x)) E (02--101,,,010000
(see Equation 27 for the definition of G).
Denote ((x) (ar) ||0||, , fix any po E
and define sequence { _ follows:
2 ag
Vo
2; = (-1) Po
Polp D 1|1
g
-
g
Also, denote kn max ( 0: ||01|| S 1-po σ1
(
1-10 12-02 02 -))c) We claim that, for each i
Po
with 0 < S kip the pair (æ;, (1+1) satisfies all of the conditions of (pu, d'-tricky pair, other than
possibly Equation 34 Notice that ||>,|| is increasing and (x,,g) has alternating sign, so Equation 29
and Equation 30 are satisfied. Recall that ||æ;|||
1- σi
+
P-Po 02 - 1) by the definition of
Pu
Pu
kg- Since S was assumed in Theorem this implies ||0: S
1- 0 + (1 02 1) G. So
Equation 31 is satisfied. Since
||>x|||
S 1-Po 01
+ [--Po 02 - 11 6, we must fulfill the first branch of po mollew, +5, which holds by construction of the I-Pa
the RHS of Equation
32 This only requires || || 2
sequence {æ:}. Finally, Equation
33 is satisfied again from e S G. since
a Pol æc
+
6
Po pol|
1 Po
Po
This verifies the claim that the pair (æ:, (441) satisfies Equation 29 Equation 33 If (a;, 1i+1) also satisfied Equation 34, then would (pn, 6)-tricky pair. Since it was assumed that there do not exist any (p, 8) 8)-tricky pairs, it must be that Equation 34 is not satisfied by (z,, 2141), so that
3(x,) S Ao 6)8(11+1)
for all 0 S S kg- Choosing i and unrolling
ko 22 2: B(x,)) < (Ao 8))k0-1
(43)
Now choose yo = (-1)4h (ai (a2 -T Then ||30|| || from the definition of ko- We again want to show that ( yo) satisfies Equation 29 through Equation 33 We can use an identical argument as above to demonstrate Equation through Equation 32 so it only remains to
show Equation 33 It was assumed in the statement of Theorem that 01 ( 1)e < G. Therefore
yo = 01 + (o2 - 1)e < ALI < -1 -1 +
1-P
which demonstrates Equation 33
This verifies the claim for (Ik yo). Again, Equation 34 would
imply that (, 1, Vo) a (po. 0) -tticky pair. But we assumed there are none, so Equation cannot be satisfied. Therefore
8(0 S Ao(po. 6)3()))
and combining with Equation 43
yields
3(xo) I (Ao(Po, 5)) 3(yo)-
(44)
Now fix some E 21 o--1) define the sequence {3/ 1:00 as:
yi = (-1) kott (02 + 1)p1 y 01 g
(02 + 1)(1 - -p1) - |lll
Denote k1 max i 2 0: | < 1-p1 +
1PL1oz -1)() G). Similarly as for the sequence
P1
P1
{æ;}. we claim that for each i with 0 < < k1, the pair (g/: M satisfies all of the conditions of (pr, -)-trckk pair, other than possibly Equation 34 Equation 29 and Equation are satisfied, since ||vell is increasing and (y:, g) alternates in sign. The upper bound of ensures that Equation 31 is satisfied. Since
|| in the definition of k
1- P1
(L-P1 -21-11)) -1)
|vll 2 Yol = a1 + (0z - 1)c 2
01 +
P1
Pi
35

---

Published as a conference paper at ICLR 2025
must fulfill the second branch of the RHS of Equation 32 This only requires
(02 1)pp 1all 01 (02 + 1)(1 - p1) -1
yy+all
which holds by construction of the sequence {y:}. Finally, to show Equation 33 we need
|//-111 11: +G G
P1
which is equivalent to
(o2 + 1)p1 11 01
Pi 11ll +
(o2 + 1)(-1))))) < 1 P
(1 - 00) + 1)pilly:-111 (1 11--10 p1)01 2 ((02 + 1)(1 p1) 1)p1/31111 + ((o2 1)(1 pı) L)G
Pillvall 1 (1 - -1pijo01 + ((02 + 1)(1 -p1) 1)G
|B::l| < 1- P1 01 +
(02 1)((1- p1) -
1- p1
P1 01
1 P1 02 - 1)c, G. P1
<
All steps in this sequence are reversible, and the last inequality holds by the upper bound of ||g:|| in the definition of ky. Therefore, Equation B3 satisfied. This verifies the claim that (y:, 36+1) satisfies all of the conditions of (P1, 5)-tricky pair, other than possibly Equation 34 Again, Equation 34 cannot hold, since this would imply the existence of a (P1, 5) --triicky pair, and we have already assumed otherwise. Therefore
B(yi) S AO(PI, (3)())
for 0 S S kj. Unrolling from i = 0 i k1 yields
B(yo) (No(11, 83) B(yr)))
(45)
Combining Equation 44 and Equation 45 yields
((xo) < (No(po, to (Ao(pi, (0) B(yk)).
(46)
We can use Lemma 16 for the sequences {|| [>; 11 and {llysl]s to lower bound ho and ky. For Ku, we
apply Lemma 16 with
Po
1 - po
1 Po
1) e.
a0
E;
A
a1
02
Po
Pa
Po
Po
Then
A(r 1) + b
1-po po
01 +
1-p0 02 1)e)
Pa
2po -1
1-pn
+ 1-po
an(r - 1) +
2P0
-1
11-p
I-po
1-po 01 +
1-p0 02 - 1)
(2po - 1) +
c(2po 1) +
1-po Po
(0) +
(02 I-po
Pn
6) (2po 1) +
2ppc
Apo-1)((1pm)
(0) + 02c) + +2(1 - pa)c
2ppc
(2po 1)(1 Po)
(01 σ26) + 1 1- Po
2phc
Po
36

---

Published as a conference paper at ICLR 2025
so Lemma
16 implies
log
(2po 11(1 11(1-po)
(0r + Ø2e) + 1-
kp
2p3e
Po
log 1-po
Pe
log
(2pa (5p0-1)(1-Pu)
(01 + Oze) + 1-po
2ple
po
log I-Po
log bo
1,
(47)
Po log 1-po
where we denoted
(2po 1)(1 Po)
1- Pa
bu
(01 + 02c)
2pije
Po
Similarly, for ki, we apply Lemma 16 with
(02 + 1)p1
01
an = 01 + (02 - 1)c,
r=
(02 + 1)(1 -P1) -
=
(02 + 1)(1
p1) -
== 1- P1
01 +
(1-P1
02 - 1) G=
1 1-P1 P1
01 +
02
Pi
P1
P1
P1
1 1- P1
Then
(02 + +1mp
(02 + 1)(2p1 1) +
r
(02 + 1)(1 PI) -
(02 + +1((1 ()(1-1)) -
so
1-P1 ( + 02 I-p1
Pi.
G) ((02 + 1)(2p) - +1) -
A(r 1) +
(02 1)(1 p1) 1
and
(01 (02 1)c) ((02 + (2pp 1) 1) 01
ao(r - 1) + b
(02 + 1)(1 - pP)) p1)-1 -
So
1-p1
(a1 + 02 - c) ((02 + 1)(2p1 - + 1) 01
A(r 1) +
A
(r - 1) b
(o + (a2 1)c) ((02 + ()(2p: - +1) σ1
Denoting the RHS as b, this yields
log b
log bj
h =
1.
(48)
log
(02 (a2+ 11 p1)
log (a2 1)(1-
(1T2 1)p
Plugging Equation 47 and Equation 48 into Equation 46
Ing
los by
(xx) I (Ao(po, o) (No(Pi,8)) (Po 5)) Using the fact that for any p.
low
PG
(Nole1, 5))
log (02
(a) Dp
1ia1 p1) B(yr.).
(No(po- 8)) log (No(Po, 8)) log A) log Ao(ps.)) )o
lag
we can choose p log bo and p logbu, bb.
B(xr) S (No(po, 0)) -1 (NO(p1,0))~ ( do ((1 d1 ((yk))
(49)
bo
b
where
1
Po
Φ log
log
do(po, 8)
1 - Po
1
(02 + 1)P1
01 log
log
)o(p2, 5)
(02 1)(1 p1)
37

---

Published as a conference paper at ICLR 2025
Note that Φ0 > Ø1. and denote m = žn log 11
We can also bound (zr,, using the gfl since we previously showed that (Yk, yk+1) satisfies Equation 29 through Equation 33 In particular, Equation 31 implies that
A/i
Lo
assumed condition (g)
<
4m
1 Pi + - P1
(----o0 -
|3kk Il
11G + (a2 (o
1)
P1
so that 13,, falls within the range for which the bound on a(g) applies. Therefore c( S
4m
||
||
or (3r.. S 4m. Plugging back to Equation 49 yields
do
1
B(xo) S 4m (Au(Pu, o)) (Au(P1,8))
(50)
60
b1
only remains to choose po and pı such that bo bı, to. and Φb can be bounded in terms of the problem parameters. First, using Lemma 15 we can rewrite do 8) as
Xo(p, 8) >o 0) (Ao(p,)) - Ao 0))
1-p
+ (No(p. )o(p.0)
p
1 P
+ <(p,5),
p
so that
P
p
1-p p p p((p.0)
Aa 8) - -- p+p((p,))
We can then rewrite do as
Po
po + PoC(po. )) /log
- Pa
Po
d
log
+ log
Pu
1
1 Po
log
1-po (pp(p.5))
1-po
po log
I-po
and Φ1 as
-(188 log
P1
- P1 + PiS(pI, 8) ))
1 P1
(02 +)p1
Φ1
+ log
log
1 p1
(02 + 1)(1 pı) -
log
P1
log
(=m+tpi(pp.d) 1-P1
I-P1
log
(02+1)pp 1)p (o2++)[[1 111-)-
log
(0a+1)pm
(o2+1)(1-p))
We choose and differently depending on the magnitude of 02. We consider two cases: 02 2 3 (bounded away from 1), and σ2 E (1,3) (close
1).
Case 1:
2 3. Here we choose po P1 2/. and this satisfies po, Pi
( 2 ) We now
bound the remaining constants. For bo:
b0 (2po 1)(1 Pa)
(a) O2E) + 1 Po
po
1
(01 + +22) +
8c
2
8E
38

---

Published as a conference paper at ICLR 2025
For b1:
1-p1
01 + (02 I-p1 G) ((02 + 11(p11 - 11)
bj
(0r + (02 1)E) ( ()(2 - +)
1-p1
((02 + 1)(2p1 - 1)) - 01 +
1- 02 - 1) ((02 + 1)(2p1 - + 1)6
Pi
P1
(ar + (02- 1]c) (00 1)(2p - 1) + 1) - 01
(L 02 - 1) - -)
(1)
(01 + (02 (()2) 1](2p1
+ +
LLPLo2 - 1) ((02 - 1)(pp: 1) + G)
(09)
P.
(0 + (02 1)01) ((02 1)(2p: -
L-Pio2 1) ((02 + -1)
p1
(02 ((02 + ()(2p] 1)
(6))
(302 1) (102 + +
(02 -) 2) (02
(02 2) (02 + 4
(02 3 02 9) 1) 01
2 + 4) 3)
202 (02 4)
02 G (i)) G
2020
60
where (1) uses the fact that
1- P1 ((02 + 1)(2p1 - 1) 1)
1
02 + 3
0 0,
P1
(ii) uses 6 S 01 as assumed in the statement of Theorem
(iit)
plugs in P1 = 2/3, and (iv) uses
02 2 3. For Φ
log
- Po + (P)
I-Po
log (1 2C(2/3, 8))
Φ
1 -1
Pu log
log
1-po
where we denoted
log (1 + (-((2/3,6))
11
log 2
For Φ1:
log
log
1 P-Pp+P:
I-p1
1-P.
Φ1 log
(a2+1)([ (022+1)pp
log
(0.
(P))
log
log (1 + 2ç(2/3,
log
+ 02-2
log
+ 02-2
log
log + 2(((233)))
=1
1
log
2 + o2
log
+ mu-2
7/
733,
where we denoted
log 2
7/2 =
log
2 -2
log (1 + (2, 6))
73
log
2 02-2
39

---

Published as a conference paper at ICLR 2025
Finally, can plug bounds of bu. b1, Qu, @1into Equation 50
(2)(233,0)) 8c
1-7
(60)
1-12-78
((xo) - 4m (Ao(2/3,6))
G
192m (A0(2/3, -1 (Ao(2/3,0))
1-71
01
1 1-72
(8)
c
1-71
12
768m
c2-21
768m
01
o + 21
1-71
A17 Lu
3072
log 1
G11 73 7
where (i) uses the fact that Ao(p, 6) is decreasing in terms of 8, and (ti) uses do 0)
-e
(from Lemma 14). As noted after Equation 49 do Φ1. that y 72 7s. Replacing ((xp) = g agg) yields
3072
1 ALf Lo
a(g) -
log
11 2t 12
74 3 72773 log 1 Lo ) (1 41
3072
(1 A17
))
$
Lo
which is the desired result.
Case 2: 02 (1,3). Here we choose po P1 this choice,
22t5
which satisfies po: P1 E
With
12
22 o2+1
02 +
02
1 Po
2po
12
6
and similarly for P1. We can now bound the remaining constants. For by:
bo (2po - 1)(1 - po)
- Pa
(0) + 026)
+
2pde
(o2 1)(-02 7) σ1 + 026
- 02 + 7
(0z + 5)2
c
+
① 6(02 1) + 02E
+
64
3(02 1)01
32c
40

---

Published as a conference paper at ICLR 2025
where (1) uses 02 E (1, For b1:
1-p1
+ 02 1-p1 G ((02 + - - 1) 01
61
(0) + (02 1)e) ((02 + ()(2p) -
1-p1
((02 + 1) - 1) 01 1-M1 1-
02 - 1 ((02 ()(2 - 1)
Pt
(o) + (02 (002 1) 1) + 1) - -1
L- 02 - 1)
1)(p1))(p1pp))))))))p - 1)2
(1)
(1 + (02 1)() ((02 1)(2p1 1)
L-PL
P: 02 - 1) (102+ + 1)(2p) - 1)
(19)
(0) + (02 1) (102+
-1 1)
12 02 1) ((02 + 11)
p
(02 ((02 + 1)(2p1 1) 1)
1-P1 02 101 - G
1 - P1 1
G
002 +7
1
G
020
P1
02
01
02
+5
02
01
(o2 1)(- 5)
G
(6))
(02 1)G
2
02 + 5)
σ1
12o
where (1) uses
1 - P1 ((02 1)(2p1 1) + 1) 1
02 +7
(02 + 1)
02 -
6 +1) -
P1
02 +5
(-02 + 7) + 5)
6(02 +
77 1>00 0,
(ii) uses S 0i as was assumed in the statement of Theorem and (iii) uses 02 E 3). For do:
log
1- PP
log (1 - ((o. 5))
a2+5
Φ =
Po
Pg log
log
I-po
-02+7
log
25 -0g77 (117)((P,)))) 5)) =1
log (1 + 2C(po, 5))
1
log
-out7 -1) 1)
log
12
1)
-02t7
1 74,
where we denoted
log (1 + 25(2(( ++(((2200> (02 + 6))
74-
log
-0g+7
Lastly, for Φ1, notice that
(o2 + 1)p1
(02 + 1)(22 +5)
(02 + () +7)
-1
(02 + 1)(1 P1) -
12
12
(o2 + () + +))
(02 + 1)(02 +5)
(02
1)(
02 + 7)
12
(02 ()(-02
02 +))
3
15
18
1 <
1.
02
02 + 5
1
41

---

Published as a conference paper at ICLR 2025
Therefore
P1 log
log
1-pi (pp(11)
1-p1
1-p1
11
log
(01++1))11
log
(0g
(mg+1)(1-p)>
(og
p1l
log
-d2+7
02+t5
log
+
-02+7
-2+5 S(p1, 6)
log
log
00-1 -1)
18
dg-1
log
-02+7
log (1 + 2C((1, 8))
log
18
18 log
1)
0221
02-1
75 76
where we denoted
12 log
1
-02
75
log
18
1
log (1 + 25( 12
(02 5), 6))
76
log
18
02-1
Finally, can plug bounds of bo, b1, 6o, Φ1 into Equation 50
32c
1-74
1201
1-70 7-70-%
B(xx) S 4m (Ao 8)) (Au(p2,8))
3(02
1)01
(02 1)G
(
2 512m (Ao (2o(2/3,0)) (Ao(2/3,0)) (b)()
E
1-70
01
1-95-70
(02
1)01
(02 - IIG
(1))
6
1-71
01
1-70
2048m
(02- 133-1pm 1)02
(02 - 1)G
1-74
2048m
(Ø2 1)2-24 112-74-93-300 -1 Gl 1-1 10-00100 20 126
8192c 1-74
AT
log
1
(02 1)2- 172-7477-77 1
2o 10 G1-76-16
Lo
8192.1-7
AL3
(1 (1+4 1144log
(1 ALL
))
log
1
(02 1)2-21 7 (AL1)
16 10 70
Lo
Lo
where (i) uses the fact that Ao (p, 8) is increasing in terms of p and decreasing in terms of and (ii) uses Ap 0) = 1-p (from Lemma 14). As noted after Equation 49 Φu > Φ1. so that 7/4 < Ys + 76-
Replacing ((xa) B(g) = ag)) yields
8192
A1. ) Lo
(1 (1+ 4
1+ ALI
a(g) <
log 1+
(02 112-74- (A 1- 200000000000000000000000 7s 70
Lo
which is the desired result.
Lemma 12. Define
on max a(g).
lig
There exists f E FanlA, La, 0, such that [V 2 for all t with
<
20ge
42

---

Published as a conference paper at ICLR 2025
Proof. Denote a = ł, log
1 + 2.: and let g E R such that | = and a(g) = Og. Define the
objective f : TR + as follows:
-c (p)())) + +a) v(a)
Pz(x) -a
f(x))
w (()())) (o(xx) + +ba(a)
(a(x)) (-a, a)
(a(
where &b is as defined in Lemma I It is straightforward to show that f is continuously dif- ferentiable, bounded from below (T. 0), and (Tn, [1] -smoohh.. Also, with the initial point ao a Aa)(a) a. satisfies [(x) l" = A. So f Fan(A, Lo, 0,0).
Consider the execution of A on f from æo (a + M-M
Toll and let to max >
0 Pg 2 for all 0 f S t). Then Vf(xx) for any t & to. so that
I++1 (VV((az)) a. a(g)g It Clgg
80
Pa(x(+1)=
#t-1: |g9|
21 oug.
[g
= Po(( au 1ull9/l =P agc.
Unrolling over yields
(2(+11)) PP Px))
1)avc.
In particular, choosing & to yields P Po( 2 Py(xn) - (to + 1)a(c)c. By the definition of to.
we also know Pg (1) ) < a. Therefore Pg Pg(x0) - (ln + 1)a(c)e < a, and rearranging yields
(x)) - a A - (a) alc)e
to + 1>
a())e
Also,
Lic
AL
A
(a)) L1
log
1+
S L1
Lo
24
2
where the last inequality uses the condition
< Ah from Theorem
So
to + 1 2
Therefore, t i A 2a(e)e² implies that & < to so that (x 2 by the definition of to. and finally [[V((z)]] =
The following lemma is nearly identical to parts of the proof of Theorem in Dron & Shamir (2020), with some small modifications fit our requirements. We include it here for the sake of completeness.
Lemma 13. For any sufficiently large d E N and any Rd - Rd, there exists some (J.g. E) Fan(A, Lo, In, 01, 02) such that (x+)) ) 6 for all 0 S < T, where
A
T
2cd
Proof.
Suppose d 2 T. Let Rd + Rd and define f f:Rd - R
T
f(x) = cx c1) + Σ 1i((2,c)))
1=2
43

---

Published as a conference paper at ICLR 2025
where
a
|a|
La (r + az)² a
2
|x| E
ai.
hx(r))
aa E
a1 4
2
La (r - 6,)² + 6,
|x] E
h.
bi
2
2
|a]| >
b,
a, 02a(ce1 + 01e)
b, = 0ia(ce1 - ojel
For any a, y Rd,
- =
(Vif(x)) - v.f(y))
Σ
(M (M(2))) 12())))²
(1 $
1
Σ
(x; - my)?
i=2
< L51l yl1
where (i) uses the fact that h is smooth. Therefore f is Lm-oth,th, and consequently is (Lu, L1)- smooth. Also, define the following stochastic gradient for f:
F(x. {) = ff(x) + (25 1))1e)(a))
where
j(x) = min (1 sisd d (x, e,) =0
This oracle is defined so that the stochastic gradient noise at step / only affects coordinate / 1 (this will be shown later). Let be the distribution of ç, defined as P(e 0) P(t 1) 1 With this definition, the stochastic gradient F satisfies
[[F E)] f(x))
[F(x, E)
V/(x)) S 01 (almost surely).
Therefore, all of the conditions for F, D) E Far(A, Lo, LI, 01,01,000 02) are satisfied other than the condition that is bounded from below and f(xp) ((x & A. This condition will be addressed at the end of this lemma's 's proof.
Now consider the trajectory of A on from the initial point æp
0. We claim that for all 0 < < T:
(1,,01) = - Σ a(F(x,;))))
(51)
1=
-aaj =
(x,, 0²)
for all 2 sjstt1
(52)
by =
(x,, 0,) = for all j t 1,
(53)
which we will prove by induction on t. By construction, all three the above hold for the base case t = 0. Now, suppose that they hold for some t t - 1. Then for 2 2,
(g(-a,)
j 5 + and E < +++1 and E
( = M1 (12, ez))
(0)
Kg(b,)
(at) 0,
(2((0)
j>[+1
where (i) uses Equation 52 and Equation
53 from the induction hypothesis, and (ii) comes from
the definition of h. Therefore Vx(x.) 6C1- Also, Equation 522 and Equation 53 imply that j(æ:)) = 2, so
F(x,,{)) vf(x)) (26: 1)010.-2
44

---

Published as a conference paper at ICLR 2025
Therefore, the next iterate 21++1 is:
F+41 n, a: ( E.) (())))))
xt - (ff( 5,)) (ce) + (25, - 1)02))22)
1-1
++1
Σ
( (F( Ei))
+
Σ
a 0,), - a(F(z,, (ce: + (2C, 1)0(0(22)
i=2
a(F(z;;;
e1
(0,, e:je; (2f, 1)a(
where (i) uses Equation 51 from the inductive hypothesis. Notice that the last term (i.e. the coefficient of 2 equals -a; when &. and it equals b; when &r = 0. This proves Equation[31] Equation [2] and Equation 53 for step / - 1. This completes the induction. Together, these three equations imply for all < T, which is the desired conclusion.
that (x:
The only remaining detail the satisfaction of the condition f(ro) - inf f(x)) < A. As currently stated, the objective does not satisfy this condition because is not even bounded from below due to the linear term e(x, e1). Similarly to Drori & Shamir (2020), we instead argue that there exists lower bounded function f that has the same first-order information as I at all of the points æ for 0 St S T. If this happens, then the behavior of A when optimizing f is the same as that of A when optimizing /, the conclusion || fax:)] still holds. Specifically, need f which is lower bounded and that satisfies:
vf(x,) = (ax)), f(x:) = f(x:)
for all 0 < t < T. The existence of such an f follows immediately from Lemma of Drori & Shamir (202)). and this ff satisfies
3e²
inf f(x) 2
min f(x,) 0515T
2Lo
Therefore
3²²
f(xo) inf f(x)
min f(x))
2L.0
USEST
3²2
T Σ (((()))))))
max USEST
-E(2(, e1)
2L
3ea
t-1 ((F((x,,)))
1+1
max 0StST
Σ hi(lar,))))
(54)
2Lo
1=
1=2
Denote ar = =((((xr; Then for 2 sistt+,,
1 Loo7a
h((2,, ei))
Plugging into Equation 54
3c2
[-1
H+
f(xo) inf f(xx) <
+
max
Lno
2
0
2L.
0
1=0
2=
3c2
1 Luoja?
<
+ max
2L
USIST
4
Q
45

---

Published as a conference paper at ICLR 2025
Qi can be upper bounded by the maximum value of exx 1/ Loo
function of æ, which is
Trom7 Therefore
3x²
e
((xo) -in
max US!ST
2T.0
362
Tea
2L.
Lool
(
3c²
+
20
2
(4)
S
A
where (1) uses T
Loo 2x
and
(ii)
v A /LLo/3 /3
Theorem 7. [Restatement of Theorem 4 Let A, Lo, L1, 01 > 0 and 02 > 1. Denote
AL1
G=
1+ 4log
1
ALi
La
G-ai and suppose G 2 as. Let 0 < < min 01, 02-1
j Let algorithm Auda denote single-step
adaptive SGD with any step size function a Rd (A Lo, I1, (1))). of 2 3, then
R. for sufficiently large d, and let F
(AI,)- 10 72 19-7 "n
T(A F, 0) 6) 20
2-22
Otherwise, 02 E (1,3), then
25 70
T(A F,c,0) 20 ÿ
(02 1)2+ 1122---70--01 10-3000----000000000000
2-
Proof of Theorem We only need to combine Lemmas 9 g I2d such that |g|| [e, + (o2 M) and
12 and 13
If there exists any
L1 m M)
agg) S O or a(g) 2 Lillgl log
1
Lo
then there exists some problem instance (f. F, D) such that (xx)) 2 for all 2 (Lemma 9). If such g exists, and there exist any tricky pairs with respect the stepsize function a, then there exists some problem instance (f, F. D) such that [V.f(x,)) 2 for all 2 0 with probability
least (Lemmal 10). Suppose neither of these cases hold. Lemma 12 implies that there exists
problem instance (f, F. D) such that fxx)))) 2 e for all with
T < 4age2
Since neither of the above cases hold, the conditions of Lemma 11 hold, so we can bound og with two cases. If 02 2 3, then
3072
log (1+ AL7 Lo )
(1 (1+ 114410g 4 (1 AL7
))
on <
((
Lo
so [[(x))]] 2 for all with
ALnoz (2 72 72 +7 70- 1 Ō
+
(55)
22-71
46

---

Published as a conference paper at ICLR 2025
If 02 (1.3), then
8192
1+ A ) (1 I 4l0g
(1+Alog
1+ ALA
))
ag S
log
(02 - 1)2-24 10--4418-76671 70 La (A
75 7
Lo
so [V || 2 for all with
ALoof
(AL1) 76
7s 7
t δ
(02
1)²
01
(56)
2-774
02
Lemma 13 implies that
ALoof
T(A F,
2c
and this can combined with Equation 55 and Equation 56 to obtain the two conclusions of Theorem
4
D AUXILIARY LEMMAS
Lemmas 14 and 1.5 deal with the asymmetric random walk described in the proof of Theorem We
restate the associated definitions below.
For E (0, 1) and À > 0, consider the random walk parameterized by (p, A):
Xo
P(X++1 X1 + p
(57)
P(X = Xt 1) = =1-p p.
Define
2p, P(3t > 0: X; 5)
Xo inf (A (A20 pp,x $ 11
6) = (p, 0) 0).
Informally, Z the probability that the random walk reaches a non-positee con-positive value, and (o 8) the smallest À required to ensure that the chance of never reaching non-positive value is at least 5.
Lemma 14. Let X₁ be defined in Equation 57 Then (o 0)
1-p
Proof. Denote A b min(a, b). Define inf 0: X, 0). Note that X, Xo Σ1- Ei.
where {E:)t=1 are i.idd. and follow the same distribution: Pr(E: A) p and Pr(E: -1) p. Now we first prove that {X, 1((A + 1)p - 1) is martingale with respect to itself. To see this, note that for any & 0, we have
E [X, ((A 1)p 1) X = E [X, + & <((2 + 1)p 1) X,-1] = X
where the last inequality holds because [5: X,-1] Ap - (1 -1-p) = (X 1)p-1.
Let T > 0 be fixed constant. Note that T is stopping time which is almost surely bounded.
Then by the optional sampling theorem,
E [X (T (TAT)( 1)p 1)] = E[X,] 1.
Therefore, we have
E E[X -
E A T
(A + 1)p
Let T + oc. By the monotone convergence theorem,
limr E. [
(A+ 11p
We consider the following cases.
47

---

Published as a conference paper at ICLR 2025
If X < 12, then (A + 1)p 1 < O. Combined with [[r] >> 0, this implies P
lim E [xTAT]] - < 0. T-000
Now we show that E by contradiction. If [F[ co, then limy- E [X
xc which is impossible because X 2 -1 for any T. Therefore Pr(T = 20) = and
Zp.A
If 2 - then (A + 1)p- - -12 2 0. Combined with E|r] > 0, this implies
lim E -[x 0. T T-200
Now show that Pr(r 00) > 0 by contradiction. If Pr(r o0) 0. then by
the bounded convergence theorem, we have limm E [ = E[X,] < 0, which
contradicts lim [X 2 0. Therefore Pr(T = oo) > 0 and 2p.A 1.
Therefore Ao(p) 1-P P
Lemma 15. Let Xe be as defined in Equation 57 Then limg-so+ Xo(p, 8) = >o 0) for all p E (0,
Proof. The idea of the proof is, given some X, to find some a E (0, 1) such that Y, = x is a martingale. We then apply the optional sampling theorem x in order get bound of pp, in terms of X, which we can use to upper bound (p 5). This upper bound goes to Ap 0) as + 0+.
Combining with the fact that (p d) is increasing in terms of ó yields lim do 6) Ao 0).
Let p (0, 1) and 8 (0.p). We want to find Ā such that p/ S 1 5 (so that Ao 8) s λ) and + (p. 0) as 8 - 0. First, need E (0, 1) such that a is martingale. This requires
Ela X₂] = Xx pa Xeta + (1 - p)a X,- -1 = a.
pa Xeta a xx + (1 - p)a X1-1-0
x1
+ (1 -p)
(58)
so we are looking for root of (x) = px x (1 - p) in the interval x E (0, 1). We claim that for all X > 1_p there is exactly one root of h2 in (0, 1). To see that such a root exists, notice that
p
(0) 1 - p > 0 and (1) = Also, =1) p( - > (since À )_²). Therefore hA(1 - 2) < 0 for sufficiently small 2 > O. Then we can apply the intermediate value theorem to hy (0) > and h1(1- 2) < 0 conclude that must have a root in (0, 1).
To see that this root is unique, note that ıĄ is strietly convex in (0, oc), since (x(x) = pA(A
1) > 0 for x > 0. Suppose hy had two roots 21, 22 E (0. 1), with Ty < D2- Letting
a= (x² /1 x1). we have by striet convexity (x2)) (1 a))x(2)) (x1) (1x
which contradicts h (x2) = 0. Therefore, hy has a unique root in (0, 1) for every X > - Denote
this root r(A).
Now define Ā inf ^ - r()) |
1- (
(the threshold 1 - 5 will be used later to show
.p.A S 1 5). In order to show that Ā exists and that Ā do 0) 5 -> need a few facts about r(A). Specifically, we need
r()) is decreasing
(59)
lim r(A) =
(60)
lim r()) = -1-p pp.
(61)
To see Equation 59 let 22 > A1 > 1-p For any E [r(A1), 1):
x x- rdx MA (r(r))
x- r(11)
hrs(s) < hx((o) $ 1 11 1- r(rr())))
+ N2, (1) = O,
(--r(A))
48

---

Published as a conference paper at ICLR 2025
where the first inequality uses the fact that (x) is decreasing in terms of À for any fixed æ, and the second inequality uses convexity. Then r(>2) cannot lie in the interval [r(A1), 1), so r()2) < r(A1). This shows that r(A) is decreasing.
To prove Equation 60, notice that r(A) E (0,1) already implics lim x- I 1. So it suffices to
show for any (0, 1) that r(A) 1 for sufficiently small X. Denoting = 1-p
p
lim hx(1 c) = p(1 c)/// x + (1 - p) - he(1 - c) > he(1) - ch/((1) 0,
(62)
where the inequality uses strict convexity of he and the last equality uses he(1) = [2(11 0. Also
lim 11 - 6)
lim p(> + 1)x* - 1= (1 x+
< 0.
(63)
Together, Equation 62 and Equation 63 tell us that for sufficiently small x: h2(1 - c) > and hy - c) < 0. Then for any x S C,
hx(x) 2 hx e) + (a
- -))
In other words, for sufficiently large X, the root of ht cannot be smaller than 1 - - or > 1 -e. This proves Equation 60
For Equation 61
let E (0, 1) and A > 1_, Then by strict convexity of hx: p
h hx z (0) (1-p) 2, -
so (x) > 0 for any x S 1-1p-pp- Therefore r(A) > 1 for any x, so that lim, T(A) 2 1 1-p
We can also show that lim r(A) S p by showing for any that r()) S 1-p+ e for
sufficiently large A. By convexity of h2:
lim hx 11 x A0000
lim p(1 - p + e)att - (1-p t) (1 -1-18 p) = -c.
So h1 - p p < e//2 sufficiently large X. Then for any x 2 - -
hx(x)= S - (1- -
= - (1-a) a)c < O. + (
So the root of hy must be smaller than 1 - (A) < c-p This proves that lim
r(A) S
1 - p. and completes the proof of Equation 61
Recall the definition Ā = inf {A يا r(()) S 1 - -0}. Equation 61 and Equation 60 together
imply that À exists, since 8 E (0,p) + 1 1 8 E (1 p. 1). Also, Equation 59 and Equation 60
imply that Ā + -- = \o 8) as d + 0. p
We can now consider the random walk X, defined in Equation 57
with X = A. Our goal is to show
that p. S 1 - 8, which implies that \o 5) < Ā. Let a = r())
1 - 5. We have constructed a to
be a root of h5. so that a Xx is martingale, as shown in Equation 58 Let To inf 2 0 S 0}. O. Define T min To. T.). We have a (T)in(T,)) is
and T,, = inf ft 2 0 X, 2 b). where
bounded for any n and it is nonnegative, therefore by optional sampling theorem and martingale convergence theorem (e.g.. Theorem 4.8.2 in Durrett (2019), we have
a X0
E [ax]]
= Pr(To < XT + (1 Pr(To < <T,
2 Pr < Tb) + (1 Pr < To))a 1+1
where the inequality holds due to (0, 1), XT, < and XT, S + A. Let + co on both sides, and note that a + O. have
a > Pr < x)) = =
(64)
Therefore
2 5 a $ - 6,
49

---

Published as a conference paper at ICLR 2025
so that Au(p, 8) S A. Finally,
Ao(p, 0) S
lim Ao 8) S lim X == Ao 0), 8-
6-20+
so that lim 2)( O).
Lemma 16. Let {as be positive sequence of reals satisfying a++1 ra; + bfor > 1, and let 2 on. Define k max 2 a, A}. Then
log
A(r-1)+b a0(r-11+b
k =
logr
Proof. is straightforward to show by induction that for any i2 0:
agr't + b re -1
b
b
a; agr'
rd
1 r-
rr
ao
r-1)
1
r-
j=0
Then a; S A if and only if
ao
+
<
r-
1 ー
b
b
pd
Op
+
A
+
r-
r-1
A
A(r
r-1
+
0o(r 1) + b
log
A(r-1)+
co(r-1)+6
i
logr
So is the largest integer smaller than or equal to the RHS of the above.
E DISCUSSION ON STABILIZATION CONSTANT Y
In Theorem [. we showed that Decorrelated AdaGrad-Nome exhibits a quadratic dependence on A, L1 in the dominating term of its convergence rate, so that the number of iterations required to find an e-stationary point is Q LiA" which covers the standard protocol in practice of choosing y to be a small constant, e.g. ? = le However, it is natural to ask whether result extend to any choice of y.
This result depends on the condition S ((AL))
In this section, we answer this question in the deterministic setting, that is, with o = 0, we show that the lower bound of Theorem can recovered even the condition 7 < Ó(LL,) is removed. This shows that (deterministic) Decorrelated AdaGrad- Norm cannot recover the optimal complexity from the smooth (deterministic) setting, no matter the choice of 7. This result is stated below.
Theorem 8. Denote Fan Fas(A, Lo, LI,0), and let algorithm ADAN denote Decorrelated AL
AdaGrad-Norm (Equation with parameters 7 > O. Let O < e S min
If
2
AL 2
Lo. then
A2TA ?
(AAaN, c) 2 á
The proof structure similar as Theorems and 3 by splitting into cases depending on the choice of and y. However, for this proof we split into slightly differently than in these three theorems; here, the cases are determined by the magnitude of n and 7/1, The proof relies on Lemma for one case and reuses the hard instance of Lemma for the other.
50

---

Published as a conference paper at ICLR 2025
Proof. We consider two cases: In the first case, both of the following hold:
ALI
2 1/41 and
7/0 S
(65)
8 log
1+
48AL;
Lo
In the second case, one or both of these two conditions fail:
A1i
" 1/L1
7/1
(66)
8 llg
1
48AL2
Lo
We will show that in the first case, there exists objective for which Decorrelated AdaGrad-Nomm will never converge, and the second case, there exists an objective for which convergence requires C 2 iterations.
Case This case is the simpler of the two, since we can directly apply Lemma 5 The conditions of this lemma are immediately satisfied by the conditions of this case. Therefore, in Case 1, there exists an objective (f.g. D) E Fact such that fxx))l 2 AL for 2
Case 2 For this case, will reuse the hard instance from Lemma
g
Denoting
L log (1 4 the objective is defined as
c(x + m) + (m)) b(x) c(x - m) + +mm)
-m [-m, m]
[x)
x > m
where
Lo 1b(xx) (exp(Li L1 | 1). T
With 9, D defined so that g(r, E) (x) almost surely when & D, was already shown in the the initial point 2ng
proof of Lemma that ( Faet, when
Letting 24 be the sequence of iterates generated by Decorrelated AdaGrad-Norm, we define to = max {t 2 0 x,, m). Notice that (z) for all 2 m, the definition of implies that [f(())) for all t S to- Accordingly, we want to show that
tu 2 á A
Actually, the trajectory of Decorrelated AdaGrad-Nomi for this objective is identical to that of Decorrelated AdaGrad, since the objective's ' domain oie-dimensional. Therefore, to analyze the trajectory 24, can reuse the analysis from the proof of Lemma 8 Starting from Equation 22
to
V/2 Ege
41JE
27
Using the assumed upper bound on
A
65
4n
An
2
<
4m
6 <
27
8ne
to
4/2 + tue
8ne2
80
> AV + eto
64
> 2272 +222
1 > 2272
+ 2
64
64722
51

---

Published as a conference paper at ICLR 2025
Denoting b
Aa 64
and
A²72 64ype4
this gives the quadratic inequality
f blg c 0.
Since to > 0, this implies
+ 02 4c
A
D7
to
+ Vc
(67)
2
12
STE²"
Finally, we apply the conditions on 7) and 7/n from the case analysis. We know that either
Ali
7 1/4 or 7/12
(68)
8 8log
+
18AL?
Lo
1n S 1/L1, then Equation 67 implies
2
A
to 2
128n 2 2
2
On the other hand, if
Ali
7/1 2
8 blog
+
182L3 Lo
then Equation 67 implies
Ay to
2
81ye
64c² log
[1+
48244 La
Either way, we have
ALL
to 2 52
which finishes the analysis for Case 2.
Putting The Cases Together The case analysis above shows that, no matter the choice of y, ?-- there always exists some objective (J.g, D) E Fert such that the number of iterations to find
e-stationary point is at least
A 1. á2
2
52


Reviews:
[{"review_id": "Q3NCK01KxC", "reviewer": "Reviewer_sfBG", "summary": "This paper analyzes complexity lower bounds for AdaGrad variants under $(L_0, L_1)$-smoothness conditions. The investigation includes Decorrelated AdaGrad (in both norm and coordinate-wise versions), as well as AdaGrad and SGD with current step-based adaptive stepsizes. A key finding is that optimization under $(L_0, L_1)$-smoothness is fundamentally more challenging than standard $L$-smoothness, as evidenced by lower bounds showing quadratic dependence on constants rather than the linear dependence on $L$ and $\\Delta$ typically seen in $L$-smooth settings.", "questions": "Could the author clarify the points in Weakness? If there are misunderstandings in these comments, I would like to increase my score.\n\nUpdate: After reading the author’s response, my first major concern was addressed. However, the second concern persists. The lower bound in Theorem 2 may be vacant when $\\\\gamma$ is allowed to be tuned. I have adjusted my score accordingly.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-written, easy to follow, and well-organized.\n- The problem it investigates is interesting and important to the study of adaptive algorithms in non-convex settings, given that the discussion of constant dependence in non-convex and $(L_0, L_1)$-smoothness settings is still not rich.\n- The results are novel and provide some theoretical insights into adaptive gradient algorithms.", "weaknesses": "The reviewer has two major concerns about this paper:\n\n- The definition of $(L_0, L_1)$-smoothness (Assumption 1) differs from most existing work in this topic ($(L_0, L_1)$-smoothness). Assumption 1 says the inequality holds for any $x$ and $y$. Essentially, for any $y$, we can set $x$ to be a stationary point and, without loss of generality, assume this point is the origin. This implies that $\\\\|\\nabla f(y)\\\\| \\leq L_0 \\\\|y\\\\|$, which means the growth of $\\\\nabla f(y)$ is linear. I guess this is $L$-smoothness.\n- Another major concern is the restriction of hyper-parameter selection in the lower bounds. In Theorems 1 and 3, parameter $\\gamma$ is required to be small. In Theorem 2, $\\\\gamma$ appears in the lower bound. While it’s understandable that a small $\\gamma$ may be practical, shouldn’t lower bounds typically be related to the best algorithm within a family of algorithms? Parameter tuning should be allowed if one want to explore the limits of an algorithm family. In this case, I’m not sure how insightful these results are, particularly Theorem 2.\n\nOther concerns are relatively minor:\n\n\n- As mentioned in the limitation section, the lower bound for AdaGrad feels weak because it doesn’t depend on $\\\\sigma$, especially the $1/\\\\epsilon^4$ term. Lower bounds for the original AdaGrad should be more interesting than the decorrelated ones, which are not commonly used in practice but are primarily for analytical convenience. However, the difference in lower bounds would also be interesting if there are fundamental differences between decorrelated and the original versions, as mentioned in the paper, “so that the update size of AdaGrad is not as sensitive to noise as the decorrelated counterpart.” However, from the existing upper bounds, it doesn’t seem so.\n- The lower bound for Single-step Adaptive SGD is also weak due to the affine-noise assumption. Therefore, we cannot compare it to existing rich upper bounds for algorithms like gradient clipping, which usually assume bounded noise or bounded variance.", "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": "", "extra_scores": {}}, {"review_id": "VccVQIpFPE", "reviewer": "Reviewer_Smgh", "summary": "This paper investigates the theoretical lower bounds for finding $\\epsilon$-stationary points using adaptive gradient algorithms under $(L_0,L_1)$-smoothness. With the assumption of bounded noise, the authors prove that the complexities of AdaGrad and its variants have a greater dependency on the problem parameters $\\Delta$, $L_0$, $L_1$ compared to their $L$-smooth counterparts.", "questions": "**Typos and minor suggestions:**\n\nLine 81: the theorem for AdaGrad should be \"Theorem 3\".\n\nLine 287: Table 1 provides the result of AdaGrad-Norm under affine noise, which is not equivalent to Equation 5.\n\nLine 746: the logic of Equation 7 is not easy to comprehend at first glance, as it appears to tighten the condition for $\\ell_{t}\\geq 4 m_{t+1}$. I suggest that the authors should explicitly point out this relationship.\n\nLine 774: \"$\\log x\\leq 1+x$\" -> \"$\\log(1+x)\\leq x$\".\n\nLine 797: missing explanation for step (i).\n\nLine 908: \"$\\mathbf{x}_t$\" -> \"$\\mathbf{x}$\".\n\nLine 927-929: \"$L$\" -> \"$L_0$\".\n\nLine 958-959: missing \\\\rangle for $\\langle\\mathbf{x}_i,\\mathbf{e}_j\\rangle$.\n\nLine 1012: \"$t\\geq 1$\".\n\nLine 1134: \"Lemma 1\" -> \"Lemma 2\".\n\n\n\n**Questions:**\n\n* We note that Assumption 1 is generally less rigid than the typical assumption proposed by Zhang et al. (2019). Specifically, Assumption 1 aligns with the $\\mathcal{L}^*_{\\mathrm{asym}}$ function class introduced by Chen et al. (2023). Nonetheless, the lower bounds established in this paper should still hold under the typical assumption.\n* Since the constructive proof of Lemma 2 is rather complicated, I encourage the authors to provide necessary remarks following the presentation of the results. Specifically, we are interested in how the higher dependency on $\\Delta$ and $L_1$ emerges in the dominant term $\\mathcal{O}(\\Delta^2L_1^2\\sigma^2\\epsilon^{-4})$. The same applies to Lemma 4.\n* In Line 484, the authors state that \"the lower bound goes to $0$ when $\\sigma_2\\rightarrow 1$\". However, the dominant term $\\mathcal{O}(\\Delta L_0\\sigma^2\\epsilon^{-4})$ does not approach zero, as $\\sigma_1>0$.\n* I encourage the authors to discuss the results of Li et al. (2023). They provide analyses for Adam under relaxed assumptions, which covers the case of $(L_0,L_1)$-smoothness.\n\n\n\nReferences:\n\nJingzhao Zhang, Tianxing He, Suvrit Sra, Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019.\n\nZiyi Chen, Yi Zhou, Yingbin Liang, Zhaosong Lu. Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization. In Proceedings of the 40th International Conference on Machine Learning, 2023.\n\nHaochuan Li, Alexander Rakhlin, Ali Jadbabaie. Convergence of Adam Under Relaxed Assumptions. In In Advances in Neural Information Processing Systems 35, 2023.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "In my opinion, these results reveal the potential difficulty of adaptive methods under relaxed smoothness and add to the current understanding within the community.", "weaknesses": "The primary weakness of this paper is that the analysis is heavily relies on update policies similar to AdaGrad. Although the authors do investigate the behavior of adaptive SGD, they assume the noise has a less common affine property, and their results do not extend to popular variants of Adam.", "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": "", "extra_scores": {}}, {"review_id": "PDKTb1mI8X", "reviewer": "Reviewer_BkD6", "summary": "This paper studies the complexity **lower bounds** for certain adaptive gradient (descent) algorithms for non-convex optimization problems under relaxed smoothness assumptions, i.e., the objective function $f$ is continuously differentiable and $(L_0, L_1)$-smooth as stated in assumption 1. More specifically, the results are in Table 1 (line 77-84). From 4 lower bounds derived for AdagGad variants, the paper concluded that the Adagrad-type algorithms cannot converge under relaxed smoothness **without** a higher-order polynomial complexity that depends on the problem parameters $\\nabla, L_0, \\sigma, L_1, \\epsilon$.", "questions": "- Assumption 2 appears to be rather strong. Are there existing references that support the validity of these assumptions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The presentation of this paper is well-structured. For example, it effectively presents the related complexity upper bounds in Table 1 and provides clear proof intuitions along with key takeaways for each theorem.\n- The results of this paper indicate that for decorrelated AdaGrad-Norm, the algorithm cannot achieve the optimal complexity attainable under a stronger smoothness assumption. This finding suggests a meaningful performance gap between $L$-smooth and $(L_0, L_1)$ smoothness conditions.", "weaknesses": "- As noted in the limitations, decorrelated AdaGrad is not commonly used in practice; therefore, proving a lower bound for decorrelated AdaGrad may lack significant technical novelty.", "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": "", "extra_scores": {}}, {"review_id": "rbr9SH8bmB", "reviewer": "Reviewer_Bg2B", "summary": "Recent advances in theory and optimization of transformers and particularly adaptive algorithms have shed light on a new type of assumption called $(L_0, L_1)$-smoothness. This paper proposes novel non-convex lower bound instances satisfying the $(L_0, L_1)$-smoothness condition for various types of adaptive algorithms including (decorrelated) AdaGrad and AdaGradNorm. The results show an iteration complexity lower bound of $\\Omega(\\Delta^2 L_1^2 \\epsilon^{-4})$ (naive, omitting $\\sigma, \\gamma$) to achieve stationarity in expectation, which shows a gap with previous results on $L$-smooth functions. The paper also provides a new lower bound for a class of single-step adaptive SGD algorithms in terms of an iteration complexity lower bound of $\\Omega(\\Delta L_0 \\epsilon^{-4})$ (naive) to achieve stationarity with high probability.", "questions": "- In Theorem 1, the proof uses a 1-dimensional instance for the large $\\eta$ case and a large dimensional instance for the small $\\eta$ case. The $T = \\Theta(\\epsilon^{-4})$ condition for the latter case results in a dimension of $d = \\Omega(\\epsilon^{-4})$ as stated in W1. On the other hand, in Theorems 2 and 3, the proof is quite the opposite: it uses a $d \\ge T$ dimensional instance for the large $\\eta$ case which does NOT have requirements like $T = \\Theta(\\epsilon^{-4})$, and a 1-dimensional instance for the small $\\eta$ case. Why can’t we use a similar approach to DAN to avoid high dimension requirements, or what are the technical difficulties in doing so?\n- In Theorem 3, the lower bound holds when $\\gamma \\le \\sigma$, but the rates themselves do not contain $\\gamma, \\sigma$ anywhere, which is probably because they cancel out somewhere if we follow the same procedure as the proof of Theorem 2. Then what can we say about the case of $\\gamma > \\sigma$ for now? By definition of AdaGrad (without decorrelation), I reckon that we must choose a not-too-small $\\gamma$ so that the first step of the algorithm doesn’t ‘explode’, and I’m just curious about what behavior we could see or expect from this lower bound instance if we send the noise to zero for a fixed $\\gamma > 0$. (The ‘better noise-dependency’ argument of AdaGrad over DAG is also true only when $\\gamma \\le \\sigma$.)\n- Why exactly does Theorem 4 derive iteration complexity lower bounds in terms of high probability (instead of expectation)? Are they just completely different results, or is this sort of a stronger result than getting lower bounds in terms of expectation (from the same instance)? (I think the two types of bounds are fundamentally different in general, but I’m asking this because the approach towards getting the lower bound instance with $\\| \\nabla f(\\boldsymbol{x}_t) \\| \\ge \\epsilon$ seems to share quite a similar spirit with those of Theorems 1-3.)\n- Light Question: Is it possible to obtain other lower bound results analogous to Theorem 4 if we focus on the (stronger) bounded-noise assumption?\n- Light Question: Can you compare Theorem 4 with the upper bounds in Section 7 of Gorbunov et al. (2023) which also has a few results assuming the finite-sum oracle setting? For SGD-PS (Algorithm 6, Gorbunov et al. (2023)), is this algorithm incomparable with the lower bound because it uses the values $f_i(\\boldsymbol{x}^{\\star})$ in the step sizes?\n- **Small Typos.** In p.17, I think we should remove the subscript $t$, as in $f(\\boldsymbol{x}) = \\epsilon \\langle \\boldsymbol{x}, \\textbf{e}_1 \\rangle + \\sum\\_{i=2}^T h_i ( \\langle \\boldsymbol{x}, \\textbf{e}_i \\rangle ) $.\n    \n    In p.18, $j(\\boldsymbol{x}) = i+2$ $\\Rightarrow$ $j(\\boldsymbol{x}_i) = i+2$.\n    \n    In p.21, $D_1 \\le \\dots \\le \\Delta/6 + \\Delta/6 + \\Delta/6 = \\Delta/2$, and some constants after this part should be slightly modified according to this.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper suggests novel lower bounds through diligent combinations of previous lower bound techniques.\n- The overall writing is clear and easy to follow (except for only a few parts and bits of typos), and the proofs in the appendices are also organized well.\n- The paper relevantly compares results with previous literature, provides rich discussion points, and is transparent about limitations.", "weaknesses": "- The lower bounds in Theorem 1 require high dimensions like $d = \\Omega(\\Delta^2 L_1^2 \\sigma^2 \\epsilon^{-4})$ which is quite large and implies that, for a fixed $d$, the proposed lower bound can only cover up to a finite range of $T$.\n- As pointed out in the paper, the results (especially Theorems 1-3) are for specific algorithms rather than a class of algorithms. Although it seems that it will be quite difficult, it could be interesting to see if the lower bound results can extend to a *class* of Adam-type algorithms (Chen et al., 2019).\n- This is a minor thing, but I think Section 6 and Theorem 4 could be organized better. It is hard to get what the new constants exactly are without reading Appendix C.1, especially the constants involving $\\zeta$. IMHO, it would have been a bit easier to understand if the details about the constants (including the random walk parts) were all in the former part of Section 6. (I reckon that it was written this way just for now because of the page limit.)", "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": "", "extra_scores": {}}, {"review_id": "nqVGKWNKAi", "reviewer": "Reviewer_AVzC", "summary": "This paper investigates the complexity of adaptive optimization algorithms in non-convex stochastic settings under $(L_0,L_1)$-smoothness assumption. The study addresses an open question regarding whether the complexity of these adaptive algorithms, which typically have higher-order dependencies on problem parameters, can be tightened.\n\nThe authors establish complexity lower bounds for different variants of AdaGrad, focusing on the dependency on parameters $Δ$, $L_0$, and $L_1$. They provide:\n- A complexity lower bound for the Decorrelated AdaGrad-Norm variant.\n- A lower bound for Decorrelated AdaGrad under specific hyperparameter conditions.\n- A lower bound for SGD with a broad class of adaptive stepsizes.\n\nThe findings of the paper show that, for certain adaptive algorithms, the $(L_0, L_1)$-smooth setting is fundamentally more difficult than the standard smooth setting.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is clearly structured, with each theorem building on the previous results to form a coherent narrative.\n\n- The theoretical contributions are solid, with clear mathematical rigor and well-constructed complexity bounds. By investigating multiple AdaGrad variations, the paper thoroughly explores different adaptive step-size strategies under non-standard conditions.\n\n- The results significantly contribute to the understanding of optimization in non-convex and non-smooth settings, highlighting limitations of popular adaptive methods when applied to challenging optimization landscapes.", "weaknesses": "N/A", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)