📊 statistics

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

This paper introduces trajectory-adaptive stopping rules for strongly convex stochastic optimization that provide time-uniform, data-dependent confidence sequences for optimization error, enabling statistically valid early termination with significantly fewer iterations than traditional fixed-time horizons.

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

Published 2026-08-27

📖 7 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, a single method has become the engine driving everything from recognizing faces in photos to predicting stock market trends. This method is a way of teaching computers to find the best possible solution to a problem by taking small, noisy steps toward a goal. Imagine trying to find the lowest point in a foggy valley. You cannot see the bottom, and the ground beneath your feet shifts slightly with every step. You must rely on the immediate slope you feel under your foot to decide which way to walk. This is how machines learn: they use a process called stochastic gradient descent, where they take many small, imperfect steps based on random samples of data, gradually inching closer to the optimal answer.

For decades, scientists have been able to predict how long this journey would take in the worst-case scenario. They could tell a computer, "Run for exactly one million steps, and you will be close enough to the answer." This approach works, but it is like telling a hiker to walk for a fixed number of hours regardless of whether they have already reached the valley floor. In practice, the computer often arrives at the solution much faster than the worst-case prediction suggests. However, the computer has no way of knowing it has arrived. It cannot stop early because the traditional rules of the game do not allow it to check its progress and make a decision based on what it has actually seen so far. If it stops too soon, it might be wrong; if it waits too long, it wastes time and energy.

A team of researchers has now solved this dilemma by creating a new way for the computer to certify its own success in real time. They developed a system that acts like a constantly updating safety net, watching the computer's journey step by step. Instead of waiting for a pre-set time to declare victory, this new method allows the computer to stop the moment it has gathered enough evidence to prove, with high statistical certainty, that it has reached the desired level of accuracy. The researchers tested this on a common machine learning task involving support vector machines, a tool used for sorting data into categories. They found that their new method allowed the computer to stop running hundreds of times earlier than the old, fixed-time rules would have permitted, without ever sacrificing the guarantee that the answer was correct.

The core of this breakthrough lies in how the researchers treated the computer's path. Rather than viewing the sequence of steps as a fixed march toward a distant horizon, they treated it as a live experiment where every step provided new clues about the final destination. In the past, the rules for stopping were rigid: you had to decide how long to run before you started. The new approach is adaptive. It constructs a "confidence sequence," which is essentially a shrinking envelope around the computer's current position. As the computer moves, this envelope tightens around the true answer. The moment the envelope becomes small enough to fit within the user's required margin of error, the computer knows it has arrived.

This might sound simple, but the mathematics behind it is intricate because the computer's path is full of randomness. The steps are not perfectly straight; they wobble due to the noise in the data. If you simply checked the position at a random moment, you might get lucky and see a wobble that looks like progress, leading you to stop too early. The researchers solved this by ensuring their safety net remained valid no matter when you looked at it. They proved that their bounds hold true simultaneously at every single step of the journey. This means the computer can check its progress as often as it likes, and the guarantee of accuracy never breaks, even if the decision to stop is made based on the very data being observed.

The researchers also discovered that their method could be made even sharper by paying attention to the specific details of the data being processed. In some situations, the noise in the data is smaller than the theoretical maximum. The new system detects this and tightens its safety net accordingly, allowing the computer to stop even sooner. When they tested this on a dataset with hundreds of thousands of entries, the results were striking. For a specific target accuracy, the new method certified the solution in a fraction of the time required by the traditional, conservative estimates. In one instance, the computer stopped after a few million steps, whereas the old rules would have forced it to run for over a billion steps to achieve the same level of confidence.

The study also examined how these rules hold up when the computer processes data in groups, or "minibatches," rather than one piece at a time. This is a common practice in modern computing to speed things up. The researchers found that their adaptive method became even more effective as the size of these groups increased. The ability to see the structure of the noise within each group allowed the safety net to shrink much faster, further reducing the number of steps needed. This suggests that as computing power grows and allows for larger groups of data to be processed at once, the benefits of this adaptive stopping rule will only become more pronounced.

Perhaps most importantly, the researchers showed that their method is robust to uncertainty. In the real world, we rarely know the exact limits of the noise in our data. We often have to guess a safe upper bound. The study demonstrated that even if these guesses are overly cautious, the new method quickly adjusts. The initial guess only affects the very beginning of the run; as the computer gathers more data, the system relies on what it actually sees rather than the initial guess. This means that users do not need to be perfect experts on their data to benefit from the method; they just need a reasonable, safe estimate to start with.

The implications of this work extend beyond just saving time. It changes the philosophy of how we run these algorithms. Instead of following a rigid script written before the computation begins, the algorithm can now respond to the reality of the data it encounters. It turns a blind march into a guided exploration. The researchers proved that this flexibility does not come at the cost of reliability. The computer can stop early, but it stops with a certificate of accuracy that is mathematically sound. This bridges the gap between the theoretical guarantees that mathematicians have relied on for years and the practical, adaptive decisions that engineers make every day.

In the end, the work provides a new tool for the digital age, one that respects the limits of our knowledge while maximizing the efficiency of our machines. It answers the question of when to stop not with a fixed number, but with a proof. By watching the journey unfold and certifying the destination as it is reached, the computer can work smarter, not just harder. The result is a system that is both rigorous and responsive, capable of delivering the same high-quality answers in a fraction of the time, ensuring that the vast resources of modern computing are used with precision and purpose.

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

1. Problem Formulation

The paper addresses a fundamental disconnect in the theoretical analysis of Stochastic Gradient Descent (SGD) for strongly convex optimization. Standard theoretical guarantees are ex ante: they specify a deterministic horizon $T$ before the algorithm runs and provide high-probability bounds on the optimization error at that specific time. However, in practice, stopping decisions are made adaptively by inspecting the evolving trajectory (e.g., monitoring validation loss or gradient norms).

This mismatch creates a certification problem:

Validity Failure: A high-probability bound proven for a fixed time $T$ does not generally hold at a data-dependent stopping time $\tau$ selected after observing the trajectory. The stopping time is coupled to random fluctuations, and selecting a time based on favorable fluctuations invalidates the original probability guarantee.
Conservatism: To preserve validity, one can pre-calculate a horizon $T_\epsilon$ by inverting a worst-case bound to find when the error is guaranteed to be below a target $\epsilon$ . However, because these bounds are derived from worst-case assumptions, $T_\epsilon$ is often excessively conservative, requiring many more iterations than necessary for the specific realized run.

The paper seeks to bridge this gap by constructing anytime-valid, trajectory-adaptive confidence sequences. These are observable upper bounds on the optimization error (squared distance to the optimizer or suboptimality) that hold simultaneously over all time steps, allowing the algorithm to stop as soon as a prescribed accuracy is certified without sacrificing statistical validity.

2. Methodology

The authors model the SGD trajectory as a sequential experiment where iterates and stochastic gradients provide evidence about the unknown optimization error. The core methodology involves constructing confidence sequences (observable, trajectory-dependent upper bounds) that remain valid simultaneously for all $t \ge t_0$ .

2.1. Core Probabilistic Tools

The construction relies on two main probabilistic techniques adapted for the recursive dynamics of SGD:

Time-Uniform Hoeffding Argument: A standard approach using exponential supermartingales and "stitching" (allocating error probabilities across dyadic scales of intrinsic time) to derive bounds that hold uniformly over time.
Time-Uniform Empirical Bernstein Inequality: A novel extension for adapted processes with time-varying conditional means and predictable ranges that may grow without bound. This is crucial because the range of the directional gradient noise terms in SGD scales with the distance to the optimizer, which evolves over time. The authors develop a "stitching" argument that simultaneously adapts to the accumulated quadratic variation (realized variance) and the running predictable range.

2.2. Performance Measures

The paper constructs confidence sequences for two specific performance measures:

Squared Distance to Optimizer ( $Z_t = \|x_t - x^*\|^2$ ): A measure of the last-iterate accuracy.
Weighted Average Suboptimality ( $\bar{F}_t$ ): A measure of the suboptimality of a linearly weighted average of iterates, which is known to achieve optimal convergence rates.

2.3. Recursive Construction for Observability

A key technical challenge is that the theoretical bounds depend on unknown quantities (e.g., the true distance $Z_t$ or the optimizer $x^*$ ). To make the bounds fully observable, the authors employ a recursive domination strategy:

They start with an observable upper bound $R_0$ on the initial distance.
They use the confidence sequence itself to bound the unknown distances in subsequent steps (e.g., replacing $Z_s$ with the previously computed upper envelope $\hat{U}_s$ ).
This "self-localizing" construction ensures that the intrinsic time (variance proxy) used in the concentration bounds shrinks as the algorithm converges, preserving the optimal $1/t$ decay rate.

2.4. Minibatch Extensions

The methodology is extended to minibatch SGD. For the empirical Bernstein bounds, the authors exploit the realized second-moment structure within each minibatch. Instead of relying on a uniform worst-case variance proxy, they use the largest eigenvalue of the realized second-moment matrix of the minibatch gradients, allowing the bounds to adapt to the geometry of the observed data.

3. Key Contributions

Trajectory-Adaptive Confidence Sequences: The paper constructs fully observable upper confidence sequences for the squared distance and weighted average suboptimality in strongly convex stochastic optimization. These sequences are valid simultaneously over time, enabling certified adaptive stopping.
Optimal Rates with Adaptivity: The constructed bounds attain the optimal $O(1/t)$ decay rate (up to iterated-logarithmic factors inherent to time-uniform validity) in the worst case. Crucially, they adapt to the realized stochastic gradients, often yielding bounds significantly tighter than worst-case predictions.
Refined Empirical Bernstein Bounds: The authors develop a new time-uniform empirical Bernstein inequality for processes with growing predictable ranges. This allows the confidence sequences to replace fixed worst-case variance proxies with realized squared gradient magnitudes, leading to sharper bounds that depend on the specific trajectory.
Minibatch Adaptation: The framework extends to minibatch SGD, where the empirical Bernstein bounds adapt to the realized second-moment structure of each minibatch, improving the convergence of the confidence sequence with increasing minibatch size.
Recursive Self-Localization: The paper introduces a recursive construction that uses the confidence sequence to bound the unknown distances required for the variance proxy, ensuring the bounds remain observable and retain optimal decay rates.

4. Results

4.1. Theoretical Guarantees

Hoeffding-based bounds: Under conditional sub-Gaussian noise, the bounds decay as $O(\frac{\log(1/\alpha) + \log \log t}{t})$ .
Empirical Bernstein bounds: Under bounded gradients, the bounds adapt to realized gradient magnitudes. The leading term scales with the realized second moments, and the additional range term decays at a faster rate ( $O(t^{-3/2})$ ).
Stopping Rules: The paper defines stopping times $\tau_\epsilon = \inf \{t : \hat{U}_t(\alpha) \le \epsilon\}$ . Proposition 1.6 proves that these stopping rules are valid: with probability at least $1-\alpha$ , if the algorithm stops, the returned iterate satisfies the accuracy requirement.

4.2. Numerical Experiments

Experiments were conducted on Support Vector Machine (SVM) problems using real-world (Covertype) and synthetic datasets.

Certification Speed: The trajectory-adaptive stopping rules certified target accuracies several orders of magnitude earlier than natural deterministic horizons derived from worst-case bounds.
- In one experiment, the empirical Bernstein bound certified a target accuracy 312 times earlier than the worst-case baseline.
- The Hoeffding-based adaptive bound certified 6.1 times earlier than the worst-case baseline.
Minibatch Effects: As minibatch size $b$ increased, the gap between the adaptive bounds and worst-case bounds widened. The empirical Bernstein bounds recovered a growing share of the gap between the worst-case bound and the ground truth as $b$ increased.
Robustness: The empirical Bernstein bounds were shown to be robust to conservative overestimation of problem constants (e.g., gradient bound $G$ or initial distance $R_0$ ). The effect of such misspecification was largely transient, vanishing as the trajectory-dependent terms accumulated.
Single-Pass Validity: The improvements persisted in a true single-pass regime (processing a finite dataset without replacement), confirming that the benefits are not artifacts of resampling from an empirical distribution.

5. Significance and Claims

The paper claims to resolve the "certification problem" in stochastic optimization by providing a theoretical framework where the evolving trajectory itself determines when sufficient progress has been made, with statistical validity.

Beyond Fixed Horizons: The work moves beyond the traditional "ex ante" analysis, offering a mechanism for online stopping that is both rigorous and adaptive.
Practical Efficiency: The primary significance is practical: the proposed stopping rules can require orders of magnitude fewer iterations than deterministic horizons derived from worst-case bounds, without sacrificing statistical guarantees.
Adaptivity to Realized Data: Unlike existing time-uniform guarantees that depend only on iteration count and global parameters, these confidence sequences adapt to the realized stochastic fluctuations and the geometry of the specific problem instance.
Modest Scope: The authors note that while the bounds are significantly tighter than worst-case baselines, a residual gap remains between the confidence sequences and the ground truth. They leave open the question of whether this gap can be reduced through sharper analysis of SGD dynamics. The paper focuses on strongly convex objectives and does not claim to solve the stopping problem for non-convex or general convex settings (though it references prior work in those areas).

In summary, the paper provides a rigorous, fully observable, and adaptive method for certifying the accuracy of SGD runs, enabling practitioners to stop algorithms as soon as a target accuracy is statistically guaranteed, rather than relying on overly conservative pre-computed horizons.