The Road Less Scheduled
Authors: Aaron Defazio
Xingyu Alice Yang
Ahmed Khaled
Konstantin Mishchenko
Harsh Mehta
Ashok Cutkosky
Venue: NeurIPS 2024 oral (2024)
Keywords: Stochastic Optimization
Optimization
Convex Optimization
Learning Rates
Learning Rate Schedules
Primary area: optimization_for_deep_networks
TL;DR: Train without learning rate schedules

Abstract: Existing learning rate schedules that do not require specification of the optimization stopping step $T$ are greatly out-performed by learning rate schedules that depend on $T$. We propose an approach that avoids the need for this stopping time by eschewing the use of schedules entirely, while exhibiting state-of-the-art performance compared to schedules across a wide family of problems ranging from convex problems to large-scale deep learning problems. Our Schedule-Free approach introduces no additional hyper-parameters over standard optimizers with momentum. Our method is a direct consequence of a new theory we develop that unifies scheduling and iterate averaging. An open source implementation of our method is available at https://github.com/facebookresearch/schedule_free. Schedule-Free AdamW is the core algorithm behind our winning entry to the MLCommons 2024 AlgoPerf Algorithmic Efficiency Challenge Self-Tuning track.

The Road Less Scheduled
Aaron Defazio Xingyu (Alice) Yang²
Fundamental Research Team, Meta
Fundamental Al Research Team, Meta
Harsh Mehta Google Research
Konstantin Mishchenko
Ahmed Khaled Princeton University
Samsung Al Center
Ashok Cutkosky
Boston University
Research Co-lead
Engineering Co-lead
Senior Author
Abstract
Existing learning rate schedules that do not require specification of the optimization stopping step T are greatly out- out-performed by learning rate schedules that depend on T. We propose approach that avoids the need for this stopping time by chewing the use of schedules entirely, while exhibiting state-of-the-ar performance compared schedules problems to large-scale deep learning problems. Our Schedule-Fre approach introduces additional "yper-paramette over standard optimizers with momen- tum. Our method is a direct consequence of a new theory we develop that unifies scheduling and iterate averaging. An open source implementation of method is available*. Schedule-Fire Adam is the core algorithm behind our winning entry the MLCommons 2024 AlgoPerf Algorithmic Efficiency Challenge Self-Tunee Seff-Tuning track.
wide family of problems ranging from convex
1 Introduction
The theory of optimization, applied in machine learning, has been successful at providing precise, prescriptive results for many problems. However, even in the simplest setting of stochastic gradient descent (SGD) applied to convex Lipschitz functions, there glaring gaps between what current theory prescribes and the methods used in practice.
Consider the stochastic gradient descent (SGD) step with step size 0, žt+1 = 799h where ge the stochastic (sub-)gradien) at time f, computed at the point 2, (formally defined in Section 1.1) of convex Lipschitz function f. Although standard practice for many classes of problems, classical convergence theory suggests that the expected loss of this sequence suboptimal, and that the Polyak-Rupper (PR) average of the sequence should be returned instead (Polyak, 1990; Ruppert, 1988):
2++1 2t 799t
Jt+1 (1 -++1) + c411
(2)
where using Cc+11 1/(1+ 1) results in T, + - 2t. Despite their theoretical optimality, PR averages give much worse results in practice than using the last-iterate of SGD (Figures 2a.8) folk-law result in the field of optimization, and large theory-practic gap that often attributed to the mismatch between this simplified problem class and the complexity of problems addressed in practice.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

ILSVRC 2012 ImageNet (ResNet-30)
WebTet (GPP2 124M)
3.2
60
Test Loss
3.0
Tast
2.9
2.8
200000
400000
600000
Epoth
Step
Figure 1: Schedule-Free methods (black) closely track the Pareto frontier of loss v.s. training time in single run. Both Schedule-Free SGD (left) and AdamW (right) match or exceed the performance of cosine learning rate schedules of varying lengths (red).
Recently, Zamani and Glineur (2023) and Defazio et al. (2023) showed that the exact worst-case optimal rates can be achieved via carefully chosen learning rate sequences (also known as schedules) alone, without the use of averaging. This result suggests that schedules have, in some sense, the same role to play as PR averaging in optimization. However, schedules have a critical disadvantage: they require setting the optimization stopping time T in advance.
Motivated by the theory-practics gap for Polyak-Ruppert averaging, we ask the following question:
Do there exist iterate averaging approaches that match the empirical performance learning rate schedules, without sacrificing theoretical guarantees?
By developing a new link between averaging and learning rate sequences, we introduce a new approach averaging that maintains the worst-case convergence rate theory of PR averaging, while matching and often exceeding the performance of schedule-basee approaches - firmly answering this question in the affirmative.
Summary of Results
Our approach does not require the stopping time T to be known or set in advance. It closely tracks the Pareto frontier of loss versus training time during single training (Figure 1), while requiring no additional
over the base SGD (with momentum) or
Adam optimizer.
Our approach uses an alternative form of momentum that replaces traditional momentum. This form has appealing theoretical properties: is worst case optimal for any choice of the momentum parameter in the convex Lipschitz setting, property that does not hold for traditional momentum.
Our key theoretical result is new online-to-bateh conversion theorem, which establishes the optimality of our method while also unifying several existing online-to-batch theorems.
We perform, our knowledge, one of the largest machine learning optimization algo- rithm evaluations to date, consisting of 28 problems, ranging from logistic regression to large-scale deep learning problems. This evaluation contains more distinct and diverse large- scale maachne-leearingg problems than any other optimizer evaluation we are aware of in the literature. Schedule-Fit Free methods show strong performance, matching or out- out-performing heavily-tuned cosine schedules.
Schedule-Free AdamW won the MLCommons 2024 AlgoPerf Algorithmic Efficiency Challenge Self-Tuning (Adaptive Algorithm) Track, providing independent verification of SOTA performance against other optimization algorithms in cases where hyperparameter- tuning is limited. We provide details of our entry and plots comparing it to the competition baseline.
1.1 Notation
Consider the stochastic convex minimization mingeR f(x) Ex] Q),, where each f(z, C) is Lipschitz and convex in r, and the expectation is taken over the random variable Ç. With slight abuse of notation, assume we are given, at time step and any point y that we choose, an arbitrary sub-gradient V Vy 4)) from the sub-differential of

---

Laseter Otheren
IWSLT14 4 (LSTM)
5.5
Polyak Averaging (4.35 SE 0.004)
Primal Averaging 44 SE 0.001)
Loss
5.0
Schodu Pmme (4.18 SE 0,001)
Cosine Schedule (4 0.003)
4.5
4.0
10000
20000
30000
40000
50000
60D00
Stop
(b) Incorporating the momentum parameter
(a) Schedule- Free learning converges faster than classical eraging approaches, often perfforrrnnng tuned schedules.
3 allows for convergence despite using larger
learning rates 7 on quadratic problems.
2
Method
We propose the following method, which we call Schedule- Free SGD:
V/ (1 B)zt + Bax,
(3)
2++1 2, 7 >V Ct);
F++1 -11- cc+1) ) + C++12+11
where ct+11 = 11((++1) and 21 æı the initial point. Note that, with this weighting, the x sequence is just a running average of the sequence. The y sequence is the gradient location sequence (on which gradients are evaluated at each step). The z sequence is the base sequence, which is where the base optimizer's update is performed (in this case SGD). The sequence is the evaluation sequence, our best estimate the weights so far.
This method has a momentum parameter / that interpolates between Polyak-Rupper averaging (3 = 0) and Primal averaging (3 1). Primal averaging (Nesterov and Shikhman, 2015; Tao et al., 2018; Cutkosky, 2019; Kavis et al., 2019; Sebbouh et al., 2021; Defazio and Gower, 2021; Defazio and Jelassi, 2022), is an approach where the gradient is evaluated at the averaged point æ, instead of 2:
2++1 2t - -V-7Vf(Ie Gt)
(6)
T++1 = C+11 Be + C4+12++1
(7)
this approach maintains the worst-case optimality of PR averaging but is generally considered to converge too slowly to be practical (Figures 2a.8). The advantage of our interpolation is that we get the best of both worlds. We achieve the fast convergence of Polyak-Rupped averaging (since the z sequence moves much quicker than the x sequence), while still keeping some coupling between the returned sequence x and the gradient-evaluation locations y. which increases stability. Values of 9 similar to standard momentum values 3 as 0.9 appear to work well in practice. We will use the notation a 1 3 when convenient.
In this formulation, 3 = 0.9 gives the practical advantages of momentum, dampening the immediate impact of large gradients, resulting in more stable training. To this, notice that the immediate effect of the gradient at step is to introduce (1 - 8)g; = 0.1g, into the iterate sequence y. This (EMA) momentum, where also (1 B)g, is added into the iterate sequence on step f. However, here the remainder of gi is very slowly added into y over time, via its place in the average whereas with an EMA with / = 0.9. the majority of the gradient is incorporated within the next 10 steps. So from this viewpoint, the Schedule-Free updates can be seen as a version of momentum that has the same immediate effect, but with greater delay for adding in the remainder of the gradient. This form of momentum (by interpolation) also has striking advantage: does not result in any theoretical slowdown; gives the optimal worst case (Nesterov, 2013) convergence for the smo-shooth convex setting (including constants), for any choice of momentum between and inclusive:
similar to ppoonentill-movingavveee
Theorem Suppose a convex function, and SI,..., ., ST an i.i.d. sequence of random variables such that F fx ( 5)) for some function f that is G- G-Lipschitz in x. For any minimizer I., define
3

---

D |0] x.Il and y D/(GTT). Then for any 3 E [0, 11, Schedule-Free SGD ensures:
((((r))F((a)))) DG VT
(8)
In contrast, exponential-movee mwwilll-ooiiiiiooe -oviing-vveraee momentum in the non-smooth setting actually hurts the theoretical corst-case convergence rate. The Schedule-Free approach maintains the advantages of momentum (Sutskever al., 2013) without the potential worst-case slow-down.
2.1 General Theory
The method analyzed in Theorem actually a special-case a more general result that incorporates arbitrary online optimization algorithms rather than only SGD, well as arbitrary time-varying sequences of Br. The proof is provided Appendix
Theorem 2. Let F be convex function. Let S1.-..,<T be iid sequence such that F(x) Eelf(z, {)). Let 21...., be arbitrary vectors and let Wi...., WT and Bi...., 3r be arbitrary numbers [0, 1] such that 26 Wi and 3e are independent of ......, Cr. Set:
W424
W
W2
I(-1
2t
(9)
1=
2i==
===
M/
f -1-ce
y1 = Be + -z)
(10)
9t fyy,
(11)
Then we have for all x.:
EE we (gt, 2t x.)]
E [[F(T)) - =(x.)l
(12)
Σ W0
To recover Theorem 1 from the above result, notice that the algorithm analyzed by Theorem is captured by Theorem 2 with w, 1. 3g constant 8 and 24-1 2 79t for all t. Next, observe that the sequence ....... 2т is performing online gradient descent (Zinkevich, 2003), for which it is well-known that the regret Et= (gt, x.,) (appearing in the numerator of our result) is bounded by DGVT and the result of Thcorem 1 immediately follows.
The regret is the principle object of study in online convex optimization (Hazan, 2022; Orabona, 2019). Viewed in this light, Theorem provides way convert online convex optimization algorithm a form of ouline-to-batee conversion (Cesa- Bess-BBincchi
into a stochastic optimization algorithm: al., 2004). Classical online-to- to-bhtch conversions a standard technique for obtaining convergence bounds for many stochastic optimization algorithms, including stochastic gradient descent (Zinkevich, 2003), AdaGrad (Duchi et al., 2011 AMSGrad (Reddi al., 2018), and Adam (Kingma and Ba, 2014). All of these algorithms can be analyzed as online convex optimization algorithms: they provide bounds on the regret E/= (gt, 2.) rather than direct convergence guarantees. It is then necessary (although sometimes left unstated) to convert these regret bounds into stochastic convergence guarantees via online-to-batch conversion. Our result provides more versatile method for effecting this conversion.
Theorem 2 actually provides a "grand unification" of number of different online-to-batch conversions that have been proposed over the years. Most of these conversion methods were first developed specifically to provide convergence analysis for SGD (or some variant such as dual averaging or mirror descent), and then generalized into techniques that apply any online convex optimization algorithm. For example, the classical Polyak averaging method can be generalized to form the "standard" online-to to-batch conversion of Cesa- Disa-Bii al. (2004), and immediately recovered from Theorem 2 by setting wi = and 3e = for all t. More recently Nesterov and Shikhman (2015): Tao et al. (2018) derived an alternative to Polyak averaging that was later generalized to work with arbitrarily online convex optimization algorithms by Cutkosky (2019); Kavis et al. (2019), and then observed to actually equivalent to the heavy-ball momentum by Defazio (2020); Defazio and Gower (2021): Defazio and Jelassi (2022). This method is recovered by our Theorem 2 by setting

---

wt and Bt = for all t. Finally, very recently Zamani and Glineur (2023) discovered that gradient descent with a linear decay stepsize provides last-iterate convergence guarantee, which was again generalized to online-to-batch conversion by Defazio et al. (2023). This final result is also recovered by Theorem by setting w) = and 8 = (see Appendix B).
In Appendix C, we give further tightening of Theorem 2 it can be improved to an equality by precisely tracking additional terms that appear on the right-hand-side. This tightened version can be used to show convergence rate results for smooth losses, both with and without strong-convexity. As an example application, we show that schedule- free opimistie-gradient methods (Rakhlin and Sridharan, 2013) converge with accelerated rates:
D2L T2
Do
E(F(zr)-F(x.) -
(13)
vT
2.2 On Large Learning Rates
Under classical worst-case convergence theory, the optimal choice of y for a fixed duration training time T is 7 D/(GVT). This is the rate used in our bounds for Theorem above. For any-time convergence (i.e. when stopping is allowed at any timestep), our proposed method can, in theory, be used with the standard learning rate sequence:
D
Nt GVI
(14)
However, learning rate sequences of this form have poor practical performance (Defazio et al., 2023).
Instead, much larger steps of the form D/G give far better performance across virtually all problems in applications (Defazio and Mishchenko, 2023) another seoory-practic mismatch that is virtually undiscussed in the literature. Existing theory suggests that this step-size is too large give O(1/VT) convergence, however, as we show below, there an important special case where such large step sizes also give optimal rates up constant factors.
Theorem 3. Consider the online learning setting with bounded gradients 9t. Let 2++1 24 79t- Let D = || - 2z 2=||.orr arbitrary reference point 2n and define G = max <T [1 Suppose that the chosen step-size is 7 D/C. then if holds that:
T
T
Let - 21) - D
19
11?
(15)
t=1
then:
T
D T
T
ges 2t - 2x) =
1g 3
(16)
This regret bound for SGD implies convergence rate bound for Schedule-Free SGD by application of our online-to-batch conversion. Condition 31 can be checked during training run (Using reference point 2. .T, and so D = ||ا] xrr)) and we find that holds for every problem we consider in our experiments in Section 4. More generally, the full conditions under which large learning rates can be used are not yet fully understood for stochastic problems. In the quadratic case, Bach and Moulines (2013) established that large fixed step-sizes give optimal convergence rates, and we conjecture that the success large learning rates may attributed to asymptotic quadratic behavior of the learning process.
Empirically, we find that Schedule-Free momentum enables the use of larger learning rates 7 even in quadratic minimization problems f(x) = 1 Ar 6 r. We generate 10 different such 20-dimensional problems with eigenvalues drawn log-uniformil in [10-6 1]. We plot the average minimal loss achieved as a function of the two parameters 3 and 7 Figure 2b. We can see that when the learning rate we use is small, what value of 3 we choose has little to no effect on the convergence of the algorithm. However, when y is large, choosing 3 1 becomes crucial to achieving convergence.
5

---

3 Related Work
The proposed method has a striking resemblance to Nesterov's 's accelerated method (Nesterov, 1983, 2013) for L-smooth functions, which can be written in the AC-SA form (Lan, 2012):
Y/ (1 C4+1)2+ ct+1
(17)
k - (((e)
20+1 = 2t 2L
(18)
T++1 (1 (1+1)= tt + C+41 1++1,
(19)
where G++ = 2/( 22. The averaging constant, and more generally
C++1 t+++1
(20)
for any real r > -1 is equivalent to the weighted average (Shamir and Zhang, 2013; Defazio and Gower, 2021) 2, Σi= t" 22, where t" represents the rth factorial power of t. Our framework is compatible with factorial power averages without sacrificing theoretical guarantees.
Our approach differs from conventional accelerated methods by using a different weight for the yr and xy interpolations. We use constant weight for ye and a decreasing weight for z₁. Accelcrated methods for strongly-convex problems convex use an decreasing weight for both, so our approach doesn" 't directly correspond to either class of accelerated method. Accelerated methods also use a much larger step size for the sequence than our approach.
constant weight for both, and those for non-strongly
The use of equal- weighted averages is less common than the use of exponential weighting in the practical deep learning optimization literature. Exponential moving averages (EMA) of the iterate sequence are used in the popular Lookahead optimizer (Zhang et al., 2019). In the case of SGD, it performs 11... inner steps:
Trj = -1,i-1 - V (2
(21)
followed by an outer step:
3t = 11-1 + a (Zt,k - 54-1))
(22)
The inner optimizer then starts 2,0 Tt-1- The Lookahead method can be seen as the EMA version of primal averaging, just as exponential weight averaging is the EMA version of Polyak-Ruppert averaging.
Tail averaging, either using an exponential moving average or an equal-weighted average, is a common 'folk-law' technique that often yields a practical improvement. For instance, this kind of averaging is used without citation by the influential work of Szegedy et al. (2016): "Model evaluations are performed using rumning average of the parameters computed over time.". and by Vaswani et al. (2017): " averagee the last 20 checkpoints". Tail averages are typically PFoyakk-Rupper style averaging as the average is not used for gradient evaluations during training.
More sophisticated tail averaging approaches such as Stochastic Weight Averaging (Izmailov et al., 2018) and LAtest Weight Averaging (Kaddour, 2022; Sanyal et al., 2023) combine averaging with large or cyclic learning rates. They are not a replacement for scheduling, instead they aim to improve final test metrics. They generally introduce additional hyper-parameters to tune, and require additional memory. It is possible to use SWA and LAWA on top of our approach, potentially giving further gains.
Sandler et al. (2023) show via a stochastic quadratic analysis framework that averaging and learning rate decreases achieve the same effective learning rate. For instance, and average of two points along the training trajectory can give almost identical results to using a learning rate two times smaller. Stochastic quadratic problems particularly special, Bach and Moulines (2013) have shown that Polyak averaging gives optimal ((1/T) rates without the use of decreasing dependent step size sequences in this setting.
Within optimization theory, tail averages can be used improve the convergence rate for stochastic non-smooth SGD in the strongly convex setting from O(log(T)TT) to O(1/T) (Rakhlin et al., 2012),

---

although at the expense of worse constants compared to using weighted averages of the whole sequence (Lacoste-Julien et al., 2012).
Portes et al. (2022) use eyclic learning rate schedules with increasing cycle periods to give a method that explores multiple points along the Pareto frontier of training time vs eval performance. Each point at the end of a cycle is an approximation to the model from a tuned schedule ending at that time. Our method gives the entire frontier, rather than just few points along the path. In addition, our method matches or improves upon best known schedules, whereas the cyclic trade-off curve underestimated the standard trade-off curve by a margin of 0.5% validation accuracy" (Portes et al., 2022).
4 Experiments
For our deep learning experiments, we evaluated Schedule- Free learning set benchmark tasks that are commonly used in the optimization research literature:
CIFARIO A Wide ResNet (16-8) architecture (Zagoruyko and Komodakis, 2016) on the CIFARIO image classification dataset.
CIFARIO0 A DenseNet (Huang et al., 2017) architecture on the CIFAR-100 (100-class) classification
dataset.
SVHN A deep ResNet architecture (3-96) on the Street View House Numbers (SVHN) dataset. ImageNet A standard ResNet-50 architecture (He et al., 2016) on the ILSVRC 2012 ImageNet
(Russakovsky et al., 2015) classification dataset.
IWSLT14 A LSTM architecture (Wiseman and Rush, 2016) on the IWSLT14 German-English translation dataset (Cettolo et al., 2014).
DLRM The DLRM (Naumov et al., 2019) architecture on the Criteo Kaggle Display Advertising dataset (Jean-Baptiste Tien, 2014).
MRI A stacked U-Net architecture (Sriram et al., 2020) on the fastMRI dataset (Zbontar et al., 20.
MAE Fine-tuning a pretrained Masked Autoencoder (He et al., 2021) ViT (patch16-512d on the
ILSVRC 2012 ImageNet dataset.
GP A 124M parameter GPT-2 (Radford et al., 2019) style decoder-only transformer on the OpenWeTText dataset (Gokaslan and Cohen, 2019).
For each problem, both the baseline and the Schedule-Free method were tuned by sweeping both the weight decay and learning rate on a grid. We also swept 3 over two values, 0.9 and 0.98. Final hyper-parameters are listed in the Appendix. Schedule-Free SGD was used for CIFARIO, CIFARI00, SVHN and ImageNet, and Schedule-Free AdamW (Loshchilov and Hutter, 2019) was used for the remaining tasks. We further include a step-wise schedule as comparison on problems where step-wise schedules are customary. Further results for Polyak and Primal averaging are in Appendix I.
Our approach shows very strong performance (Figure 3) uer-perforing existing state-of saae-off-the-rt -th--art cosine schedules on CIFAR- 10, CIFAR- SVHN, IWSLT-14 (Figure 2a) and WebTee GPT-2 problems, as well as the state-of-the-arr Linear Decay schedules on the fastMRI and Criteo DLRM tasks. On the remaining two problems, MAE fine-tuning and ImageNet ResNet-50 training, it ties with the existing best schedules.
In general, the optimal learning rates for the Schedule-Free variants were larger than the optimal values for the base optimizers. The ability to use larger learning rates without diverging may be contributing factor to the faster convergence of Schedule-Free methods. The / parameter works well at the default value of 0.9 for all problems except NanoGPT, where the loss started to increase rapidly when 0.9 was used (similar to the Polyak Averaging results in Appendix D). The larger 3 0.98 value in our sweep was stable
4.1 MLCommons Algorithmic Efficiency benchmark
The AlgoPerf challenge (Dahl et al., 2023) is designed to be a large-scale and comprehensive bench- mark for deep learning optimization algorithms, covering major data domains and architectures. It includes Transformers, ConvNets and U-Net models across image, language, graph and speech domains, and contains 8 problems total. We evaluated Schedule- -Fre AdamW following the com- petition guidelines, comparing against NAdamW, the competition reference Algorithm, running 10 seeds of each. As this is a time-to-target competition, traditional error bars are not appropriate so we instead plot all 10 seeds separately. Note that we excluded one benchmark problem, 5e training. neither AdamW nor NAdamW can hit the target accuracy on that task.
7

---

CIRAR-1O (WAN-16-8)
CITAR-100 (DenseNitt
80
93
Tout Aocureeyy [44]
80
Free
Scheddlee Free
Tree
Step
0.033
10
Step-Wise Sctedtie 176.41% 0.34
Conlie Schweade 185, Sit 0.04)
Costaee Schodale (77.41% SE 0.09)
73
40
100
2,50
100
200
Eprch
SVIU (ResNet-3-66)
ILSVRC 2012 Imaag (RuoNae-50)
08
(eett Arturracy (h1
60
96
Schedule Free 80% SE 0.01)
Cosksee Schodulu (76. (76.90% 0.06)
Stag-AVise Schwdulee (98.20% SR: 2.01
Stop Wise Sciedule 176.40% SE 0.01)
94
40
100
230
Epoch
TURMEE Koswe (VariNet 2.0)
Kagple (DLRM)
0.790
Text: Netumry
0.985
Oesine Schodule 0.0015:
0.780
Schodulc Free (0.9112 3.0000))2)
SchwdoleePoen jo. 22.815 conzo)
Epoch
Epoch
MAE ImageNet Pinetune (VIT)
Open
3.2
Couine Schadule (2.853 SE 0.904)
80
3.1
Scheduls-Frou 12:831 SE 0.008)
3.0
70
Scheddule-Pree 54 (.C.3)
2.8
Epoch
Step
Figure 3: Deep Learning Experiments
The self-tuning track restricts participants to provide single of tyyper-parametee use for all 8 problems. Given the large number of problems, this gives performance representative of a good default configuration.
Schedule-Free Free Adam W performs well across all considered tasks, out-performing the baseline on the WMT, VIT, FASTMRI and OGBG training, while tying the Conformer and Criteo workloads, and marginally mnderrpprforming on the DeepSpeech workload. We attribute the performance on the Conformer and DeepSpeech tasks to their use of batch-norm the AlgoPerf setup doesn't easily allow us to update the BN running statistics on the x sequence, which is necessary with our method to get the best performance (See Section 4.3).
4.2 Convex Problems
We validated the Schedule-Free learning approach on a set of standard logistic regression problems from the LibSVM repository. For each problem, and each method separately, performed full learning rate sweep on a power-of-two grid, and plotted mean and standard-error of the final train accuracy from 10 seeds using the best learning rate found.
Schedule-Free learning out-performs both averaging approaches and the state-of-the-arr linear decay (LD) schedule baseline (Figure 7). It converges faster on all but of 12 problems. has higher accuracy on the problems, and ties the baseline on the remaining problems. This demonstrates that the performance advantages of Schedule- Free methods are not limited to non-convex problems.
4.3 Implementation Concerns
The Schedule-Free variant of a method typically has the same memory requirements as the base method. For instance, Schedule-Free SGD requires no extra memory over standard SGD with momentum. Whereas SGDM tracks the current point x and the momentum buffer m, we can track and z. The quantity y can be computed directly from the latest values of z and and so doesn't 't need

---

WMT
Normalisd Thee MAree
VI7
Normatize Thee MAtre
2.000
0.8
0.75
Nornaied
0.50
0,945
0.8
Nodamit Beseline
Sahedull Pree
0.25
NidureWW Baseline
Schrduli-Sree
Mi-oorlW Swonline
dule Free
0.590
0.6
Normaliod Time
Nomallond Time
Nommaloed Time
Nottalled Ttet Meide
Nomaalnd Tast Motile
1.00
1.0
0.81
03998
0.98
Schodalee Sree
NAdborW Baseline
0.7
> Adummi Suatims
Scthedidn-Tree
Sc Schedulee Sree NAdimn Baoniin
0.97
0.6
0.066
0.2
0.5
D/4
Normation Toxt Meo.Meedee
Librispeeoh Doopsprech
1.00
Schodude
NAdamW Swenline
0.0
0.4
0.4
0.0
Noctralized Time
Figure 4: Schedule-Free Adam compared to target-setting baseline on the Algoperf competition self-tuning track.
Algorithm 1 Schedule-Free AdamW
1: Input: Z1, learning rate y, decay X, warmup steps T Tarmup B1, B2,
2: 21 = 21
3: to 0
4: for = 1 to do
5:
Yt (1 -B1)2, FT
Momentum via interpolation A Gradient is evaluated at
6:
Jr E @f( (t)
7:
Ut B2U2-1 + (1 B2)97
8:
Tt 7 TV - -13 min 1,1/7 warmup)
L.R includes warmup and Adam bias-correction
9:
z++ = -httt/ Pn9t:(lV (Vu + 70h
7?
10: G+1 El 77
11: Tt+1 = (1 C(+1) De + 14+1
b. Update weighted iterate average
12: end for
13: Return XT
xx
be explicitly stored. It's also possible to instead store and y, and then compute when needed. This low memory usage is the case for Adam also, see Algorithm 1.
Our efficient PyTorch implementation actually parameter buffer to store either x or y. with the stored quantity flipping between the two for training and test/inference passes.
buffer always store and the primary
Our method requires extra code to handle models where batch norm is used. This is due to the fact that BatchNorm layers maintain running mean and running var to track batch statistics which is calculated at y. For model evaluation, these buffers need to updated to match the statistics on sequence. This can be done by evaluating small number of training batches using right before each eval. More sophisticated approaches such as PreciseBN (Wu and Johnson, 202 1) can also be used. This calculation is not needed for other normalization layers that do not use batch-statistics.
Learning rate warmup is still necessary for our method. We use linear warmup for a fixed duration, and fuse the Adam bias-correction term into the learning rate for simplicity (this po- tentially impacts the effect of weight- decay during early iterations), giving a learning rate LR Yt = /Vi 3 min(1, ( 4/Twampp)) that approaches 7 when the warmup and bias-correction period ends. We found that performance greatly improved by using weighted e sequence when

---

ILSVIG 2012 ImageNet (leesNet550) Learning Nate Sweep
ILSVIC 2012 ImageNet (tesNet--00)
That Accacaay U%0
75
75
Test Acturarrryy
Schwdule-Frow EA (7..77 SE 0.88)
SGB LR 0.5 (78.42% SE 0.05:
70
Schedule Uree 1773.1177.99 0.05:
70
0.03:
Schodule-Pree Free LR (77.85% SE 0.03)
SQD LR 0.15 (77,57% SE 0.02)
65
SchedullsProw 1.R 1.0 42% 0.02)
65
SGD L.R 0.1 (77.88% SE n.04:
Schedule Vree 176.17 0.072
(77 SE
60
60
25
50
75
100
125
150
175
200
25
100
125
150
175
200
Upoch
Epoch
Figure 6: Comparison of the LR sensitivity of Schedule-Free training and cosine schedule training
warmup is used, weighted by the square of the " used during warmup:
7
C++1
(23)
This sequence decreases at a 1/6 rate after the learning rate warmup. shifted by one from the indexing used in Theorem 2, which is done to simplify the implementation. This sequence is motivated by Theorem 2's weighting sequences, which suggest weights proportional polynomials of the learning rate. This sequence was used for both SGD and AdamW experiments.
Weight decay for Schedule-Free methods can be computed at either the y or sequences. We used decay at y for our experiments, as this matches the interpretation of weight-decay the use of an additional 1-2rreullrrieer term the loss. We found that computing the regularization at y gives significantly better performance on some problems including ImageNet and NanoGPT training.
Parameter Sensitivity
For Schedule-Free learning to be truly schedule- free, it's important that the momentum hyper- parameter doesn't implicitly have dependence on the time-horizon. If tuning this parameter gave different values depending on the train- ing duration, then the problem of setting the
ILSVRC ImageeNat (BoeNNat-50) Strapp
That.Acccuncc 190
Scbadale-Pees MIM (76.
Schadale-Poes (77.
Schadale-Foww NOM (76.99944 0.66)
Sohwehll--ree MDM 0.98 (75.3 58 0.00)
horizon has just been shifted to setting the mo- mentum value. In Figure 5 we run ImageNet training with Schedule- Fheee SGD for longer- sten-standard 200 epochs with a variety of mo- mentum values, with the LR fixed to 1.5. We
60
25
50
76
100
125
150
175
200
Epoch
Figure Sensitivity to momentum values
find that the best choice of momentum (3 = 0.9) is the same for all durations of training.
Schedule-Free learning has similar mild time-horizon dependency for the baseline learning rate value as schedule-bard approaches. Figure 6 shows that the optimal learning rate stays the same for broad range of values, for both Schedule-Free and Schedule based training. For short duration training (5 25 epochs), larger LR values begin to show the best performance. Appendix shows the sensitivity of the final test accuracy to the baseline learning rate for selection of our test problems, in comparison to the baseline optimizer with a cosine schedule. We see that the overall sensitivity is similar to the baseline optimizer in each problem.
6 Conclusion
Two roads diverged in a wood, and I- took the one less traveled by, And that has made all the difference. - Robert Frost
We have presented Schedule-Fre learning, an optimization approach that removes the need to specify a learning rate schedule while matching or outperforming schedule-based learning. The primary practical limitation is the need to sweep learning rate and weight decay, as the best values differ from the those used with schedule. We provide preliminary theoretical exploration of the method, establishing its worst-case optimal performance for non-smooth Lipschitz convex optimization.
10

---

Funding Acknowledgments
AC supported by NSF grant number CCF-2211718.
References
Bach, F. and Moulines, E. (2013). Non-strongly-convex smooth stochastic approximation with convergence rate ((1/n). In Burges, C., Bottou, L.., Welling, M., Ghahramani, Z., and Weinberger, K., editors, Advances Neural Information Processing Systems, volume 26. Curran Associates, Inc.
Cesa-Biand Bian-Biacchi, N., Conconi, A., and Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 5009)22000-2057.
Cettolo, M., Nichues, J., Stüker, S.. Bentivogli, L., and Federico, M. (2014). Report on the 11th IWSLT evaluation campaign. In /WSLT.
Chiang, C.-K., Yang, T., Lee, C.-., Mahdavi, M., Lu, C.-J,, Jin, R., and Zhu, S. (2012). Online optimization with gradual variations. In Conference on Learning Theory, pages 6-1. JMLR Workshop and Conference Proceedings.
Cutkosky, A. (2019), Anytime online-to-batch, optimism and acceleration. In International conference on machine learning. pages 1446-1454. PMLR.
Dahl, E., Schneider, F., Nado, Z., Agarwal, N., Sastry, S., Hennig, P., Medapati, S., Eschenhagen, R., Kasimbeg, P., Suo, D., Bae, J., Gilmer, J., Peirson, A. L., Khan, B., Anil, R., Rabbat, M., Krishnan, S., Snider, D., Amid, E., Chen, K., Maddison, C. J., Vasudev, R., Badura, M., Garg, A., and Mattson, P. (2023). Benchmarking Neural Network Training Algorithms.
Defazio, A. (2020). Momentum via primal averaging: Theoretical insights and learning rate schedules for non-convex optimization.
Defazio, A., Cutkosky, A., Mehta, H., and Mishchenko, K. (2023), When, why and how much? adaptive learning rate scheduling by refinement.
Defazio, A. and Gower, R. M. (2021). The power of factorial powers: New parameter settings for (stochastic) optimization. In Balasubramanian, V. N. and Tsang, I,, editors, Proceedings of The 13th Asian Conference on Machine Learning, volume 157 of Proceedings of Machine Learning Research, pages 49-64, PMLR.
Defazio, and Jelassi, S. (2022). Adaptivity without compromise: momentumized, adaptive, dual averaged gradient method for stochastic optimization. Journal of Machine Learning Research, 23:1-34.
Defazio, A. and Mishchenko, K. (2023). Learning-rate-free learning by D-adaptation. The 40th International Conference Machine Learning (ICML. 2023).
Duchi, J., Hazan, F.,, and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61).
Gokaslan, A. and Cohen, V. (2019). Openwebtext corpus. http://Skkyioon007, .1177.gitin github. io/ OpenWebTexttCrruus
Hazan, E. (2022). Introduction to online convex optimization. MIT Press.
Hazan, E. and Kale, S. (2010). Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine learning, 80:165-188.
He, K., Chen, X., Xie, S., Li, Y., Dollár, P., and Girshick, R. (2021). Masked autoencoders are scalable vision learners. 111:7:2111.06377.
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition.

---

Huang, G., Liu, Z., Van Der Maaten, L., and Weinberger, K. Q. (2017), Densely connected convolu- tional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2261 2261-2269.
Izmailov, P., Podoprikhin, D., Garipov, T., Vetrov, D., and Wilson, A. G. (2018). Averaging weights leads to wider optima and better generalization. Conference on Uncertainty in Artificial Intelligence (UAI).
Jean-Baptiste Tien, joycenv, O. C. (2014). Display advertising challenge.
Joulani, P.. György, A., and Szepesvári, C. (2017). A modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, and variational bounds. International Conference on Algorithmic Learning Theory, pages 681-720 PMLR.
Joulani, P., Raj. A., Gyorgy, A., and Szepesvári, C. (2020). A simpler approach to accelerated optimization: iterative averaging meets optimism. In International conference on machine learning, pages 4984 4993-4993. PMLR.
Kaddour, J. (2022). Stop wasting my time! saving days of ImageNet and BERT training with latest weight averaging.
Kavis, A., Levy, K. Y., Bach, F, and Cevher, V. (2019). UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32.
Kingma, D. P. and Ba, J. (2014). Adam: a method for stochastic optimization. In International Conference on Learning Representations.
Lacoste-Julien, S., Schmidt, M., and Bach, F. (2012). A simpler approach to obtaining an o(1/t) convergence rate for the projected stochastic subgradient method.
Lan, G. (2012). An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(1):365-397.
Loshchilov, I. and Hutter, (2019). Decoupled weight decay regularization. International Conference Learning Representations.
Naumov, M., Mudigere, D., Shi, H. M., Huang, J.. Sundaraman, N., Park, J., Wang. X., Gupta, U., Wu, C., Azzolini, A. G., Dzhulgakov, D., Mallevich, A., Cherniavskii, I., Lu, Y., Krishnamoorthi, R., Yu, A., Kondratenko, V., Pereira, S., Chen, X., Chen, W., Rao, V., Jia, B., Xiong, L., and Smelyanskiy, M. (2019). Deep learning recommendation model for personalization and recommendation systems. CoRR.
Nesterov, Y. (1983). A method for solving convex programming problem with convergence rate O(1/k2). Soviet Mathematics Doklady.
Nesterov, Y. (2013). Lectures on Convex Optimization. Springer Nature.
Nesterov, Y. and Shikhman, V. (2015), Quasi-monotone subgradient methods for nonsmooth convex minimization. Journal of Optimization Theory and Applications, 165(3):917-940.
Orabona. F. (2019). A modern introduction online learning. arXiv preprint arXiv:1912.3321..
Polyak, B. (1990). New stochastic approximation type procedures. Avtomatica i Telemekhanika. 7:98-107.
Portes, J., Blalock, D., Stephenson, C., and Frankle, J. (2022). Fast benchmarking of accuracy vs. training time with eyclic learning rates.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019). Language models are unsupervised multitask learners. Technical report, OpenAI.
Rakhlin, A., Shamir, O., and Sridharan, K. (2012). Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference International Conference Machine Learning.
12

---

Rakhlin, A. and Sridharan, K. (2013). Online learning with predictable sequences. In Conference on Learning Theory, pages 991-1019. PMLR.
Reddi, S. J., Kale, S., and Kumar, S. (2018). On the convergence of Adam and beyond. In International Conference on Learning Representations.
Ruppert, D. (1988), Efficient estimations from a slowly convergent Robbins- Monro process, Technical Report, Cornell University.
Russakovsky, O., Deng, J., Su, H.. Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla,
A., Bernstein, M., Berg, A. C.,, and Fei-Fei. L. (2015). ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (ICV)), 115(3).
Sandler, M., Zhmoginov, A., Vladymyrov, M., and Miller, N. (2023). Training trajectories, mini-batch losses and the curious role of the learning rate.
Sanyal, S., Neerkaje, A., Kaddour, J., Kumar, A., and Sanghavi, S. (2023). Early weight averaging meets high learning rates for LLM pre-training.
Sebbouh, O., Gower, M., and Defazio, A. (2021). On the (asymptotic) convergence of stochastic gradient descent and stochastic heavy ball. In Conference on Learning Theory, COLT 2021, Proceedings of Machine Learning Research. PMLR.
Shamir, O. and Zhang. (2013). Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In Proceedings of the 30th International Conference on Machine Learning.
Sriram, A., Zbontar, J., Murrell, T., Defazio, A., Zitnick, C. L.. Yakubova, N., Knoll, F., and Johnson, P. (2020). End-to-end variational networks for accelerated MRI reconstruction. In International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer.
Sutskever, I., Martens, J., Dahl, G., and Hinton, G. E. (2013). On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on International Conference on Machine Learning Volume 28. JMLR.org.
Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., and Wojna, (2016). Rethinking the inception architecture for computer vision. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2818-2826.
Tao, W., Pan, Z.,, Wu, G., and Tao, Q. (2018). Primal averaging: A new gradient evaluation step to attain the optimal individual convergence. IEEE Transactions Cybernetics, PP:1-11.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u. and Polosukhin, (2017). Attention is you need. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
Wiseman, S. and Rush, A. M. (2016). Sequence-to-sequence learning as beam-search optimization. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics.
Wu, Y. and Johnson, J. (2021). Rethinking "batch" in batchnorm.
Zagoruyko, S. and Komodakis, N. (2016). Wide residual networks. In Proceedings of the British Machine Vision Conference (BMVC).
Zamani, M. and Glineur, F. (2023), Exact convergence rate of the last iterate in subgradient methods.
Zhontar, J., Knoll, F., Sriram, A., Muckley, M. J., Bruno, M., Defazio, A., Parente, M., Geras, K. J., Katsnelson, J., Chandarana, H., et al. (2018). 8). fastMRI: An open dataset and benchmarks for accelerated MRI. arXiv preprint arXiv: 10t.11881..8899
Zhang, M., Lucas, J., Ba, J., and Hinton, G. E. (2019). Lookahead optimizer: k steps forward, step back. In Wallach, H., Laroceele,, H., Beygelzimer, A., d'Alché-Bue, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc
13

---

Zinkevich, M. (2003). Online convex programming and generalized infinitssimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, pages 928 928-935.
14

---

Contributions
Aaron Defazio discovered the method, led research experimentation and proved initial versions of Theorems 1 and 7, with experimental/theorttical contributions by Alice Yang. Alice Yang led the development of the research codebase. Ashok Cutkosky proved key results including Theorem and led the theoretical investigation of the method. Ahmed Khaled developed preliminary theory for obtaining accelerated rates which was later supplanted by Theorem 2, and investigated the utility of with large learning rates for quadratics. Additional derivations by Konstantin Mishchenko and Harsh Mehta are included in appendix sections. Discussions between Aaron Defazio, Ashok Cutkosky, Konstantin Mishchenko. Harsh Mehta, and Ahmed Khaled over the last year contributed to this scientific discovery.
A Proof of Theorem 2
Theorem 2. Let F be a convex function. Let Si..... ,r be an iid sequence such that F(x) = Ez[f(z, {)]. Let 21....,22 be arbitrary vectors and let Wi...., wr and $.,..., 31 be arbitrary numbers [0, 1] such that 24 W4 and Be are independent of Se...., Sr. Set:
Ei Ei
W3Zi
We
Wt
21
xt-1
28
(9)
W/
Eim1 W/
Vt Brx + -B:)20
(10)
9r V((ee Cc).
(11)
Then we have for all x.:
EI Wi (gt, 21 x.)]
E[F(oT) - 5
(12)
Σ W;
Proof. Throughout this proof, we will use the notation showing the following identity:
Et= Wi The result is established by
w. (V)()) xx)). Where here (y:) indicates a subgradient of F at with R[g [ = VF(v:). Given the identity
(1,)F(xt)) Wia- -
(24)
(24), we over all / from to T. Then the LHS will telescope obtain:
(F(r))
Σ w. (VF())) 2 x.),
from which the conclusion immediately follows since Elg. [4] Fv.)). So, let establish (24). To do so, it will help to observe the following identities:
Wt = W1t Wi:t 1Zt-1
W1.- (0+ Iz-1) Wul Iz))
(25)
Be
2t
Br
(v+ Iz)-
(26)
Now, setting F((x;) to be an arbitrary subgradient of at 2t, we have:
(1=FF(;;) W1: 1 wo F(x.)
= 1 - F( + w/( (F(z)) - F(x+))
w: (F(xt) F(x))) < ( x1
using (25):
w, (VF(It)) 21 xx) + (i F(x.))
w., (VF(I)) xz) + un (F(x)) F(u))) + w: (F F(x+))
S (VF Ix)) + wi (VF(x:), xt y1) + we (.F U: x.a)
= =VF(VF(E)) - -V(()). 2 - + ( (V F (Vt)). -x,)
15

---

using (26):
Be (VF()))) VVF()))VF(())). V1 rz) + w. (B))), 2 -x.) 1- 3,
Finally, recall that any convex function satisfies (VF(6) (F - 0 for all a, b. This classical fact can be established by adding the following two subgradient identities:
F(a) 2 F(b) + (VF(b), b), (()) F(a) (VF()), a).
Then, since 3e [0, 1], we have 1-1 desired identity (24).
8, FV)())) (v:);) Vt 22) S 0, which establishes the
B Recovering Prior Conversions, and Connections to Momentum
The following recursions provide an equivalent update to our main algorithm that casts the update in more "momentum-like" like" form.
Theorem 4. Under the same assumptions and notation as Theorem 2, set:
A: 2t+1 kt.
m. It+1 It.
Vt+1 ye-
Then:
W1+1W1:t1
W++1 A.
m, Wy W0:11:111
m4-1
W1++1
Wid
d4 B: (Be Bu+1)
m + (1 3,)
Wi+1
Here in is playing the role of the "update vector", the sequence of points Yt where will be evaluating gradients. The A, value can be interpreted as a "base update" value: for the case that the 2, sequence specified by SGD in Theorem 1). A, === -9 Thus, the update can be interpreted as momentum term m, plus an extra "push" in the direction of A, scaled by 1 - -r.
Proof. Let's solve for my in terms of previous values:
m, Tz+1
Tt.
W4+1
(ze+1 2z,)
Wi.-1
Wr+1
(A, 2t xit)
w1:-1
Wi+1
(Ae
W1it-1
(I), It-1))
w1:t-1
Wi
W4+1
11-1W11-11 m4-1
+ W++1 A.
WyW1::11
W11+1
Now let's solve for ue:
U B1418141 + (1- B141) BL3 (1 - Bi)
Bym, (1 13,4,, (B, B1+1) (2e41 x(++1
Bym, + (1 - (Be -B+1)) Wi:
(x1+1 Izt)
Wi+1
Wid
-mm, + -,,,,,, + (B, - -B411
W4+1
= -(Ba + (8. - Bet1)
Widt
mi + - (1-3:)
wi+1
16

---

In the special case that wi = 1 for all t. the updates simplify to:
-
m4 + m4-1 +
t+1 A.
(Be 1B3 Be+1)) m4 + (1 3.)
In the special case that 3, = for I, the update for ue simplifies to:
Ur = 8m, + (1 -)
From this, it is clear that if 3 1 and wi = 1, then recover the standard Polyak momentum with
[-1 a time-varying momentum factor my 1+1 m + 1 Ac, while if 3 = 0, then we have ordinary SGD without momentum.
#1
B.1 Recovering Linear Decay
Let's take look at the update for 0t 1/++1 - in the special case that w, for all
Up = (3, + ((, B)+1) m, + (1 B,) Let us define a, 1 Bt. Then we re- re-write this update
"4 (1 a, f(a--1 at)) me + an
looks like we might be able to set (; such that the coefficient of me vanishes. In this case, a would play the role of "schedule" the update would just be u4 a, Solving the recursion we get:
0₁ - 1 = [(a++1 - at),
(t + 1)
0++1
Amazingly, this recursion is satisfied by at = I-t which is the linear decay schedule! Notably, this schedule has ar = O, which in turn implies that yr 2T, that the last iterate of our algorithm is Ir, for which Theorem provides a convergence guarantee.
The recursion is also satisfied by Notably, this recursion shows that a₁ will determine all subsequent a values. The values will decease linearly to zero, and then they will try to negative, which is not allowed. So the linear decay schedule the value of an that "just barely" allowed since hits zero at aT.
1 for all (which recovers standard Polyak-Rupper averaging).
In general with arbitrary Wx, the recursion is:
W1dt 0.
a (a141 at)
W1+1
If insist that or (so that yr xT and we get "last iterate" guarantee), then solving the recursion yields:
Wh+1-7
Wi.
which exactly recovers the main result of Defazio et al. (2023).
C Generalizing Theorem 2 via Bregman Divergences
Here, we provide a generalized version of Theorem 2 in the style of Joulani al. (2020). This result employs Bregman divergences to tighten the inequality of Theorem 2 to an equality.
Theorem 5. Let F' be convex function. Let St...., ST be sequence of i.i.d. random variables, and let g be a function such that EEg((x, G:) E (x) for all x and Let 21...., 2r be arbitrary vectors and let Wi,..., WT and a1...., .T be arbitrary non-negative real numbers with < 1 such that 2t, Wi and as are independent of CI. Define the Bregman divergence of F as By(a, F(a) - F(b) (VF(b), b) Set:
Ft = E Wi
R4-1 (1
(1-
W't
+
W's
2t
Σ Wt
El= W/g
Σ
W/
3: at). + a,
g: = g(v, Gi)
2if F' is not differentiable, then by abuse of notation define FF(() = E[g(b, {)), which is particular choice of subgradient of F.
17

---

Define the "compressed sum" notation: Wi:t = Ei=ı with w1o = 0.
Then have for all Nz:
Σ 1
Wi (gt, 21 - I.a
E[F(TT) - F(x,)) = E
W1.T
Ei=1 we By(ye, xx) w1 Br (Tts y/b
ai
W1.T
Lt=l 1int-1pp(x--11 + wy BF (F
E
W1.7
Let's take minute unpack this result since is depressingly complicated. Recall that the Bregman divergence for convex function must be positive, and so all the subtracted Bregman divergence terms can be dropped to make the bound only looser. This recovers Theorem 2. However, Section D, we show how to exploit the negative Bregman terms to achieve accelerated rates when F is smooth, and in Section we show how to exploit the negative Bregman terms to achieve faster rates when F strongly-convex.
Proof. The proof is nearly the same as that of Theorem 2. The only difference is that we keep track of all the error terms in the inequalities via Bregman divergences.
Throughout this proof, use (x))) indicate Eg [1(, {)]. When F differentiable, this is simply
the ordinary gradient at x. When F is non-differentiable, this reprents specific choice of subgradient æ.
Recall that any convex function satisfies (VF(b)- - VF(a), a b) = - (a, Bp (b. a) for all a, This classical fact can be established by adding the following two subgradient identities:
F(a) F(b) + (VF(b),
b) Br(a, 6)
F(b) (()) + (VF(a), b- a) B
a)
(VF(6) a - = -B (b.
(27)
The Theorem is established by showing the following identity:
Wi:t F(re) - W1: ((5--1) - w, F(r.) )) = ni (VF())), 2t - x.,)
We
we(1 - -a)) Br (xt,
Br (yt, x..)
a2
at
-h (1 we Br (1 Wt)-
(28)
Given the identity (28), we sum over all t from to T. Then the LHS will telescope to obtain:
wir((((r)- - F(x.)) = Σ wr V (V)()) 2t - x.)
w: BF(y)
wi(1-ai) - as)
BF BF vc)
at
at
Σ Wi: Br (x w. Br (xx,
from which the conclusion immediately follows since Eig (91, ......, 1-11 V (1)((())))
.t...
91-1].
So, let us establish (28). To do so, it will help to observe the following identities:
# W1 W1:1-122-
Whe- (Ex Iz-1) 1) = wy (Zt xt.)
(29)
2t
1/1 a4 (yr It).
(30)
18

---

So, we have:
W1:- Wh: F(xx))
= (F(z)( - F( (F(((x))) - F(x.))
[VF=1(VV(();) -(-1) + we (F(x.) F(x.))
B
using (29):
= w 2 - F(x.)) w1s- B
wi (VF(())) - wi (F(zt) F(y))) + we (F(r)) F(x.))
-
wi [V
yb) wt (F())) Br x.)
-. 22) - w B (r,
(VVF(())-VV(((1 Vb) wt wo (1))) 24 x.)
- - z.)
2z) - w, BF (x. yt
using (30):
at (VF(x;) - VF(W)). xι) + w. W. - x.)
= w1 at
W Br wr, x4) we B (F( U1)
using (27):
W. (V(())) x.)
Wi 1 at (Br(Ie: By (y).
Bi w. BFBBF xz) we Bu(FF 21)
m, (VF()))) 21 x.,)
wi(1 aa) Br (x,, Vc)
W: Br (y): Br(tt 3:4)
at
at
w1:- (B -
- w; Br(x,, Vt).
D Acceleration
In this section, we show that by instantiating our framework with optimistic online learning algorithm (Rakhlin and Sridharan, 2013), we achieve accelerated convergence guarantees. Our results match those available in the prior literature (Kavis et al., 2019; Joulani et al., 2020). Our approach is inspired by Joulani et al. (2020),: their method is based upon a version of Theorem for the special case that a₂ O. Our result simply extends their analysis a, O11/t).
First, we establish an important technical Corollary that simplifies Theorem 5 in the case that F is smooth and a, is sufficiently small.
Corollary Under the same conditions as Theorem 5, suppose additionally that is L-smooth and suppose aq I ve for all t. Then have for all x,:
10w1.
We (gt, 24 x.
E[F(xT) F(xx)]
WI.T
T
Wi:t [[VF(()) - V (x
E
6Lw1
where above the value of yo is arbitrary (since the coefficient is W1.0 0).
19

---

Proof. The key thing is to observe that smoothness implies (o, b) 2 rest of the argument is straightforward manipulation of the terms in Theorem
The
Wt (y 21) at
wr(l -ar) By (2 yo) S
(2 as))
[VF
VF())
a4
2La
-1+ Bp (xt-1, u4 (r, U1)
w1:1-1
2L
Next, observe that for any vectors a, b, c, for any À >> 0:
-I|a + b clI2 = -|a||| - ||6|2 - ||c|| - 2(a, 2(b, c) 2(a, c)
S - ||a (2) 1)1b1 + ||c|l(),
where we have used Young's ' inequality: ((v, w) - obtain:
Ivll
+ M|ll" 2
Therefore, setting A = we
2A
B11-1B w. (r.,
w1:-- [V (
6L
500 ([
(IIVF(z;
(w()) | -
2L
Now, since Or <
1 1. we obtain:
10w
wt
w1 at) BF - - - we BF (xl 31)
07
07
w1:-1
V (y:) - AF F 13)1
6L
5wid
VF(x))1 + 5w01-11 [F(xz-11)
|VF
V F
2L
2L
Now summing over ł from to T (and dropping one negative term), the sum telescopes to:
Σ
wla-1 VF())) (F
6T.
The result now follows from Theorem 5.
Now, we consider the case that zę given by optimistic mirror descent algorithm:
Corollary 2. Suppose F is L-smooth. Define go 0 and suppose also that for some D satisfying
D 11 xz]l:
Σ welgr 2 x.)) S D
Σ wflles 11.
Finally, suppose Billg: 9t-1 12 < (V VF 2 of for some constants di..... Or (these are just variance bounds on the stochastic gradient oracle). Then with we = and a₁ S 5((-1)) we have:
14D2L E[F(or) - -(x.))
2D ΣT= tot
T(T
+1)
T(T
+1)
= =o D2
Do
T2
VT)
where a is uniform upper-bound on o,, Note that the algorithm does not need to know L or a.
Algorithms producing sequences obtaining the guarantee stated here are called "optimistic online learning algorithms"..
20

---

Proof. Applying Corollary 1, we obtain immediately:
T(T + 1)
((F(xT) F(x+)l
2
T
T
1)
12 Ple 11-1
[F)))) V
12L
T Σ 1=1
VF(y1)11
$ D
E (B)) VF( + 2oo +
24L
T
PB ([)((()) - VF(6-11)1
24L 1=1
[F )1?
DD
PE [E([)F(())) VF D
120 2
24L
E (((()) VF(M-11111)
24L
1=1
Using the identity AVO BC < 12
Llyy1 xx11?
s <DD2L
+
Po
24
S 7DD +
Pot.
Divide by T(T+1)
to conclude the result.
D.1 An Optimistic Regret Bound
In this section we provide an algorithm that achieves the optimistic regret bound required for our acceleration result Corollary 2. This algorithm is mild variation on the established literature (Rakhlin and Sridharan, 2013; Chiang et al., 2012; Hazan and Kale, 2010; Joulani et al., 2017) to slightly improve a technical dependence on the maximum gradient value.
Lemma 1. For a sequence of vectors 9I.....TT, set 1
with go 0, define V2 lll 9: Ill2
maxige ||g: Ii-1ll || and define the sequence of vectors 2t, 24 and ÿt by the recursions:
=1 =0 0
0. -t-1 min (m4-1, 11g. 11-1
9t -t-1
llg. -t-1
D
14
V mm + E 1g 11-
<41 11 SD2 111tt
2,41 I S - T/.t.
Then:
T
(gt. xx) < 7D,
2
l1ge
9:-
1=1
21

---

Proof. For purposes of notation, define gu = 0 and 2/ = 0. Further, observe that:
5t 9t-1
I m
9. I 9 9t-1
19 9t
my m
D
>
++1
1
91-1
i=1
v 2 > m=
I
11g. 91-1 1
1
D
Next, notice that z/411 = argmin order optimality conditions:
|= (rr =) + 1
|| - -2112. Therefore since ||x,|| S D, by first
2ny.
*
2/
gt
+
2/411 - 2x 00
111
(gt, 2441 xza) s 17c
(2) 4441:2411 - x2+)
||
11²
1 - 1=
| 2/11
217t.
21/t
21).
Similarly, we have = argmin |= (9120991112))) + 2n 21=111 22.2 From this we have:
21 2
91-1+ +
2t 1/41 0
11-1
12
21+1
1 2/2+112
12] - 2/
(90-1, 24 2/(11 5
271-1
21/111
27)[-1
||
21+111?
|| - 2/+111" 112
1 - 2/
(ār, +(+1)
21/-11
21h-11
21/-11
+ (ā:
It-1 2t
x((22
by Young's 's inequality:
2 1/11112
1| - 1//
1 - z/11²
21/-1
21/111
27/-1
+ 171 1 11ğ;
9e-1/12
1| 24+1ll" 11?
+
217
| #(+1 2
M 11āe -1-1 112
27p-1
So, combining these facts (and noticing that 7/- 2 T}{i)
1/g - 12
||
x=112
1/-
9t-1
(ūr, -x.) <
+
211r
21/²
2
(gr, xx.) <
1// - 11
||
xx112
7:
01
9t-11
1111
+ (g.
ge, xx)
2:11
2
|| 217
12
|
x=11 11?
+
Th
01
91-111
+ +m(m -m-1)..
2T71
2
22

---

So, we have:
gt. - -xa) S 2Dmr + 1 - 12
-x.1
T
2
x,
1
21/1
2
Th
1=2
111 1 19: -1--11
1=1
22mm + 4D2 pmp +
9/-11
9t
9t
2
< <6D2 |Tr
T
1/-11
-t-1 11
2
1=1
T
D1
D
9
9t-1 1/2
< 6DD /nr +
1=1
2v
Di=1 11: 1:-1
T
S 6D /Tr +
Σ
11 11-1
1=1
T
S 7D
11gt 12
1=1
E Strongly Convex Losses
Suppose that the expected loss F is actually known to be j-strongly convex. Then we'd like to have convergence guarantee of (1//pT)) This is achieved in Theorem 6 below.
Theorem 6. Under the same assumptions Theorem 5, define (((z) (ge, =) + Ellve - =112. Define the "regret" of the sequence 2t as:
T
Regret,(x.)= (x.)) - - le(x)))
Then we have for x. = argmin F::
(F - F F(x.)) Regret,
EE= WI.T
wast
|| yell2
In particular, suppose || S D for some known bound D and ||gell S G for all for some so long l|uell S D. Then if we define w, for all and set z by:
2(g: + p(zz -V))
2+1 II II 24
p(t 11
then we have:
E[F(xT) -((())))F(x)] 2(G + 2μD)2
u(T + 1)
Proof. From Theorem 5, we have:
2m welge, - -x,)
we BF (x Mt)
E[F(xT) F(xx)) 5
W1.T
Wi:T
23

---

Now, since F is y-strongly convex, we have (x( 2 //2 llve -x. Further, we have:
T
Σ w we 2t - x.m Σ -
- (x()))) - WiHl
2 2 - yell 12 + 2 1 - yel1
WiHl
1=1
From this we obtain the desired result:
Regret,((x.) - EE= Well 1 30112
B[F(TT) F(x-)) E
W1.7
For the final statement, observe that with = t, wzle(z) = t,ee, 2) + 인タこ || ye 1 is tj-strongly convex. Therefore if we use learning rate = puie OGD yields:
2 pc(++Ty. then standard analysis of projected
T K (Vle(z)) - -x.)
Σ -allz)))(((..)))
ty
2 || - x.112
2
1| - 2.112
1 2
1| - 2211²)
||2T+1 - x.
2071
201
T
1
t/i
T
(2,(2,))
+
Σ
11ze - 2=112
+
2TT
27--1
2
1=2
t=1
[[(((=))11
T
1 Σ 11.. + pl(z - 1x)112
1 1=1
T(G + 2μD)2
where in the last inequality we have observed that since || < D and ye is a linear combination of past values, ||we|| < D well. Finally, observing that wir T(T+1) the result follows.
F Large Step size convergence
Theorem 7, Consider the online learning setting with bounded gradients 9t. Let 24+1 = 2t - 19--- Let D [ 2x for arbitrary reference point 2, and define G max [|g: Suppose that the chosen step-size is 7 = D/G, then if holds that:
T
Σ
Lor 21 21) s D.
Σ
99. 11
(31)
then:
T
D
(gt - -2,) = 0
Σ
11 11
(32)
T
T
1=
Proof.
Consider SGD with fixed step size y::
2t41 24 79t.
Let
T
8T+1
79t-
1=1
24

---

Recall from D-daptatioo (Defazio and Mishchenko, 2023) theory that:
1 72
7 (gt, -21
199 12
||sc-1|1
(33)
2 1=1
and:
T (et, 2 - 21)
Σ (gts 2t - 2,) S ST+
Σ
(34)
t=1
Now suppose that the regret at time T is negative. Then trivially the theorem holds:
D
ge. - 2.) 00=0
19
T
T
therefore, without loss of generality we may assume that Et= 7 (ot, =2,) 2 0. Then from combining Equation 34 with Equation 33 we have:
T D +
0 2
88 11 + |
Σ 72 11
2 1=1
This is quadratic equation in ||s+I||| which we can solve explicitly via the quadratic formula, taking the largest root:
bb=
vb²
4ac
||s+I|| 5
2a
Plugging in the values
-1, b-
D.
7² |19: 1?:
T
D + D2 +
22 ||9:| 5 +
Σ
22 ||
1=1
Therefore:
|sT+I|| S 2D + 7
||
Substituting this into Equation 34:
Σ y (9r, 21) $ 2D" +
Σ lloell Σ
1or 21
21)
Therefore, if Dt= (gt, 2t - =1) - D Σ ||9e|1 then:
y (gr,2 - 22,) 2D" + 24D
11
Plugging in y= D/G:
(gt, tt - 24) 5 2DG + 2D,
|19.11
< 4D
Σ l1ge.12
and the theorem follows.
25

---

G Experimental Setup
G.1
Convex experiments
Each dataset is obtained from the LIBSVM repository and used without modifications.
Hyper-parameter
Value
Hyper-parameter
Value
GPUs
VX0000
Decay
0.0
Batch size
16
Optimizer
Adam
Epochs
100
Baseline Bi
0.9
Seeds
10
F3
0.95
Schedule-Free 3
0.9
G.2 CIFAR-10
We used custom training code based on the PyTorch tutorial code for this problem. Following standard aata-auumentation practises, we appliyed random horizontal flips and random offset cropping down to 32x32, using reflection padding of pixels. Input pixel data was normalized by centering around 0.5.
Hlper-paaameeter Architecture
Value
Hyper-parameter
Value
Wide ResNet 16-8
Seeds
10
Epochs
300
decay
0.0001
GPUs
1x V100
Baseline Momentum
0.9
Batch size per GPU
128
Schedule-Free LR
10
Cosine/Schedule-FF Warmup
5%
Schedule-Free
0.9
Baseline Stepwise LR
0.1
Baseline Cosine LR
0.2
G.3 CIFAR-100
We used the same codebase as for our CIFAR-I0 experiments, with the same data augmentation. We normalized each input image using fixed mean and standard error values derived from pre- processing the data.
Klyper-parameter
Value
Hyper- paraaetr
Value
DenseNet [6, 12,24,16],
Batch size per GPU Seeds
64
Architecture
growth rate 12
10
Epochs
300
Decay
0.0002
GPUs
I V VI00
Baseline Momentum
0.9
Schedule-Free B
0.9
Schedule- LR
Cosine/Schedule-FF Warmup
5%
Baseline Cosine LR
0.05
Baseline Stepwise LR
0.05
G.4 SVHN
We used the same codebase as for our CIFAR experiments, and following the same data preprocessing.
Hyper-parameter
Value
Hyper-parameter
Value
Batch size
32
Cosine/Schedule--FP FFree Warmup
5%
Weight decay Cosine
0.0001
Schedule- decay
0.0002
Weight decay Step Sched
5c-5
Schedule-Free LR
1.0
Seeds
10
Schedule-Free B
0.9
Baseline Stepwise LR
0.1
Baseline Cosine LR
0.1
26

---

G.5 ImageNet
We used the same code-base as for our CIFAR-10 experiments, and applied the same preprocess ing procedure. The data-anggentttiios consisted of PyTorch's RandomResizedCrop cropping to 224x224 followed by random horizontal flips. Test images used fixed resize to 256x256 followed by center crop to 224x224.
Sxyper-arramttr Architecture
Value
Value
ResNet50
Seeds
Epochs
100
Decay
0.0001
GPUs
8xV100
Baseline Momentum
0.9
Batch size per GPU
32
Schedule-Free 5
0.9
Schedule-Free Decay
0.00005
Cosine/Schedule-FFee Warmup
5%
Baseline Stepwise LR
0.1
Schedule-Free LR
1.5
Baseline Cosine LR
0.05
G.6 IWSLT14
We used the FairSeq framework for our experiments. Rather than a vanilla LSTM we use the variant from Wiseman and Rush (2016) provided in the FairSeq codebase.
Hyper- parameter
Value
Prper-parameter
Value
Architecture
Istm_ _iseman iwslt de en
Share decoder, input, output embed
True
Max Epoch
55
GPUs
x VTO0
Float16
True
Tokens per batch
4096
Update Frequency
Warmup steps
4000
Seeds
10
Dropout
0.3
Decay
0.05
Label smoothing
0.1
Baseline Bi
0.9
Schedule-Frre LR
0.02
Schedule- Free B1
0.9
Schedule-Free warmup
5%
Bg
0.98
Baseline schedule
Linear Decay
Baseline LR
0.01
G.7 NanoGPT
We followed the NanoGPT codebase + as closely as possible, matching the default batch-size, training length and schedule. Our runs replicate the stated 2.85 loss the documentation. Disabling gradient norm clipping is crucial for the Schedule-Free runs.
Hyper- parameter
Value
Hyper-parameter
Value
Architecture
transformer gpt
Block Size
1024
Batch size per gpu
12
Num layer
12
Max Iters
600,000
Num head
12
GPUs
40x VIOO
Num embd
768
Tokens per sample
512
Float16
True
Dropout
0.0
U
Update Frequency
16
Baseline LR
0.0005
Seeds
Warmup
2,000
Decay
0.1
Schedule- Free LR
0.005
Baseline 31, 32
0.9,
Schedule-Free
0.98
Gradient Clipping
0.0
Schedule-Free decay
0.05
27

---

G.8 MAE
Our implementation uses the offical code?, with nlype-paraamtter following examples given in the repository.
Hyper-parameete
Value
Hyper-parameter
Value
Model
vit_ base base_patch166
0.999
Epochs
100
Schedule-Free Free LR
0.002
GPUs
32x VT00
Schedule-Free decay
0.05
Batch Size
32
Schedule-Free Ø1
0.9
Baseline LR
5e-4
Drop Path
0.1
Layer Decay
0.65
Reprob
0.25
Weight Decay
0.05
Mixup
0.8
Baseline 31
0,9
Cutmix
1.0
G.9 DLRM
We used a custom implementation of the DLRM model based on the publicly available code. Our optimizer uses dense gradients for implementation simplicity, although sparse-gradients using Ada- Grad is a more common baseline on this problem, we consider AdaGrad variants of our scheduling approach future work.
Hyper-paramets
Value
Hyper-parameter
Value
Iterations
300 000
Seeds
5
Batch Size
128
Decay
0.0
Emb Dimension
16
Baseline B
0.9
GPUs
V100
Warmup
Schedule-Free LR
0.0005
Baseline LR
0.0002
Schedule-Free B
0.9
Baseline schedule
Linear Decay
B2
0.999
G.10 MRI
We used the version of the the fastMRI code base at https://githut. com//acebookresearchh fastMRI/tree/ wateeemainn/baneeeeeeeeee weriin/baniinggeeee removal. Note that we found that training failed using Py PyTorch or newer, and so we ran these experiments using PyTorch 1.9.
Hyper-parameter
Value
Hyper-parameter
Value
Architecture
12 layer VarNet 2.0
Low frequency lines
16
Epochs
50
Mask type
Offset-1
GPUs
8x VTOO
Seeds
5
Batch size GPU
Decay
0.0
Acceleration factor
Baseline 31
0.9
Bascline Schedule
Linear Decay
Schedule-Free LR
0.005
Bascline LR
0.005
Schedule-Free 3
0.9
32
0.999
G.11 Algoperf
Our full algoperf entry is availiable at https://github. wwwm/facebookeeeerreeeeeoaoceeee hwwpe///oooreeeeeeeeeeeeeeaeeeee hcchcuceleceeeeeeeeeeeeceeeeeeec aeee/tree/maiin htte///hhheeeeeeaaalaaaa secheullerree/algopert The hyper-parameters used for the self-tuning track
submission are listed below.
htttps//ggthuu..oo/faaarttttttte
28

---

Hyper-paree parameter
Value
Hyper- Hyper-paramene parameter
Value
Learning Rate
0.0025
Dropout Rate
0.1
one-minus Betal
0.1
Warmup Percentage
2%
Beta2 (default)
0.99551596897999077
Label Smoothing
0.2
Weight Decay (default)
0:08121616522670176
Polynomial in C average
0.75
29

---

H
Convex Experiments
60
Primaal Avaraging (83, c.44)
Prinal Averaging 195.4 58 52
Princal hearaging (30..0 c.o0
Sctwidahe droe 180.7 000
Sctedua- Soen 31.2 (.01)
Schestale 1100. 52 taz)
E diaaall (99 3 (.0.5.1
60
1B Setweddii 195. 66 01)
Lnf Schwiich cino 0.60)
100
100
Alcurey (94)
16.0
02.5
Prumall Avaraginng (E5. c.511
Pranal Averaging 52
Pricudl Aversping (71,8 0.52)
Ereee (T2, so 101
Schhedice Fine 248.8 SE
Sithefule Pris 177 (.05)
L. S-chodale (72.3 SX 24241
80.5
LD Scbadlde 128.5 52 0.931
LD Schodall (77 a 0.23)
40
100
60
89
1.00
Bpech
Pesiayyn
1.00
1.0
ACC-RR [S3
60
henrigingg 196,
03
Primal Avaragingg (P4,) 0.121
Ereee (96 011
Franal Ameraging 190. 52 0.66)
Schedite Pieee 24111 SE
Prizud Arerupzu c.c5i 6cch-tule Fris 196. Sn (ass) LD Schodale ore a 0.03)
LD S-cholale 135 5.021
LU Scbaoldd 178.2 22 0.911
20
40
100
80
60
20
89
100
Spoct
Speah
70
Polenic hewriiing Dramal Avanggingg 0.15)
Prrypic Pranal Averaging 171.2 52 0.38)
46
Frbyicc Pranul Areregazy (302.0 c.oo Scheddil Dive (1 sn (.0d) La betecdake 1390 l 0.000
Sibbetth--rree (B2 50 001 Lo S-cholale 180 bx 2:341
Schedice-Pewe Thee (77.5 SE.. 6.00
20
LG Schadule 177. se 0.131
20
40
60
100
60
40
50
100
20
60
83
100
Spect
Tonch
Spech
Figure 7: Stochastic logistic regression experiments.
30

---

I Polyak and Primal Averaging Runs
These experiments follow the same tuning setup as Figure where the learning rate and momentum is tuned separately for each method. In each case the weighting sequence used for Schedule-Fres training also used ensure fair comparison. The Polyak averaging runs include momentum in the base optimizer as we found this gave the best results. We ran the NanoGPT experiment for shorter 200,000 steps due to computational budget considerations. The NanoGPT Polyak averaging runs show a divergence in test loss for Polyak averaging.
CIFAR-10 (WRN-16-8)
CIPAR 100 (DenseNet)
Test Accurscy (h)
70
Test: Accuracy
85
Polyak Averaging (95, 56% 0.05)
60
Polyak dewrgging (76.94) SF. 0.12)
80
Primal Averaging (92.00% SE 07)
Prinall Averagligg 0.19)
Schedulee Froe Reference 03%
Schedule Free Reference 78.71%
75
50
100
150
200
250
300
0
100
150
200
250
300
Epach
Epoch
SVHN (ReoNot-3-06)
ILSVRC 2012 Image (RosNet-50)
99
Test Anturayy 176)
That Accurncy (%)
70
60
Polyak Averaping (98.32% 0.01)
Polyak Averaging (72.84% 02)
95
Primal Averaping (97.36% SE 033
50
Primal Averaging (60.78%, 78%, SE 0 0.09)
Reference
Schedule- Free Reference 76.90%
94
40
50
100
150
200
250
300
20
00
60
80
100
Epoch
Epoch
fastMR Knee 2..)
Criten Kaggle (DLRM)
0.912
Tost SSIM
0.910
Thst Annrney
0.785
0.908
Averaging SE
Averaging (9.7899 SE 0.00006;
Polyak Averaging (0.9088 SE 0.00141)
0,780
Polyak Averaging (0.7901 Su 0.0000t:
0.906
Schedulee Free Reference 0.9122
Schedule Free
10
20
20
40
20
40
80
100
Epoch
Epoch
MAE ImageNet Finetune (VIT)
WebnWeblee:: (GPT2 124M)
1est Accurscy (%)
Polyaks Averaçing (5.588 SB 0.136)
Averaging (3.033 SB 0.004)
Teoel Lob5
Schrdule-FFre Fron Referenon 200% 2,878
Polyak Averaging (92.72 SE 0.03)
Primal Averiging 03)
Scheduie- Free Refereace 83.54%
20
50000
100000
150000
200000
Epach
Step
Figure 8: Polyak and Primal Averaging Experiments
31

---

J Additional LR Sensitivity Plots
CHIMR-1 (WRN-116-8) LR Seenemiityy
CIPAR- 100 (DenseNeti LR Senenivity
96
The Acmuray 240
Test Accurssr
76
74
Schodule-Fre
72
Schodule Sanlll---a roo Cosine Schedale
94
Cosine Schedule
10
SVHN 33-366 LR Sunsitivlty
Accurscy
96.3
982
Schedule tree Cosine Schodule
98.1
10-2
200
LR
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper contains new theory as well as extensive experimental results for our method.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We detail the limitations of our method in the conclusion section.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theorems stated in the paper are proven in the Appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Detailed results concerning the experimental setup provided in the ap- pendix.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have already open sourced method. Experiments can be replicated using our open source PyTorch optimizer implementation together with existing open source code bases implementing each method.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: To the best of our knowledge, we provide sufficient information about hyper- parameter settings for all experiments to be reproducible.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All experiments reported use multiple seeds, and error bars are included in all plots.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Question:
33

---

Answer: [No]
Justification: As our method has no runtime overhead compared to existing approaches, we do not report computation times.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttps://Aat /ttp:///neuupsppeee https///ww.p...cccccccccteeeeee.
Answer: [Yes]
Justification: We have abided by the code of ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: There is no foreseeable societal impact from our work.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not Applicable
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [No]
Justification: We do distribute any models or datasets with this work. Datasets used for evaluation have license information available at the cited source.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: No new assets are being released.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: Not Applicable
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Not Applicable
34


Reviews:
[{"review_id": "LlE2Vc8rmo", "reviewer": "Reviewer_rKis", "summary": "This paper proposed an optimization style for stochastic optimization, termed schedule-free optimization, which is free of manually selected/tuned learning rate schedulers. The proposed method enjoys both the worst-case optimal last-iterate convergence and promising empirical performance. The authors also introduced a general online-to-batch analysis framework to analyze the proposed method. The empirical results show that the proposed method outperforms the state-of-the-art methods in various tasks, including training large language models (LLMs) and image classification tasks.", "questions": "1. Why don't you report any empirical results that combining schedule-free methods and parameter-free methods? By the way, certain parameter-free literature is cited in the Appendix for the use of proof. The authors are encouraged to elaborate on the connection between this citation and the current work.\n2. Any conjecture/explanation on the empirical observation on Line 158?\n3. How do you deal with the \"decoupled weight decay\" issue in adapting the most popular optimizer for LLMs (i.e., AdamW) to the schedule-free style?", "limitations": "No major societal limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The mismatch between the theoretically optimal learning rate schedule and the practice is an important problem. This paper re-introduces and re-emphasizes this issue in a well-educated manner.\n2. The proposed online-to-batch analysis framework is general and insightful.\n3. The positive result in the empirical verification of equation (9) introduces an interesting new open problem that is worth further investigation: why could well-known convex/non-convex optimization problems as such an \"bounded-regret\" property under gradient descent?\n4. The proposed schedule-free method enjoys both the worst-case optimal last-iterate convergence and promising empirical performance.", "weaknesses": "1. In the update rule of $z_{t+1}$, using $y_t$ instead of $z_t$ could incur additional forward passes during the optimization process (of neural networks through backprop), which especially undermines the efficiency and applicability of the proposed method in the scenario of model parallelism.\n2. The adaptation from schedule-free SGD to schedule-free AdamW is still in a heuristic way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "x2glxioLED", "reviewer": "Reviewer_Q984", "summary": "The authors propose a method for training neural nets without needing to know the total training time T in advance. This contrasts with a standard training setup where one chooses a learning rate schedule in advance, and the schedule must include an a priori chosen stopping time T (e.g. cosine schedule or linear decay). If the method really works as advertised it therefore simplifies practical training setups and reduces the cost of training, by avoiding the need to run multiple training runs with different values of stopping time T.\n\nThe method works by tracking two sequences: one is the \"noisy\" sequence z that integrates noisy gradient updates, the second is the \"smoothed\" sequence x that tracks a uniform average over all past noisy iterates z. Gradients are evaluated at an interpolation between the current noisy z and smoothed x sequence, and added back to the noisy z sequence which is then averaged into the smoothed x sequence.\n\nAuthors present theoretical results about their technique for convex optimisation, and evaluate the method across a set of training benchmarks, some that involve tuning and some that don't. The results look promising.", "questions": "- do you know if beta is sensitive to e.g. training time? Fine if you don't know, but consider adding a limitation saying future work could investigate this closer\n- which sequence is used to do inference x, or y, or z? It might be worth clearly flagging this in this paper. Sorry if I just missed it.", "limitations": "\"Note that we excluded one benchmark problem, ResNet-50 training, as neither AdamW nor NAdamW can hit the target accuracy on that task.\" ---- this feels artificial to me. I still want to know how schedule free AdamW does!", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- the idea is legitimately really cool and clever and seems very original to me. People know that weight averaging on top of standard training can boost performance, so it's really cool to ask \"is there a way to fold this back into the training loop\" as the authors do. \n- my broad understanding of the technique is that it's doing noise filtering in a clever way, and I think that this idea can inspire others to explore this direction, which is great\n- the paper is very clearly written and I like the mix of the intuitive description of the technique, the formal results, and then the experimental evaluation\n- it's great that the authors engaged with the MLCommons Algorithmic Efficiency benchmark, and from what I understand the results are very promising.", "weaknesses": "Okay as I've mentioned, I think the idea is cool and original and can inspire followup work, which is all we really want of a paper. So I'm going to focus on giving you feedback which is intended to be constructive and I hope can help you generally improve the quality of the work or followup work that you do. I'm not going to hold the paper hostage, but if I feel like you engage meaningfully with my critiques I'm willing to upgrade my score. All of my critiques can be addressed either by making minor amendments to text or by adding a limitations section at the end of the paper *or* by running more experiments and addressing them, but I won't insist on which and leave this up to the authors.\n\n### **Paper may be over claiming slightly on its results**\n\nThe paper makes claims to be **\"one of the largest and most comprehensive machine learning optimization algorithm evaluations”**. Can you quantify in what sense this is true? To me the evaluation doesn't feel that comprehensive---for instance, there is only one plot on hyperparameter sensitivity, while a broad swathe of the community has started to explore this question as standard in evaluations papers. The authors also state their method **\"has no notable memory, computation or performance limitations compared to scheduling approaches\"**. In my opinion, the truth value of this statement is essentially unknowable without more thorough evaluation. It would be fine to amend the statement by saying \"WE BELIEVE THAT our method has no notable memory, computation or performance limitations compared to scheduling approaches.\"\n\n### **Hyperparameter sensitivity is not thoroughly investigated**\n\nIn my opinion, the main potential limitation of the work is that tuning hyperparameters (learning rate, weight decay, interpolation constant $\\beta$) may implicitly be tuning an LR schedule. This is especially the case for this technique since the role of these hyperparameters is quite subtle given the unusual form of the update sequences. Now the authors may argue that they address this with their MLCommons Algorithmic Efficiency experiments that reportedly use the same set of hyperparameter across all tasks, but in my opinion this could be a fluke relating to all the MLCommons tasks involving similar training times for instance. What I would want to see to convince me otherwise is to see experiments that sweep across beta for different training times, and check if the optimal beta is invariant to training time, say.\n\n### **Paper applies a potentially ill-suited theoretical framework to deep learning, and as such there are gaps**\n\nThe paper comes from a part of the community that uses convex optimization frameworks to do algorithm design, and then extends the methods to deep network training. Sometimes the extension can feel a bit forced: e.g. let's switch to Adam instead of SGD as our base optimiser because it works better, let's use learning rate warmup because it works better, etc. The paper uses theorems within this convex framework to support its significance, but as far as I can tell these theorems don't answer basic questions a practitioner would have about the technique: e.g. Theorems 1 and 2 provided no guidance on setting the interpolation parameter $\\beta$ since they hold uniformly for all $\\beta \\in [0,1]$.\n\nI want to point out that another part of the community is trying to build up understanding and frameworks for deep learning fundamentals that involve less of a \"jump\" from convex optimisation to deep learning. To point out two examples:\n- https://arxiv.org/abs/2103.00065 \"Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability\"\n- https://arxiv.org/abs/2405.14813 \"Scalable Optimization in the Modular Norm\" (concurrent work)\n\nI think it would be great to at least read these works and potentially engage with them---not in this paper, but in the future\n\n### **Final note**\n\nI sometimes worry about giving frank feedback as I think I can sometimes have a blunt style. I want to re-emphasise that I really like this paper. I think the idea is clever and creative, and I really encourage you to pursue these directions further. The feedback is intended constructively. I am currently giving the paper a score of 5 because a score of 6 requires \"no major concerns with respect to evaluation\" and I am not there yet. I can get there if I become confident that you've engaged with my review.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Strengths\nWe are glad that you find our work interesting! We think that this approach has wide applicability and we are doing our best to spur adoption by doing an open source release in both PyTorch and Jax. An entry using our method was entered into the AlgoPerf competition earlier this year, and the final results were just released this week, showing that Schedule-Free AdamW ranked **first** in the self-tuning division, beating out all other entries including the AdamW+Cosine implementation tuned by the organizers. We hope this independent verification will help you assess the potential impact of our work.\n\n# Weaknesses\n\n## Paper may be over claiming slightly on its results\n\n*\"one of the largest and most comprehensive machine learning optimization algorithm evaluations”. Can you quantify in what sense this is true?*\n\nWe will reword this phrase as we agree it is not precise enough. We wanted to convey that we run experiments on a larger set of test problems than any prior paper on deep learning optimization. As far as we are aware, there is no paper out there that runs as many full-training (not fine-tuning) experiments as we do on deep learning problems. The are larger comparisons on logistic regression and other convex problems in past literature, as well as model fine-tunings, so we need to be careful to adjust our wording to clarify.\n\nWe have ran additional hyper-parameter sensitivity experiments, please see the section below.\n\n*\"has no notable memory, computation or performance limitations compared to scheduling approaches\"* \n\n- We will cut this phrase from the conclusion as we agree it is overreaching at the moment.\n\n## Hyper-parameter sensitivity is not thoroughly investigated\nThis is a good point, we don't currently investigate hyper-parameter sensitivity thoroughly. We ran a series of additional experiments and have included these results in the PDF attached to the global rebuttal. We ran as many experiments as we were able to in the 1 week rebuttal period, so they are not completely conclusive. We will run additional experiments for the camera ready.\n\n### Learning Rate\nWe ran a series of learning rate sweeps for the smaller problems in our test bench (these sweeps are time consuming to run), CIFAR10, CIFAR100 and SVHN. We see that the sensitivity to the optimal learning rate is very similar to SGD with momentum, with some variability observed. For CIFAR10/100 the curves look essentially the same, and for SVHN the curve has a somewhat tighter peak.\n\n## Momentum\nFor our momentum sweep, we see a similar result. For both problems that we ran, neither Schedule-Free or the SGD+Momentum baseline show clearly more or less sensitivity to the hyper-parameter, and there isn't a clear pattern.\n\n### Beta v.s. Training Time\nSee the Questions section below.\n\n## Paper applies a potentially ill-suited theoretical framework to deep learning, and as such there are gaps\nThe analysis framework to use here is a question we constantly struggle with as researchers in this area. The convex framework is usually considered ill-suited to describe deep learning problems, but it leads to results that seem to work well in practice (this paper's method is a great example). Averaging of iterates for general non-convex problems can't be analyzed as far as we are aware, since you can end up averaging between winding valleys of the parameter space and the resulting points don't necessarily have low loss. \n\nIn terms of the optimal values of $\\beta$, we are investigating this as followup work. So far we have a result that for stochastic quadratic problems $\\beta=0.5$ is optimal. A similar result holds for strongly convex problems although it may not be strictly optimal in that case. In other convex settings, larger $\\beta$ values than 0.5 are potentially better, but there is a dependence on the local quadratic-ness of the problem, and the more quadratic, the closer to 0.5 the value should be.\n\n## Questions:\n\n1) *do you know if beta is sensitive to e.g. training time?*\n\n We have run an additional experiment to understand this dependence for the ImageNet test problem, it is included in the global rebuttal PDF. We ran training out to 200 epochs instead of 100, to see if larger $\\beta$ values given improvements at the very late-stages of training.\n\nWe find that at the early stages of training, the value of $0.9$ gives the highest test accuracy, but at approximately epoch 50, the larger value of $0.95$ starts to dominate (we didn't run $0.9$ in our sweep in our paper, so this result is an improvement over the previous results). This $0.95$ value dominates for the remainder of training, and the larger value of $0.98$ is far behind in terms of test accuracy. The beta=0.75 run doesn't do better at the beginning, so it's not the case generally that smaller beta is always better at the beginning.\n\nSo to summarize, smaller $\\beta$ values can perform better for shorter duration training runs, but this dependence on training time for the optimal beta seems very mild.\n\n2) *which sequence is used to do inference x, or y, or z?* \n\nThis a good suggestion, we don't currently clearly indicate which sequence is used. We will update the paper. The sequence used for inference should be the $x$ iterate.\n\n\nIf you have any further questions please don't hesitate to ask.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "ZBM1DBOgrO", "reviewer": "Reviewer_mxnW", "summary": "The paper proposes a scheduler free method for training, analyzes it theoretically to show that it matches the theoretical benefits of Polyak averaging while recovering the performance of standard cosine decay used in practice. Their approach can be interpreted as being an interpolation of Polyak averaging and Primal averaging (which is equivalent to momentum). Thus it gets the benefits of acceleration while maintaining the low variance of Polyak averaging.", "questions": "Could the authors add comparison to (tuned) EMA? I would happy to increase my rating further if the authors do this.", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The empirical comparison to cosine decay scheduler is done in a thorough manner.\n2. Another strength of this work is that alternative approaches such as Polyak averaging or EMA require maintaining one extra copy of the weights.", "weaknesses": "Since the focus of the paper is to match theoretical guarantees of Polyak averaging while matching empirical performance of schedulers they also need to compare to Polyak averaging and EMA variants[1]. The paper does not do this thoroughly. \n1. Line 22 states “Despite their theoretical optimality, PR averages give much worse results in practice than using the last-iterate of SGD with well-chosen learning rate sequences (Figure 2a)” but Figure 2a states the Polyak-averaging diverges. Clearly this could be fixed with a slightly smaller learning rate since cosine decay did not destabilize? \n2. The paper does not compare to EMA which is another method which can empirically reduces variance while not using schedules.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Weaknesses\n\n1.\n\nThis is a really good point. It is possible to get Polyak averaging to converge by using a smaller LR value. For the IWSLT14 illustrative plot we did not include a full LR sweep (as we did with all experiments in the experiments section) when we should have. We have ran this LR sweep and included the updated plot in the global rebuttal PDF. It shows that both Polyak and Primal averaging still greatly under-perform compared to both a cosine schedule and the Schedule-Free approach.\n\nWe currently do include Polyak and Primal averaging in all convex-case experiments but we can also run these for the deep learning experiments for completeness. We will run these additional experiments for the camera ready. After reflecting on your question, we realize that there hasn't been any published experiments extensively comparing Polyak or Primal averaging to schedules in the non-convex setting, and their sub-optimality is more a folk-law result. These additional experiments could be useful to the community.\n\n2) See experimental results below.\n\n# Questions\n*Could the authors add comparison to (tuned) EMA?*\nThis turned out to be an interesting question. We ran an experiment on CIFAR-10 using SGD with momentum 0.9, using the same experimental setup as in the paper, and with warmup-then-flat learning rate schedule. \nWe found that with a careful sweep of the exponential model averaging parameter, we are able to achieve essentially the same test accuracy as we get with Schedule-Free. See below a list of EMA values and the associated test accuracies (single seed), sorted from best to worst:\n\n0.9998: 96.02\n\n0.9996 95.92\n\n0.9999: 95.83\n\n0.99996: 95.743\n\n0.998: 95.66\n\n0.999: 95.60\n\n0.99998: 95.343\n\n0.996: 95.313\n\n0.99: 94.852\n\n0.99999: 92.768\n\nThis is an interesting result! It suggests that the averaging in Schedule-Free may have a similar effect to exponential weight averaging, but without the requirement to tune an additional parameter, and also without the additional memory cost of EWA. Thank you for the suggestion that we investigate this. This link definitely warrants further investigation and we will run additional experiments for the camera ready that directly compare to EMA.\n\nWe also tried running exponential model averaging using a warmup+cosine schedule for the SGD+M method. This was significantly worse across the board than the warmup+fixed schedule, which is surprising as existing papers usually stack EMA with a schedule. See the results below:\n\n0.998 95.48\n\n0.99996 95.45\n\n0.9996 95.38\n\n0.9998 95.38\n\n0.95 95.33\n\n0.98 95.30\n\n0.999 95.292\n\n0.996 95.24\n\n0.99 95.16\n\n0.9999 95.04\n\nWhen combining with a schedule there is less sensitivity to the choice of $\\beta$.\n\nWe hope these experiments help answer your questions. Please let us know if you have any further questions or comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "3hGKskX9i5", "reviewer": "Reviewer_8hsg", "summary": "This paper proposes a new optimization procedure for deep learning that yields good any-time performance instead of requiring learning rate schedules that decay to zero. The method can be performed on top of standard optimizers, making it easy to apply to existing networks. The paper theoretically describes the method, proving desirable properties. The method is evaluated across a broad range of tasks, including various deep learning tasks (supervised learning) and simpler convex optimization tasks, typically roughly matching or slightly exceeding the performance of standard baselines. The any-time performance of the method in a single run is comparable to the pareto frontier of standard methods when using different schedule lengths, a very large advantage of the proposed method.", "questions": "Minor Suggestions:\n- L20: Specify whether g_t is evaluated at x or z\n- L29: Maybe clarify that this “T in advance” applies to many popular schedules. There are many examples of schedules that don’t have this, e.g. trapezoidal schedules / warmup-stable-decay / reduce-on-plateau.\n- L41: No additional hyperparameters over SGD *with momentum* or Adam\n- Maybe include equation numbers, they make it much easier for people to refer to the equations e.g. when discussing the paper even if you do not use these references in the manuscript. Labeling equation 1 as such seems odd since nothing else is labeled.\n- L178: Why is Lookahead like EMA? I can see the resemblance to PA but not necessarily EMA.\n- L290: It would be nice to show some results for different types of weighing when using a warmup", "limitations": "Yes, no concerns here.", "rating": 10, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The problem studied is of significant relevance to the community and likely to have a large impact. The use of learning rate schedules is almost universal and this has the potential to change that. Strong anytime performance can significantly simplify experimental procedures.\n- Good theoretical contribution.\n- Strong empirical evaluation across a large number of tasks with sufficiently strong baselines with very good results.\n- Significant novelty as far as I know, I have not seen any works that can provide this type of any-time performance before.\n- Paper is relatively easy to follow with clear figures.\n- Experimental validation is done over multiple seeds.", "weaknesses": "- Deep learning evaluation could be improved slightly, especially with respect to hyperparameter tuning and transferability of the hyperparameter values. The effects of different hyperparameters and how they change between settings is not discussed. The full ranges of the hyperparameter tuning of the method and baseline is not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for providing line-by-line comments we will update the camera ready and arxiv to reflect all of your suggestions. We also address them below\n\nL20: Specify whether g_t is evaluated at x or z\n - Good point, we will update.\n\nL29: Maybe clarify that this “T in advance” applies to many popular schedules. There are many examples of schedules that don’t have this, e.g. trapezoidal schedules / warmup-stable-decay / reduce-on-plateau.\n\n - Yes, we will state that there does exist schedules that instead require a cool-down period to be chosen, which can be chosen during the course of the run, and that the historically popular reduce-on-plateau schedule also doesn't require a stopping time (with the downside that it is significantly out-performed by modern cosine/linear schedules).\n\nL41: No additional hyperparameters over SGD with momentum or Adam\n - This should specify SGD+momentum not just SGD, we will fix.\n\nMaybe include equation numbers, they make it much easier for people to refer to the equations e.g. when discussing the paper even if you do not use these references in the manuscript. Labeling equation 1 as such seems odd since nothing else is labeled.\n - We will add equation numbers through the whole paper. Thanks!\n\nL178: Why is Lookahead like EMA? I can see the resemblance to PA but not necessarily EMA.\n - By EMA here we mean that the x sequence is an EMA, since it's updated with a fixed interpolation weight $\\alpha$ rather than a decreasing weight sequence that would given an equal-weighted average. This can be seen by rearranging the equation for $x$ in the more classical EMA form: $x_{t}=\\left(1-\\alpha\\right)x_{t-1}+\\alpha z_{t,k}$. It's not strictly an EMA of the z sequence just of the last z from each inner loop. We will clarify this in the paper.\n\nL290: It would be nice to show some results for different types of weighing when using a warmup. \nThis is a good suggestion. During the early development of the algorithm we did a sweep of weighting value powers and found that a power 2 works the best. We have not performed a large scale ablation of this value though. We will add this to the camera ready. \n\n\nWe are very glad to see your enthusiasm for our method! We want to note that a submission to the AlgoPerf competition that used our method has achieved a first-place result in the final standings, providing further independent evidence of the practicality of our method. We hope you will consider increasing your score in light of this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": {}}]

Author rebuttal:
Several reviewers requested additional plots to examine the hyper-parameter sensitivity of our method. We have ran as many experiments as time allowed in the rebuttal period, covering the sensitivity to learning rate, momentum and the duration of training.

Meta-review: The reviewers are unanimously positive on this paper. They believe that the proposed approach has good potential to be quite significant for the field, both practically (as evidenced by good performance on AlgoPerf), and theoretically (it is a novel combination of momentum and weight averaging with theoretical analysis). They raised concerns about the hyperparameter sensitivity of the method and its relation to other work.

I agree with the general assessment on the potential impact of the paper and feel that it would be of very wide interest to the community. Therefore, I recommend to accept the paper as an oral.
Decision: Accept (oral)