aiqbench analysis
This paper establishes the theoretical limits of time-uniform convergence rates for standard stochastic gradient descent on smooth convex objectives, proving that $\sqrt{\log n / n}$ is an asymptotic bound that cannot be strictly reached. The authors derive a precise condition involving a dyadic horizon-free schedule and conditional-restart inequalities to determine when these near-optimal bounds are achievable versus impossible under Gaussian noise. These findings refine the fundamental understanding of optimization dynamics in machine learning, distinguishing between what is theoretically possible and what remains an open gap in convergence guarantees.
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
arXiv:2609.08537v1 Announce Type: cross Abstract: We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-\alpha$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. \] The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
Abstract:We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-\alpha$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. \] The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2609.08537 [math.OC]
(or arXiv:2609.08537v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2609.08537 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 233 words
Related coverage
I trained GPT-2 with full-batch gradient descent so you don't have to
LessWrong · Oct 14, 2026
Exploding variance of means of exponentials: least-squares to the rescue – Machine Learning Research Blog
francisbach.com · Sep 27, 2026
Feature Normalization under Finite Training Budgets
arXiv · Oct 14, 2026
Synthesis Superintelligence: from Semiconductors to Superconductors — Periodic Labs’ Liam Fedus and Ekin Dogus Cubuk
Latent Space · Oct 8, 2026