REVIEW 3 major objections 5 minor 18 references
Linear Convergence of Adaptive Stochastic Gradient Descent
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read AdaGrad-Norm converges linearly on strongly convex losses without parameter tuning.
desk verdict A genuinely new two-stage framework for AdaGrad-Norm linear convergence, with a real but likely fixable gap in the stochastic proof. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Restricted Uniform Inequality of Gradients (RUIG): for every $\epsilon > 0$ and every $x$ with $\|x - x^*\|^2 > \epsilon$, the probability over the sample index that $\|\nabla f_i(x)\|^2 \ge \alpha \|x - x^*\|^2$ is at least $\gamma$. RUIG guarantees that in Stage I the accumulated step-size reciprocal $b_t$ grows above thresholds such as $\eta L$, deterministically in the batch setting and with high probability in the stochastic setting, while a separate lemma bounds $\|x_t - x^*\|$ during that growth. Once $b_t$ crosses the threshold, AdaGrad-Norm becomes a contraction in expectation and another lemma bounds $b_t$ from above, producing the linear decay. This two-stage split is what removes the need to know $L$, $\mu$, or a bounded domain.
What would settle it
Run AdaGrad-Norm with $b_0 > \eta L$ on a strongly convex smooth quadratic whose labels contain independent noise, so $\nabla f_i(x^*) \neq 0$ with positive probability; if the error still decreases at an exponential rate to arbitrarily small values, the noiseless-at-the-optimum assumption is unnecessary, and if it plateaus above the noise floor, the theorem's dependence on (A4) is confirmed.
Extended reading notes
Core claim
In the strongly convex stochastic setting, under assumptions (A1a), (A2), (A3), and (A4), AdaGrad-Norm reaches $\min_i \|x_i - x^*\|^2 \le \epsilon$ with high probability after $T = O(\log 1/\epsilon)$ iterations when $b_0 > \eta L$, and after $T = O(1/\epsilon + \log 1/\epsilon)$ iterations when $b_0 \le \eta L$. The batch full-gradient analogue gives deterministic $O(\log 1/\epsilon)$ rate bounds for strongly convex functions and, via Theorem 3, for non-convex functions satisfying the PL inequality, with a logarithmic correction when $b_0$ starts small. The rates match classical fixed-step-size SGD and GD up to constants, but the algorithm does not need the smoothness constant, strong-convexity parameter, or a bounding box for the minimizer.
Load-bearing premise
The stochastic linear-rate proof requires Assumption (A4): every component function's gradient vanishes at the global minimizer almost surely, so all stochastic noise disappears at the optimum.
Editorial extensions
If this is right
- With $b_0 > \eta L$ (a small initial step), stochastic AdaGrad-Norm is linearly convergent from any starting point and no projection or parameter knowledge is needed.
- With $b_0 \le \eta L$ (a large initial step), the price is only a sublinear warm-up stage; once $b_t$ exceeds $\eta L$, the same linear contraction applies.
- The batch analysis grants the same linear guarantees to non-convex objectives satisfying the PL inequality, a class that includes over-parameterized neural-network training objectives.
- The two-stage framework is presented as transferable to other adaptive step-size methods, with Adam and AMSGrad named as direct candidates.
Reading between the lines
- RUIG can be read as a testable landscape diagnostic: on a real dataset one can estimate the probability that a sampled gradient norm exceeds $\alpha \|x - x^*\|^2$ and check whether the $\alpha\gamma$ product stays bounded away from zero.
- The high-probability Stage I growth in Lemma 1 relies on the sampled gradient-indicator events being treated as independent; if samples are correlated, the effective variance grows and the warm-up count would need a larger slack term.
- The small-$b_0$ guarantee is stated for the best iterate; extending the same rates to the last iterate would require an additional argument and is a natural open follow-up.
- The paper names the weak growth condition $E\|\nabla f_\xi(x)\|^2 \le M\|\nabla F(x)\|^2 + \sigma^2$ as a route to relax Assumption (A4); making that step work would widen the stochastic result to objectives with bounded noise at the optimum.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes the norm version of AdaGrad (AdaGrad-Norm) and proves non-asymptotic convergence rates for strongly convex objectives in both stochastic and batch settings, and for non-convex objectives satisfying the Polyak--Lojasiewicz (PL) inequality in the batch setting. It introduces the Restricted Uniform Inequality of Gradients (RUIG) assumption, which lower-bounds the probability that a stochastic gradient at a point away from the optimum has norm at least a constant times the distance to the optimum. The proof uses a two-stage framework: Stage I shows that the adaptive stepsize parameter b_t grows past a critical threshold within a controlled number of iterations unless the algorithm has already reached the desired accuracy, and Stage II shows that after the threshold is crossed the error contracts linearly. The principal advertised result is that for stochastic strongly convex problems, AdaGrad-Norm achieves epsilon accuracy in O(log 1/epsilon) iterations with high probability when b0 > eta L, and in O(1/epsilon + log 1/epsilon) iterations for arbitrary b0, without prior knowledge of smoothness, strong convexity, or a containing convex set. Numerical experiments on least squares and a two-layer network illustrate linear convergence and robustness to b0.
Significance. If the stochastic results were fully established, the paper would provide a genuinely parameter-free linear-convergence guarantee for an adaptive SGD method, complementing the known sublinear guarantees for AdaGrad-Norm under bounded-variance assumptions. The RUIG condition is a new and interesting way to quantify the 'balancedness' of stochastic gradient norms, with explicit worked examples (Gaussian least squares, strongly convex sums) that do not presuppose the desired rate. The two-stage framework is clearly explained and likely transferable to other adaptive algorithms. The batch-setting proofs (Theorems 2 and 3) are coherent and follow from co-coercivity and descent arguments, and the numerical experiments support the main qualitative claims. The main weakness is that the stochastic Theorem 1 rests on a high-probability growth lemma whose proof, as written, relies on an invalid independence assertion; this is a load-bearing gap that needs to be repaired or the stochastic claim must be weakened.
major comments (3)
- [Appendix C.1, Lemma 1] The indicators Z_j defined in Eq. (9) are not independent across iterations, because x_j depends on the past samples xi_0,...,xi_{j-1}; the proof treats them as i.i.d. Bernoulli(gamma) and applies Lemma C3. The subsequent remark asserting that the sum of dependent sub-Gaussians with sigma=0.5 has variance at most 0.25N^2 and hence concentrates is incorrect: a perfectly correlated sum can take value 0 or N with probabilities 1-gamma or gamma, so no concentration around gamma N holds. Since Lemma 1 is the sole mechanism forcing b_N > eta L in Stage I of Theorem 1, the stochastic high-probability convergence statement is not established as written. A valid martingale concentration argument on the bounded martingale difference sequence Z_j - E[Z_j | F_{j-1}] would likely repair the proof, but the manuscript does not supply it.
- [Section 2, Assumption (A4)] The assumption P(grad f_i(x*) = 0) = 1 for each component is used as a substitute for the noiseless-at-the-optimum condition in the co-coercivity steps (Appendix D, Eq. (13)) and in the contraction step of Theorem 1 (Appendix A, Eqs. (1)-(2)). The authors themselves note that this 'may not be appropriate for certain applications.' Because Theorem 1 and the bounds in Stage I both rely on this condition, the headline robustness claim in Section 1 should explicitly state that the stochastic linear-convergence guarantee is restricted to settings with a.s. zero component gradient at x*. This is not a correctness error, but it materially narrows the scope of the stochastic result compared to the abstract's phrasing.
- [Theorem 1 and Lemma 1] The high-probability term exp(-delta^2/(2(N gamma (1-gamma)+delta))) contains the same delta that appears in the iteration count N = ceil((eta^2 L^2 - b0^2)/(alpha gamma epsilon) + delta/gamma), but the dependence of the failure probability on the problem parameters is not discussed. In particular, for the claimed O(1/epsilon + log 1/epsilon) rate, the authors should state explicitly how delta is chosen (e.g., delta = sqrt(4c gamma (1-gamma) N log N)) and verify that the total failure probability tends to zero as epsilon -> 0 without requiring gamma to grow with N. As written, the probability and the iteration bound are not reconciled.
minor comments (5)
- [Appendix C.1, Lemma 1] The phrase 'independent identical Bernoulli' is inaccurate: even under RUIG, the conditional probabilities P(Z_j = 1 | x_j) are only bounded below by gamma; they are not necessarily equal to gamma. Please use 'stochastically dominated by' or similar.
- [Theorem 1] The constant delta_h is not defined in the theorem statement; it is introduced later in the proof (Appendix A). Define it where the theorem is stated so that the probability bounds are self-contained.
- [Abstract and Section 1] For precision, the informal summary of the stochastic result should mention Assumption (A4) explicitly, since the theorem statement relies on it and the assumption materially restricts the data distribution.
- [Theorem 2] The threshold b0 > eta (mu + L)/2 is stated in the theorem, while Lemma 2(a) uses a general C; the relation between C and the threshold should be spelled out for readability.
- [Throughout] There are several typographical issues: 'Polyak- Lojasiewicz' has an errant space; 'AdaGrad-Norm' is sometimes hyphenated inconsistently; 'P_i' is used before being defined in the Notations paragraph.
Circularity Check
No significant circularity: the linear convergence result is a conditional derivation from RUIG, smoothness/strong convexity, and Assumption (A4), not a restatement of those assumptions.
full rationale
None of the load-bearing steps reduces to its own inputs. RUIG (Assumption A3) is a genuine lower-bound condition on stochastic gradient norms with explicit worked examples (Gaussian least squares, strongly convex sums), and it is not defined in terms of AdaGrad-Norm's iterates or its convergence rate. Lemma 1 derives the growth of b_N from the update rule b_{j+1}^2 = b_j^2 + ||∇f_{\xi_j}(x_j)||^2 together with RUIG; the subsequent Stage II contraction in Appendix A, Eqs. (1)-(2), uses only L-smoothness, strong convexity, and Assumption (A4), with b_max controlled by Lemma 4. No fitted quantity is renamed as a prediction: the constants in the rates are explicit functions of assumed parameters, not estimated from data. Self-citations to Ward et al. (2018), Needell et al. (2016), and Wu et al. (2019) are used for standard or elementary lemmas (co-coercivity, the integral lemma, background comparisons) and are not standing in for the target theorem; the core estimates are proved in the appendix. The suspicious point in Lemma 1, namely treating the indicators Z_j as independent even though x_j depends on past samples, is a genuine proof gap, but it is a correctness issue rather than circularity: even if the high-probability bound on b_N fails, the theorem is not asserting its own conclusion by construction. There is no uniqueness theorem imported from the authors and no ansatz smuggled in via citation.
Assumptions & free parameters
assumptions (5)
- domain assumption Assumption (A1a): F is μ-strongly convex
- domain assumption Assumption (A1b): F satisfies the μ-PL inequality
- domain assumption Assumption (A2): each fi is Li-smooth with L = sup_i Li
- ad hoc to paper Assumption (A3): (ε, α, γ)-RUIG
- domain assumption Assumption (A4): fi convex and ∇fi(x*) = 0 almost surely
Cite this review
Pith. "Pith review of Linear Convergence of Adaptive Stochastic Gradient Descent." pith.science (2026). https://pith.science/paper/SOY7X4OM
@misc{pith2026190810525,
author = {Pith},
title = {Pith review of: Linear Convergence of Adaptive Stochastic Gradient Descent},
year = {2026},
howpublished = {\url{https://pith.science/paper/SOY7X4OM}},
note = {Machine review of arXiv:1908.10525}
}
read the original abstract
We prove that the norm version of the adaptive stochastic gradient method (AdaGrad-Norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-convex functions that satisfy the Polyak Lojasiewicz (PL) inequality. The paper introduces the notion of Restricted Uniform Inequality of Gradients (RUIG)---which is a measure of the balanced-ness of the stochastic gradient norms---to depict the landscape of a function. RUIG plays a key role in proving the robustness of AdaGrad-Norm to its hyper-parameter tuning in the stochastic setting. On top of RUIG, we develop a two-stage framework to prove the linear convergence of AdaGrad-Norm without knowing the parameters of the objective functions. This framework can likely be extended to other adaptive stepsize algorithms. The numerical experiments validate the theory and suggest future directions for improvement.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[1]
(2018): F (xk0−1) ≤ F (x0) + η2L 2 (1 + log( b2 k0−1 b2 0 ))
and the lemma in Ward et al. (2018): F (xk0−1) ≤ F (x0) + η2L 2 (1 + log( b2 k0−1 b2 0 )). The upper bound of bj is also from Ward et al. (2018): bmax =bk0−1 + 2 η (Fk0−1−F∗)≤ηL + 2 η (F (x0)−F∗ + η2L 2 (1 + log(η2L2 b2 0 ))) (7) Y uege Xie∗, Xiaoxia W u†, Rachel W ard∗† Then, F (xk0+M−1)−F∗≤ exp(−µηM bmax )(F (x0)−F∗ + η2L 2 (1 + 2 logηL b0 )) Hence, we ...
work page 2018
-
[2]
When initialize x0 with extremely bad one, x0 = 100∗ w0, where w0 is a randomly generated vector w0 and w0∼N (0, I), AdaGrad-Norm takes much more iterations than before. However, after tuning η = 10000 in stochastic setting and η = 100 in batch setting, the convergence rate of AdaGrad-Norm is better again. In this case, b0 plays a small role. 0 2500 5000 ...
work page 2019
-
[4]
Figure 12 (left) clearly illustrates that AdaGrad-Norm (black curve) converges linearly. Figure 12 (right) shows the norm of the gradients at the first few iterations by AdaGrad-Norm are often big enough to accumulate to exceed ηL, which empirically verifies Assumption (A3). 0 1000 2000 3000 4000 5000 6000 7000 8000 Iteration 10 8 10 6 10 4 10 2 100 min-bat...
work page 2000
-
[7]
A sufficient condition for con- vergences of adam and rmsprop
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for con- vergences of adam and rmsprop. arXiv preprint arXiv:1811.09358, 2018b. Matthew Staib, Sashank J Reddi, Satyen Kale, San- jiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. arXiv preprint arXiv:1901.09149,
arXiv 1901
-
[8]
Ada- grad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Ada- grad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv:1806.01811,
-
[9]
Wngrad: learn the learning rate in gradient descent
Xiaoxia Wu, Rachel Ward, and L´ eon Bottou. Wngrad: learn the learning rate in gradient descent. arXiv preprint arXiv:1803.02865,
-
[10]
On the conver- gence of stochastic gradient descent with adaptive stepsizes
Xiaoyu Li and Francesco Orabona. On the conver- gence of stochastic gradient descent with adaptive stepsizes. arXiv preprint arXiv:1805.08114 ,
-
[11]
Sharan Vaswani, Francis Bach, and Mark Schmidt
PMLR. Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated percep- tron. arXiv preprint arXiv:1810.07288 ,
Show all 18 references
-
[12]
Understanding deep learning requires rethinking generalization
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Ben- jamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530,
-
[14]
Mark Schmidt and Nicolas Le Roux
ISSN 1862-4480. Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370 ,
-
[15]
Global convergence of adaptive gradient methods for an over-parameterized neural network
Xiaoxia Wu, Simon S Du, and Rachel Ward. Global convergence of adaptive gradient methods for an over-parameterized neural network. arXiv preprint arXiv:1902.07111,
1902 arXiv
-
[2010]
Adam: A method for stochastic optimization
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980,
-
[2011]
Adaptive bound optimization for online convex optimization
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:1002.4908 ,
-
[2014]
Di- agonal rescaling for neural networks
Jean Lafond, Nicolas Vasilache, and L´ eon Bottou. Di- agonal rescaling for neural networks. Technical re- port, arXiV:1705.09319,
-
[2015]
A convergence theory for deep learning via over- parameterization
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.03962,
-
[2017]
Reddi, Satyen Kale, and Sanjiv Kumar
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. CoRR, abs/1904.09237, 2018a. Vatsal Shah, Anastasios Kyrillidis, and Sujay Sang- havi. Minimum norm solutions do not always gen- eralize well for over-parameterized problems. arXiv preprint...
1904 arXiv
-
[2018]
Stochastic gradient descent optimizes over- parameterized deep relu networks
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018a. Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machin...
-
[2019]
On exponential convergence of sgd in non- convex over-parametrized learning
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non- convex over-parametrized learning. arXiv preprint arXiv:1811.02564,
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.