REVIEW 2 major objections 4 minor 1 cited by
Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A non-uniform average of SGD iterates reaches the optimal 1/T convergence rate with probability 1-δ, not just in expectation.
desk verdict Solid upper bound for non-uniform averaging SGD; the lower bound misses the theorem's assumptions, so the optimality claim is not yet established. 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 proof is carried by a specialized martingale concentration bound: the generalized Freedman inequality, which controls a martingale by its total conditional variance. The relevant martingale has increments $d_t=t\langle \hat z_t, x_t-x^*\rangle$, where $\hat z_t$ is the oracle noise, and its total conditional variance is $V_T=\sum_{t=1}^T t^2\|x_t-x^*\|^2$. The crucial step (Lemma 4.3) shows that, with the step sizes $\eta_t=2/(\mu(t+1))$, this variance can itself be bounded by a linear combination $\sum_i \alpha_i d_i+\beta$ of the martingale increments, with $\alpha_i=O(T/\mu)$ and $\beta=O(L^2T^2/\mu^2)$. This self-bounding, 'chicken-and-egg' structure lets the inequality produce a tail estimate with only a $\log(1/\delta)$ factor instead of the weaker $\sqrt{T}$ factor that generic martingale arguments would give. The weights $t/(T(T+1)/2)$ and step sizes are chosen so that summing the strong-convexity inequalities telescopes, leaving only the noise term to be controlled.
What would settle it
Run Algorithm 1 on $f(x)=\|x\|^2/2$ with noise drawn uniformly from the unit sphere (so $\|\hat z_t\|\le1$ and the theorem's assumptions hold), record the empirical $\delta$-quantile of $f(\sum_t\gamma_tx_t)-f(x^*)$ over many trials; if for any fixed constant $C$ the quantile exceeds $C\log(1/\delta)/T$ as $T$ grows, the upper bound is false. For the lower bound, compute the exact distribution of the weighted average under the paper's Bernoulli oracle on $x^2/2$ and check whether its tail dominates $\log(1/\delta)/(9T)$ with probability $\delta$.
Extended reading notes
Core claim
The paper's central claim is Theorem 3.1: for a $\mu$-strongly convex, $L$-Lipschitz function and a stochastic gradient oracle whose noise satisfies $\|\hat z_t\|\le 1$ almost surely, projected SGD with step size $\eta_t=2/(\mu(t+1))$ and averaging weights $\gamma_t=t/(T(T+1)/2)$ satisfies $f(\sum_{t=1}^T \gamma_t x_t)-f(x^*) = O((L\log(1/\delta)+L^2/\mu)/T)$ with probability at least $1-\delta$. A companion lower bound, Claim 3.3, constructs a zero-mean Bernoulli oracle on $f(x)=x^2/2$ for which the same averaged output has error at least $\log(1/\delta)/(9T)$ with probability at least $\delta$, so the $\log(1/\delta)$ factor is necessary. Together these show that the simple, online-computable non-uniform average has the optimal high-probability convergence rate, not merely the optimal expected rate.
Load-bearing premise
The entire argument assumes the oracle noise has bounded or at least subgaussian tails; if the noise is heavy-tailed, the martingale variance bound collapses and the $O(\log(1/\delta)/T)$ guarantee may fail.
Editorial extensions
If this is right
- A single run of SGD with the non-uniform average gives a rigorous $O(\log(1/\delta)/T)$ error bound with probability $1-\delta$, so users can trust one trial instead of averaging many.
- The $\log(1/\delta)$ factor is unavoidable: no algorithm of this form can beat the $\log(1/\delta)/T$ high-probability rate on nonsmooth strongly convex problems under bounded noise.
- Non-uniform averaging matches suffix averaging's high-probability guarantee while remaining fully online, with no need to know the time horizon in advance.
- The subgaussian extension (Theorem C.3) covers Gaussian noise with the same $O(\log(1/\delta)/T)$ rate, replacing $\|\hat z_t\|\le1$ by a $\kappa$-subgaussian assumption.
- On regularized SVM problems, the experiments show the weighted average and suffix average dominate the final iterate and uniform average in both typical error and spread.
Reading between the lines
- The paper does not prove it, but the same variance self-binding argument likely extends to any output weights within a constant factor of $t$, such as a sliding-window suffix average, which would give practitioners a larger family of simple high-probability averaging schemes.
- A natural testable extension is the heavy-tailed noise regime: if the oracle noise has only finite variance or power-law tails, one would expect the $\log(1/\delta)/T$ guarantee to degrade, and truncating the stochastic gradient before averaging might restore it.
- The lower bound's Bernoulli oracle suggests that the $\log(1/\delta)$ factor is intrinsic to subgaussian noise itself; proving a similar lower bound for any first-order randomized method, rather than for this specific averaging scheme, would make that intuition a theorem.
- The high-probability bound is stated for a fixed horizon $T$; combining it with a union bound over horizons could yield a stopping rule with a guaranteed $\log(1/\delta)\log(T)/T$ rate when $T$ is chosen adaptively.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper analyzes stochastic gradient descent with the non-uniform averaging scheme of Lacoste-Julien et al. for nonsmooth strongly convex functions. The main theoretical result is a high-probability upper bound of O((L log(1/δ) + L^2/μ)/T) on the function error, under the assumption that the oracle noise is almost surely bounded by 1. The proof uses a generalized Freedman inequality to bound the martingale formed by the noise terms, together with deterministic bounds adapted from Rakhlin et al. The paper also claims a matching lower bound of Ω(log(1/δ)/T), extends the upper bound to subgaussian noise, and reports experiments comparing averaging schemes.
Significance. If the upper bound is correct, the paper provides a simple algorithm with a high-probability O(log(1/δ)/T) guarantee, which is optimal in T for fixed δ. The proof is clear and the use of the generalized Freedman inequality is appropriate. However, the advertised matching lower bound is not proved for the algorithm and noise model analyzed in the upper bound, so the optimality claim is not currently established. The upper bound and its proof are nevertheless a useful contribution, and the subgaussian extension is a reasonable addition.
major comments (2)
- [5, Claim 3.3 and Remark 5.1] The lower bound is proved for step size η_t = 1/(t+1), whereas Algorithm 1 and Theorem 3.1 use η_t = 2/(μ(t+1)) (with μ = 1 for f(x) = x^2/2). Claim 3.3 states it runs Algorithm 1 with these step sizes, which is inconsistent. Remark 5.1 acknowledges the modification and asserts without proof that it is nonessential. As a result, the lower bound does not apply to the algorithm whose upper bound is proved, and the paper's claim of a matching lower bound in the abstract and introduction is unsupported.
- [5, lower-bound oracle and Claim 5.2 vs. Theorem 3.1] The oracle used in the lower bound produces noise ẑ_t = ((T+1)/(T-t)) X_t for T/2 < t ≤ 3T/4, which can have magnitude about 4, violating the bounded-noise assumption ‖ẑ_t‖ ≤ 1 used in Theorem 3.1 and in the proof of Lemma 4.1. Claim 5.2 only assumes |ẑ_t| ≤ 6. Thus the lower bound is proved outside the hypotheses of the upper bound, so it does not demonstrate optimality of Algorithm 1 in the setting where the upper bound holds.
minor comments (4)
- [A, proof of Lemma 4.5] In Eq. (4), the second summand is written with ‖ĝ_t‖² but the index of summation is i; this appears to be a typo for ‖ĝ_i‖².
- [C.2, Lemma C.10] The statement of Lemma C.10 appears to have a typo: the condition should likely be E[exp(X²/κ²)] ≤ 2 (matching the paper's definition of subgaussian) rather than E[exp(X/κ²)] ≤ 2. As written, the lemma does not follow from the cited proposition.
- [4, proof of Theorem 3.1] The telescoping step states 'the right-hand side telescopes' after omitting the non-positive term involving ‖x_{T+1}-x*‖²; this is correct but could be stated explicitly to help the reader.
- [6, experiments] The abstract claims the non-uniform averaging strategy has 'smaller variance'; the experimental plots in Figure 1 only show trial clouds, so this claim is not quantified. A quantitative variance comparison would strengthen the presentation.
Circularity Check
No significant circularity: the high-probability upper bound follows from a general martingale inequality plus self-contained lemmas, and the lower-bound mismatch is a validity concern rather than a circular reduction.
full rationale
The paper's central upper bound (Theorem 3.1) is not derived from the result it aims to prove. Its proof uses the Generalized Freedman Inequality (Theorem 2.2), quoted from the authors' prior work Harvey et al. [2018], but that theorem is a general martingale tail bound that does not assume the SGD error bound. The remaining technical ingredients, Lemmas 4.4 and 4.5, are adapted from Rakhlin et al. [2012] and proven in the appendix, and Lemma 4.3 is an explicit decomposition bounding the total conditional variance by a linear combination of martingale increments. No fitted parameter is renamed as a prediction: the upper-bound constants are explicit in the theorem statement, and the proof does not tune a parameter to the target function or to the claimed bound. The lower bound (Claim 3.3) is an adversarial oracle construction on f(x)=x^2/2; it does not fit a parameter to force a specific output, but rather constructs a noise sequence so that the averaged iterate is a Bernoulli average. That construction does use a step size eta_t=1/(t+1) rather than Algorithm 1's eta_t=2/(mu(t+1)), and it allows |z_t|<=6 rather than the |z_t|<=1 used in Theorem 3.1. This is a mismatch between the lower-bound setting and the upper-bound assumptions, and it undermines the advertised optimality claim as a matter of theorem applicability, but it is not a circular derivation: the lower bound does not assume the upper bound, and the upper bound is not defined in terms of the lower bound. The paper's self-citation is to an independent probabilistic tool, not to the paper's own conclusion, so the circularity burden is not met.
Assumptions & free parameters
free parameters (1)
- step-size schedule eta_t = 2/(mu(t+1)) =
2/(mu(t+1))
assumptions (5)
- domain assumption Oracle noise z_t has zero mean conditional on the past and is either bounded (||z_t|| <= 1 a.s.) or kappa-subgaussian conditioned on F_{t-1}.
- domain assumption f is mu-strongly convex and L-Lipschitz on a closed convex set X.
- standard math The Generalized Freedman Inequality of Harvey et al. 2018 (Theorem 2.2 and Theorem 3.3) is valid.
- standard math The reverse Chernoff (Klein-Young) lower tail bound is valid for averages of i.i.d. Bernoulli variables.
- standard math Euclidean projection onto X does not increase distance to any point in X.
Cite this review
Pith. "Pith review of Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent." pith.science (2026). https://pith.science/paper/S5U3EE5H
@misc{pith2026190900843,
author = {Pith},
title = {Pith review of: Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent},
year = {2026},
howpublished = {\url{https://pith.science/paper/S5U3EE5H}},
note = {Machine review of arXiv:1909.00843}
}
abstract
We consider stochastic gradient descent algorithms for minimizing a non-smooth, strongly-convex function. Several forms of this algorithm, including suffix averaging, are known to achieve the optimal $O(1/T)$ convergence rate in expectation. We consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. (2011) and prove that it achieves the optimal $O(1/T)$ convergence rate with high probability. Our proof uses a recently developed generalization of Freedman's inequality. Finally, we compare several of these algorithms experimentally and show that this non-uniform averaging strategy outperforms many standard techniques, and with smaller variance.
Figures
Forward citations
Cited by 1 Pith paper
-
Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
First almost sure convergence rates and maximal concentration bounds with exponential tails for general contractive stochastic approximation with Markovian noise, via a diminishing-interval skeleton discretization.
Reference graph
Works this paper leans on
- [1]
-
[2]
Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. CoRR, abs/1812.05217, 2018. URL http://arxiv.org/abs/1812.05217
arXiv 2018
-
[3]
Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15 0 (1): 0 2489--2512, 2014
2014
-
[4]
Making the last iterate of SGD information theoretically optimal
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of SGD information theoretically optimal. arXiv preprint arXiv:1904.12443, 2019
arXiv 1904
-
[5]
Sham M. Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. In NIPS, pages 801--808, 2008
work page 2008
-
[6]
Philip Klein and Neal E Young. On the number of iterations for D antzig-- W olfe optimization and packing-covering approximation algorithms. SIAM Journal on Computing, 44 0 (4): 0 1154--1172, 2015
work page 2015
-
[7]
Simon Lacoste - Julien, Mark W. Schmidt, and Francis R. Bach. A simpler approach to obtaining an O (1/t) convergence rate for the projected stochastic subgradient method. CoRR, abs/1212.2002, 2012. URL http://arxiv.org/abs/1212.2002
arXiv 2002
-
[8]
Concentration inequalities and model selection
Pascal Massart. Concentration inequalities and model selection. Springer, 2007
work page 2007
Show all 11 references
-
[9]
Nesterov and V
Yu. Nesterov and V. Shikhman. Quasi-monotone subgradient methods for nonsmooth convex minimization. Journal of Optimization Theory and Applications, 165 0 (3): 0 917--940, Jun 2015
2015
-
[10]
Making gradient descent optimal for strongly convex stochastic optimization
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of ICML, 2012
2012
-
[11]
High-dimensional probability: An introduction with applications in data science
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, 2018
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.