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

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

Source-linked AI summary

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

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

arXiv:2608.25551v1Aug 26, 2026cs.LGmath.OCmath.STstat.ML

TL;DR

The paper addresses the lack of valid certificates for adaptive SGD stopping and the conservatism of worst-case deterministic horizons. It develops fully observable, trajectory-adaptive confidence sequences for strongly convex SGD, with refined empirical-Bernstein constructions, and finds that the resulting stopping rules can terminate several orders of magnitude earlier than trajectory-independent bounds. A remaining gap persists between the confidence sequences and the comparison bounds.

Problem
Fixed-horizon guarantees generally do not remain valid at data-dependent stopping times, while horizons obtained by inverting worst-case guarantees can be highly conservative.
Method
The paper constructs sharper, fully observable confidence sequences for strongly convex SGD, including refinements based on realized increments and extensions to minibatch settings.
Results
The resulting stopping rules terminate several orders of magnitude earlier than trajectory-independent bounds in numerical experiments.
Takeaways & Limitations
Trajectory-adaptive certificates can support online SGD stopping while adapting to the realized trajectory and retaining the paper's stated validity.
Takeaways & Limitations
A considerable gap remains between the confidence sequences and the trajectory-independent bounds used for comparison.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the gap between fixed-horizon guarantees and adaptive stopping by constructing time-uniform, trajectory-adaptive certificates for strongly convex SGD. These certificates support observable stopping rules while preserving worst-case rates and adapting to realized stochastic behavior.

Motivation: Fixed-time high-probability guarantees generally do not remain valid when SGD is stopped at a data-dependent time chosen by inspecting the run.This creates a gap between rigorous but potentially conservative deterministic horizons and adaptive procedures without certificates.
Certified stopping: A trajectory-adaptive stopping rule can stop at the first time its confidence bound falls below a prescribed tolerance while retaining validity at the selected time.For distance certification, the returned iterate is certified within the target squared distance with probability at least 1 − α whenever the stopping time is finite.
Rates and adaptivity: The confidence sequences attain the optimal 1/t worst-case decay rate up to iterated-logarithmic factors while adapting to stochastic fluctuations observed along the trajectory.The strongly convex setting exploits contractivity but requires new recursive and self-normalized sequential techniques.
Contributions: The paper constructs fully observable anytime-valid upper confidence sequences for last-iterate squared distance and weighted-average suboptimality.The bounds use observed stochastic gradients, predictable stepsizes, and iterates, and remain valid simultaneously throughout the run.
Empirical findings: Numerical experiments show that trajectory-adaptive stopping rules can terminate several orders of magnitude earlier than deterministic horizons from conventional fixed-time guarantees.In Figure 1, the trajectory-adaptive distance certificate is roughly five orders of magnitude smaller than the finite-horizon bound of Rakhlin et al., with an even larger gap relative to Pham et al.'s time-uniform bound.
Refined and minibatch bounds: The paper extends the constructions to minibatch SGD and develops a time-uniform empirical Bernstein inequality using realized gradient magnitudes and growing predictable ranges.The minibatch extension exploits reduced conditional variance, while the empirical Bernstein refinement can produce substantially smaller bounds than worst-case alternatives.

2 Confidence Sequences under Sub-Gaussian Noise

The paper constructs observable, time-uniform confidence sequences for last-iterate distance and weighted-average suboptimality in SGD. Recursive trajectory-based bounds preserve near-optimal 1/t decay up to iterated-logarithmic factors and remain valid under adaptive stepsizes.

Confidence-sequence framework: Anytime-valid confidence sequences provide simultaneous-in-time upper bounds for the last-iterate squared distance and weighted-average suboptimality.These bounds turn trajectory observations into performance certificates that remain valid throughout the run.
Confidence-sequence framework: The generic concentration step controls adapted partial sums using conditional exponential bounds, predictable variance proxies, and stitched intrinsic-time boundaries.Dyadic stitching combines fixed-λ bounds across variance scales to produce a curved boundary valid over an infinite horizon.
Last-iterate distance: The recursive distance construction converts initialization, observed squared-gradient accumulation, and directional gradient noise into a fully observable certificate.The resulting process is computable from an observable upper bound R0 and the SGD trajectory while retaining simultaneous coverage.
Adaptive stepsizes: The confidence sequences accommodate predictable stepsizes selected adaptively from the observed trajectory rather than requiring a fixed schedule or a priori convergence-rate choice.This flexibility is stated for the last-iterate construction and supports trajectory-adaptive operation.
Last-iterate distance: The observable last-iterate distance envelope achieves the worst-case 1/t rate up to an iterated-logarithmic factor under the classical stepsize specialization.A direct diameter substitution would instead yield t^-1/2-type decay, whereas the recursive envelope preserves the near-1/t rate.
Weighted-average suboptimality: The weighted-average construction yields a fully observable upper confidence sequence whose worst-case suboptimality rate is also 1/t up to iterated-logarithmic factors.Passing from distance bounds to suboptimality does not degrade the optimal worst-case rate and improves dependence on the strong-convexity parameter by one power.

3 Refined Confidence Sequences under Bounded Gradients

The paper develops empirical-Bernstein confidence sequences that adapt to realized stochastic gradients while remaining valid uniformly over time. These constructions provide observable bounds for both last-iterate distance and weighted-average suboptimality, with near-1/t worst-case decay up to iterated-logarithmic factors.

Construction: The empirical-Bernstein construction replaces the fixed proxy G2 with realized squared gradient increments.This allows the stochastic contribution to respond to observed gradient magnitudes along the trajectory.
Construction: A time-uniform empirical-Bernstein inequality handles predictable ranges that vary with history and grow without a finite uniform bound.The construction stitches over both accumulated quadratic variation and the largest predictable range encountered.
Theory: The paper presents the growing-range empirical-Bernstein bound as a new time-uniform concentration result for adapted processes.The authors connect the construction to prior empirical-Bernstein supermartingale methods and self-normalized bounds.
Last-iterate distance: The resulting recursive distance confidence sequence is fully observable from the initial bound and SGD trajectory.Its quadratic process depends on realized values of ∥g_s∥2, while the recursive envelope removes the unknown distance.
Rates: The observable distance sequence retains the near-1/t worst-case decay rate, with the growing-range contribution lower order.The same decay conclusions are established for the weighted-average suboptimality sequence.
Weighted-average suboptimality: The refined confidence sequence for weighted-average suboptimality is likewise fully observable and recovers near-1/t worst-case decay.Its stochastic term is the one isolated by the suboptimality decomposition.

4 Minibatch Extensions

The confidence-sequence framework extends to minibatch SGD by combining averaged stochastic increments with realized within-minibatch second moments. Spectral relaxation makes the resulting bounds observable while preserving trajectory-specific geometric information.

Basic extension: Sub-Gaussian minibatch sequences follow by replacing σ2 with σ2/b and g_t with the minibatch average.This direct extension uses the conditional sub-Gaussian behavior of averaged independent gradients.
Empirical-Bernstein extension: The minibatch empirical-Bernstein construction applies concentration before averaging, retaining individual realized quadratic contributions.The leading square-root term receives the usual minibatch reduction, while the linear range term carries an explicit 1/b factor.
Empirical-Bernstein extension: Proposition 4.1 supplies a minibatch empirical-Bernstein bound for conditionally independent observations with a growing predictable range.For b = 1, it reduces exactly to the single-gradient result.
Distance: The minibatch distance confidence sequence is fully observable and uses a spectral relaxation of the within-minibatch second-moment matrix.The largest eigenvalue provides a direction-free bound based entirely on observed stochastic gradients.
Distance: The spectral relaxation can be sharper than the uniform worst-case factor G2 when realized gradients are small or spread across directions.Its largest eigenvalue can be computed from a b × b Gram matrix rather than a full d × d matrix.
Suboptimality: The same minibatch construction extends to weighted-average suboptimality and remains fully observable from the minibatch SGD trajectory.With b = 1, both minibatch constructions reduce exactly to their single-gradient empirical-Bernstein counterparts.

5 Experiments

Experiments on real and synthetic SVM instances show that trajectory-adaptive confidence sequences can certify accuracy much earlier than deterministic or worst-case bounds. Empirical-Bernstein bounds consistently exploit realized gradient and minibatch structure, including in a true single-pass regime.

Certified stopping: 312 times earlier, the empirical-Bernstein minibatch bound certifies ε = 10−3 than the worst-case baseline in the introductory experiment.The corresponding lookup counts are 5.1 × 106 for EB, 2.6 × 108 for H, and 1.6 × 109 for the worst-case baseline.
Overall findings: Empirical-Bernstein sequences are consistently tighter than Hoeffding-based sequences in the reported experiments.Their advantage reflects use of realized stochastic-gradient and within-minibatch second-moment information.
Minibatching: 53.8%, empirical-Bernstein recovery of the worst-case-to-ground-truth gap reaches for b = 1024, compared with 24.8% for b = 1.The reported recovery fractions are 24.8%, 43.6%, and 53.8% for b = 1, 32, and 1024.
Adaptivity across instances: Three synthetic datasets with fixed bound constants produce different empirical-Bernstein certificates as class separability increases.After 106 iterations, the suboptimality bound is roughly 17 times tighter for C than for A: 1.9 × 10−6 versus 3.2 × 10−5.
Adaptivity across instances: 73% and 98%, the average λmax(bΣt) over the final 1% decreases from A to B and from A to C, respectively.A deterministic bound depending only on G cannot distinguish these trajectories.
Robustness: A factor of 1.06, misspecified and correctly specified empirical-Bernstein curves differ by after 107 iterations for both reported quantities.Conservative choices of G and R0 have largely transient effects along the tested trajectories.
True single-pass: 2269 SGD iterations, the true single-pass run uses complete minibatches with no observation reused.The reported improvements persist in this single-pass expected-risk setting.
Certified stopping: Several orders of magnitude earlier, trajectory-adaptive bounds certify target accuracy than trajectory-independent bounds in the reported experiments.The improvement is attributed to adaptation to the realized SGD trajectory.

A.1.2 Proof of Proposition 2.2

The supplied proof passages show a local proof step for controlling a time-uniform process and substituting that control into the distance confidence-sequence decomposition.

Proof step: The proof controls the auxiliary process uniformly over time using predictable measurability and a conditional concentration lemma.The resulting bound is substituted into the preceding decomposition to obtain the distance confidence sequence.

A.1.3 Proof of Theorem 2.3

The proof establishes that the recursive observable bounds are well-defined and then verifies their claimed uniform control by induction, logarithmic-factor bounds, and deterministic-term estimates.

Recursive construction: The recursive quantities are fully observable and recursively well-defined because each time-t update uses previously defined quantities and data observed through time t.The construction begins from an explicit initialization and proceeds inductively.
Uniform validity: The confidence event from Proposition 2.2 has probability at least 1 − α, and the proof verifies the target bound on this event.Monotonicity of Hα and induction over time connect the event to the recursive envelope.
Inductive proof: The induction starts at t0 using the initialization bounds, A3 = 3, η3 = 1/(3µ), and the gradient bound ∥g3∥≤G.The base case uses K = 4096 and the standing bounds on R0 and the stochastic gradients.
Inductive proof: The induction step combines the recursive observable intrinsic time with the induction hypothesis, monotonicity of Ls, and absorption of initial and truncation terms into a common scale.The proof separately bounds deterministic terms and controls the stitched logarithmic factor.
Logarithmic control: The stitched logarithmic factor is bounded by iterated logarithms of B, t, and Lt, yielding the claimed recursive bound after substituting K = 4096.The argument uses elementary logarithmic inequalities and closes the induction.

A.1.5 Proof of Proposition 2.7

The proof of Proposition 2.7 obtains a time-uniform bound for the weighted-average error by applying an empirical Bernstein lemma to its adapted increments and substituting the resulting observable boundary.

Increment control: Because xt is Ft−1-measurable, Assumption 1.3(ii) applies in the predictable direction t(x⋆−xt), giving the required conditional control.This establishes the increment conditions needed for the empirical Bernstein argument.
Empirical Bernstein step: Applying Lemma 2.1 to the weighted-average process and its variance proxy yields a uniform confidence bound for the stochastic term.The proof identifies the relevant variance and range parameters before applying the lemma.
Conclusion: Substituting the stochastic bound into the preceding decomposition and using the definition of Usub produces the observable weighted-average suboptimality bound.The resulting expression is expressed through quantities available along the trajectory.

A.1.6 Proof of Theorem 2.8

The proof of Theorem 2.8 combines two confidence events to establish the observable last-iterate suboptimality bound uniformly over all times after t0.

Proof setup: The proof first invokes the recursive observable bounds needed to control the stochastic and deterministic components of the last-iterate error.These bounds are used up to time t in the theorem’s target inequality.
Uniform event: The event E2 has probability at least 1 − α/2, and on E2 the bound Usub is verified for every t ≥ t0.The argument applies the previously established confidence-sequence result at the required confidence level.
Probability conclusion: The final probability statement follows by combining the event controlling each recursive component with the initial bound Zt0 ≤ R0 and applying a union bound.This completes the uniform-in-time theorem guarantee.

A.1.7 Proof of Proposition 2.9

The proof of Proposition 2.9 bounds the weighted-average suboptimality by controlling deterministic terms, the observable boundary, and the resulting effective intrinsic time and logarithmic factor.

Proof convention: The proof treats the universal constant C as finite and allows its value to change between inequalities.This convention is used throughout the proposition’s estimates.
Decomposition: The weighted-average suboptimality bound is expanded using its observable definition and the initialization relation µt0(t0 −1)/4 = 3µ.The proof then separates deterministic and stochastic contributions.
Deterministic terms: The deterministic terms are bounded using ∥gs∥≤G and the standing initialization bound on R0.These estimates provide the baseline scale for the proposition.
Boundary control: Remark 2.6 supplies an observable boundary for the remaining term at confidence level α/2, for every s ≥ 5.The boundary uses the logarithmic factor from Proposition 2.4.
Intrinsic-time control: The effective intrinsic time is controlled by logarithms of Bsub, t, and Lsub, whose iterated-logarithmic contributions are absorbed into Lsub.Combining these estimates yields the proposition almost surely.

A.2.1 Proof of Lemma 3.2

The proof establishes the scalar inequality underlying Lemma 3.2 by analyzing hθ over separate intervals and then applies it conditionally. It extends fixed-parameter bounds uniformly through dyadic stitching, yielding a fully observable recursive process.

Scalar inequality: The proof verifies hθ(x) ≥ 0 on x ≥ −1 by analyzing its monotonicity separately on [0, ∞) and [−1, 0].It uses endpoint values hθ(−1) = 0 and hθ(0) = 0, together with the sign change of qθ.
Conditional bound: The scalar inequality is converted into a conditional exponential bound by setting m := E[X | G] and applying the inequality to X/b.The argument uses conditional expectations and the G-measurability of e−λm.
Uniformization: Fixed-λ bounds are stitched over dyadic ranges of Wt and Ct using running maxima, predictability, and a union bound.The resulting statement holds simultaneously over the dyadic indices and all t ≥ t0, with monotonicity inherited from the boundary terms.
Recursive construction: The recursion defines nonnegative Ft-measurable quantities, so the resulting confidence process is fully observable.An induction over time establishes the recursive event, and Proposition B.1 supplies its probability guarantee.

A.2.4 Proof of Proposition 3.6

The proof of Proposition 3.6 controls the empirical Bernstein boundary through induction. It bounds deterministic and stochastic contributions, manages logarithmic factors, and derives the stated asymptotic forms under the prescribed stepsize.

Inductive control: The proof uses induction from time 4 to control the recursive quantities defining the empirical Bernstein boundary.The base case follows from A3η3 = 1/µ and the lower bounds L4 ≥ 1 and Φ4 ≥ L4/4.
Boundary arguments: The two boundary arguments are bounded separately, with initial contributions and unit floors absorbed into the resulting estimates.The proof handles the s = 3 contribution explicitly before applying the induction hypothesis for later times.
Logarithmic factor: The logarithmic factor is controlled by the definitions of Lt and elementary logarithmic inequalities, producing iterated-logarithmic terms.The bounds use log((j + 1)(j + 2)) ≤ 2 log(j + 2) and control nested logarithms involving t, Lt, and qt.
Final estimate: The square-root and linear-range contributions are each bounded by multiples of the empirical Bernstein scale, closing the induction.A sufficiently large universal constant K absorbs the combined coefficient and proves the main boundary estimate.
Asymptotic consequence: For fixed α and problem parameters, the prescribed deterministic stepsize makes condition (37) automatic and yields the lower-order relation t = o(qt).The proposition's probability statement combines two events, each having probability at least 1 − β.

A.2.6 Proof of Proposition 3.9

The proof of Proposition 3.9 applies the same inductive empirical-Bernstein analysis to suboptimality-related quantities. It controls the boundary arguments, logarithmic terms, and deterministic components to obtain the stated estimates.

Inductive boundary control: The proof follows a predictable-truncation and stitching argument while inductively controlling the two arguments of the empirical Bernstein boundary.The sequence Lt is nondecreasing and satisfies Lt ≥ 1, supporting the subsequent bounds.
Logarithmic control: The logarithmic factor is bounded using the definitions in (30), dyadic-index inequalities, and nested logarithmic controls.The resulting expression includes logarithms of t, Lt, and 1 + qt, together with iterated logarithmic terms.
Boundary estimate: The square-root and linear terms are combined with the empirical Bernstein bounds to establish the proposition's main estimate.The proof absorbs initial contributions and unit floors before applying the resulting inequalities.
Deterministic terms: Assumption 3.1, R0 = G2/µ2, and St ≥ t2/4 control the deterministic terms appearing in the boundary.Using Lt ≥ 1 strengthens the resulting estimate and supports the sharper form under the additional condition Lt ≤ t.
Asymptotic consequence: For fixed problem parameters, the proof obtains the lower-order relation t = o(qt), matching the proposition's stated interpretation.This conclusion follows from the sharper estimate in the regime used by the proposition.

A.3.1 Proof of Proposition 4.1

The proof of Proposition 4.1 extends the empirical-Bernstein construction through predictable truncation and dyadic stitching over intrinsic-time and range scales. The resulting bound holds simultaneously for all t ≥ t0 with probability at least 1 − α.

Predictable truncation: The proof fixes dyadic range levels and uses predictable truncation to handle processes with time-varying ranges.The construction tracks both intrinsic-time and range scales.
Supermartingale construction: Conditional independence of the exponential factors preserves a nonnegative supermartingale after replacing centered increments by truncated ranges.This preserves the exponential-process argument used for the earlier theorem.
Uniform guarantee: Dyadic stitching over intrinsic-time and range scales yields a bound simultaneously for every t ≥ t0 with probability at least 1 − α.The uniform statement is the proposition's central probabilistic conclusion.
Normalization: The conditional mean relation ms = E[Hs | Fs−1] identifies the normalization used to obtain the final bound.Division by b completes the proposition's stated inequality.

B Additional Results

The appendix establishes refined confidence sequences for last-iterate distance and weighted-average suboptimality. Its proofs combine contractive SGD decompositions with time-uniform concentration for adapted processes.

Refined confidence sequences: Proposition B.1 establishes a refined confidence sequence for the squared distance between the last iterate and the optimizer.The result is obtained after applying a time-uniform bound and substituting it into the distance decomposition.
Concentration argument: The concentration argument applies to adapted processes with predictable quadratic processes and running predictable ranges, using conditional unbiasedness.The proof also invokes bounds on the stochastic-gradient-derived process under Assumption 3.1.
Refined confidence sequences: Proposition B.2 establishes a refined confidence sequence for the suboptimality of the weighted average using η_t = 2/(µ(t + 1)).The construction uses the quantities V_sub,EB_t and B_sub,EB defined in the proposition.
Distance decomposition: Projection nonexpansiveness and strong monotonicity yield a one-step contractive recursion for the squared distance to the optimizer.The recursion uses x⋆ ∈ X and the first-order optimality condition at x⋆.
Decomposition proofs: The appendix unrolls the contractive recursion for predictable stepsizes and divides by positive normalization factors to obtain the stated decompositions.For the last-iterate result, Assumption 1.4 ensures A_t > 0.
Weighted-average decomposition: The weighted-average decomposition retains the directional gradient-noise term pathwise rather than replacing it with its expectation.This supports the subsequent anytime-valid concentration analysis.