PaperlayerView exact revision on arXiv

Source-linked AI summary

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

Ruijie Li, Kang Chen, Tianyu Wang

arXiv:2609.08537v1math.OCcs.LGstat.ML

TL;DR

Time-uniform guarantees for SGD matter because they remain valid under data-dependent stopping, but the attainable raw-iterate rates for the general smooth convex setting require a precise overhead criterion. The paper characterizes that frontier through reciprocal-square summability and an approach combining dyadic scheduling with conditional restart. The resulting rates can approach, but do not attain, the square-root log-over-n order.

  • Problem

    The paper asks which profiles permit time-uniform raw-iterate bounds for standard SGD uniformly over unconstrained smooth convex objectives, a setting where guarantees must remain valid under data-dependent stopping.

    Source: §1 · p. 1

  • Method

    The sufficiency argument uses dyadic epochs and an additive conditional-restart inequality to control terminal positions and allocate confidence across epochs.

    Source: §1.3 · p. 2, §3.2 · p. 4

  • Results

    The achievable overhead profiles are exactly those with a convergent reciprocal-square series over dyadic horizons, and the rate approaches but never reaches the square-root log-over-n order.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The obstruction to attaining the limiting rate already holds for a one-dimensional analytic smooth convex objective with Gaussian noise, so it is not an artifact of high dimension or nonsmoothness.

    Source: §5 · p. 9

    The stated problem class uses the separability convention, restricting spaces to finite-dimensional Euclidean spaces or spaces isomorphic to ℓ2.

    Source: §2 · p. 3

Abstract

from arXiv · show

We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-\alpha$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. \] The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.

1 Introduction

The introduction characterizes exactly which overhead profiles permit time-uniform raw-iterate bounds for standard SGD, and explains why such guarantees matter for data-dependent stopping. It situates the frontier among related results and sketches the sufficiency and necessity arguments.

1 Introduction

  • Time-uniform guarantees remain valid under data-dependent stopping, unlike a fixed-time bound, and the paper studies profiles uniformly over smooth convex problems without dimension dependence.The setting is standard SGD on unconstrained smooth convex objectives with conditionally unbiased norm-sub-Gaussian noise.Source: §1 · p. 1

1.1 Contributions

  • A profile h is achievable exactly when the reciprocal-square series over dyadic horizons converges, yielding rates arbitrarily close to but not reaching the square-root log-over-n order.The criterion applies to arbitrary slowly varying profiles, not only a prescribed logarithmic power.Source: §1.1 · p. 2

1.2 Related works

  • Prior anytime guarantees cited here concern momentum, contractive objectives [15], or projected weighted-suboptimality [16], rather than standard SGD raw iterates on the general smooth convex class.The authors state that the exact overhead frontier for this target setting had not been characterized.Source: §1.2 · p. 2

1.3 Technical overview

  • Sufficiency uses dyadic epochs and an additive conditional-restart inequality to control every terminal position while separating harmonic and confidence costs; necessity combines progress and noise constraints into a recurrence.The necessity argument uses independent Gaussian block events on one-dimensional analytic quartic-flat convex objectives.Source: §1.3 · pp. 2–3

2 Preliminaries

The paper formalizes time-uniform convergence for standard SGD on unconstrained smooth convex objectives under conditionally unbiased norm-sub-Gaussian noise. It characterizes exactly which sub-√n overhead profiles can be achieved by a deterministic schedule independent of horizon, instance, and confidence level.

2 Preliminaries

  • The class comprises standard SGD on unconstrained smooth convex objectives in separable real Hilbert spaces, with bounded initial distance and conditionally unbiased norm-sub-Gaussian noise.The space is finite-dimensional or isomorphic to ℓ2.Source: §2 · p. 3
  • A profile h in H0 is achievable exactly when the reciprocal-square series over dyadic values, sum_j 1/h(2^j)^2, converges.H0 consists of positive, eventually nondecreasing profiles with h(n) = o(√n).Source: §2 · pp. 3–4
  • The achieving schedule is deterministic and independent of the horizon, instance, and confidence level, while the high-probability bound holds simultaneously for all n.The bound constant may depend on the confidence level and problem parameters.Source: §2 · pp. 3–4
  • There is no asymptotically smallest achievable profile; iterated-log examples approach the √(log n/n) rate arbitrarily closely without reaching it.The first logarithmic profile is not achievable, whereas its power 1/2 + ε is achievable for every ε > 0.Source: §2 · p. 4

3 Sufficiency of the reciprocal-square profile

The sufficiency result constructs a horizon-free schedule for every profile satisfying reciprocal-square summability, yielding an all-time high-probability rate of order h(n)/√n. The construction uses dyadic epochs and conditional estimates on blocks of an uninterrupted SGD trajectory.

3 Sufficiency of the reciprocal-square profile

  • Every profile with sum_j 1/h(2^j)^2 < ∞ admits a deterministic schedule whose raw SGD iterates satisfy an O(h(n)/√n) bound simultaneously for all n.The schedule depends on h and problem parameters, not on the horizon, instance, or confidence level.Source: §3 · p. 4

3.1 The horizon-free dyadic schedule

  • The schedule uses constant stepsizes within dyadic epochs and decreases them across epochs; reciprocal-square summability bounds the total squared-step energy.The bounded energy supports control of the entire trajectory within a fixed radius.Source: §3.1 · p. 4

3.2 Core tool: additive conditional restart

  • An analytical restart applies finite-block estimates conditionally from a trajectory-dependent starting point, without resetting the SGD trajectory.The block estimate accommodates a comparator measurable at the block's starting time.Source: §3.2 · p. 4

11 end

The proof combines a global radius event with conditional finite-block bounds along the dyadic schedule to establish uniform control over all times. Using an additive stochastic cost preserves the target rate under a summable confidence allocation.

3.3 Proof of sufficiency

  • Finite total schedule energy confines the infinite trajectory to a fixed ball, enabling the finite-block estimate throughout the run.The proof uses a global high-probability radius bound to make the active stepsizes admissible.Source: §3.3 · p. 5
  • Early terminal positions use the epoch's starting iterate as comparator to avoid the excessive penalty of the 1/r bound; later positions use the minimizer.Adjacent dyadic epochs pass the late-half bound forward to control the next epoch.Source: §3.3 · pp. 5–6
  • The additive stochastic cost vanishes relative to the target profile under the summability condition, whereas multiplicative dependence would lose the frontier.Uniform control of all positions in an epoch uses a summable confidence allocation.Source: §3.3 · p. 6
  • The constructed schedule gives a uniform O(h(n)/√n) bound over the problem class on one event controlling every time.The schedule is independent of the instance and confidence level, and the result applies whenever the reciprocal-square series converges.Source: §3.3 · pp. 5–6

4 Necessity of reciprocal-square summability

The necessity argument derives constraints on any deterministic schedule from fixed-horizon progress and noise, then applies them to one fixed flat objective across dyadic epochs. Together, the epoch bounds force reciprocal-square summability for a time-uniform h(n)/√n boundary.

4 Necessity of reciprocal-square summability

  • Reciprocal-square summability is necessary for any deterministic schedule to attain a time-uniform h(n)/√n boundary.The necessity result allows the schedule to be fixed before the run and independent of the terminal horizon and problem instance.Source: §4 · p. 6

4.1 Fixed-horizon analysis

  • The fixed-horizon noise constraint trades off Q_n against S_n: accommodating larger Q_n requires correspondingly larger S_n for a sufficiently small error bound.This stochastic-energy restriction complements the deterministic-progress requirement for sufficient cumulative stepsize.Source: §4.1 · p. 7

4.2 A fixed flat-active witness and the dyadic epoch ceiling

  • A quartic-flat convex objective and Gaussian noise yield a time-uniform dyadic epoch ceiling through block anti-concentration.When epoch stepsize mass is too large, disjoint blocks require independent Gaussian increments to fall in prescribed small intervals; the argument yields a factor 1/j.Source: §4.2 · pp. 7–8

4.3 Reciprocal-square summability

  • Upper and lower bounds on dyadic quantities combine with a nonlinear lower recurrence for Q_j to connect epoch energy growth to reciprocal-square summability.The recurrence is identified as the mechanism linking dyadic energy growth to the series condition.Source: §4.3 · p. 8

5 Conclusion

The paper characterizes the exact time-uniform overhead frontier for standard SGD on smooth convex objectives. Achievable profiles satisfy reciprocal-square summability, yet there is no asymptotically smallest achievable profile, and the obstruction already holds in a one-dimensional analytic example with Gaussian noise.

5 Conclusion

  • Achievable overhead profiles are exactly those satisfying reciprocal-square summability, and they can approach log n/n arbitrarily closely without attaining it.The achievable class has no asymptotically smallest element.Source: §5 · p. 9
  • The obstruction already holds for a one-dimensional analytic smooth convex objective with Gaussian noise, even when the schedule may depend on confidence.The conclusion identifies the frontier as intrinsic to time-uniform raw-iterate control in the general noncontractive setting.Source: §5 · p. 9

AI use statement

The authors used generative AI to assist with necessity-proof development, Lean 4 formalization, and polishing some writing; they report manually checking the proof arguments and auditing the formalization.

AI use statement

  • GPT-5.6 Sol assisted with necessity-proof strategies and introduction writing, while GPT-6-Astra assisted with Lean 4 formalization that was kernel-checked and independently audited.The authors say they independently checked the AI-assisted necessity arguments and did not use generative AI to generate the sufficiency proof.Source: AI use statement · p. 9

A Deferred proofs from Section 2

The deferred material constructs a strictly smaller achievable overhead profile and supplies geometric and barycentric ingredients for bounding the raw iterate through weighted one-step inequalities.

A Deferred proofs from Section 2

  • Every achievable profile admits another achievable profile that is asymptotically strictly smaller, so the achievable class has no asymptotically smallest element.The deferred construction proves g(n) = o(h(n)).Source: A Deferred proofs from Section 2 · p. 11

B.1.1 Local smooth geometry

  • Lemma B.2 states its setup for one update, x+ = x − η(∇f(x) + ζ), when 0 < η ≤ 1/(2L), and for any reference point z ∈ H.Source: §B.1.1 · p. 12

B.1 Additive conditional restart theorem: proof and supporting lemmas

  • The proof framework bounds global error at an arbitrary comparator by combining single-step errors through a barycentric recursion.The recursion relates reference points to iterates so the weighted single-step errors telescope to the global error.Source: §B.1.2 · pp. 12–13

B.1.2 Terminal weights and barycentric identities

  • Terminal weights and barycentric identities set the linear-combination coefficients so the weighted one-step inequalities telescope to the final iterate’s error.The proof uses nonincreasing weights and the identity a_T = C.Source: §B.1.2 · pp. 12–13

B.1.3 Proof of the additive conditional restart theorem

This proof establishes a high-probability restart bound for constant-stepsize blocks with measurable comparators, then controls the SGD trajectory uniformly in time using supermartingales and calibration.

B.1.3 Proof of the additive conditional restart theorem

  • For a constant-stepsize block, Theorem B.7 gives a high-probability bound for any almost surely finite comparator measurable at the block’s start.The proof obtains it by conditioning on the starting filtration and applying the block estimate.Source: §B.1.3 · p. 16

B.2 Global radius and calibration

  • Two nonnegative supermartingales control accumulated noise energy and stopped directional noise uniformly over time.Ville’s inequality supplies simultaneous bounds; the stopping-time argument then yields D_t ≤ B_β for every t on the calibrated event.Source: §B.2 · pp. 16–18
  • The argument assumes D0 ≤ R²/2, finite Q∞, and stepsizes satisfying 0 ≤ ηt ≤ 1/(2L).Source: §B.2 · p. 16

B.3 Proof of the sufficiency theorem

The sufficiency proof calibrates a dyadic schedule using reciprocal-square summability, applies restart estimates within epochs, and propagates the bounds across epochs and the finite prefix.

B.3 Proof of the sufficiency theorem

  • For every epoch j ≥ j0, stepsizes γj are nonincreasing and satisfy 0 < γj ≤ 1/(2L); they vanish before j0, are constant on later epochs, and have finite total squared-step energy.Source: §B.3 · p. 18
  • Reciprocal-square summability makes the epoch constants bounded independently of the epoch index.The proof uses these constants to control the within-epoch estimates.Source: §B.3 · p. 19
  • Within each epoch, restart estimates bound both the objective increment from the epoch’s starting iterate and the objective gap in its latter half.The latter-half estimate from one epoch initializes the early-half estimate in the next, propagating a single constant across active epochs.Source: §B.3 · pp. 19–20
  • The proof absorbs the finitely many iterates before the epoch estimates take over using a bound from smoothness at the minimizer.The schedule sets stepsizes to zero before the initial active epoch.Source: §B.3 · p. 20

C.1 Fixed-time analysis

This section analyzes a quartic-flat analytic convex objective and transfers fixed-horizon coverage statements to a limiting quadratic recursion. It then uses these constructions to prove fixed-horizon restrictions.

C.1 Fixed-time analysis

  • The flat-active family is real analytic, convex, and smooth, but is neither strongly convex near its minimizer nor PL with any positive constant.Its objective is quartic-flat at the unique minimizer.Source: §C.1 · p. 21
  • For a fixed number of iterations, the quartic-flat recursion converges pathwise to its quadratic limit as a decreases to zero.This convergence transfers marginal coverage inequalities to the limiting quadratic model.Source: §C.1 · pp. 21–22
  • The proof of the fixed-horizon restrictions uses the limiting quadratic recursion under both zero-noise and Gaussian-noise constructions.The section states that these restrictions are proved using the constructed instances.Source: §C.1 · pp. 22–23

C.2 Preliminaries for the fixed Gaussian instance

The necessity proof uses a fixed Gaussian instance that forces stepsizes to vanish, then groups step mass into greedy blocks and applies dyadic sequence estimates.

C.2 Preliminaries for the fixed Gaussian instance

  • The fixed instance is convex, L-smooth, non-PL, and quartic-flat; under the theorem’s assumptions, it forces η_t to converge to zero.Its oracle uses independent Gaussian noise and starts at the minimizer.Source: §C.2 · pp. 23–24

C.3 Greedy step-mass blocks

  • Greedy sub-blocking yields at least 2H_j/(5τ_j) blocks when H_j ≥ 2τ_j, and the block noise sums are independent centered Gaussians.The blocks are formed by accumulating stepsize mass up to a tolerance.Source: §C.3 · p. 25

C.4 Dyadic sequence estimates

  • The passage states that its main focus is proving Lemmas 4.7 and 4.8; in the proof of Lemma 4.7, H_j = S_{N_{j+1}} − S_{N_j}.Source: §C.4 · p. 27
Loading 2609.08537v1…