Search papers, labs, and topics across Lattice.
This paper establishes the exact theoretical boundary for anytime (time-uniform), high-probability convergence of standard SGD raw iterates on smooth convex objectives. The authors prove that a time-uniform rate of $h(n)/\sqrt{n}$ is achievable if and only if the dyadic series $\sum_{j=1}^{\infty} h(2^j)^{-2}$ converges, revealing that convergence can get arbitrarily close to $\sqrt{\log n / n}$ but fundamentally never attain it. The matching lower bound applies to all deterministic nonnegative step-size schedules even on 1D Gaussian problems, resolving the open question of optimal anytime rates for standard SGD.
Standard SGD can get arbitrarily close to an anytime convergence rate of $\sqrt{\log n / n}$, but hitting that benchmark exactly is mathematically impossible under any deterministic step-size schedule.
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-伪$ 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.
