A stopping rule that follows the run
A preprint proposes a data-based stopping signal for stochastic gradient descent (SGD), using the path of gradients generated during the run. It asks whether SGD can certify, from that realized trajectory, when it should stop. The proposed confidence sequences are designed to remain valid during continuous monitoring, including at a stopping time chosen after looking at the observed path.
Here, a confidence sequence is an upper bound designed to keep its stated validity as new iterations arrive, rather than only at one fixed, preselected horizon. The construction applies to strongly convex stochastic optimization and targets two quantities: the squared distance of the latest iterate from the optimizer and the suboptimality of a weighted average of iterates.
The method is intended to let the stopping decision follow the run instead of being tied to a predetermined endpoint. Once an observable certificate crosses a target accuracy, it can support stopping while retaining its formal validity. In worst-case theory, both certificates recover the canonical 1/t decay, apart from iterated-logarithmic factors.
When the bound uses the gradients
The main refinement is empirical Bernstein, a bound that replaces a fixed worst-case variance proxy with the squared magnitudes of the stochastic gradients actually observed. The paper reports that this trajectory-adaptive construction preserves the worst-case rate and adds a correction that decays as t^-3/2, up to logarithmic factors. The resulting bound reflects the variability recorded along a particular run.
The authors also extend the method to minibatches. Its leading term has the usual minibatch improvement, while the lower-order correction improves faster. The boundary includes realized within-minibatch second-moment information, making its value dependent on the observed variability.
The reported experiments
The clearest stopping-time comparison used covertype.binary, batches of 256 gradients and a target accuracy of 10^-3. The Hoeffding certificate crossed the target 6.1 times earlier than the worst-case baseline. The empirical-Bernstein minibatch certificate crossed it 312 times earlier. The comparison came from one trajectory and one target setting, so these are relative results rather than an estimate of average performance.
In a comparison across minibatch sizes, empirical Bernstein was about one order tighter than Hoeffding at b = 1. The Rakhlin et al. bound was about one order above the worst-case baseline at b = 1, and its gap reached three orders at b = 1024. The reported relative advantage of the adaptive bounds widened as minibatches grew.
A separate experiment used three synthetic make_classification datasets with increasing class separability and tracked ground truth alongside the empirical-Bernstein certificate. For suboptimality, the reported bound was 1.9 x 10^-6 for dataset C and 3.2 x 10^-5 for dataset A, making the certificate for C roughly 17 times tighter. The comparison was exploratory and based on single trajectories.
The pattern also appeared in a true single-pass run, in which observations were not reused. That dataset contained 581,012 observations; with b = 256, the run ended after 2,269 iterations. Hoeffding was 6.4 times tighter than the worst-case suboptimality bound, while empirical Bernstein was 2.7 x 10^2 times tighter. The run had no population ground truth.
Where the guarantees are fragile
The guarantees are conditional on the assumptions behind the construction. The empirical-Bernstein refinement requires a valid bounded-gradient condition, and the minibatch result requires conditional independence within each minibatch. The experiments also show why the problem constants matter: misspecified gradient bounds inflated the reported worst-case curves, and starting-distance estimates affected the early certificates.
When the gradient-bound specification was misspecified, the worst-case curves were approximately 100-fold above the well-specified curves, with a similarly strong effect for Hoeffding. For empirical Bernstein, overestimating R0 by factors of 10, 100 and 1,000 had a pronounced early effect that diminished rapidly. Even with a 1,000-fold overestimate, the relative difference was 4% after 100 iterations in the reported experiment.
The evidence is narrower than the size of the headline ratios might suggest. The numerical results are selected trajectory-level comparisons, not repeated-run coverage studies, and the single-pass result covers only one dataset. No empirical coverage estimate was reported. Where ground truth was available, the authors still found a considerable gap between the confidence sequences and the true quantity, leaving sharper analysis of SGD as an open question.
The work is an arXiv preprint, version 1, dated 26 August 2026.
Paper data and sources
Original title: Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules
Authors: Liviu Aolaritei, Lucas Lévy, Francis Bach, Michael I. Jordan
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text