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

1 Introduction

• Fixed-time SGD guarantees generally fail at data-dependent stopping times, while horizons obtained by inverting worst-case bounds can be valid but overly conservative.Repeatedly inspecting iterates, stochastic gradients, or validation losses couples stopping to observed random fluctuations, so a deterministic-time certificate need not remain valid.Source: §1 · p. 2
• The paper constructs fully observable confidence sequences that simultaneously bound last-iterate squared distance and weighted-average suboptimality, enabling valid stopping when a bound crosses a target tolerance.The certificates support continuous monitoring and remain valid at the selected stopping time.Source: §1 · p. 3
• These strongly convex certificates attain the canonical 1/t rate up to log log t factors, adapt to realized stochastic behavior, and terminate orders of magnitude earlier than natural deterministic horizons in numerical experiments.The construction uses recursive confidence sequences and empirical Bernstein bounds for adapted processes with time-varying conditional means and growing predictable ranges.Source: §1 · p. 3

1.1 Problem formulation

• The optimization model assumes a differentiable µ-strongly convex objective over a closed convex set, yielding a unique minimizer and projected SGD dynamics.The analysis also extends directly to nondifferentiable objectives by replacing gradients with subgradients.Source: §1.1 · pp. 3–4
• Stepsizes must be predictable—measurable from the past trajectory—so the framework permits deterministic, diminishing, and trajectory-adaptive schedules such as AdaGrad-type rules.At iteration t, ηt is Ft−1-measurable, while Ft contains the complete trajectory through that iteration.Source: §1.1 · p. 4
• Anytime-valid confidence sequences can be monitored continuously and evaluated at trajectory-selected stopping times without invalidating guarantees.With probability at least 1 − α, each finite stopping rule returns an iterate satisfying its prescribed accuracy requirement.Source: §1.1 · pp. 4–6
• The two target measures are squared distance to the optimizer for last-iterate certification and weighted-average suboptimality for certifying an observable averaged iterate.The corresponding stopping rules return the first iterate certified within squared distance ε or ε-suboptimality, respectively.Source: §1.1 · pp. 5–6

1.2 Contributions

• Under sub-Gaussian noise, fully observable confidence sequences are computable online from observed stochastic gradients and stepsizes and attain the optimal 1/t rate up to iterated-logarithmic factors.They remain sensitive to the realized trajectory and can be smaller than corresponding worst-case bounds.Source: §1.2 · p. 6
• The bounded-gradient empirical-Bernstein refinement replaces the worst-case variance proxy G^2 with realized squared gradient magnitudes and adds a t^-3/2 correction.It preserves worst-case rates while remaining fully observable and was generally one order of magnitude smaller than Hoeffding-based sequences in experiments.Source: §1.2 · p. 7
• For minibatch SGD with b conditionally independent gradients, Hoeffding sequences reduce the variance proxy to σ^2/b, while empirical Bernstein pools within-batch second-moment information.The minibatch empirical-Bernstein boundary improves at 1/√b in its leading term and 1/b in its lower-order correction.Source: §1.2 · p. 7
• Two to three orders of magnitude separate the adaptive bounds from corresponding worst-case bounds for larger minibatches, with ex ante guarantees potentially more conservative.Figure 1 illustrates trajectory-adaptive certification for squared distance and weighted-average suboptimality at target accuracy ε = 10^-3.Source: §1.2 · pp. 7–8, Figure 1 · p. 8
• The paper establishes a time-uniform empirical Bernstein inequality that adapts jointly to the observed quadratic process and a predictable range that may grow without bound.Predictable truncation and dyadic stitching produce an explicit boundary nondecreasing in both quantities.Source: §1.2 · pp. 7–8, §1.3 · p. 9
• Linearly increasing weights attain the optimal O(1/t) rate, whereas uniform averaging incurs an additional logarithmic factor and achieves O(log t/t).This weighted-averaging choice underlies the paper’s suboptimality analysis for the averaged iterate.Source: §1.2 · p. 7

1.3 Related work

• Anytime-valid sequential inference motivates certificates that remain valid under continuous monitoring and data-dependent stopping, avoiding failures of fixed-time validity after favorable fluctuations.The framework is rooted in time-uniform boundaries constructed from exponential supermartingales through mixtures or stitching.Source: §1.3 · pp. 8–9
• In strongly convex SGD, contractivity enables sharper trajectory-adaptive certificates but requires new recursive and self-normalized sequential techniques.The paper continues trajectory-adaptive confidence-sequence work from convex and smooth nonconvex SGD into the strongly convex setting.Source: §1.3 · p. 9
• Trajectory-adaptive confidence sequences provide fully observable online stopping certificates, adapt to realized stochastic fluctuations, and retain the same worst-case decay orders.Existing time-uniform bounds depend only on iteration count and global parameters, whereas these certificates adapt to the realized trajectory.Source: §1.3 · p. 10
• Roughly five orders of magnitude separate the Figure 1 trajectory-adaptive distance certificate from Rakhlin et al. [36]’s finite-horizon bound, with an even larger gap versus Pham et al. [33].The comparison highlights the quantitative benefit of adapting to the observed trajectory rather than using ex ante worst-case envelopes.Source: §1.3 · p. 10

1.4 Organization and notation

• The paper develops time-uniform Hoeffding confidence sequences, empirical-Bernstein refinements for bounded gradients, minibatch extensions, and numerical evaluations of certified stopping rules.Sections 2–4 develop the confidence-sequence methods, while Section 5 evaluates the resulting sequences and stopping rules numerically.Source: §1.4 · p. 10

2 Confidence Sequences under Sub-Gaussian Noise

• The framework constructs anytime-valid upper confidence sequences for the last-iterate squared distance and weighted-average suboptimality by controlling directional gradient-noise partial sums.The SGD-specific recursions establish conditional exponential-moment bounds using predictable variance proxies.Source: §2 · pp. 11–12
• Dyadic stitching converts fixed-λ sub-Gaussian boundaries into a curved boundary that adapts to realized intrinsic time uniformly over the infinite horizon.The construction combines boundaries across successive dyadic scales while allocating error probability across scales.Source: §2 · p. 11

2.1 Last-iterate squared distance to the optimizer

• Replacing unknown distances by the uniform diameter bound yields t^-1/2 decay, whereas the recursive construction achieves near-1/t decay.The sharper rate comes from recursively exploiting simultaneous coverage rather than discarding contraction toward the optimizer.Source: §2.1 · p. 13
• Theorem 2.3 gives a fully observable, simultaneously valid confidence sequence for last-iterate squared distance from an observable initial upper bound and the SGD trajectory.The recursive envelopes dominate the unknown distances entering intrinsic time, preserving the coverage guarantee under Assumptions 1.1–1.4.Source: §2.1 · pp. 13–14
• The observable distance confidence sequence supports any predictable stepsize sequence, including stepsizes selected adaptively from the observed trajectory.It is not tied to a particular schedule or an a priori convergence-rate calculation.Source: §2.1 · p. 14
• The last-iterate distance confidence sequence also decays at the worst-case 1/t rate up to an iterated-logarithmic factor under η_t = 1/(µt).The recursive construction is self-localizing: shrinking certified radii reduce future variance scales, lowering intrinsic-time growth from order t^3 to order t^2 up to slowly varying factors.Source: §2.1 · pp. 14–15
• Directly replacing distances Zt by the diameter bound yields only t−1/2-type decay, up to stitched-logarithmic factors, whereas the recursive observable envelope preserves the near-1/t rate.Source: §2.1 · p. 15

2.2 Suboptimality of the weighted-average iterate

• The weighted-average construction uses linear weighting to telescope distance terms and retains directional gradient noise explicitly for anytime-valid analysis.The resulting bound is made observable by substituting the distance sequence’s observable upper bounds directly, without a second recursive construction.Source: §2.2 · pp. 16–17
• The observable confidence sequence for weighted-average suboptimality is valid simultaneously over time under Assumptions 1.1–1.4 and η_t = 2/(µ(t + 1)).It combines the distance confidence sequence with a stitched bound for weighted directional gradient noise, allocating α/2 to each event and obtaining overall coverage at least 1 − α.Source: §2.2 · pp. 17–18
• The observable suboptimality envelope recovers the optimal 1/t worst-case decay rate up to iterated-logarithmic factors.Source: §2.2 · p. 18
• The observable suboptimality certificate does not degrade the optimal worst-case rate inherited from the distance envelopes.The near-1/t distance envelopes yield a corresponding near-1/t suboptimality rate.Source: §2.2 · p. 18
• The suboptimality bound achieves near-1/t decay because its intrinsic time grows as t^2, its stitched boundary as t, and S_t scales as t^2.This mechanism produces the near-1/t rate after dividing the boundary by S_t.Source: §2.2 · p. 18
• The suboptimality certificate improves strong-convexity dependence by one power, replacing G^2/µ^2 and σ^2/µ^2 with G^2/µ and σ^2/µ.When µ is small, this improvement can make the certificate informative substantially earlier.Source: §2.2 · p. 18

3 Refined Confidence Sequences under Bounded Gradients

• The empirical Bernstein construction replaces the fixed proxy G^2 with realized squared gradient values, adapting confidence sequences to stochastic gradients observed along the trajectory.The method uses realized increment squares rather than a predictable variance proxy.Source: §3 · p. 19
• Theorem 3.3 provides a time-uniform empirical Bernstein bound whose predictable range may evolve with history and grow without any finite uniform bound.The construction stitches simultaneously over accumulated quadratic variation and the largest predictable range encountered.Source: §3 · pp. 19–20

3.1 Last-iterate squared distance to the optimizer

• For the last-iterate distance, combining the distance decomposition with Theorem 3.3 yields a latent empirical Bernstein confidence sequence.The construction handles trajectory-dependent directional-noise ranges that can grow under canonical η_t ≍ 1/t stepsizes.Source: §3.1 · p. 21
• Compared with the sub-Gaussian construction using G^2, the refined last-iterate sequence is driven by realized directional quantities bounded by ||g_s||^2 Z_s.The cited passage states the worst-case comparison continues up to an additional iterated-logarithmic factor, but its numerical expression is not included here.Source: §3.1 · p. 22
• The refined distance sequence adapts to realized stochastic-gradient magnitudes and directions, while its growing-range contribution is lower order and preserves near-1/t worst-case decay.The observable quadratic process uses realized gradient norms, and Proposition 3.6 establishes the lower-order range contribution and near-1/t rate for η_t = 1/(µt).Source: §3.1 · pp. 22–23
• Theorem 3.5 constructs a fully observable confidence sequence for the last-iterate squared distance by recursively replacing optimizer-dependent quantities with observable distance envelopes.The construction is valid under the stated assumptions and requires an initial observable upper bound R0 on the initial latent distance.Source: §3.1 · p. 22

3.2 Suboptimality of the weighted-average iterate

• Theorem 3.8 extends the recursive observable construction to a fully observable confidence sequence for weighted-average suboptimality.The construction combines the suboptimality analysis with observable distance envelopes to remove dependence on the unknown optimizer and uses simultaneous confidence allocation.Source: §3.2 · pp. 24–25
• The refined suboptimality sequence adapts to realized gradient magnitudes, retains near-1/t worst-case decay, and incurs only a lower-order contribution from the growing predictable range.Proposition 3.9 gives these conclusions for η_t = 2/(µ(t+1)) under the stated initialization and assumptions.Source: §3.2 · p. 25

• Minibatch averaging yields conditional sub-Gaussian noise with variance proxy σ2/b, so Section 2 confidence sequences apply after replacing gt with ¯gt.Source: §4 · p. 26
• The minibatch empirical Bernstein extension preserves individual realized quadratic contributions, achieving the usual 1/sqrt(b) reduction in the leading term and an explicit 1/b linear range term.Source: §4 · p. 26

Last-iterate distance

• The refined distance sequence is fully observable and uses λmax(bΣs) to retain realized minibatch geometry instead of a uniform worst-case G2 bound.The spectral relaxation is direction-free and can be substantially sharper when gradients are small or their energy is distributed across directions.Source: §4 · p. 28

Weighted-average suboptimality

• The same spectral relaxation and recursive distance envelope produce a fully observable minibatch confidence sequence for weighted-average suboptimality.Source: §4 · pp. 28–29

• For general batch size b, the empirical Bernstein boundary retains the usual 1/sqrt(b) decay up to stitching factors, while its linear range term scales explicitly as 1/b.Source: §4 · p. 29

5.1 Experimental setup

• Each figure reports one SGD trajectory to expose trajectory-dependent confidence sequences and stopping certificates, with repeated seeds showing essentially identical qualitative behavior.The plotted horizon is arbitrary because the displayed confidence sequences remain valid beyond it and do not depend on that horizon.Source: §5.1 · p. 30

5.2 Introductory plot

• At the first time a bound drops below ε = 10−3, stopping certifies with probability 1 −α that the returned weighted average has suboptimality at most ε.This demonstration uses SGD on covertype.binary with minibatch size b = 256 and evaluates all bounds along the same trajectory.Source: §5.2 · p. 32
• The recursive adaptive distance bound Udist lies several orders of magnitude below RSS12 because it uses larger realized information and accounts for minibatch variance reduction.RSS12 uses larger explicit constants and does not account for minibatching, whereas Udist uses the minibatch variance proxy.Source: §5.2 · p. 32
• 312 times earlier, the empirical-Bernstein minibatch bound required 5.1 × 10^6 gradient lookups versus 2.6 × 10^8 for H and 1.6 × 10^9 for the worst-case baseline.All comparisons used the same confidence level, and the improvement came from exploiting observed trajectory quantities and realized minibatch second moments.Source: §5.2 · p. 32

5.3 Effect of the minibatch size

• For SGD on covertype.binary, EB improves on H by about one order of magnitude at b = 1, while the Rakhlin et al. [36] bound is about one order above the worst-case baseline.As b grows, the gap between the Rakhlin et al. [36] bound and the worst-case baseline widens to three orders of magnitude at b = 1024.Source: Figure 2 · p. 33, §5.3 · p. 33

5.5 Robustness to parameter misspecification

• Overestimating G by 10 makes worst-case and H curves approximately 100 times larger, whereas misspecified and well-specified EB curves are asymptotically equivalent.EB’s leading deviation term uses realized minibatch second moments, while G affects only its lower-order range term; conservative upper bounds preserve validity but reduce tightness for other constructions.Source: Figure 4 · p. 35, §5.5 · pp. 35–36
• Overestimating R0 by a factor of 1000 changes the squared-distance confidence sequence by only 4% after 100 iterations and 0.01% after 10^3 iterations.The initial discrepancy matches the misspecification factor but vanishes rapidly as trajectory-dependent terms accumulate.Source: §5.5 · p. 36

5.6 True single-pass

• In the true single-pass covertype.binary experiment, bUsub_t is 2.7 × 10^2 times tighter after 2269 SGD iterations, and improvements persist without reused observations.The corresponding Section 5.2 factors are 6.4 and 2.7 × 10^2 after the same number of iterations.Source: §5.6 · p. 37

5.7 Summary of the empirical findings

• Confidence sequences certify target accuracy several orders of magnitude earlier than trajectory-independent bounds, with minibatching recovering more of the gap to ground truth as b increases.Worst-case bounds remain unchanged across problem instances, whereas the confidence sequences adapt to realized trajectories.Source: §5.7 · p. 37
• Empirical-Bernstein sequences are consistently tighter than Hoeffding-based sequences, adapting through realized second moments while conservative G and R0 effects become negligible later.Hoeffding-based sequences retain asymptotic dependence on the fixed sub-Gaussian variance proxy σ2.Source: §5.7 · p. 37
• Despite these improvements, experiments retain a considerable gap between confidence sequences and ground truth, leaving sharper analysis of SGD dynamics open.This limitation applies where ground truth is available for comparison.Source: §5.7 · p. 37

A.1.1 Proof of Lemma 2.1

• The Lemma 2.1 proof obtains a time-uniform variance-adaptive bound by stitching fixed-λ supermartingale bounds over dyadic variance ranges and applying a union bound.The construction then selects the dyadic range containing the effective variance process at each time.Source: §A.1.1 · pp. 41–42

• The proof begins by controlling ¯X_t uniformly over time.Source: §A.1.2 · p. 42
• Because x_t, η_t, and A_t are F_{t−1}-measurable, Assumption 1.3(ii) applies with a predictable direction.Source: §A.1.2 · p. 42
• Lemma 2.1 is then applied, and its bound is substituted into the preceding decomposition to obtain U_dist.Source: §A.1.2 · p. 42

A.1.3 Proof of Theorem 2.3

• Theorem 2.3’s recursive quantities are defined inductively from prior data, making the resulting confidence construction fully observable at every time.The proof first establishes recursive well-definedness before applying the adaptive confidence sequence.Source: §A.1.3 · p. 42
• On the event E_α with probability at least 1 − α, induction verifies the claimed bounds from the base case through every later time.Monotonicity of H_α and the recursive confidence-sequence guarantee drive the induction.Source: §A.1.3 · p. 43

A.1.4 Proof of Proposition 2.4

• Proposition 2.4 begins by bounding the deterministic component of the recursive envelope under the monotonicity and lower-bound properties of L_t.The proof uses assumptions including B ≥ 1 and the stated relations among G, μ, and L_t.Source: §A.1.4 · p. 44
• The proposition’s base case is established explicitly at s = 4 using A_3 = 3, η_3 = 1/(3μ), R_0 ≤ G^2/μ^2, and ∥g_3∥ ≤ G.The constant K = 4096 is used to complete this initial bound.Source: §A.1.4 · p. 45
• The induction step propagates the envelope using the observable intrinsic-time recursion, monotonicity of L_s, and the condition σ^2/μ^2 ≤ B.The initial term and truncation by 1 are absorbed into the same scale using inequalities involving K, B, t, and L_t.Source: §A.1.4 · pp. 45–46
• The stitched logarithmic factor is controlled by bounding its component logarithms with L_t and combining them into a product-scale bound.The argument bounds terms involving B, t, and L_t, then applies the resulting estimate in the recursive inequality.Source: §A.1.4 · p. 46
• Combining the deterministic and logarithmic estimates closes the induction and yields the claimed bound after substituting K = 4096.The final steps also use L_t ≤ L_{t+1} and the bound 1/(t − 1) ≤ 5/[3(t + 1)] for t ≥ 4.Source: §A.1.4 · p. 46

• Because x_t is F_{t−1}-measurable, Assumption 1.3(ii) applies with the predictable direction t(x⋆−x_t).Source: §A.1.5 · p. 47
• The increments E_t = Ē_t − Ē_{t−1} therefore satisfy the hypotheses of Lemma 2.1 with the specified variance and exponent parameters.Source: §A.1.5 · p. 47
• Applying Lemma 2.1 to Ē_t using V_t^sub yields a uniform bound, which is substituted into the decomposition and combined with U^sub's definition.Source: §A.1.5 · p. 47

• On E2, the recursive observable bounds establish U_t(α) for every t ≥ t0.Source: §A.1.6 · p. 47
• Theorem 2.3 gives P(E2) ≥ 1 − α/2, providing the high-probability event on which the remaining argument proceeds.Source: §A.1.6 · p. 47
• The proof also controls the initial quantity through Z_t0 ≤ R0 and combines the component events using a union bound.Source: §A.1.6 · pp. 47–48

A.1.7 Proof of Proposition 2.9

• A universal constant C is allowed to change between displays throughout the proof of Proposition 2.9.This convention supports the successive deterministic and boundary-term estimates.Source: §A.1.7 · p. 48
• The proof of Proposition 2.9 controls deterministic and observable boundary terms, then absorbs their logarithmic contributions into the iterated-logarithmic factor.The argument concludes the proposition almost surely after combining the preceding bounds.Source: §A.1.7 · pp. 48–49

A.2.1 Proof of Lemma 3.2

• The proof of Lemma 3.2 establishes the logarithmic inequality by analyzing hθ separately on [0, ∞) and [-1, 0], using monotonicity and endpoint minima.For nonnegative x, hθ is nondecreasing; on the negative interval, its minimum is attained at an endpoint, where hθ(-1)=hθ(0)=0.Source: §A.2.1 · p. 50
• The conditional part of Lemma 3.2 applies the deterministic inequality with x=X/b and θ=λb, then takes conditional expectations to obtain (28).The argument uses the conditional mean m=E[X | G] and the condition λm ≥ -λb > -1.Source: §A.2.1 · p. 50

A.2.2 Proof of Theorem 3.3

• Theorem 3.3 is proved by stitching fixed-λ bounds over dyadic ranges of Wt and Ct and applying a union bound over the resulting indices.Predictability and the running maximum Cs support the construction, while monotonicity follows from the nondecreasing terms in the bounds.Source: §A.2.2 · pp. 51–52

A.2.3 Proof of Theorem 3.5

• Theorem 3.5 first verifies that the recursion defines nonnegative, Ft-measurable quantities, making the resulting process fully observable.The recursion is then analyzed on an event with probability at least 1-α.Source: §A.2.3 · p. 53
• Theorem 3.5 completes its proof by induction over time, using the confidence event at each step and monotonicity to obtain the final inequality simultaneously for all t ≥ t0.The induction assumes the claim through time t-1, proves it through time t, and then closes the argument with the stated probability guarantee.Source: §A.2.3 · p. 53

Induction argument

• An induction argument verifies the recursive claim from the base case s = 4 and propagates it for all later times.The base case uses A_3η_3 = 1/µ, while the induction step controls the deterministic recursion and both empirical-Bernstein arguments.Source: §A.2.4 · p. 54

Empirical-Bernstein control

• The proof bounds the empirical-Bernstein square-root and linear-range contributions by choosing a sufficiently large universal constant K, closing the induction and proving (46).The logarithmic factor is controlled using bounds on the empirical-Bernstein arguments and elementary logarithmic inequalities.Source: §A.2.4 · p. 55

Sharper regime

• When t ≥ 4 and q_t ≤ 1, a sharper version of the bound yields (47).This follows from the sharper form of the recursive estimate after fixing the universal induction constant K.Source: §A.2.4 · p. 55

Asymptotic interpretation

• For fixed α and fixed problem parameters, t = o(q_t), confirming the proposition’s lower-order interpretation.This conclusion follows from the established bounds and the fixed-parameter asymptotics.Source: §A.2.4 · p. 55

• For the prescribed deterministic stepsize, condition (37) is automatic.Source: §A.2.5 · p. 56
• With β := α/2, Proposition B.2 and Theorem 3.5 ensure that each required event has probability at least 1 − β.Source: §A.2.5 · p. 56
• Monotonicity of B_β and the relation Z_t0 ≤ R_0 transfer the bounds to every t ≥ t0, completing the proof.Source: §A.2.5 · p. 56

A.2.6 Proof of Proposition 3.9

• The proof assumes L_t is nondecreasing with L_t ≥ 1 and uses this structure throughout the confidence-bound estimates.These properties support subsequent controls of logarithmic and deterministic terms.Source: §A.2.6 · p. 56
• The proof separately controls both arguments entering the empirical-Bernstein boundary before combining their bounds.Initial contributions and the unit floor are absorbed into the resulting estimates.Source: §A.2.6 · p. 57
• The logarithmic factor is bounded using the definitions of L_t, inequalities for log((j + 1)(j + 2)), and the condition L_t ≥ 1.The argument controls terms involving log L_t and log(1 + log(1 + q_t)) before combining them with earlier bounds.Source: §A.2.6 · pp. 57–58
• The proof bounds the remaining deterministic terms using Assumption 3.1, R_0 = G^2/µ^2, and S_t ≥ t^2/4.Combining these bounds with the empirical-Bernstein controls yields a stronger intermediate estimate.Source: §A.2.6 · p. 58
• The combined estimates prove (59), while the additional condition L_t ≤ t implies q_t ≤ 1 and yields the sharper form (60).The sharper conclusion follows from the strengthened bound under the same condition.Source: §A.2.6 · p. 58
• The proof concludes that t = o(q_t), confirming the lower-order interpretation stated after the proposition.This establishes the asymptotic relationship used to interpret the proposition’s remainder terms.Source: §A.2.6 · p. 58

• The proof fixes a dyadic range level and applies predictable truncation together with stitching over intrinsic-time and range scales.Source: §A.3.1 · pp. 58–59
• Conditional independence of the exponential factors ensures the proof process remains a nonnegative supermartingale after centered increments are truncated.Source: §A.3.1 · p. 59
• With probability at least 1−α, the resulting inequality holds simultaneously for every t ≥ t0, and division by b establishes (63).Source: §A.3.1 · p. 59

B Additional Results

• Proposition B.1 establishes a refined confidence sequence for the squared distance of the last iterate to the optimizer under the stated assumptions and condition (37).The bound is obtained by applying Theorem 3.3 and substituting the resulting inequality into the distance decomposition, simultaneously over all t ≥ t0 with probability at least 1 − α.Source: B Additional Results · pp. 59–60
• The refined last-iterate sequence uses empirical-Bernstein variance and predictable-range quantities defined in equations (35)–(36), with condition (37) ensuring the required integrability.The proof treats the relevant process as adapted and its range as predictable and almost surely finite before invoking the time-uniform inequality.Source: B Additional Results · p. 59
• Proposition B.2 establishes a refined confidence sequence for the weighted-average suboptimality f(x̄_t) − f(x⋆) using η_t = 2/(µ(t + 1)).The resulting bound holds simultaneously for every t ≥ t0 with probability at least 1 − α after applying Theorem 3.3 to the suboptimality decomposition.Source: B Additional Results · p. 60

C Supporting Lemmas

• Lemma C.1 derives a one-step contractive recursion for projected SGD iterates under strong convexity and projection nonexpansiveness.The proof retains the directional gradient-noise term explicitly, enabling the subsequent anytime-valid analysis.Source: C Supporting Lemmas · pp. 60–61
• Lemma C.2 unrolls the contractive recursion into a last-iterate distance decomposition for general predictable stepsizes.The decomposition uses a telescoping mechanism and divides by A_t, whose positivity follows from Assumption 1.4.Source: C Supporting Lemmas · p. 61
• Lemma C.3 derives a weighted-average suboptimality decomposition for η_t = 2/(µ(t + 1)) through a weighted telescoping argument.The pathwise derivation retains the directional gradient-noise term rather than taking expectations, then divides by the aggregate weight and uses convexity.Source: C Supporting Lemmas · pp. 61–62