- 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 , an high-probability guarantee, uniform over the stated problem class, is achievable by a deterministic horizon-free schedule if and only if . 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 , 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
- The parameter requirements and restriction to deterministic schedules limit the scope of the result. Algorithm 1 uses 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 or 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.
- 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.
- 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
-
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?
-
Profile assumption: What motivates requiring to be eventually nondecreasing, rather than requiring the error boundary to be eventually nonincreasing? How much of the characterization depends on this choice?
7 comments
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, is not achievable, whereas is achievable for every . 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 , there exists another achievable profile . 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.
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.
Response to W1
We thank the reviewer for raising this. Mathematically, it is not hard to remove the dependence on R and σ.
In the revised manuscript, we show that the entire characterized rate frontier can be achieved without requiring prior knowledge of R or σ. Below we sketch how to make this argument.
For an admissible profile h, let Nj=2j, hj=h(Nj), and retain the normalization constant from Algorithm 1. Define j0:=inf{j≥Jh:hj≥1},γj:=2LchNjhj1,j≥j0.
The resulting schedule does not depend on R or σ and yields the same O(h(n)/n) time-uniform guarantee. The core reason that the dependence on R and σ can be removed is that the global radius control in Lemma B.8 relies only on two conditions: (i) supηt≤(2L)−1; (ii) ∑tηt2<∞. Consequently, the original schedule can be replaced by an R,σ-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,L suffices simultaneously for all R,σ>0. The necessity direction remains unchanged. Our original lower bound allows arbitrary deterministic schedules to depend even on R,σ and the confidence level α. 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).