PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Soham Bonnerjee, Aaditya Ramdas

arXiv:2610.23570v1stat.MLcs.LGmath.OCstat.ME

TL;DR

Fixed-iteration convergence guarantees do not justify stopping at a data-dependent time, while existing anytime-valid envelopes can be conservative or case-specific. The paper presents a modular recipe that combines algorithmic recursions with time-uniform bounds for weighted noise. Its constructions recover or sharpen existing guarantees in some settings, provide first data-dependent guarantees in others, and betting-based envelopes often outperform stitching- and mixing-based ones.

  • Problem

    Oracle performance measures do not justify data-dependent stopping, and existing anytime-valid analyses can be limited to specific assumptions and settings.

    Source: §1 · p. 1

  • Method

    The paper combines algorithm-specific performance recursions with time-uniform bounds for weighted noise under a strongly adapted sub-ψ condition.

    Source: §2 · p. 7, §2.1 · p. 7, §3 · p. 13

  • Results

    The constructions recover and often sharpen existing time-uniform guarantees in some settings, provide first data-dependent guarantees in several others, and betting-based envelopes often outperform stitching and mixing.

    Source: §6 · p. 30

  • Takeaways & Limitations

    The resulting envelopes are computed from observed trajectories and apply across multiple iterative stochastic algorithm settings.

    Source: §6 · pp. 29–30

    The framework allows predictable SGD step sizes, but not step sizes adapted to the current stochastic gradient; extending it to Markovian noise remains open.

    Source: §6 · p. 30

Abstract

from arXiv · show

Most convergence guarantees for iterative stochastic algorithms are stated at a fixed iteration count and do not justify stopping at a data-dependent time. Recent work has constructed anytime-valid envelopes that do, but deterministic envelopes are typically too conservative for practical stopping, and existing data-adaptive ones are derived case-by-case, each coupling a specific algorithm to a specific noise model and boundary construction. This paper provides a general recipe for constructing such anytime-valid data-adaptive boundaries for a large class of iterative algorithms. Performance measures of many of these algorithms satisfy a one-step recursion that reduces the entire error analysis to a single general requirement: time-uniform concentration for predictably weighted sums of noise. We formalize this through a strongly adapted sub-$\psi$ condition, and derive off-the-shelf boundary constructions via continuous and discrete mixtures, stitching, and product betting martingales. We show how these boundaries can be directly coupled with a separate algorithmic analysis that derives the one-step recursion to provide a class of readymade anytime-valid envelopes across diverse settings including stochastic gradient descent (SGD), temporal difference learning, and Bures-Wasserstein SGD. In particular, for SGD, our framework either recovers or significantly sharpens every existing envelope we are aware of. Our constructions come with explicit implementation details and are substantiated by numerical experiments.

1 Introduction

The introduction proposes a modular recipe for anytime-valid envelopes that separates deriving an algorithm-specific recursion from constructing time-uniform bounds on weighted noise. It aims to replace conservative deterministic envelopes and case-by-case analyses with data-adaptive boundaries that support broader algorithm, noise, and step-size settings.

1 Introduction

  • Oracle performance measures do not support data-dependent stopping or valid confidence sets at ad-hoc stopping times, motivating nonasymptotic anytime-valid upper bounds.Anytime-valid envelopes facilitate arbitrary post-hoc data-dependent stopping times.Source: §1 · pp. 1–2
  • The modular recipe separates deriving a performance recursion from constructing time-uniform bounds, so algorithm-specific analysis is needed only to obtain the recursion.The resulting framework recovers or sharpens existing SGD bounds and supplies new anytime-valid bounds for settings previously unexplored in this respect.Source: §1 · pp. 2–3
  • Observed-data envelopes are much sharper than deterministic anytime-valid envelopes, and the framework imposes no particular noise-tail or optimization-growth assumptions structurally.Additional assumptions can be used to derive the recursion needed for a particular algorithm and performance measure.Source: §1 · p. 3

1.1 Prior Work

  • Prior work is sparse, while deterministic envelopes can be too large for practical stopping and may require particular deterministic step-size schedules.Related data-dependent analyses are restricted to specified noise, optimization assumptions, and performance measures.Source: §1.1 · pp. 5–6
  • The framework accommodates general data-dependent step sizes and noisy observations, using adapted sub-ψ analysis and product betting martingales across varied settings.The paper reports sharper SGD envelopes and first data-dependent anytime-valid bounds in several other settings.Source: §1.1 · p. 6

2 Probabilistic tools: sub-ψ processes and boundaries

The section turns a one-step recursion for an algorithm’s performance measure into observable, anytime-valid envelopes by controlling predictably weighted noise sums. It formalizes a stronger sub-ψ condition and develops mixing, stitching, and betting boundaries for that purpose.

2 Probabilistic tools: sub-ψ processes and boundaries

  • A one-step recursion lets envelopes be built inductively: a valid envelope for Z_{t-1} is used to construct one for Z_t, reducing the analysis to uniform control of weighted noise sums.The resulting observable recursive envelopes control Z_t at all times with the stated error probability.Source: §2 · pp. 6–7

2.1 Assumptions on ξt

  • The strongly adapted sub-ψ condition strengthens existing sub-ψ assumptions to support uniform boundaries for arbitrary predictable weights and varied tail behaviors.The results do not require ξ_t to have finite moments.Source: §2 · p. 7, §2.1 · pp. 7–8

2.2 Boundaries by mixing, stitching and betting

  • The paper develops mixing, stitching, and betting as three procedures for constructing time-uniform envelopes; betting can give sharper bounds when the noise variables are bounded.Mixing combines supermartingales over λ, stitching combines linear boundaries across a geometric λ-grid, and betting uses product-betting martingales.Source: §2.2 · pp. 8–9

2.2.1 Boundaries for Ytpvq

  • Observable boundaries for weighted noise can be combined with the recursive envelope lemma to produce anytime-valid envelopes for Z_t.In the applications, observable bounds on the weights can be constructed recursively from previous envelopes; the authors report that obtaining observable J_t and H_t is straightforward in most applications.Source: §2.2.1 · pp. 9, 10, 12

3 Anytime-valid boundaries in stochastic gradient descent

This section applies the paper’s modular recipe to SGD, deriving anytime-valid envelopes from one-step recursions and time-uniform boundaries under restricted secant inequality and Lipschitz-gradient assumptions. For Polyak–Ruppert averaged SGD, it transfers cumulative-noise bounds to the averaged iterate and compares the asymptotic rates of several boundary constructions.

3.1.1 Optimization module for RSI

  • For RSI, the optimization analysis yields a one-step recursion for squared distance to the minimizer, enabling application of the general boundaries.RSI is weaker than strong convexity, and bounded stochastic gradients give an almost-sure bound on the distance-based performance measure.Source: §3.1 · p. 13, §3.1.1 · p. 14

3.1.2 Betting construction under RSI

  • The RSI betting construction uses bounded gradients to sharpen supermartingale-based boundaries with product betting and provides an observable anytime-valid envelope.The section also presents a sub-gamma stitching alternative with a closed-form expression, while noting that the exponential discrete-mixture boundary outperforms stitching in simulations.Source: §3.1.2 · p. 14
  • Under restricted secant inequality (RSI) and bounded stochastic gradients, the framework gives a class of anytime-valid envelopes uniformly sharper than Aolaritei et al. [2026].The paper also compares betting, exponential discrete-mixture, and stitching constructions; in simulations, the exponential discrete-mixture boundary outperforms the stitching bound.Source: §3.1.2 · pp. 14–15

3.2 Case II: Lipschitz gradient

  • With only an L-Lipschitz gradient, the section treats potentially nonconvex objectives and uses a stationarity-oriented performance measure rather than distance to a minimizer.The measure combines objective suboptimality with a stationarity component; the paper develops self-normalized and betting-based time-uniform envelopes for it.Source: §3.2 · p. 15

3.2.1 Optimization module for LS

  • The descent lemma yields a one-step recursion for the Lipschitz-gradient performance measure, so the general boundaries provide anytime-valid envelopes for it and its stationarity component.Some stitching constructions recover Aolaritei and Jordan [2025, Corollary 2.6], while an alternative can be sharper near local optima.Source: §3.2.1 · p. 16

3.2.2 Self-normalized and betting envelopes under bounded gradients

  • Under bounded gradients and conditionally sub-Gaussian noise, the section constructs self-normalized envelopes and sharpens them with a quadratic product-betting supermartingale.The quadratic betting envelope requires no restriction on λ or boundedness of the stochastic gradients gt.Source: §3.2.2 · pp. 16–17

3.2.3 Combining the self-normalized and the betting envelope

  • A hybrid envelope combines the sub-Gaussian discrete-mixture and betting constructions before inversion, yielding a boundary uniformly sharper than Aolaritei and Jordan [2025]’s sub-Gaussian stitching boundary.This combination avoids simply taking the maximum of the two envelopes or applying a union bound.Source: §3.2.3 · p. 17
  • The combined results recover, improve, and offer alternatives to existing boundaries, with further constructions in the appendices for assumption and performance-measure combinations.The paper notes that most of those additional constructions have no prior precedents in their corresponding settings.Source: §3.2.3 · p. 18

3.3 Case III: Polyak–Ruppert averaging (strong convexity, Lipschitz gradient)

  • PR averaging addresses last-iterate sensitivity to the step-size schedule and motivates studying envelope optimality under strong convexity and Lipschitz gradient assumptions.For ηt proportional to t^-β with β in (1/2, 1), the averaged iterate has distance to the minimizer of order t^-1/2, compared with t^-β/2 for the last iterate; prior time-uniform guarantees for the averaged iterate are asymptotic.Source: §3.3 · p. 18

3.3.1 Optimization module for PR-averaged SGD under SC and LS

  • The optimization module preserves noise cancellation by isolating cumulative noise and transferring its anytime-valid envelope to the averaged iterate through an observable linearization.A naive bound that averages individual error bounds forfeits that cancellation; the analyzed performance measure is the squared distance of the averaged iterate to the minimizer.Source: §3.3.1 · p. 18

3.3.2 Boundaries for PR-averaged iterates

  • Under Theorem 3.1’s conditions, four boundary choices yield an anytime-valid envelope for the squared error of the PR-averaged iterate, holding for all t ≥ 1.The choices are Gaussian mixture, sub-Gaussian stitching, sub-Gamma stitching, and betting; the theorem also assumes a Lipschitz Hessian.Source: §3.3.2 · p. 19

3.3.3 Optimality properties of different boundaries

  • Stitching and betting envelopes achieve iterated-logarithmic rates, whereas Gaussian-mixture envelopes have order log t/t under power-law step sizes.The paper attributes the mixture boundary’s slower rate to a fixed Gaussian mixing distribution assigning exponentially decreasing mass to useful scales; stitching instead allocates error budget polynomially across scales. Modulo logarithmic penalties for validity at all times, the envelopes attain known fixed-time optimal rates.Source: §3.3.3 · p. 20

4 Applications beyond SGD

The section applies data-dependent anytime-valid boundaries to Oja’s algorithm, temporal difference learning, and Bures-Wasserstein SGD, using algorithm-specific one-step recursions under stated conditions. For BW-SGD, it also supports tolerance-based stopping for posterior summaries and decision-theoretic stopping rules in stochastic VI, with computational guarantees that require control of an additional term.

4 Applications beyond SGD

  • The framework provides the first data-dependent, anytime-valid boundaries for Oja’s algorithm, TD learning, and Bures-Wasserstein SGD.The applications derive algorithm-specific one-step recursions and then apply the paper’s general boundary constructions.Source: §4 · p. 20

4.1 Oja’s algorithm

  • Oja’s envelopes allow predictable step sizes and, with a known conditional fourth-moment bound, cover Gaussian and other unbounded observations without independence.With bounded observations, the framework also yields normal-mixture, stitching, and betting envelopes.Source: §4.1 · p. 21

4.1.1 Set-up and optimization module for Oja’s algorithm

  • Oja’s sharper recursion replaces a global bounded-data second-order control with the observable, data-dependent term 3||Σ̂_t u_{t-1}||².This sharper recursion supports the boundary construction; the paper also describes feedback that tightens the contraction as the run proceeds.Source: §4.1.1 · p. 22, §4.1.2 · p. 22

4.2 Temporal difference learning

  • TD learning yields data-dependent envelopes for any predictable step sizes, with no burn-in, that also bound value-function error apart from linear-approximation bias.The TD recursion retains an observable second-order term alongside a term that vanishes under conditional expectation.Source: §4.2 · p. 23, §4.2.1 · p. 24

4.2.2 Boundaries for TD-learning

  • TD learning’s boundary follows from a strongly adapted sub-ψ noise proxy, or, for projected TD learning, a product-betting boundary.The resulting value-function guarantee holds simultaneously over time.Source: §4.2.2 · p. 24

4.3.1 Set-up and optimization module for Bures - Wasserstein SGD

  • For Bures-Wasserstein SGD, the derived recursion applies to predictable step sizes up to the stability threshold and has an observable second-order term.The term controlling the recursion is bounded using the preceding envelope without knowing the optimal mean, covariance, or transport map.Source: §4.3.1 · p. 25

4.3.2 Boundaries for BW-SGD

  • Bures-Wasserstein SGD’s first anytime-valid convergence-error bound holds simultaneously over iterations with probability at least 1 − α.The theorem permits Gaussian-mixture or sub-Gaussian stitching boundaries; the Wasserstein error bound also transfers to posterior summaries and decisions.Source: §4.3.2 · p. 26
  • The additional term can be controlled under extra assumptions using Katsevich and Rigollet [2024, Theorem 2.1].The passage notes that the guarantees concern computation and that this term requires control.Source: §4.3.2 · p. 26
  • Alternatively, the additional term may be estimated post hoc using the bounds of Huggins et al. [2020].This is presented as an alternative to controlling it under additional assumptions.Source: §4.3.2 · p. 26
  • Proposition 7 permits stopping BW-SGD when the stated bound falls below a user-specified tolerance for posterior summaries of interest, yielding decision-theoretic stopping rules in stochastic VI.The paper describes these as first-of-its-kind results in stochastic VI.Source: §4.3.2 · p. 26

5 Numerical Experiments

The experiments compare anytime-valid envelopes on ridge regression and FrozenLake TD(0). In both settings, the betting envelope is especially sharp relative to alternatives, and the TD learning envelopes provide data-dependent stopping guarantees.

5.1 Warm-up: a ridge regression example

  • The ridge-regression comparison uses projected SGD over 10^7 iterations and evaluates envelopes at level α = 0.05.The envelopes are transferred from distance to the ridge solution to distance from the regression coefficient for comparison with prior work.Source: §5.1 · p. 27
  • In ridge regression, the betting envelope is about 20 times smaller than the empirical-Bernstein envelope, and all three proposed envelopes are sharper throughout.The deterministic envelope remains at the global bound until t = 807,518, while the proposed envelopes fall below it by t = 193.Source: §5.1 · p. 28
  • Table 3 reports the ridge-regression envelopes before bias correction because the common correction masks differences among data-dependent envelopes.The betting envelope also requires bounded gradients, which hold in this example.Source: §5.1 · p. 28, Table 3 · p. 28

5.2 Temporal difference learning on FrozenLake

  • The FrozenLake example evaluates a uniform policy with tabular features on 11 nonterminal states, using TD(0) for 10^7 iterations at level α = 0.05.Transitions are sampled independently, and the initial parameter vector is zero.Source: §5.2 · p. 29
  • At t = 10^7, the betting envelope is 12% smaller than the stitching envelope, while the gamma-exponential mixture is 2.6 times larger.The betting envelope is the smallest throughout the FrozenLake run.Source: §5.2 · p. 29
  • These are the first data-dependent anytime-valid envelopes for TD learning, and they yield level-α stopping times with error at most ε with probability at least 1 − α.The stopping time is the first time the envelope is at most ε.Source: §5.2 · p. 29

6 Conclusion

The paper presents a general recipe for observable, nonasymptotic anytime-valid envelopes by reducing algorithm performance recursions to time-uniform bounds on weighted noise sums. Its scope does not yet cover current-gradient-adapted step sizes or Markovian noise.

6 Conclusion

  • The recipe combines an algorithm’s performance recursion with time-uniform bounds on weighted martingale differences to produce observable anytime-valid envelopes.Mixing, stitching, and product-betting martingales provide boundary constructions transferred back to the iterates.Source: §6 · p. 30
  • The framework recovers or sharpens existing time-uniform guarantees in some settings and provides the first data-dependent guarantees in several others.The paper reports that betting-based envelopes often outperform stitching- and mixing-based envelopes.Source: §6 · p. 30
  • For SGD, the framework allows predictable step sizes, but not step sizes adapted to the current stochastic gradient; Markovian noise remains future work.Current-gradient-adapted step sizes make the weighted noise sum cease to be a martingale.Source: §6 · p. 30

AI usage statement4

The authors acknowledge using ChatGPT-Pro to improve exposition and simplify some proofs, including calculations in §14 that were independently verified.

AI usage statement4

  • ChatGPT-Pro was used to improve exposition and simplify some proofs, including tedious calculations in §14 that were independently verified.The numerical experiments were implemented by Codex, and the authors take responsibility for the paper’s claims and technical details.Source: AI usage statement4 · pp. 30–31
  • The authors state that they take responsibility for the veracity of all claims and technical details.The numerical experiments were implemented by Codex.Source: AI usage statement4 · p. 31
  • The numerical experiments were implemented by Codex.Source: AI usage statement4 · p. 31

Appendix

The appendix expands the boundary constructions and optimization module, derives SGD recursions, adds applications, and presents modularized proofs.

Appendix

  • Section 7 gives a detailed, case-by-case treatment of the boundary constructions, while §8 analyzes the optimization module.Source: Appendix · p. 41
  • Section 9 derives the key recursion for stochastic gradient descent under different assumptions.Source: Appendix · p. 41
  • Section 10 adds two applications that provide first anytime-valid data-dependent envelopes in their respective cases.Source: Appendix · p. 41
  • Sections 11–14 present the proofs, organized section by section.Source: Appendix · p. 41

7 Discussion on anytime-valid boundaries

The section connects the strongly adapted sub-ψ condition to sequential-inference machinery, then compares mixture, stitching, and betting boundaries. Their trade-offs center on computational tractability and tightness, with betting exploiting realized noise projections for sharper control.

7.1 Connotations of Definition 2.2

  • With ℓ0 = 1, the strongly adapted sub-ψ condition is equivalent to a supermartingale formulation, and under a mild variance condition the noise is a martingale-difference sequence.The section relates Definition 2.2 to standard sub-ψ processes and states a square-integrable martingale-difference result under an additional finite-variance condition.Source: §7.1 · p. 41

7.2 Boundary by mixing method

  • Mixture boundaries adapt to predictable weights, but their integration domain may vary over time; normal mixtures can have sharp closed-form bounds, while other cases may need numerical inversion.The framework also gives a sharp, easily computable gamma-exponential upper bound and discrete mixtures for numerical root-finding when closed forms are unavailable.Source: §7.2 · p. 42

7.2.1 A new closed-form Gamma-Exponential mixture boundary

  • Gamma-exponential mixture inversion requires root-finding at every iteration, while bounds on incomplete gamma functions yield sharp closed-form upper bounds.The per-iteration numerical inversion is identified as a practical computational barrier.Source: §7.2.1 · pp. 42–43

7.2.2 Discrete mixture boundary

  • Discrete mixtures empirically retain much of continuous-mixture sharpness and support numerical implementation, but may still require a one-dimensional root solve at every monitoring time.This requirement applies in the absence of sharp upper bounds.Source: §7.2.2 · p. 43

7.3 Boundary by stitching method

  • Stitching avoids mixture-boundary root-finding through geometrically spaced epochs and closed-form evaluation, but loses tightness by retaining only the largest single-account term.That replacement discards mutual cancellation among accounts retained by discrete mixtures.Source: §7.3 · p. 44

7.4 Boundary by betting method

  • Product betting yields a sharper boundary than discrete mixing by using exact martingales, and realized noise projections can tighten control when noise is light-tailed relative to its range.The improvement is relative to the discrete-mixture boundary; the light-tailed condition is that projections are typically much smaller than their worst-case bound.Source: §7.4 · p. 45

7.4.1 A sharper betting envelope

  • When observable gradients are bounded, betting can provide a sharper envelope than applying the bounded-noise theorem with the difference bound 2c.The construction adapts the betting argument to ξt = gt − Et−1gt for observables gt bounded by c.Source: §7.4.1 · p. 45

7.5 Proofs of results in §7

  • The proofs use predictable truncation to preserve the supermartingale control needed for Ville’s inequality, and the betting proof combines product martingales across support points.The truncation matches the predictable weights to the relevant time-varying parameter set before applying the uniform bound.Source: §7.5 · pp. 46–47

8 Optimization module for Stochastic gradient descent

The optimization module derives one-step recursions by pairing SGD performance measures with compatible growth and smoothness assumptions. It also organizes implications among assumptions, helping identify which structural conditions can support a given analysis.

8 Optimization module for Stochastic gradient descent

  • The SGD optimization module derives recursion (1) under different assumptions, then converts it into anytime-valid boundaries using the paper’s general boundary results.Growth conditions impose lower-curvature structure, while smoothness conditions constrain how erratically the objective behaves.Source: §8 · p. 47

8.1 Growth assumptions

  • Growth assumptions range from convexity to weaker conditions used in non-convex SGD analyses, and different analyses rely on different subsets.The paper collects examples in Table 4.Source: §8.1 · p. 48, Table 4 · p. 48

8.2 Smoothness assumptions

  • Smoothness assumptions bound the structure of ∇F and are collected alongside their implications with other assumptions.The paper presents the implication chart in Figure 4 and proofs in §8.4.Source: §8.2 · p. 48, Figure 4 · p. 50

8.3 Performance measures

  • The analysis primarily targets last-iterate performance, and each performance measure must be paired with structural assumptions compatible with a recursion.The paper also considers Polyak-Ruppert averaged iterates separately; deterministic envelope transfer between measures is possible under the stated table conditions without slackness.Source: §8.3 · pp. 48–49

8.4 Proofs for implications between different growth and smoothness assumptions

  • The implication results include SC ⇒ C ⇒ StC ⇒ QCγ, SCm ⇒ RSIm and PŁ ⇒ KŁ*, plus quantitative links such as SCm ⇒ PŁ2m and RSIμ with LS_L ⇒ PŁ2μ²/L.Additional results establish SC ⇒ DISS, PŁ with QCγ and LS ⇒ RSI, and LS or LC ⇒ LG.Source: §8.4 · pp. 49–51

9 From assumptions and performance measures to envelopes

This section develops routes from assumptions and performance measures to one-step recursions and observable anytime-valid envelopes, including an LSC-based approach and transfers between performance measures without additional slack. It illustrates stitching, mixture, and betting constructions across optimization settings and provides proofs for the envelope results.

9.1 sub-Gamma stitching boundary for RSI with Zt,1

  • For RSI with Zt,1, the betting boundary is strictly sharper than stitching, and stitching choices recover the empirical Bernstein boundary of Aolaritei et al. [2026].Other stitching parameter choices yield alternative anytime-valid boundaries.Source: §9.1 · pp. 51–52

9.2 sub-Gaussian stitching boundary for LS and ˜Zt,2

  • For LS with ˜Zt,2, stitching recovers Aolaritei and Jordan [2025] under bounded gradients, while an alternative boundary needs no gradient bound and can be sharper.The alternative uses the chain’s position to control the gradient proxy; discrete mixtures can provide a provably sharper boundary.Source: §9.2 · p. 52

9.3 Boundaries under LS and KŁ‹

  • Under LS and KŁ, the gap condition controls Zt,2 directly; the PL case gives zero additive slack and linear contraction, and SGD under C recovers and sharpens Aolaritei and Jordan [2025].The section also supplies valid βt choices for power-type KŁ conditions.Source: §9.3 · p. 53, §9.3.3 · p. 54

9.4 Boundaries under C

  • For projected SGD under convexity alone, the weighted-suboptimality potential supports stitching boundaries that recover Aolaritei and Jordan [2025], while discrete mixtures can sharpen them.The analysis uses the potential Zt,1 + 2StZt,4 and sets at = 1 in the recursion.Source: §9.4 · p. 54, §9.4.1 · p. 54, §9.4.2 · p. 54

9.4.3 Combining the sub-Gaussian and the betting envelope

  • Under the stated conditions, the hybrid sub-Gaussian-and-betting envelope is time-uniform and no larger than the stitching envelope.The hybrid combines the benefits of the two constructions for convex SGD with bounded stochastic gradients.Source: §9.4.3 · p. 55

9 From assumptions and performance measures to envelopes

  • Matching growth and smoothness assumptions to their natural performance measures reduces envelope construction to a one-step recursion and observable boundary control.The section applies this pattern across multiple settings, using generic observable boundaries from Theorems 2.3–2.5.Source: §9.4.3 · p. 55, §9.5 · p. 55

9.5.1 Analysis under QC

  • Quasar-convexity supports a simultaneous bound on weighted suboptimality, while adding strong convexity yields a larger potential for the recursion.The QC analysis tracks Zt,4; under strong convexity the potential also includes accumulated suboptimality.Source: §9.5.1 · pp. 55–56

9.5.2 Convexity and Lipschitz gradient

  • With convexity and Lipschitz gradients, the interpolation inequality controls Zt,5 at no additional cost, and bounded stochastic gradients enable a betting construction.The optimization module assumes 0 ≤ ηt ≤ 1/L.Source: §9.5.2 · p. 56
  • The cited excerpt gives the relation t ≤ R_t for every t ≥ 0, but does not identify what quantities t and R_t represent.Source: §9.5.2 · p. 56

9.5.3 Analysis under LSC

  • Under LSC, Hessian bounds at x0 yield local curvature bounds m* = e^-CrD m0 and L* = e^CrD M0, enabling anytime-valid boundaries for Z_t,1.The argument uses the Hessian-controlled ball to obtain strong convexity and smoothness locally; the resulting predictable coefficient depends on past observations.Source: §9.5.3 · p. 57

9.5.4 Transfers between performance measures

  • If Z_t,i ≤ R_t for i ∈ {1, 2, 3, 4, 5} holds for all t with probability at least 1 − α, Table 7 transfers bounds among these measures with the same probability and no slack.Bounds on or from Z_t,1 require x* to be unique.Source: §9.5.4 · p. 57, Table 7 · p. 58

9.6 Proofs for the results in §9

  • By Lemma 2.1, the probability that Z_t^C stays at or below R_t for every t ≥ 0 is at least 1 − α.Source: §9.6 · p. 59

10 Extended applications

Section 10 gives explicit boundaries for Oja’s algorithm and temporal difference learning, then develops data-dependent anytime-valid envelopes for momentum-assisted SGD. The momentum envelopes allow arbitrary predictable step sizes, include a finite-variance guarantee, and recover established asymptotic rates under specified schedules.

10.1 Explicit boundaries for Oja’s algorithm

  • For Oja’s algorithm, the section supplies explicit mixing, stitching, and betting boundary constructions for bounded observations, plus mixing and stitching constructions under a finite fourth-moment condition.The realized-norm construction replaces the worst-case B⁴ with ||X_s||⁴.Source: §10.1 · p. 60

10.2 Explicit boundaries for Temporal Difference learning

  • For temporal difference learning, the self-normalized envelope is sharper than the sub-Gaussian envelope and adapts to small realized TD updates.The comparison follows from the stated bound ν_t ≤ 2G(θ_{t−1})².Source: §10.2 · p. 60

10.3 Momentum-assisted SGD

  • The paper gives the first data-dependent, anytime-valid guarantees for momentum-based stochastic optimization, including a finite-variance guarantee.In the finite-variance regime, the previous results cited here provided only in-expectation and almost-sure convergence.Source: §10.3 · p. 61, §10.3.2 · p. 63

10.3.1 Set-up and optimization module for momentum-assisted SGD

  • The momentum-SGD optimization module accommodates arbitrary predictable step sizes, including non-monotone, data-driven choices.For nonincreasing step sizes, the recursion coincides with the cited earlier result.Source: §10.3.1 · pp. 61–62

10.3.2 Boundaries for momentum-assisted SGD

  • Under finite conditional variance, self-normalized envelopes provide an anytime-valid guarantee for momentum SGD; quadratic product betting further sharpens these envelopes.The stated variance condition is E_{t−1}||ξ_t||² ≤ σ².Source: §10.3.2 · p. 63

10.3.3 Rates of the observable envelopes

  • The constructed observable momentum-SGD envelopes recover the asymptotic rates of Feng et al. [2023, 2025], and match the fixed-iterate rate of the actual performance measure under the stated step-size choice.With p = 2, the envelopes match the asymptotic fixed-iterate rate of E[F(x_t) − F*].Source: §10.3.3 · p. 64

10.4 Q-learning

The Q-learning analysis turns the Bellman operator’s ℓ∞ contraction into a recursion for a smooth weighted Lyapunov performance measure, then supplies anytime-valid envelopes for Q-iterates and quality functions. Under bounded rewards, the betting envelope is uniformly sharper than stitching, and the envelope also supports a direct condition for certifying an optimal greedy policy.

10.4 Q-learning

  • The section derives the Q-learning optimization recursion and applies general boundary theorems to construct envelopes for Q-iterates or quality functions.This provides anytime-valid counterparts to the stopping conditions of Even-Dar et al. [2006], whose intervals are tailored to elimination schemes rather than generic Q-learning trajectories [p011].Source: §10.4 · p. 65

10.4.1 Set-up and optimization module for Q-learning

  • The setup covers synchronous updates of every state-action coordinate and asynchronous updates that sample a coordinate with known positive probability.The analysis considers a finite-state-space MDP and uses the Bellman optimality operator’s ℓ∞ contraction.Source: §10.4.1 · p. 65
  • Because the Bellman operator contracts in ℓ∞, the analysis uses a smooth weighted ℓϱ Lyapunov function rather than squared ℓ2 error or the nonsmooth ℓ∞ error.The choice of ϱ trades off contraction strength against smoothness.Source: §10.4.1 · p. 65

10.4.2 Boundaries for Q-learning

  • With probability at least 1 − α, the envelope bounds the Lyapunov measure, Q-iterate ℓ∞ error, and greedy-policy value loss simultaneously for all iterations.If every greedy action has a Q-value gap exceeding 2√(2R_t), the greedy policy is optimal with probability 1 − α.Source: §10.4.2 · p. 66
  • Under bounded rewards, the betting envelope is uniformly sharper than the stitching envelopes.Source: §10.4.2 · p. 66

10.5 Proofs of results in §10

The proofs verify that algorithm-specific recursions can be paired with observable boundaries to yield anytime-valid envelopes. They also establish the required controls for SGD and Q-learning, including the transfer from iterate bounds to objective or policy guarantees.

Proofs for §10.3

  • For Theorem 10.1, the proof verifies the recursion and compares observable and oracle boundaries on the event where prior iterates remain within their envelopes.The resulting envelope transfers to objective suboptimality on the same event.Source: §10.5 · p. 67
  • The product-betting proof uses predictable noise-weighted sums and a nonnegative supermartingale, then applies Ville’s inequality to obtain a simultaneous probability bound.It compares the observable and oracle mixtures on the event where the envelope controls the predictable weights.Source: §10.5 · p. 68
  • Theorem 10.2’s proof controls noise and iterate moments on high-probability events, then uses the discrete Grönwall inequality to transfer the envelope to objective suboptimality.Source: §10.5 · p. 69

Proofs for §10.4

  • The Q-learning proof combines the weighted Lyapunov contraction with the general envelope result to bound the Lyapunov measure and derive ℓ∞ iterate and value-function guarantees.Source: §10.5 · p. 70

11 Proofs of results in §2

These proofs establish general anytime-valid boundaries by comparing observable boundary constructions with oracle ones on suitable events. The resulting argument yields simultaneous envelopes for all iterations.

Proofs of results in §2

  • The proof establishes Z_t ≤ R_t for all t ≥ 0 by controlling the boundary crossing and applying the general boundary result.Source: §11 · p. 71
  • The proof applies mixing, discrete-mixture, and stitching constructions to the predictable weighted-sum boundary, obtaining simultaneous threshold bounds.It then inverts the thresholds to derive the stated boundary comparisons.Source: §11 · p. 71
  • The discrete-mixture comparison bounds the stated boundary by Gα(V_t, c_t).Source: §11 · p. 72

12 Proofs of results in §3

The proofs establish bounds underpinning the §3 results, including conditions for applying time-uniform boundaries, a transfer from noise-process bounds to averaged iterates, and growth and moment bounds under Theorem 3.2’s assumptions. They also derive decay bounds for weighted terms and apply them to bound the §3.3 theorem’s error quantity term by term.

12.1 Proofs of results in §3.1

  • The §3.1 proof verifies Lemma 2.1’s conditions by applying Corollary 7.6 to the key recursion and checking the required boundary and remainder inequalities.It then invokes Theorem 2.5 and Lemma 2.1 to complete Proposition 1.Source: §12.1 · p. 73

12.2 Proofs of results in §3.2

  • The §3.2 proofs construct nonnegative supermartingales and use Ville’s inequality (Lemma 1 of Howard et al., 2020) to obtain time-uniform guarantees for Propositions 2 and 3.For Proposition 2, the proof lower-bounds the betting process by an observable quantity before applying the boundary lemma.Source: §12.2 · p. 74

12.3 Proofs of results in §3.3

  • On the event that ||Ξ_t|| ≤ B_t for all t, Proposition 14 transfers this bound to a simultaneous envelope for the averaged-iterate performance measure.Theorem 3.1’s proof then establishes the corresponding probability guarantee for all t ≥ 1.Source: §12.3 · p. 75
  • For each boundary choice b ∈ {NM, GS, ΓS, Bet}, the proof bounds B_t^2 by C_b t h_b(t) almost surely for all t ≥ 1.C_b depends on α and G, and additionally on ρ for NM.Source: §12.3 · p. 76
  • Under Theorem 3.2’s assumptions and η_t = η°(t + t_0)^−β, the proof obtains E||e_t||^2 ≤ C(t + t_0)^−β for all t ≥ 1.Here β ∈ (0, 1), and C depends only on G, μ, η°, t_0, and β.Source: §12.3 · p. 77
  • With the stated parameter choices, Lemma 14.2 gives w_t ≤ C(t + t_0)^-2β for t ≥ 1.The choices are a_k = w_T 1_{k≤T}, c = 4μη°, ν = β, and q = 2β.Source: §12.3 · p. 77
  • To control D_t,2, the proof uses Minkowski’s inequality, summation by parts, and the bound on the L2 norm of e_s.It also uses ‖e_0‖ ≤ G/μ and a concavity-based bound on successive inverse step sizes.Source: §12.3 · p. 77
  • The proof of Theorem 3.2 bounds the error quantity termwise, discards the cap G/μ, and applies Lemma 12.1 and (70) with Minkowski’s inequality.The concluding comparison uses β ∈ (1/2, 1), h_b ≥ 1, and t^-1 ≤ h_b(t)/t.Source: §12.3 · p. 78

13 Proofs of results in §4

The appendix proves the algorithm-specific recursions and envelopes used in §4, including results for temporal difference learning and Gaussian variational inference.

13.1 Proofs of results in §4.1

  • For Proposition 4, spectral decomposition isolates the top-eigenvector drift and bounds the remainder to establish recursion (24) for every realization.The proof controls the two remainder terms separately before concluding the recursion.Source: §13.1 · pp. 78–79

13.2 Proofs of results in §4.2

  • For temporal difference learning, the update yields recursion (26), and the resulting envelope bounds value-function error by R_t with probability at least 1−α.The proof substitutes the TD update into the performance measure and applies the general envelope result.Source: §13.2 · p. 79

13.3 Background on stochastic variational inference and proofs of §4.3.1

  • Within the Gaussian family, the Bures–Wasserstein gradient is the L2(q)-projection of the KL gradient onto affine vector fields, and Gaussian optimal transport is affine.The affine optimal transport map is available in closed form.Source: §13.3 · pp. 79–80
  • The Bures–Wasserstein proof couples the update to the optimizer and derives drift at least µZ_{t−1} using strong geodesic convexity.Theorem 4.2’s proof also establishes an initial bound before invoking Proposition 6 and the general envelope results.Source: §13.3 · pp. 81–82

14 Helper results and proofs

The helper results provide bounds for boundary thresholds, step-size schedules, gradient-dominated objectives, and polynomially decaying recurrences.

Lemma 14.1

  • If ||∇F(x)||²≤K_*(F(x)−F*) for all x, then F(x)−F*≤K_*||x−x*||²/4 and ||∇F(x)||≤K_*||x−x*||/2.The proof obtains the bounds by applying the gradient inequality to a regularized square root of the objective gap.Source: §14 · p. 82

Lemma 14.2

  • Under Lemma 14.2’s recurrence assumptions, a_{k+1} is bounded by K1(k+1+γ)^{-q}+K2(a0)exp{−c(k+1+γ)^{1−ν}/(1−ν)}, so sup_k(k+γ)^q a_k<∞.The constants K1 and K2 depend only on (c,d,q,ν,γ).Source: §14 · p. 82

Lemma 14.3

  • Lemma 14.3 bounds the threshold where m_{ρ,G}(x;v,b)<1/α by u_{α,ρ,c}(v,b).The bound is expressed using c(b−1)+cbD_{a(v,b)}(L(v,b)).Source: §14 · p. 82

Lemma 14.4

  • For η_t=η°log^{-p}(t+2), with η°>0 and p>1, Lemma 14.4 bounds the displayed sums using an integral test and convergent series.The proof uses a logarithmic step-size schedule and bounds the sums by quantities including H_p and C°.Source: §14 · p. 83
Loading 2610.23570v1…