Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules
Authors: Liviu Aolaritei, Lucas Lévy, Francis Bach, Michael I. Jordan
Organizations: Department of Electrical Engineering and Computer Sciences, UC Berkeley, USA · Inria, École Normale Supérieure, PSL Research University, France · Department of Statistics, UC Berkeley, USA
Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon chosen before the algorithm is run, even though practical stopping decisions are made adaptively by inspecting the evolving trajectory. This mismatch creates a fundamental certification problem: fixed-time guarantees do not generally remain valid at data-dependent stopping times, while deterministic horizons derived from worst-case bounds can be highly conservative. We address this problem for strongly convex stochastic optimization by constructing fully observable, trajectory-adaptive upper confidence sequences for the squared distance of the last iterate to the optimizer and the suboptimality of a weighted average. These bounds hold simultaneously over time, attain the optimal 1/t decay rate up to iterated-logarithmic factors in the worst case, and adapt to the realized stochastic gradients, allowing SGD to stop as soon as a prescribed accuracy is certified without sacrificing statistical validity. Our approach treats the evolving SGD trajectory as a sequential experiment whose observations provide evidence about the unknown optimization error. To formalize this perspective, we develop new recursive confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes with time-varying conditional means and predictable ranges that may grow without bound. We further extend these confidence-sequence constructions to minibatch SGD, with the empirical Bernstein bounds exploiting the realized second-moment structure within each minibatch. Numerical experiments show that the resulting stopping rules can require several orders of magnitude fewer iterations than natural deterministic horizons.
Figures & tables
Figure 1: Trajectory-adaptive certification of SGD on an SVM problem with minibatch size b=256 and confidence level 99% . H and EB denote our Hoeffding- and empirical-Bernstein-based confidence sequences, respectively; worst-case is the trajectory-independent version of our Hoeffding construction obtained by replacing the realized squared stochastic-gradient norms ∥gt∥2 by their uniform upper bound G2 , while RSS12 denotes the finite-horizon high-probability bound of Rakhlin et al. [36] . 4 4 4 The bound of Rakhlin et al. [36] is simultaneous over all t≤T , but requires the horizon T to be fixed in advance. More recent fully time-uniform guarantees, such as Pham et al. [33] , remove the need to prescribe T but are numerically more conservative in this comparison. Left: squared distance to the optimizer. Right: suboptimality of the weighted average. The gray curves show the corresponding ground truth. In the right panel, crosses and vertical lines mark the first iteration at which each bound falls below the target ε=10−3 , and hence the time at which that bound first certifies the prescribed accuracy. Further details are provided in Section 5 .
Label
Quantity
Anytime-valid
Trajectory-adaptive
Reference
Zt
Ground truth
∥xt−x⋆∥2
—
—
—
H
Utdist(α)
yes
yes
Theorem 2.3 10 10 10 In the minibatch experiments, we use the direct minibatch extension described at the beginning of Section 4 , replacing σ2 with σ2/b in the corresponding variance processes and gt with gˉt in the SGD recursions.
EB
Utdist,EB,MB(α)
yes
yes
Corollary 4.3
worst-case
Uˇtdist(α)
yes
no
( 75 )
RSS12
( 77 )
no
no
[ 36 ]
Fˉt
Ground truth
f(xˉt)−f(x⋆)
—
—
—
Table 1: Quantities compared in the experiments. All bounds are plotted at confidence level 1−α=0.99 and use the same trajectory.
Figure 2: SGD on the covertype.binary dataset for minibatch sizes b=1 (left), 32 (middle), and 1024 (right). Top row: squared distance to the optimum. Bottom row: suboptimality of the weighted average. All panels use the conventions of Figure 4 : ground truth (solid gray line), worst-case bound (dash-dotted blue line), H (solid orange line with squares), and EB (solid red line with triangles); RSS12 (dotted blue line) is shown in the distance panels only.
Figure 3: SGD on three datasets generated with make_classification , with increasing class separability from A to C . Left: squared distance to the optimum. Right: suboptimality of the weighted average. Each panel shows the ground truth (solid gray lines) and EB (solid red lines) for each dataset, with increasing shade darkness from A to C and each curve labelled accordingly, together with the worst-case bound (dash-dotted blue line); RSS12 (dotted blue line) is shown in the distance panel only.
class_sep
flip_y
A (low separability)
0.2
0.1
B (medium separability)
1.0
0.02
C (high separability)
5.0
0.0
Table 2: Parameters of each generated dataset.
Figure 4: SGD on dataset B from Table 2 , with b=256 , comparing the bounds obtained with the correct gradient bound G and with G overestimated by a factor of 10 . Solid and dash-dotted lines correspond to the correct value, while dashed lines in lighter shades correspond to the overestimated one. Each panel shows the ground truth (solid gray line), the worst-case bound (blue line), H (orange line with squares), and EB (red line with triangles).
Figure 5: SGD on make_classification dataset, b=256 , comparing EB computed with the correct value of R0 and with R0 over-estimated by factors 10 , 100 and 1000 . Each panel shows the ground truth (solid gray line) and the four confidence sequences (red lines, in increasingly light shades and increasingly sparse dotting as the over-estimation factor grows, as indicated in the legend).
Figure 6: SGD on the covertype.binary dataset in a true single-pass regime, with b=256 . Each panel shows the worst-case bound (dash-dotted blue line), H (solid orange line with squares), and EB (solid red line with triangles).
AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal last-iterate rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Ω(logT/T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that logT in existing average-iterate upper bounds is unavoidable. Finally, we show that this logT loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/T).
Weiming Ou, Xiao Wang
Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics
Most convergence guarantees for iterative stochastic algorithms are stated at a fixed iteration count and do not justify stopping at a data-dependent time. Recent work has constructed anytime-valid envelopes that do, but deterministic envelopes are typically too conservative for practical stopping, and existing data-adaptive ones are derived case-by-case, each coupling a specific algorithm to a specific noise model and boundary construction. This paper provides a general recipe for constructing such anytime-valid data-adaptive boundaries for a large class of iterative algorithms. Performance measures of many of these algorithms satisfy a one-step recursion that reduces the entire error analysis to a single general requirement: time-uniform concentration for predictably weighted sums of noise. We formalize this through a strongly adapted sub-ψ condition, and derive off-the-shelf boundary constructions via continuous and discrete mixtures, stitching, and product betting martingales. We show how these boundaries can be directly coupled with a separate algorithmic analysis that derives the one-step recursion to provide a class of readymade anytime-valid envelopes across diverse settings including stochastic gradient descent (SGD), temporal difference learning, and Bures-Wasserstein SGD. In particular, for SGD, our framework either recovers or significantly sharpens every existing envelope we are aware of. Our constructions come with explicit implementation details and are substantiated by numerical experiments.
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 logn/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
j=1∑∞h(2j)21<∞.
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.
Ruijie Li, Kang Chen, Tianyu Wang
School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University