Pith. sign in

REVIEW 4 major objections 4 minor 25 references

Analysis of Schedule-Free Nonconvex Optimization

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A single Lyapunov potential extends Schedule-Free's horizon-free guarantees to smooth nonconvex optimization, without global Lipschitz assumptions.

desk verdict A clean Lyapunov framework with one new rate (Theorem 5) and one unproven load-bearing assumption (Theorem 4); worth a real referee, but the headline O(log T/T) claim needs a proof or a proper caveat. read the letter →

arxiv 2508.06743 v1 pith:UZBM75V2 submitted 2025-08-08 cs.LG cs.AI

Connor Brown This is my paper
classification cs.LGcs.AI MSC 90C2665K05
keywords schedule-freeoptimizationnonconvexLyapunovframeworkhorizon-freeconvergencePolyak-Ruppertaveragingmomentumperformanceestimationproblemsmooth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to give worst-case convergence guarantees for the Schedule-Free (SF) optimization method in nonconvex settings, dropping the global Lipschitz-gradient and well-behaved assumptions that limited earlier analyses. It claims that one Lyapunov potential reduces SF's analysis to a single-step descent inequality, yielding horizon-agnostic rates: O(1/log T) for the classic constant step with Polyak–Ruppert averaging, O(log T/T) for a linearly growing step, and a continuum of O($T^{{-(1-alpha)}}$) rates for polynomial averaging weights. If sound, this means SF's horizon-free property—no need to know the total training time T—extends to smooth nonconvex problems. The paper also uses Performance Estimation Problem experiments up to T=100 to validate these rates and to suggest that the O(1/log T) bound may be improvable to O(1/T).

What carries the argument

The Lyapunov potential V_t = f(x_t) - f* + A_t||delta_t||^2, where delta_t = z_t - x_t and A_t = c_{t+1}(1 - L eta_t c_{t+1}) / (2 eta_t (1 - c_{t+1})^2). The coefficient A_t is engineered so that, under the step-size constraint L eta_t c_{t+1} <= 1, the potential is non-negative and the bracketed discrepancy term in Lemma 1 is non-positive when beta_t = 1. Telescoping this one-step descent inequality over t yields all the stated rates; the bounded-growth Assumption 2 is what lets the linearly-growing-stepsize regime pass the discrepancy term through the telescope without losing the O(log T/T) rate.

What would settle it

Run the paper's PEP SDP for T beyond 100 steps with eta_t = (t+1)/L and check whether the worst-case ||z_t - x_t||^2 stays below a $D^{2}$(t+1) envelope; if it eventually exceeds that linear bound, Assumption 2 fails and Theorem 4's O(log T/T) rate collapses. Alternatively, a smooth nonconvex function whose min gradient norm decays slower than C/log T would falsify the claim that O(1/log T) is the achievable rate for the constant-step SF regime.

Watch

Extended reading notes

Core claim

The central claim is that for an L-smooth, lower-bounded objective, the Schedule-Free three-sequence update admits a Lyapunov function V_t = f(x_t) - f* + A_t||z_t - x_t||^2, where A_t is chosen from the step size and averaging coefficient so that V_t decreases monotonically in the deterministic setting. Lemma 1 converts the entire convergence analysis into one descent inequality that charges the gradient norm of the slow sequence against the telescoping of V_t. From this, the paper derives horizon-agnostic worst-case rates: O(1/log T) with SF's original constant step and uniform averaging (Theorem 3), O(log T/T) with a linearly growing step under a bounded-growth condition on the z-x discre

Load-bearing premise

The O(log T/T) bound for the linearly growing step size rests on an unproved assumption that the distance between the two iterate sequences stays at most linear in time; the evidence is only finite-horizon numerical experiments up to 100 steps, which the paper itself notes show spikes and a possible upward tail.

Editorial extensions

If this is right

  • With constant step size and uniform averaging (c_{t+1}=1/(t+1), beta=1), SF reaches min gradient norm O(1/log T) on any L-smooth lower-bounded function, with no horizon-dependent hyperparameters.
  • With the linearly growing step eta_t = eta_0(t+1) and Assumption 2, the same guarantee improves to O((V_2/eta_0 + D^2 log T)/T), matching momentum-style rates up to a log factor.
  • Polynomial averaging weights c_{t+1} = (t+1)^{-alpha} interpolate between uniform averaging (alpha=0) and the tail-averaging regime (alpha=1), with rates O(1/T^{1-alpha}) for alpha in [0,1) that collapse to a constant for alpha>1.
  • Increasing averaging weights c_{t+1} = (t/(t+1))^alpha preserve an O(1/T) rate up to a mild logarithm for alpha in [0,1).
  • PEP experiments up to T=100 support the stated rates and suggest the O(1/log T) bound for the constant-step case may actually be O(1/T), meaning the log factor could be an artifact of the proof technique.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the O(1/T) conjecture from the PEP curves holds, SF's constant-step guarantee would become optimal in the deterministic nonconvex sense, eliminating the remaining gap between SF and scheduled momentum at the level of rates.
  • The framework's recommendation to set beta=1 in worst-case analysis implies that any certified robustness of SF to the averaging-versus-momentum tradeoff will require either a different potential or a late-start averaging scheme; the present one-step descent cannot handle beta<1 without weakening the bound.
  • Assumption 2 is the most fragile point in practice: the paper's own numerics show spikes in ||z_t - x_t||^2 under the linear step size, so testing the linear envelope beyond T=100 is a direct way to see whether the O(log T/T) rate extends to realistic horizons.
  • The stochastic extension in the appendix adds only an additive variance term, but it relies on standard bounded-variance assumptions; extending the framework to variance-reduced or adaptive-step variants would require re-deriving the one-step inequality for those updates.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a Lyapunov framework for the Schedule-Free (SF) method in smooth nonconvex optimization. Under L-smoothness and lower boundedness, it claims O(1/log T) for the constant-step regime with ct+1=1/(t+1) and βt=1 (Theorem 3), O(log T/T) for a linearly growing step-size under an additional bounded-growth assumption on ||zt−xt||² (Theorem 4), and a continuum of O(T^{-(1−α)}) rates for polynomial averaging (Theorem 5). The proofs center on Lemma 1, a one-step descent inequality for a potential Vt = f(xt) − f* + At||δt||². PEP experiments up to T=100 are reported as numerical support. The central idea is promising, but several load-bearing proof steps are currently invalid or rely on an unproven trajectory-level assumption; the abstract also overstates the conditions under which the linear-step rate is established.

Significance. If fully corrected, the Lyapunov framework would provide a unified and simple analysis of SF-type methods under minimal assumptions, and the explicit PEP code and honest discussion of limitations are strengths. The O(1/log T) rate for constant step is not new (it is attributed to Liu et al.), but the framework's breadth across averaging schedules is a useful contribution. However, the advertised headline acceleration to O(log T/T) depends on an unproven trajectory assumption, and the current proofs of Theorems 3 and 4 contain invalid telescoping steps. The significance of the paper therefore depends on whether these gaps are fixable; as printed, the central claims are not fully established.

major comments (4)
  1. [§D.1 (Theorem 3)] The telescoping step is invalid. The proof derives S_T · min_{2≤t≤T−1} ||∇f(xt)||² ≤ V2 + (σ²η/2)S_T, where S_T = Σ_{t=2}^{T−1} 1/(t+1). It then replaces S_T by log T on the left, writing (η/4) log T · min ≤ V2 + ... . Since S_T < log T, this is a stronger inequality and does not follow. The correct conclusion, min ≤ 4V2/(η S_T) + 2σ², still yields O(1/log T), so the theorem's rate is salvageable, but the printed proof must be corrected.
  2. [§4.2 / Theorem 4] Theorem 4's O(log T/T) rate rests entirely on Assumption 2, a trajectory-level bound ||δt||² ≤ D²(t+1) that is not proved for the L-smooth lower-bounded nonconvex class. The PEP evidence is finite-horizon (T≤100) and is computed with PEPit's SmoothFunction, which is convex; Section 5 itself notes intermittent spikes and an upward tail in the linear-step plot, and says the O(log T/T) bound 'may not hold uniformly in the true worst case.' The abstract's claim of O(log T/T) 'under only L-smoothness and lower-boundedness' is therefore not supported. This needs to be reframed as conditional on Assumption 2, or Assumption 2 must be proved or replaced by a condition implied by Assumption 1.
  3. [§D.2 (Theorem 4)] Even conditional on Assumption 2, the final telescoping step uses the wrong denominator. The proof sums t=2,...,T−1, so the first term should be 4V2/(η0(T−2)), not 4V2/(η0T). The printed bound is stronger than what the displayed inequality proves. The asymptotic O(1/T) rate is preserved after this correction, but the proof as written is invalid.
  4. [Eq. (4) vs §C.5 (Lemma 1)] The index convention for At is inconsistent between the main text and the proof. Eq. (4) defines At = c_{t+1}(1−Lηt c_{t+1})/(2ηt(1−c_{t+1})²), while in the proof of Lemma 1, At+1 is set to c_{t+1}(1−Lηt c_{t+1})/(2ηt(1−c_{t+1})²) and the final bracket contains c_t-terms. Since Lemma 1 underpins all theorems, the coefficient sequence must be defined consistently and the cancellation step re-verified.
minor comments (4)
  1. [§3.6] The SDP in Eq. (3) lists matrices Ai,j, Bi,j, Ci, Di, but their definitions are incomplete. Also, the PEP code uses SmoothFunction (convex), so claims that the numerics validate nonconvex behavior should be qualified.
  2. [Theorem 5 (increasing c)] The displayed bound writes '+2σ²' inside the denominator: 'ηT − 2η − αη log T + 2σ²'. The proof gives 4V2/(ηS) + 2σ²; the theorem statement should match the proof.
  3. [§D.3 (Theorem 5, decreasing c)] The proof line 'which is always true for t ≥ 2' condenses a nontrivial inequality chain. Please expand it; the current derivation does not make the sufficient condition explicit.
  4. [General presentation] There are typos and rendering artifacts: 'by by Ahn', 'Defazio et al. and and Sebbouh', and figure axes showing 'uni00A0'. These should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Lyapunov descent proof is self-contained; Theorem 4 depends on an explicitly stated, unproven trajectory bound, which is a correctness risk rather than a circular input.

full rationale

The central derivation is self-contained. Lemma 1 establishes a one-step Lyapunov inequality from Assumption 1 (L-smoothness and lower-boundedness) by algebraic manipulation; Theorems 3 and 5 substitute the stated hyperparameter schedules and telescope the resulting inequality. No target rate is inserted as an assumption or fitted parameter, and no theorem is defined in terms of its own conclusion. Theorem 4 is explicitly conditional on Assumption 2, a stated trajectory bound on ||z_t - x_t||^2; the O(log T/T) rate follows by summing the resulting D^2·O(1/(t+1)) terms, so the advertised rate is a mathematical consequence of the assumption, not a renaming of it. The PEP experiments are used only to motivate Assumption 2 and to provide finite-horizon worst-case curves; they do not appear in the proofs, and the paper explicitly disclaims extrapolation beyond T=100 and notes the upward tail and spikes that could indicate the assumption fails. No load-bearing self-citation chain or imported uniqueness theorem is present; Theorem 3's O(1/log T) result is explicitly credited to Liu et al. [14]. The unproven nature of Assumption 2 is a genuine correctness risk for Theorem 4, but it is a gap in support, not a circular derivation.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central framework rests on the standard smoothness/lower-boundedness assumption, one ad hoc bounded-growth assumption for the linear-step rate, and standard algebraic inequalities. No new physical or algorithmic entities are postulated. The only free parameter is the unspecified constant D in Assumption 2.

free parameters (1)
  • D (bounded-growth constant) = unspecified
    Assumption 2 introduces D such that ||z_t - x_t||^2 <= D^2(t+1) for the linear-step theorem. No bound on D is derived, and it appears in the final rate as D^2 log T / T.
assumptions (4)
  • domain assumption The objective f is L-smooth and lower bounded (Assumption 1).
    Standard basis in deterministic nonconvex optimization; invoked throughout the proofs.
  • ad hoc to paper There exists D > 0 such that ||z_t - x_t||^2 <= D^2(t+1) for all t (Assumption 2).
    Used only in Theorem 4; not proven, only supported by finite-horizon PEP numerics.
  • domain assumption Stochastic assumptions: unbiased gradients, independent samples, bounded variance (Assumption 3).
    Standard for stochastic extensions; deterministic results set sigma = 0.
  • standard math Algebraic inequalities used in Theorem 5 proofs, including Bernoulli's inequality and convexity of x^alpha.
    Unproved background results in the polynomial-averaging analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Analysis of Schedule-Free Nonconvex Optimization." pith.science (2026). https://pith.science/paper/UZBM75V2

@misc{pith2026250806743,
  author       = {Pith},
  title        = {Pith review of: Analysis of Schedule-Free Nonconvex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UZBM75V2}},
  note         = {Machine review of arXiv:2508.06743}
}
abstract

First-order methods underpin most large-scale learning algorithms, yet their classical convergence guarantees hinge on carefully scheduled step-sizes that depend on the total horizon $T$, which is rarely known in advance. The Schedule-Free (SF) method promises optimal performance with hyperparameters that are independent of $T$ by interpolating between Polyak--Ruppert averaging and momentum, but nonconvex analysis of SF has been limited or reliant on strong global assumptions. We introduce a robust Lyapunov framework that, under only $L$-smoothness and lower-boundedness, reduces SF analysis to a single-step descent inequality. This yields horizon-agnostic bounds in the nonconvex setting: $O(1/\log T)$ for constant step + PR averaging, $O(\log T/T)$ for a linearly growing step-size, and a continuum of $O(T^{-(1-\alpha)})$ rates for polynomial averaging. We complement these proofs with Performance Estimation Problem (PEP) experiments that numerically validate our rates and suggest that our $O(1/\log T)$ bound on the original nonconvex SF algorithm may tighten to $O(1/T)$. Our work extends SF's horizon-free guarantees to smooth nonconvex optimization and charts future directions for optimal nonconvex rates.

Figures

Figures reproduced from arXiv: 2508.06743 by the authors.

Figure 1
Figure 1. Worst-case ||zt − xt||2 curve for Assumption 2 . 6 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Worst-case bias curve for Theorem 4. 4.3 Constant stepsize with polynomial averaging We generalize the averaging weight to a polynomial decreasing average ct+1 = (t + 1)−α and polynomial increasing average ct+1 = t α/(t + 1)α and keep βt = 1. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Worst-case bias curves for Theorem 5, ct+1 = [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Worst-case bias curves for Theorem 5, ct+1 = [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 20 canonical work pages

  1. [1]

    The Road Less Scheduled

    Aaron Defazio et al. The Road Less Scheduled . Available at https://arxiv.org/abs/ 2405.15682v4. 2024. arXiv: 2405.15682v4 [cs.LG] (1, 4, 10)

    arXiv 2024

  2. [2]

    Performance of First-Order Methods for Convex Optimization

    Yoel Drori and Marc Teboulle. “Performance of First-Order Methods for Convex Optimization”. In: Mathematical Programming 145.1-2 (2014), pp. 451–482 (1, 5, 10)

    work page 2014

  3. [3]

    Robust stochastic approximation approach to stochastic program- ming

    Arkadi Nemirovski et al. “Robust stochastic approximation approach to stochastic program- ming”. In: SIAM Journal on Optimization 19.4 (2009), pp. 1574–1609 (1)

    work page 2009

  4. [4]

    Stochastic first- and zeroth-order methods for nonconvex stochastic programming

    Saeed Ghadimi and Guanghui Lan. “Stochastic first- and zeroth-order methods for nonconvex stochastic programming”. In: SIAM Journal on Optimization 23.4 (2013), pp. 2341–2368 (1, 10)

    work page 2013

  5. [5]

    Stochastic gradient descent for nonconvex learning without variance reduction

    Yingbin Lei, Michael I. Jordan, and Noureddine El Karoui. “Stochastic gradient descent for nonconvex learning without variance reduction”. In: Machine Learning 108.12 (2019), pp. 2313–2338 (1, 10)

    work page 2019

  6. [6]

    New Stochastic Approximation Type Procedures

    Boris T. Polyak. “New Stochastic Approximation Type Procedures”. In: Automation and Remote Control 51.7 (1990). English translation of a Russian paper, pp. 937–946 (1)

    work page 1990

  7. [7]

    Acceleration of Stochastic Approximation by Averaging

    Boris T. Polyak and Anatoli B. Juditsky. “Acceleration of Stochastic Approximation by Averaging”. In: SIAM Journal on Control and Optimization 30.4 (1992), pp. 838–855 (1)

    work page 1992

  8. [8]

    Efficient Estimations from a Slowly Convergent Robbins-Monro Process

    David Ruppert. Efficient Estimations from a Slowly Convergent Robbins-Monro Process . Technical Report. Cornell University, 1988 (1)

    work page 1988

Show all 25 references
  1. [9]

    General framework for online-to- nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization

    Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky. General framework for online-to- nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization. 2024. arXiv: 2411.07061 [cs.LG]. URL: https://arxiv.org/abs/2411.07061 (1, 4, 10)

    2024 arXiv

  2. [10]

    Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning

    Francis Bach and Eric Moulines. “Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning”. In: Advances in Neural Information Processing Systems (NeurIPS) 24 (2011), pp. 451–459 (3)

    2011

  3. [11]

    Making gradient descent optimal for strongly convex stochastic optimization

    Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. “Making gradient descent optimal for strongly convex stochastic optimization”. In: (2012), pp. 249–256 (3)

    2012

  4. [12]

    Optimal Non-Asymptotic Bound of the Ruppert–Polyak Averaging without Strong Convexity

    Sébastien Gadat and Fabien Panloup. “Optimal Non-Asymptotic Bound of the Ruppert–Polyak Averaging without Strong Convexity”. In:Bernoulli 23.3 (2017), pp. 1991–2021 (3)

    2017

  5. [13]

    Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization

    Aaron Defazio. Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization. 2021. arXiv: 2010.00406 [cs.LG]. URL: https: //arxiv.org/abs/2010.00406 (3)

    2021 arXiv

  6. [14]

    Yanli Liu, Yuan Gao, and Wotao Yin.An Improved Analysis of Stochastic Gradient Descent with Momentum. 2020. arXiv: 2007.07989 [math.OC]. URL: https://arxiv.org/abs/ 2007.07989 (3, 6)

    2020 arXiv

  7. [15]

    Global convergence of the Heavy-ball method for convex optimization

    Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the Heavy-ball method for convex optimization. 2014. arXiv: 1412.7457 [math.OC]. URL: https://arxiv.org/abs/1412.7457 (4)

    2014 arXiv

  8. [16]

    Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

    Adrien B. Taylor, Julien M. Hendrickx, and Francis Glineur. “Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization”. In: Mathematical Programming 161.1-2 (2017), pp. 1–33 (5, 10)

    2017

  9. [17]

    Exact Worst-case Performance of First-Order Methods for Smooth Convex Optimization

    Donghwan Kim and Jeffrey A. Fessler. “Exact Worst-case Performance of First-Order Methods for Smooth Convex Optimization”. In: SIAM Journal on Optimization 26.2 (2016), pp. 1142– 1172 (5)

    2016

  10. [18]

    Introductory Lectures on Convex Optimization: A Basic Course

    Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course . Springer, 2013 (5)

    2013

  11. [19]

    Smooth Strongly Convex Interpolation and Exact Worst-case Perfor- mance of First-order Methods

    Adrien B. Taylor et al. “Smooth Strongly Convex Interpolation and Exact Worst-case Perfor- mance of First-order Methods”. In: Mathematical Programming 178.1-2 (2019), pp. 393–418 (5)

    2019

  12. [20]

    Stochastic Performance Esti- mation Problem: Tight Convergence Guarantees for Stochastic Gradient Methods

    Adrien B. Taylor, Julien M. Hendrickx, and Francis Glineur. “Stochastic Performance Esti- mation Problem: Tight Convergence Guarantees for Stochastic Gradient Methods”. In: SIAM Journal on Optimization 31.3 (2021), pp. 2323–2353 (5)

    2021

  13. [21]

    On worst-case analyses for first-order optimization methods

    Adrien Taylor and Baptiste Goujaud. On worst-case analyses for first-order optimization methods. Lecture notes from TraDE-OPT workshop. 2024. URL: https://trade- opt- itn.eu/workshop.html (5). 11

    2024

  14. [22]

    Scaling Laws and Compute-Optimal Training Beyond Fixed Training Durations

    Alexander Hägele et al. Scaling Laws and Compute-Optimal Training Beyond Fixed Training Durations. 2024. arXiv: 2405.18392 [cs.LG] . URL: https://arxiv.org/abs/2405. 18392 (10). 12 A SGD+M and SPA Equivalence Theorem 1. Define the SGD+M method by the two sequences: mt+1 = θtmt...

    2024 arXiv

  15. [23]

    Unbiasedness: At each iteration t, ∇f (xt, ζt) satisfies Eζt ∇f (xt, ζt) = ∇f (xt)

  16. [24]

    Independent samples: The random samples {ζt}∞ t=0 are independent

  17. [25]

    O M P _ N U M _ T H R E A D S

    Bounded variance: The variance of ∇f (xt, ζt) with respect to ζt satisfies Varζt (∇f (xt, ζt) = Eζt ||∇f (xt, ζt) − ∇f (xt)||2 ≤ σ2 for some σ2 ≥ 0. C.2 Claim 1 Claim 1. Define Schedule-Free by the three sequences: yt = (1 − βt)zt + βtxt, zt+1 = zt − ηt∇f (yt, ζt) xt+1 = (1 − ...

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.