General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization
Authors: Kwangjun Ahn
Gagik Magakyan
Ashok Cutkosky
Venue: ICML 2025 oral (2025)
Keywords: Schedule-free optimizaer
non-convex optimization
online-to-nonconvex conversion
Primary area: theory->optimization
TL;DR: Through online-to-nonconvex conversion we show that Schedule-Free SGD is also optimal for non-convex non-smooth optimization.

Abstract: This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, non-convex optimization problems. Our proof begins with the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into an optimization algorithm for nonconvex losses. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these new conversions corresponds directly to schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choices for schedule-free SGD, addressing a theoretical gap that the convex theory cannot explain.

General framework for online-to-noncomvex conversion: Schedule-free SGD is also effective for nonconvex optimization
Kwangjun Ahn *1
Gagik Magakyan 22
Ashok Cutkasky"
Abstract
without any learning rate scheduling. The schedule-free method is an add-on scheme that can be applied to any cho- sen base optimizer, converting it into schedule-free variant. While this method has shown strong empirical performance in training large neural network models, its theoretical anal- ysis has been limited the convex setting (Defazio et al., 2024). Our aim is extend the theoretical understanding of schedule-free methods to nonconvex optimization.
This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems. Our proof begins with the development of a general framework for online- to-non oo-nonoovex conversion, which converts a given online learning algorithm into nonconvex opti- mization algorithm. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these conversions corresponds directly schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choice for schedule-fres SGD, addressing a theoretical gap that the convex theory cannot explain.
As an initial step, this work focuses on the version where the base optimizer is chosen as SGI,, referred to as schedule- free SGD. For a given learning rate y > 0 and interpolation weights ct Ke E [0, 1]. the updates of schedule-free SGD maintain xs, Yc. and Zy, follows:
X (1 G. x CiZt,
Y: = (1 Kz KgXt,
(SF-SGD)
gi = a stochastic gradient at yt.
2 1
gge-
Here, corresponds to the base SGD trajectory, x is a (weighted) average of 2,, and y: an interpolation between X; and z, where the stochastic gradient is computed.
1. Introduction
1.1. Our main result and approach
Training large-scale neural network models, such large language models, requires a well-designed optimization strategy to ensure stable and fast convergence. For instance, training typically requires a carefully designed optimizer, such as the Adam optimizer (Kingma and Ba, 2014), along with meticulously tuned learning rate scheduling.
To understand the effectiveness of schedule-free SGD for training neural networks, we analyze the method in the non- smooth and nonconvex setting (Zhang et al., 2020; Davis et al., 2022b; Tian al., 2022). Specifically, we adopt the (X, <) -ttttionnyyy criterion from (Zhang and Cutkosky, 2024; Ahn and Cutkosky, 2024) (Definition I), which seeks upproximate Goldstein stationary points (Goldstein, 1977). This criterion emerges as a practical framework for analyz- ing optimization algorithms, particularly considering recent findings that show practical optimizers like SGD with mo- mentum and Adam are theoretically optimal (Zhang and Cutkosky, 2024; Ahn and Cutkosky, 2024).
Recently, Defazio et al. (2024) introduced the sehedule-free method, which achieves impressive training performance
"qqual contribution 'Microsoft Research, Cambridge, MA, USA "Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA. USA 'Department of Elec- trical & Computer Engineering, Boston University, Boston, MA, USA. Correspondence to: Kwangjun Ahn <kwangju- nahn @iierssott.com.. Gagik Magakyan <gagmag mii. Ashok Cutkosky <ashok @ @utkosky.com>>.
Our main results demonstrate that schedule-free SGD is optimal not only for convex optimization, as established by Defazio et al. (2024), but also for the most challenging case of nonsmooth and nonconvex optimization. Our main results can be summarized informally follows:
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Schedule-free SGD is also effective for nonconvex optimization
Theorem 1.1 (Informal; see Section 5). Schedule-free SGD (SF-SGD), with an appropriate choice of parame- ters C, Kt, achieves optimal rates for nonsmooth and nonconvex F.
2. Preliminaries
We first introduce the key assumptions and the notion con- vergence. Throughout this paper, unless specified otherwise, ||-I| denotes the L2 norm.
Our proof technique leverages the muline-to-nonconver con- version framework pioneered by Cutkosky et al. (2023). In essence, this framework takes an online learner as input and outputs an optimization algorithm. As its name suggests, this framework translates online learning guarantees into nonconvex guarantees, analogous to the well-known online- to-batch conversion for convex settings (Cesa-Biane Bessh-Bianchi et al., 2004). As suggested by our title, we first introduce a gen- eral framework for online-to-nonconvex conversion. This framework not only encompasses the previous conversion (Cutkosky et al., 2023; Zhang and Cutkosky, 2024; Ahn and Cutkosky, 2024) as special case but also enables new con- version schemes, as we present in Section 4.2 and Section 5.
2.1. Setting
Following Cutkosky et al. (2023), we consider optimizing a loss function that satisfies the following conditions.
Assumption Let F; Rd R be a differentiable func- tion with the following properties:
Let Ar == F(xo) infx F(x).
For any two points x and w, F(x) - F(w) fo (VF(W t(x w)), w) dt.
F'ss G-Lipshitz, i.e., for any point x, |VF(()]I S G.
With the new conversion schemes, our main observation is that one of these novel conversions, outlined in Algorithm 5, directly corresponds schedule-free SGD. Specifically, by choosing basic online mirror descent as the online learner in Algorithm 5, we naturally recover the schedule-free SGD algorithm. From this, our main result, Theorem 1.1, follows.
Here, the second condition, called well-behavedess in (Cutkosky et al., 2023, Definition 1), is a mild regularity condition. For any locally Lipschitz function F, applying an arbitrarily small perturbation is sufficient to ensure this condition (Cutkosky et al., 2023, Proposition 2).
Wc optimize the loss function F by via stochastic gradient oracle, which is formalized as follows:
Notably, our approach provides fresh practical insight into the parameter choice of schedule-fres methods, which can- not be explained by prior convex analysis in Defazio al. (2024). Our results suggest that setting K2 close to 1 is advan- tageous for nonconvex optimization. This finding clarifies the curious importance of choosing near in (Defazio et al., 2024) for empirical performance a phenomenon not previously explained by convex theory.
Assumption 2 (Stochastic gradient oracle). We assume access to a stochastic gradient oracle at any point x. More formally, for any given point x, each call to the oracle inde- pendently returns a stochastic gradient g that satisfies the following properties:
E Dggl Fx)),, and E
l|g VF(x)]I] S s²²
1.2. Related work
We denote the stochastic gradient oracle as STOGRAD. When the oracle returns the stochastic gradient g at point x, we write this as g + STOGRAD(x).
Our work builds on a line of research focused on conver- gence guarantees for nonsmooth, nonconvex optimization. Intuitively, our convergence criterion aims to find approx- imate Goldstein stationary points (Goldstein, 1977). The formal study of iteration complexity for finding approximate Goldstein stationary points was initiated by Zhang et al. (2020) and has since garnered significant interest (Davis et al., 2022b; Tian and So, 2022; Lin et al., 2022; Chen et al., 2023; Jordan et al., 2023; Cutkosky et al., 2023; Kornowski and Shamir, 2024). Alternative convergence notions are also widely used, including approaches based on the Moreau en- velope or by imposing weak convexity conditions (Davis et al., 2018; 2022a). In particular, the criterion consider in this work, formalized in Definition 1, follows the relaxed version proposed by Zhang and Cutkosky (2024), which slightly modifies the original criterion from Zhang et al. (2020). Additional discussion of related work is provided in Section 7.
2.2. Approximate Goldstein stationary point
For the notion of optimality, we follow Zhang and Cutkosky (2024); Ahn and Cutkosky (2024) and consider the follow- ing notion of stationarity for nonconvex and nonsmooth functions. This notion can be regarded as approximate version of the notion of Goldstein stationarity point.
Definition 1 ((), ---sttiionn point). Suppose F IR. RR is differentiable. We say is a (A, --stationaryy point of F if [V)())) < where
|VF inf inf ( AE |w -wxl']
x||]]
Here the infimum is taken over the distribution p E P(IR)) such that Ew [w] = x.
2

---

Schedule-free SGD is also effective for nonconvex optimization
Our algorithms will identify (A, -stattoonay points using O (A1/2-77/2) calls to stochastic gradient oracle, which is the optimal rate (Zhang and Cutkosky, 2024).
base online learners must be adaptive to varying com- parators, also known the dynamic regret setting. Inspired by Ahn et al. (2024); Zhang and Cutkosky (2024); Ahn et al. (2024), we design such dynamic online learners by considering the following "discounted" version of regret.
To further motivate this definition, we remark that (A,=)- stationary points retain the desirable properties of Goldstein stationary points. Specifically, the following result (Zhang and Cutkosky, 2024, Lemma 2.3) demonstrates that, akin to Goldstein stationary points. (A, -stationnayyy points can be reduced to first-order stationary points with appropri- ate choices of À when the objective function is smooth or second-order smooth.
Definition 2 (Discounted regret). Consider the loss se- quence frT For any T 2 1, we define the discounted regret of an online learner with respect to a comparator u as:
T
[ Regrety T (u) =
Σ 8 3T (e((.)) - - ((
Proposition 2.1. If F is L-smooth, then (L'e- ,e)- stationary point of F satisfies F[)]( S 2s. Moreover, if F is H ssecond-order-snne
then an ( point x of F satisfies [|F((x)] S 28.
For instance, Ahn et al. (2024) demonstrate that online learners with low discounted regret can achieve low dynamic regret through what they call the discounted totettteddt--dmmmiieee conversion. Additionally, discounted regret has been shown to be a more effective metric for designing adaptive online learners in dynamic environments across various contexts, including conformal prediction (Zhang et al., 2024) and online linear regression (Jacobsen and Cutkosky, 2024).
Note that another popular notion of approximate Gold- stein stationarity is called (6, =)sstttionari due to Zhang et al. (2020). However, the algorithms that achieve opti- mal complexity under that notion often require clipping on the momentum term (Cutkosky et al., 2023), which introduces deviations from the practical optimization al- gorithms. Hence, in this work, we adopt the notion of (A, -tttttttioon for which it has been demonstrated that optimal algorithms does not require clipping operations (Zhang and Cutkosky, 2024). We also remark that algo- rithms that identify (A, ) points can also identify (8, st-sttoionr points when Fis is Lipschitz, as demonstrated in (Zhang and Cutkosky, 2024, Lemma 2.4).
3. General framework for online-fo-noncoonve conversion
In this section, we introduce general scheme (Algorithm for converting online learning guarantees into nonconvex optimization guarantees. As a preview, we will demonstrate that our Algorithm not only recovers existing approaches as special cases, but also enables the design of novel conver- sion methods. Let us begin with the pseudocode.
As mentioned above, the stochastic gradient oracle com- plexity of finding (A, e) stationary point is ((21/2=-7)) 7/23 (Zhang and Cutkosky, 2024). By Proposition 2.1, any algo- rithms achieving this rate (such as the ones we will present), can also find a point x with [|V S in O(e ora- cle calls when I' is smooth and O 3.5) calls when F is second-order smooth. These are the optimal rates for their respective function classes (Arjevani et al., 2023; 2020).
Algorithm General scheme for daline-to-noncone con- version
1: Input: Initial iterates xo Wo, online learner A, and T E N, regularization strength μ 2 0.
2: for t = 1,2,..., do
3: Receive 8, from A.
4: Choose x, arbitrarily. // The design choice
2.3. Online learning
Update w, = X, + 8,.
In this section, we provide a brief background on online learning, which plays a key role in our development, Online learming is modeled as a sequential decision-making process over T rounds. In each round f, the online learner chooses a point 5, E IRd, and then a loss function & : Rd + R is revealed. The learner then incurs a loss (6.). The choice of 6, based on the previous loss sequence 1 and after selecting 5t, the learner observes the next loss f,
Update y: = Xx + s, where S st S is drawn
uniformly i..dd
7: Compute ge STOGRAD(y:).
Send loss fe(-) (g.,.) :) # |1-11 to A. A.
end for
Overall, Algorithm 1 generates three sequences of iterates: Xt. Yr, and w.. At each iteration, the stochastic gradients are fed into the online learner, which outputs 8,
The performance of the online learner is measured using the regrer with respect to a comparator u, formally defined as: (u) = Σ (6,) - & (u)). However, recent works (Cutkosky et al., 2023; Ahn et al., 2024) demonstrate that when designing nonconvex optimization algorithms,
The main design feature of Algorithm that gives it flexi- bility is the ability to choose x, arbitrarily at each iteration. However, there are technical properties we want x, to sat-
3

---

Schedule-free SGD is also effective for nonconvex optimization
isfy in order to achieve better nonconvex guarantees, which detailed in Section 3.3.
by Cx 2 0, is the smallest nonnegative constant such that:
T
T
The online learner's output ö, is then used alongside x, to compute We according to the update rule we = X, + 6,. Additionally, the iterates Yt are sampled uniformly from the line segment connecting x and Wr, and the stochastic gradients are computed these ye iterates.
E
X X2
x1
S
Cx
E
1
With the concept of the iterate stability factor, we can now state the conversion result.
Lemma 3.1 (Generic maiie-to-noncoone conversion). Consider the iterates generated according to Algorithm 1. For 3 E (0, 1) and D > 0, define the comparators for online learner as follows:
3.1. Output of the general scheme
To establish nonconvex optimization guarantees, we utilize the exponential moving average (EMA) of the y; iterates, similar (Zhang and Cutkosky, 2024; Ahn and Cutkosky, 2024). We begin by formally defining these EMA iterates. Definition 3. Given a discount factor B E (0, and sequence of iterates {y J=>) the 3-EMA of the sequence up to time I, denoted as yr, is defined as
1A E [T], u, = - Σ 8 Vy
E 30- (P(y))
Then, as long as the regularization strength satisfies p 2
8AD (1 + Cx(1 - 33 3)- the following holds:
1 1 3 y, = 3
ys
E, |F -
3 DT
E
Regret T
(ur))
T
In particular, as we will see in Lemma 3.1, the final output will be the random EMA iterate y,, where r is a carefully selected random index, defined as follows.
+
1
DT
E Regret,
[3] (ui)
t=1
(F(x)) - F((w))) + 1D
Definition 4 (Random index distribution). Let be a ran- dom index distributed over {1, (1.2...., T with the following distribution:
DT
2
1=1
0
+ +ovi-8
TV1 - 3
g* for I,...,TT T 1, for T.
Pr(r= = () =
Proof. See Appendix A.
ST
Lemma 3.1 provides an upper bound on the main quantity of interest, E, (y) |]|[[|] One of the main terms in this up- per bound is the sum of the discounted regret terms, which indicates that improved performance by the online learner leads better guarantees in nonconvex optimization. Thus, Lemma 3.1 effectively translates the online learning guaran- tee into a nonconvex optimization guarantee, suggested by its name, online-to-nonconn
We note that previous works select the output uniformly at random from the sequence {y.)T= (Zhang and Cutkosky, 2024; Ahn and Cutkosky, 2024). Our carefully designed random EMA iterate from Definition 4 leads an improved conversion result, offering stronger nonconvex optimization guarantees, as we will discuss in Section 4.
Notice that as 3 approaches 1, the random index 7 assigns a significantly higher probability (by a multiplicative factor of ) to the final index T. This aligns with common practice, where the final iterate rather than an average of previous iterates-is often used as the output. Indeed, we will select B3 very close to for our nonconvex guarantees (we will choose 3 = 1 - O)))))
conversion.
However, in its current form, the presence of several addi- tional terms in the upper bound makes the result less inter- pretable. Before demonstrating the strength of this general conversion framework, we first reformulate Lemma 3.1 into more interpretable and user-frient user-friendly form.
3.3. User-friendly nonconvex optimization guarantees
3.2. Conversion guarantees
In this section, we apply a concrete discounted regret bound to Lemma 3.1 to derive more user-friendly nonconvex guarantee, which will be used throughout the remainder of the paper. In particular, discounted version of com- posite objective online mirror descent (OMD) (Beck and Teboulle, 2003; Duchi et al., 2010; Zhang and Cutkosky, 2024) achieves the following discounted regret bound.
Given the description of the algorithm and its output, we now present the online-to-nonconvex conversion guarantees. We begin by introducing key definition that quantifies the stability of the x, sequence.
Definition (x-iterate stability). Consider the iterates gen- erated by Algorithm 1. The iterate stability factor, denoted

---

Schedule-free SGD is also effective for nonconvex optimization
Lemma 3.2. Let B E (0, μ 0, 1 O, and sequence of vectors H= Suppose that ||g: 2| 2 G +o² for t [T]. Consider an online learner initialized with 61
4. Warm-up: two simple ways to achieve optimal nonconvex guarantees
and updated as follows:
In this section, as a warm-up, present two simple ways to achieve the optimal nonconvex guarantee using our gen- eral conversion scheme, Algorithm 1. Since Algorithm I maintains two sequences iterates, X; and wt, perhaps the two simplest options for x, are as follows:
B qu
0z+1
(ô:
7gr)
(8-OMD)
Then, this online learner with 7 achieves the following discounted regret bound:
||||| v1
3
G4a
Set x; = Wt-1 for all f [Z]]
2 2||ul] (G oo)
II. Set X;-1 for all E [7].
Regrety [8] (u)) 2 B
E
(1)
As we will demonstrate shortly, the first option recovers the previous conversion, while the second option leads to a novel conversion scheme, showcasing the versatility of our general framework. We will build on these warm-up cases to analyze schedule-free SGD in Section 5. Throughout this section, A can be any online learner that achieves the discounted regret bound (1).
Proof. See Section D.I.
We expect that alternative online learning frameworks, such as helow-tth-rggullriee--eeede can achieve the discounted regret bound similar to (I). However, a comprehensive exploration of discounted online learners lies outside the scope of this work.
4.1. Option leads to previous conversion
Using the bound (I), we can derive an user-friendly non- convex guarantee as follows. In the following two sections, only the regret bound (1) is important; the specifics of the discounted OMD algorithm are irrelevant. Any algorithm achieving similar (or better) regret bound would provide the same (or improved) results.
We begin with the first option, described in Algorithm 2.
Algorithm 2 Option 1: In Algorithm 1, set X, = Wi-1 for all t E [T].
Theorem 3.1 (Generic nonconvex guarantees). Consider the iterates generated according to Algorithm 1, where the online learner A achieves the discounted regret given by (1). Let E > be such that E I [G + o) and let T Z 49(G + =22 Then, there exists a choice of parameters B., D D., μ He such that the following holds:
Algorithm recovers previous approaches (Cutkosky et al., 2023; Zhang and Cutkosky, 2024; Ahn and Cutkosky, 2024). In particular, since Algorithm 2 leads the update w: wi-1 = ô,, it provides nice interpretation of selecting the increments w, w based on the online learner's output, as highlighted by (Ahn et al., 2024).
The main advantage of Algorithm 2 that the cumulative sum of loss decrements can be kept small due to a telescop- ing sum (recall that Ar = F(x.) inf F(x)):
421/2--1/27,
E, IVF((,)) 3
T
Here the algorithan-dependet quantity Ixx is defined as
(F(x)) F(w.)) Σ (F( (2)
Tx (1+ +
1=1
E
Σ (F(x,) F(w.))
= F(WT) S AF.
Moreover, from Algorithm 2, we have ||x, - X,-1|| 8 for t 2 2, and for t = 1, ||x: - X/-1| Wo xoll = 0. Therefore, we have
and the iterate factor Ox is defined in Definition 5.
Proof. See Appendix B.
x; X <
1
(3)
The key takeaway is that the nonconvex guarantees are determined by the magnitude of lxx Thus, it is essential to select the iterates x, in a way that minimizes Xx- As a warm-up, we examine two simple special cases that lead to optimal complexity.
which shows that the iterate stability factor C'x is at most I. Combining these two calculations, Theorem 3.1 leads to the following nonconvex optimization guarantee.
5

---

Schedule-free SGD is also effective for nonconvex optimization
Corollary 4.1. Consider the iterates of Algorithm 2. Under the setting of Theorem 3.1, it holds that E, |[F((,))| 1 4e, provided that
Algorithm 4 Anchoring scheme
1: Input: Initial iterate Xo, and integers N, T N.
Set the initial anchor point a == Xg-
3: for n. .,,,..., N do
T 2 49(G ==)=== max { 8A 3/2 1] (4)
4: Starting from a run Algorithm 3 for T iterations to
generate the iterates {x, (x("), W (n) [n) }
(n) /t=1- (By the
Proof. With Algorithm 2, the above inequalities, (2) and (3), show that Ei= (F(x))- F(w.)) ((w.))F(w.)) I AF and Cx I 1. Therefore, follows that
choice in Algorithm 3, we have x =\t a, for all
E [T].)
5: Sample the next anchor point an+1 uniformly at ran- dom from {w, (w/")] (7)
Tx (1 49(G + A Ar
22 49(G + o))² Ar,
===1
6: end for
8²
22
since S [G +o). Thus, Theorem 3.1 yields:
Corollary 4.2. Consider the iterates of Algorithm 4, Under the setting of Theorem 3.1, it holds that
8 1/2 49(G+)))*
AF)
E,, ( S 35 +
En-Unif([N]]] Br VF S 4E, (6) |
provided that T' 49 + -- The second term in the upper bound is at most if (o Hence taking the maximum of the two requirments for T, the iteration complexity bound (4) follows.
provided that N 2 4Ap2 3/2 -32 and T N 49(G +
3ipE -2 Hence, the total iteration complexity
T T. 49(G + -0 -mxx (4px2/22-377 3/2 1}.
We note that the complexity bound in Corollary 4.1 is op- timal, in light of the lower bound results of (Zhang and Cutkosky, 2024). In fact, our use of the random index т leads to a slightly better guarantee; the upper bound in (Zhang and Cutkosky, 2024) has the second argument of the maximum O (GG + -o)-")). whereas ours is O (1).
Proof. By Theorem 3.1 together with (5), the following holds for each epoch n:
E, V F Fy( (M]
3 + 41 / 1/1-2-11/2
We emphasize here that Algorithm 2 recovers commonly used momentum-based optimizers as special cases. Zhang and Cutkosky (2024) show that setting A as the OMD in Lemma 3.2 corresponds to SGD with momentum, while Ahn and Cutkosky (2024) demonstrate that choosing A discounted version of FTRL results in the Adam optimizer, up minor modifications.
E Σ
(((m)) F(w(")))
T
= 3 + 4x 1/2 1/2 (F(an) F(ant1)),
where the last equality follows because a is chosen uniformly at random from {w(") } (
Summing over epochs, since ΣM' (F(an) F(an+1)) = F(a1) F(aN+1), have:
4.2. Option Il leads to a novel optimal conversion
We now consider the second option. Since x; X for all it follows that x; xy for all E [T].
E En-Uni(((NT)) E, ()()(")) [A]
< 35 + 1 1/2
E (F(ai) - F(aN+1))
Algorithm 3 Option II
N
1: In Algorithm 1, set x, Xg for all / E (T).
11/2
< 3r +
The main advantage of Algorithm 3 is that Cx because x₁ is fixed for all iterates. This implies that
Thus, setting N 2 4Ap 1/2 3/2 ensures that the right- hand side is at most 4s.
This result demonstrates that Algorithm 4 provides an al- ternative approach for achieving the optimal nonconvex guarantee. Interestingly, this method bears a conceptual re- semblance to the classic online-to-conver conversion (Cesa- Bianchi al., 2004). In particular, the traditional conversion
Fx E (F(x))-F(w)) F(w:)).
(5)
Hence, we only need to control the term (5), which can be done via the following anchoring scheme.
6

---

Schedule-free SGD is also effective for nonconvex optimization
online learner for T iterations and then selects iterate uniformly random (or averages iterates, applying Jensen's inequality). This approach closely parallels the pro- cedure of a single epoch of Algorithm 3. This is analogous to non-convex optimization approaches based upon repeat- edly solving convex subproblems created by appropriate regularization, as discussed by Chen and Hazan (2024).
g
X++1
Wee1
66:-1 81+1
0
Thus far, we explored two simple methods for selecting X both of which can lead to the optimal nonconvex guarantee. In the next section, we will consider yet another conversion approach that leads to the optimal guarantee.
Figure 1. Illustration of how Algorithm can be interpreted as schedule-free SGD. By defining the z-iterates according (8), becomes clear that the z-iterates follow the base SGD trajectory of schedule-free free SGD (SF-SGD).
5. Schedule-free SGD is effective for nonconvex optimization
Then, it holds that E, /VF((F) - 5e, provided that
In this section, we build on Section 4 and consider another special case of Algorithm that achieves the optimal non- convex guarantee. Specifically, we fix the online learner A to 3-OMD from Lemma 3.2. This is in contrast to the previous sections in which the specifics of the online learner were not important. Recall the update rule of 3-OMD:
T T 49(G + 8 max {20 3/2 1}
Proof. The proof is very similar to that of Corollary 4.1; see Appendix C.
8'+1 5 C (ô; - 7
(8-OMD)
Corollary 5.1 shows that Algorithm 5 achieves the same optimal complexity as the conversion methods discussed in Section 4, differing only by multiplicative constant factors. Next, we will examine the update rule more closely.
where we let Ç == 1+mp
to simplify.
5.1. Yet another optimal conversion
Consider the following special case of Algorithm 1, specifi- cally designed for 3-OMD.
5.2. Option III is equivalent to schedule-free SGD
A striking outcome of our general conversion framework (Algorithm 1) is that one of its special cases, Algorithm 5, turns out to be equivalent to the schedule-free SGD method.
Algorithm& 5 Option III
1: In Algorithm 1 with A chosen as B-OMD, choose x xt-1 + &o, for all E [7].
To demonstrate this equivalence, we introduce set of ex- trapolated iterates, 2,, defined follows:
We first demonstrate that this conversion scheme achieves the optimal nonconvex guarantee. The key idea is that, with Algorithm 5, the iterates x, remain sufficiently close to Wt-1, allowing us to take advantage of the telescoping sum from Algorithm 2. More specifically, with Algorithm 5, one can easily check that the following holds:
1 6..
(8)
These iterates follow an SGD trajectory. just like the base method used in schedule-free SGD, with an effective step size of y = - See Section D.2 for details.
1 6, 8 -11-1 5
Proposition 5.1. Under Algorithm 5 and using the extrapo- lated iterates defined in (8), the following holds:
X; W
In other words, ||x, - wr- is significantly smaller than the size of the update made by A. With this observation, now show that Algorithm 5 achieves the optimal nonconvex optimization guarantee.
Z - 2, =
gr.
1
Next, we demonstrate that Algorithm 5 mirrors the update rule of schedule-free SGD. We begin by presenting the explicit form of Algorithm 5, where we substitute the choice of x; according to Algorithm i.e. x, x along with the choice of AA as 3-OMD. The resulting explicit update form shown in Algorithm 6.
Corollary 5.1. Consider the iterates of Algorithm with the parameter choices as in Theorem 3. 1, i.e., 3 = B,, D D.,
J = ph,, and the parameters of 3- B-OM chosen as:
2 1) = 77. = G+0
B.
D. D.V1=
-B, and Ç= ==
1 1 Malt.
7

---

Schedule-free SGD is also effective for nonconvex optimization
Algorithm 6 Explicit form of Algorithm 5
Algorithm Rewriting of Algorithm 5 using the extrap-
for prrt= = 1, 1,2.... ........ ., do
olated z- z-iterates (8)
2: Receive 6, from A =3-OMD, i.e. 8,
Input: Initial iterates Xo Zo.
((ôt-1 7)--1).
for t 1, ... T do
3: Update Xt-1 + jo..
3: Update x, - (Xt-1 + (1 ()Ze.
4: Update w. xx + ò₁.
4: Set = K,X, + (1 Kit 24, where Ki is drawn
5: Set y; = x sr4e, where 8, is drawn uniformly
uniformly from [c, 11, i..d.
from [0, 1] i.id.
5: Compute gt + STOGRAD(y:).
6: Compute ge < STO)RAD(y:).
Update Ze+1 = 2, - 7gt, where the step size
7: Send loss (e)-) = (g..) 1) + 11.11 to A.
chosen as ? = T-('
8: end for
end for
We can observe that Algorithm 6 can be reformulated in terms of the iterates X Yt, and 2,, eliminating the depen- dence on We. This follows from (8), along with the choice X2 X + Sor which implies the following relationship:
We interpret these parameter choice in light of empirical findings by Defazio et al. (2024) that lacked theoretical ex- planation. Their convex guarantee (Defazio et al., 2024, Theorem 2) permits K2 be chosen arbitrarily within the in- terval [0, 1]. yet experimental results indicated that selecting K2 near 1 (e.g., 0.98) was crucial for strong empirical per- formance. Our results provides theoretical support for this choice, as noted the first bullet point of Proposition 5.2.
(x + (1 ()zz.
This result is also visually illustrated in Figure 1. Addition- ally, since yı X, stôt, we have:
6. Conclusion and future directions
Y: = x + 26 (z: x() = (1 - s6(1 x))x; + se(1 - ()zz.
Motivated by the impressive empirical performance of schedule-free methods, this work investigates their effec- tiveness for nonconvex optimization. As a first step, we demonstrate that schedule-free SGD achieves optimal iter- ation complexity for nonsmooth, nonconvex optimization. This accomplished through a general conversion frame- work that only recovers existing conversions but also introduces two novel conversion schemes. Notably, of these novel conversions directly corresponds to schedule- free SGD, which serves as the basis for our analysis.
By combining these steps, we obtain Algorithm 7, a reformu- lation of Algorithm 6. Notably, this algorithm is equivalent to the schedule-free SGD method. Specifically, Algorithm selects Ne uniformly from the interval [s, 1] each itera- tion, employs step size y - and consistently sets c = 1 for all L.
5.3. Practical insights from results
Our results highlight an important property of schedule-fres SGD: it not only achieves the optimal convex guarantee established by Defazio et al. (2024) but also attains the optimal nonconvex guarantee, This versatility helps explain the empirical success of schedule-free methods across a important
While this paper lays important groundwork, it merely scratches the surface our understanding of schedule- free methods and opens up several avenues for future research. Below, outline few of these potential directions for the reader's interest.
broad spectrum of optimization problems. to note that our current analysis requires distinct parameter settings for y and cz. depending on whether F' is convex or nonconvex.
Other special cases of our general conversion. In this work, explore three specific instances of the general conversion framework. However, it is unlikely that these are the only viable conversions. Since these special cases yield highly practical optimizers, it would be worthwhile to investigate additional special cases and assess the practical implications of those conversions.
We now discuss how our results offer new insight into pa- rameter selection for schedule-free SGD. To begin, we note the following fact (see Section D.3 for further details).
Proposition 5.2. With the parameter choices given in Corol- lary 5.1, we have Ç C. = θ
(G+o)= Specificully, the parameter Be in schedule-fres free SGD is chosen uniformly from (S., 1], implying that 1 - (G+ay < < for all This selection ensures that 8s, remains close to
Adaptive schedule-free methods. Considering the im- pressive practical performance of the schedule-free version of Adam, as highlighted in (Defazio et al., 2024), it would be intriguing explore whether this method can be under-
8

---

Schedule-free SGD is also effective for nonconvex optimization
stood special case of the general online-to-monconvex conversion framework. Our current analysis provides correspondence only for schedule-free SGD.
iterates, X,, directly according the online learner, the maline-to-nonconver conversion framework determines the increments, X based updates from the online learner.
Advanced weighting schemes. The convex analysis of (Defazio et al., 2024) allows for arbitrary sequence of "weights" for each example which inform the choice for in (SF-SGD). While uniform weighting (corresponding to = 1/t) is worst-case optimal, it is not instance optimal, and in fact certain empirical heuristics such as learning rate warmup can be recovered by eeeence-dependent weighting (Defazio al., 2023). Our analysis makes use of exponen- tially increasing weights, corresponding to consant o y as detailed in Algorithm 7. While our weights achieve the optimal worst-case convergence guarantees, we conjecture that improvements are possible by incorporating instance- dependent weighting.
Practically, the moline-to-nonconye conversion framework offers a promising perspective on the success of popular optimizers. By choosing standard online learners within this framework, we recover practical algorithms: online mirror descent corresponds SGD with momentum (Zhang and Cutkosky, 2024), while variant of folluw-the-regullarized leader (FTRL) aligns with Adam (Ahn and Cutkosky, 2024), This natural alignment with widely used optimizers under- scores the framework's ' potential as a powerful tool for un- derstanding the success of practical optimization algorithms. Building on this, our work further demonstrates the frame- work's ' promise by showing that it also captures the highly effective schedule-free SGD algorithm.
Truly universal methods. It is noteworthy that the schedule-free method achieves optimal rates for nonsmooth losses regardless of their convexity. However, as discussed in Section 5.3, the current analysis requires distinct parame- ter settings for 7 and ca. depending whether F is convex or nonconvex. This indicates that we have not yet developed fully unified algorithm that seamlessly addresses both cases. Nevertheless, these findings suggest the potential for a unified algorithmic framework. would be valuable to explore whether a single parameter choice can be effective for both scenarios and to determine if such choices align with those observed in practice.
Lastly, we note that the existing theory for the schedule-free method is limited to convex losses, analyzed through online- to-batch conversions (Defazio et al., 2024). Specifically, when the base optimizer is selected as an online learner, Defazio et al. (2024) demonstrate that schedule-free meth- ods effectively transform online learning guarantees into optimization guarantees for the last iterate, similar to the re- sults of (Cutkosky, 2019; Kavis et al., 2019). However, this convex theory does not account for the empirical success of schedule-free methods in training neural networks. Our work extends these insights by showing that schedule-free SGD is also effective for nonsmooth, nonconvex optimiza- tion.
Why schedule-free schedule-free? Lastly, we acknowl- edge that the main limitation of our analysis its inability to fully explain why shhedule-free methods can effectively alleviate the need for learning rate decay schedules, which is their most notable empirical advantage. Addressing this gap likely requires the development of theoretical framework for understanding learning rate scheduling in nonconvex optimization.
Impact Statement
This paper studies Schedule-Free optimizer in the non- convex setting. This work theoretical and we do not see any immediate potential societal consequences.
7. A Aditionnl related work
As discussed in Section 1.1, our approach specifically builds on leverages the mnline-t--nonconver conversion framework introduced by Cutkosky et al. (2023), a versatile frame- work that established the first optimal algorithm for stochas- tic nonsmooth, nonconvex optimization. Similar the well-known online-to-batch conversion (Cesa-Biand) -iesa-iianchi al., 2004), which transforms online learning algorithm into an optimization algorithm for convex losses, this framework adapts this transformation to nonconvex settings. A key distinction, as noted by Ahn et al. (2024), lies in how each framework sets the iterates of the resulting optimization algorithm. While the online-to- tolline-t--btch conversion sets the
9

---

Schedule-free SGD is also effective for nonconvex optimization
References
D. Davis, M. Díaz, and D. Drusvyatskiy. Escaping strict sad- dle points of the moreau envelope in nonsmooth optimiza- tion. SIAM Journal on Optimization, 32(3):195811983, 2022a.
K. Ahn and A. Cutkosky, Adam with model exponential moving average is effective for nonconvex optimization. In Advances in Neural Information Processing Systems, 2024.
D. Davis, D. Drusvyatskiy, Y. T. Lee, S. Padmanabhan, and G. Ye. A gradient sampling method with complexity guar- antees for lipschitz functions in high and low dimensions. In Advances in Neural Information Processing Systems, volume 35, pages 6692-6703, Curran Associates, Inc., 2022b.
K. Ahn, Z. Zhang, Y. Kook, and Y. Dai. Understanding adam optimizer via online learning of updates: Adam is ftrl in disguise. In Forty-first International Conference on Machine Learning, 2024.
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, A. Sekhari, and K. Sridharan. Second-order information in non- convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299. PMLR, 2020.
A. Defazio, A. Cutkosky, H. Mehta, and K. Mishchenko. Optimal linear decay learning rate schedules and further refinements. arXiv preprint
2023.
A. Defazio, H. Mehta, K. Mishchenko, A. Khaled, A. Cutkosky, et al. The road less scheduled. arXiv preprint arXiv22405.15682 2024.
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Sre- bro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Prcsiiccallororrr Programming, 199 (1):165-22) 2144, 2023.
J. C. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. In COLT, volume 10, pages 14-26. Citeseer, 2010.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3163):167-175, 2003. 2003.
A. Goldstein. Optimization of lipschitz continuous func- tions. Mathematical Programming, 13:14-22, 1977.
A. Jacobsen and A. Cutkosky. Online linear regression in dynamic environments via discounting. In International Conference on Machine Learning. PMLR, 2024.
N. Cesa-Bianchi, A. Conconi, and C. Gentile, On the gen- cralization ability of on-line learning algorithms. Infor- mation Theory, IEEE Transactions on, 2009):000-20577, 2004.
M. Jordan, G. Kornowski, T. Lin, O. Shamir, and M. Zam- petakis. Deterministic nonsmooth nonconvex optimiza- tion. In The Thirty Sixth Annual Conference on Learning Theory, pages 4570-4597. PMLR, 2023.
L. Chen, J. Xu, and L. Luo. Faster gradient-fi free algorithms for nonsmooth nonconvex stochastic optimization. In International Conference Machine Learning, pages 5219-5233. PMLR, 2023.
A. Kavis, K. Y. Levy, F. Bach, and V. Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019.
X. Chen and E. Hazan. Open problem: Black-box reduc- tions and adaptive gradient methods for nonconvex opti- mization. In The Thirty Seventh Annual Conference Learning Theory, pages 5317-5324. PMLR, 2024.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.660 2014.
A. Cutkosky. Anytime online-to- toiine-to-bue bo-bathh, optimism and accel- eration. In International Conference on Machine Learn- ing. pages 1446-1454, 2019.
G. Kornowski and O. Shamir. An algorithm with opti- mal peeession-depeddence for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122) 2024. URL http: html.
A. Cutkosky, H. Mehta, and F. Orabona. Optimal stochas- tic non-smooth non-convex optimization through online- to-non-convex conversion. In International Conference on Machine Learning (ICML), volume 202, pages 6643- 6670. PMLR, 2023.
/ htw.a/oorg/ppperrsss/eeee
T. Lin, Z. Zheng, and M. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160-2611 2022.
D. Davis, D. Drusvyatskiy. K. J. MacPhee, and C. Paquette. Subgradient methods for sharp weakly convex functions. Journal of Optimization Theory and Applications, 179: 962-982, 2018
L. Tian and A. M.-C So. No dimension-fiee determin- istic algorithm computes upproximate stationarities of lipschitzians. arXiv preprint 10.06697 2022.
10

---

Schedule-free SGD is also effective for nonconvex optimization
L. Tian, K. Zhou, and A. M.-C. So. On the finite-time complexity and practical computation of approximate sta- tionarity concepts of lípschitz functions. In International Conference on Machine Learning, pages 21360-21379. PMLR, 2022.
J. Zhang, H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie. Com- plexity of finding stationary points of nonconvex nons- mooth functions. In International Conference on Machine Learning, 2020.
Q Zhang and A. Cutkosky. Random scaling and momentum for non-smooth non-convex optimization. Proceedings of the s/ International Conference on Machine Learning, 2024.
Z. Zhang, D. Bombara, and H. Yang. Discounted adap- tive online prediction. In International Conference Machine Learning. PMLR, 2024.

---

Schedule-free SGD is also effective for nonconvex optimization
A. Proof of the discounted-toonnooconne conversion (Lemma 3.1)
begin this proof with some notations, Recall that T the random index distributed over [T] as:
3
if 1, ..... T 1
Pr(T 1) = Pr
if t == T.
For each & [T], let Y, the random iterate distributed over {y.)==1 as:
Pr(Y, = ys) 9t,s -/ 1 B
for 1,2,...... ....
1 B 1-31 E Br y.
In particular, it follows that Ey, [Y,]
yc.
In order to prove Lemma 3.1, we want to upper bound the following quantity:
E, |VF(}>)]'
From the definition (A, -ttttioonayyy point (Definition 1), follows that
E, (IFF(y)))) [ E, [|EX, VF(+)) +EE, II,, - 8, 1/]
We will now upper bound each term individually. We begin with the first term.
Lemma A.1. For 3 (0, 1), consider the iterates generated as per Algorithm 1. Consider the following definitions:
For each E (T), let u, E BF. - VFl.
For each E (T), let Y, be the random iterate distributed over {y=)==1 as:
1 B 1 gr for 1.2.....t
Pr(Y, =y) =t.=
gt-s
Then, the following upper bound holds:
AE Regret
10 (uT)
+ +11-8)2? E Regret, 9 (u.)
μE >T
||,,11
E, VF(x))I
DT
2DT
E
T
(F(x,) F((w))
WD
+ o
tov1 1 3+
DT
T
2
Proof. See Section A.1.
For the second term, we use the following upper bound. Lemma A.2. For 3 E (0, 1), consider the iterates generated as per Algorithm 1
T
4/3
T
E,Ey, ||,, V-11²
10.11 +
Xx - x:-1
(1 - 2)
Proof. See Section A.2.
Now let us combine above two results finish the proof. First, by Lemma A.2, we get
Ex, Y, 1 <
41
18, 2
1
E
X
x(-111²)
T
(1
8)2
12

---

Schedule-free SGD is also effective for nonconvex optimization
Therefore, Upon combining Lemma A.1 together with Lemma A.2, we get:
E
|VF()))]
3E
Regret [0] (uT)
+ (1 - 3)
E Regret 10] (ui)
DT
1
E
(F(xi) -((w))
DT
4X
1
T
T
+
E
||&,11
+
x(-111
||
(1 (3)2
2DT
1=1
1=1
ID
+0V1-B
2
TVI-3
Now, using the definition of Cx (see Definition 5), it follows that
4A
E
T
16.1
E
X
x(-111
11
Σ
|
T
(1-3)²
2DT
1=1
T
< (41(1 + Cx(1 - -3)
11
1 S 0,
2D
T
+ Cx(1 - 2)- Therefore, we get the desirable upper bound. where the last line holds since μ 2 81D(1+
A.1. Proof of Lemma A.1
We begin with the following identity:
T a
T
Σ
g0- -F(x))
F(x:))
Σ gn (1 (1-31)(FFF))) (F)((w)))) F(xx))
T
8r -1+1 (F(w)) - -F(x))
Σ (F(w.) - F(xi)) Σ 3T (F(.) (F(w:)-F(xx) F(xi)).
After rearranging and taking expectations, follows that
T
T
0 (1 3)
E
g
(F(w)) F(x)) + SE
- (F(w.) F(x)) +E (F(x)) F(w.)) 8
n=
1=1
1=1
1=1
(A)
B
Given this decomposition, we will carefully upper bound both (A) and (B). This will be done based on the following result.
Lemma A.3. For B E (0, 1), consider the iterates generated as per Algorithm 1. Consider the following definitions:
For each E [T], let = DD E.m F(y..
BC FFGy))
For each E (T), let Y, be the random iterate distributed over {ys) as:
8
Pr(Y, = =ya) =qt, = gt-
for 5 = 1.2
1 - gt
13

---

Schedule-free SGD is also effective for nonconvex optimization
Then, for any n (T), we have
-D 1 8r EE Ex VF((,,)I +
oD
E
r (F(w))))x(())
1
v1 -1-B
+ E|Regret ( (u,)) + E
gu ( 11 2
+ 14 D²).
2
1=1
Proof. See Section A.3.1.
By Lemma A.3, it follows that
(A) S - DE Σ
BB) Σ
Regret [ (u,)
n=1
n=1
+ (1 B
8
(
11
| 2 D2
Note that the last term can be further simplified:
T
T T
(1 - 3)
16
6
2
+
11 n2
= (1 - E
gn-t
1
|1.,11 2
+ 1
D²)
2
2
2
2
1=1 n=
T
= E
(1
3T-
1+1 )
11 2
11,111
+ D
2
t=1
Next, again using Lemma A.3, we get
3- -BT++
OBD
(B) S DD
E Ey, VF(YT)|
1-3
VI-
T
+ [Regret (uT)
+ E
3T
-+1 (- 1|o.11 + 2 D2).
Combining the above two inequalities for (A) and (B), and plugging them back to the original identity, we get the following inequality:
gT41
T Σ
0 D
E
EY, VF(Y)) +
(1 39)
VF(Y))I
1-9 8
1=1
T
+ toDT 3 (1 B)E
Regret [8]
(u,) +E
(1 3
11 110.112 11 D2)
t=1
-I-3 + JE Regret [9]
agD
(ur)) + E
gI- 11 ||,,11 2
+ 11 D22
Σ (F(x:) - F(w.)).
2
Hence, after rearranging, we get the following inequality:
3 g+
D. E
Ex,, VF(YT)| + Σ - (1-B9)18 |Ix. VE(Y))]
1- 3
T
(1 B)E
Regret [ (u:) + Regreet (99] (ur) + Σ
(F(x)) F(w:))
1=1
+oDT 3+
oBD
+E
/ |6
11
D?).
V1 3
2
2
14

---

Schedule-free SGD is also effective for nonconvex optimization
In order simplify the left hand side, notice first that
gT
8 gT+
- gT -
+ Σ 11 - 8*)
=
T
T.
1 1- 3
1-
1- B
Let J be the random index among (T) such that
1-8²
if 1. 1....,T-11,
Pr(r= -
1-8"
T
8(1-8
1
1-8"
if t-
1-3
Then, follows that
3- 3T+1 1-3
D.E
Ex VF(Y)) + -0- B9) |x,, [Bx = DT E, |x, VF(Y,))I-
Plugging this back to the above inequality and dividing both side by DT, we get the desired incquality Lemma 3.1.
A.2. Proof of Lemma A.2
Similar to Y,, Vn we define the random iterates for the x-sequence:
For each
[T]. define the random iterate X, distributed over {xn]== s=1 as:
Pr(X, =x,)= Un,s gm- 1 3
for 1.2.....
1 fm
Let x,, be defined
1
X Ex,
B
1
gn
Given this notation, prove the following result.s
Lemma A.4 (Variance decomposition lemma). For each [T] the following holds:
Ey, Y, --.12 2Ex. 1X, x,
In lyy x²11.
Proof. See Section A.3.2.
Applying Lemma A.4 to the random index т results in
E, Ey, YY, - 111 < Ex. XX, 111 + 2E,
Σ Tr, ly. - xx11
For upper bounding the first term, we use the following result. Lemma A.5. The following holds:
23
ExE X, - x112 (1 B)2T
Σ |xn 11.
Proof. See Section A.3.3.
15

---

Schedule-free SGD is also effective for nonconvex optimization
Using Lemma A.5 for the first term the RHS, obtain:
43
T
2E, Ex, X, X
Xnn
11-
B)27
n=1
Expanding the expectation for the second term, gives us:
n
2E,
Σ tr, llys - x,11²
Σ
Pallis llys -
-xsl Xsl1
rum
2
Σ
Σ Pn An=s
lly, xx,1?
s=1
Finally, plugging in the values of pr and In,s. we get:
I
T-1
Σ
Σ (prln,)) + +pr91,
Pn =
7=
m=
T-1
8"
g 1-8
1- 8m ))
1 1- ST
(gT-0. 1- 3 B
T
1- T
n=a
T-1
gT-s
f7-0(11
3) +
T
T
R=S
8T-8
1
T
T
Putting these two upper bounds together and using the fact that E l|w, x, = 11,,111 our final bound follows.
A.3. Proofs of technical lemmas
1. PROOF OF LEMMA A.3
For an index t, let us first consider the term (w:) - F(x)). By 1 and the fact that w. X2 = ō., together with the fact that yt X, S, for 8t Unif(o, 1] (see Algorithm 1), we have the following:
(F(:)) F(x;)] = E,, (VF(y.), 5z).
On the other hand, for n 2 f, holds under the randomness over stochastic gradient g: that
Eg (V) Egg (VF(),), u.) + Eg, (VF(y.), 5, uu,)) Eg. (VF(y), un) + Eg. (VF(y,) - g: ô, un) + (gi, d. up)
Eg. (VF(y)) un) Eg. (VF()) gi: -u,) + Eg. (gi, 8r un))
where the last line follows since
Eg (VF(y.) gr, 8.) (Ez, (VF(y.) -.), -.
Upon taking the overall expectation, we have
B[F(w:) F(x:)] EI (VF(y)) gr. u.,) (gc, 6, =n,)]
Hence, it follows that
E Σ (FWw) F(x)) 8 KVF(y.), un) (VF(y.) gr. -u,) (gr, 6. un)]
99)
Let us consider each term on the right hand side one by one:
16

---

Schedule-free SGD is also effective for nonconvex optimization
Using the definition Un = - Σ FF(y))
the first term can be expressed as:
Ei= (F(())
E = 8" VF((y.)
E
g
(VF().): un) B
8 (F
-D
(10)
Σ 1=1 (F-(.F
=-D - gr
=D
Σ 8 VF
E | VF(Y,)I
(11)
1 1-
For the second term, using Cauchy-Schwartz inequality, we have
n (V gr)
(y) Br. u.,)
E
Σ
Ellun
(12)
Using the bounded variance assumption on the stochastic gradient oracle, we have
a²
E
8" (VF(w))
gi)
E
82(n VF
-gill" 1
(13)
1
1
where we used the fact
1-3² S I-B-
Thus, it holds that
oD
g--t (VF(y)) ge. -u,) S
VI -I-B
For the third term, have
E
8
(g, 8 - un)) = Regrett [9] (un) +
8
B--1(- ((-
11
|
+
un,
n
2
2
1=1
E Regrett (3) (u,,)] 2 Bm-t(- 11
|
11
D²)
2
2
This completes the proof of Lemma A.3.
A.3.2. PROOF OF LEMMA A.4
Let S,, be a random index distributed over 2,..., n such that Pr(S, =8) = In,s- Moreover, let S, be an independent copy of Sn, Then, follows that
Ys. Eg, sy !|?
Ey, Yr, J.ll²
Esg
Yss Xs, -B3, [yg. X3 ||?
Es
xs. Ez, [x3.]
< 2Es
xs. - E3, [x3,
+ +22.s
ys. XS. Bs, IN - X3
< 2Es
XS. - Es, [x |||
+ +Ess Ilys. - xs. 11?
2Ex, Ix, x, + Σ In.s Ily: xzl12
where for the first bound we have used || v|
2 ||=|
+ 2 12 and for the second one we applied E X EX
|| |
x 2 This completes the proof.
17

---

Schedule-free SGD is also effective for nonconvex optimization
A.3.3. PROOF OF LEMMA A.5
We start with the following two results.
Proposition A.I. For each n. E (T), it holds that
[-1 In - j).
Ex, X -x,, x, S 2
An, Iix - x
where An,t =
1=1
Proof of Proposition A.1. Let us fix n E [T). Let X, be an independent copy of X Then, by Jensen's 's inequality, we get:
Xn Bx, Xui| Ex,,x, Xn X, ||
Ex, |x,, Xn xnl Ex,
(14)
i-1 In, ||2; - x1,1?
Σ
(15)
==
Next, using Cauchy-Schward Schwartz and triangle inequality, we get:
2 111
- x111 -
||x:
X x
(i- Σ
x x111
+=++1
b=j-1
Hence, it follows that
Ex. |x,
xn 1 2
In. - ||z, - x1-111
1=1 j=l
2
Σ
In.i (i -5) 1x: 1x:- xx-1
j=1
This completes the proof.
Proposition A.2. For S L S v. S T, it holds that
+ 1)33 1n t+1
An,t
3m
Proof of Proposition A.2. In order to prove the desired upper bound, let us first simplify the expression for An, follows:
8
An,t
3 3m-igh 1n-iggn-1 in
1 - gm
i=t j=l
3
2
8n in-5
(8 = i- f)
1
3m
i=t 8=1-tH1
1
8
2 n-t
Σ
8 3ht0
(k=
3m
1 3
n-f
R-
B2k
Σ
8,38
1 3m
k=n-k-tt1
Next, let us compute the inner summation:
nーk- 1-1
83 = 3 d n
g = 3. d
gn-h--t1 gn-k
dB
d3
1- 3
-
S=n-k-t 1-1
ga ga-k+1 gb-k+1
(a k)
(b - k)
(a t== ==
(1 - 3)
1 3
18

---

Schedule-free SGD is also effective for nonconvex optimization
Substituting this back the above expression for Xn, have
2
n-
ga-k+1 k+1
gb-
(a
An, =
82k
+
gr
(1 - -32
1
k=0
n-t
[ga+]
gb+1
a,3a
6,9
8 8
8
kggh
+
gn
(1 B32
1 B
1 3
A=
Now one can compute the first and second terms above using the following identities:
First term: note that En 9h
1-8r 111
1-ge 1-3
1-8
Second term: note that Σ En=o k:
11180
8 8-190+1
48 1-3-
1-3
31-
Thus, it follows that
I 3m )² . 1
1 1-88 2
[ [Batt] - g0+1
ag 639h
1 - g"
8" 3h
3 - gat1
O
An,t=
(1 8)²
3
3
(1 3)²
1 3
(Bat1 B
1-
+ (a.3 b (1 - 30) - (8a+1
8b+11 ) 1-
+ (3a 36 Ja
1-B
1-3
(1 gm
(afa - b,9%)(1 - 39) + (3aa
8hh a,33 a. (1 - (b)) bB (1 - ga)
0,5 (1 - 8
(1-
(1 fgm
(1 - B2
Upon plugging back the definition of a and b, this completes the proof of Proposition A.2.
For the remainder of the proof, let use the following notation for simplicity:
8, ||x: x
(16)
Combining Proposition A.I and Proposition A.2, it follows that
(n t + 1)33 10)3n--4
1+1
Ex. XX,, - x,,l1 < 2
53.
(17)
1 gm
With this bound, one can upper bound the overall averaged variance term as follows:
Ex, |X,
X,
2 Σ
Ex
|x,, - xxa11
+ Ex |XT - Xr
-xx11
(18)
2 T-1
1 8
(n + g1-
+ 2 - ST)
TT + 1n+
-n+1
82
(19)
Bm
3)T
3r
n=1
[=1
n=1
2 T-1
(nn +
1) ++1
-++1
82
+
2
n+1 82. Σ (T n + -n+1
(20)
(1
ByT
19

---

Schedule-free SGD is also effective for nonconvex optimization
For the first term above, note that
T-1
(n - t 1)88
n - t+ 1)8m
==1
67 k
67 d
T-t 8h
]]
T-1
d
[
---
Σ
d3
dB
B
1=1
88 B - -BT -42
(T + 1)
+
(1-
1 1- 3
- (8 BT
3
(T + 1)
8
+
(1 B)²
1-8
3
Upon plugging this back to the upper bound on the overall averaged variance, we get:
ExEx ||,
x=12
2
T-1
Σ
B² - 1011-33-11 33
B
82
+
(1- ByT 52
2,3
T
(1 - (1-3)
1 3
n
$
2
Σ
T-1
B² + 3(1 3)
82
+ (1 - ByT
23
67
T
(1 (1-38² 3)2
n=1
T
2
82
(1
2)
This completes the proof of Lemma A.5.
B. Proof of the user-friendly nonconvex guarantees (Theorem 3.1)
Let us first recall the upper bound from Lemma 3.1:
T
E, [IVF(}))]))
3E
Regret T (ur) + (1 -3)
Σ
E Regret, (0) (u:))
DT
t=1
+
1 DT
E
F (x(,) - F((w)))
+ HD
T TV +ov1 1 8
σ
2
Below, we further upper bound the discounted regret terms. First, since ||u ll = D, Lemma 3.2 implies:
vt E [T].
BE Regret!
[+] (u.)
2D σ)
e D2
(21)
VI- 3 2
where this upper bound holds for all E [T] since the upper bound does not depend on T.
To simplify the upper bound on the regret term, we impose the following condition:
1 ー 1
-
(22)
2
Additionally, we introduce the following notation to streamline our expressions:
1 - 3.
(23)
In the sequel, we will select - = (s))), ), so readers can treat a as a small quantity.
20

---

Schedule-free SGD is also effective for nonconvex optimization
With the condition (22) together with the simplifying notation, we have 3 S 22am and of 2 1. Therefore, plugging the upper bound (21) into the discounted regret term, it follows that:
1 DT
3B
Regret 131 (ur)
+
Σ
T
Regret ! [egree/((u.)]]
S
+1)
(2D + o) Va
+ ZuD2
DT
1=1
3aT
[2DGG+
+ ZuDe) = 6(G
3 gapD & + zuD.
DT
Va
Now let us plug this bound back to Lemma 3.1. For the regularization strength, we choose
== 14, = SAD (1 Voga-1)²
This is valid choice for Lemma 3.1 since SAD (1 + vCxa 2 SAD (1 Cxa Thus, we arrive the following bound:
E EE= (F(x)) - F(wi))
E, [IVE(S))1N
+[GG+)VV++1AD
VOxa-1y
DT
Tya
(A)
Now, show that the choice of paramters in Theorem 3.1 (i.e. B,g D, defined in the statement) leads each of the underbraced terms is bounded by
(B): Choosing , = =3, = 1 ((GToo) )- ) we have a = (T(ŌTT)) Hence, term (B) is at most E.
(C): Taking D = D, 11-1/221/2 vxxa-1)-1 we have
(C) 161(1+ + VCza-11320 =E
Hence, term (C) is at most Expanding with (TiCTTo) )²
?
we have:
1/2 (1+ 49(G + o0)2
D= D. =
/x
(A): Taking T' 2 aa -1/2g-1 .erm (A) is at most E.
Therefore, we have the following inequality as desired:
E DI (F(x.) F(w.))
E
|VF(E))1
< 32 +
D.T
Finally, let us reconcile these parameter choices with the earlier condition (22) on B. As long as e S
2 (G + Ø). it holds that
1 < 1. implying 3 2 X, which satisfies the condition 3 2 }. Additionally, to ensure 3 < 7 we impose T 2 a
Therefore, the overall condition on T becomes:
T max oaa foa
1/2g-1, a-1} max (To 49(G+o)2 = 49(G + -
This completes the proof of Theorem 3.1.
C. Proof of Corollary 5.1
We first recall the choice parameters from Theorem 3.1 for the reader's convenience.
21

---

Schedule-free SGD is also effective for nonconvex optimization
The discount factor is 8, = - (((++0)
The comparator norm D. - 1/2 (1+ 40(G+o)² vCx The regularization strength is = 22122 (1= 49(G)t))
VCx)
=²
The step size of 3-OMD is G+o D.V1 - 3+.
now show that Cx bounded by First, note that with the above choice of parameters, we have
3.
< c
(24)
+ M/llx
Since e $ (G + d), it follows that 84 2 = Moreover, we have
M.H4
2
D. D.V1- 1.V1-B. B. -2112//1112 11
49(G + o02
VCx
(25)
G+o
8²
2
x
1/12211/2
-211/22112 7[G
(26)
G+o
e2 7
7(G 0)² 4'
S
(27)
This shows that
1 Malt 5-
11/4
B. <
< 4.
(28)
3/4
Thus, from Algorithm 5, we have
|x X1-1 = 116-11:111 for 2 leading to the following inequality:
T
T
T
E
1 = 2F D |, & 16E
|
(29)
which shows that Cx S 16.
Next, we upper bound the sum of loss decrements. We begin with the following decomposition, using the G-Lipschitzness of F:
(((x)) F(w.)) Σ (F(x)) F(W(-1) F(w.-1)- F(ww))
(30)
Σ
G| wi-il++ -((())))F((.))) F(ww))
(31)
Thus, using the closeness property (7) between x; and w,-1, follows that
T
T
E
(((x))
F(w,)) S GE
Σ n ll
+ +E(((w)) - F(Wr)]
(32)
1=1
AF.
(33)
22

---

Schedule-free SGD is also effective for nonconvex optimization
Finally, let substitute this upper bound, together with Cx S 16, back into the inequality in Theorem 3.1. We obtain
E, [IFF(})))
= 3E +
1
E
(F(x)) - F(w)))
D,T
1
3 +
2GD Br + +AF)
D,T
(1+ 42 1/2
49(G+0]2 .Vxx)
S 38 + 2G
DF
7GG o
T
4Ap21/2--11 1/2 (5.
49/G+o) e²
< 48 +
T
provided that 2 49(G + =
Thus, the desired iteration complexity bound follows.
D. Deferred proofs of other results
D.1. Proof of the OMD discounted regret (Lemma 3.2)
To begin, let VI, V2...., VT be sequence of vectors, and consider the quadratically regularized linear loss sequence ( defined as:
WE [T), 4x -v)= 11-112
where the regularization strengths μ4 2 for all E [T] are given and known to the online learner. Since the quadratic regularization term is fully known, it standard for the online learner to incur regret only from the uncertainty in V,-
For instance, Zhang and Cutkosky (2024) demonstrate that a version of composite objective Online Mirror Descent (OMD)
(Beck and Teboulle, 2003; Duchi et al., 2010) provides the following regret bound for chosen decreasing step sizes n) 0 (i.e., 0 < 1 I for all t):
T + 2
Σ (6.) - (u)) S
2
PT+1
||
Σ ?e
(34)
1T
2
See their Theorem 4.1 for details. The version of composite objective Online Mirror Descent (OMD) considered by Zhang and Cutkosky (2024) is initialized with d; = 0 and updated as:
1
6,41 arg min (ve, + 2Mt
1|8
6,112
+
Me+1
[|8]
+
Ø++1
||012
(35)
For more details, see Section 4 therein.
Computing the argmin of the right-hand side, the update rule (35) can be equivalently written as:
8
(ō. Vc).
(36)
1 + 71/411 + 7) n
Now, with the choice v, == Br 1i 3-1 and 1/: 84,,, the update rule (36) becomes:
1
8
1+ 3 m1 + -1 (8. -7g:);
(37)
which, after rearranging, precisely matches (3-OMD) the statement of Lemma 3.2.
23

---

Schedule-free SGD is also effective for nonconvex optimization
Moreover, plugging this choice into the regret bound (34), we get:
Σ (5 gr: Ó. u) - BT+1n + B p1
1
T
1
2
Σ
S
3
g
(38)
2
2
which, after multiplying both sides by B", becomes:
(
T
(8) Regrety T (u) - 8-1
|
2
n
-t
gr
(39)
2
2
t=1
Now let us simplify this into discounted regret bound in Lemma 3.2. Since we have gg discounted regret bound (39) can be further upper bounded as:
S G² + o² for all the
E [Regret (9) (u)]
14 |||
2
1
71
+
2
B
11
3
and
E Regrret (9]
(u)]
11
||u|
2
2
1
(G +
3 11.
2
B
1 3 2
Choosing 7
2| 2 and noticing that the right-hand side no longer depends on T, the discounted regret bound
G+a
becomes:
2 (G)
2 2||u| (G
Vt E [T. E Regret! [+|
(w)
+ ||ul
BVI-
This gives the discounted regret bound given in Lemma 3.2.
D.2. Proof of Proposition 5.1
From the definition the z-iterates (8), holds that
1
Z(+1 (x++1 +
81+1) (xi +
8,)
1
1 --
7
+
81t1 1- 6₁
1-
((1-5+
((
+1) 8141 - 6,
17
gr-
1-
Hence, the desired conclusion follows.
D.3. Proof Proposition 5.2
From the proof of Corollary 5.1 (see Appendix C), we have the relationship:
c2
n-H4. 7(G + o)
(40)
Since 3, = (T(GTT)) we can deduce the following:
8.
(1 - (a) + Matla
(G+o}²
z²
1 G. =1
0
(41)
M//44 + Matti
+ (G+o)
(G k)²
From this, the conclusions of Proposition 5.2 follow.
24


Reviews:
[{"review_id": "gsLAcKtsBl", "reviewer": "Reviewer_vDmv", "summary": "This paper presents a general framework for conversion of any online-learning algorithm into a non-convex (non-smooth) optimization algorithm. The authors provide general non-convex convergence guarantees for the online-to-nonconvex unified framework in terms of the $(\\lambda, \\epsilon)$-stationary point. Their analysis, which applies to any online algorithm with appropriate discounted regret guarantees, is subsequently refined for the case of the discounted online mirror descent algorithm. Furthermore, the authors present three different conversions schemes as special cases of their framework. They show that their last conversion enables the recovery of the schedule-free SGD method.\n\n## Update after rebuttal: \nI thank the authors for their response to my questions. Since my recommendation is already for acceptance, I will keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and suggestions. \n \n\n- The choice of these comparator sequences can be motivated by viewing them as the \"good\" update direction in hindsight. If we ignore EMA averaging in the choice of comparators (for simplicity), we can see that the comparator points exactly in the direction of $\\nabla F(y_t)$, i.e., the ``lookahead'' gradient. Notice that at iteration $t-1$, we do not have access to this gradient, and that's why we call this lookahead.  \n\n\n\n\n- As can be seen from the algorithm, each epoch can be viewed as performing local optimization around an anchoring point. However, if the algorithm spends too much time around the same anchor point, the landscape may remain underexplored, preventing the algorithm from reaching the desired stationary point. Therefore, once the algorithm completes an epoch, it shifts away to explore other regions of the landscape. \n     As mentioned in the paper, this algorithm design has a nice connection to previous nonconvex optimization approaches that repeatedly solve convex subproblems constructed via appropriate regularization (e.g., Chen and Hazan (2024)).", "claims_and_evidence": "All the claims made in this paper are supported by sufficient evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are appropriate for the given problems.", "theoretical_claims": "I looked through the proofs in Appendix C and D and they seem to be correct.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This work extends the online-to-nonconvex framework to recover some popular optimizers, which have been shown to have optimal guarantees. This idea provides insight into the success of these algorithms even for the non-convex non-smooth case and allows for a better understanding of the step size choices of these in practice. This paper also introduces a new random EMA scheme, which is used for the algorithmic output. This method allows (slightly) improved convergence guarantees as compared to previous works selecting the output uniformly at random.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n- This paper follows a good structure, the writing is good and most claims are presented with sufficient explanations to help explain the main results.\n- The designed random EMA iterate is a novel scheme that allows for improved convergence results and is consistent with practical applications.\n- The convergence analysis provided in this work is solid and based on relatively mild assumptions.\n\nWeaknesses:\n- I think including some experimental results possibly in some simple settings could help illustrate the behavior of the presented algorithms and potentially help clarify the advantage of schedule-free methods for non-convex optimization.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. Could the authors give some intuition/explanation about the choice of the comparators for the online learner in Lemma 3.1?\n2. Could the authors elaborate a bit more on the motivation and intuition for the iterates produced by option II and the anchoring scheme?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LVELFTH430", "reviewer": "Reviewer_y9cm", "summary": "This paper introduces a more general online-to-nonconvex reduction. Based on the an OMD variant with discounted regret guarantees, the optimal convergence rate to a $(\\lambda,\\delta)$-stationary point is shown for three different variants. The third variant is shown to coincide with schedule-free SGD algorithm with specific parameter choices. The parameter choices required to achieve optimal rates for this variant of schedule-free SGD correspond to those that lead to the best empirical performance, which was not explained by the theory of schedule-free SGD in the convex setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for encouraging feedback!\nWe do agree that designing and analyzing algorithms for the nonconvex and non-smooth setting is a very interesting direction.\nWe also agree that it's nice to see have strong theoretical guarantees for practical optimizers.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "-", "theoretical_claims": "No.", "experimental_designs_or_analyses": "-", "relation_to_broader_scientific_literature": "The key contribution is the online-to-nonconvex conversion framework which is an extension of the work of Cutkosky et al. (2023). Using this reduction with a specific version of OMD, the authors show that the resulting algorithm corresponds to schedule-free SGD (Defazio et al., 2024), which was only studied in the convex setting before, and achieves  optimal worst-case convergence rates.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Designing and analyzing algorithms for the nonconvex and non-smooth setting is a very interesting direction. Given that SFO works so well in practice, it is very interesting to see that it is optimal for the nonconvex and non-smooth setting and that the parameter choices required to achieve optimal rates for this variant of schedule-free SGD correspond to those that lead to the best empirical performance.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uihms37yl5", "reviewer": "Reviewer_upc5", "summary": "This paper develops a general framework for online-to-nonconvex conversion, which reduces the problem of finding a stationary point of a non-convex objective function to an online learning problem. Their framework extends the work of Zhang & Cutkosky (2024) with a tighter analysis, and it also leads to two new conversion schemes. All three schemes are shown to achieve the optimal convergence rate for nonsmooth, nonconvex stochastic optimization problems. Moreover, the third scheme is shown to have the form of the schedule-free SGD in Defazio et al. (2024). As a result, it complements the convergence analysis for the convex setting in that work and establishes that schedule-free SGD remains optimal in the nonsmooth, nonconvex settings with the proper choice of parameters.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments!\n\n**Regarding the step size comparison.**\n  Thank you for pointing this out. Indeed, the step size of our Schedule-Free algorithm should not be compared with the step size of the OMD, and instead with the ``effective'' step size of the momentum method of Zhang and Cutkosky (2024). We agree with the observation that the stepsizes are of the same order and will update the presentation accordingly. \n\n\n **Regarding $\\kappa_t$.** We acknowledge that our nonconvex analysis adopts a different averaging scheme, using $c_t = 1 - \\zeta$ instead of the original choice $c_t = \\frac{1}{t}$ proposed by Defazio et al. (2024). A more detailed investigation of this difference is an interesting direction for future work, and we will clarify this point in the final version of the paper.\n       \nThat said, our preliminary experiments suggest that the specific choice of $c_t$ has limited impact on the performance of schedule-free methods. For example, when training a ResNet on CIFAR-10, we often find that EMA averaging (as used in our method) results in more stable training compared to the full averaging scheme of Defazio et al. (2024). Here is the link for the experiments https://docs.google.com/document/d/1WBeV1DuS_zTZ6370hfRvQk617NILsp5uWwvD1CYUn74/edit?tab=t.0 .\n\n\nIn contrast, the choice of $\\kappa_t$ plays a much more critical role in practice. Performance degrades significantly when $\\kappa_t$ is set below $0.9$, highlighting the importance of tuning this parameter carefully. Unlike the convex analysis of Defazio et al. (2024), which allows $\\kappa_t$ to be chosen arbitrarily ($\\beta_t$ in their notation), our nonconvex analysis imposes a more realistic constraint and, in this sense, better aligns with the practical settings.\n \n\n**Typos and other suggestions.** Thanks for the suggestions regarding the presentation and pointing out the typos. We will update the paper accordingly.", "claims_and_evidence": "Most claims in this paper are supported by rigorous mathematical proofs. However, I have some reservations regarding the practical insights provided by the analysis. \n- The authors observe that under their framework, the choice of $\\kappa_t$ for schedule-free SGD is close to 1, which aligns with the empirical observations in Defazio et al. (2024). On the other hand, other aspects of the parameter selection do not exactly match practical choices. Specifically, in Defazio et al. (2024), the choice of $c_t$ is independent of $\\kappa_t$ and scales as $1/t$, which is different from the suggestion in Proposition 5.2. Due to this discrepancy, it seems unclear which formulation better explains the empirical success of schedule-free SGD.  \n\n- At the end of Section 5, the authors claim that the learning rate $\\gamma$ for schedule-free SGD is $\\Theta(\\frac{(G+\\sigma)^2}{\\epsilon^2})$ times larger than the optimal step size for SGD with momentum. However, in Proposition 5.2, $\\gamma$ is compared to the **OMD step size $\\eta_*$** for the online learning problem, which does not directly correspond to the step size in SGD with momentum. In fact, as mentioned by the authors, SGD with momentum corresponds to Option I with OMD as the online learner. Following the reformulation in Zhang and Cutkosky (2024), the effective learning rate for SGD with momentum is given by $\\frac{\\beta \\eta}{\\eta \\mu + \\alpha} = \\frac{\\eta \\xi}{1- \\xi}$. Since $\\xi$ is close to 1 in the considered setting, the learning rates only differ by a constant close to 1. Hence, the analysis does not necessarily suggest a much larger learning rate than SGD with momentum.", "methods_and_evaluation_criteria": "This is a pure theoretical paper, and thus empirical evaluation is not applicable.", "theoretical_claims": "Yes, I have checked the proofs in the Appendix, and to the best of my knowledge they are correct, except for some minor typos.", "experimental_designs_or_analyses": "There are no experiments in this paper.", "relation_to_broader_scientific_literature": "Two prior works are most relevant to this submission: \n- The proposed framework can be viewed as an extension to Zhang and Cutkosky (2024). In particular, it adopts the same key concepts (e.g., the approximate Goldstein stationary point and discounted regret) and the key techniques (e.g., the composite objective OMD). In some sense, the current submission presents the analysis from Zhang and Cutkosky (2024) in a more modular way and make the observation that there is some flexibility in choosing the sequence $\\{x_t\\}$ in the update rule. \n- The main contribution of this paper is to establish the optimal convergence guarantees for schedule-free SGD (Defazio et al., 2024), a recently proposed optimizer with strong empirical performance, in nonsmooth and nonconvex optimization. The original paper focuses on the stochastic convex optimization setting with a completely different analysis, and this paper offers a new perspective on the algorithm's design.", "essential_references_not_discussed": "I think the authors did a good job and included the most essential references.", "other_strengths_and_weaknesses": "The paper is well-written and easy to follow. However, one potential concern is that its theoretical contribution may not be significantly more substantial than that of Zhang and Cutkosky (2024), as it builds upon the same key concepts and techniques. While the authors introduce two new conversion schemes within their new framework, all proposed schemes ultimately achieve the same convergence guarantees (up to a constant). This raises the question of what advantages the newly proposed schemes offer beyond the existing approach.", "other_comments_or_suggestions": "For clarity, it may be helpful to briefly review how Option 1 corresponds to SGD with momentum and contrast it with Option 3. This addition would help readers better understand the differences between these two methods. \n\nTypos: \n- Lemma C.1 (Line 645): the denominator in the first term should be $DT$. \n- Lemma C.5: On Line 820, the second expectation should be over $\\mathbf{X}_{\\tau}$. Also, in the proof on Line 832, the left-hand side should be $\\\\|y_s - x_s\\\\|$ instead of $\\\\|w_s-x_s\\\\|$.", "questions_for_authors": "I do not have additional questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EebVu4IrrL", "reviewer": "Reviewer_TSfg", "summary": "This work investigates the effectiveness of schedule-free methods in nonconvex optimization. The authors first develop a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into a nonconvex optimization algorithm. This framework not only recovers existing conversions but also leads to two new conversion schemes. In particular, one of these new conversions corresponds directly to the schedule-free SGD, therefore allowing us to establish its optimal iteration complexity for nonsmooth nonconvex optimization. \nThe analysis results also provide valuable insights into the parameter choices for schedule-free SGD in practical applications.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful question. We agree that a deeper understanding of optimizer behavior ultimately requires incorporating finer-grained properties of the training loss landscape.\n\nThat said, a somewhat surprising takeaway from our work—especially in light of your comment—is that certain practical choices of hyperparameters can already be explained using fairly generic assumptions on nonsmooth, nonconvex losses. This suggests that some aspects of real-world training dynamics may be governed by broader principles.\n\nWe believe that incorporating additional structural assumptions on the loss—closer to the training losses in practice—could further bridge the gap between theory and empirical behavior, and we view this as a promising direction for future work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "May inspire new optimization algorithm design and analysis in nonconvex machine learning.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "This is a solid theory paper on extending the theoretical understanding of schedule-free methods to nonconvex optimization. The main contribution is the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into a nonconvex optimization algorithm. By specifying the choice of sequences, this framework can recover existing conversions and also leads to two new conversion schemes that cover the schedule-free SGD method. Overall, I found the contribution of this work very fundamental, and the developed framework may spark new research directions on nonconvex optimization algorithm design and analysis.", "other_comments_or_suggestions": "Several algorithms (5,6,7) correspond to the same algorithm. It seems that only Algorithm 6 is necessary.", "questions_for_authors": "The authors claim that the analysis result can explain why $\\kappa_t$ should be chosen close to 1 in practice. I don't see a strong evidence here. The theoretical choice of $\\kappa_t \\approx 1$ is to achieve theoretical guarantee in general nonconvex optimization, while the practical choice of $\\kappa_t \\approx 1$ is to achieve the best performance for a specific problem.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: This work develops a general framework for online-to-nonconvex optimization, which converts a given online learning algorithm into a nonconvex optimization method with strong guarantees. Specifically, the proposed framework not only recovers existing conversion schemes but also leads to a couple of new ones, from which a schedule-free SGD method emerges as an output. All the reviewers unanimously agree with the acceptance of the paper and believe that the paper is with rigorous and transparent analysis.
Decision: Accept (oral)