acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 unbiased norm-sub-Gaussian gradient noise, the time-uniform convergence rate gets arbitrarily close to but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence satisfying , a bound of order , holding simultaneously for all with probability at least and uniformly over the problem class, is achievable if and only if 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.

Primary area:
optimization
Keywords:
stochastic gradient descent, stochastic optimization, convex optimization, last-iterate convergence, time-uniform convergence, high-probability bounds, concentration inequalities

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_XXPeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies time-uniform convergence of the raw iterate of standard SGD on smooth convex objectives under conditionally unbiased norm-sub-Gaussian noise. It shows that, for eventually nondecreasing positive profiles h(n)=o(n)h(n)=o(\sqrt n), an O(h(n)/n)O(h(n)/\sqrt n) high-probability guarantee, uniform over the stated problem class, is achievable by a deterministic horizon-free schedule if and only if ∑jh(2j)−2<∞\sum_j h(2^j)^{-2}<\infty. The upper bound uses a dyadic schedule and an additive conditional-restart inequality. The lower bound combines fixed-time restrictions with a one-dimensional smooth convex objective under Gaussian noise.

Critical strengths

The paper provides matching upper and lower bounds within its stated setting. For eventually nondecreasing profiles h(n)=o(n)h(n)=o(\sqrt n), the reciprocal-square criterion identifies which time-uniform rates are achievable by deterministic horizon-free SGD schedules. The necessity result applies beyond the specific dyadic construction used for the upper bound.

Critical weaknesses
  1. The parameter requirements and restriction to deterministic schedules limit the scope of the result. Algorithm 1 uses L,R,σL,R,\sigma as inputs, whereas the relevant SGDM schedules in [Feng et al. (2023), Theorem 5] (https://arxiv.org/html/2310.19598) and [Feng et al. (2025), Proposition 1] (https://arxiv.org/html/2506.23335) do not require RR or σ\sigma as inputs. The frontier also concerns only schedules fixed before the run. In comparison, [Aolaritei and Jordan (2025), Assumption 1.1] (https://arxiv.org/html/2512.13123) allow predictable, data-dependent stepsizes. Their convex results concern weighted-average suboptimality certificates for projected SGD, so they do not establish the same raw-iterate guarantee. Nevertheless, the algorithm class covered by this paper is narrower in its treatment of stepsizes, and its lower bound leaves adaptive and randomized schedules unresolved. These restrictions limit the broader implications of the exact characterization.
  2. I am not convinced that the additional precision amounts to a sufficiently significant theoretical advance. Existing SGDM results already reach the near-critical logarithmic-power scale. This paper establishes that scale for standard SGD and precisely classifies the remaining overhead profiles. That is mathematically interesting, but much of the additional sharpness concerns logarithmic and iterated-logarithmic distinctions. The paper does not establish further consequences that make this exact classification important beyond completing the rate characterization.
  3. The notation and proof organization need improvement. The notation is cluttered, and the argument is difficult to follow in places. I suggest consolidating the notation and organizing the proofs into a simpler structure, with clearer explanations of how the lemmas connect.
Questions for authors
  1. Implications for SGD: What guidance do the results offer for SGD parameter selection or practical applications? For example, can the characterization help choose a stepsize schedule for a finite computation budget?

  2. Profile assumption: What motivates requiring h(n)h(n) to be eventually nondecreasing, rather than requiring the error boundary h(n)/nh(n)/\sqrt n to be eventually nonincreasing? How much of the characterization depends on this choice?

7 comments
AuthorsOpenReview ↗

Response to W1

We thank the reviewer for raising this. Mathematically, it is not hard to remove the dependence on RR and σ\sigma.

In the revised manuscript, we show that the entire characterized rate frontier can be achieved without requiring prior knowledge of RR or σ\sigma. Below we sketch how to make this argument.

For an admissible profile hh, let Nj=2jN_j = 2^j, hj=h(Nj)h_j = h(N_j), and retain the normalization constant from Algorithm 1. Define j0:=inf⁡{j≥Jh:hj≥1},γ~j:=12LchNjhj,j≥j0.j_0 := \inf \{ j \geq J_h: h_j \geq 1 \}, \quad \widetilde{\gamma}_j := \frac{1}{2 L c_h \sqrt{N_j} h_j}, \quad j \geq j_0.

The resulting schedule does not depend on RR or σ\sigma and yields the same O(h(n)/n)O(h(n) / \sqrt{n}) time-uniform guarantee. The core reason that the dependence on RR and σ\sigma can be removed is that the global radius control in Lemma B.8 relies only on two conditions: (i) sup⁡ηt≤(2L)−1\sup \eta_t \leq (2L)^{-1}; (ii) ∑tηt2<∞\sum_t \eta_t^2 < \infty. Consequently, the original schedule can be replaced by an R,σR, \sigma-independent one without affecting the radius-control argument.

Beyond addressing the reviewer's concern regarding parameter requirements, this modification strengthens our main theoretical result (Theorem 2.3). In the revised version, we strengthen this statement by showing that a single schedule depending only on h,Lh,L suffices simultaneously for all R,σ>0R,\sigma>0. The necessity direction remains unchanged. Our original lower bound allows arbitrary deterministic schedules to depend even on R,σR,\sigma and the confidence level α\alpha. It therefore continues to apply to this more restricted class of parameter-independent schedules.

Regarding the comparison with [Aolaritei and Jordan (2025)], their Assumption 1.1 indeed allows predictable, data-dependent stepsizes. However, their convex results concern weighted-average suboptimality certificates for \emph{projected} SGD, whereas our result concerns raw-iterate time-uniform guarantees without any projection needed. We emphasize that our necessity result is restricted to deterministic schedules fixed before the run. We have clarified this scope.

Very importantly, neither Feng et al. (2023, 2025) nor Aolaritei and Jordan (2025) establish time-uniform lower bound characterizations. To the best our knowledge, we are the first one to prove this time-uniform lower bound, and match it with the vanilla SGD (without prejection or other modifications).

AuthorsOpenReview ↗

Response to W2

We thank the reviewer for raising this question.

We would like to clarify that our contribution is not merely to establish a similar rate for vanilla SGD, but to characterize the entire class of achievable time-uniform rates for its raw iterates under deterministic horizon-free schedules.

The significance of this exact characterization goes beyond distinguishing logarithmic and iterated-logarithmic factors, for three reasons.

First, the characterization identifies a sharp attainability boundary. The reciprocal-square criterion distinguishes achievable rates from fundamentally unattainable ones. For example, h(n)=log⁡nh(n)=\sqrt{\log n} is not achievable, whereas h(n)=(log⁡n)(1+ε)/2h(n)=(\log n)^{(1+\varepsilon)/2} is achievable for every ε>0\varepsilon>0. The same distinction persists at finer iterated-logarithmic scales. These are not merely different upper bounds: the necessity result establishes that no deterministic horizon-free schedule can attain a profile outside this boundary.

Second, Corollary 2.4 reveals that the set of achievable profiles has no asymptotically smallest element. Specifically, for every achievable profile hh, there exists another achievable profile g=o(h)g=o(h). Thus, in the setup of minimizing a smooth convex objective under zero-mean sub-Gaussian noise, there is no asymptotically fastest deterministic horizon-free convergence rate. This provides a structural explanation for why characterizing the entire achievable profile class is more informative than identifying a particular logarithmic-power rate.

Third, our necessity proof reveals the mechanisms underlying this boundary. It identifies a fundamental tension between the cumulative stepsize required for deterministic optimization progress and the squared-stepsize energy needed to control stochastic excursions. By coupling these requirements across dyadic epochs through a one-dimensional smooth convex construction with Gaussian noise, we derive the reciprocal-square summability criterion.

Taken together, these results show that our contribution goes beyond establishing a near-critical convergence rate for vanilla SGD. Theorem 2.3 identifies the exact boundary between achievable and unachievable time-uniform rates, Corollary 2.4 reveals that the achievable class has no asymptotically smallest element, and Theorem 4.1 explains the fundamental optimization–noise tradeoff underlying this boundary. Thus, the logarithmic and iterated-logarithmic distinctions are not merely refinements of existing rate bounds; they are concrete manifestations of the exact attainability structure.

AuthorsOpenReview ↗

Response to W3

We thank the reviewer for raising this. We have streamlined several mathematical notations throughout the manuscript and clarified the organization of the sufficiency proof.

In particular, the sufficiency argument is organized around three main steps: (i) establishing a global radius bound using the finite squared-stepsize energy of the schedule; (ii) controlling all terminal positions within each dyadic epoch through the conditional restart inequality, using two different comparators for the early and late portions of each epoch; and (iii) propagating these bounds across adjacent epochs and combining the corresponding events through a summable confidence allocation.

The necessity proof retains its original technical development. Its main argument can be understood in the following sequence. First, the fixed-time analysis (Lemmas 4.3–4.5) establishes two constraints on the stepsize schedule: the cumulative stepsize must be sufficiently large to ensure optimization progress, while the accumulated squared stepsize must remain controlled to limit stochastic fluctuations. Next, we construct a one-dimensional quartic-flat convex objective with Gaussian noise. Under the assumed time-uniform guarantee, the iterates must remain in a shrinking neighborhood of the minimizer throughout the run. Since the objective is particularly flat near its minimizer, the deterministic gradient drift is weak there. Gaussian anti-concentration then yields an upper bound on the cumulative stepsize within each dyadic epoch (Lemma 4.6). Combining this epoch-wise bound with the fixed-time constraints gives upper bounds on the cumulative stepsize and squared-stepsize energy, together with a nonlinear lower recurrence for the latter (Lemmas 4.7–4.8). Finally, this recurrence implies the reciprocal-square summability condition, establishing the necessity direction of Theorem 2.3.

Reviewer_bVDDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper characterizes the time-uniform convergence of plain SGD with a deterministic, horizon-free step-size schedule for unconstrained LL-smooth convex objectives over a Hilbert space. The initial distance to the minimizer set is bounded by RR, and the gradient noise is conditionally unbiased and norm-sub-Gaussian with parameter σ\sigma. Achievable time-uniform rates can approach log⁡n/n\sqrt{\log n/n} arbitrarily closely, but this rate itself is unattainable over the stated problem class.

Critical strengths
  1. The authors provide a sharp theoretical characterization. The paper provides a clear, well-posed if-and-only-if characterization of achievable time-uniform convergence rates for raw-iterate SGD on smooth convex objectives.

  2. Transparent AI-use disclosure: The detailed AI-use statement clearly describes the role of generative AI and the authors’ verification procedures, supporting transparency and accountability.

Critical weaknesses
  1. This reviewer is concerned about limited practical scope. The paper studies plain SGD on smooth convex objectives, limiting its direct relevance to modern optimization methods such as momentum, Adam, Adagrad, and variance-reduced methods such as SVRG or SARAH.

  2. Unclear coverage of the formal verification: Validation consists of mathematical proofs, supplemented by a reported Lean 4 formalization and correspondence audits. For the AI-assisted necessity proof, the authors should identify which Lean declarations cover Lemmas 4.6–4.8 and C.4–C.8, distinguishing kernel-checked results from unformalized arguments or assumed statements.

  3. No empirical connection to the stopping-rule motivation is presented. The paper provides no experiments or simulations demonstrating how its guarantees support practical data-dependent stopping. This leaves the practical implications of the theoretical result insufficiently illustrated.

Questions for authors
  1. Does Theorem 4.1 extend to SGDM or other momentum methods with deterministic parameters?

  2. In Line 36, what is the role of ξt\xi_t?

  3. Where Lipschitz constant is used in the proof?

8 comments
AuthorsOpenReview ↗

Response to W1

We thank the reviewer for raising this concern. Our focus on standard SGD is deliberate: by restricting the algorithmic setting, we aim to obtain a precise understanding of the fundamental time-uniform convergence limitations of the standard SGD recursion.

Despite its simplicity, this setting exhibits a rich mathematical structure, including an exact characterization of achievable rate profiles, the absence of an asymptotically smallest achievable rate, and a matching impossibility result that holds even for a one-dimensional analytic smooth convex objective with Gaussian noise. These findings provide a theoretical baseline for investigating how additional algorithmic mechanisms affect time-uniform convergence.

Extending this analysis to momentum, adaptive optimization, and variance-reduced methods is an important direction for future work. We will clarify this perspective and better discuss the broader implications and scope of our results in the revised manuscript.

AuthorsOpenReview ↗

Response to W2

We thank the reviewer for pointing out that the formal-verification coverage was insufficiently explicit. All eight cited lemmas (Lemmas 4.6–4.8 and C.4–C.8) are covered by kernel-checked Lean proofs. The corresponding proved declarations are listed below.

Paper resultLean declarations
Lemma 4.6epochCeiling_proved
Lemma 4.7stepUpperBound_proved
Lemma 4.8energyAmplification_proved
Lemma C.4fixedWitnessGeometry_proved, fixedWitnessDerivative_proved
Lemma C.5diminishingSteps_proved
Lemma C.6toleranceBound_proved
Lemma C.7greedyMassPartition_exists, subBlockAlgebra_proved
Lemma C.8blockNoise_proved, epoch_block_average_bound

For Lemma C.7, greedyMassPartition_exists constructs the partition used in subBlockAlgebra_proved. For Lemma C.8, blockNoise_proved establishes the independent Gaussian block laws, variance lower bounds, and success-event inclusion, while epoch_block_average_bound proves the averaged inverse-variance inequality with the stated constant. Both results contribute to the proof of the epoch ceiling. The final necessity theorem is established by TimeUniformSGD.necessity_proved.

All production declarations have been checked by Lean's kernel and passed transitive axiom auditing, which reports only the standard logical axioms propext, Classical.choice, and Quot.sound. The AI-assisted necessity arguments were formalized as Lean proof terms and independently checked by the kernel. The correspondence between the formalized model and the manuscript assumptions is documented in docs/ModelCorrespondenceAudit.md. For instance, the proof of Lemma 4.7 uses the proved auxiliary result geometric_harmonic_barrier.

The complete formalization and verification suite is available in the supplementary material and can be reproduced using python scripts/verify_artifact.py. We have revised the Reproducibility Statement to identify the Lean declarations corresponding to Lemmas 4.6–4.8 and C.4–C.8, distinguishing kernel-checked results from unformalized arguments or assumed statements.

AuthorsOpenReview ↗

Response to W3

We thank the reviewer for pointing this out.

The main contribution is an exact theoretical characterization rather than a new empirical optimization algorithm. The purpose of the time-uniform guarantee is to provide a valid convergence certificate at every iteration, including iterations selected through data-dependent stopping rules.

We have strengthened the discussion of this implication and clarified that the guarantee concerns the actual raw iterate, without requiring knowledge of the eventual stopping iteration.

SGD has been the subject of extensive empirical investigation. Nevertheless, as the reviewer points out, systematic empirical assessment of time-uniform convergence behavior of SGD is a promising direction for future research.

Reviewer_rfuMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper is focused on a less conventional type of convergence analysis, referred to as the "time-uniform convergence of the raw iterates", for the vanilla stochastic gradient descent (SGD) method. Similar (and seemingly sharper) results for Momentum-based variations of SGD have been previously obtained, under strongly convex assumption, and/or on average iterate algorithm outputs. This current work extends the analysis beyond those requirements.

Critical strengths
  • Time-uniform convergence of the raw iterates for vanilla SGD seems to have not been previously established
  • The proofs seem to be rigorous and correct
Critical weaknesses

W1. Discussions on the implications of the theoretical results are often opaque and inadequate.

W2. The results involve implicit characterizations (such as the presence of h in the convergence results), while in contrast the literature (in various similar settings) seems to have provided more explicit rates.

Questions for authors

Q1. Can the authors thoroughly justify the significance of time-uniform convergence of the raw iterates for vanilla SGD in contrast to similar results in related but different settings? Can they also justify the use of the results beyond data-dependent stopping?

Q2. Can the authors present explicit constructions of h in the theorems instead?

Q3. Can the authors explain the implications and insights for every theoretical results. In particular, can the authors explain the significance of Part (ii) of Theorem 2.3.

Q4. Can the authors carefully examine/audit the presentation of all theoretical results -- to remove unnecessary statements (e.g., Line 190--191) from theorem statements, to avoid unnecessary interim notations (e.g., the use of \Delta_t and as such), to avoid switching between t and k in denoting iteration counts, and to replace non-standard terms like "overhead profile” and “analytical restart”?

Q5. Can the authors better correspond the informal theorems with formal counterparts? E.g., is Theorem 2.3 a formal statement of Theorem 1.1?

9 comments
AuthorsOpenReview ↗

Response to W1

We thank the reviewer for this comment. We would like to highlight three important implications.

First, our results quantify the intrinsic cost of requiring time-uniform convergence for the raw SGD iterate. Unlike fixed-time guarantees, time-uniform guarantees remain valid under arbitrary almost surely finite data-dependent stopping times. Theorem 2.3 precisely characterizes the unavoidable rate overhead imposed by this requirement.

Second, our necessity result establishes the same impossibility even for a one-dimensional analytic smooth convex objective with Gaussian noise, and even when the stepsize schedule is allowed to depend on the confidence level. This demonstrates that the rate limitation persists under particularly simple problem instances.

Third, Corollary 2.4 reveals that there is no explicit asymptotically smallest achievable rate. Although achievable rates can approach the limiting order of O(log⁡n/n)\mathcal{O}(\sqrt{\log n/n}) arbitrarily closely, this boundary itself remains unattainable.

We will expand the discussion in the Introduction and Conclusion to better articulate these implications, particularly the intrinsic cost of time-uniform raw-iterate guarantees and the significance of the matching impossibility result.

AuthorsOpenReview ↗

Response to W2

We thank the reviewer for this comment. Although a single explicit rate can be more immediately interpretable, the use of a general profile hh is necessary: there is no asymptotically smallest achievable rate that can be written out explicitly.

Specifically, Theorem 1.1 provides an exact if-and-only-if characterization: a rate of O(h(n)/n)\mathcal{O}(h(n)/\sqrt{n}) is achievable if and only if ∑j=1∞h(2j)−2<∞\sum_{j=1}^{\infty} h(2^j)^{-2} < \infty. Corollary 2.4 further proves that no single explicit rate can represent the optimal time-uniform convergence rate: actually, for every achievable hh, there exists an achievable profile g(n)=o(h(n))g(n) = o(h(n)). Any particular explicit rate would capture only a single point in the achievable-rate frontier, while our result characterizes the entire frontier together with its matching impossibility boundary. For some concrete examples of particular achievable hh-s, please refer to our response to Q2.

AuthorsOpenReview ↗

Response to Q1

We thank the reviewer for raising this important question. The importance of time-uniform convergence cannot be overstated.

The core difference separating time-uniform bounds from last-iterate (or fixed-iterate) guarantees is that a time-uniform bound yields a single high-probability event under which the raw SGD iterates obey the convergence bound uniformly across all iterations. P(f(xn)−f∗≤bα(n), ∀n≥1)≥1−α.\mathbb{P}\left(f(x_n)-f^*\leq b_\alpha(n),\ \forall n\geq 1\right)\geq 1-\alpha. This is fundamentally different from a collection of fixed-time guarantees, each of which is valid only at one iteration.

In particular, the time-uniform guarantee immediately implies validity at any almost surely finite stopping time τ\tau adapted to the algorithm's filtration: P(f(xτ)−f∗≤bα(τ))≥1−α.\mathbb{P}\left(f(x_\tau)-f^*\leq b_\alpha(\tau)\right)\geq 1-\alpha.

Beyond data-dependent stopping, this property is useful for anytime monitoring of optimization progress, online decision-making, and computational environments in which the available computation budget is not known in advance. It allows practitioners to inspect the current raw iterate and terminate the algorithm based on observed progress without having to derive a new fixed-time guarantee for each possible termination iteration.

We will expand the Introduction and Related Work to clarify these distinctions and the corresponding scope of our contribution.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions

We have uploaded a revised manuscript incorporating the following changes:

  1. Strengthened main theorem (Theorem 2.3): We establish that the exact rate frontier remains achievable by a stepsize schedule depending only on hh and LL, without requiring prior knowledge of RR or σ\sigma.

  2. Revised stepsize construction and sufficiency proof (Algorithm 1, Theorem 3.4, and Appendix B): We provide the parameter-independent construction and the corresponding proof.

  3. Improved notation and proof presentation: We have simplified several notations and clarified the organization of the sufficiency proof.

  4. Additional clarifications: We have refined the explanations of the theoretical results and their assumptions in response to the reviewers' questions.

  5. Updated Lean 4 formalization and reproducibility statement: We have updated the formalization in our supplementary material to cover the strengthened main theorem and the revised sufficiency result, with the corresponding declarations verified by the Lean kernel. We also expanded the reproducibility statement in the paper to clarify the scope of formal verification, the correspondence between mathematical statements and Lean declarations, and the verification procedures.

The corresponding changes can be found in the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.