Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness

Michael Crawshaw; Mingrui Liu

REVIEW 2 major objections 5 minor 1 cited by

Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Under relaxed smoothness, the paper proves Decorrelated AdaGrad-Norm needs at least Ω(Δ²L₁²σ²ε⁻⁴) stochastic gradient queries to find an ε-stationary point — a quadratic penalty in gap and smoothness that clipped SGD escapes.

desk verdict Solid and genuinely useful lower-bound work, but Theorem 1 has a load-bearing smoothness gap in the divergence construction that needs repair before the main claim is established. read the letter →

arxiv 2505.04599 v1 pith:TVRRAMPH submitted 2025-05-07 cs.LG math.OC

Michael Crawshaw , Mingrui Liu This is my paper · ORCID

classification cs.LGmath.OC MSC 90C2690C6068Q25

keywords relaxedsmoothness(L0L1)-smoothnessAdaGrad-Normadaptivegradientmethodsnon-convexstochasticoptimizationcomplexitylowerboundsstabilizationconstant

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Recent convergence guarantees show AdaGrad-type methods can find an $\epsilon$-stationary point under relaxed $(L_0,L_1)$-smoothness, but at rates that are higher-order polynomials in the problem parameters rather than the optimal $\Theta(\Delta L \sigma^2 \epsilon^{-4})$ that SGD achieves under ordinary smoothness. This paper asks whether those polynomial dependencies can be tightened and answers no for several AdaGrad variants: its main result is a lower bound of $\Omega(\Delta^2 L_1^2 \sigma^2 \epsilon^{-4})$ stochastic gradient queries for Decorrelated AdaGrad-Norm under bounded noise, and it gives similarly quadratic lower bounds for Decorrelated AdaGrad, the original AdaGrad, and single-step adaptive SGD. A sympathetic reader cares because the bounds match the best known upper bounds in two of three dominating terms, leaving a narrow, noise-controlled gap, and because SGD with gradient clipping provably attains the classical $\Delta L_0 \sigma^2 \epsilon^{-4}$ rate in the same setting — so a simple clipped method beats these adaptive optimizers there. The paper's own reading is that, for certain adaptive algorithms, the relaxed-smooth setting is fundamentally more difficult than the standard smooth setting in terms of the initial optimality gap and the smoothness constants.

What carries the argument

The argument is carried by a two-regime construction, split on the step-size coefficient $\eta$. In the divergence regime ($\eta \ge 1/L_1$), the hard objective is pieced together from $\psi(x) = (L_0/L_1^2)(\exp(L_1|x|) - L_1|x| - 1)$, the fastest-growing one-dimensional function allowed by $(L_0,L_1)$-smoothness since $|\psi''(x)| = L_0 + L_1|\psi'(x)|$; prescribing gradient magnitudes that grow like $\Theta((t \log t)^t \Delta L_1)$ makes the normalized update jump across valleys while keeping $\|\nabla f(x_t)\| \ge \Delta L_1$ for every step. In the slow-convergence regime ($\eta \le 1/L_1$), a high-dimensional objective adapted from the classical smooth-setting lower bound keeps the true gradient at magnitude $\epsilon$ in coordinate one while bounded noise lands in fresh coordinates; because Decorrelated AdaGrad-Norm divides every coordinate by the same accumulated norm, the noise shrinks the effective learning rate on the $\epsilon$-gradient direction. For coordinate-wise variants the same $\psi$-valley jump is executed coordinate by coordinate with one noisy coordinate per step, and for single-step adaptive SGD the proof classifies step-size functions by 'tricky pairs' — two anti-parallel stochastic gradients whose step-size products are comparable — turning the trajectory into a biased random walk that diverges with constant probability unless the step size is so small that convergence is slow.

What would settle it

A direct falsifier: exhibit an $(L_0,L_1)$-smooth objective with bounded noise on which Decorrelated AdaGrad-Norm, for some valid $\gamma \le \tilde{O}(\Delta L_1)$, reaches an $\epsilon$-stationary point in $o(\Delta^2 L_1^2 \sigma^2 \epsilon^{-4})$ gradient queries; the paper's two-case argument implies no such instance exists, so a single counterexample would refute Theorem 1. A sharper test isolates the weakest premise: run the same construction family under stochastic noise with $\gamma$ much larger than $\tilde{O}(\Delta L_1)$ — if the algorithm then escapes the claimed bound, the stabilization-constant restriction is doing real work, whereas the deterministic analogue (Theorem 8) already covers that regime.

Watch

Extended reading notes

Core claim

The central claim is that under $(L_0,L_1)$-smoothness with bounded stochastic gradient noise, the worst-case number of stochastic gradient queries Decorrelated AdaGrad-Norm needs to find an $\epsilon$-stationary point is $\tilde{\Omega}(\Delta^2 L_1^2 \sigma^2 \epsilon^{-4} + \Delta L_0 \sigma^2 \epsilon^{-4} + \Delta^2 L_1^2 \epsilon^{-2})$: the iteration count grows quadratically in the initial optimality gap $\Delta$ and the relaxed-smoothness constant $L_1$, so the algorithm cannot recover the optimal $\Theta(\Delta L \sigma^2 \epsilon^{-4})$ of the classical $L$-smooth setting. The bound holds for every step-size coefficient $\eta$ through a two-case construction: large $\eta$ forces divergence on an exponentially growing objective whose gradients outpace the shrinking AdaGrad denominator, and small $\eta$ traps the algorithm on a high-dimensional stochastic objective whose noise deflates the shared learning rate. The paper extends the template to coordinate-wise AdaGrad variants, obtaining $\Omega(\Delta^2 L_0^2 \sigma^2 \gamma^{-2} \epsilon^{-4})$ for Decorrelated AdaGrad and $\Omega(\Delta^2 L_0^2 \epsilon^{-4})$ for AdaGrad proper, and to single-step adaptive SGD under affine noise, where a biased random-walk construction yields nearly quadratic dependence on $\Delta$ and $L_1$. The lower bounds are stated in expectation (Theorems 1–3) and with high probability (Theorem 4), and the deterministic case retains the quadratic term $\Delta^2 L_1^2 \epsilon^{-2}$ with the $\gamma$ restriction removed. The authors interpret the collection as showing that relaxed smoothness is fundamentally harder than standard smoothness for these adaptive methods, with clipped SGD as the outperforming baseline.

Load-bearing premise

The load-bearing premise is that the stabilization constant $\gamma$ is at most $\tilde{O}(\Delta L_1)$; both halves of the Theorem 1 construction control the step-size denominator relative to this threshold, and if $\gamma$ is chosen larger the stochastic lower bound is not established — the paper removes the restriction only in the deterministic case, $\sigma = 0$ (Appendix E).

Editorial extensions

If this is right

Decorrelated AdaGrad-Norm cannot recover the smooth-setting optimal rate $\Theta(\Delta L \sigma^2 \epsilon^{-4})$ under relaxed smoothness; its worst-case query count is quadratic in $\Delta$ and $L_1$.
The main lower bound matches the existing AdaGrad-Norm upper bound in two of its three dominating terms, so the remaining gap reduces to a $\sigma$-dependent third term.
SGD with gradient clipping attains $\Delta L_0 \sigma^2 \epsilon^{-4}$ in the same relaxed-smooth setting, so a simple clipped method provably outperforms the studied adaptive algorithms there.
The slowdown is not a noise artifact: for $\sigma = 0$ the lower bound is $\tilde{\Omega}(\Delta^2 L_1^2 \epsilon^{-2})$ and it holds for every choice of $\gamma$, not just small ones.
The original AdaGrad also incurs a quadratic lower bound $\Omega(\Delta^2 L_0^2 \epsilon^{-4})$, which exceeds the smooth-optimal complexity whenever $\Delta$ or $L_0$ is large relative to $\sigma$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural extension, untested here, is to test whether Adam and AdamW inherit or escape the quadratic dependence; the paper leaves them open, and its two-regime template would predict the answer depends on whether their bias-corrected denominators still deflate with accumulated feedback in the same way.
The proofs isolate the decorrelated step size — excluding the current gradient from the denominator — as the noise amplifier: the Decorrelated AdaGrad bound exceeds the plain AdaGrad bound by a factor $\sigma^2/\gamma^2$, hinting that non-decorrelated practical variants may be less noise-sensitive than the paper's strongest negative results.
A transferable prediction from the machinery: any normalization scheme whose step size shrinks monotonically with accumulated squared gradient norms will inherit the quadratic dependence, whereas methods that clip each gradient without accumulation (like clipped SGD) will not; this could be checked by adapting the paper's constructions to RMSProp-style updates.
The $\gamma \le \tilde{O}(\Delta L_1)$ restriction gestures at a possible escape for practitioners — a very large stabilization constant might bypass the stochastic lower bound; building a stochastic hard instance valid for arbitrary $\gamma$ would settle whether that escape is real.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the paper is a real step forward on lower bounds for adaptive methods under (L0,L1)-smoothness. Theorems 2–4 look sound on inspection. But the central result, Theorem 1, has a genuine gap: the hard instance in Lemma 5 is not C^1 at the internal breakpoints of the phi_t pieces, so it lies outside the problem class Fas. The issue is concrete. At x = m_t + m_{t+1}, the left derivative is psi'(m_{t+1}) = g_{t+1}, and the right derivative is the linear slope g_t. Since g_{t+1} > g_t, phi_t is not differentiable there, and the assembled f inherits the failure. The proof only checks continuity and differentiability at the piece boundaries d_t, not at these interior points. This matters: the divergence case of Theorem 1 (eta >= 1/L1) relies on Lemma 5, so as submitted the theorem is not established for large eta. The fix looks straightforward — replace the linear slope g_t with g_{t+1} and adjust the constant accordingly — and since the trajectory never queries that segment, the argument should survive. But it has to be done, not assumed. What the paper does well: the constructions for Decorrelated AdaGrad and AdaGrad (Theorems 2 and 3) are different from the broken one and appear sound. The high-dimensional noise-injection trick is clever, and Theorem 4's adaptive-SGD bound is a genuine contribution. The related-work table is useful, and the self-citations are for context and prior upper bounds, not load-bearing. Other soft spots are minor by comparison. The gamma <= O~(Delta L1) restriction on Theorem 1 is real and load-bearing; Appendix E removes it only for sigma = 0. There are also mechanical typos in the appendix. The reader's report is fair on the overall structure but too generous on Theorem 1; the C^1 issue is not a typo. This paper is for researchers working on complexity of adaptive optimization. It deserves a serious referee, but only for a revised version. Recommendation: send to peer review, and require the Lemma 5 construction to be fixed and the theorem restated accordingly before acceptance.

Referee Report

2 major / 5 minor

Summary. The paper derives worst-case query-complexity lower bounds for several adaptive gradient algorithms under (L0, L1)-relaxed smoothness. For Decorrelated AdaGrad-Norm it claims an Ω(Δ²L1²σ²/ε⁴) bound under bounded noise (Theorem 1); for Decorrelated AdaGrad and AdaGrad it claims Ω(Δ²L0²σ²/(γ²ε⁴)) and Ω(Δ²L0²/ε⁴) (Theorems 2-3); and for single-step adaptive SGD it claims an almost-quadratic bound under affine noise (Theorem 4). The proofs split into divergence cases for large step-size coefficients and slow-convergence cases for small coefficients, using hard instances built from exponential ψ functions and high-dimensional constructions adapted from Drori and Shamir. An appendix removes the γ ≤ O(ΔL1) restriction in the deterministic setting.

Significance. If correct, these results would be the first lower bounds showing that AdaGrad-type methods cannot recover the ΔL0σ²ε⁻⁴ rate of the smooth non-convex setting under relaxed smoothness, complementing the AdaGrad-Norm upper bounds of Wang et al. The paper's strengths are the explicitness of the hard-instance constructions, the care in separating divergence and slow-convergence regimes, and the candid discussion of limitations, including that the strongest bounds hold for decorrelated variants. The central claim is interesting and plausible, but one load-bearing construction in the proof of Theorem 1 is currently not admissible, so the main result is not established as submitted.

major comments (2)

[Appendix A, Lemma 5 (main-text Lemma 1)] The constructed hard instance is not an element of F_as because each φ_t is not continuously differentiable at its internal breakpoints. For the first internal breakpoint x = m_t + m_{t+1}, the left derivative is ψ'(m_{t+1}) = g_{t+1}, while the right derivative of the middle linear piece is g_t; since the sequence g_t is strictly increasing, these do not agree. The same mismatch occurs at the second breakpoint x = ℓ_t − 2m_{t+1}, where the left derivative is g_t and the right derivative is −ψ'(−m_{t+1}) = g_{t+1}. The proof only verifies differentiability at the boundaries between the pieces φ_t, not at these internal breakpoints, so the assembled f is not C^1 and violates Assumption 1(2). Consequently the divergence case η ≥ 1/L1 of Theorem 1 is not established; the theorem currently holds only for η ≤ 1/L1 via Lemma 6. Appendix E relies on the same lemma in Case 1 and inherits the gap. The construction appears repairable by replacing the slope g_t of the middle linear piece (and the corresponding constant g_t(ℓ_t − 3m_{t+1} − m_t)) with g_{t+1}, which would make the one-sided derivatives agree without changing the queried gradient sequence; this repair is not a formality, however, and must be carried through the proof.
[Appendix C, Lemma 13] Lemma 13 as stated omits a condition on ε that its proof requires. The proof concludes with f̂(x0) − inf ≤ 3ε²/(2L0) + Tε⁴/(L0σ1²), then substitutes T = ΔL0σ1²/(2ε⁴) and uses ε ≤ sqrt(ΔL0/3) to obtain a value at most Δ. The main theorem, however, only assumes ε ≤ sqrt(ΔL0/2), which is insufficient: with this larger bound the term 3ε²/(2L0) can be as large as 3Δ/4, so the total can exceed Δ. The first term ΔL0σ1²/ε⁴ of Theorem 4 is therefore not established for the full stated ε-range. This is a constant-level condition mismatch and can be fixed by strengthening the ε bound in Theorem 4 or by scaling the constant in T, but as written the proof has a gap.

minor comments (5)

[Appendix A, Theorem 5 proof] The case split contains a typo: the first displayed condition "If η ≤ 1/L1" should read "If η ≥ 1/L1" for the divergence argument, and the second occurrence should keep η ≤ 1/L1. Also, "‖∇f(xt)‖ ≥ ΔL0 > ε" should read "‖∇f(xt)‖ ≥ ΔL1", since the gradient is lower bounded by ΔL1 in that construction.
[Theorems 2 and 3] The equation references are swapped: Decorrelated AdaGrad is Equation (3), not Equation (2), and AdaGrad is Equation (2), not Equation (3).
[Theorem 2 statement] The statement in the main text writes T(ADA, F, ε), while the proof in Appendix B proves the high-probability version T(ADA, F, ε, δ); the notation should be aligned.
[Appendix A, Lemma 6] In the displayed unrolling of ⟨x_{t+1}, e1⟩, the summation index is written as α_t instead of α_i; this is a typographical error in an otherwise clear induction.
[Appendix A, Lemma 5] The proof defines j(x) = max{t ≥ 0 : d_t ≤ x}, which requires that d_t → ∞; this follows from the lower bound ℓ_t ≥ 4m_{t+1} and growth of m_t, but the argument is only implicit and would benefit from a one-sentence justification.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower-bound hard instances are constructed in the paper and all load-bearing lemmas are proved from Assumptions 1–2; self-citations are contextual.

full rationale

The paper's central claims are worst-case query-complexity lower bounds for specific adaptive algorithms over explicit problem classes. The difficult instances are built from scratch in Lemmas 5–6 (Theorem 1), Lemmas 7–8 (Theorems 2–3), and Lemmas 9–13 (Theorem 4), and each instance is then explicitly verified to satisfy the stated assumptions (bounded below, (L0,L1)-smooth, unbiased and noise-bounded stochastic gradients). The complexity measure T(A,F,ε) is the standard worst-case expected number of gradient queries and is not assumed in the construction. For example, Theorem 5 splits on whether the step-size coefficient satisfies η≥1/L1 or η≤1/L1 and exhibits, in each case, an admissible instance on which the gradient norm never drops below ε for the claimed number of steps. No fitted parameter is renamed as a prediction, and no part of the conclusion is used as an input to the construction. Self-citations (e.g., Crawshaw et al., 2022; Crawshaw et al., 2023a;b; Liu et al., 2022) appear in related-work discussion and as methodological motivation; the load-bearing arguments are new and proved in the appendices, with independent external machinery such as Drori & Shamir (2020) and Arjevani et al. (2023) used where standard results are needed. The paper's own stated limitations — e.g., that the strongest lower bounds are for decorrelated AdaGrad variants, and that Theorem 1 requires γ≤O~(ΔL1) in the stochastic case — are scope restrictions, not circular steps; Appendix E explicitly removes the γ condition in the deterministic setting. Even the possible non-differentiability concern in the piecewise construction of Lemma 5 would be a correctness defect, not circularity, because a repair would still leave the hard instance independent of the claimed conclusion. Overall, the derivation is self-contained against external benchmarks and no prediction reduces by construction to its inputs.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new postulates or fitted constants. It constructs explicit hard instances (piecewise exponential functions and coordinate-noise oracles) within the standard (L0,L1)-smooth framework. The complexity measure is the standard worst-case expected or high-probability query count.

assumptions (3)

domain assumption Assumption 1: f is bounded below with f(0) minus inf f less than or equal to Delta, is continuously differentiable and (L0,L1)-smooth, and the stochastic gradient is unbiased.
Defines the problem class F_as and is the setting for all lower bounds.
domain assumption Assumption 2 (Bounded-Noise or Affine-Noise): stochastic gradient noise is bounded almost surely by sigma or by sigma1 plus sigma2 times the gradient norm.
The lower bounds are stated for these noise classes; for Bounded-Noise the bounds transfer to the weaker Bounded-Var.
standard math Standard probability tools: optional sampling theorem, martingale convergence, convexity-based root existence (Lemmas 14 and 15).
Used in the random-walk analysis for the adaptive SGD lower bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness." pith.science (2026). https://pith.science/paper/TVRRAMPH

@misc{pith2026250504599,
  author       = {Pith},
  title        = {Pith review of: Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TVRRAMPH}},
  note         = {Machine review of arXiv:2505.04599}
}

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.

Figures

Figures reproduced from arXiv: 2505.04599 by the authors.

**Figure 1.** Objectives from Lemma 1. m := (ψ ′ ) −1 (∆L1) = 1 L1 log 1 + ∆L 2 1 L0 . Lemma 1. Suppose that ∆L 2 1 ≥ L0, η ≥ 1 L1 , and γ ≤ O˜(η∆L 2 1 ). Then there exists a problem instance (f, g, D) ∈ Fas(∆, L0, L1, 0) such that k∇f(xt)k ≥ ∆L1 for all t ≥ 0. The trajectory of the algorithm analyzed in Lemma 1 is informally pictured in Figure 1b. The objective function is a piecewise combination of copies of the function ψ(… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness
math.OC 2025-09 conditional novelty 6.0 of 10

DNSGD is a decentralized normalized stochastic gradient method for (L0,L1)-smooth nonconvex optimization, with complexity bounds that match standard smooth decentralized results when L1=0.

Reference graph

Works this paper leans on

51 extracted references · 41 canonical work pages · cited by 1 Pith paper

[1]

14 Published as a conference paper at ICLR 2025 Case 1 t =

work page 2025
[2]

Therefore, the effective learning rate of the algorithm at stept is ηt = η √ γ2 +∑ t−1 i=0 ‖F (xi,ξi)‖2 = η√ γ2 +t(ǫ2 +σ2) =αt+2

Further, the above implies ‖F (xi,ξi)‖2 =ǫ2 +σ2. Therefore, the effective learning rate of the algorithm at stept is ηt = η √ γ2 +∑ t−1 i=0 ‖F (xi,ξi)‖2 = η√ γ2 +t(ǫ2 +σ2) =αt+2. 18 Published as a conference paper at ICLR 2025 We can then verify the inductive hypothesis for step t + 1 by considering the coordinates of xt+1: ⟨xt+1, e1⟩ = ⟨xt −ηtF (xt,ξt), ...

work page 2025
[3]

We now bound the remaining constants

Here we choose p0 = p1 = 2 3 , and this satisﬁes p0,p 1 ∈ ( 1 2, σ2 σ2+1 ) . We now bound the remaining constants. For b0: b0 = (2p0 − 1)(1 −p0) 2p2 0ǫ (σ1 +σ2ǫ) + 1 −p0 p0 = 1 8ǫ (σ1 +σ2ǫ) + 1 2 ≥ σ1 8ǫ. 38 Published as a conference paper at ICLR 2025 Forb1: b1 = 1−p1 p1 ( σ1 + ( σ2 − p1 1−p1 ) G ) ((σ2 + 1)(2p1 −

work page 2025
[4]

Let 0<ǫ< min      ∆ L1 2 , /radicaltp /radicalvertex /radicalvertex √ ∆ L1σ 4 √ 2 log ( 1 + ∆ L2 1 L0 )      . If the parameters of Decorrelated AdaGrad satisfy η ≤ √ 2γ L1σ log ( 1 + L1ǫ L0 ) , then there exists some (f,g, D) ∈ F as(∆ ,L 0,L 1,σ ) such that ‖∇f (xt)‖ ≥ ǫ for all t ≤ ∆ 2L2 0σ2 256γ2ǫ4 + ∆ 2L2 1σ2 256γ2ǫ2 log2 ( 1 + ∆ L2 1 L0 ). ...

work page 2025
[5]

Let algorithmADAN denote Decorrelated AdaGrad-Norm with parameters η >0 and 0<γ ≤ ∆ L1 8 log ( 1 + 48 ∆ L2 1 L0 )

[Restatement of Theorem 1] Let ∆ ,L 0,L 1,σ > 0, and let F = Fas(∆ ,L 0,L 1,σ ). Let algorithmADAN denote Decorrelated AdaGrad-Norm with parameters η >0 and 0<γ ≤ ∆ L1 8 log ( 1 + 48 ∆ L2 1 L0 ). Let 0<ǫ ≤ min { √ 2 3 √∆ L0, 1√ 3 √∆ L1γ, ∆ L1 } . If ∆ L2 1 ≥L0, then T (ADAN, F,ǫ ) ≥ 1 + ∆ 2L2 1σ2 144ǫ4 + ∆ L0σ2 log(1 +σ2/γ2) 24ǫ4 + ∆ 2L2 1 144ǫ2. 21 Publi...

work page 2025
[6]

Near -optimal non-convex stochastic opti- mization under generalized smoothness

Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near -optimal non-convex stochastic opti- mization under generalized smoothness. arXiv preprint arXiv:2302.0603 ,

arXiv
[7]

Adaptive bound opti mization for online convex opti- mization

H Brendan McMahan and Matthew Streeter. Adaptive bound opti mization for online convex opti- mization. arXiv preprint arXiv:1002.4908 ,

arXiv
[8]

V ariance-reduced clipping for non-convex optimization

Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Ja dbabaie. V ariance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303.00883 ,

arXiv

Show all 51 references

[9]

Adagrad stepsizes: Sharp convergence over nonconvex landscapes

12 Published as a conference paper at ICLR 2025 Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research , 21(219):1–30,

2025
[11]

Suppose g ∈ Rd with ‖g‖ =ǫ

Suppose that 0<α (g)< 4 L1‖g‖ log ( 1 + L1 min(‖g‖, ∆ L1) L0 ) , (42) for allg ∈ Rd with ‖g‖ ∈ [ǫ,σ 1 + (σ2 + 1)∆ L1], and that there do not exist any (p,δ )-tricky pairs with respect toα. Suppose g ∈ Rd with ‖g‖ =ǫ. If σ2 ≥ 3, then α(g) ≤ ˜O ( 1 L1(∆ L1)1−γ2−γ3ǫγ1σγ2+γ3−γ1 1 ...

2025
[13]

If there exi sts any g ∈ Rd such that ‖g‖ ∈ [ǫ,σ 1 + (σ2 + 1)M ] and α(g) ≤ 0 or α(g) ≥ 4 L1‖g‖ log ( 1 + L1 min(‖g‖,M ) L0 ) , then there exists some problem instance (f,F, D) such that ‖∇f (xt)‖ ≥ ǫ for all t ≥ 0 (Lemma 9). If no such g exists, and there exist any tricky pai...

2025
[14]

(8) 15 Published as a conference paper at ICLR 2025 The RHS of Equation 7 can be bounded as 4 L1 log ( 1 + L1gt+1 L0 ) = 4 L1 log ( 1 + ∆ L2 1 L0 ( 576(t +

) . (8) 15 Published as a conference paper at ICLR 2025 The RHS of Equation 7 can be bounded as 4 L1 log ( 1 + L1gt+1 L0 ) = 4 L1 log ( 1 + ∆ L2 1 L0 ( 576(t +

2025
[15]

f is informally pictured in Figure 1b of the main text

With this deﬁnition, f is essentially a piece-wise function, where each piece is an interval [dt,dt+1] whose function value is a translation of φt. f is informally pictured in Figure 1b of the main text. Notice thatf is continuous and differentiable within each piece. At the b...

2025
[16]

Thereforef (x0) − infxf (x) ≤ ∆

The initial point x0 = 0 satisﬁes f (x0) = φ0(0) = ψ(−m0) = g0 L1 − L0 L2 1 log ( 1 + L1g0 L0 ) ≤ g0 L1 = ∆ . Thereforef (x0) − infxf (x) ≤ ∆ . Since each φt is (L0,L 1)-smooth, so is f . We will use a stochastic gradient g, D for this function which is always equal to the tru...

2020
[17]

Proof. Letd ≥T , and deﬁne f : Rd → R as: f (x) = ǫ⟨x, e1⟩ + T∑ i=2 hi(⟨xt, ei⟩), where hi(x) =    L0 2 x2 |x|< ai 2 −L0 2 (x −ai)2 + L0 4 a2 i |x| ∈ [ ai 2,ai ] L0 4 a2 i |x|>a i ai =αiσ αi = η √ γ2 + (i − 2)(ǫ2 +σ2) . 17 Published as a conference paper at ICLR 2025 To see...

2025
[19]

Actually,f does not satisfy this condition becausef is not even lower bounded, due to the linear term ǫ⟨x, e1⟩

The only remaining detail is whether the objective f satisﬁes the condition f (x0) − inf xf (x) ≤ ∆ . Actually,f does not satisfy this condition becausef is not even lower bounded, due to the linear term ǫ⟨x, e1⟩. Similarly to Drori & Shamir (2020), we instead argue that th er...

2020
[20]

Speciﬁcally, we need ˆf which is lower bounded and that satisﬁes: ∇ ˆf (xt) = ∇f (xt), ˆf (xt) = f (xt) for all 0 ≤t ≤T

If this happens, then the behavior of A when optimizing ˆf is the same as that of A when optimizing f , so the conclusion ‖∇ ˆf (xt)‖ =ǫ still holds. Speciﬁcally, we need ˆf which is lower bounded and that satisﬁes: ∇ ˆf (xt) = ∇f (xt), ˆf (xt) = f (xt) for all 0 ≤t ≤T . The e...

2020
[22]

First, recall the deﬁnition of ψ: ˜ψ(x) = L0 L2 1 (exp (L1|x|) −L1|x| − 1)

Proof. First, recall the deﬁnition of ψ: ˜ψ(x) = L0 L2 1 (exp (L1|x|) −L1|x| − 1). Then deﬁne f (x) = T∑ i=1 ψ(⟨x, ei⟩). To see thatf is (L0,L 1)-smooth, let x, y ∈ Rd. Denoting x = (x1,...,x T ) and y = (y1,...,y T ), ‖∇f (x) − ∇f (y)‖2 = T∑ i=1 (∇if (x) − ∇if (x))2 = T∑ i=1 ...

2025
[23]

Thenj(xt) = t + 2, so ⟨F (xt,ξt), et+2⟩ = ⟨∇f (xt), et+2⟩ + ⟨(2ξ − 1)σet+2, et+2⟩ = ˜ψ′(⟨xt, et+2) + (2ξ − 1)σ (i) = ˜ψ′(0) + (2ξ − 1)σ = (2ξ − 1)σ, where (i) uses Equation 19 from the inductive hypothesis. Therefore, for Decorrelated AdaGrad: ⟨xt+1, et+2⟩ = ⟨xt, et+2⟩ − η√ γ2...

2025
[25]

Therefore, with the initial point x0 =m + ∆ 2ǫ , the objective satisﬁes f (x0) − inf x f (x) = ǫ(x0 −m) +ψ(m) =ǫ ∆ 2ǫ + ∆ 2 = ∆

= L0 L2 1 ( 1 + L1ǫ L0 − log ( 1 + L1ǫ L0 ) − 1 ) = ǫ L1 − L0 L2 1 log ( 1 + L1ǫ L0 ) (i) ≤ ǫ L1 ≤ ∆ 2, where (i) uses the conditionǫ ≤ 1 2 ∆ L1. Therefore, with the initial point x0 =m + ∆ 2ǫ , the objective satisﬁes f (x0) − inf x f (x) = ǫ(x0 −m) +ψ(m) =ǫ ∆ 2ǫ + ∆ 2 = ∆ . W...

2025
[26]

If η ≥ √ 2γ L1σ log ( 1 + L1ǫ L0 ) , then by Lemma 3 there exists a problem instance for which Dec orrelated AdaGrad will never ﬁnd an ǫ-approximate stationary point

We ﬁrst consider Decorr elated AdaGrad. If η ≥ √ 2γ L1σ log ( 1 + L1ǫ L0 ) , then by Lemma 3 there exists a problem instance for which Dec orrelated AdaGrad will never ﬁnd an ǫ-approximate stationary point. Otherwise, by Lemma 4 there exists a problem instance for which Decorr...

2025
[27]

λ0(p,δ ) = inf {λ ≥ 0 : zp,λ ≤ 1 −δ} ζ(p,δ ) = λ0(p,δ ) −λ0(p, 0). (25) Informally,zp,λ is the probability that the random walk reaches a non-positi ve value, andλ0(p,δ ) is the smallestλ required to ensure that the chance of never reaching a non-po sitive value is at least δ....

2025
[28]

Recall the function ψ : R → R deﬁned as ψ(x) = L0 L2 1 (exp(L1|x|) −L1|x| − 1)

First, deﬁne ˜g := min( ‖g‖, ∆ L1) g ‖g‖ ,m := 1 L1 log ( 1 + L1‖ ˜g‖ L0 ) . Recall the function ψ : R → R deﬁned as ψ(x) = L0 L2 1 (exp(L1|x|) −L1|x| − 1). It is straightforward to verify thatψ bounded from below by 0, continuously differentiable, (L0,L 1)- smooth, and satisﬁ...

2025
[29]

In this case, the learning rate α(g) is large enough to ensure that f (xt+1) ≥ f (xt) for an exponentially increasing f

30 Published as a conference paper at ICLR 2025 Case 2: α(g) ≥ 4m ‖g‖ . In this case, the learning rate α(g) is large enough to ensure that f (xt+1) ≥ f (xt) for an exponentially increasing f . By creating f that only depends on ⟨x, g⟩ and which is piecewise linear and exponen...

2025
[30]

This completes the induction

= −km′ g ‖g‖ −α (‖g‖ ‖˜g‖ ∇f (xt) ) ‖g‖ ‖˜g‖ ∇f (xt) (i) = −km′ g ‖g‖ −α(g)g = −km′ g ‖g‖ −α(g)‖g‖ g ‖g‖ = −km′ g ‖g‖ −m′ g ‖g‖ = −(k + 1)m′ g ‖g‖, 31 Published as a conference paper at ICLR 2025 where (i) uses the fact that xt = −km′ g ‖g‖ =⇒ ∇ f (xt) = ‖˜g‖ g ‖g‖ . This comp...

2025
[32]

Also, ‖g1 −ℓg‖ = |c1 −ℓ|‖g‖ =ℓ −c1 = 1 −p p (c2 −ℓ) ≤ 1 −p p (σ1 +σ2ℓ) ≤σ1 +σ2ℓ, where the last inequality uses p > 1 2

In the ﬁrst case, |c1| ≤ 1 −p p σ1 + (1 −p p σ2 − 1 ) ǫ (38) |c2| ≥ p|c1| +ǫ 1 −p , (39) so ℓ = (1 −p)|c2| +p(−|c1|) ≥ǫ, 32 Published as a conference paper at ICLR 2025 and ‖g2 −ℓg‖ = |c2 −ℓ|‖g‖ =c2 −ℓ = p 1 −p (ℓ −c1) (i) ≤ p 1 −pℓ + p 1 −p (1 −p p σ1 + (1 −p p σ2 − 1 ) ǫ ) =...

2025
[34]

The upper bound of ‖yi‖ in the deﬁnition of k1 ensures that Equation 31 is satisﬁed

Equation 29 a nd Equation 30 are satisﬁed, 35 Published as a conference paper at ICLR 2025 since ‖yi‖ is increasing and ⟨yi, g⟩ alternates in sign. The upper bound of ‖yi‖ in the deﬁnition of k1 ensures that Equation 31 is satisﬁed. Since ‖yi‖ ≥ ‖ y0| =σ1 + (σ2 − 1)ǫ ≥ 1 −p1 p...

2025
[35]

+ǫ 2p0ǫ = (2p0−1)(1−p0) p0 (σ1 +σ2ǫ) + 2(1 −p0)ǫ 2p0ǫ = (2p0 − 1)(1 −p0) 2p2 0ǫ (σ1 +σ2ǫ) + 1 −p0 p0 , 36 Published as a conference paper at ICLR 2025 so Lemma 16 implies k0 =     log ( (2p0−1)(1−p0) 2p2 0ǫ (σ1 +σ2ǫ) + 1−p0 p0 ) log p0 1−p0     ≥ log ( (2p0−1)(1−p0) 2p...

2025
[36]

We can also bound β(yk1 ) using the assumed condition α(g) < 4m |g| , since we previously showed that (yk1, yk+1) satisﬁes Equation 29 through Equation

37 Published as a conference paper at ICLR 2025 Note that φ0 > φ1, and denote m = 4 L1 log ( 1 + ∆ L2 1 L0 ) . We can also bound β(yk1 ) using the assumed condition α(g) < 4m |g| , since we previously showed that (yk1, yk+1) satisﬁes Equation 29 through Equation

2025
[38]

For φ0 : φ0 = 1 − log ( 1−p0+p0ζ(p0,δ) 1−p0 ) log p0 1−p0 = 1 − log (1 + 2ζ(2/3,δ )) log 2 = 1 −γ1, where we denoted γ1 = log (1 + 2ζ(2/3,δ )) log 2 . Forφ1: φ1 = log ( p1 1−p1 ) log ( (σ2+1)p1 (σ2+1)(1−p1)−1 ) − log ( 1−p1+p1ζ(p1,δ) 1−p1 ) log ( (σ2+1)p1 (σ2+1)(1−p1)−1 ) = lo...

2025
[39]

For b1: b1 = 1−p1 p1 ( σ1 + ( σ2 − p1 1−p1 ) G ) ((σ2 + 1)(2p1 −

64 σ1 +σ2ǫ ǫ + 1 2 ≥ 3(σ2 − 1)σ1 32ǫ 40 Published as a conference paper at ICLR 2025 where (i) usesσ2 ∈ (1, 3). For b1: b1 = 1−p1 p1 ( σ1 + ( σ2 − p1 1−p1 ) G ) ((σ2 + 1)(2p1 −

2025
[40]

Also as in the ﬁrst case, |c1 −ℓ| ≤ |c2 −ℓ|

Therefore ℓ = pc1 + (1 −p)c2 ≥ ǫ as in the ﬁrst case. Also as in the ﬁrst case, |c1 −ℓ| ≤ |c2 −ℓ|. Therefore (f,g, D) satisﬁes ℓ ≥ ǫ and the noise condition in the second case. Consider the initial point x0 = (a +α(g2)‖g2‖)g. Recall that ‖g2‖ = |c2| ≤ |ℓ| + |c2 −ℓ| ≤ σ1 + (σ2 ...

2025
[41]

41 Published as a conference paper at ICLR 2025 Therefore φ1 = log ( p1 1−p1 ) log ( (σ2+1)p1 (σ2+1)(1−p1)−1 ) − log ( 1−p1+p1ζ(p1,δ) 1−p1 ) log ( (σ2+1)p1 (σ2+1)(1−p1)−1 ) = log ( σ2+5 −σ2+7 ) log ( 18 σ2−1 − 1 ) − log ( 1 + σ2+5 −σ2+7ζ(p1,δ ) ) log ( 18 σ2−1 − 1 ) ≥ log ( 12...

2025
[42]

42 Published as a conference paper at ICLR 2025 Proof

such that ‖∇f (xt)‖ ≥ ǫ for allt with t ≤ ∆ 2α0ǫ2. 42 Published as a conference paper at ICLR 2025 Proof. Denotea = 1 L1 log ( 1 + L1ǫ L0 ) , and let g ∈ Rd such that ‖g‖ = ǫ andα(g) = α0. Deﬁne the objectivef : Rd → R as follows: f (x) =        −ǫ ( ˆPg(x) +a ) +ψ(a) ˆ...

2025
[43]

Therefore,t ≤ ∆ 2α(ǫ)ǫ2 implies thatt<t 0 + 1, so that ˆPg(xt) ≥a by the deﬁnition of t0, and ﬁnally ‖∇f (xt)‖ =ǫ

So t0 + 1> ∆ 2α(ǫ)ǫ2. Therefore,t ≤ ∆ 2α(ǫ)ǫ2 implies thatt<t 0 + 1, so that ˆPg(xt) ≥a by the deﬁnition of t0, and ﬁnally ‖∇f (xt)‖ =ǫ. The following lemma is nearly identical to parts of the proof of Theorem 2 in Drori & Shamir (2020), with some small modiﬁcations to ﬁt our ...

2020
[44]

such that ‖∇f (xt)‖ =ǫ for all 0 ≤t ≤T , where T = ∆ L0σ2 1 2ǫ4 . Proof. Supposed ≥T . Let α : Rd → Rd and deﬁne f : Rd → R as f (x) = ǫ⟨x, e1⟩ + T∑ i=2 hi(⟨x, ei⟩), 43 Published as a conference paper at ICLR 2025 where hi(x) =              L0 4 a2 i |x|< −ai −L0 ...

2025
[45]

Therefore ∇f (xt) = ǫe1

Then for j ≥ 2, ∇jf (xt) = h′ j(⟨x, ej⟩) (i) =    h′ j(−aj) j ≤t + 1 andξj = 1 h′ j(bj) j ≤t + 1 andξj = 0 h′ j(0) j >t + 1 (ii) = 0, where (i) uses Equation 52 and Equation 53 from the induction hypothes is, and (ii) comes from the deﬁnition of h. Therefore ∇f (xt) = ǫe1. ...

2025
[46]

Together, these three equations imply that ‖∇f (xt)‖ =ǫ for allt ≤T , which is the desired conclusion

This completes the induction. Together, these three equations imply that ‖∇f (xt)‖ =ǫ for allt ≤T , which is the desired conclusion. The only remaining detail is the satisfaction of the conditi onf (x0) − inf xf (x) ≤ ∆ . As currently stated, the objectivef does not satisfy th...

2020
[47]

By the monotone convergence theorem, E[τ ] = limT →∞ E [Xτ ∧T ] − 1 (λ + 1)p − 1 We consider the following cases

LetT → ∞. By the monotone convergence theorem, E[τ ] = limT →∞ E [Xτ ∧T ] − 1 (λ + 1)p − 1 We consider the following cases. 47 Published as a conference paper at ICLR 2025 • If λ< 1−p p , then (λ + 1)p − 1<

2025
[48]

Speciﬁcally, we need r(λ) is decreasing (59) lim λ→ 1−p p + r(λ) = 1 (60) lim λ→∞ r(λ) = 1 −p

asδ → 0, we need a few facts aboutr(λ). Speciﬁcally, we need r(λ) is decreasing (59) lim λ→ 1−p p + r(λ) = 1 (60) lim λ→∞ r(λ) = 1 −p. (61) 48 Published as a conference paper at ICLR 2025 To see Equation 59, let λ2 >λ 1 > 1−p p . For any x ∈ [r(λ1), 1): hλ2(x) <h λ1(x) ≤ ( 1 −...

2025
[49]

Deﬁne T = min(T0,Tb). We have αXmin(T ,n ) is bounded for any n and it is nonnegative, therefore by optional sampling theor em and martingale convergence theorem (e.g., Theorem 4.8.2 in Durrett (2019) ), we have α =αX0 = E [ αXT ] = Pr(T0<T b)αXT0 + (1 − Pr(T0<T b))αXTb ≥ Pr(T...

2019
[50]

If ∆ L2 1 ≥L0, then T (ADAN, Fdet,ǫ ) ≥ ˜Ω (∆ 2L2 1 ǫ2 )

Let 0 < ǫ ≤ min { ∆ L1 2 , √ ∆ γ 4η } . If ∆ L2 1 ≥L0, then T (ADAN, Fdet,ǫ ) ≥ ˜Ω (∆ 2L2 1 ǫ2 ) . 50 Published as a conference paper at ICLR 2025 The proof structure is similar as Theorems 1, 2, and 3, by spli tting into cases depending on the choice ofη andγ. However, for th...

2025
[51]

Starting from Equation 22, t0√ γ2 +t0ǫ2 ≥ 1 ǫ ( ∆ 4ηǫ − ǫ 2γ ) . Using the assumed upper bound on ǫ, ǫ ≤ √ ∆ γ 4η ǫ2 ≤ ∆ γ 4η ǫ 2γ ≤ ∆ 8ηǫ, 51 Published as a conference paper at ICLR 2025 so t0√ γ2 +t0ǫ2 ≥ ∆ 8ηǫ2 8ηǫ2t0 ≥ ∆ √ γ2 +ǫ2t0 64η2ǫ4t2 0 ≥ ∆ 2γ2 + ∆ 2ǫ2t0 t2 0 ≥ ∆ 2γ2 ...

2025
[2010]

On the co nvergence of a class of adam-type algorithms for non-convex optimization

Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the co nvergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv:1808.02941 ,

arXiv
[2013]

A n ovel convergence analysis for algorithms of the adam family

Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Y ang. A n ovel convergence analysis for algorithms of the adam family. arXiv preprint arXiv:2112.03459 ,

arXiv
[2017]

The min-max complexity of distributed stochastic convex optimization with interm ittent communication

Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Sre bro. The min-max complexity of distributed stochastic convex optimization with interm ittent communication. arXiv preprint arXiv:2102.01583,

arXiv
[2018]

Generalized-smooth nonconvex optimization is as efﬁcient as smooth nonconvex optimization

Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex optimization is as efﬁcient as smooth nonconvex optimization. arXiv preprint arXiv:2303.02854 ,

arXiv
[2020]

Lower bound for randomiz ed ﬁrst order convex optimization

Blake Woodworth and Nathan Srebro. Lower bound for randomiz ed ﬁrst order convex optimization. arXiv preprint arXiv:1709.03594 ,

arXiv
[2022]

Beyond uniform smooth- ness: A stopped analysis of adaptive sgd

11 Published as a conference paper at ICLR 2025 Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay S hakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.06570 ,

2025 arXiv
[2023]

Converg ence of adam under relaxed assump- tions

Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Converg ence of adam under relaxed assump- tions. arXiv preprint arXiv:2304.13972 ,

arXiv
[2024]

Improved analysis of clipping algorithms for non-convex optimization

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–15521, 2020a. Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping...

2025

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

14 Published as a conference paper at ICLR 2025 Case 1 t =

work page 2025

[2] [2]

Therefore, the effective learning rate of the algorithm at stept is ηt = η √ γ2 +∑ t−1 i=0 ‖F (xi,ξi)‖2 = η√ γ2 +t(ǫ2 +σ2) =αt+2

Further, the above implies ‖F (xi,ξi)‖2 =ǫ2 +σ2. Therefore, the effective learning rate of the algorithm at stept is ηt = η √ γ2 +∑ t−1 i=0 ‖F (xi,ξi)‖2 = η√ γ2 +t(ǫ2 +σ2) =αt+2. 18 Published as a conference paper at ICLR 2025 We can then verify the inductive hypothesis for step t + 1 by considering the coordinates of xt+1: ⟨xt+1, e1⟩ = ⟨xt −ηtF (xt,ξt), ...

work page 2025

[3] [3]

We now bound the remaining constants

Here we choose p0 = p1 = 2 3 , and this satisﬁes p0,p 1 ∈ ( 1 2, σ2 σ2+1 ) . We now bound the remaining constants. For b0: b0 = (2p0 − 1)(1 −p0) 2p2 0ǫ (σ1 +σ2ǫ) + 1 −p0 p0 = 1 8ǫ (σ1 +σ2ǫ) + 1 2 ≥ σ1 8ǫ. 38 Published as a conference paper at ICLR 2025 Forb1: b1 = 1−p1 p1 ( σ1 + ( σ2 − p1 1−p1 ) G ) ((σ2 + 1)(2p1 −

work page 2025

[4] [4]

Let 0<ǫ< min      ∆ L1 2 , /radicaltp /radicalvertex /radicalvertex √ ∆ L1σ 4 √ 2 log ( 1 + ∆ L2 1 L0 )      . If the parameters of Decorrelated AdaGrad satisfy η ≤ √ 2γ L1σ log ( 1 + L1ǫ L0 ) , then there exists some (f,g, D) ∈ F as(∆ ,L 0,L 1,σ ) such that ‖∇f (xt)‖ ≥ ǫ for all t ≤ ∆ 2L2 0σ2 256γ2ǫ4 + ∆ 2L2 1σ2 256γ2ǫ2 log2 ( 1 + ∆ L2 1 L0 ). ...

work page 2025

[5] [5]

Let algorithmADAN denote Decorrelated AdaGrad-Norm with parameters η >0 and 0<γ ≤ ∆ L1 8 log ( 1 + 48 ∆ L2 1 L0 )

[Restatement of Theorem 1] Let ∆ ,L 0,L 1,σ > 0, and let F = Fas(∆ ,L 0,L 1,σ ). Let algorithmADAN denote Decorrelated AdaGrad-Norm with parameters η >0 and 0<γ ≤ ∆ L1 8 log ( 1 + 48 ∆ L2 1 L0 ). Let 0<ǫ ≤ min { √ 2 3 √∆ L0, 1√ 3 √∆ L1γ, ∆ L1 } . If ∆ L2 1 ≥L0, then T (ADAN, F,ǫ ) ≥ 1 + ∆ 2L2 1σ2 144ǫ4 + ∆ L0σ2 log(1 +σ2/γ2) 24ǫ4 + ∆ 2L2 1 144ǫ2. 21 Publi...

work page 2025

[6] [6]

Near -optimal non-convex stochastic opti- mization under generalized smoothness

Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near -optimal non-convex stochastic opti- mization under generalized smoothness. arXiv preprint arXiv:2302.0603 ,

arXiv

[7] [7]

Adaptive bound opti mization for online convex opti- mization

H Brendan McMahan and Matthew Streeter. Adaptive bound opti mization for online convex opti- mization. arXiv preprint arXiv:1002.4908 ,

arXiv

[8] [8]

V ariance-reduced clipping for non-convex optimization

Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Ja dbabaie. V ariance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303.00883 ,

arXiv