Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules

Liviu Aolaritei; Lucas Lévy; Francis Bach; Michael I. Jordan

cs.LGAug 26, 2026

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

Abstract

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 $\left\|g_{t}\right\|^{2}$ by their uniform upper bound $G^{2}$ , 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\leq 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 $\varepsilon=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
$Z_{t}$	Ground truth	$\\|x_{t}-x^{\star}\\|^{2}$	—	—	—
	H	$\widehat{U}^{\mathrm{dist}}_{t}(\alpha)$	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 $\sigma^{2}$ with $\sigma^{2}/b$ in the corresponding variance processes and $g_{t}$ with $\bar{g}_{t}$ in the SGD recursions.
	EB	$\widehat{U}^{\mathrm{dist,EB,MB}}_{t}(\alpha)$	yes	yes	Corollary 4.3
	worst-case	$\check{U}^{\mathrm{dist}}_{t}(\alpha)$	yes	no	( 75 )
	RSS12	( 77 )	no	no	[ 36 ]
$\bar{F}_{t}$	Ground truth	$f(\bar{x}_{t})-f(x^{\star})$	—	—	—

Table 1: Quantities compared in the experiments. All bounds are plotted at confidence level

1-\alpha=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 $R_{0}$ and with $R_{0}$ 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).

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
Sep 26, 2026Weiming Ou, Xiao WangConvergence Analysis Adaptive Gradient Methods
Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics
A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms
Oct 16, 2026Soham Bonnerjee, Aaditya RamdasStochastic Optimization
University of Pennsylvania · Stanford University
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Sep 8, 2026Ruijie Li, Kang Chen, Tianyu WangLearning Rate Scheduling Last-Iterate Convergence
School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University

Sep 26, 2026J/K move · Enter open · S save

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

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

Convergence Analysis Adaptive Gradient Methods Last-Iterate Convergence

Open paper AskPDF arXiv

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

Ω(\log T/\sqrt T)

lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that

\log T

in existing average-iterate upper bounds is unavoidable. Finally, we show that this

\log T

loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates

{O}(1/\sqrt{T})

Abstract

Stochastic Optimization

Explore similar work

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms

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