acceptodds
Under review as a conference paper at ICLR 2027

From Conservative Certificates to Adaptive Capital: Faster Anytime-Valid Stopping for SGD

Abstract

Stochastic gradient descent remains the default optimizer in large-scale learning, yet it is almost always terminated by heuristics such as a preset iteration budget or a plateau in the training loss. These rules provide no statistical certificate. Recent trajectory-aware stopping procedures restore validity, but they typically rely on closed-form envelopes of an exponential e-process family. In finite samples those envelopes are often loose, so certification arrives later than necessary and extra gradient steps are wasted. We introduce Stopping-Optimized e-Portfolios for SGD (SOEP-SGD). Instead of collapsing the e-process family into a conservative closed-form bound, SOEP-SGD keeps the family explicit and treats certified stopping as a capital-allocation problem: statistical mass is placed on the variance scales that actually govern when a valid certificate can be issued. We establish anytime-valid, optional-stopping-safe guarantees for convex SGD, in the form of weighted suboptimality bounds, and for smooth nonconvex SGD, in the form of weighted stationarity bounds. Simulations and CIFAR-10 experiments show substantially earlier certified stopping than existing closed-form certificates, without sacrificing validity.

Primary area:
optimization
Keywords:
stochastic gradient descent, early stopping, anytime-valid inference, e-values, e-process

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_hxXoOpenReview β†—
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The authors studied anytime-valid stopping for stochastic gradient descent. They proposed SOEP-πœ‹ procedure which approximately minimizes average boundary height over a prescribed set of variance scales. Their Theorems 1 and 2 give simultaneous bounds for weighted suboptimality and weighted squared-gradient stationarity, respectively. Numerical studies are included.

Critical strengths

An important problem with a simple, validity-preserving construction.

Critical weaknesses

My biggest concern is that inequalties (20) and (26) in Theorems 1 and 2 are too conservative. The authors have not convincingly studied the sharpness of the final stopping inequalities (20) and (26). For example, at Ξ±=0.05\alpha = 0.05, the reported simulations imply empirical rates of 0% for both final stopping-failure events. Please directly estimate the probabilities in (20) and (26), separately for each problem and tolerance, with Monte Carlo confidence intervals and clearly stated horizons. Distinguish these estimates from weighted-average failure rates and underlying boundary-crossing probabilities. Since the present experiments report zero stopping failures at nominal level 0.050.05, they demonstrate empirical safety but do not establish how close the final guarantees are to the nominal risk level.

I also have concerns on the novelty of the paper. As mentioned in the paper under review, Aolaritei and Jordan (2025) already derived Bk(v)B_k(v); see their Remark 4.5 about geometric grids and scale matching. I am not convinced that the results in this paper are substantially novel. Formular (A51) in Section A.6 in Howard et al. (2021) is pretty similar as the manuscript’s convex formula. Section 3.5 in the latter paper is also related.

In Appendix E, lines 1463–1465, claims that using Softplus and average pooling keeps the network globally C∞C^\infty with bounded Hessian. The bounded-Hessian assertion is false for an unrestricted multilayer parameterization.

The sin-mix example in (73) violates the gradient-bound assumption.

Questions for authors

Sharpness of (20) and (26). At 𝛼 = 0.05, please directly estimate, separately by problem and tolerance, the finite-horizon probabilities. Please provide Monte Carlo confidence intervals, independent replication counts, and the monitoring horizon. Distinguish these from weighted-average failures and from the boundary-crossing experiment, whose generating process and configuration also need specification. Use all trajectories as the denominator for these unconditional probabilities; a failure rate conditional on stopping is a different quantity. Repeated tolerances on the same path should not be treated as independent replications. The probabilities need not equal 0.05 in every example, but their distance from the nominal level is essential for assessing conservatism.

4 comments
AuthorsOpenReview β†—

Response to Reviewer hxXo Part 1/2

Thank you for recognizing the problem and construction, and for identifying the calibration and assumption gaps.

Q1 & W1: How conservative are the final stopping guarantees?

  • Final stopping risks are far below 5% in the tested settings. Thank you for specifying events and sampling units. We measured (20)/(26) directly: stopping by TT with an inaccurate returned average or no qualifying historical iterate. All NN paths form the denominator; non-stopping paths contribute zero. Methods, targets and fits share these paths.
  • Original valid tasks: At Ξ±=.05\alpha=.05, T=300,000T=300{,}000, all 15 configurations have 0/1,000 final failures per method/target, with pointwise two-sided 95% Clopper-Pearson CI [0, 0.3682%]. Cellwise tables give every problem/tolerance, stopping counts and weighted-target failures.
  • Independent stress test: A 1-D nonconvex task uses L=G=1L=G=1, independent N(0,.252)N(0,.25^2) noise, N=100,000N=100{,}000, T=128T=128, Ο΅=.75\epsilon=.75, f(0)=0f(0)=0 and x1=1.02x_1=1.02. Set fβ€²(x)=clip⁑(x,βˆ’1,1)f'(x)=\operatorname{clip}(x,-1,1), except 1.9βˆ’x1.9-x on [.95,.96] and xβˆ’.02x-.02 on [.96,1.02]. Steps are .00375 for 1-32, 6 at step 33, then .1. Exploration selected this large-step configuration; evaluation used fresh paths.

Table 1. Distinct events, each counted over all 100,000 paths.

RuleStoppedFinal failures [95% CI, %]Weighted failuresBoundary crossings
Single-start SOEP + exact inversion12,63810 [.00480, .01839]104117
Preselected single-Ξ»\lambda14,284114 [.09404, .13693]324391
  • Boundary-crossing event: βˆƒt≀T:βˆ’βˆ‘s≀tΞ·sfβ€²(xs)ΞΎsβ‰₯B(Οƒ2G2Vt)\exists t\le T:-\sum_{s\le t}\eta_s f'(x_s)\xi_s\ge B(\sigma^2G^2V_t). Table 1 reports this separately from final and weighted-target failures.
  • The weighted-average-to-minimum step dominates measured slack. On 128 replays of the original 100-D cosine task at its tightest target, the weighted-average squared-gradient to historical-minimum gap averages 85.94% of Ο΅\epsilon; the boundary-minus-realized-martingale gap averages 3.08%. Substantial slack therefore remains after tightening the probability boundary alone.
  • The bounded CIFAR head shows substantial stopping delay. Across three representations with 100 paths each, direct full-gradient verification returns at 2,048/4,096 steps for relative targets .1/.03. Original SOEP averages 103,168 steps at .1 and has zero stops by 10610^6 at .03. Each prefix-method/target/representation cell has 0/100 final failures, CI [0, 3.6217%]. We report stopping rates and extra gradient-query costs alongside risk.
AuthorsOpenReview β†—

Response to Reviewer hxXo Part 2/2

W2: Relation to prior work and novelty.

  • We will narrow the contribution to weight allocation for a specified design distribution and its empirical tradeoffs. Thank you for identifying the precedents. Aolaritei and Jordan [1] provide trajectory-based SGD certificates and scale matching; Howard et al. [2] develop mixture confidence sequences. Matched experiments favor the tuned baseline on mean capped stopping time.

W3: The global bounded-Hessian assertion.

  • We will withdraw the assertion and label the original CNN results as proxy evaluations. Thank you for identifying the error. Smooth activations and pooling alone leave parameter-space curvature potentially unbounded.

W4: The sin-mix gradient bound.

  • The original sin-mix gradient is unbounded; we will remove it from theorem-valid results. Thank you for flagging this violation. Separately proved predictable-gradient-bound/guarded variants will be identified as new modifications.

References

[1] L. Aolaritei and M. I. Jordan (2025). Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences. arXiv:2512.13123.

[2] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055-1080.

Reviewer_hxXoOpenReview β†—

response to the rebutal

Thanks the authors for answering my main empirical question about (20) and (26) with additional experiments.

I agree with the authors’ narrower novelty claim regarding weight allocation for a specified distribution of variance scales. Given the prior work on scale matching and mixture boundaries, the matched comparison carries significant weight in my assessment.

After I read other reviewers' comments, I keep my rating of 2 (weak rejection): the main reason is that the evidence that the proposed allocation improves stopping performance over a well-tuned baseline seems limited.

Dear Reviewer hxXo,

Thank you for your follow-up. To clarify the matched comparisons discussed with Reviewers hsQz and fQBD, the tuned baselines achieve 6.19% to 11.37% lower mean stopping time only by fitting hyperparameters on 64 target-task SGD pilot trajectories (264.27 s setup), which defeats single-run early stopping. Requiring zero SGD pilots (2.67 s setup), exact SOEP-Ο€\pi outperforms both the closed-form baseline (ratio 1.6963) and the untuned numerical-inversion AJ mixture (ratio 1.0153, CI [1.0105, 1.0247]), while matching the pilot-tuned geometric mean (0.9897).

Since the calibration and assumption issues are resolved, could you also consider updating your score?

Thank you!

Reviewer_fQBDOpenReview β†—
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper solves the problem of stopping time certification of SGD. The authors propose SOEP-SGD that is a tighter certificate yielding early stopping time. The main technical contribution is to use a set of exponential supermartingales to control the noise bound. The paper also makes sythethic and deep learning experiments can improve the early stopping bounds when choosing right parameters.

Critical strengths
  1. On concrete settings such as the synthetic convex case where all assumptions are justified, the tighter analysis gives strong improvement in early stop time estimation.
Critical weaknesses
  1. The proved theorems use strong assumptions. For theorem 1, bounded trajectories and sub-Gaussian gradient noise are assumed. For theorem 2, bounded gradients and sub-Gaussian gradient noise are assumed.
  2. The improved bounds rely on some unknown constants such as Rx,Οƒ,LR_x, \sigma, L, and GG, and it is computationally unclear under what regimes of these parameters the new error bounds are tighter.
  3. The above two limitations make the theorems only apply to limited practical setting.
  4. The experiments used some rough estimate such as L=1L=1 to justify the tighter early stopping time.
Questions for authors
  1. What improvement the baseline bounds can obtain if one optimize it with numerical inversions, i.e., computing the boundary with some optimized parameter selections? In this case, are the gains obtained in this work still significant?
6 comments
AuthorsOpenReview β†—

Response to Reviewer fQBD Part 1/2

Thank you for recognizing the gains in assumption-valid convex settings and for examining the constants, scope and baseline tuning.

Q1: How much do numerical inversion and parameter tuning improve the baseline?

  • After numerical inversion and scale tuning, the AJ-type baseline has 6.19% lower mean capped stopping time than original SOEP. Thank you for asking how much gain survives a stronger baseline. Numerical inversion of the fixed Aolaritei-Jordan (AJ) mixture [1] reduces mean capped stopping time by 40.14% relative to the original closed-form baseline. Table 1 shows the progression and the remaining difference from original single-start SOEP with exact inversion.

Table 1. Mean min⁑(Ο„,T)\min(\tau,T), baseline/SOEP-exact; values below one favor the baseline.

BaselineRatio95% paired bootstrap CI
Original closed form1.6963[1.6477, 1.7912]
Fixed AJ-type mixture, numerical inversion1.0153[1.0105, 1.0247]
AJ-type mixture, numerical inversion + scale tuning0.9381[0.9097, 0.9924]
Same-grid mixture, numerical inversion + center/width tuning0.8863[0.8350, 0.9857]
  • Numerical baseline: The AJ-type approximation retains 81 geometric-grid atoms and their original prior weights, with residual mass at Ξ»=0\lambda=0. Scale tuning selects a common multiplier for these atoms using independent pilots. The center/width-tuned mixture uses SOEP's 81-point grid.
  • Protocol: Three independent CIFAR-10 representations each have 100 fresh SGD paths, T=106T=10^6, and two independent 32-path pilot fits. Methods share evaluation paths. Targets Ο΅=Ξ΄q0\epsilon=\delta q_0, δ∈{.1,.03}\delta\in\{.1,.03\}, are equally weighted; q0q_0 is the initial full-gradient squared norm. There are 300 independent evaluation paths. Intervals resample representations and paired paths; three representations limit inference.
  • Tight-target stopping: At Ξ΄=.03\delta=.03, SOEP stops on 0/100 paths in each representation; the same-grid tuned mixture stops on 100/100, 100/100 and 0/100.

Table 2. Mean online seconds over 30 independent timing paths (270 method/target runs).

MethodΞ΄=.1\delta=.1Ξ΄=.03\delta=.03
SOEP exact18.50177.90 (all censored)
Same-grid tuned mixture exact21.07152.12 (partly censored)
Direct full-gradient return verification0.390.74
  • Setup cost: SOEP averages 2.67 s using a deterministic variance design; the same-grid tuned mixture averages 264.27 s including SGD pilots and candidate search. Online costs include monitoring and full-gradient checks when performed. Shared preparation, initial-gradient evaluation and process startup are excluded. Direct verification is a separate control using extra full-training-gradient queries.
AuthorsOpenReview β†—

Response to Reviewer fQBD Part 2/2

W1 & W3: Strong assumptions and practical scope.

  • Analytic constants are available for the projected convex tasks and the new bounded CIFAR-10 head. Thank you for asking where the assumptions hold. Projection supplies a known trajectory radius. The head uses frozen normalized features and logits 3tanh⁑(Wz/3)3\tanh(Wz/3), with G=2G=\sqrt2, L=1/2+4/(93)L=1/2+4/(9\sqrt3) and Οƒ=.125\sigma=.125 for independent with-replacement batches of 128. Its guarantee concerns empirical-risk stationarity. Establishing usable constants for general deep networks remains open.

W2: Unknown constants and sensitivity.

  • Conservative constants can eliminate practical stopping gains. Thank you for highlighting this dependence. On 256 fixed projected-quadratic paths, multistart SOEP's mean stopping time at Ο΅=.045\epsilon=.045 rises from 10,158 to 36,331 when the valid noise bound doubles, and to 41,172 when RxR_x doubles. At Ο΅=.015\epsilon=.015, both settings have 0/256 stops by 10610^6 steps.

W4: The use of L=1L=1 in the original CNN.

  • We will label the original CNN stopping times as proxies and withdraw the global bounded-Hessian assertion. Thank you for identifying the unjustified constant. The revised certification claims will apply to models with justified bounds.

Dear Reviewer fQBD,

As the discussion deadline (Nov 18 AoE) approaches, we wanted to briefly check in to see if our responses (Parts 1–2) have addressed your questions and weaknesses.

If our revisions resolve your concerns, we would really appreciate it if you could consider updating your score. Please let us know if anything is still unclear before the discussion closes. Thank you again for your time and helpful feedback!

Best regards,

The Authors

Reviewer_hsQzOpenReview β†—
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper replaces the closed-form e-process boundary for anytime-valid SGD stopping with the exponential e-process family, and treats certified stopping as a capital-allocation problem. It certifies convex weighted suboptimality and smooth nonconvex weighted stationarity through a minimum over weighted boundaries, and sets the weights from a design distribution via SOEP-Ο€\pi. The validity argument looks correct. I am not convinced that the allocation adds much over variance-scale tuning, and I do not think the CIFAR-10 runs support the certified-stopping claim.

Critical strengths
  1. The optimization procedure is unchanged, so stopping rules are compared on the same trajectories. The simulations also allow direct evaluation of the targets with shared trajectories.
  2. The probability arguments hold. Theorem 1 follows from the conditional moment bound and a fixed mixture with Ville's inequality, while Theorem 2 follows from the predictable variance process and a monotone boundary.
Critical weaknesses
  1. The deep-learning procedures do not satisfy Theorem 2's assumptions. To be specific, Theorem 2 needs a valid LL, a conditional sub-Gaussian bound and an almost-sure gradient bound. Appendix B.2 calls L=1L = 1 a placeholder and Οƒ=0.5\sigma = 0.5 unverified, and the only check it reports is that minibatch norms stayed below GG. That is a finite sample, so it establishes none of the three bounds. Also, Appendix E says that Softplus with average pooling gives a bounded Hessian, but no argument is given.

  2. The benchmark does not distinguish the method from scale tuning. The existing literature (Aolaritei and Jordan) already has both decompositions and anytime-valid stopping, and mixtures and scale tuning are standard (Howard et al.). Sections 5.1-5.2 use the default portfolio, so their speedups do not test Algorithm 1.

Questions for authors
  1. Provided the baselines with the same Ξ»\lambda grid and scale tuning, how much improvement remains?

  2. Can the CNN results be presented as proxy evaluations, or can the bounds be established?

4 comments
AuthorsOpenReview β†—

Response to Reviewer hsQz Part 1/2

Thank you for your careful assessment and for recognizing the shared-trajectory comparisons and validity arguments.

Q1 & W2: What remains after matching the grid and tuning the baselines?

  • Across the two targets, the tuned baseline has 11.37% (exact) and 11.51% (min) lower mean capped stopping time. Thank you for asking us to isolate weight optimization. We compared original single-start SOEP with a center/width-tuned mixture on the same 81-point grid and matched envelopes.

Table 1. Baseline/SOEP stopping-time ratios; values below one favor the baseline.

StatisticRatio95% paired bootstrap CI
Mean min⁑(Ο„,T)\min(\tau,T), exact/exact0.8863[0.8350, 0.9857]
Mean min⁑(Ο„,T)\min(\tau,T), min/min0.8849[0.8329, 0.9857]
GM$(1+\min(\tau,T))$, exact/exact0.9897[0.9291, 1.0225]
  • Protocol: Three independently trained CIFAR-10 representations each have 100 fresh SGD paths, T=106T=10^6, and two independent 32-path pilot fits. Methods share evaluation paths. Targets ϡ∈{0.1q0,0.03q0}\epsilon\in\{0.1q_0,0.03q_0\} are equally weighted, with q0=βˆ₯βˆ‡f(W0)βˆ₯2q_0=\|\nabla f(W_0)\|^2. The independent evaluation count is 300 paths. Intervals resample representations and paired paths; three representations limit cross-representation inference.
  • Target dependence: Original SOEP has zero stops at 0.03q00.03q_0 by TT. The geometric-mean ratio is near one, with its CI spanning one.
  • Setup and attribution: The baseline optimizes pilot stopping times; SOEP optimizes boundary height over a deterministic variance design, requiring no SGD pilots. We will report these information and setup-cost differences. Sections 5.1-5.2 evaluated the default portfolio; Algorithm 1 requires separate evaluation. We will correct the attribution and distinguish the original update, multistart variants and exact inversion.
  • Contribution: Weight allocation for a specified design distribution. The foundations are the SGD certificates of Aolaritei and Jordan [1] and the mixture methodology of Howard et al. [2]; we will revise the novelty claim accordingly.
AuthorsOpenReview β†—

Response to Reviewer hsQz Part 2/2

Q2 & W1: Can the CNN results be treated as proxies, or can the assumptions be established?

  • The original SmoothCNN results will be labeled proxy stopping evaluations. Thank you for identifying the assumption gap. We will withdraw the globally bounded-Hessian assertion. Global constants require justification beyond observed minibatch norms.

  • The new bounded head has analytic constants. It uses frozen features with βˆ₯zβˆ₯≀1\|z\|\le1 and logits 3tanh⁑(Wz/3)3\tanh(Wz/3):

    L=1/2+4/(93),G=2,Οƒ=0.125.L=1/2+4/(9\sqrt3),\quad G=\sqrt2,\quad \sigma=0.125.

    With independent with-replacement batches of 128, the guarantee concerns this head's empirical-risk stationarity.

  • Prediction accuracy improves while the relative stationarity targets remain unmet at measured checkpoints. Ten new original-CNN seeds trained for 10,000 updates improve mean test accuracy from 9.61% to 66.56%. All 12 full-gradient checkpoints per seed exceed 0.1q00.1q_0 and 0.03q00.03q_0; Ο΅=5\epsilon=5 already holds at every initialization.

References

[1] L. Aolaritei and M. I. Jordan (2025). Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences. arXiv:2512.13123.

[2] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055-1080.

Reviewer_hsQzOpenReview β†—

Response to the rebutal

I appreciate the authors' honest response and their efforts in addressing these issues. Based on the clarified contribution and the trade-offs of the pilot-free design, I will update my score.

Thanks for your feedback! We are pleased to hear that our responses have addressed most of your concerns. We will incorporate your valuable suggestions to improve the quality of our paper.We sincerely appreciate your support !

Comments on the paper

1 comment

Dear AC, SAC, and PC,

We would like to express our gratitude to all the reviewers for their valuable feedback. We have carefully considered all suggestions and updated our submission accordingly.

However, we have not yet received responses from Reviewer hsQz, Reviewer fQBD, and Reviewer hxXo. With only two days remaining for discussion, we kindly request your assistance in reaching out to these reviewers. It would be greatly appreciated if you could encourage them to review our rebuttal, as we are eager to know if we have adequately addressed their questions and concerns.

Thank you for your hard work and support.

Best regards,

The authors of Paper 10128

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.