cs.LGJul 10, 2026

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

Authors: Jiseok Chae, Donghwan Kim

Abstract

Schedule-Free methods have attracted growing interest for alleviating the burden of designing and tuning a learning rate scheduler, while matching and sometimes even outperforming optimizers with tuned schedulers. Despite their strong empirical results, their convergence theory in nonconvex optimization, where modern machine learning objectives typically arise, has remained largely unexplored. In this paper, we provide worst-case analyses of Schedule-Free gradient descent and Schedule-Free stochastic gradient descent, in their standard form and without auxiliary modifications or restrictive conditions, for smooth but possibly nonconvex objectives. Based on a Lyapunov analysis derived from the continuous-time limiting ordinary differential equation associated with these methods, we show that Schedule-Free gradient descent and Schedule-Free stochastic gradient descent achieve the optimal worst-case convergence rates attainable among first-order methods. We further formulate Schedule-Free gradient descent as a nonautonomous dynamical system and prove strict-saddle avoidance under an arbitrarily small one-time perturbation. These theoretical results provide a better understanding of the strong performance that Schedule-Free methods demonstrate.

Explore similar work

CardsList
Date pendingmath.OC

Silver Rate Is (Almost) Optimal for Gradient Descent

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing psil=log⁡2(1+2)p_{\mathrm{sil}}=\log_2(1+\sqrt{2}), we prove an Ω(n−psil−O(log⁡log⁡n/log⁡n))\Omega\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n−2psil1+psil−O(log⁡log⁡n/log⁡n))\Omega\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right). Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.
Yuhan Ye, Kaizhao Liu
Large Step SizesGradient DescentConvex OptimizationOptimization Convergence AnalysisOptimalOptimal Sample Complexity+1
AskPDF
Aug 11, 2026math.OC

A lower bound for stepsize-based acceleration of gradient descent

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of O(T−1)O(T^{-1}) (where TT denotes the number of iterations) to O(T−log⁡2(1+2))O\big(T^{-\log_2(1+\sqrt{2})}\big) using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical Ω(T−2)Ω(T^{-2}) benchmark for general first-order methods. In this work, we present a new lower bound of Ω(T−1.9319)Ω(T^{-1.9319}) for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal O(T−2)O(T^{-2}) convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
Jianhao Ma, Yuxin Chen
Large Step SizesGradient DescentZeroth-Order OptimizationOptimization Convergence AnalysisLower Bounds
AskPDF
Sep 8, 2026math.OC

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

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 log⁡n/n\sqrt{\log n / n} but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence hh satisfying h(n)=o(n)h(n) = o(\sqrt{n}), a bound of order h(n)/nh(n)/\sqrt{n}, holding simultaneously for all nn with probability at least 1−α1-α and uniformly over the problem class, is achievable if and only if ∑j=1∞1h(2j)2<∞.\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.
Ruijie Li, Kang Chen, Tianyu Wang
Stochastic Gradient DescentOptimization Convergence AnalysisStochasticObjectives
AskPDF