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

Jul 16, 2026

Upload by Quinn

Schedule-Free methods are designed to reduce the effort of engineering and tuning learning-rate schedulers while retaining, or even improving upon, the performance of optimizers paired with tuned schedules. Existing results were mainly empirical; rigorous nonconvex convergence theory was largely missing. This paper proves worst-case rate guarantees for Schedule-Free gradient descent and Schedule-Free stochastic gradient descent on smooth, possibly nonconvex objectives using a Lyapunov analysis from the associated continuous-time ODE, and establishes strict-saddle avoidance via an arbitrarily small one-time perturbation.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages51

Reading Time2 h 9 min

Introduction

Our Contributions

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles Jiseok Chae Natural Science Research Institute KAIST Daejeon, Republic of Korea [jsch@kaist.ac.kr](jsch@kaist.ac.kr) Donghwan Kim Department of Mathematical Sciences KAIST Daejeon, Republic of Korea [donghwankim@kaist.ac.kr](donghwankim@kaist.ac.kr) arXiv :2607 .09 167v 1 [ cs .LG] 10 Jul 2026 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. 1 Introduction There are many first-order methods that can be used to solve a minimization problem min f (x), (1) x∈Rd ranging from the established gradient descent (GD) and stochastic gradient descent (SGD) methods to those that are now standard in the machine learning community, such as Adam [17] and AdamW [20] . In modern machine learning tasks, such first-order methods are typically used together with a learning rate scheduler, which changes the learning rate during training according to a predefined rule. However, as training dynamics are largely unpredictable a priori, the choice and design of the learning rate scheduler have traditionally relied heavily on ad hoc approaches and heuristics. Schedule-Free [9] is an optimization scheme that aims to eliminate the need for handcrafted learning rate schedules, which are often difficult to design and tune. The update rule of the Schedule-Free method, which combines the techniques of iterate averaging and a momentum-like interpolation with a given base optimizer, is defined as yk = (1 − β)zk + βxk (2a) zk+1 = zk − γkgk (2b) xk+1 = (1 − ck+1)xk + ck+1zk+1 (2c) Preprint. with initial points x0 = z0 , where β ∈ [0 , 1] is a fixed constant, {γk }k≥0 is the sequence of learning rates which is often set to be a constant sequence, {ck+1}k≥0 is a predefined sequence of averaging rates such that ck+1 ∈ [0 , 1], and gk is the update direction produced by the base optimizer at yk. For example, Schedule-Free stochastic gradient descent (SF-SGD) uses gk = ∇f(yk ,ζk) for some random variable ζk accounting for the stochasticity in the gradient evaluation, as in standard SGD. A notable interpretation of the Schedule-Free scheme is to understand it as an interpolation between two well-known averaging schemes. When β = 0, under the standard choice ck+1 = k1 , Schedule-Free reduces to Polyak–Ruppert averaging [27, 28], where xk becomes the uniform average over the computed iterates y0 , . . . , yk. On the other extreme, when β = 1, Schedule-Free reduces to a scheme known as primal averaging [24, 31] . Despite this connection, β = 1 is seldom used in Schedule-Free methods. A few common choices for β in practice are 0.9 and 0.98, following the original experiments conducted by Defazio et al. [9] . In this paper, as the case β = 1

FAQs

What problem do Schedule-Free methods target in optimization?

They aim to eliminate the need for handcrafted learning-rate schedulers by using an update rule that combines iterate averaging with a momentum-like interpolation applied to a base optimizer.

What theoretical results are provided for Schedule-Free methods in nonconvex optimization?

The paper gives worst-case analyses for Schedule-Free gradient descent and Schedule-Free stochastic gradient descent, proving optimal attainable convergence rates for first-order methods on smooth, possibly nonconvex objectives.

How does the paper handle saddle points for Schedule-Free gradient descent dynamics?

It formulates Schedule-Free gradient descent as a nonautonomous dynamical system and proves strict-saddle avoidance under an arbitrarily small one-time perturbation.

Jul 16, 2026

Upload by Quinn