The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Ruijie Li, Kang Chen, Tianyu Wang
math.OC · cs.LG · stat.ML
Quick verdict
Proves an exact iff frontier (Σ1/h(2^j)²<∞) for time-uniform h(n)/√n SGD bounds; spot-checked proofs hold; scope is deterministic schedules only.
Summary
This paper characterizes exactly when standard stochastic gradient descent (SGD) on smooth convex objectives achieves a time-uniform (anytime-valid) bound of order h(n)/√n on the raw last iterate, for a positive eventually nondecreasing profile h with h(n)=o(√n). Theorem 2.3 proves that a single deterministic schedule, independent of horizon and confidence level, achieves such a bound uniformly over the problem class with conditionally unbiased norm-sub-Gaussian noise if and only if Σ_j 1/h(2^j)² converges. Sufficiency is constructive: dyadic epochs with constant per-epoch stepsizes, and an additive conditional-restart inequality (Theorem 3.2) separating harmonic and confidence costs. Necessity is proved on a one-dimensional analytic quartic-flat objective with Gaussian noise, via a per-epoch step-mass ceiling from Gaussian block anti-concentration (Lemma 4.6) and a Riccati-type recurrence (Lemma 4.8). Consequently (log n)^{(1+ε)/2}/√n is achievable for every ε>0 while √(log n/n) is not, and the achievable class has no asymptotically smallest element. Limitations: the characterization covers deterministic schedules for plain SGD only — adaptive or randomized rules and momentum methods fall outside the theorems; the exact scope of the Lean 4 formalization is not specified in the text; constants are non-explicit and no numerical experiments are reported.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
4 strengths · 4 weaknesses · 4 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- A time-uniform O(h(n)/√n) bound for plain SGD on smooth convex objectives under one deterministic horizon- and confidence-free schedule is achievable if and only if Σ_j 1/h(2^j)² < ∞ (Theorem 2.3).
- (log n)^{(1+ε)/2}/√n is achievable for every ε>0 but √(log n/n) is not, and the achievable profile class has no asymptotically smallest element (Corollary 2.4).
- The necessity obstruction already arises for a one-dimensional analytic quartic-flat objective with Gaussian noise and applies to every deterministic nonnegative schedule, even α-dependent ones (Theorem 4.1).
- The enabling tool is an additive conditional-restart inequality (Theorem 3.2) whose harmonic and confidence terms separate, making per-epoch stochastic overhead j/h_j² vanish exactly when the reciprocal-square series converges.
Strengths
Complete iff characterization, not just matching bounds
Theorem 2.3 pins achievability exactly to Σ_j h(2^j)^{-2}<∞ at the level of arbitrary slowly varying profiles, not a prescribed log power; Corollary 2.4 (Appendix A) further shows the achievable class has no asymptotically smallest element via an explicit reweighted tail-sum construction.
The key technical device is load-bearing, not cosmetic
Theorem 3.2 gives additive dependence 6σ²γH_r + 9σ²γlog(1/δ) via remaining-time weights; Section 3.3 correctly shows a multiplicative dependence would produce j²/h_j² per epoch and destroy the frontier, while the additive form gives j/h_j² which vanishes by Lemma 3.3.
Unusually strong lower bound
Verification artifacts and disclosure
Weaknesses
Frontier is protocol-specific
Lean formalization scope is vague
Non-constructive constants and idle prefix
Class restrictions and a mild envelope asymmetry
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies plain SGD (x_{t+1}=x_t−η_tG(x_t,ξ_t)) on L-smooth convex objectives over Hilbert spaces with conditionally unbiased norm-sub-Gaussian noise (E[exp(‖Z_t‖²/σ²)|F_t]≤e), and asks: for which overhead profiles h (positive, eventually nondecreasing, h(n)=o(√n)) does P(Δ_n ≤ C·h(n)/√n, ∀n) ≥ 1−α hold under one deterministic schedule fixed before the run, independent of horizon and confidence (Definition 2.2)? The answer (Theorem 2.3) is exact: achievable ⟺ Σ_{j≥1} 1/h(2^j)² < ∞. Consequences: (log n)^{(1+ε)/2}/√n is achievable for every ε>0; √(log n)/√n is not; and there is no asymptotically smallest achievable profile (Corollary 2.4, proved in Appendix A via a reweighted tail-sum construction). The abstract's slogan — arbitrarily close to √(log n/n) but never reaching it — is exactly what the criterion yields, since Σ1/j diverges while Σ1/j^{1+ε} converges.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 4 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does time-uniform (anytime) convergence of SGD mean?
A single high-probability bound that holds simultaneously at every iteration n of the infinite run — one event over the whole trajectory — so it remains valid at data-dependent stopping times. Fixed-horizon bounds hold only at one pre-chosen n and cannot justify such stopping rules.
Why can't SGD reach the √(log n/n) time-uniform rate?
The paper proves an overhead profile h works if and only if Σ_j 1/h(2^j)² converges. For h(n)=√(log n) this series is a constant multiple of the harmonic series and diverges, so no deterministic schedule achieves it; the obstruction already appears on a one-dimensional quartic-flat objective with Gaussian noise.
Which rates are achievable instead?
h(n)=(log n)^{(1+ε)/2} for any ε>0, plus slower iterated-logarithmic profiles approaching √(log n) arbitrarily closely; there is no single best achievable profile. All of this concerns plain SGD with a deterministic schedule — momentum variants in prior work already attain comparable rates.
Is there code or a formal proof?
Complete proofs are in the appendices, and the authors link a public Lean 4 machine-checked formalization of the targeted results on GitHub; no numerical experiments are reported in the paper.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The Lean 4 formalization, its audit files, and rebuild instructions are supplementary artifacts referenced but not included in the extracted text; the exact set of kernel-checked theorems cannot be confirmed from the paper alone.
- PDF extraction garbles some inline math (superscripts, fractions); every constant cited in this review was cross-checked in its surrounding context before quotation.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.