acceptodds
Under review as a conference paper at ICLR 2027

Understanding Implicit Averaging in Schedule-Free Stochastic Gradient Descent

Abstract

Schedule-Free SGD (SF-SGD) eliminates the need for predefined learning-rate schedules by combining momentum updates with implicit averaging. A distinctive feature of SF-SGD is that it generates two iterates: the gradient-location point , where the stochastic gradient is evaluated, and the evaluation point , which implicitly aggregates information from past gradient-location iterates. Despite the practical importance of this averaging mechanism, its effect on the relationship between these two points remains insufficiently understood. We study SF-SGD under nonconvex objectives with constant averaging and establish convergence guarantees for both and , together with an upper bound on their gradient-norm gap. In particular, we show that the upper bound at can be smaller than that at , providing theoretical evidence that implicit weighted averaging can improve the stationarity of the evaluation point. We also derive sufficient conditions characterizing the admissible ranges of the learning rate, momentum parameter, and averaging coefficient and extend our analysis to mini-batch stochastic gradients without assuming bounded gradients. Numerical experiments show that constant averaging can outperform uniform averaging in terms of gradient norms, gradient-norm gaps, and test accuracy while being more robust to the momentum parameter. We also observe advantages of increasing over fixed batch sizes under both matched training-sample budgets and equal numbers of optimization steps. The code is available at https://anonymous.4open.science/r/schedule_free_convergence-CBAD, which also includes additional experimental results.

Primary area:
optimization
Keywords:
Schedule-Free SGD, Exponential Weight Averaging

Reviews

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

This papers studies the "Schedule-Free Stochastic Gradient Descent" algorithm, introduced by Defazio et al. in 2024. It studies the convergence to a critical point in expectation in the LL-smooth and bounded variance case, focusing on the constant averaging coefficient ct=cc_t = c. Compared with previous works, there is a lower bound ε\varepsilon on the admissible value of cc, and there is an emphasize on the different results we can obtain on the sequences xtx_t and yty_t.

Critical strengths

None

Critical weaknesses
  • The contribution appears to be limited, there is only one convergence result in the LL-smooth regime. Critically, the paper argues a better upper bound for the gradient norm of xtx_t compared with yty_t, from which the authors deduce some theoretical implications. Nonetheless, the bound for yty_t is deduced from the one of xtx_t, using a formula of the form 2⟨x,y⟩≤∣∣x∣∣2+∣∣y∣∣22\langle x,y \rangle \le \vert \vert x \vert \vert^2 + \vert \vert y \vert \vert^2. It is thus trivial the the upper bound for yty_t is less favorable, and does not show that it is inherently worse.
  • I think the writing could be significantly improved. There are several repetitions, for instance on the first page "In addition to the original choice ct=1/(t+1)c_t = 1/(t+1) of Defazio et al.[...] ct=1/(t+1)c_t = 1/(t+1) is the original choice of Defazio et al. [...]", or on page 2 "since the stochastic gradient is evaluated at yty_t [...] whereas yty_t is the current point where the stochastic gradient is evaluated". It is sometimes somewhat imprecise too. For instance, on page 4 "this condition is satisfied by taking ℓ\ell as the cross entropy loss", I do not think that "condition" is the right term, and some lines below "Note that ξt\xi_t is independent of a {xk}k=0t\{ x_k\}_{k=0}^t generated by SF-SGD", it is an assumption, not something that should be noted. Overall I believe the writing is below the ICLR standards.
  • It is hidden in the bigO notation a factor 1/ε1/\varepsilon, which is not negligible for small value of ε\varepsilon.
Questions for authors

Please see my remarks in the weakness section.

Reviewer_njQsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The draft studies Schedule-Free SGD with a constant averaging coefficient, focusing on the evaluation point xtx_t and the gradient-location point yty_t. Under smooth nonconvex objectives and unbiased stochastic gradients with bounded variance, the authors use a Lyapunov function to derive stationarity bounds for both sequences and a bound on their gradient difference. They also give sufficient parameter conditions and interpret xtx_t as an exponentially weighted average of past gradient-location points. Experiments on CIFAR-100 and ImageNet compare constant and uniform averaging, different momentum parameters, and fixed or increasing batch sizes.

Critical strengths
  1. The authors study both xtx_t, which is used for evaluation, and yty_t, where gradients are computed. They analyze the convergence of both points without assuming bounded gradients.
  2. The authors compare constant and uniform averaging on CIFAR-100 and ImageNet. They report both gradient norms and test accuracy, and also compare different batch-size choices using the same number of training samples.
Critical weaknesses
  1. Regarding Proposition 1: take L=8/5L = 8/5, ϵ=1/100\epsilon = 1/100, β=0\beta = 0, c=1/99c = 1/99, and η=1/690\eta = 1/690. These values satisfy ϵ<c<1\epsilon < c < 1 and 0<η<δ=1/6800 < \eta < \delta = 1/680. However, R(c,η,β)=16609335522863500>0R(c,\eta,\beta) = \frac{1660933}{5522863500} > 0, while the proposition claims R<0R < 0. Please check the step-size condition and its use in the proof of Theorem 1. The convergence bound may still be correct, but this step needs to be fixed.

  2. In Theorem 1, the minimum gradient gap includes t=0t = 0. Since x0=z0x_0 = z_0 gives y0=x0y_0 = x_0, this minimum is always zero. It therefore does not show how the gap changes during training. Could the authors instead state a bound on the average gap? Also, a smaller upper bound does not show that xtx_t has a smaller gradient norm than yty_t. At β=1\beta = 1, the two points are identical, but the bounds still differ by a factor of two. Appendix A.6 notes this, but the main text should make this limit clear.

Correct me if I am wrong about the above two points.

  1. The empirical comparison could be stronger. All experiments fix the learning rate at 0.1, and Table 2 uses beta=0.9, while the 50,000-step sensitivity study in Figure 2 finds that Uniform performs best at beta=0.8. It is unclear how much of the gain remains after tuning both methods. Please compare them using the same tuning budget and training-sample budget.
Questions for authors

Please see Weaknesses above.

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

The paper analyzes schedule-free SGD with a constant averaging coefficient, separating the evaluation iterate xtx_t from the gradient-location iterate yty_t. Under smoothness and bounded noise variance assumptions, it derives a Lyapunov descent inequality and stationarity bounds for both iterates, together with a condition on the step size and momentum. Experiments compare constant and uniform averaging on CIFAR-100 and ImageNet. The gradient-gap bound in Theorem 1 is vacuous as stated, and the comparison of two bounds does not show that averaging helps.

Critical strengths
  1. Separating the two iterates is a practical issue, and analyzing both at once is the right target.
  2. No bounded-gradient assumption, which is weaker than the bounded-gradient condition usually needed to control the separation.
Critical weaknesses
  1. Theorem 1 defines G2(xT,yT)=min⁡0≤t<TE∥∇f(xt)−∇f(yt)∥2G^2(x_T,y_T)=\min_{0\le t<T}\mathbb E\|\nabla f(x_t)-\nabla f(y_t)\|^2. Algorithm 1 initializes x0=z0x_0=z_0, which implies y0=x0y_0=x_0. Hence G2(xT,yT)=0G^2(x_T,y_T)=0 for every T≥1T\ge1, regardless of subsequent behavior. The stated bound is therefore trivially satisfied and provides no information. Specifically, it does not support the statement on page 6 that the gap decreases with the number of iterations.
  2. The two bounds do not order the errors. Theorem 1 gives BTB_T for xtx_t and 2BT2B_T for yty_t. At β=1\beta=1, the iterates coincide and the bounds still differ by two, so the smaller bound cannot be read as evidence that averaging helps.
  3. The experiments measure a different quantity. Figures 1-4 plot the running minimum of ∣∥∇f(xt)∥−∥∇f(yt)∥∣\bigl|\|\nabla f(x_t)\| - \|\nabla f(y_t)\|\bigr|, not the norm of the vector difference, and opposite gradients have equal norms. The squared vector discrepancy would be the right quantity to report.
Questions for authors
  1. Can the gap statement be an average or tail statement?
  2. Can the experiments measure the same vector quantity?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.