Adaptive Gradient Methods with Local Guarantees
Authors: Zhou Lu
Wenhan Xia
Sanjeev Arora
Elad Hazan
Venue: Submitted to ICLR 2023 (2023)

Abstract: Adaptive gradient methods are the method of choice for optimization in machine learning and used to train the largest deep models. In this paper we study the problem of learning a local preconditioner, that can change as the data is changing along the optimization trajectory. We propose an adaptive gradient method that has provable adaptive regret guarantees vs. the best local preconditioner. To derive this guarantee, we prove a new adaptive regret bound in online learning that improves upon previous adaptive online learning methods. 
We demonstrate the robustness of our method in automatically choosing the optimal learning rate schedule for popular benchmarking tasks in vision and language domains. Without the need to manually tune a learning rate schedule, our method can, in a single run, achieve comparable and stable task accuracy as a fine-tuned optimizer.

Under review as a conference paper at ICLR 2023
ADAPTIVE GRADIENT METHODS WITH LOCAL GUAR- ANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Adaptive gradient methods are the method of choice for optimization in machine learning and used to train the largest deep models. In this paper we study the problem of learning local preconditioner, that can change the data is changing along the optimization trajectory. We propose an adaptive gradient method that has provable adaptive regret guarantees vs. the best local preconditioner. To derive this guarantee, we prove new adaptive regret bound in online learning that improves upon previous adaptive online learning methods.
We demonstrate the practical value of algorithm for learning rate adaptation in both online and offline settings. For the online experiments, we show that method is robust to unforeseen distribution shifts during training and consis- tently outperforms popular off-the-shelf learning rate schedulers. For the offline experiments in both vision and language domains, we demonstrate our method's robustness and its ability to select the optimal learning rate on- an-the-fly fly and achieve comparable task performance as well-tuned learning rate schedulers, albeit with less total computation resources.
INTRODUCTION
Adaptive gradient methods have revolutionized optimization for machine learning and are routinely used for training deep neural networks. These algorithms are stochastic gradient based methods, that also incorporate a changing data-dependent preconditioner (multi-dimension)) generalization of learning rate). Their empirical success is accompanied with provable guarantees: in any optimization trajectory with given gradients, the adapting preconditioner is comparable to the best hindsight, in terms of rate of convergence to local optimality.
Their success has been source of intense investigations over the past decade, since their introduction, with literature spanning thousands of publications, some highlights intuitive understanding of their success is their ability to change the preconditioner, or learning rate matrix, per coordinate and on the fly. methodological way of changing the learning rate allows treating important coordinates differently as opposed to commonly appearing features of the data, and thus achieve faster convergence.
surveyed below. The common
In this paper we investigate whether more refined goal can be obtained: namely, can we adapt the learning rate per coordinate, and also in short time intervals? The intuition guiding this question the rising popularity in "exotic learning rate schedules" for training deep neural networks. The hope is that an adaptive learning rate algorithm can automatically tune its preconditioner, on per-coordinate and per-time basis, such guarantee optimal behavior even locally.
To pursue this goal, we use and improve upon techniques from the literature on adaptive regret in online learning to create provable method that is capable of attaining optimal regret in any sub-interval of the optimization trajectory. We then test the resulting method and compare it to learning learning rate schedule from scratch. Experiments conducted validate that algorithm can improve accuracy and robustness upon existing algorithms for online tasks, and for offline tasks it saves overall computational resources for hyperparameter optimization.

---

Under review as a conference paper at ICLR 2023
1.1 STATEMENT OUR RESULTS
The btochastic/subb-grddieee descent algorithm is given by the following iterative update rule:
Ir+1 I, 7/ Vr-
If 77r is matrix, it is usually called a preconditioner. A notable example for a preconditioner is when 7/, is equal the inverse Hessian (or second differential), which gives Newton's method. Let .... Vr be the gradients observed in an optimization trajectory. the Adagrad algorithm (and subsequent adaptive gradient methods, notably Adam) achieves the following regret guarantee for online convex optimization (OCO);
T
0 min
V. I1p).
MEH
where H is family of matrix norms, commonly those with bounded trace. In this paper we propose a new algorithm SAMUEL, which improves upon this guarantee in terms of the local performance over any sub-interval of the optimization trajectory. For any sub-interval / [s, t]. the regret over I can be bounded by
Ö
min HEH
V- 11
which also implies a new regret bound over [1, T):
Ô
min H HREH
min
|-+1l
rEL,
This regret can be significantly lower than the regret of Adagrad, Adam and other global adaptive gradient methods that do not perform local optimization the preconditioner. We spell out such scenario in the next subsection.
Our main technical contribution is variant of the multiplicative weight algorithm, that achieves full-matrix regret bound over any interval by automatically selecting the optimal local preconditioner. The difficulty in this new update method stems from the fact that the optimal multiplicative update parameter, to choose the best preconditioner, depends future gradients and cannot be determined in advance. To overcome this difficulty, we run in parallel many instantiations of the update rule, and show that this can be done albeit increasing the number of base adaptive gradient methods by only logarithmic factor. A comparison our results in terms of adaptive regret is given Table []]
We conduct experiments in optimal learning rate scheduling to support theoretical findings. We show that for an online vision classification task with distribution shifts unknown to the learning algorithm, method achieves better accuracy than previous algorithms. For offline tasks, method is able to achieve near-optimal performance robustly. with fewer overall computational resources hyperparameter optimization.
1.2 WHEN DO LOCAL GUARANTEES HAVE AN ADVANTAGE?
Our algorithm provides near optimal adaptive regret bounds for any sub-interval [s, C [1.7]
simultaneously, giving more stable regret guarantee for changing environment. In terms classical regret bound over the whole interval [1, T'. our algorithm obtains the optimal bound of Adagrad up to (Vlog I') factor.
Moreover, adaptive regret guarantees drastically improve the loss over the entire interval. Consider the following example in one dimension. For E [1, T the loss function is f((x) = (2 + 1)2 and for the rest of time it is fe(x) = (a - 1) Running a standard online gradient descent method that is known to be optimal for strongly convex losses, f.e. with 7, 2. gives Ollog T') regret. However, the overall loss is 32(T') because the best comparator in hindsight is x = 0 which has overall loss T. However, if we have adaptive regret guarantees, the overall loss on both [1, F and 1 + 1, T] are both Ollog T). which is a dramatic O(T) improvement in regret.
2

---

Under review as a conference paper at ICLR 2023
Algorithm
Regret over -
Hazan & Seshadhri (2007)
Õ(VT)
Danicly et al. (015)) Jun et al. (2017)
0 O(VID)
Cutkosky (2020)
Öly M' |V+1
SAMUEL (ours)
DivE V
Table 1: Comparison of results. We evaluate the regret performance of the algorithms on any interval I [s. tl. For the ease of presentation we hide secondary parameters. Our algorithm achieves the regret bound of Adagrad, which is known to be tight in general, but on any interval.
1.3 RELATED WORK
Our work lies in the intersection of two related areas: adaptive gradient methods for continuous optimization, and adaptive regret algorithms for regret minimization, surveyed below.
Adaptive Gradient Methods. Adaptive gradient methods and the Adagrad algorithm pro- posed in (Duchi et al. 201T). Soon afterwards followed other popular algorithms, most notable amongst them Adam (Kingma & Ba 2014) and RMSprop (Tieleman & Hinton| 2012). Despite significant practical impact, their properties are still debated Wilson et al. (2017).
Numerous efforts were made to improve upon these adaptive gradient methods terms of paralleliza- tion, memory consumption and computational efficiency of batch sizes, e.g. (Shazeer & Stern 2018
Agarwal al., 2019 Gupta et 2018 Chen et 2019). survey of adaptive gradient methods
appears in Goodfellow et al. (2016): Hazan (2019).
Adaptive Regret Minimization in Online Convex Optimization. The concept of competing
with a changing comparator was pioneered in the work of (Herbster & Warmuth 1998 Bousquet & Warmuth] 2003) on tracking the best expert. Motivated by computational considerations for convex optimization, the notion of adaptive regret was first introduced by Hazan & Seshadhri (2007). which generalizes regret by considering the regret of every interval. They also provided an algorithm Follow-The-LLaddng-HHiin
which attains Ö(VT) adaptive regret. Daniely al. (2015) considered
the worst regret performance among all intervals with the same length and obtain O log" T)
interval-length dependent bounds, improved later by Jun et al. (2017) and Cutkosky (020))
For other related work, some considered the dynamic regret of strongly adaptive methods Zhang et al. (2018 2020). IZhang et al. (2019) considered smooth losses and proposes SACS which achieves an e (xx,) log" 7) regret bound.
O
Learning Rate Schedules and Hyperparameter Optimization. On top of adaptive gradient meth- ods, plethora of nonstandard learning rate schedules have been proposed. A commonly used one the step learning rate schedule, which changes the learning rate at fixed time-points. A cosine annealing rate schedule was introduced by Loshchilov & Hutter (016)). Alternative learning rates were studied Agarwal al. (202T). Learning rate schedules which increase the learning rate over time were proposed in Li & Arora (2019). Learning the learning rate schedule itself was studied in Wu al. (2018). Large-scale experimental evaluations (Choi et al. 2019, |Schmidt et al. 22000] Nado al., 202 conclude that hyperparameter optimization over the learning rate schedules are essential to state-of-the-an performance.
SETTING AND PRELIMINARIES
Online convex optimization. Consider the problem of online convex optimization (see Hazan (2016) for comprchensive treatment). At each round т. the leamner outputs point 2, I. for some convex domain IC Rd, then suffers a convex loss e, (x+) which is chosen by the adversary. The learner also receives the sub-gradients V, of (+() at TT., The goal of the learner in OCO is to
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Strongly Adaptive regularization via MUltiplicative (SAMUEL)
Input: OCO algorithm A, geometric interval set S, constant Q = 4 Gog Initialize: for each / E S, Q copies of OCO algorithm Ar.a.
Set 1/5, 22 for q Q]. Initialize u01 (7, = (1/, m1. if = [1, and wy (7.g) = 0 otherwise for each / E S.
for ..... T' do
Let -, (1, 9)= Ar(T)
Let W E LiES(r) w+ (I,))
Let I, EiEs(T) W/ (1, 1.9)z, (1,g)/W))
Predict 27,
Receive loss (- define r e, (x+) L, (x,(((1))))
For each / = [s,1] E S, update Wr+ 1 (I, q) as follows,
1 {
0
T+1
(1.z) w++1
m mp.) (T, q) + (l
7+
else
end for
minimize regret, defined as
Regret Σ
(x+)
min
(x).
zER
Henceforth we make the following basic assumptions for simplicity (these assumptions are known in the literature to be removable):
Assumption 1. There exists D. Doo > 1 such that ||0||| S D and || S Doo for any K.
Assumption 2. There exists G such that V 2 S G, VT [I,
We make the notation of the norm || for any PSD matrix H to be:
|| V
And we define its dual norm to be M 0, (H)) I d}. We consider Adagrad from Duchi al. (0111). which achieves the following regret run on I = [s,
V H V In particular, we denote {H) >
Regret(I)= =
Ddt min HER
Σ V.
The multiplicative weight method. The multiplicative weight algorithm is generic algorithmic methodology first used to achieve vanishing regret for the problem of prediction from expert advice Littlestone Warmuth ( (1994). Various variants of this method are surveyed in Arora al. (2012). that attain expert regret O(VT No)) for binary prediction with N experts.
AN IMPROVED ADAPTIVE REGRET ALGORITHM
In this section, we describe the SAMUEL algorithm [ which combines novel variant of multiplica- tive weight as well as adaptive gradient methods to obtain stronger regret bounds in online learning and optimization.
The SAMUEL algorithm guarantees that given any black-box OCO algorithm A as experts, achieves an
(1
min MEHH
V.
7=8
4

---

Under review as a conference paper at ICLR 2023
regret bound (w.r.t the experts) over any interval J [s.t] simultaneously. Next, by setting Adagrad as the black-box OCO algorithm A, the above bound matches the regret of the best expert and holds w.r.t. any fixed comparator as result, implying an optimal full-matris adaptive regret bound.
Roughly speaking, Algorithm| T first picks a subset of all sub-intervals and initiates an instance expert. The expert for interval I
of the black-box OCO algorithm A on any interval I E S is especially designed to achieve optimal regret over / instead of [1, T To improve upon previous works and achieve the full-matrix regret bound, we make Ollog I*) duplicates of each expert with different decaying factors which is the main novel mechanism of our algorithm (notice that these duplicates share the same model therefore won't bump up computational cost). Then Algorithm| [] runs multiplicative weight update on all active experts A1.q denoting the expert over I with the g-th decaying factor y (if E according to the loss of their own predictions, normalized by the loss of the true output of the algorithm.
We follow Daniely al.] (2015) on the construction of S: without loss of generality, we assume T = 2 and define the geometric covering intervals following Daniely et al. 2015)): ",
Definition Define S. {[1 2 [2 + 1,2 ..... [2 2 + 1, 2 for S S k. Define
S = U;S; and S(T)= = (T S CT.
For 2h < < 2 one can similarly define S: = 21..2']. + 1,,
2 + 1,7]},
see Daniely et al. (0155). The intuition behind using S is reduce the (T) computational cost of the naive method which constructs an expert for every subinterval of [1, T. Henceforth at any time the number of 'active' intervals is only (log(()) this guarantees that the running time and memory cost per round of SAMUEL is as fast as (T)g) Decompose the total regret over an interval J RJ) R2 (J), where Rg (J) is the regret of expert A, and R₁ (J) is the regret of the multiplicative weight algorithm Our main theoretical result is the following:
Theorem 2. Under assumptions 7 and 2 the regret (J) of the multiplicative weight part in Algorithm 7 satisfies that for any interval 1
R1(J) 0 D Dlog(T)) max GV GVVoog(T)dl df
min MEH
V.
Remark 3. We note that q that r- (I, g) and x. xI, .q) doesn't depend for the same I, so we may write r (T) and xr (I) instead for simplicity. We use convex combination in line 8 Algorithm because the loss is convex, otherwise we can still sample according to the weights.
In contrast, vanilla weighted majority algorithm achieves Ô(vT) regret only over the whole interval [1, 2", and we improve upon the previous best result Ö(V?- -V/--3) Daniely et al. (2015) Jun et al. (2017). The proof of Theorem can be found in the appendix.
3.1 OPTIMAL ADAPTIVE REGRET WITH ADAPTIVE GRADIENT METHODS
In this subsection, we show how to achieve full-matrix adaptive regret bounds by using Adagrad as experts as an application of Theorem 2 together with other extensions. We note that this reduction general, and can be applied with any adaptive gradient method that has regret guarantee, such as Adam or Adadelta.
Theorem bounds the regret R1 of the multiplicative weight part, while the total regret is Ro + Ri- To get the optimal total regret bound, we only need to find an expert algorithm that also haves the optimal full-matrix regret bound matching that of Rj. As result, choose Adagrad as expert algorithm A, and prove regret bounds for both full-matrix and diagonal diagonal-matrix matrix versions.
Full-matrix adaptive regularization
Corollary (Fuli-matrix Adaptive Regret Bound). Under assumptions) and when Adagrad is used as the blackbox A, the total regret Regret( IT) of the multiplicative weight algorithm in Algorithm 7 satisfies that for any interval 1 [s
Regret(I) =
(Dlog(T) max {
G GV/log(T),
min NEH
5

---

Under review as a conference paper at ICLR 2023
Remark 5. We notice that the log(T) overhead is brought by the of S and Cauchy-Schwaer We remark here that by replacing S with the set of all sub-intervals, we can achieve an improved bound with only Vlog(T) overhead using the same analysis. On the other hand, such improvement in regret bound is at the cost of efficiency, that each round need to make (T) computations.
Diagonal-matrix adaptive regularization If we restrict our expert optimization algorithm to be diagonal Adagrad, we can derive similar guarantee for the adaptive regret.
Corollary 6. Under assumptions and when diagonal Adagrad is used the blackbox A. the total regret Regret(I) of the multiplicatiive weight algorithm in Algorithm satisfies that for any interval I = t).
Regren(T) = (T)
D Σ
Vedtil22
Here Van,i denotes the ith coordinate of Σt VT.
4 EXPERIMENTS
In this section, we demonstrate empirical effectiveness of the proposed framework for online and offline learning scenarios. For online learning experiment, consider simulated data distribu- tion shift setting using CIFAR-10. For offline supervised learning, we experimented on standard benchmarks in vision and natural language processing domains.
4.1 ONLINE EXPERIMENTS
experiment setup: Our simulated online experiment is designed to assess robustness to unforeseen data distribution changes during training. Algorithms do not know advance whether or when the data shift will happen. We design this online data distribution shift with the CIFAR-10 dataset. We partition the CIFAR-10 dataset into two non-overlapping groups with five classes each. We denote D as the distribution for the first subset of data {X1, Yi} and D2 for the other subset of data {X2, Y2)- Specifically, the two subsets of data we used our implementation have categories {dog, frog. horse, ship, truck) and fairplane, automobile, bird, cat, deer]. We shift the data from D₁ D2 at iteration 17,000 out of a total of 25,600 training iterations. We choose this transition time point because empirically all baselines have stable performance this point, which permits fair comparison when the data shift occurs. We use the ResNet-I8 18 model for all experiments under this online setup. Since each subset of data only contains classes, we modified the model's last layer corresponding.
We compare our learning rate adaptation framework with different combinations of off- the-shelf learning rate schedulers and optimizers from the optax libray. To ensure fair comparison, we well-tuned the hyperparameters associated with each of the baseline learning rate schedule x optimizer combinations. Specifically, our baseline learning rate schedulers include constant learning rate, cosine annealing, exponential decay, and warmup with cosine annealing, Our baseline optimizers include SGD, AdaGrad, and Adam. total, we have 12 learning rate scheduler x optimizer pairs for baseline experiments. We report detailed hyperparameter choices for each baseline in the appendix.
baselines:
evaluation metrics: We evaluate our method and baselines using three performance metrics:
post-shift local accuracy: the average evaluation accuracy during a specified window starting at the beginning of the data distribution shift. We consider three window sizes: 100, 500, and 1000 iterations. This metric used to measure the robustness of algorithms immediately after the data distribution change.
shift accuracy: the maximum evaluation accuracy prior to the data distribution shift.
post-shift accuracy: the maximum evaluation accuracy after the data distribution shift.
implementation: We follow Algorithm | for SAMUEL implementation under the online setup. Our SAMUEL framework admits any choice of black-box OCO algorithms; for our online experiment use Adagrad. Each expert is an Adagrad optimizer with a specific external learning rate multiplier. The total number of training iterations 25,600 and specify the smallest geometric interval to

---

Under review as a conference paper at ICLR 2023
constant Ir
cosine annealing
SGD
AdaGrad
Adam
SGD
AdaGrad
Adam
avg acc. (window 100)
62.44+00.33
63.02+1.84
69.39-0.41
71.71+1.77
76.71-0.24
72.35+1.54
avg acc. (window500)
73.57++0.47
77.02++0.98
84,41+0.19
82.14+0.45
84.13=0.41
85.87+0.32
avg acc. (window 1000)
01.33-+0.25
81.34:1..77
87.55+0.14
85.05:+0.32
86.95=0.33
88.72:10.16
pre-shift acc.
96.29-10.04
96.2611.12
96,8710.05
97.06110.05
97.41=0.00
97.35:10.12
post-shift acc.
93.87-10.23
93.4910.117
94,2710.02
92.80:10:45
94.02=0.15
94.3210.16
warmup cosine annealing
exponential decay
SAMUEL (ours)
SGD
AdaGrad
Adam
SGD
AdaGrad
Adam
09.7310.98
71.8.10.64
74.1711.87
17.1311.48
69.6411.77
74.68=0.37
69.7110.83
07.31-10.16
83.27-10.00
84.23:1.33
83.00=0.433
78.83400.58
82.42-0.16
82.1410.36
89.21=10.05
86.12:4.21
86.81=0.15
86,49=10.22
81.96:40.44
85.06=0.12
85.66:10.27
97.47=00.13
97.26:+0.10
97.06=:.114
96.88=0.09
96.88:00.03
97.22=0.14
97.27=00.02
94.79++0.23
93.27++0.07
93.25++0.12
93.13=40.43
90.52+0..2
91.44=0.27
92.77=0.32
Table 2: Five accuracy metrics (%) for SAMUEL and baseline methods under online data distribution shift setup. Standard deviation computed using three runs with different random seeds.
120
SAMUEL vs. AdaGrad
SAMUEL vs.
SAMUEL Adam
50
00-
60
80-
60-
20
AdaGred Cencartt
50
SGD Constant
50
Ad4mL Coneant
Ada CentreArneal
SGD Cacre/men
Adam. Costretrneal
Gred DepenentalDecay
SGD Expor Decay
Adam. Exparent DiDcayy
Warmup Couinefenee
30-
5GD Wiammp Cosnsienea
Adam Warmu Casirekmmal
SAWKEL
SAMUEL
20
26-
20
17000
19520
17640
17660
17080
37100
17060
37620
1765e
37040
17560
12300
17030
37020
37540
17609
17080
37106
Figure 1: Behavior comparison following data distribution shift. Each subplot compares SAMUEL with an optimizer paired with different learning rate schedulers. We focus on a window of size 100 iterations post data distribution shift. SAMUEL systematically recovers fastest from data change and has a leading test accuracy throughout the window. The confidence band for each trace is the standard deviation computed across three different random seeds.
have length of 200 iterations. In total, the geometric intervals specified in Algorithm I hhave 8 different lengths, and therefore at each training iteration, experts are running on 8 different geometric intervals. Furthermore, we provide five learning rate candidates [0.05, 0.1, 0.25, 0.5, 1] to SAMUEL. In total 40 experts run at each training iteration. All experiments were carried out on TPU-V2 hardware with training batch size of 512.
results: We report the quantitative scores under five evaluation metrics of our algorithm and baselines Table We find that SAMUEL surpasses all baselines for every performance metric we considered. Although a number of baselines, such as Adagrad with cosine annealing, Adam with cosine annealing, and SGD with warmup cosine annealing, have comparable pre-shift test accuracy to SAMUEL, SAMUEL's ability to adaptively select the learning rate multiplier confers robustness to unforeseen changes data distribution. This is unsurprising, given that typical off-the-shelf learning rate schedulers give deterministic learning rate multiplier function across training and are therefore prone to suffering from data distribution changes. We also compare the qualitative behaviors of our algorithm and baselines within 100-iteration window after the data distribution change in Figure I It is clear from the plots that SAMUEL recovers faster than baselines. Furthermore, SAMUEL consistently maintains higher test accuracy throughout the window.
4.2 OFFLINE EXPERIMENTS
experiment setup: We experiment with popular vision and language tasks to demonstrate SAMUEL's ability in selecting optimal learning rates on-the-fly without hyperparameter tuning. The tasks conducted are image classification on CIFAR-10 10 and ImageNet, and sentiment classification on SST-2. We use ResNer-18 for CIFAR-10, ResNet-50 for ImageNet, and L.STM for SST-2.
7

---

Under review as a conference paper at ICLR 2023
baseline: We the step learning rate scheduler baseline, which is commonly used off-the-sheel scheduler. We specifically use a three-phase schedule where we fix the two step transition points based heuristics and provide five candidate learning rates to each phase. An exhaustive search thus yields a total of 125 different schedules.
implementation: We adjusted Algorithm 1 to be computationally efficient. Instead of running experts for each of the log 7 geometric intervals, we take a fixed number experts (five total experts for these experiments, with one candidate learning rate per expert) with exponential decay factor on the history. Unlike Algorithm where experts are initialized at the start of each geometric interval, we initialize experts at the step transition points. We introduce parameter a that determines the effective memory length: I(+1 =
o V. Vz. A fixed interval with different os
can be seen "soft" version of the geometric intervals in Algorithm All experiments were conducted on TPU-V2 hardware. We provide pseudo-code for the implementation in the appendix.
SA-U 0746-33
SANUIO Trapedes
SAMUEL AUVEELYYSSTT
Figure 2: Comparison of exhaustive searched step learning rate schedule (top) and SAMUEL (bottom) on CIFAR-10, ImageNet and SST-2.
We compare a ResNet-18 18 model trained with SAMUEL to ResNet-18 trained with Adagrad using brute-force searched step learning rate schedules. We process and augment the data following He et al. (2016). For training, we use batch size of 256 and 250 total epochs. We fix the learning rate transition point at epoch 125 and 200, and provide five candidate learning rates {0.0001, 0.001, 0.01, 0.1, } for each region. Thus an exhaustive search yields 125 different schedules for the baseline. For a fair comparison, we adopt the same learning rate changing points for our method. We compare the test accuracy curves of the baselines and methods in Fig 2 The left plot in Fig displass 125 runs using Adagrad for each learning rate schedule, where the highest accuracy is 94.95%. A single of SAMUEL achieves 94.76% with the same random seed (average 94.50% across 10 random seeds). which ranks in the top 3 of 125 exhaustively searched schedules.
CIFAR-10:
ImageNet: We continue examining the performance of SAMUEL on the large-scale ImageNet dataset. We trained ResNet-50 with exhaustive search of learning rate schedules and compare with SAMUEL. We also consider more practical step learning rate scheduling scheme where the learning rate decays after each stepping point. Specifically, the candidate learning rates are {0.2, 0.4, 0.6, 0.8, 1.0) in the first phase, and decay by 10x when stepping into the next phase. We set the stepping position at epoch 50 and 75 in a total of 100 training epochs. We adopted the training pipeline from Heee et al. (2020). For both baselines and SAMUEL, we used the SGD optimizer with nesterov momentum of 0.9 and training batch size of 1024. The second column of Fig displays the comparison of the exhaustive search baseline (top) to SAMUEL (bottom). The best validation accuracy out of exhaustively searched learning rate schedules is 76.32%. SAMUEL achieves 76.22% in single run (average 76.15% across 5 random seeds). Note that 76.22% is near-SOTA given the model architecture.
SST-2: We conduct experiments on the Stanford Sentiment Treebank (SST-2) dataset. We adopt the pipeline from (Heek et al. 2020 for pre-processing the SST-2 dataset and train simple bi-directional
8

---

Under review as a conference paper at ICLR 2023
SAMUEL hypermater tuning on CIFAR-10
test accuracy (96)
60
50
20
10050
20000
30030
45020
iteration
Figure 3: stability study of SAMUEL with different hyperparameters.
LSTM text classifier. We set the learning rate step transitions at epoch 15 and in a total 25 training epochs. For both baseline and our algorithm,
use SGD with momentum of 0.9 and additive weight decay of 3e-6 with training batch size of 64. The learning rate schedule setting is the same as that of CIFAR-10. 10. The right column of Fig. 2 shows that the best accuracy of exhaustive search is 86.12%, and the accuracy of SAMUEL using the same seed is 85.55% (average 85.58% among 10 different random seeds).
stability of SAMUEL:
We demonstrate the stability of SAMUEL to hyperparameter tuning. Since algorithm will automatically select the optimal learning rate, the only tunable hyperparameters are the number of multiplicative weight factor and the quantity of history decaying factors, a. We conduct 18 trials with different hyperparameter combinations and display the test accuracy curves in Fig 3 Specifically, we consider the quantity of decaying factors a with values {2, 3, 6} and (5, 10, 15, 20, 25,30) 30) number of 17 As Fig shows, all trials in SAMUEL converge to nearly the same final accuracy regardless of the exact hyperparameters.
computation considerations: A table of runtime comparison is provided in the appendix. As described in the implementation section, SAMUEL here has five experts in total, which incurs five times more compute than one single run of the baseline. Nevertheless, this is dramatic improvement over brute-force hyperparameter sweeping of learning rate schedulers. For the step learning rate scheduler we experimented with, SAMUEL is times more computationally efficient than tuning the scheduler with grid search. In addition, experts can be fully parallelized across different acceleration devices. expected that the run time of SAMUEL would approach that of a single run of the baseline with efficient implementation.
CONCLUSION
In this paper we study adaptive gradient methods with local guarantees. The methodology based on adaptive online learning, in which contribute a novel twist the multiplicative weight method that we show has better adaptive regret guarantees than state of the art. This, combined with known results in adaptive gradient methods, gives algorithm SAMUEL with optimal full-matrix local adaptive regret guarantces. We demonstrate the effectiveness and robustness of SAMUEL in experiments, where show that SAMUEL better task accuracy in online tasks with distribution shifts. For offline tasks, SAMUEL consistently achieves comparable accuracy an optimizer with fine-tuned learning rate schedule, using fewer overall computational resources in hyperparameter tuning.
automatically adapt the optimal learning rate and achieve
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang Efficient full-matrix adaptive regularization. In International Conference on Machine Learning. pp. 102-110. PMLR, 2019.
Naman Agarwal, Surbhi Goel, and Cyril Zhang. Acceleration via fractal learning rate schedules. arXiv preprint arXiv:2 10t.0220003333 2021.

---

Under review as a conference paper at ICLR 2023
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta- algorithm and applications. Theory of computing, 8(1):121-164, 2012.
Olivier Bousquet and Manfred K. Warmuth. Tracking small set of experts by mixing past posteriors. Mach. Learn. Res., 3:363-396, 2003. ISSN 1533-7928.
Xinyi Chen, Naman Agarwal, Elad Hazan, Cyril Zhang, and Yi Zhang. Extreme tensoring for low-memory preconditioning. In International Conference on Learning Representations, 2019.
Dami Choi, Christopher Shallue, Zachary Nado, Jachoon Lee, Chris J Maddison, and George E Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint 2019.
Ashok Cutkosky. Parameter-frre, dynamic, and strongly-adaptive online learning. In International Conference on Machine Learning, pp. 2250-2259. PMLR, 2020.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405-1411, PMLR, 2015.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. In International Conference on Machine Learning, pp. 1842-1850, PMLR, 2018.
Elad Hazan. Introduction online convex optimization. Foundations and TrendsÅ@ Optimization, 203-4::57-322, 2016. ISSN 2167-3888. doi: 10.1561/24000000113 URL http://cxx doi TTg/10.1551/24000000
Elad Hazan. Lecture notes: Optimization for machine learning. arXiv preprint arXiv: 190.v31900.03550 2019.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on computational complexity (ECCC), volume 14-088, 2007.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Mare van Zee. Flax: A neural network library and ecosystem for JAX, 2020. URL
http://github. ctm/ wtt.:cocmmggoogoe gotg////oglllleeooe
Mark Herbster and Manfred Warmuth. Tracking the best expert. Mach. Learn., 32(2):151-178, www..dd..rr//1.100//......
1998. ISSN 0885-6125. doi:
Kwang-Sung Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statistics, pp. 943-951. PMLR, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Zhiyuan Li and Sanjeev Arora, An exponential learning rate schedule for deep learning. arXiv preprint arXiv:1910.07454 2019.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-2611 1994.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint /608 /008000833 2016.
10

---

Under review as a conference paper at ICLR 2023
Zachary Nado, Justin M Gilmer, Christopher J Shallue. Rohan Anil, and George E Dahl. A large batch optimizer reality check: Traditional, generic optimizers suffice across batch sizes. arXiv preprint w7X1v:2102.063566, 2021.
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Descending through crowded valley- benchmarking deep learning optimizers. arXiv preprint arXiv:2007.01547, 2020.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pp. 4596 4604. PMLR, 2018.
Tijmen Ticleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4151-4161, 2017.
Xiaoxia Wu, Rachel Ward, and Léon Bottou. Wngrad: Learn the learning rate in gradient descent.
arXiv preprint arXiv: 1803 028665 2018.
Lijun Zhang, Tianbao Yang, Zui-Hua Zhou, et al. Dynamic regret of strongly adaptive methods. In International conference machine learning, pp. 088825891. PMLR, 2018.
Lijun Zhang, Tie-Yan Liu, and Zhi-Hua Zhou Adaptive regret of convex and smooth functions. In International Conference on Machine Learning, pp. 7414-7423, PMLR, 2019.
Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simulta- neously. International Conference on Artificial Intelligence and Statistics, pp. 309-319, PMLR, 2020.

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 PROOF OF THEOREM
2
Proof. We define the pseudo weight w, (1,q) w. (1.9g/ m1 for t S and for t we just set wr (I,q) - (T, q). Let Wr = Lis((), w,(1, q). we are going to show the following inequality
W, - (log(T)) + 1) log( ( log(T)
(1)
We prove this by induction. For r follows since on any interval [1, the number of experts is exactly the number of possible gs, and the number of intervals [1, E C S is Ollog(T)) Now we assume holds for all r' S т. We have
W+11= = Σ
w++1(I,9)
IES(r+1)
Σ
(T+1(I,9)
Σ
(++1(I,9)
S llog(T + 11)(T++))og((777) 1o))og((TD)) log))))))))))))))))))))))))))))) +14
Σ
(T,1(1,9)
= llog(r + 1) (og)) log(T) +1+
+1+
Σ
T (1, + m))r(())
log(T + 10)(++))ogg(dT))) log(T) +1+
Σ
(,,
wr
1E3(F).4
$ (T + 1)(ogg + + 1)
log log log(T)+
+
Σ
w/ (,(4g))r,
IES.
We further show that ElEStr) wy w- (1,gg)==(1) S:
Σ
w-(I.g)r+(1) = W, Σ
- ((((
IES(T).g
IES(F).g
W Σ pr(T,9)( Σ
IES(F)
JES(T).4
which finishes the proof induction.
Based on this, proceed to prove that for any I= [s, S.
(iog(() max
Σ (1) =
DG Dlg(T),(),
Σ (v. (x, - x, (1)))2
T=a
By inequality
we have that
(1, q) I W441 s + 1) + 1) + log log(T)
Taking the logarithm of both sides, we have
log( W (I,g)) q)) I log(t 1) + log(log(t + 1) + 1) log(og((TTD)'))) log(log(T)))
Recall the expression
W (T,9) = II + (lgg+((1)
By using the fact that log(1 + x) 2 x - x2, Vr 2 - 1/2 and
(m)))((1)) 4GD
|زم x [I.gg)]22 S 1/2
12

---

Under review as a conference paper at ICLR 2023
obtain for any
log( (T,4)) Σ m.r"r(1) (1) (
Now upper bound the term Er= T+ (T)2. By convexity have that r+( (x(x+) (x+ V. (s, xr (1)), hence
4 (T)
Σ (1) 5
+ 4mr
Σ 1=9
[V. (a, - xx,
T]..9
The next step is upper bound the term V (xy (T)) By Hölder's inequality have that V (xe, (T)) - | H-ll=-1lee || - xr (+())l ll for any H. As a result, we have that for any which
PSD and tr(11) S d,
(V, (2, Tr (1)))
xI, - S V
where ||,, - x (1) < d is by elementary algebra: let H = V- MV be its diagonal decomposition where B is a standard orthogonal matrix and M is diagonal. Then
| (1)l (x, xxr (1)) H(x, - x+(()) (V(x+ =-)( MV xz- xI)
(V I. TT)) x., (T)
$ 4Ddd
Hence
(To
Σ
4m1.g D2
min V H-
min
71.4
H
T=8
The optimal choice of is of course
log(T) Ddd minn Eis V H-
When minn E V -. S 64G2 D2 (T)( m gives the bound OGGD log(T)). When D2d ming E V -. > 64G D2 log(T), there always exists such that 0.51jr. S S
2mr. by the construction of that the regret Rí (T) is upper bounded by
o D log max
G GVlog(T),
min MEH
V H-
(2)
Now we have proven an optimal regret for any interval / E S, it's left to extend the regret bound to any interval J. We show that by using Cauchy-Schwarz, can achieve the goal the cost of an additional / /log(T') term. We need the following lemma from Daniely al. 2015
Lemma (Lemma 5 in Daniely et al. (2015).. For any interval J, there exists set of intervals S such that S contains only disjoint intervals whose union is exactly J. and |S (log(T))
We now use Cauchy-Schwarz to bound the regret:
Lemma 8. For any interval J which can be written as the union of disjoint intervals U,I, its regret Regrel(J) can be upper bounded by:
Regret(J) S
Regret(T.)
13

---

Under review as a conference paper at ICLR 2023
Proof. The regret over J can be controlled by Regret(J)) Ei=1 Regret(I.). By Cauchy-Schie we have that
Regret(L.)) n Regret(11)
which concludes our proof.
We can now upper bound the regret (J) using Lemma 8 replacing Regret by Rí and n by |S,| (T))) For any interval J, its regret R1 (J) can be upper bounded by:
R1(J) $
SS Σ RT(T)²
IES,
Combining the above inequality with the upper bound on R (T)
we reach the desired conclusion.
A.2 PROOF OF COROLLARY
Proof. Using Theorem
2 have that R1 (T) is upper bounded by
Rí (1) (og(T) max
G (oVlog(T).oo d
|
11
HEH
Because each interval J E S, one of the Adagrad experts achieve the bound
Ro(J) = Dat
min
V
For any interval I, using the result from Daniely et al. (2015) (Lemma) 7 and Lemma 8 by replacing Regret by Ro, follows
Ro(1) 0 DV
min MEH
11
Combining both bounds give the desired bound on Regret(I).
A.3 PROOF OF COROLLARY
Proof. The proof is almost identical to that of the previous corollary, observing that the re- gret RT( is Ō(D>o Ed (ataill)) due to Duchi et al. (2011), and the regret (T) remains Ö(DY minHEn E H V+), which upper bounded by Ö(Doc Ed (V.a..)l))
A.4 BASELINE HYPERPARAMETERS FOR ONLINE EXPERIMENTS
Here we report the hyperparmeters used in the baseline learning rate schedulers in the online experiments. We use the off the-shelf learning rate schedulers from the optax library. Please refer to the optax documentation for the specific meaning of the parameters.
AdaGrad
constant learning rate: learning rate 0.2.
cosine annealing: init value 0.2, decay steps = 25600, alpha = 0.
warmup with cosine annealing: init value = le-5, peak value 0.15, warmup steps = 1000, end value O.
exponential decay: init value 0.35, transition steps= 3000, decay rate 0.5.
14

---

Under review as a conference paper at ICLR 2023
SGD
constant learning rate: learning rate 0.15.
cosine annealing: init value 0.3, decay steps = 25600, alpha = =0 warmup with cosine annealing: init value = le-5, peak value = 0.5, warmup steps = 1000, end value O.
exponential decay: init value 0.6, transition steps= 3000, decay rate 0.5.
Adam
constant learning rate: learning rate 0.001.
cosine annealing: init value 0.001, decay steps 25600, alpha 0.
warmup with cosine annealing: init value le-5, peak value 0.005, warmup steps 1000, end value = O.
exponential decay: init value 0.005, transition steps= 3000, decay rate 0.5.
A.5 COMPUTE COMPARISON FOR OFFLINE EXPERIMENTS
We report the compute resource consumption of both baselines and SAMUEL from the offline experiments. We run experts sequentially and the running time of our algorithm is longer than the baselines. With more efficient implementation and parallelizing each expert across TPU devices, it is expected the running time of SAMUEL would approach the running time of the baseline algorithm.
CIFAR-10
device config
runtime (m)
grid-search cost (trials)
runtime per expert (m)
total TPU hours
baseline
4TPU
11
125
11
91.6
SAMUEL
4TPU
13.2
ImageNet
baseline
4TPU
254
125
254
2116.6
SAMUEL
16TPU
794
158.8
211.7
SST-2
baseline
ITPU
12
125
12
25
SAMUEL
4TPU
25
5
1.6
Table 3: compute comparison
A.6 PSEUDOCODE FOR OFFLINE EXPERIMENTS
15

---

Under review as a conference paper at ICLR 2023
Algorithm SAMUEL experiment pseudocode
1: Input: AdaGrad optimizer A, constant Q, set of learning rates 01, 0.001, 0.0000, reinitialize frequency
2: Initialize: for each learning rate i S, copy of A,
3: Set 1/K.9 = 24 for q E [1, Q].
4: Initialize wi (t)
(1/2 m..)) Initialize NN params 20
5: for 7 = 1..... do
6: Let updated NN params x, (1, A,(
7: Let W, = Ei, wt (1,
8: sample according to (i, g) /)
9: Receive batch loss (((,),, define r-(i)= = l. (+(7)) (xx(((11))
10:
For each i, update w++1 9) as follows.
Wr+ (i, q) wr (i, (1 + n1.0 (1)
11: if 7%K 0 then
12: Re-initialize w- (1. = min mr,g)
13: All copies A, start from NN params Fr
14:
end if
end for
16


Reviews:
[{"review_id": "lzJwwQ9EE74", "reviewer": "Reviewer_vT2z", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Based on the strongly adaptive regret framework of Daniely et al., this paper proposes a strongly adaptive version of AdaGrad. The novelty seems to lie in an improved regret bound of SAOL, the meta algorithm of Daniely et al., which is similar to the regret bound of AdaGrad.", "summary_of_the_review": "The idea is novel, simple, and seems to be empirically effective. However, the correctness of the theory is unclear to me, and the regret bound is indeed worse than that of AdaGrad by a $\\sqrt{d}$ factor, which seems to be dismissed in the paper. Also, the connection between the proof of this paper and that by Daiely et al. is not addressed; this can mislead the reader about the paper's novelty. Therefore, I cannot suggest acceptance of this paper currently. \n\n====\n\n***After reading the author response***\n\nThe first two weaknesses were actually due to my carelessness. I am sorry. \n\nHowever, the technical novelty seems to be limited and there is a novelty issue regarding the paper by Zhang et al. (NeurIPS 2021). So I cannot recommend acceptance of this paper. \n\nTwo suggestions to the authors: \n1. Please highlight the novelty and address explicitly address what parts essentially follow existing proofs, to help the reader evaluate the novelty of the paper and its connection to existing literature.\n2. Please make the dependence on dimension and possibly other problem parameters explicit in the big-O notations (e.g., in Table 1).", "strength_and_weaknesses": "***Strength***\nThe idea is novel, simple, and seems to be effective in practice. \n\n***Weaknesses***\n1. I do not understand the proof of Theorem 2, the main result, in Appendix A. Perhaps I missed something. The proof consists of three parts, among which the second part is new and confusing. \n    - The first part, until the first inequality on p. 13, just follows the proofs of Lemma 1 and Lemma 2 of Daniely et al. \n    - The second part is new and confusing to me. It directly analyzes the regret, without referring to any intermediate result obtained in the first part. The meaning of the first part is then unclear. \n    - Moreover, the second part starts with a regret bound of SAOL, which is the second inequality on p. 13. The regret bound is given without any proof and citation, but it is not obviously true to me. \n    - The third part, starting from Lemma 7, is a directly application of the results by Daniely et al. \n2. If I understand correctly, the result in this paper does not actually inherit the regret bound of AdaGrad. The regret bound in this paper has a $\\sqrt{d}$ factor which is not present in the regret bound of AdaGrad (see, e.g., Theorem 5.6.1 of the second version of *Introduction to Online Convex Optimization* by Hazan). \n3. This is minor: Why not define $D$ as the radius of the constraint set? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "f9YmPFzInD", "reviewer": "Reviewer_dUbb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the classic online convex optimization game and proposes a method to obtain “full matrix” regret bounds in a “strongly adaptive” sense. That is, the algorithm outputs $w_t\\in W\\subset \\mathbb{R}^d$ in response to vectors $g_1,\\dots,g_{t-1}$ such that for any interval [a,b], the algorithm ensures:\n$$\\sup_{u\\in W} \\sum_{t=a}^b \\langle g_t, w_t - u\\rangle \\le \\tilde O(D \\sqrt{d} \\inf_{H\\in \\mathcal{H}}\\sqrt{\\sum_{t=a}^b g_t^\\top H^{-1} g_t}$$\n\nWhere $\\mathcal{H}$ is the set of symmetric PSD matrices of trace at most $d$ and $D$ is the L2 diameter of $W$.\n\nExperiments are presented on problems with explicit drift and in offline deep learning settings.\n", "summary_of_the_review": "The theoretical results appear to not show advantage over prior methods. Given the focus of much of the paper on theory, this seems a significant issue.", "strength_and_weaknesses": "\nSo far as I can tell, the results appear to be correct and are clearly presented and well-motivated. However, I have some concerns about the quality of the theoretical bounds.\n\nIn particular, the main term in the regret bound of $\\sqrt{d} \\inf_{H\\in\\mathcal{H}} \\sqrt{\\sum_{t=a}^b g_t^\\top H^{-1} g_t}$ is equal to $\\text{trace}\\left(\\sqrt{\\sum_{t=a}^b g_tg_t^\\top}\\right)$ (by https://jmlr.org/papers/volume12/duchi11a/duchi11a.pdf lemma 15). \n\nNow, by applying the identity $\\sum_{i} \\sqrt{\\lambda_i} \\ge \\sqrt{\\sum_i \\lambda_i}$ to the eigenvalues of $\\sum_{t=a}^b g_tg_t^\\top$, we have: $$\\text{trace}\\left(\\sqrt{\\sum_{t=a}^b g_tg_t^\\top}\\right)\\ge \\sqrt{\\text{trace}\\left(\\sum_{t=a}^b g_tg_t^\\top\\right)}=\\sqrt{\\sum_{t=a}^b \\|g_t\\|^2}$$ where $\\|\\cdot\\|$ indicates the 2-norm. Thus, the proposed bound of $D \\sqrt{d} \\inf_{H\\in \\mathcal{H}}\\sqrt{\\sum_{t=a}^b g_t^\\top H^{-1} g_t}$ appears to never improve upon $D\\sqrt{\\sum_{t=a}^b \\|g_t\\|^2}$.  However, this bound is relatively easily obtainable without resorting to expensive matrix operations (e.g. in Cutkosky 2019 as cited in the paper. I believe also the analysis of Zhang et al 2018 https://arxiv.org/pdf/1906.10851.pdf can be tweaked to achieve this).\n\nSee for example http://blog.wouterkoolen.info/GrokkingAdaGrad/post.html for more discussion of this issue. So, while I am willing to believe that there is a possible improvement in the regret here, I do not see how this analysis brings it out. Instead, the theoretical result appears to be a somewhat worse regret bound with a significantly less efficient algorithm.\n\nSome possibilities in this regard:\n\nWhile the Duchi et al. 2011 does propose an example in which full-matrix adagrad performs better than a scalar learning rate, this analysis involved a special-case analysis of the dynamics of the algorithm rather than simply comparing regret bounds. Perhaps there is some way to modify this analysis to derive a general regret expression that can be applied here.\n\nAlternatively, Cutkosky 2020 (https://proceedings.neurips.cc/paper/2020/hash/6495cf7ca745a9443508b86951b8e33a-Abstract.html) suggests that one can improve the analysis of adagrad by tuning the scalar part of the learning rate more carefully. Given the focus on learning rate adaptation in the experiments, perhaps the analysis could be improved to show a similar or better result in theory.\n\n\nBeyond this issue, there should ideally be some discussion of Zhang et al 2018 https://arxiv.org/pdf/1906.10851.pdf  which achieves a different full-matrix bound of: $$\\sum_{t=1}^T \\langle g_t, w_t - u\\rangle \\le \\tilde O\\left(\\sqrt{d \\sum_{t=a}^b \\langle g_t, w_t-u\\rangle^2}\\right).$$ Since both this paper and that one attempt to decrease the meta regret beyond $O(\\sqrt{T})$ to obtain a better bound, it would be valuable to describe the differences.\n\n\nRegarding the experiments: I appreciate the promise here, but I do not feel that these are convincing enough to overcome the analytical issues. With particular regard to the offline deep learning experiments, I am concerned that the algorithm will not scale to larger models. My understanding is that for modern extremely large models, even the space requirements that are a small linear multiple of the model size (e.g. as in Adam) can become difficult to accommodate, so I would much prefer to see convincing evidence that the method can scale up well. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OU_nrr977HW", "reviewer": "Reviewer_fGkK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an algorithm for strongly-adaptive full-matrix regret of the form $R_I\\le \\tilde O(\\min_{H\\succ 0}\\sqrt{\\sum_{t\\in I} \\|\\|\\nabla\\ell_t(w_t)\\|\\|^2_{\\star,H}})$ for any interval $I\\subseteq[1,T]$. The core idea is to apply the geometric covering intervals of Daniely 2015 with instances of full-matrix AdaGrad as the base learners. A simplified version of the algorithm is tested empirically in simple online and offline experiments.", "summary_of_the_review": "Overall, I do not recommend accepting this paper in its current form. I am not confident in the correctness of the algorithm and analysis, which constitutes the main contributions of the paper, and a prior work (Zhang 2021) seems to achieve a strictly stronger result. The experimental results serve mostly as a sanity check, showing that a simplified version of their algorithm does something reasonable, but do not provide any novel insights in their own right.", "strength_and_weaknesses": "Correctness\n---\nI have some concerns with the correctness of the analysis. \n\nFollowing standard experts analysis, the regret over an interval $I$ is decomposed as the regret of an expert $A_k$ on the interval, $R_{A_k}(I)$, and the regret of the meta-algorithm on the interval $R_\\mathit{meta}(I, A_k)$ for not choosing this expert. To get the right rate in the meta-algorithm, it's necessary to balance a $\\frac{\\log(T)}{\\eta}$ and a $\\eta\\sum\\langle\\nabla\\ell_t(w_t),w_t-u\\rangle^2$ term, where $\\eta$ is the scaling factor of AdaGrad's step-size (see [Duchi 2011, Algorithm 2](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=14)). Since the optimal $\\eta^\\star$ is unknown a priori, the proposed algorithm runs several instances of AdaGrad over a grid of values, and argue that some $\\eta_k\\approx\\eta^\\star$, so that the meta-algorithm has the correct bound.\n\nThe flaw then is that it is stated that $R_{A_k}(I)\\le O(D\\min_{H\\succ 0}\\sqrt{\\sum \\|\\| \\nabla\\ell_t(w_t)\\|\\|^2_{\\star,H}})$ since it is an instance of AdaGrad (i.e. [Corollary 11](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=16)). But this is not true for arbitrary $\\eta$. Instead, one should be invoking [Theorem 7](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=13) to get\n\\begin{align*}\nR_{A_k}(I)&\\le O\\left( \\frac{\\|\\|x^{\\star}\\|\\|^2\\text{Trace}(G_t^{\\frac{1}{2}})}{\\eta_k}+\\eta_k \\text{Trace}(G_I^{\\frac{1}{2}})\\right)\\\\\\\\\n&\\le O\\left( \\frac{\\|\\|x^{\\star}\\|\\|^2\\sqrt{\\min_H\\sum_t\\|\\|\\nabla\\ell_t(w_t)\\|\\|^2_{\\star,H}}}{\\eta_k}+\\eta_k\\sqrt{\\min_H\\sum_t\\|\\|\\nabla\\ell_t(w_t)\\|\\|^2_{\\star,H}}\\right)\n\\end{align*}\nwhere $G_I=\\sum_{t\\in I}\\nabla \\ell_t(w_t)\\nabla\\ell_t(w_t)^\\top$, and the inequality applies [Lemma 15](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=31).\nNow if we assume that $\\eta_k\\approx \\eta^\\star=\\sqrt{\\frac{\\log(T)}{D^2d\\min_H\\sum_t\\|\\|\\nabla\\ell_t(w_t)\\|\\|^2_{\\star,H}}}$ (from page 13), we seem to get something strange like\n\\begin{align*}\nR_{A_k}(I)\\le \\tilde O\\left(D^3\\sqrt{d}\\min_H\\sum_t\\|\\|\\nabla\\ell_t(w_t)\\|\\|^2_{\\star,H}\\right).\n\\end{align*}\n\n\nAside from this, there were a few minor oddities:\n- Why are we assuming $G\\ge 1$ and $D\\ge 1$? This is not standard shouldn't really be necessary either\n- It seems strange that the number of experts $Q=4\\log(dTG^2D^2)$ in each interval is tied to the Lipschitz constant and the size of the domain, I don't think i've seen this happen in any prior works and it seems like it could lead to infeasible computation even at short horizons. In general, It's sort of rare to see factors of $G$ and $D$ inside of a logarithm without some fudge factor $\\epsilon$ to correct the \"units\". I suspect that this issue is actually related to the above assumption that $G\\ge1$ and $D\\ge 1$ and the number of experts in an interval should actually be more like $O(\\log(T))$\n\nThe Algorithm\n---\n- To get this sort of bound, is there any reason you couldn't just apply the residual learning algorithm of Cutkosky 2020? Their approach needs the base algorithm to have the parameter-free property $R_I(0)=\\sum_{t\\in I}\\langle\\nabla\\ell_t(w_t),w_t\\rangle\\le \\epsilon$ for some $\\epsilon$, but there are algorithms with full-matrix regret bounds that do this, such as the Matrix FreeGrad algorithm of Mhammedi 2020.\n\nExperiments\n---\n- \"As described in the implementation section, SAMUEL here has five experts in total, which incurs five times more compute than one single run of the baseline. Nevertheless, this is a dramatic improvement over brute-force hyperparameter sweeping of learning rate schedulers\"\n  - I'm confused by this.  The preceeding paragraph states \"specifically, we consider the quantity of decaying factors α with values {2, 3, 6} and {5, 10, 15, 20, 25, 30} number of $\\eta$\"; does this not imply that SAMUEL takes either 5x, 10x, 15x, 20x, 25x, or 30x computation compared to the baseline? Moreover, since these hyperparameters were tuned, overall didn't SAMUEL use the equivalent computation of a baseline which had its hyperparameters tuned over $3*(5+10+15+20+25+30)=315$ values?\n  - Similarly, at the start of the section it's stated that \"We experiment with popular vision and language tasks to demonstrate SAMUEL’s ability in selecting optimal learning rates on-the-fly without hyperparameter tuning\"; but it seems that $\\eta$ and $\\alpha$ were actually  tuned hyperparameters?\n- Specific hyperparameter settings are given in the appendix, but as far as I can tell there's no mention of how the baselines' hyperparameters were actually tuned. Without this information I can't really tell if these are actually reasonable baselines to compare against.\n- \"We demonstrate the effectiveness and robustness of SAMUEL in experiments, where we show that SAMUEL can automatically adapt to the optimal learning rate\"\n  - This was never actually demonstrated, just that SAMUEL empirically outperformed the baselines, none of which necessarily are equivalent to using the optimal learning rate\n\n\nReferences\n---\n[1] Mhammedi, Z., & Koolen, W. M. (2020). Lipschitz and comparator-norm adaptivity in online learning. In J. Abernethy, & S. Agarwal, Proceedings of Thirty Third Conference on Learning Theory (pp. 2858–2887). PMLR.\n\n[2] Cutkosky, A. (2020). Parameter-free, dynamic, and strongly-adaptive online learning. In H. D. III, & A. Singh, Proceedings of the 37th International Conference on Machine Learning (pp. 2250–2259). PMLR.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject