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

L20: Specify whether g_t is evaluated at x or z

• Good point, we will update.

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.

• 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).

L41: No additional hyperparameters over SGD with momentum or Adam

• This should specify SGD+momentum not just SGD, we will fix.

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.

• We will add equation numbers through the whole paper. Thanks!

L178: Why is Lookahead like EMA? I can see the resemblance to PA but not necessarily EMA.

• 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.

L290: It would be nice to show some results for different types of weighing when using a warmup. This 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.

We 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.

Weaknesses

This 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.

We 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.

2. See experimental results below.

Questions

Could the authors add comparison to (tuned) EMA? This 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. We 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:

0.9998: 96.02

0.9996 95.92

0.9999: 95.83

0.99996: 95.743

0.998: 95.66

0.999: 95.60

0.99998: 95.343

0.996: 95.313

0.99: 94.852

0.99999: 92.768

This 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.

We 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:

0.998 95.48

0.99996 95.45

0.9996 95.38

0.9998 95.38

0.95 95.33

0.98 95.30

0.999 95.292

0.996 95.24

0.99 95.16

0.9999 95.04

When combining with a schedule there is less sensitivity to the choice of $\beta$.

We hope these experiments help answer your questions. Please let us know if you have any further questions or comments.

Strengths

We 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.

Weaknesses

Paper may be over claiming slightly on its results

"one of the largest and most comprehensive machine learning optimization algorithm evaluations”. Can you quantify in what sense this is true?

We 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.

We have ran additional hyper-parameter sensitivity experiments, please see the section below.

"has no notable memory, computation or performance limitations compared to scheduling approaches"

• We will cut this phrase from the conclusion as we agree it is overreaching at the moment.

Hyper-parameter sensitivity is not thoroughly investigated

This 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.

Learning Rate

We 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.

Momentum

For 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.

Beta v.s. Training Time

See the Questions section below.

Paper applies a potentially ill-suited theoretical framework to deep learning, and as such there are gaps

The 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.

In 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.

Questions:

1. do you know if beta is sensitive to e.g. training time?

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.

We 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.

So 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.

2. which sequence is used to do inference x, or y, or z?

This 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.

If you have any further questions please don't hesitate to ask.

Thank you for the detailed review, we appreciate it. We are very glad you see the potential of our method. We would like to start by addressing each of your concerns separately:

Weaknesses:

1. additional forward passes This is a good point! In our PyTorch and Jax implementations, we are able to avoid any additional forward or backward passes over regular AdamW, except when BatchNorm is used, where the extra forward passes are needed to warmup the BN running_mean/var buffers before a test loss evaluation. These extra forward passes have less than 2% runtime overhead. Given this low overhead, and the fact that batch-norm is quickly being replaced by layer-norm and other alternatives in modern architectures, we don't think this is a major issue.

2. heuristic adaptation for AdamW As you say, our Schedule-Free AdamW version is heuristically adapted from standard AdamW. We will add a section to discuss this to the paper. AdamW doesn't have a concrete regret bound, but related methods that "fix" AdamW's theory, such as AMSgrad, can also be used. Since our main Theorem shows how any method with a proven regret bound can be used adapted to be Schedule-Free, it is then no longer heuristic. Our theorem handles arbitrary learning rates including warmup, and any weighting sequence, so this bound directly applies to the methods as practically implemented.

Questions:

1. LR Adaptation We have done some initial investigation into integrating Schedule-Free with various recently described LR adaptation methods. This integration is surprising subtle as the theory doesn't apply directly for the technical reason that D-Adaptation and DoG methods show bounds on the stochastic loss, NOT the regret, whereas our method specifically requires a regret bound. This difference is crucial to those methods behavior from the theory point of view. We so far have not seen good results when using Schedule-Free in combination with D-Adaptation or Prodigy. We are planning to next investigate integrating with regret-bound methods such as Mechanic and Coin-Betting approaches in the future, and we hope to see good results there.

2. Line 158 - Momentum allows larger LR values In the quadratic setting, for large beta values, our method becomes convergent for larger learning rates then you would normally be able to use. This is likely related to the similarity between our method and momentum which provides acceleration in the quadratic case. However, we don't believe this result is indicative of the actual behavior of the method on deep learning problems as it only holds in the quadratic setting. We have further theoretical results in this direction that didn't make it into the paper by the submission deadline, and we see in the stochastic strongly convex case, our method provides provably better convergence rate bounds with beta \in (0,1) than is achieved with Polyak or Primal averaging.

3. decoupled weight decay Integration of optimization methods with decoupled weight decay is a surprisingly subtle issue. Currently we have a switch in the open source code that supports weight decay calculated either at $y$ (the default used in our experiments) and $x$. We find empirically that calculating it at $y$ performs a tiny bit better on some problems but it largely doesn't matter. From a theory point of view, you can make arguments for both forms, which is why we support both. We will add additional clarification around this difference in the paper.

We hope that you will consider raising your score given our comments above. We believe this work has potential to become the default training method in the future given it's strong advantages over classical schedules and it's ease of use. An entry using our method was recently announced as the first-place winner in the self-tuning track of the AlgoPerf competition, a further indication of the potential of our method. It significantly beat all other entries including a tuned AdamW.

We are very glad to see the level of discussion here, it's rare to have so responsive reviewers! The points that Reviewer Q984 make are relevant, and so we will address them in detail:

Novelty of weight averaging

The connections between learning rate schedules and weight averaging are well known

We discuss this at the beginning of our introduction, quoting from our work: ".. 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". We tried to be careful to not over-claim here, we are not saying we discovered this link between averaging and schedules. Our claim is that our work is the first to give a method that uses averaging that does not require a schedule, while still matching or outperforming schedule-based approaches.

The work of Sandler et al 2023 doesn't use averaging to yield a schedule free method. They show that for stochastic quadratic models, you can achieve the convergence rate by averaging $k$ weights as you can by reducing the learning rate by a factor $k$. A quote:

“Thus averaging two solutions with a higher learning rate $\lambda$ gives us practically identical solution as if following the trajectory from $\theta_1$ to $\theta_2$, but with the learning rate $\lambda/2$.”

There work is relevant and we will add a citation to our related work section, but their result is orthogonal to ours. They use averaging to replace the LR decreases in a regular schedule, but that still requires you to choose when to introduce and increase the amount of averaging, it's not "schedule-free", and the idea of the existence of schedule-free methods is not discussed in their work.

Schedule-Free-ness

The extent to which the paper is actually schedule-free is unclear

We are running more experiments to verify this, as this is an important concern. Our theoretical results are very clear here, they explain why it's possible to learn without a time-dependence on the hyper-parameters. The experiments we include in the global PDF show that it may be possible to achieve a slightly higher test accuracy at the early stages of training by using less momentum, but the difference is tiny. We also show in Figure 1 in our work that a single run of Schedule-Free is competitive with runs with cosine schedules of varying lengths, which strongly supports our claim.

Falsifiable Predictions

There is no actual evidence provided for a connection between the theorems and the practical performance of the method

This question is a difficult one to tackle, as we present a lot of empirical results to support our theory, but it's unclear to what degree these can be considered falsifiable predictions.

Our work was motivated by the earlier theoretical results which suggested that averaging should be able to match schedules in performance; this could be considered the core theoretical prediction behind our work. In the introduction we state the question:

"Do there exist iterate averaging approaches that match the empirical performance of learning rate schedules, without sacrificing theoretical guarantees?"

This is not quite a falsifiable prediction in the classical sense of the scientific method, but we do demonstrate a method that matches the theoretical behavior predicted of averaging methods; this is strong empirical and scientific evidence.

Our paper also introduces a new form of momentum, which has appealing theoretical properties not satisfied by regular momentum, such as being worst-case optimal for any choice of momentum parameter. We can generally expect that a method with better worst-case bound should perform the best, and that is what we show empirically: our method out-performs classical momentum. This is in a sense a prediction of the theory that is born out in practice.

We hope reviewers will judge that our theoretical and empirical results are strong and convincing, even though we don't strictly follow the framework described by Reviewer Q984.

We are very glad to be able to present our work to responsive and thoughtful reviewers. We hope that our comments above will be considered on their merits.