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.

Source: arXiv cs.LG | 2026-09-09