Mechanic: A Learning Rate Tuner
Authors: Ashok Cutkosky
Aaron Defazio
Harsh Mehta
Venue: NeurIPS 2023 poster (2023)
Keywords: optimization
deep learning
online convex optimization
TL;DR: A meta-algorithm that tunes the LR of any base optimizer, with empirical evaluation.

Abstract: We introduce a technique for tuning the learning rate scale factor of any base optimization algorithm and schedule automatically, which we call Mechanic. Our method provides a practical realization of recent theoretical reductions for accomplishing a similar goal in online convex optimization. We rigorously evaluate Mechanic on a range of large scale deep learning tasks with varying batch sizes, schedules, and base optimization algorithms. These experiments demonstrate that depending on the problem, Mechanic either comes very close to, matches or even improves upon manual tuning of learning rates.

Mechanic: A Learning Rate Tuner
Ashok Cutkosky Boston University Boston, MA ashok@cutkosky.. com
Aaron Defazio Meta, FAIR New York, NY adef adlfazio@meta.commmmmmmm com
Harsh Mehta Google Research Mountain View, CA harshm@google com
Abstract
We introduce a technique for tuning the learning rate scale factor of any base op- timization algorithm and schedule automatically, which we call MECHANIC. Our method provides practical realization of recent theoretical reductions for accom- plishing similar goal in online convex optimization. We rigorously evaluate MECHANIC range of large scale deep learning tasks with varying batch sizes, schedules, and base optimization algorithms. These experiments demonstrate that depending on the problem, MECHANIC either comes very close to, matches even improves upon manual tuning learning rates.
Introduction
Modern deep learning is driven by first-order stochastic optimization algorithms. These are algo- rithms that are designed solve the classical stochastic optimization problem:
min F F(x) min [ z)]
where z is minibatch of examples, x E TRd is the model parameters, and f is the loss incurred by using weights x the minibatch A first-order algorithm follows the protocol:
1. Output tth iterate Xx-
2. Sample random minibatch Z:.
3. Compute g: = ff(x,, z;) (the gradient is taken with respect to x, only).
4. Possibly update some internal algorithm state based upon g: in preparation for computing the next iterate X
The prototypical such optimization algorithm is stochastic gradient descent (SGD), which exempli- fies the attractive features of this approach: it is computationally cheap (running ((d) time per update), and with proper tuning obtains minimax optimal convergence guarantees [2 Modern practice makes use of wide range of variants of SGD, such SGD with momentum, AdaGrad B. Adam [4, AdamW (5) or Lion [6]. Interest in such improvements to SGD is driven by the increas- ing computational demands of training large neural networks: better optimization means cheaper training, which translates to significant savings in terms of time, cost, and environmental impact.
Most modern algorithms for training neural networks equipped with scalar "scale factor" or "learning rate" hyperparameter E R.. Roughly speaking, these algorithms produce iterates of the u, where u, is some update gradients g...... (we will use bold font for vectors in IR like and normal font for all other quantities like s). As an example, the classical SGD algorithm sets u, -n) n] for some sequence of scalars }nd} typically called the schedule, The formula for the SGD update is:
form X++1
produced function of the observed
X1
(1)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The process of selecting the optimal s is called "tuning", and is key resource sink in machine learning. The typical approach is simply to try many possibilities to find the empirically optimal s, which requires multiple expensive training runs. This paper introduces technique for choosing automatically on-the-fly order to avoid this expense.
Our procedure, which we call MECHANIC, is generic wrapper around any base optimization al- gorithm (BASE) that produces a new optimizer which does not require tuning of the scalar s. The base optimization algorithm is allowed to make any kind of update (for example, it may use any kind of schedule, preconditioner or weight decay). x E R is the tth iterate of BASE, then the wrapper will produce scalar E R and set the tth iterate of the wrapped algorithm to be + sy xx/45)). As an example, suppose that BASE is the classical SGD algorithm
x; = = xfiASF with update equation
[T]. Then, given st, we would set X; = x for now the fact that the gradients g, actually depend on the iterates x we see that x₃ is what the tth iterate of SGD would have been if the schedule were scaled by st-
8: Ei Mg. Disregarding
Removing tuning of learning rate scalars is already a well-studied problem. One of the main attractions of early work in "addattiv" optimization such as AdaGrad and Adam 3 7 4 is that these algorithms require less tuning than ordinary SGD. Over the last decade, number of works have aimed to tackle this problem from both an empirical and theoretical perspective
8 2 10 I1 12 13, 14 15 16 17 18 19I. An intuitive approach might take the route of "hy- pergradient descent": that is, differentiating the update step of the optimization algorithm itself (e.g. (. Strangely, it appears to be difficult to prove that such schemes behave well: theory-based approaches often adopt rather different strategies. Instead, we start from known theory and propose a few important modifications to produce a simple and effective practical implementation. We then rigorously evaluate algorithm a variety of datasets. We emphasize that primary contri- bution is not new theoretical development, but instead the translation between theory and practice, which involves fusing several known analytical techniques as well as subtle departures from theory.
Previous works that investigate deep learning performance of "learning-rate free" optimization in- spired by theory (e.g. [20, 21 [6 [5) have already demonstrated impressive results. However, these works typically build "hand-crafted" algorithms that often blend theoretical analysis with spe- cific empirically successful algorithms such as Adam. In contrast, our wrapper works well with any base algorithm and so can scamlessly integrate new empirical advances in optimization: one does not need intimate familiarity with the analysis of our approach to apply it to algorithm.
2 Background: Online Convex Optimization
OCO is a popular framework for design and analysis of stochastic optimization algorithms. In brief, for each of T rounds (corresponding to T iterations of optimization), the OCO algorithm must first output a tth iterate x,, after which the algorithm is presented with a fth loss function 4, Typically, one envisions the case (x) = f(x, 2 for some fixed loss l and new data point 2, The goal of an algorithm ALG is to minimize the regret (AALG(x).
We develop our formalism via online convex optimization (OCO) 20 23 2
RAGG (x)
Σ (x.:) - (x))
Many references focus primarily on the case X argmin ΣT= (x(x) in order to consider the single scalar value sup& Ry (x) (25 26), but we will employ the formulation of regret as a function above instead it is strictly more general. When lg is convex, then with g: A (x,, (or, more generally when g: is subgradient of l, at xt), we have:
BALG (x) S E(:
A Re (x).
As a result, the vast majority of OCO algorithms provide analysis that bounds only the linearized regret R Such algorithms do not need to observe the entire function f,: instead, they only make use of the gradients g:, That is, the ith output of ALG (i.e. X₂) is purely a function of the previous sequence of gradients gi, g.,..., - so that ALG is a first-order algorithm.
'This seems like significant issue to disregard, but we will provide mathematical justification shortly.

---

2.1 Learning the Scale in OCO
Just like stochastic optimization algorithms, most OCO algorithms also require a scale factor 8. In fact, many stochastic optimization algorithms (such as SGD and AdaGrad) are also OCO algorithms. Setting y) = ry for all SGD ensures the regret bound:
(
||x
x1
T
R SGD
(x)
SGD Finear
()) IO
+ 81)
gi
S71
From this equation, deduce in hindsight that for any given x, the optimal value for is which would provide the bound:
x
x-xill
Σ |
P SGD WITH TUNED
lincar
(Xx
S
O
|| x1
Σ B 12
This result is minimax optimal 27 but requires knowledge of the unknown optimal 8. Very re- cently, [14 16 15] have produced algorithms that estimate the value of ||x|AS - x|| on-the-fly and use this estimate to quickly identify the optimal scaling value These algorithms achieve impres- sive practical performance, but they require an understanding of the closed-form solution for the optimal value above. Our goal is to learn the correct scaling regardless of the base algorithm.
To this end, we will leverage scheme recently developed by [2 that allows one to automatically tune the scale of base OCO algorithm using another "meta" OCO algorithm. We reproduce their result below (with notation altered to suit our application) along with the short proof:
Theorem ((28). Suppose BASE and TUNER are both OCO algorithms. Let (x+^Sk} C. Rd indicate the iterates of BASE in response to an arbitrary sequence of gradients {geh. and let {si} C R indicate the iterates of TUNER response the sequence of scalars {he (gi, x... x1)}. Define new online algorithum MECHANIC via.
MECHANIC
xBASE + (xBASE xBASE).
MECHANIC ensures regret: Then X,
RMECHANIC
(x) < inf RIUUER (3) + &RBASE
((x x x
Ennear
Proof. By definition, for any 8, we have:
lincar
MMEHANICC
gi
BASE
3t (X.ASE xBASE) x)
t=1
BASE Bi Xx
X BASE 8) (g X
x XAASE
(x
x xBASE)
Rineur
(3) + 5 finear
BASEE + (x BASE) 1/8).
With this result, the job of finding the optimal s can usually be completely relegated to TUNER. Although the value appears in both terms of the sum RIUNEE ()) + & (x/ASE + (x x(ASE) / 8), turns out that for essentially all plausible BASE algorithmss, there a particular value & that causes
& RRASS (xRASE + (x- x / to obtain the optimal regret bound (3). Thus, by setting & to be
this value, which unknown a priori, we need only ensure that Ru (8) small enough to not significantly affect the overall regret bound. Note that this setting of 8 is done entirely in the analysis.
For example, if BASE is actually SGD with a learning rate and = as in 2 we have
DMECHANIC (x) < inf linear (3) + |
x 1|
EMECHANIC (x)
linear
+ Sm
g
3

---

setting 8
1
11 11-1-11 15:11
| x1 "V WE ||B:112
RUNNER
+0
| X1
||
lgll 1l?
Thus, if TUNER obtains low regret, then we will obtain the same regret bound as if we had optimally tuned the scaling factor for SGD. Intuitively, the gradient hn provided TUNER approximates the gradient over the entire course of the base optimizer rather than just at the most recent iterate. That is, for SGD, h, x 4f(x)==)) where X2 =1 - > -
k= T/KKk.
2.2 Parameter-Fre Free Online Optimization
The problem with the above result is that we seem have simply pushed the problem off to TUNER: what if TUNER itself requires us to set scale factor? Solving this problem has been the focus of The most advanced
substantial effort in the online optimization community (29) 30
28
such algorithms are able to ensure for all simultaneously:
T
Riiinar (8)
Σ
he(s: 8)
5)
1
S
Σ
n?
Thus, we set h4 (gr, x BASE
x x(AAEE), we obtain:
(8) 5O
B
Σ
gr, BASE X1 BASSE2
linear
In a theoretical development of this technique, it is necessary to prevent the terms (gr, xBASE x from becoming too large (as otherwise Ringar is large). Typically, this is accomplished by constraining the base algorithm to satisfy || |x - x < p for some user-specified arbitrary
p. Enforeing such a constraint means that the regret bound ( would only apply || S p. but
ensures that (g,, BASE x s p² |g Thus, by setting å = ||
1Ip, the combined
algorithm obtains the optimal regret bound of O(I x || VVT |lg. l12) (amazingly, the value of p irrelevant!). practice however, we do not attempt to explicitly enforce any such constraints and simply rely on the intuition that any non-diverging algorithm is unlikely to produce excessively large iterates.
At no point in this process do we need access to the internal state of the base algorithm BASE This means that improvements algorithm. In this paper, we investigate the performance of MECIANIIC on deep learning tasks. We consider a variety of settings for the base algorithm BASE (i.e. AdamW, Lion, SGD, with various batch sizes and learning rate schedules of various shapes), and employ parameter-fre free algorithm as the TUNER to automatically find the best scale factor for the base algorithm.
BASE will automatically be reflected in improvements
the overall
3 The MECHANIC algorithm
Our MECHANIC algorithm is specified in Algorithm ! The algorithm is built by applying Theo- rem] to parameter- free TUNER algorithm presented in Algorithm 2 which is described along with theoretical analysis in Appendix D. However, when building MECHANIC, theoretically tractable Algorithm to simplify the implementation while still capturing the essential intuition and maintaining the same performance. In the remainder of this section will provide some intuition behind the TUNER update as used in MECHANIC as well as describing some poten- tially unfamiliar subtleties relating to use of exponentially weighted moving averages.
modify the "pure"
MECHANIC takes as input a base algorithm that generates update vectors u, as described in the previous sections. We then set A =Et= Ug x x[ASE_ The majority of the algorithm contains TUNER method, which is a variant of the analytically tractable Algorithm 2 with

---

Thus, the update looks like a combination of an AdaGrad-esque gradient descent step with learning rate scaled by 8, and kind of "adaptive decay" (multiplication by ) The adaptive decay very important for stabilizing the algorithm: without it the values for s; are prone unchecked Algorithm MECHANIC
1: Input: Base algorithm BASE. B E
[0. 1 (default n = 6, 3
(0.9, 0.99, 0.999, 0.9999, 0.99999, 0.999999), X I (default 0.01). Sinst R:
first non-zero value (default Sinit = 10- ). = 10 10- small value for numerical stability.
2: no f- RR", ro f O RR, mg <- E R." X BASE
3: A f- E I2d
4: 0 E R". // We will use 8t,1 to indicate the ith coordinate of 8t.
5: for = Io.
VV((,, 2,). x/ is the Ith set of model parameters and is the /th minibatch. 7: Send gr to BASE, receive update up. // On its own, BASE would update X++1 < X₁ + uy.
6:
8: [Optional] Set A, =
X, -ref to save memory instead of storing A, from last round.
(Ei- )E
9: Artl t A Up.
2 (E
9t.m |R
10:
h4 +
Ai. +
// Note use A rather than A
x my max max(3m (4) (multiplications by / and maximum are taken coordinate-wise)
12:
+ f111111 h
FE 3r--1 St-1he
14:
& max(0.r,) r,) This step is used instead of more complicated procedures in Algorithm)
W. f- Sin +
W,
16:
8t41
Verte
X1+1
BASE
+E 8441,)) Ac+1
18: end for
few modifications. Note that the indexing on A very important and may be counterintuitive: the definition of ht does not include A+t1, but rather A. h2 is the "gradient" that is supplied to TUNER, as described by Theorem
To gain some intuition behind the update, let us consider the case that n = 1 and 3 = 1.0 (that is, without employing any exponentiallywweighed moving averages). We keep track of the quantity W, Sinst my Ei=1 hysk. which usually called the "wealth" of the algorithm (the quantity Ei= h is sometimes called the "reward"). Sinit specifies the starting value for s, and should be an under-estimate of the true optimal scaling. We then set 8t+1 = W. (neglecting the included for numerical stability). To understand this update strategy, we can re-write the update as:
ve,
8t+1 = 8t V
sphe
2 (1
sehe
St
20:
exponential growth due to scaling by st in eche, Intuitively, this decay is the minimum amount required to prevent instabilities.
In Appendix D we provide a formal Theorem bounding the regret of a variant of the procedure described above. Roughly speaking, for this result suggests:
T
T
he(st - 50 max st) mr + 3 log(T33///g Σ 1
(5)
In fact, the dependence of O(log
equation can be improved to O(vlog(T) via more However, we favor the simpler update and pleasing
complicated algorithms (e.g. 28 12
31
32
resemblance to familiar algorithms like AdaGrad via the Taylor expansion analysis above. Of note, the dependence Sinit is very mild: this suggests that should be able set sint to very small
5

---

value without damaging performance. In practice, we choose Sinit 10 10- which we expect to dramatically underestimate the optimal value all scenarios.
We hypothesize that the simplified TUNER we use in MECHANIC in fact possesses a rigorous theoret- ical analysis (although perhaps only with respect simpler non-fully-worst-case adversaries), but demonstrating such a bound appears to involve difficult technical hurdles. In particular, our imple- mention is designed to "scale-free": rescaling the values of gr by any constant scalar will have no effect on 8t. This property was first achieved only recently in theoretical analysis of parameter-free algorithms [2]. and ys- requires significantly more involved algorithms [2 33
3.1 The use of)
We include / introduce some recency bias in the statistics recorded by MECHANIC, common feature of practical optimizers. Mathematically, we accomplish this by up-weighting the /th feed- back to TUNER by 9- h4 + h,g5 Thus, for example, we have V, = Ex= 8 and - - Using these weights directly results in numerical stability issues as the weights become exponentially large. Instead, since we only need to maintain the correct ratio W. y
we can cancel a factor of 3.¹ from both sides, giving the update equations in Algorithm
We found that tuning the value of B can significantly improve performance different tasks. Thus, we incorporated multiple 3 values simultaneously in a way that obviates the need for such tuning.
Our approach is inspired by work on "'combining" parameter free algorithms (34 The idea is simple: parameter-free algorithms typically ensure Rinear < for some constant e set by the user. So, if st,1,..., St,n the outputs of n parameter-free algorithms with regret bounds Rl (s).... R [innaa (8), we have for any j:
T
n
T
T
he
Σ 1=1
$1,5
$
Σ
he(s1.5 - 3) +
h4 (1 -0)
1=1
igf t=1
R (8) +
Riinear (0) S Ry Ri (8) + (n 1)c.
(
So, with small constant additive overhead in the regret, the sum of all the outputs st,1 + ....... + St, achieves the same regret as the best of all the outputs. Motivated by this observation, instantiate n = copies TUNER with different 33 values and add their iterates to produce a final scaling.
3.2 Weight decay
Finally, we found that an addition of a peculiar weight-decay-esque term helped significantly on certain tasks, including vision tasks with smaller datasets, multi-objective NLP tasks and es- pecially with reducing the variance final results for all tasks. Specifically, rather than pro- viding h4
(ge, A.) the input to the TUNER algorithm, we instead provide h, (g. + (.:l 85.4) xx
A.). We conjucture that this term helpful in the common case that the base algorithm itself is incorporating regularization or weight-decay.
[x
This extra term is the derivative of the regularizer x + Allgell (Ein st,;) ||x|| From standard theoretical perspective, this regularization may seem overly large. However, may not have as big an impact as one might imagine because the base algorithm does not see this regularization. Instead, the base algorithm may (or may not) perform weight decay using another method that MECHANIC has no insight into. That said, we do not propose an analytical explanation for this modification. We simply observed that in practice it performed well with a fixed 0.01.
3.3 Runtime and Memory Cost
MECHANIC incurs little additional cost over that of BASE. Algorithm I we denote dddimensional vectors with bold font, and n--imensional vectors and scalars with normal font (note that typically n = 6). We use I additional (dd) memory slot, and four (dd)-imme steps in lines 8, 9, and 17. All other steps are O(1) O(n) time and so have negligible cost.

---

Model
Size
Pre Opt
MLM
Optimizer
MNLI-m/mm
QNLI
SST-2
QQP
AdamW
84.3/84.8
91.0
92.4
90.1
AdamW
71.5
M-AdamW
83.7/83.5
90.6
91.9
90.5
BERT-B
110M
AdamW 84.7/85,1
91.2
93.3
90.7
M-AdamW
71.7
M-AdamW
84.5/84.4
91.3
92.5
91.1
Lion
83,4/83.5
86.8
89.7
89.4
Lion
71.8
M-Lion
83.1/83.8
89.9
91.0
90.2
BERT-B
110M
Lion
84.5/84.2
89.0
91.2
90.8
M-Lion
72.0
M-Lion
84.2/84.2
88.6
91.1
90.2
AdamW
86.2/86.4
92.2
93.9
91.3
AdamW
75.4
M-AdamW W
86.1/86.4
92.5
93.7
91.5
BERT-L
340M
AdamW
86.3/86.5
92.7
94.4
91.4
M-AdamW
75.3
M-AdamW
1/86/
91.7
93.5
91.5
Lion
86.7/86.6
90.7
92.9
91.1
Lion
75.7
M-Lion
86.0/86.2
90.3
93.4
91.2
BERT-L
340M
Lion
87.4/87.4
92.9
93.3
91.7
M-Lion
75.5
M-Lion
87.2/87.1
91.5
92.3
91.6
Table 1: Comparing MECHANIC on BERT. 5 largest datasets from GLUE. Results reported are peak validation scores averaged over runs, both for the baseline and MECHANIC tuned models.
4
Experiments
In this section we describe our experiments using MECHANIC to tune various base optimizers on dif- ferent tasks. Note that almost all base optimizer implementations require a user-specified scale factor which is is not directly visible to MECHANIC. We set this value to 1.0 before applying MECHANIC. Since MECHANIC multiplies the base update by st. setting the base scale factor 1.0 allows to interpret as the "correct" value for the base scale.
4.1 Masked Language Modeling
We perform BERT pre-training the Wikibooks dataset following the procedure from [35 with few minor changes, most notably, we omit the Next Sentence Prediction (NSP) loss following [36]. Masked language modeling (MLM) requires reconstructing randomly masked tokens given input sequence of tokens. As shown in Table using MECHANIC leads to a noticeable improvement in MLM accuracy.
Varying batch size and model size: Past works observe that the scale factor s should decrease either batch size is decreased that MECHANIC learns, we vary the batch size and model size while pre-training BERT using ME- CHANIC. As shown in Figure in both cases, MECHANIC learns decrease the scale factor when decreasing the batch size and when increasing the model size.
model size is increased [37 (38]. To inspect the scale factor
Addition Ablations: Ablation studies on the effects of X, Sinit can be found in Appendix B
Finetuning pre-trained models: In addition to pre-training, evaluate models the largest datasets from the GLUE suite [39] One possible failure mode of MECHANIC tuned pre-trained models could have been that, even though they lead high accuracy at pre-training time, transfer learning may fail at finetuning time.
To ensure that standard transfer learning pipelines still work with MECHANIC pre-trained models, we finetume them without learning rate tuner using the Adam optimizer and find that MECHANIC pre-trained models lead to higher accuracy at mr-itraining time. and they also outperform in finetun- ing more often than not. We finetune BERT-B B 10M) and BERT-L (340M) models for at most 10 epochs on each of the GLUE datasets and report results the GLUE dev set in Table
Using MECHAND for finetuning: We also investigated using MECHANIC for finetuning. Typically, to not erase the progress already made, much lower base learning rate is employed at finetuning

---

65
AdamW Mt-AdmmW
20"
64
MLM Acc
30"
60
22-4
Batch Size
of examples
(a) Varying batch size
75
10-1
AdamW
70
M-AdammW
BERT-S
10"2
BERT
MLM ACC
65
BERT-B
60
10
5
55
50
45
40
BERT-TI
BERT
BERT
10-4
0.0
1.0
1.5
2.0
Model Size
# of examples
(b) Varying model size
Figure Scaling values s learned by MECHANIC while varying batch size and model size.
time. This could easily have been a potential failure mode of any kind of automatic learning rate tuner such strategies might "explore" a high learning rate at the beginning of the optimization procedure. Fortunately, we observed that this inductive bias typically baked at finetuning time still maintained when using MECHANIC.
4.2 Image Classification
this Section, we present results on popular Image Classification tasks. Apart from training from scratch, we also perform transfer learning experiments where we pre-train on the JFT-300M 440 dataset and finetune on ImageNet, Cifar-10 and Cifar- 100 datasets. We follow the exact setting employed in [1 for both pre-training and finetuning.
As shown Table 2 MECHANIC is quite competitive across the board and produces results either very close to the baseline or better. Since MECHANIC optimizes for the train loss, in general, we observe that it results better test performance on tasks with large amounts of data where the model is unable to overfit to the train set. For instance, we see that MECHANIC beats the baseline substantially when pre-training ViT models on JFT-300M, whereas lags slightly behind on smaller datasets like ImageNet- 1k or CIFAR-10W 10/100. Even though we fix À to 0.01 as default for all our reported experiments, we find that for small datasets like CIFAR- 10, increasing led better test performance.
4.3 Comparison with D-adaptation
Recently, 16 introduced the D-adaptation algorithm, with the same goal of learning the correct scale for SGD and Adam base optimizers. D-adaptation showed impressive empirical results on range of popular deep learning tasks, so we compare MECHANIC with D-adaptation on a selection of tasks that D-adaptation worked well on, using code provided by the authors. Hyper-parameter set- tings were kept the same ensure fair comparison. contrast to D-adaptation, MECHANIC does not require modification for different base optimizers and, shown in Figure 2 it remains quite

---

Model
Size
Pre Opt
Pre Acc
Optimizer
11K
Cifar100
Cifar
CNN from scratch on CIFAR datasets
Mom
77.6
95.4
ResNet-18
11
M-Mom M-Mom (A 0.1)
75.3
94.1
76.6
95.3
Mom
79.9
WRN-40-10
56M
M-Mom
79.6
Pre- traitrain IFT-300M
Mom
84.7
91.9
99.1
A
48.5
M-Mom
84.7
90.7
99.1
ViT-B/16
86M
Mom
84.2
91.5
99.1
M-AdamW
49.9
M-Mom
84.1
90.3
99.1
Mom
85.3
92.1
99.2
Lion
47.0
M-Mom
85.2
91.0
99.2
ViT-B/16
86M
Mom
84.7
92.3
99.2
M-Lion
49.6
M-Mom
84.6
90.9
99.1
Mom
86.7
93.9
99.5
AdamW
54.4
M-Mom
86.6
92.7
99.5
VIT-L/16
307M
Mom
86.3
93.4
99.4
M-AdamW
54.4
M-Mom
86.0
92.0
99.3
Mom
86.7
93.8
99.4
Lion
52.0
M-Mom
86.7
93.0
99.4
VIT-L/16
307M
Mom
87.2
94.0
99.4
M-Lion
55.4
M-Mom
87.2
93.4
99.4
Table 2: Comparing MECHANIC vision models. All fine-tuning results are averaged over
independent runs with different seeds.
competitive on small datasets like CIFAR-10/100 while outperforming both manually tuned base- line and D-adaptation on bigger tasks like IWSLT14 and language modeling on BookWiki dataset. We present additional results in Appendix including comparison on suite of 12 logistic regression problems.
Conclusion
MECHANIC new technique for scaling the updates any base optimization algorithm. Our approach provides practical implementation of recent developments in optimization theory, and is able to match the performance of tuned baselines on large-scale machine learning tasks. This work suggests several natural future directions. First, is there theoretical motivation for our weight-decay term? Next,
possible to leverage similar techniques to learn a per-layer scale factor? Such capacity would not significantly increase computation cost, but by allowing more degrees of freedom may yield a method that significantly outperforms baselines since is infeasible to manually tune a scale factor for every layer.
Acknowledgments
Ashok Cutkosky acknowledges funding support from NSF grant CCF-2211718, an Amazon research award, and Google.
References
[1] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2668 2013.

---

CIRAR-10 o (WRN-16-8)
CIFAR-100 (DenseNel)
955
Test Accuracy (8)
75
Test Aecuracy
.90
70
865
D- D-Adapt SCD (95.56% SE 0.04)
D-Adapt SCD (76.90% SE 0.06)
80
SGD (95.59% SE 0.0.3)
80
SGD (76.41% 11% SE 0.14)
(95.46% 0.03)
Mechanic (75.44% 0.08)
50
100
150
200
250
300
100
150
200
250
300
Epoch
Epoch
IWSLT14 (LSTM))
BookWiki (GPT Transformer)
40
Adam (1.31 SE 0.003)
Adam (19/19 SE 0.012)
Mechanic Adam (4.31 .044
Test Perplexity
D-Adapt Adam 119.6 SB 0.019)
D-Adapt Adam (4.33 SB 0.003)
30
Mechanic Adam (18.60 SE 0,038)
25
15
10000 20000
30000
40000
50000
60000
10000 20000 30000 40000 50000 60000
Step
Step
Comparing MECIANIIC with D-adaptation and Adam or SGD with manually tuned learn- ing rates on vision and language tasks.
Figure 2:
[2] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 0rXiv:1912.02365 2019.
[3] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COL.T), pages 257-269, 2010.
[4] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014.
[5] nya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2018
[6] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, al. Symbolic discovery of optimization algo- rithms. arXiv preprint arXiv:2302.06675, 2023.
[7] H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), pages 244-256, 2010.
[8] Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation machine learning: a survey, Journal of machine learning research, 18, 2018.
[9] Kartik Chandra, Audrey Xie, Jonathan Ragan- Kelley, and Erik Meijer. Gradient descent: The ultimate optimizer. Advances in Neural Information Processing Systems, 35:8214-82255, 2022.
[10] Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 577-585. Curran Associates, Inc., 2016.
[11] Ashok Cutkosky and Kwabena Boahen. Online learning without prior information. In Confer- ence on Learning Theory, pages 643-677, 2017.
[12] Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-nomn adaptivity in on- line learning. Conference on Learning Theory, pages 2858-2887, 2020.
10

---

[13] Kfir Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with recursive momen- tum for nonconvex optimization. Advances in Neural Information Processing Systems, 34: 20571-20582, 2021.
[14] Yair Carmon and Oliver Hinder. Making sgd parameter-free. Conference Learning Theory, 2022.
[15] Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dy- namic step size schedule. arXiv preprint arXiv:2302.12022 2023.
[16] Aaron Defazio and Konstantin Mishchenko. Learning-rate- learning by d-adaptation. arXiv preprint MtXXiv23301.7733: 2023.
[17] Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang. Disentangling adaptive gradient methods from learning rates. arXiv preprint arXiv:2002.11803 2020.
[18] Zhou Lu, Wenhan Xia, Sanjeev Arora, and Elad Hazan. Adaptive gradient methods with local guarantees. arXiv preprint arXiv:2203.01400 2022.
[19] Xinyi Chen and Elad Hazan. A nonstochastic control approach to optimization, arXiv preprint 230.00330..7900, 2023.
[20] Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. In Advances in Neural Information Processing Systems 30: An- nual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 2157-2167, 2017. URL httpp://pppae nips. cc/paper/ 6811-training- -
wwthout- -earntt---annnnn-eee rates -oroough- ottaaaaeeeaaiiaaaaeeeorrrrrrrrrr
[21] Ashok Cutkosky and Kwabena A Boahen. Online convex optimization with unconstrained domains and losses. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 748-756. Curran As- sociates, Inc., 2016
[22] Shai Shalev-Shwarzz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
[23] Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv:1909.05207, 2019.
[24] Francesco Orabona. arXiv:1912.13213. 2019.
A modern introduction to online learning.
arXiv preprint
[25] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 928-938 2003.
[26] S. Shalev-Shwarzz. Online Learning: Theory, Algorithms, and Applications. PhD thesis, The Hebrew University of Jerusalem, 2007.
[27] Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the nineteenth annual conference on computational learning theory, pages 415 415-424, 2008
[28] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in Banach spaces. In Conference On Learning Theory, pages 1493-1529, 2018.
[29] Brendan Memahan and Matthew Streeter. No-regret algorithms for unconstrained online con- vex optimization. In Advances in neural information processing systems, pages 2402-2410, 2012.
[30] Brendan McMahan and Jacob Abernethy. Minimax optimal algorithms for unconstrained lin- ear optimization. Advances Neural Information Processing Systems, pages 2724-2732, 2013.

---

[31] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pages 1216-1259. PMLR, 2021.
[32] Francesco Orabona and Dávid Pál. Parameter-free stochastic optimization of variationally coherent functions. arXiv preprint 1XXi::2002.002366 2021.
[33] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Proceedings of Thirly Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4160-4211, PMLR, 2022.
[34] Ashok Cutkosky. Combining online learning guarantees. In Proceedings of the Thirty-Seconal Conference on Learning Theory, pages 895-913, 2019.
[35] Jacob Devlin, Ming- wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Con- ference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies, Volume (Long and Short Papers), pages 1171-188,, Minneapo- lis, Minnesota, 2019. Association for Computational Linguisties. doi: 10. 10.18653/v1/N19/ 1423.
1423.
[36] Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis. Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. ArXiv preprint, abs/1907.11692, 2019. URL https://arxiv.or org/
abs/1907 11692
[37] L. Bottou and O. Bousquet. The tradeoff's of large scale learning. In Advances in Neural Information Processing Systems (NIPS), 2008.
[38] Shixiang Shane Gu, Sergey Levine, Ilya Sutskever, and Andriy Mnih. Muprop: Unbiased backpropagation for stochastic neural networks. CoRR, 0ts/1511.05177 2015.
[39] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bow- man. Glue: A multi-task benchmark and analysis platform for natural language understanding. ArXiv, abs/1804.07461, 2018
[40] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning era. 2017 IEEE International Conference on Computer Vision (ICCV), Oct 2017. doi: 10.1 (0.1109/icc.22017.99
http: doi org/ 1109/
2017.9017.97
[41] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL http:///ppaaeeeeee.eeee/rrrrraar
[42] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdi- nov. Dropout: A simple way prevent neural networks from overfitting. Journal of Ma- chine Learning Research, (9(6)):929-1955)) 2014. http::/m:/ org/ hang/papers/vis v15/
srivastava14a. html
[43] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, Yifeng Lu, and Quoe V. Le. Symbolic discovery of optimization algorithms, 2023.
[44] Ashok Cutkosky, Artificial constraints and hints for unbounded online learning. In Proceedings of the Thirty-Second Conference on Learning Theory, pages 874-894, 2019.
[45] Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Conference on Learning Theory, pages 2490-28 P5.. 2019.
[46] Michal Kempka, Wojciech Kotlowski, and Manfred K Warmuth. Adaptive scale-invariant on- line algorithms for learning linear models. In International Conference on Machine Learning, pages 3321-3330, 2019.
12

---

A Limitations
In this paper, we introduce a technique for automatically learning the right scale of the learning rate called MECHANIC and evaluate it a broad range of practical deep learning problems and settings. We find that, depending on the problem, MECHANIC can be quite effective and even surpass performance of manual tuning of learning rates fraction of the cost. We also find that in addition to training from scratch, MECHANIC also works for finetuning.
While the initial set of results encouraging, many challenges remain. Firstly, found that MECHANIC does not seem to work well with dropout [2)]. While MECHANIC is effective against noise from sampling, work well with MECHANIC. Second, MECHANIC re- purposss the gradient coming from the train set for learning the learning rate, which means optimizes for train loss. This is different from manual tuning of learning rates where researchers tune it based on performance on the validation set. A principled way handle this discrepancy is also in interesting avenue of future research.
believe there may be
fundamental reason why dropout does not
B Additional Ablations
B.1 Setting BASE learning rate with Mechanic
Even though we recommend setting peak learning rate of Base optimizer to 1.0, to make sure that Mechanic truly is insenstive to the peak learning rate and robust to the choice of this hyperparameter, we conduct study where we vary peak learning rate of AdamW on BERT-B masked language modeling task. As shown in Table 3 Mechanic is largely robust against choice of peak LR set for AdamW on BERT-B MLM task.
Peak LR of BASE with Mechanic
MLM Acc
le-2
71.7
le-1
71.6
lc0
71.6
lcl
71.4
71.6
Table MECHANIC is largely robust against choice of peak LR set for AdamW on BERT-B MLM task.
B.2
Robustness to Sinit
Ssnit
1e-8
1e-7
1e-6
le-5
le-4
Accuracy
49.8
49.8
49.9
49.7
49.6
Table 4: Accuracy on JFT-300M using model ViT-B/16 and optimizer M-AdamW as a function Sinit. MECHANIC is robust to varying this parameter.
B.3
Ablation of
A
0
le-3
le-2
le-1
1e0
Accuracy
49.7
49.8
49.9
49.7
Diverged
Table 5: Accuracy on JFT-300M using model ViT-B/16 and optimizer M-AdamW as function A. We have observed that while is helpful in stabilizing MECHANIC some problems, long set to a reasonable small value it does not affect performance by lot.
13

---

B.4 Number of? 3 values
Number of B values (n)
Accuracy
48.9 49.5
49.9
49.6
Table 6: Accuracy JFT-300M using model ViT-B/16 and optimizer M-AdamW function n, the number of B values. The 3 values are set as 1 - 0.1* for from to n. This is the most sensitive parameter in MECHANIC. For smaller we see some significant performance degradation, while for larger we see milder degradation. Theory suggests that larger n should result in a degradation that roughly logarithmic in
C Additional Experimental Details
C.1 Hyperparams for BERT
Model
Aug
Optimizer
81
Ir sweep
best Ir
Weight decay
BERT-B
AdamW
0.9
0.999
[5e-4, 1e-3, 2e-3, 5e-3, 1e-2] [5c-4, 1e-3, 2c-3, 5e-3, 1c-2]
5e-3
BERT-L
AdamW
0.9
0.999
le-3
BERT-B/I
M-AdamW
0.9
0.999
0.01
BERT-B
Lion
0.9
0.99
[5e-5, le-4, 2e-4, 5e-4, 1e-3]
5e-4
BERT-L
Lion
0.9
0.99
[5e-5, Ic-4, 2c-4, 5c-4, 1c-3)
2c-4
BERT-B/L
M-Lion
0.9
0.99
0.1
Table 7: Critical hyperparameters used for BERT pre-training. For the baselines grid searched the learning rate as shown in the table. Batch size 2k, trained for 150k steps on original Wikibooks dataset w/o NSP loss (similar Roberta). We found that small amount of weight decay makes MECHANIC slightly more effective.
Model
AdamW LR
MECHANIC-Adam
BERT-B
71.1
71.5
71.5
71.5
71.3
71.7
BERT-L
75.0
75.4
75,4
74.6
74.4
75.3
Lion LR
MECHANIC-Lion
BERT-B 70.8
70.8
71.1
71.8
71.4
72.0
BERT-L 75.1
75.6
75.7
74.7
Diverged
75.5
performed grid search of learning rate values for each base optimizer. Here, we present the resulting accuracy values.
Table 8: As detailed in Table 7
14

---

Hyperparam
Optimizer
Without MECHANIC pre-training
With MECHANIC pre-training
Learning Rate
Adam
[5e-5, le-4, 2e-4, 3e-4. 5e-4] [5e-6, le-5, 2e-5, 3e-5,
[le-5, 2e-5, 3e-S, Se-5, le-4] [le-6, 2e-6, 3e-6, Se-6, le-5]
Learning Rate
Lion
Batch Size
[16, 32]
[16, 32]
Weight Decay
Max Epochs
10 Lincar
10 Lincar 0.06
Learning Rate Decay
Warmup Ratio
0.06
Dropout
0.1
0.1
Attention Dropout
0.1
0.1
Table 9: BERT GLUE finetuning hparams with AdamW.
Hyperparam
Value
Batch Size
[16, 32]
Weight Decay
Max Epochs
10
Learning Rate Decay
Linear
Warmup Ratio
0.06
Dropout
0.0
Attention Dropout
0.1
Table 10: BERT GLUE finetuning hparams when using mechanic at finetuning time. We found
limitations of MECHANIC that does not perform well in combination dropout, set dropout rate to 0 for these experiments.
C.2 Hyperparams for Image Classification
Model
Aug
Optimizer
81
92
Ir
Weight decay
Num epochs
VIT-B/16
AdamW
0.9
0.999
8e-4
0.1
VIT-B/16
M-AdamW
0.9
0.999
0.1
VIT-L/16
AdamW
0.9
0.999
4e-4
0.1
VIT-L/16
M-AdamW
0.9
0.999
0.1
VIT-B/16
Lion
0.9
0.99
le-4
0.3
VIT-B/16
M-AdaaW
0.9
0.99
0.3
VIT-L/16
Lion
0.99
lc-4
0.3
VIT-L/16
M-AdamW
0.9
0.99
0.3
Table 11: Critical hyperparameters we used for all the experiments, most of them directly repurposed from 4T. For each baseline repurposed well-tuned base learning from previous work [ 43 Trained on JFT-300M with batch size 4k with L.R cosine decay schedule.
15

---

Res
ViddekesNet-40OO0//IAAAAOOO
0.07
0.06
0.015
0.35
0.04
0.010
0.03
0.005
0.01
0.000
0.00
125
150
200
25
50
75
100
epoch
opoch
Figure Scaling values s learned by MECHANIC during ResNet18 training on CIFARIO and WideResNet training CIFARIO0. Shaded area represents max/min value over 3 runs. Dark line is average.
Hyperparam
ImageNet
Clfar100
Cifar10
Learning rate sweep
(0.003, 0.01, 00.03, 0.06}
f0.001, 0.003, 0.01, 00.03)
{0.001, 0.003, 0.01, 00.03)
Batch size
512
512
512
Weight decay
0
Num steps
20k
10k
10k
Warmup steps
500
500
500
Learning rate decay
Cosine
Cosine
Cosine 0.0
Dropout Clipping norm
0.0
0.0
1.0
1.0
1.0
Table 12: We directly use VIT finetuning hyperparams recommended by [41]. For MECHANIC we also use same hyperparameters, omitting just the learning rate sweep, since we don't 't need it now. We use finetuning resolution 384.
Hyperparam
Value
weight decay Ir SGD Momentum / batch size num epochs schedule augmentations
[0.001, 0.0005, 0.0001]
[0.3, 0.1,0.03)
0.9
128
200
Step decay by 0.2 at 60, 120, 160 epochs
Random Crop, Random Horizontal Flip 1.0
Gradient clip by global norm
Kept at default 0.01
Table 13: Hyperparameters for tuning ResNet18 CIFARIO and WideResNet CIFAR100
C.3 Hyperparams and additional results on comparisons with D-adaptation
D Theoretical Analysis
Here provide the theoretically tractable version of TUNER well as its analysis.
D.I Algorithmic Simplifications
To simplify the implementation of MECHANIC, we replaced the red in Algorithm with single line Tt max(0, rı) right after the definition of rt. This is motivated by two ideas.
16

---

Settarleas
Accurscy
Accunscy
70
80
80
Adam 0.01)
Aduun
60
D-AdiptAlam (90.0 0.071
D-Adupt (97.1
70
D-Ailipt Adaas
Niechentc Adurn 150.3 0.013
Mechanic Adam cPuu suz 0.00
Mtechanae Adam (100.0 0.00)
20
69
100
20
40
60
80
100
20
20
109
Epock
Epach
Epoch
Class
Lzsa
Lettoer
100
76
Accunuoy (Nr
Aecuraec (%)
75
60
Adam L72,5 SE 5:141
Adam (98.3 SE. (.D.13
Advin (F7.6 SE 5.011
Nochhaiis Aduass (57.6 0.25)
D-Adapt.AAae Adamn (72.3 0.19)
Mdeduuis Adlun (98.0 SB 0.07)
D-Adupt Adaan (99.0 SE 0.009
70
D-Adapt 122,2 SE 0.011
Nocharie Adurs 177.7 SE 0.013
300
100
80
Epoot
Epoch:
Eproh
Peodiiiits
SoaENORR
35
(80
90
Accussry (55)
Necuuuy (%)
80
24
0.03)
92
D-Addpp Adaum (20.8 0.021
40
D-Adlpt 0.04)
D-Adlapt 198.6 0.011
Nicchanic Adiass 0.08)
Mechhnicc (20.8 S2 0.10
Niechazic Adars 158.1 0.013
200
100
100
Epock
Epach.
Epoch
Volade
Vonca
Wase
80
80
60
60
50-
Adim (62.1 SE 0,081
Adam (77.4 SE 0.13)
Adam (1 (100.0 SE 0.50)
40
D-Adeap Adam 0.16)
D-Adapt (27. 0.15)
D-AAdppt Adarm (100.d 0.000
Nicchantc Adamm (50.7 0.11)
Mechaniic siz 0.050
Mechanic Adam (100,0 0.00)
30
20
300
150
100
Epack
Epoch
Epoch
Figure 4: Comparing MECHANIC with D-adaptation and manually tuned learning rates on a suite of convex tasks.
CUNAOLO (M036-1G4)
CIIMB-10E CeasNNe
Doubiiie IGFT Truntarmad
320
SIDD SE 6ed51
SCD 2e-2222222222 50 2.2000
Doddlpp SE 8.003)
10
Naclauiic 12 Se-00 (3405)
Nachasi: S. 54000)
Mieclaiic Adua 115:2 50.0200510000 5233303)
20-4
Sur3000 Koee
00
Adara 13.221 ST. 8
A6.2-6222 0023
Mechazi: Ades (64310 SE (2501)
Miachatic Adue 14 0
D-kdap: Adam 154225 830220
2- (6.3
7.5
20
10200 200ce 2006 50200 50030 63003
Figure 5: Complementary train set results of MECHANIC with D-adaptation and manually tuned learning rates on vision and language tasks.
17

---

Algorithm TUNER((herreticall tractable version
1: Input: 3 10 W6: initial "wealth".
2: no 6 IR, ro < 0 E R. q: + E R, mo + 0 R, 81 t R
3: for [orl=10 T...
4: Output St.
5: Receive le.
6: m, f- maaxx3m,-1111 (11))
7:
h = clip(hy, 11 m1--1) // Red text are steps that we omit in practice (see Algorithm
8:
qr 3q:-1 + th:
9:
t 8r:-1 -
10:
W, t Wn + +r+ // Blue text is changed in practice (see Algorithm !
11:
Ut + pZ ui-it hā
12:
81+1 V Vimi+uute clip(q:/ + 0,
W.
end for
First, we conjecture that the clip operation using q:/ oy may even be unnecessary in theory observed no change from removing this operation in practice, and observe that the update has an intuitive interpretation via the Taylor expansion discussed in Section 3
Second, the clip operation on hy using m is essentially designed to prevent the wealth W, from becoming negative
using the gradient truncation technique employed by 44 45 12 While less consistent with known theory, we found it simpler to ensure the wealth W, does become negative would cause the
simply by clipping rr directly (we did clip W, be nonnegative as W, algorithm to output & for all future iterations). We found these changes simplified the algorithm while having noticeable effect the performance. Although these deviations technically do come with guarantees, the accomplish similar intuitive goals and so we expected (and observed) that they simplified the implementation while not damaging performance.
D.2 Eliminating Wo in favor of Sinit
While TUNER makes use of the "initial wealth" value Wo. MECHANIC instead adopts a varying value for Wo proportional to Sinit my- This makes the first value proposed by MECHANIC equal to Sinit, which is more intuitive to set than Wn. The exponential growth in s allows us to set 8init to very small value of 10-8, also makes the values for "scale-free" in the sense that rescaling the updates u, by any constant will have no effect on the resulting 8t-
D.3 Regret Bound
Theorem 2. With 1, Algorithm guaranntes for all $ 0:
T
Σ he(st - 3) S Wo ($+ max st) mr + log(T šmy /m Wo),
Σ h2
Proof. First, we employ an argument developed by
44
T he(st -8) +
Σ
he(s:
8) <
hh hel(1sel 181)
1=1
t=1
1=1
he(st 8) (max [st] [81) hh,
hel
he(st - 8) + mT (max [se| + [$]).
PRemoving the clip in theory may requiring some additional worst-case assumption.
18

---

So, in the following, it suffices to bound E ho(st- 3). This is helpful because we will be able use the bound | S m and m is known before he is revealed.
As is typical the analysis of parameter-free free algorithms, the proof proceeds by lower-bounding the wealth. Define a function a(x) piecewise by:
2 S 0 3 E [0, 1] x²
a(x)
12/2
1/2
x 2
Notice that a(x) is differentiable, monotonically increasing and I-Lipschitz. We are going roughly show that Wi 2 1((exp((-EEx va))) after which the regret bound will follow from the wealth-regret duality [10].
The key technical inequality in the proof the following: for any A, B, m with z 4m?, and any |x|| S m, we have:
A
x
A
-A x
x²
a
clip
0,1
2
(6)
VB
VB
VB+ x²
B
Once 6
is established, we proceed as follows: defining Ct clip(Ens]
hx/ V
im
+
1
-
we
have:
log(W,) = loollo( (0g( + log(1 - )(ce)
2 Log(WW-11 hice - Rí c7
where we have used 6 S 1/2 and the identity log(1 x) 2 - x² for x S 1/2 (which applies
since hg I m by definition). Now, set = E1=1 dip and B = 4m + 1 and x = h in 06
we see that:
x VB
AA
log(W)) - log((W))))
2
clip
0,
/B"
4m
Vi-1
-A œ
A
x²
h2
2 a
B x
B
B
Amg 1 Ve-1
Ek hi
Σ1 hxs
2
4m2_ Uz-1
4m7 1 + Ut
Am? 1 + Ve-1
Ei=r Puke
E111 h
24g
2 a
a
V 4m Ue
4m + U2-1
4m + U2-1
Thus by telescoping the sum, we have:
2k= hi
T Σ
2h
log( (gg(W)) > log( Wo)
VeT
4m + vt-1
Now, observe that log((T CoggTmmT/ne m that overall:
2hg
2h
< 2(log(v:) log(")-))), so we have Σ mt
<
+
Womn T2m
DT km
Peu
]
WT >
exp
Ur
19

---

Thus, if we define p(H)
Wom exp 75mp
we have Wi 2 p(- Oy(Ek=1 ha). Now, we
VeT
employ the reward-regret duality:
T
Σ
he(s: - 8) Siiit +
Σ
(-hu) WT
1=1
S Wn + sup GGGpp())
G
Wn + p (8(
S Wo + O(s log(sT/ Smitt) /UT)
Where is the Fenchel conjugate of p and the evaluation of the conjugate follows from direct calculation (see, e.g. 10, 28 46)).
Thus, to prove the theorem we need only show 66 This is established via casework in a manner similar to [46]
Case 1. -4 S 0: In this case, the statement is equivalent to: 2 VB
-A-x (B+x*
Note that since
0, we have A 220 0. Therefore:
A
B + 12
VB xx +B+
VB + x2
Further, we clearly have /B4z2 that:
A
x22 2(B + x2)
S x²
S a
B
+ +
v B +
So, the following we assume
VB 0.
Case 2.
У 0: In this case, it suffices to show e A/
( 0,1)
B
x²
B
The case
assumption implies m -2 0. Therefore, since B 2 4m clip A
0,1
that
/B
- VB
clip
A 0,1 24 as desired.
So, in the following now further assume
VB+x²
Case 3.
-4
E [0, 1]: We have (-t))
4²
and also since a(2) < 1 for all 2, a
-A-
VB
2B.
(A+a))
Thus, it suffices to show that
A2
A
(Ata)2
a²
but this equivalent to B
(A+a))
2(B+a")
2B
B
2B+r
2B
(A+r))
a² which clearly holds.
2(B+02)
2B.
Case 4: -4 2 and
In this case it suffices to show
73 To
VB
VB+2
VB
VB
B
see this, we have:
-A - 2
-A
B 7
/B
VB + x
< -A
+ T
VB
VB
VB
/B
A
3
5
VB
VB
3B3/2
-A
x
VB
VB
B
20

---

where in the second-to to-last line we have used the fact that h +
1
is a convex in h, and in the
VB+R
last line we have used v B 2 2
Case 5: =A
and
= E [0, 1): In this case we need to show V++*²
=A
2 2
(A+=) 3
x²
/B
VB
2
B
vB
To see this, we first observe that since
-A-x VB+.² [0. 1), we have
A + 2Ar x² < B 2
A + 2Ar S.
Thus, by quadratic formula, A 2 -x V
1 + B, so that we have A E 1-0 -BVB
v2
Next, target identity can be rearranged into equivalent form as follows:
A 1
(A+x))
x²
VB
x2²
VB
2)+
A
x2
2(
VB
B
VB'
so that it suffices to show the second line above. Notice that the RHS of this expression is convex in
A and is maximized at the boundary of the range [-x Vx2 B, -VB. When A = -VB B have:
(A + x)² B ..2)
A VB
r²
(A x)+
A
1 x²
2
< 0.
2
B
VB
2B
VB
2
B
V
2B
Alternatively, when = -
Vx²
+
B, we have
(A + x)
A
1
x
V
B
x.2
+
+
=
2(B + x2)
VB
2
B
VB
B
0.
This establishes the claimed inequality (6) and completes the proof.
21


Reviews:
[{"review_id": "LZviJ6Wg8D", "reviewer": "Reviewer_2EmS", "summary": "This paper develops a method to automatically determine the learning rate of an optimization algorithm. Their approach, referred to as Mechanic and motivated by theoretical advances in online convex optimization, determines a new learning rate for iteration t using an update that resembles an adagrad update plus an additional decay factor. Their method is tested in deep learning settings ranging from language to large scale vision, where it approaches and sometimes outperforms a \"tuned baseline\". ", "questions": "- Different base algorithms and problem settings result in different performance for Mechanic vs. the baseline. Do the authors have any ideas why this may be?\n- How is performance affected by s_init and the betas.\n- I was slightly lost in the explanation for how multiple betas were used in the section where the adagrad like update transforms into more of an adam like update. Could the authors extend this trick so that multiple betas could be used simultaneously in other contexts, e.g., for the adam estimators for the params?\n- Can you explain the tuning that went into the baseline. Ideally a plot of LR vs. perf for the baseline could be contrasted with mechanic.\n- Why do the authors compare only to D-adapt and not, e.g., DoG https://arxiv.org/abs/2302.12022.", "limitations": "Yes, the limitations are discussed.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper has many strengths:\n- The problem that the authors explore is very important to the community. Even if their method is not a universal solution, any sound progress towards this target is potentially valuable. If the community succeeds in removing the need for tuning learning rates, significant resources use will be eliminated.\n- Mechanic can be applied to any base algorithm, not only in theory but also in practice: the authors show results for Adam, Lion, and SGD.\n- Mechanic is tested in various different domains from masked language modeling to large scale JFT pre-training.\n- Mechanic has only two tunable hyper-paramters, s_init and the vector of beta.", "weaknesses": "- The central weakness in this paper is the lack of clarity surrounding the \"tuned baseline\". How was that baseline tuned? What scheduler is used? Is it the best learning rate and if so out of how many searched? It would be great to see a line plot of LR vs. perf for the baseline and then a horizontal line for mechanic. This weakness is why I've listed the soundness as only fair.\n- There are no ablation studies for the relevant hyperparameters s_init and the betas.\n- Minor: There are some claims in the paper which I do not believe to be true. For instance, in the conclusion the authors claim that it is infeasible to manually tune a scale factor for each layer. However, there is work, e.g.,  mu-transfer which aims to specify a \"corrected\" learning rate for each layer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Main concern about baseline hyperparameter tuning**\n \nWe provide a lot more detail into the appendix section B. However, to specifically answer your questions:\n\n```How baseline was tuned and Is it the best learning rate and if so out of how many searched```: For all baselines we either grid sweeped over a reasonably large range learning rates (e.g. BERT) or (to limit costs) used a well tuned learning rate from a paper on the code open-sourced by the authors of the baseline (e.g. ViT pre-training) Exact values can be found in sections B.1 and B.2\n\n```What scheduler is used```: Assuming you mean LR scheduler, we used the schedules mentioned in the original baselines for both with and without Mechanic. Specifically, linear schedule for BERT and cosine schedule for ViT. Note that Mechanic does not eschew a need for a schedule (at least not yet), it simply learns the right scale factor to be used for a predefined schedule.\n\n```It would be great to see a line plot of LR vs. perf for the baseline and then a horizontal line for mechanic.```: This is a great suggestion! We will post data for this during the discussion period and even add plots in the final version of the paper.\n\n**Regarding betas and s_init**\n\nYou are absolutely right that ablating hyperparameters may result in useful insights, however in this case, both beta (with the addition scheme) and s_init are robust enough not to produce meaningful difference in performance.\n\nWe have found that using a single value for beta required tuning of the beta value for each model/dataset separately. However, the “addition scheme” we used does not. This was motivated by theory (via the “combining regret bounds via addition” technique introduced by [33]). We found that as long as a reasonable beta value for the problem is present in the betas sequence (default), performance doesn’t change.\n\nRegarding tuning of s_init, we intended the scheme to work with “obviously too small” values like 1e-8 (a property that is supported by the logarithmic dependence on 1/s_init in theory) but in practice changing s_init to even a few orders of magnitude does not affect performance much.\n\nLet us know if you still want us to add those results in the paper, we would be more than happy to do so!\n\n**Regarding the multiple beta trick**\nThe trick we used to combine multiple beta values in the tuner algorithm relies on a theorem relating to parameter-free online algorithms that states a “meta algorithm” created by adding the outputs of many sub-algorithms will have performance no worse than the best of the sub-algorithms (even if we do not know which one is best at first). Thus, since we did not know which beta value would be best at first, we simply added the outputs of many instances of Tuner with different beta values. In principle, one might be able to apply a similar trick with the beta values in a high dimensional algorithm like Adam, but this would require blowing up the memory and runtime of Adam by a factor of [number of beta values]. Since Tuner requires only O(1) memory and time, this blowup is irrelevant compared to the time needed to simply compute a gradient, but Adam requires O(d) time/memory where d=[number of parameters in the model], so this may incur more significant performance issues.\n"}, {"review_id": "WFmXccC1B5", "reviewer": "Reviewer_7tau", "summary": "The paper proposes a scheme to automatically tune the learning rate scale factor for any gradient-based optimization algorithm.  The method can be viewed as a practical realization of recent theorertical results in online convex optimization (OCO), which reduces the problem to minimizing the regret of a one-dimensional OCO algorithm. The authors test their proposal on a range of large-scale deep learning benchmarks, showing  competitive performance compared to strong manually tuned baselines. It is also shown that the method can outperform a recently proposed learning rate tuner, D-adaptation, without requiring the modifications accross base optimizers that D-adaptation does.", "questions": "I am confused by the notation (line 41 or line 95) suggesting that the MECHANIC iterates are mere interpolations of the initial point and the BASE iterates.  It makes it look like one needs to run the base algorithm  once completely to be able to define the MECHANIC iterates, which is clearly not the case from Algorithm 1. I see how  MECHANIC depends on the BASE *updates* -- but these are built from  gradients that depend on previous MECHANIC iterates, not on the BASE iterates.  (The authors seem to acknlowedge this abuse of notation in Footnote 1, but I cannot see the mathematical justification that the footnote is referring to). \n\n\nI am not sure about the editorial choice that  consists of motivating the algorithm with the OCO analysis. \nI feel a better choice could be to first introduce the wrapper as an additional  optimization step over the scaling factor $s$ with loss $\\ell_t(x_1 - s \\sum_t \\mbox{base updates}_t)$, which I find intuitive and elegant in and of itself  -- as it optimizes in the direction of what would have been a good scale in hindsight  ; then to introduce OCO subsequently for the sake of the analysis.  \n\nMiscalleneous: \n\n* l38 allowed make <-- allowed to make \n\n* Footnote 1: presently <-- below or shortly\n\n* Inconsistent index for s_t between l41 and l42. \n\n* From l45, I suggest to just create a new \"related work\" section. An explicit list of contributions in the introduction would also be helpful. \n\n* l93 let and <-- and let \n\n* l103 approximates of the gradient <-- approximates the gradient\n\n* l110: isn't an example of such an advanced algorithm SGD initialized a s=0? (from l83). \n\n* l110: A TUNER subscript is missing in the regret formula.  \n\n\n* l113 missing words: \"so by setting To show\" ...\n\n\n* On Algorithm 1 : l6 gk <-- gt. I suggest adding What is zt? x_ref not updated? \n\n* Table 1: it would be nice to see standard deviations reported as well \n\n* The last mentioned limitation in section A looks like an advantage to me (no validation set required).", "limitations": "Limitations adequately acknowledged in the appendix.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "* Strong empirical evaluation, which shows solid results against strong baselines in large-scale contexts where learning rate tuning is known to play a criticial role. \n\n* Great potential  for practicaly applicability, as it provides an off-the-shelf  wrapper that can be used on top of any gradient-based optimization algorithm.\n\n* (At least part of) the approach is theoretically motivated -- and subject to theoretical analysis. \n\nGiven the above, I believe the project can be turned into a very strong submission -- provided the weaknesses below are addressed.", "weaknesses": "Despite the paper's great potential, a major reservation I have, which justifies my rating, is about the clarity of the presentation -- at least for those without strong expertise of the relevant literature. \n\n* The background section, which motivates the approach, is based  on prior work -- specifically, recent progress in parameter-free online convex optimization (such as ref [28]). I think the authors can do a much better job at reproducing and explaining these known results (the fact that presentation is plagued with misprints does not help).  \n\nFor example, while Theorem 1, which bounds the regret of Mechanic in terms of the regrets of Base and Tuner, is relatively clear, the exposition of how it is exploited (end of Section 2.1 and Section 2.2 ) is very unclear to me. To be specific, the right-hand-side in the last equality on line 97, s dot shows  up in both regrets, which suggests some sort of tradeoff between both regrets --  I do not follow the reasoning  that the problem is completely relegated to Tuner (for example, the optimal s dot  on line 101 from the BASE regret term looks distinct from the optimal s dot on line 119 from the tuner regret).  Furthermore,  the paragraph between l112-l122 completely lost me.\n\n I think this would be highly beneficial to rewamp entirely this exposition  for the sake of readability,  especially for non OCO experts like myself.(I formulate more specific comments / questions in Questions section.  \n\n* In Section 3 the specific form of Tuner (even  in its simplified form after line 148) seems to come out of the blue. \nI am not sure whether or not it was supposed to follow from the background analysis; if it does, I think being  explicit  about  the transition would be helpful (of course the empiricial justifications of some specific ingredients, as in 3.2 for weight decay, is completely fine).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your detailed review and feedback on the presentation - making sure everyone can follow the paper is a priority for us. Unfortunately, we cannot provide an updated revision, so below we’ve copied in some changes that will ameliorate the issue. We would be happy to hear your feedback, and we intend to make a careful edit of the paper with an eye to accessibility.\n\n```For the paragraph starting at line 99, we propose to add detail as follows:```\n\n“\nWith this result, finding the optimal $s$ can usually be completely relegated to $\\texttt{tuner}$. Although the value $\\mathring{s}$ appears in both terms of the sum $\\text{Regret}\\_{\\text{linear}}^{\\texttt{tuner}}(\\mathring{s}) + \\mathring{s}\\text{Regret}\\_{\\text{linear}}^{\\texttt{base}}(x^{\\texttt{base}}\\_1+(\\mathring{x}-x^{\\texttt{base}}\\_1)/\\mathring{s})$, it turns out that for essentially all known base algorithms, there is a particular value $\\mathring{s}$ that causes $\\mathring{s}\\text{Regret}\\_{\\text{linear}}^{\\texttt{base}}(x^{\\texttt{base}}\\_1+(\\mathring{x}-x^{\\texttt{base}}\\_1)/\\mathring{s})$ to obtain the optimal regret bound $\\|\\mathring{x}\\|\\sqrt{\\sum_{t=1}^T \\|g_t\\|^2}$. This value for $\\mathring{s}$ is unknown a priori, and depends on the data and the base algorithm. However, if $\\text{Regret}\\_{\\text{linear}}^{\\texttt{tuner}}(\\mathring{s})$ is sufficiently small for this unknown value $\\mathring{s}$, then overall we achieve the optimal regret bound without having to know $\\mathring{s}$ ahead of time. Note that setting $\\mathring{s}$ in this way can be done entirely in the analysis without modifying the algorithms, as justified by the infimum in the Theorem.\n“\n\n```For the paragraph at line 112:```\n\n“\nIn the a theoretical development of this technique, it is necessary to prevent the terms $\\langle g_t, x_t^{\\texttt{base}}  - x_t^{\\texttt{base}}\\rangle^2$ from becoming too large (as otherwise $\\text{Regret}^{\\texttt{tuner}}$ is too large). Typically, this is accomplished by constraining the base algorithm to satisfy $\\|x_t^{\\texttt{base}}  - x_t^{\\texttt{base}}\\|\\le \\rho$ for some user-specified arbitrary $\\rho$. Enforcing such a constraint means that the regret bound (2) would only apply to $\\|\\mathring{x}\\|\\le \\rho$, but ensures that $\\langle g_t, x_t^{\\texttt{base}}  - x_t^{\\texttt{base}}\\rangle^2\\le \\rho^2 \\|g_t\\|^2$. Thus, by setting $\\mathring{s} = \\|\\mathring{x}−x_1^{\\texttt{base}}\\|/\\rho$, the combined algorithm obtains the optimal regret bound of $O(\\|\\mathring{x}−x_1^{\\texttt{base}}\\|\\sqrt{\\sum_{t=1}^T \\|g_t\\|^2})$ (amazingly, the value of $\\rho$ is irrelevant!). In practice however, we do not attempt to explicitly enforce any such constraints and simply rely on the intuition that any non-diverging algorithm is unlikely to produce excessively large iterates.\n“\n\n```Regarding motivating the Tuner algorithm: We will first motivate a further simplified update with the following text:```\n\n\n“\nWhile the specific form of our tuner update is based upon more involved analysis, we can capture some intuition by appealing to the familiar SGD algorithm. First, notice that the “gradient” sent to Tuner is $h_t$. Thus, the SGD update would be $s_{t+1} = s_t - \\eta h_t$ for some learning rate $\\eta$. It turns out that the analytically optimal value for $\\eta$ is $\\frac{\\mathring{s}}{\\sqrt{\\sum_{i=1}^T h_i^2}}$. Unfortunately, we do not know this value at first. Instead, at time $t$ we estimate the denominator with the running sum $\\sqrt{\\sum_{i=1}^t h_i^2}$ and the numerator with the “optimistic” approximation $\\mathring{s}\\approx s_t$, so that the update becomes $s_{t+1} = s_t - \\frac{s_t h_t}{\\sqrt{\\sum_{i=1}^t h_i^2}}$. Unfortunately, this update is unstable and can result in exponential blowup in the $s_t$ values as bigger $s_t$ results in bigger learning rates. Much of the technical detail in our update is designed to deal with this instability, essentially by introducing a carefully designed decay into the $s_t$ update.\n“\n\n\n```Regarding the intuition of taking the “gradient with respect to s” of $\\ell(x^{\\texttt{base}}_1 + s\\cdot(x^{\\texttt{base}}_T -x^{\\texttt{base}}_1)$```: We agree this makes sense a high level, but in fact the analysis is totally different and we could not see any way to formally justify the algorithm with this intuition. We were a bit wary of emphasizing it too much since we cannot be confident that variations based solely on this intuition will behave well. Nevertheless, we will flesh out the idea a bit more in the discussion after Theorem 1. This is actually related to your question about footnote 1 - our analysis is essentially a mathematical “trick” that enables us to sidestep issues that arise with more intuitive arguments.\n\n```Regarding footnote 1, as well as the concern about needing to first do a run of the base algorithm```: The justification is Theorem 1, and you are correct that we do NOT need to run the base algorithm first.\nOur analysis is based on regret and actually does not stipulate any particular meaning for the vectors $g_t$. The base algorithm is viewed as a black box taking as input any sequence of vectors $g_1,\\dots,g_t$ and yielding some $x_{t+1}^{\\texttt{base}}$. Although it is intuitive to set $g_t=\\nabla f(x_t^{\\texttt{base}},z_t)$, this is not assumed in our analysis. Nevertheless, all standard algorithms like SGD, AdaGrad etc ensure bounded regret for arbitrary sequences $g_t$.\n\n\n```Other questions:```\nLine 110: The “advanced” part of these algorithms is that they obtain the bound $\\mathring{s}$ automatically, while SGD would require tuning the learning rate depending on $\\mathring{s}$.\n\nLine 113: The partial phrase “so by setting” should be deleted: the sentence ends after the parentheses (the value for $\\mathring{s}$ is provided later in the paragraph).\n\nAlgorithm 1: $z_t$ represents the $t^{th}$ minibatch (see line 11). $x_{\\text{ref}}$ should be $x_1^{\\texttt{base}}$ (and so does not need updating).\n"}, {"review_id": "JI9BNgjAAr", "reviewer": "Reviewer_mCwi", "summary": "This paper proposes a parameter-free technique to tune the learning-rate scale factor automatically, which can be applied to any given base optimization algorithm to match its performance given carefully tuned hyper parameters. This approach is mainly empirical in nature, though grounded in reduction from recent advancements in theoretical understanding of online convex optimization. The implementation is also \"scale-free\", i.e. invariant to scaling the stochastic gradients $g_t$ by a constant. The authors provide experimental evidence to support their claims, including both training from scratch as well as transfer learning, and across domains and model architectures.", "questions": "1. How were the hyper-parameters of the base algorithms set? How are the results change if the hyper-parameter of the base algorithm are under-optimal? Was there a thorough tuning phase to verify the chosen hyper-parameters (including the total number of update steps) of the baseline algorithm were indeed correctly tuned?\n2. What is the standard deviation in the given results?\n3. What is the effect of $\\lambda$ and the effect of $\\beta$ ? Also, what is the effect of learning rate schedulers on the performance of MECHANIC?", "limitations": "The authors have addressed the limitation of their work adequately. Namely, the authors mention the lack of theoretical guarantees or intuition into some of the results, as well as potential future work. There is no ethical considerations relevant in this case.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "With the rapid rise in both demand and costs to train large models, the compounding effects of hyper-parameter tuning transitioned from being a technical inconvenience to a true bottleneck. While there have been some advancements in parameter-free optimization, any practical contribution to this field is highly valuable. A general-use, easy to implement extension to existing optimizers that act as a force multiplier and improves upon their results falls comfortably into this category.\nIn addition to providing some theoretical justification to their method, the authors also provide a detailed, easy-to-follow background to the field and its main results thus far. The paper also include some interesting intuitions by the authors, instead of post-hoc explanations of empirical findings. \nThe experiments performed by the authors include various domains and model architecture, and notably include both pre-training from scratch as well as fine-tuning which are known to behave differently.", "weaknesses": "As stated by the authors themselves: their \"primary contribution is not new theoretical development, but instead the translation between theory and practice\". Since this paper is focused mainly on empirical evidence rather than new theoretical results, the burden of proof grows larger. While the authors do perform various experiments, there is key information that is missing to fully convince in the efficacy of the approach.\n1. The experimental setting is lacking some details. Namely, how were the hyper-parameters for the base algorithm chosen? Following existing procedures while altering some hyper-parameters (e.g. dropping the NSP loss) may affect the results. Additionally, the given hyper-parameters are not guaranteed to be optimal in the first place. To make the claim that MECHANIC helps in achieving competitive results to carefully tuned optimizers, the base optimizers should indeed be carefully tuned.\n2. Moreover, statistical significance of the results is not assured, as no measure for variance in the results is given. Very often, the advantage of the MECHANIC based training is small enough to potentially be attributed to the inherent noise in the evaluations.\n3. It is not clear that all models converged in the presented results as there are missing details. For example, Table 1 provides fine-tuning results of BERT like models on GLUE, which underperform the results reported by Devlin et al. 2018, and Liu et al. 2019. This may be due to the difference in pre-training corpus, or due to undercutting of the models. In the latter case, additional training may have changed the results.\n4. There are missing experiments to show how well does MECHANIC operate when the hyper-parameters of the base algorithm are not well tuned. If it fails in such cases, then one still has to tune the parameters of the base algorithm, and gain nothing by using this approach. \n5. there are missing ablation tests - what is the effect of $\\lambda$ and the effect of $\\beta$? Also, what is the effect of learning rate schedulers on the performance of MECHANIC?\n6. While the paper focuses on empirical findings, the authors suggest the method should be robust, but with no guarantees. For example, line 194-196 the authors claim that weight decay should not affect the operation of MECHANIC, but provide no proof (lie 195-196) and no empirical evidence. \n7. While the method is presented as parameter-free, there is evidence that tuning its hyper-parameters may indeed be required. For example, lines 175-176 discuss the importance of setting $\\beta$. While the authors try to obviate the need to tune it, the choice of defaults may not generalize well to other settings. Also, lines 239-240 mention that tuning $\\lambda$ may be beneficial. \n\n\nSome additional comments regarding the presentation of the paper:\n* Algorithm 2 is referred to quite a lot and is being analyzed in the paper. As such, I think it will be beneficial for the reader if it is included in the body of the paper.\n* In line 49, you state the \"Empirical studies often take the route of \"hyper-gradient descent\". However, this approach is rarely used in practice, and even in the work you cite, most empirical approaches do not follow it, nor compare to it.\n* The \"scale\" buy which the paper measure gains is not consistent. When MECHANIC is outperformed by base algorithms it is said to be \"quite competitive\", while when it has the advantage by smaller absolute gains, it is said to outperform. For example, see lines 247-248 which discuss the results of Figure 2. \n\n\nThere are a few typos and styling issues that should be fixed prior to final submission: \n1. line 38, there is a missing \"to\" between \"allowed\" and \"make\"\n2. line 93, the words \"let and\" were swapped\n3. line 113, **missing key information** - the sentence of how you set the scaling factor is missing \"and so by setting <MISSING> To show...\" \n4. In Table 2, there are at least 5 cases where the base algorithm achieved **identical** results to those of the MECHANIC tuning, while the table gives only the results of the MECHANIC tuning in boldface which is confusing and misleading.\n5. line 218, \"works\" $\\rightarrow$ \"work\"\n6. line 219, \"not that\" is swapped\n7. The bibliography style is inconsistent in its presentation. For example, [7,11,14,33] are all cited from CoLT, each with different styling. [20,21,36] are both from NeurIPS but with very different styles as well. Also 35 cites from arXiv differently from e.g. 38.\n8. All references in the paper are not \"clickable\". Namely, figures, table and citation references are not clickable in the PDF", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed comments! Your feedback will be very helpful to us in revising the paper. In the below we provide some more detail that we hope will address your main concerns.\n\n**Main concern about missing empirical information**\n \nWe provide a lot more detail in the appendix section B. However, to specifically answer your questions:\n```Namely, how were the hyper-parameters for the base algorithm chosen?``. We have actually tried to be faithful to the original baseline whenever possible. For instance, for our image classification experiments, we even use the exact code open-sourced by the original authors for both pre-training and fine tuning, with original hyperparameters (including the tuned learning rate) to limit any confounding factors. There is exactly one place where we deviate from the baseline, which is the removal of NSP loss. We did that only to simplify our experiments since it did not affect the performance of the baseline at all.\n\n```To make the claim that MECHANIC .. the base optimizers should indeed be carefully tuned.```: You are absolutely right. Since learning rate is the most significant hyperparameter for this study, for all baselines we either grid sweeped over a reasonably large range learning rates (e.g. BERT) or (to limit costs) used a well tuned learning rate from a paper on the code open-sourced by the authors of the baseline (e.g. ViT pre-training) Exact values can be found in sections B.1 and B.2. We also note that as a sanity check, we report competitive results on the *baselines* when compared with what was reported by the original authors.\n\n```Moreover, statistical significance of the results is not assured```: For results on small dataset like GLUE, you are right, it is hard to attribute the gains directly to Mechanic since there can be a lot of variance. But this is true even for the baselines. For that reason, similar to what was done in the original baseline papers, for all finetune runs, we report an average of 3 runs to counteract the variance. Finally, our aim is not to claim that with Mechanic one can get better performance than the baseline with well tuned learning rates, we merely hope to illustrate that it can help eschew the need for learning rate tuning for similar performance.\n\n```It is not clear that all models converged```: We are a little confused by this concern. We did look again at the original BERT results and compared our ```baseline``` results with what they report. We would like to note that contrary to the concern, for some GLUE datasets such as QNLI, SST-2 ad QQP, with BERT-L, we in fact report better or almost the same results than what was reported with BERT on dev set (from Table 5 in Liu et al). Let us know if we misunderstood your concern.\n\n``` There are missing experiments ..``` This is an interesting question and your point is well taken! We presented the case in which the other hyperparameters of the base algorithm (such as the schedule) are well-tuned. That said, we have observed that Mechanic continues to improve upon even poorly tuned baselines although we did not perform enough experiments on this case for the original submission as we felt that the well-tuned case was the one of most practical significance. Our hope is that Mechanic is indeed robust against other changes in hyperparameters, but there are still cases where Mechanic is currently less effective, such as when using dropout or normalized gradient updates like LARS and LAMB. These are certainly limitations of Mechanic and we will make sure to document them as such in our limitations section.\n\n```\\lambda, \\beta and lr schedules```:  [Also elaborated in response to reviewer 2EmS] you are absolutely right that ablating hyperparameters may result in useful insights, however in this case, beta (with the addition scheme), s_init and \\lambda (if not too big) are robust enough not to produce meaningful difference in performance. Regardless we are happy to add the plots if you think they help!\n\nInspired by your suggestion, one interesting ablation study might be to change num_betas (*n* in Alg 1), following table shows  *n* vs Acc of ViT-B/16 on JFT-300M:\n\n```\n| n   | 2    | 4    | 6    | 8    |\n| Acc | 48.9 | 49.5 | 49.9 | 49.6 |\n```\nInterestingly,  training runs with *n* < 6 perform worse and also shows instabilities, however, increasing *n* beyond 6 leads to slightly poor performance.\n\n**Tuning other hparams**\n\n```If it fails in such cases, then one still has to tune the parameters of the base algorithm…```: We focused here on tuning only the scale factor for the updates, NOT in particular regularization constants or the schedule or any other aspect of optimization. Tuning this scale is typically one of the most important hparams, so removing the need to tune it is already a significant improvement that will certainly save computational resources. Note that without mechanic you still need to tune those parameters anyway. That said, we certainly acknowledge that our method does not completely obviate the need for ALL tuning.\n\n```While the method is presented as parameter-free``` Please note that for our experiments we used the SAME values of beta/lambda across various models and datasets, providing evidence that in future tasks no alteration/tuning of mechanic is necessary. In the case of beta, the use of multiple beta values at once does actually come from some theoretical motivation for why this technique obviates the need to tune beta. For lambda we have less understanding and simply propose it as an empirical improvement. In practice it seems the default value is good, but certainly you could choose to tune it if you desire.\n\nThe sentence on line 113 should have ended after the parentheses, so the words “and so by setting” should have been deleted. The setting for $\\mathring{s}$ in this particular example is provided later in the paragraph. See also our response to reviewer 7tau for a proposed alternative phrasing of this paragraph.\n"}, {"review_id": "uqebZc9Nzt", "reviewer": "Reviewer_DR7W", "summary": "This paper focuses on a method (MECHANIC) for tuning the learning rate of any given base optimizer. This is compatible with any given base optimizer along with a learning rate schedule*. Let u_1, u_2,..u_t be the steps of the base optimizer up until now, then MECHANIC chooses a s_t such that the neural network weights are set to w_{init} + s_t (\\sum_i u_i). They do this by leveraging a similar scheme developed for online convex optimization. They implement this method with some minor changes to simplify the implementations and improve the convergence speed (by using momentum and a variant of weight decay).\n\nThe authors show that in experiments on masked language modeling and image classification, using MECHANIC leads to faster optimization (although it does sometimes lead to worse generalization).\n\n*One thing to note is that this is not a replacement for learning rate schedulers. In the CIFAR10 plots (Fig 2), there is still a need for learning rate decay. Rather, it seems to help over the tuned baselines for any given learning rate schedule.\n\nTypos:\nLine 32: The end quote is flipped.\nLine 17 in algorithm: s_{t+1,n} should be s_{t+1,i}.\nLine 113: Text is missing.\nTable 3, last line: MAdamW should be M-LION.", "questions": "1. Could the authors provide some intuition about the fact that s_t is multiplied to the sum of the steps taken by the network till now rather than the next step (as is done in learning rate schedulers). \n2. It is surprising that the learned value of s (Figure 1 and 3) is usually  << .1? For comparison against tuned learning rates I would have expected s to be not significantly smaller/larger than 1. Does this suggest that the learning rates being compared to could have been reduced by a factor of 10 without significant effects? Could the authors provide some intuition about the learnt values of s? \n3. The main body says that lamba is always set to .01 while Table 2 says that lambda=.1 in one of the cases. Was lambda tuned for MECHANIC? If so, was weight decay tuned for the base optimizers? \n4. I may have missed the justification referred to in “This seems like a significant issue to disregard, but we will provide mathematical justification presently.”. Could the authors point where this is? Also, I think the first line of the proof of 3.1 is assuming this i.e. that g_t is independent of s_t.\n5. Line 100: What is “s”? The previous lines only had s^{o}.\n", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Improving over tuned baselines is an important contribution. The authors do so for large scale deep learning datasets such as BERT and JFT-300m. It is a bonus that the authors are able to do so by using a theoretically motivated algorithm.\n", "weaknesses": "The results would have been more impressive if the authors had used more recent baselines such as Mosaic ML’s BERT codebase. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments and work reviewing our paper! We have included answers to your questions below, and we’d be happy to elaborate further.\n\nIntuition for scaling by the sum of the steps: At a high level, the sum of the steps is a more “stable” value because it changes slowly. Individual steps, in contrast, change direction very quickly and so make it difficult to stabilize on the correct learning rate. In a technical sense, this manifests in analyses of algorithms that attempt to learn the scale factor applied to each step often needing to solve optimization problems with high variance or Lipschitz constants and so are unable to ensure quick convergence.\n\nThe scale factor is applied to the base learning updates with no learning rate (or, if you prefer, a learning rate of 1.0). This is why s is smaller than 1.\n\nWe did tune lambda for mechanic, as well as weight decay for the base optimizers. We found that without lambda, mechanic still performed well, but not quite as well (especially on smaller datasets). Please see the response to reviewer mCwi and the ablation plots included in the general response for more detail.\n\nThe justification is provided in Theorem 1, for which the regret of the base algorithm is measured with gradients evaluated at rescaled iterates rather than the original base iterates. We are not sure what you mean by the first line of the proof of 3.1: what is 3.1? We don’t think we ever assumed any kind of independence: in fact, our proofs do not assume any kind of stochastic structure at all and hold even for completely adversarial gradient or loss sequences, which is typical in online convex optimization. Specifically, our analysis has the following overall structure:\n\nFirst, by convexity one has $\\mathbb{E}\\left[\\sum_{t=1}^T F(x_t) -F(\\mathring{x}) \\right]\\le \\mathbb{E}\\left[\\sum_{t=1}^T  \\langle g_t, x_t - \\mathring{x}\\rangle\\right]$.\n\nSecond, we prove that for *any* sequence of vectors $g_1,\\dots,g_t$, the quantity $\\sum_{t=1}^T  \\langle g_t, x_t - \\mathring{x}\\rangle$ is small. In particular, this part of the analysis actually does not need the $g_t$ to be gradients of anything - they can be arbitrarily and even adversarially generated. Please check out the response for reviewer 7tau for more intuition behind the analysis.\n\nLine 100:  $s$ is the scale value used in the base implementation of SGD, as described in equations (1) and (2). $\\mathring{s}$ is the “correct” scale value that we should have used.\n\n\n"}]

Author rebuttal:

Meta-review: The reviewers have reached a consensus in favor of accepting this paper, appreciating the way it bridges theory and practice and provides promising empirical results. However, the reviewers have expressed important concerns about the clarity of the experiments and missing ablations. I fully agree with the reviewers on both counts, recommending acceptance while **requiring** the authors to revise the paper by adding all the explanations and additional experiments discussed with the reviewers. Crucial details such as the methodology for hyperparameter selection must appear in the main part of the paper rather than the appendix.

In addition to all the important points raised by the reviews (which the authors should carefully peruse when making the revision, as some comments remained unaddressed), I have a few comments of my own:

1) The submitted paper and supplement appear to be missing the following crucial detail: **what LR is used in the BASE optimizers**? This matters, since TUNER is not invariant to the BASE LR (as evidenced by the fact that LR schedules matter). The authors’ reply to reviewer DR7W suggests that the LR for all BASE algorithms is 1.0. While this seems like a fair setting, if taking BASE’s LR to be 1.0 is essential it would contradict the paper's claim that BASE could be any algorithm. The authors must discuss the choice of BASE’s LR in the main part of the paper. In addition, they should add an experiment testing whether the LR parameter in the BASE algorithm truly does not matter as claimed. 

2) As reviewer 7tau briefly notes, deviation metrics are missing throughout the paper. At least for the fine-tuning experiments, the authors must repeat them with multiple seeds and report, e.g., standard deviation along with the accuracy. 

3) The authors call a JFT-300M a “popular” dataset, which I find highly objectionable considering it is available only to Google employees, while the rest of the community does not even have a proper description of the content of the dataset. Remove this misplaced adjective.
Decision: Accept (poster)