The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

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 √log n / n but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence h satisfying h(n) = o(√n), a bound of order h(n)/√n, holding simultaneously for all n with probability at least 1-α and uniformly over the problem class, is achievable if and only if [ sumj = 1∞ frac1h(2j)2 < ∞. ] 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.