{"id":"527f37b5-d678-4bf4-848f-2ab0fa54ea70","arxiv_id":"2505.04599","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AdaGrad-type algorithms provably need a complexity quadratic in the initial gap and smoothness constants under relaxed smoothness, so they cannot match the optimal rate of clipped SGD.","lead":"Adaptive optimization algorithms like AdaGrad are shown to be slower than previously thought when the function is only relaxed-smooth, needing extra steps that grow with the square of the problem parameters. This theoretical paper provides new lower bounds, showing these algorithms cannot easily close the gap with simpler methods like clipped SGD.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5's constructed objective f is not C^1 at internal breakpoints: the one-sided derivatives at x = m_t + m_{t+1} are g_{t+1} on the left and g_t on the right, so the divergence instance lies outside the problem class Fas.","rationale":"The reader identified the stabilization-constant restriction gamma <= O~(Delta L1) as the weakest assumption. That is a limitation, but it is explicitly stated and even partially removed in Appendix E for the deterministic case. The more serious problem is that the proof of Lemma 5, which supplies the divergence case of Theorem 1, constructs an objective that is not continuously differentiable, contradicting Assumption 1. This is a concrete mathematical error in the proof of the paper's headline result. The error looks like a typo---replacing g_t with g_{t+1} in the linear segment of phi_t restores C^1 smoothness without changing the queried gradient sequence---so the central claim may survive after a correction. However, as submitted, the proof is not valid. The verdict of conditional acceptance remains appropriate, because the paper's other results and the high-level approach are still valuable, but the authors must fix this gap and rerun the affected derivations. The gamma restriction remains a secondary concern worth noting but is not the weakest link once the C^1 issue is identified.","tokens_in":52395,"tokens_out":10626,"duration_ms":100642,"concrete_test":"Verify the differentiability claim directly: using the definitions in Lemma 5 (Appendix A), compute the left and right derivatives of phi_t at x = m_t + m_{t+1}. The left derivative is psi'(m_{t+1}) = g_{t+1}; the right derivative is g_t. Since g_{t+1} > g_t, the function is not C^1 there. Then test the proposed fix: change the linear-piece slope in phi_t from g_t to g_{t+1} and adjust the constant in the third piece correspondingly; recompute the value and derivative continuity at both internal breakpoints and confirm that the trajectory xt = d_t and the gradient lower bound ||nabla f(x_t)|| >= Delta L1 still hold. If the corrected construction satisfies Assumption 1, the divergence case is salvageable; if not, Theorem 1 lacks a valid lower bound for eta >= 1/L1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main lower bound (Theorem 1) splits on the step-size coefficient eta. For eta >= 1/L1, Lemma 5 (main-text Lemma 1) constructs a deterministic hard instance with gradient magnitudes growing like (t log t)^t. The instance is piecewise defined using functions phi_t in Appendix A. Each phi_t has two interior breakpoints: x = m_t + m_{t+1} and x = ell_t - 2m_{t+1}. At the first breakpoint, the left piece is psi(x - m_t), whose derivative at the boundary is psi'(m_{t+1}) = g_{t+1}; the right piece is the linear function g_t(x - m_t - m_{t+1}) + psi(m_{t+1}), whose derivative is g_t. Since g_{t+1} > g_t, the derivative is discontinuous there. The same mismatch occurs at the second breakpoint. Therefore phi_t is not differentiable, and the assembled f is not continuously differentiable, violating Assumption 1(2) and the definition of Fas(Delta,L0,L1,sigma). Consequently the divergence case of Theorem 1 does not apply to any admissible problem instance, and the lower bound is not established for eta >= 1/L1. The construction appears repairable: replacing the linear-piece slope g_t (and the corresponding constant g_t(ell_t - 3m_{t+1} - m_t)) with g_{t+1} would make the derivatives match and preserve the trajectory argument, since the linear slope never enters the queried gradients. But as submitted, the proof has a genuine gap in the central theorem. The paper's other results (Theorems 2-4) use different constructions and are not affected by this particular issue, nor is the slow-convergence case (Lemma 6) for eta <= 1/L1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":52754,"tokens_out":9461,"duration_ms":86601,"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":[{"comment":"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.","section":"Appendix A, Lemma 5 (main-text Lemma 1)"},{"comment":"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.","section":"Appendix C, Lemma 13"}],"minor_comments":[{"comment":"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.","section":"Appendix A, Theorem 5 proof"},{"comment":"The equation references are swapped: Decorrelated AdaGrad is Equation (3), not Equation (2), and AdaGrad is Equation (2), not Equation (3).","section":"Theorems 2 and 3"},{"comment":"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.","section":"Theorem 2 statement"},{"comment":"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.","section":"Appendix A, Lemma 6"},{"comment":"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.","section":"Appendix A, Lemma 5"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Lemma 5 is localized and likely repairable by the slope change described above, but because it directly underpins Theorem 1 and the deterministic extension in Appendix E, the current submission does not establish the headline lower bound. I would not recommend rejection provided the authors carry out the repair and re-verify the differentiability and smoothness of the assembled objective."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.","headline":"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.","tokens_in":652,"tokens_out":680,"would_cite":false,"duration_ms":39461,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C60","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["relaxed smoothness","(L0,L1)-smoothness","AdaGrad-Norm","adaptive gradient methods","non-convex stochastic optimization","complexity lower bounds","stabilization constant"],"falsifier":"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.","tokens_in":52200,"feed_emoji":"📉","tokens_out":15148,"duration_ms":117488,"temperature":0.7,"pith_summary":"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.","feed_headline":"AdaGrad provably cannot match SGD under relaxed smoothness","feed_subtitle":"New lower bounds saddle AdaGrad variants with a quadratic dependence on gap and smoothness that clipped SGD escapes.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Introduces relaxed smoothness and the divergence-style GD lower bound whose two-regime template this paper extends.","marker":"(Zhang et al., 2020b)"},{"why":"Supplies the AdaGrad-Norm upper bound under relaxed smoothness that Theorem 1's lower bound is matched against.","marker":"(Wang et al., 2023)"},{"why":"Provides the high-dimensional stochastic hard instance adapted in Lemma 2 to force slow convergence via noise-deflated learning rates.","marker":"Drori & Shamir (2020)"},{"why":"Defines the decorrelated step sizes whose complexity is lower-bounded in Theorems 1 and 2.","marker":"(Li & Orabona, 2019)"},{"why":"Establishes the optimal $\\Theta(\\Delta L \\sigma^2 \\epsilon^{-4})$ complexity in the smooth setting that serves as the baseline these bounds must beat.","marker":"(Arjevani et al., 2023)"},{"why":"Shows clipped SGD achieves the classical rate under relaxed smoothness, the comparison that makes the AdaGrad slowdown consequential.","marker":"(Zhang et al., 2020a)"},{"why":"Supplies the biased-random-walk lower-bound technique under affine noise that Theorem 4 adapts for single-step adaptive SGD.","marker":"(Faw et al., 2023)"},{"why":"Provides prior one-dimensional slow-convergence lower bounds under relaxed smoothness that the paper extends to $\\epsilon^{-4}$ dependence.","marker":"Crawshaw et al. (2022)"}],"fun_headline_variants":["AdaGrad's quadratic lower bounds under relaxed smoothness","AdaGrad cannot match SGD's optimal rate under relaxed smoothness","Lower bounds: AdaGrad needs far more steps under relaxed smoothness","Quadratic gap from relaxed smoothness: AdaGrad vs SGD","Relaxed smoothness makes AdaGrad quadratically worse than SGD"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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).","fun_headline_variants_meta":{"raw":{"variants":["AdaGrad's quadratic lower bounds under relaxed smoothness","AdaGrad cannot match SGD's optimal rate under relaxed smoothness","Lower bounds: AdaGrad needs far more steps under relaxed smoothness","Quadratic gap from relaxed smoothness: AdaGrad vs SGD","Relaxed smoothness makes AdaGrad quadratically worse than SGD"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000502,"raw_usage":{"total_tokens":2628,"prompt_tokens":1292,"completion_tokens":1336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":908,"completion_tokens_details":{"reasoning_tokens":1244}},"tokens_in":908,"tokens_out":1336,"duration_ms":9896,"temperature":1.0,"reasoning_tokens":1244,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:23:54.145068+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}