Statistical Adaptive Stochastic Optimization
Authors: Pengchuan Zhang
Hunter Lang
Qiang Liu
Lin Xiao
Venue:  (2020)

Abstract: We investigate statistical methods for automatically scheduling the learning rate (step size) in stochastic optimization. First, we consider a broad family of stochastic optimization methods with constant hyperparameters (including the learning rate and various forms of momentum) and derive a general necessary condition for the resulting dynamics to be stationary. Based on this condition, we develop a simple online statistical test to detect (non-)stationarity and use it to automatically drop the learning rate by a constant factor whenever stationarity is detected. Unlike in prior work, our stationarity condition and our statistical test applies to different algorithms without modification. Finally, we propose a smoothed stochastic line-search method that can be used to warm up the optimization process before the statistical test can be applied effectively. This removes the expensive trial and error for setting a good initial learning rate. The combined method is highly autonomous and it attains state-of-the-art training and testing performance in our experiments on several deep learning tasks.

Under review as a conference paper at ICLR 2020
STATISTICAL ADAPTIVE STOCHASTIC OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate statistical methods for automatically scheduling the learning rate (step size) in stochastic optimization. First, we consider broad family of stochas- tie optimization methods with constant hyperparameters (including the learning rate and various forms of momentum) and derive a general necessary condition for the resulting dynamics be stationary. Based on this condition, we develop a simple online statistical test to detect (non- soton))staiinartty and use it to automati- cally drop the learning rate by constant factor whenever stationarity detected. Unlike in prior work, our stationarity condition and statistical test apply to differ- ent algorithms without modification. Finally, we propose a smoothed stochastic line-search method that can be used to warm up the optimization process before the statistical test can be applied effectively. This removes the expensive trial and error for setting good initial learning rate. The combined method is highly tonomous and it attains statc-of-the-ant training and testing performance in our experiments several deep learning tasks.
INTRODUCTION
We study adaptive stochastic optimization methods in the context of large-scale machine learning. Specifically, we consider the stochastic optimization problem
minimize #ERP
F F(x) e [f(()]]]]
(1)
where & a random variable representing data sampled from some (unknown) probability distribu- tion. 2 E R represents the parameters of the machine learning model (e.g., the weight matrices in a neural network), and fe is the loss function associated with data Ç. The objective function is the expectation of fe over the distribution of the data.
Many stochastic optimization methods for solving problem 1 can be written in the form
x+1 x² agd
(2)
where d is a (stochastic) search direction and as > O is the step size or learning rate. In the classical stochastic gradient descent (SGD) method,
where & training example (or mini-batch of examples) randomly generated iteration k. This method traces back to the seminal work of Robbins & Monro (1951), and it has become very popular machine learning (e-g.. Bottou 1998 Goodfellow et 2016). Many modifications of SGD aim to improve its theoretical and practical performance. For example, Gupal & Bazhenov (1922) studied a stochastic analog of the heavy-ball method (Polyak) 1964). where
d = =1 -1-3x) 3x)g" + 3kd
and B& E [0,1) is the momentum coefficient. SSutskever et al. 2013 proposed to use a stochastic variant of Nesterov's accelerated gradient method Nesterov 2004). where
V Ve. (x
axBidd + 3
(5)
Other recent variants include, e.g., Jain al. (2018) and Ma & Yarats 2019
Theoretical conditions for the asymptotic convergence of SGD are well studied, and they mostly focus polynomially decaying learning rates of the form 0g (b k) for some a, >

---

Under review as a conference paper at ICLR 2020
and 1/2 < <c < 1 (e.g., Robbins & Monro 1951 Polyak & Juditsky 1992). Similar conditions
for the stochastic heavy-ball methods are also established (e.g., Gupal & Bazhenov, 1972 Polyak [977). However, these learning rate schedules still require significant hyperparameter tuning efforts in modern machine learning practice.
Adaptive rules for adjusting the learning rate and other parameters the fly have been developed in both the stochastic optimization literature (e.g., Kesten 1958 Mirzoakhmedov & Uryasev] [983]
Ruszczyáski& & Syski 1983] 1984 1986a b Delyon & Juditsky, 1993) and by the machine learning
community (e.g.. Jacobs 1988 Sutton, 1992 Schraudolph 1999; Mahmood et al., 2012 Baydin
al., 2018). More recently, adaptive algorithms that use diagonal scaling replacing 0r in () with
an ad justable diagonal matrix- have become very popular (Duchi et al. [011] Tieleman & Hinton
2012 Kingma & Ba, 2014 e.g..) Despite these advances, costly hand-tuning efforts are still needed to obtain good (generalization performance in practice (Wilson et al. 2017).
In this paper, we focus on statistical methods for automatically scheduling the learning rate. This line of work goes back to Kesten (1958), who used the change of sign of the inner products of consecutive stochastic gradients as a statistical indicator of slow progress and as a trigger to decrease the learning
rate (see extensions in Delyon & Juditsky 1993). Pilug (1983) 1988) considered the dynamics
of SGD with constant step size for minimizing convex quadratic functions and derived necessary conditions for the resulting process to be stationary. PHug (983 1990) also devised sequential statistical test to detect stationarity; when the test fires, the step size is decreased by a constant factor. Ruszczyúski & Syski (183)) used online statistical tests to check if the present step size and momentum constants satisfy certain optimality conditions and adjust them if the conditions are not satisfied. However, Lang et al. (2019) found that these methods have limited success in machine learning applications due to their reliance on quadratic approximation and/or strong assumptions on the noise models.
Most recently, Yaida 2018) derived fluctuation-dissin dissipptiinn relations (necessary conditions) that characterized the stationary behavior of stochastic gradient methods with constant learning rate and momentum. These relations hold exactly for any stationary state (regardless of the loss function or the noise model), so they can be very effective at detecting stationarity and can serve as a reliable indicator of when to decrease the learning rate. [Lang et al. (2019) devised more rigorous statisti- cal test for Yaida's conditions and obtained robust and competitive performance on common deep learning tasks.
Our contributions in this paper are threcfold:
We consider a broad family of stochastic optimization methods with constant hyperparameters (including the learning rate and various forms of momentum) and derive a more general neces- sary condition (than Yaida's) 's) for the associated learning process to be stationary. Yaida (2018) established a "master equation." " from which different stationarity conditions can be derived for different variants of stochastic gradient methods (some of them may not admit a usable analyti- cal form). We derive a simple "master condition" that works for different methods without any change and holds exactly for any stationary process. Because of its conceptual and analytical simplicity, it greatly simplifies implementation and deployment in software packages.
We develop simple statistical test for checking stationarity based our "master condition." It is a simple confidence interval test (checking if it contains zero), as opposed to the "equivalence test" for Yaida's condition used by Lang al. (0199) This simple test is as robust as the equivalence test and avoids the use of an additional hyperparameter.
A major challenge for almost all adaptive stochastic gradient methods is how set the initial learning rate appropriately without expensive trial and error. We propose a smoothed stochastic line-search method that can be used to warm up the optimization process. Starting from any safe, small learning rate, this method automatically increases it to a suitably large value for fast initial convergence. Afterwards, the statistical test for stationarity can be applied to gradually reduce the learning rate and obtain finer convergence.
Combining the three components above, we obtain highly autonomous algorithm called SALSA (Stochastic Approximation with Line-search and Statistical Adaptation). We conduct extensive ex- periments several deep learning tasks to test its training and testing perfromance well as its robustness to changes in the hyperparameter settings. SALSA matches the best performance of hand-tuned methods across different deep learning tasks using default hyperparameters.
2

---

Under review as a conference paper at ICLR 2020
2 NECESSARY CONDITIONS FOR STATIONARITY
We consider general stochastic optimization methods in the form of with constant learning rate:
2 x ad..
(6)
We assume that the stochastic search direction d is generated with time-homogeneous dynamics; In particular, any additional hyperparameters involved must be constant (not depending on k). As an example, we consider the search directions generated by the family of Quasi- -yyer-Hyperbolic Momentum
(QHM) methods (Ma & Yarats 2019):
ht = (1 3)g" + 3,
dt = (1- + +vh.
where 0 < 3 < 1 and 0 u. 1. With B = or v O, it recovers the SGD direction 33. With With 0 <
= recovers the stochastic heavy-ball direction to the direction with Nesterov momentum given in ( (Susskevrr et al. 2013 Gitman et al. 2019).
< 1. it is equivalent
We assume that the dynamics of (6) e.g., driven by stochastic gradients 9 through (7). stable. Stability regions of the hyperparameters in QHM are characterized by Gitman et al. (2019).
In addition, we assume that the stochastic process {x*), as -> co, becomes stationary. Recall that (x*) is (strongly) stationary if the joint distribution of any subset of the sequence is invariant
with respect to simultaneous shifts in the time index (e.g., Dembo 2013 Section 3.2.3). As direct consequence, for any deterministic function
R² R. we have
E, [o[ Ex [d(x")],
Ak.
(8)
where x denotes the stationary distribution of {**}. If the test function & is smooth, then we use Taylor expansion to obtain
((* = s0* - ad") = ,x*²) a ((Vo(==)
), dd) + 2
(V (ool"""dd d + O(a²).
Taking expectations both sides of the above equality and applying (8) have
E [(Vo(=*), d+* g (V )d dd)] = O
For an arbitrary smooth function Φ, Oaa²) term on the right-hand side. In addition, computing the Hessian- product (² can be very costly. Therefore, we only consider simple quadratic functions for which the (aa)) term in vanishes. In particular, the choice of ((x) = (1/2)][=]|| results in
very hard practice to characterize or approximate the
Ex [(* 2 [[] = 0.
(10)
This condition holds exactly for any stochastic optimization method of the form (6) if it reaches stationarity. Indeed, weak stationarity is sufficient since á is quadratic function of the state (e.g., Dembo 2013] Section 3.2.3). Beyond stationarity, requires no specific assumption on the loss function noise model for the stochastic gradients. Moreover, it can be applied to different methods without any change. We call this the master condition for stationarity.
Yaida 2018 focused on state perturbation along g A S (x** obtaín his "master equation"
E [dbaa* ogg*)] E, [d(a)))
4h.
This equation can be combined with the actual state update equation (6 to obtain more specific stationarity conditions for different algorithms. For example, for the stochastic heavy-ball method with d -1 f) + 3dk-1 the master equation leads to (aidaa 2018)
Ex (at (lttgg*) 1-
0.
(1I)
It simple exercise show that this is equivalent to our master condition (T).. For the QHM update (7). a more complex stationarity condition may also be derived, but it will still be equivalent (10p. In practice, the single, simple master condition [0) is much more preferred.
If {I*} starts with a nonstationary distribution and converges to a stationary state, we have lim E [(a d+) -/2 ||d O.
(12)
8-000
In the next section, we devise a simple statistical test to determine if the master condition fails to hold. In this case, the learning process has not stalled, and we can continue with the same step size. If we fail to detect non statiioiion (i.e., the dynamics may be approximately stationary), we would like to reduce the learning rate allow for finer convergence.
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1: SASA+: SASA with master condition and simple statistical testing
1 input: x² E RR, > 0, Mmin > 0, Krest > 0, 8 (0, 0 (0,1),TE (0,
2 f- ag
3 ko +-
4 for k 0,.,, T do
5
Randomly sample Ex and compute stochastic search direction d (e.g.. using QHM)
6
In+1 x² ad
7
As + ,,d,d 21
8
N [o(k- [oo]
9
if > Nuin and k mod Kiest = O then
(ĀN, NN) < sample mean and BM/OLBM variance of (Aa- - ,
11
0 E juN + 1/-8/2/N AN then
12
a c 70
13
ho k
end
15
end
16
end
17
output: x² (or the average of last epoch)
Table
List of hyperparameters of Algorithm
Parameter
Range
Explanation
Default value
Nmi
Z+
minimum number of samples for testing
1000, [n/b]}
Kestt
Z
period to perform statistical test (1-8)-confiden) interval
min(100, [n/b]]
(0,1)
0.01 (99% confidence)
1)
fraction of recent samples to keep (after reset)
1/4
(0,1)
learning rate drop factor
1/10
STATISTICAL TESTS OF (NON-)STATIONARITY
In order to test if the master condition
(0) holds approximately, we collect the simple statistics
A (x
- ||d (a++11 2 111
Here the second expression for Ag is obtained using the direct substitution *+1 = wtth - ad. which can be more convenient to implement A collected after the state updates to A+1
In the language of statistical hypothesis testing (e.g.. Lehmann & Romano, 2005), make null hypothesis that the dynamics (6) have reached stationary distribution т. we have N samples [Ak]. know from equation (O) and the Markov chain CLT (see its application in Jones et al. 20066) that as N - oo, under the null hypothesis the mean statistic follows normal distribution with mean 0 and variance /N.... Our alternative hypothesis is that the dynamics (6) have not reached stationarity. To test these hypotheses, adopt the classical confidence interval test. More specifically, we use the most recent samples (A--N-1...- A to compute the sample mean an and variance estimator o for o3. Then can form the (1 8) conofiiieeeee interval
ŌN
(ĀN WN, A.N + WN)
with half width
WN 8/-8/2 VN
(13)
where 1/-8/2 is the (1 5/2) quantile of the Student's L-distribution with degrees of freedom cor- responding to that in the variance estimator σ% Because the sequence {Ax-N+1:
Ax are
highly correlated due to the underlying Markov dynamics, the classical formula for the sample vari- ance (obtained by assuming i..d. samples) does not work for 8. We need to use more sophisticated batch mean (BM) overlapping batch mean (OLBM) variance estimators developed in the Markov chain Monte Carlo literature (c.g., Jones et al. 2006 Flegal & Jones 2010). See Lang et al. (2019) for detailed explanation. We also list the formulas for computing BM and OLBM in Appendix

---

Under review as a conference paper at ICLR 2020
Algorithm 2: Smoothed Stochastic Line-Search (SSLS)
1 input: xº E RR, a- > O, sufficient decrease coefficient E (0. 1/2), line-search factors
Pine 2 Pdec E (0, 1), smoothing parameter 7 E [0, 1] and maximum LS count m 2 for k = 0....,
do
3
Sample E.. compute g" t- VSee (z*) and search direction dl (e.g., using QHM)
4
Mi < -1-
5
while fex (x* magg > fea (a*) c- mTkll 11 and mu Pdoc Q do
6
- Pdectkk
7
end
8
OAk + (1 - -))xx-1 + Mh
9
I xht1 x² apd
10 end
11 output: x²
If the confidence interval in (13 contains O, we fail to reject the null hypothesis that the learning process is at stationarity, which means the learning rate should be decreased. Otherwise, we accept the alternative hypothesis of non-stationarity and keep using the current constant learning rate.
Stochastic optimization methods equipped with such an adaptation scheme belong to the gen- eral framework of SASA (Statistical Adaptive Stochastic Approximation) proposed by Lang et al. 2019 Algorithm| [ is our new variant called SASA+. Table lists its hyperparameters and their default values (where is total number of training examples and b is the mini-batch size).
Lang et al. (2019) focused on the stochastic heavy-ball method and devised a statistical test for the condition 11). Another major difference is that they set non-stationarity stationarity as the alternative hypothesis (opposite to ours). This leads to more complex "equiva- lence test" that requires an additional hyperparameter. Our test is simpler and more straightforward, and computationally as robust.
the null hypothesis and
4 SMOOTHED STOCHASTIC LINE SEARCH
SASA+ can automatically decrease the learning rate to refine the last phase the optimization process, but it relies an appropriate setting of the starting learning rate on for sufficient initial ex- ploration. The appropriate initial learning rate varies substantially for different objective functions, machine learning models, and training datasets, and setting it correctly without expensive trial and error is a major challenge for all stochastic gradicnt methods, adaptive or not.
Several recent works (e.g., Schmidt et al.) 2017; Vaswani al. 2019) explore the use of classical line-search techniques (e.g.) Nocedal Wright 2006 Chapter 3) for solving stochastic optimization problems with special structure. One of the main difficulties of applying line-search to stochastic optimization is that the estimated step sizes may vary a lot from step to step and it may not capture the appropriate step size for the average loss function. To overcome this difficulty, we propose smoothed stochastic line-search (SSLS) procedure listed in Algorithm 2
During each step k, SSLS uses the classical Armijo line-search find an appropriate step size mık for the randomly chosen function fe, (initialized by 1). then sets the overall learning rate to be
ag = (1 - 7)aa-11101-1 + 7Tk.
where 7 E [0, 1]. When ? 1, SSLS reduces to the stochastic Armijo line-search used by Vaswani al. (2019). A good choice to set 7 b/ //n where n the total number of training examples and 20 is accepted at step k then
b is the mini-batch size. Suppose Pinc = 2 and
a₁ (1 7) + 7 (2 - 1) (1 + 71
If this happens at every iteration over epoch (of [n/b] iterations) and > b, then
[x+[n/b]] = (1 + b/n) [n/b] ag x e ag.
(14)
Therefore, the most aggressive growth of the learning rate by a factor of e over one epoch. Such growing factor is reasonable for line search in deterministic optimization (e.g.. Nesterov 2013).
5

---

Under review as a conference paper at ICLR 2020
Algorithm 3: SALSA: SASA+ with warmup by SSLS
1 input: x² E RP, number of steps for warmup Twu and total number of steps T > T Tw
2 for l = 0, ..., Tw do
3 Run SSLS (Algorithm
4 end
5 for k = Twn I,...
T do Run SASA+ (Algorithm
6
7 end
8
output: x.
Setting 7 =Vb/n b/n leads to maximum growth of e² over one epoch. A similar smoothing effect holds for decreasing the learning rate well. The smoothing scheme allows us standard increasing and decreasing factors, such as Pine = 2 and Pdec 1/2. Without the smoothing scheme, Vaswani et al. (2019) set Pine = 2 to restrict dramatic growth of ag: The (equivalent to 7 = 1 in SSLS).
However, the decreasing of or = 7/a can be excessive and premature, even with prec 0.9.
Following the theoretical framework of Vaswani et al. (019), it may be possible to show that SSLS has similar convergence properties as stochastic Armijo line-search under the smooth and interpola- tion assumptions, which we leave as a future research project. In this paper, we are mainly interested in investigating its performance practice. In particular, we use it on deep neural network models with ReLU activations. Here the loss functions are non-smooth, and classical theoretical foundations for line-search do not carry over. Nevertheless, we found SSLS to have robust performance all of our experiments. In order to handle the case of potential non-descent directions in the non-smooth case, we exit the line search after a maximum of m tries by adding the condition 7/k > Pide Tlk for staying in the line-search loop. By default, we
10 together with Pdec
1/2.
Finally, we combine SASA+ with SSLS to form Algorithm 3 which we call SALSA (Stochastic Approximation with Line-search and Statistical Adaption). Without prior knowledge the loss function and training dataset, we start with a very small learning rate and use SSLS to gradually increase it to be around a stationary value that is (automatically) customized to the problem. The after Twn steps, we switch to SASA+ to gradually reduce the learning rate to settle down to a (hopefully good) local minimum. We typically set the number of warm-up steps Two be equivalent to few tens of epochs. According to the calculation in (I4). using 30 epochs would allow a potential growth factor up to a reasonable fraction of e00 which sufficient for most applications. We could avoid a warmup phase by running SASA+ and SLSS together until the first SASA+ drop, which could only come after SLSS had reached a relatively stable value for ag, allowing the dynamics to approach stationarity. However, we use a fixed warmup phase Twu in our experiments for simplicity.
Computational cost of SSLS. When we fix the number of training epochs, the wall-clock time of Smoothed Stochastic Line Search (SSLS) is about 1.5 times of that of the plain stochastic optimiza- tion algorithm. This 0.5 computational overhead is due to 2 function evaluations in each line search step on average. Notice that the function evaluation is on the same minibatch and line search only needs the function value without gradient. In SALSA, we switch from SSLS to SALSA at one-third of the total training epochs. Therefore, the total computational overhead caused by using SSLS only 0.15 of the original total training time.
EXPERIMENTS
We evaluate the performance of SASA+ (Algorithm D. SSLS (Algorithm 2 and SALSA (Algo- rithm 3) by conducting several experiments on two common deep learning datasets. We compare SALSA to the following baselines: SGD with a hand sund-dtundddd constant-and -nn-cuut learning rate schedule and Adam with tuned warmup phase (e.g..) Wilson et al. [017 Lang et al. 2019). We also compare SASA+ to the original SASA from Lang et al. (2019). We use weight decay in all experiments.
We use the default values in Table 1 for hyperparameters.

---

Under review as a conference paper at ICLR 2020
95
95
Global learning rate
Training Loss
1.0
1.0
10-1
10-1
Tast Accurgo
90
0.5
0.5
85
85
10-3
10-1
0.0
0.0
80
80
100
150
100
150
0
100
Epoch
Epoch
Epoch
Figure 1: Comparison of different optimizers on CIFAR-I0. All SASA, SASA+ and SALSA are using SGD with momentum 0.9. SALSA starts from small initial learning rate 0.01 while other methods starts from an oracle maximal learning rate 1.0. SALSA witches from SSLS to SASA+ at epoch 40.
We trained an 18-layer ResNet model (He et al. 2016 on CIFAR-10 10 (Krizhevsky & Hinton 2009) with random cropping and random horizontal flipping for data augmentation and weight decay 0.0005. Row of Figure [ compares the best performance of each method. Here SGM-hand uses ag 1.0 and
CIFAR-10
0.9 and drops a by a factor of 10 every 50 epochs. Adam has tuned global learning rate ogg and a "warmup" phase of 50 epochs. With only a tuned og = Le (the optimal value in our grid search of {le 5, 1e 1e 1e 2]). Adam is only able reach around 93% test accuracy for this model. On the other hand, both SASA+ and SALSA are able to reach similar performance with the hand-tuned SGD. While other methods starts from an oracle maximal learning rate 1.0, SALSA starts from a small initial learning rate 0.01. The SSLS in the first stage of SALSA able to gradually grow the learning rate to a maximal value and then switches to SASA+ in the second stage.
Figure 2 shows the evolution of SASA+'s different statistics over the course of training the ResNet18 model on CIFAR-10 10 using the default parameters in Table I Between two jumps, the statistics Ak decays toward zero. As long as its confidence interval (13) does not overlap with 0, we are confident that the process is not stationary yet and keep exploring with the current learning rate. Otherwise, we decrease the learning rate and enter another cycle of approaching stationarity.
We give experiments that demonstrate the sensitivity of SASA+ to values around its defaults in 3 The top row shows that SASA+ is robust to the choice of the dropping factor т. The larger the + is, the longer the process will stay between two drops, which can be also seen in Figure The middle row shows the effect of statistical parameter 8. Smaller ó leads to wider confidence interval, and makes easier and thus earlier to fire the statistical test. The bottom row shows the effect of 0, the fractions of samples to keep after reset. Smaller 0 values lead to more frequent dropping, but do not seem to impact the final performance.
Figure 4 shows the dynamics of SSLS and SALSA. In the upper row, SLSS increases the learning rate in the initial phase, and then reaches a stable learning rate once the increases and decrease balance out. With enough momentum (QHM 3 v 0.9), the SSLS can further decrease the learning rate automatically and achieve good training and testing performance. However, without momentum (SGD), the stable learning rate gets too large, and its optimization performance is bad, but the process is still stable and the learning rate does not blow up. In the lower row, SALSA switches from SSLS to SASA+ when it reaches the maximal learning rate. Then even in the case without momentum, SASA+ still works and finally gets as good performance as best hand-tuning SGD. This shows that the SSLS is able approximate the best hand-tuned maximal learning rate, and the combination of SSLS and SASA+ + is necessary to get final good optimization performance.
ImageNet We also test our algorithms on the large scale ImageNet dataset (Deng et al. 2009). We use the ResNet18 architecture, random cropping and random horizontal flipping for data aug- mentation and weight decay 0.0001. Row of Figure 5 compares the performance of the dif- ferent optimizers. Even with tuned ao = le (the optimal value in our grid search of {le 1e le le 1}) and allowed to have a long warmup phase (30 epochs), Adam failed to match the generalization performance of SGM. On the other hand, both SASA+ and SALSA were able to match the performance of hand-tumed SGM using the default values of its parameters. Although both SASA+ and SALSA are using the NAG (equivalent QHM (7) with B = 0.9),
7

---

Under review as a conference paper at ICLR 2020
0.6
0.6
of, 1f
Statistics of df
0.6
0.4
BM
OLBM
d 0.2
Jiy Sty
STD
0.2
0.0
0.0
0.0
100 Epoch
150
200
100
150
100
150
200
Epoch
Epoch
Statistics bf
0.4
BM
-8
0.5
0.5
Jiy GaV
STD dn
018M
0.0
100
200
100
200
500
100
150
200
Epech
Epoch
Epech
Figure 2: Statistics used in SASA+. Upper row: drop ratio 7 1/2: lower row: T = 1/10. The left column shows the instantaneous value of A.- The middle column shows the confidence interval of E constructed by SASA+, which should contain with high probability if the process is stationary. The right column shows the variance estimated by different methods, where BM and OLBM takes into the consideration of correlation in Markov chains and are more accurate.
1.00
Training loes
== 1/2
Learing rate
10a
t 1/2
0.75
T 1/5
Tast accuracy
90
0.50
== 1/10
80
== 1/2
10
1/10
== 1/5
0.25
70
- 1/10
10:2
0.00
60
100
1.5
200
50
100
150
200
50
100 Epoch
150
200
Epoch
Epoch
1.00
Test accuracy (9)
100
Training loes
0.75
0.1
0.01
90
Learinng rale
10a
6 0.1
0.01
0.50
6 0.001
80
6 0.1
10-1.
0.001
8=0.
0.25
70
0.001
0.00
60
10
100
150
200
50
100
150
200
50
100
150
200
Epoch
Epoch
Epoch
Training loes
- 1/2
Leariing rate
10a
0.75
= 1/4
Tast accuracy
90
0.50
m 1/8
80
8- 1/2
10-1
8
0= 1/4
0.25
700
0= 1/8
0.00
60
10-2
50
100
150
200
50
100
150
200
50
100
150
200
Epoch
Epoch
Epoch
Figure 3: Sensitivity analysis of SASA+ on CIFARIO, using 0.9 and v The training loss, test accuracy, and learning rate schedule for SASA+ using different values of 7 (top row), 5 (middle row), and (bottom row) around the default values are shown.
they start with different initial learning rates and have quite different dynamics. SASA+(Nag) starts with an initial learning rate of 1.0, while the SALSA(Nag) starts with a small learning rate 0.1 and automatically determines the appropriate largest learning rate by using SSLS. As consequence, SASA+Naa) reaches a stationary state much faster. Nevertheless, their final performances are nearly the same, with SALSA(Nag) even slightly higher.
8

---

Under review as a conference paper at ICLR 2020
1.5
TTss accuracy (9)
100
10'
Learning rats
1.0
80
10
SGD y
Training
SGD y-005-5 5.05
60
SG22
OHEM
0.05
10-1
0EM y 0.05
3.0025
0.5
SGD y- 5.0225
0025
011 y 0.0025
gENN 0.05
QUIN y 0.0023
10-2
0.0
20
50
100
200
100
200
100 150
200
Epoch
Epoch
Epoch
1.5
SGD y- 0.05
Test accuracy (%)
100
107
SGD y 5.05
Truining loss
1.0
GEK y- 0.05
5GD ym 0025
80
Leariing rate
10
QBM 0.05
5r1p ym 0.00p5
QEI 0.0025
QBM 0.0025
60
5CD
10
40
10-2
50
100
150
200
20-
0
50
100
150
200
50
100
150
200
Epoch
Epoch
Epoch
Figure 4: First row: SSLS. Second row: SALSA (warmup 40 epochs). Here, SGD with 3 0.0 and QHM with parameters 3 = 0.9 and v = 0.9. SSLS is able to find a balance between increasing and decreasing learning rate, and results in a stable large learning rate (SGD) or further decreases the learning rate (QHM). In either case, switching to SASA+ (the lower row) gets good final performance.
Row 2 of Figure 5 shows that SASA+ is simple and general enough to work with different stochas- tic optimization methods with constant hyperparameters, i.c., SGM with 3 = 0.9, NAG, and the recommended QHM setting (3 0.999 and // 0.7). The dotted curves show the performance of these methods with the best hand-tuned constant-and-cut learning rate schedule. The solid lines show the automatic tuning by SASA+, which learns faster and finally achieves similar performance.
Figure shows the sensitivity analysis of SSLS. From the left and middle panels, we can see that the SSLS always converges to large learning rate (1.806 this case), which is comparable with the best human-chosen value of 1.0. The right panel shows that the larger the sufficient descent constant e is, the smaller the maximal learning rate is and the slower SSLS reaches to its maximal learning rate. This is intuitive because larger puts more limits the SSLS to grow the learning rate. Moreover, within 60 epochs, SSLS never decreases the learning rate again once it achieves a large stable learning rate, so it is necessary to switch SASA+ after SL.SS reaches stable learning rate.
CONCLUSIONS
We presented SASA+, a simpler yet more powerful variant of the statistical adaptive stochastic ap- proximation (SASA) method proposed by Lang et al.) (201)). SASA+ is equipped with single statistical test for (non-)stationarity that works for a broad family of stochastic optimization meth- ods without modification. This greatly simplifies its implementation and deployment in software packages. While SASA+ focuses on how to automatically reducing the learning rate to obtain bet- ter asymptotic convergence, we also propose a smoothed stochastic line-search method (SSLS) to warm up the optimization process, thus removing the burden of expensive trial and error for setting a good initial learning rate. The combined algorithm, SALSA, highly autonomous and robust over variations of its hyperparameters. Using the same default setting, SALSA obtained state-of-the- performance on several common deep learning models that is competitive with the best optimizers.
REFERENCES
Atilim Günes Baydin, Robert Comish, David Martínez Rubio, Mark Schmidt, and Frank Wood. On- line learning rate adaptation with hypergradient descent. In Proceedings of the Sixth International Conference Learning Representations (ICLR), Vancouver, Canada, 2018.

---

Under review as a conference paper at ICLR 2020
Test Acouracy (%)
70
700
Giobal leamiin rale
Treining Loss
alam
10-1
10-1
60
-60
(NAC+
(MAsa(NAG)
50
50
10-3
10:
40
50
100
100
0
50
100
Fpoch
Epoch
Epoch
Training Loss
s - 0.9
Tost, Accurracy (%
70
109
10c
Ginibal loarning
10-1
10
4-
(oged (.0)
0.0)
4
50
10
10-2
40
</y
10-3
10-1
50 Epoch
100
Fpoch 100
100
Epoch
SGD with momentum 0.9, while SASA+ and SALSA use NAG (QHM with 3 = v 0.9). SALSA starts from small initial learning rate 0.1 while other methods starts from an oracle maximal learning rate 1.0. SALSA witches from SSLS to SASA+ at epoch 40. Lower: the first three curves are stochastic optimization algorithms with hand-tuning learning rate, i.e., decrease every 30 epochs as it is shown in the lower right panel. The last three curves are SASA+ combined with these 3 algorithms. SASA+ automatically adapt their learning rate (see the lower right panel), achieves comparable and even slightly higher testing accuracy (see the lower middle panel).
Figure 5: Upper: Comparison of different optimizers on ImageNet. All SASA
Global learning rate
10
10a
10
10
10
10a
c=0.]
10"
100
10
10"
10a
2=02
10-1
10-1
10-1
10-1
10-1
10-1
10-2
0.01
10-2
10-2
Y- 20
10-2
10-2
0=0.0
10-3
10-3
10-3
10-3
10-3
20
40
60
0
20
40
60
0
20
40
60
Epach
kpoch
Hpoch
Figure 6: Sensitivity analysis of SSLS around ag = 0.01, = b/n 0.0002, = 0.1, with SGD 0.9, v 1 on ImageNet.
Léon Bottou. Online algorithms and stochastic approximations. In David Saad (ed.), Online Learning and Newral Networks. Cambridge University Press, Cambridge, UK, 1998. URL www.oott...oooo.ooooeoeoooo..... wtt.://w.....ppppppp/oooooooooo. 98x Revised, Oct 2012.
B. Delyon and A. Juditsky. Accelerated stochastic approximation. SIAM Journal Optimization, 3(4):868-881, 1993.
Amir Dembo. Stochastic Processes. Lecture notes, Stanford University, 2013.
J. Deng. W. Dong, R. Socher, L.-.. Li. K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(u1))2121-2159, 201
James Flegal and Galin Jones. Batch means and spectral variance estimators markov chain monte carlo. The Annals of Statistics, (114))0034-17000 2010.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role momentum in stochastic gradient methods. In Advances in Neural Information Processing Systems, volume 32, 2019.
10

---

Under review as a conference paper at ICLR 2020
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http: 7/www dwwpleeannnggboooee ozq
A. M. Gupal and L. T. Bazhenov. A stochastic analog of the conjugate gradient method. Cybernetics, 8(1):138 (10, 1972.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual networks for image recog- nition. In Proceedgins of the 29th IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
R. A. Jacobs. Increased rates of convergence through learning rate adaption. Neural Networks, 1: 295-307, 1988.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerat- ing stochastic gradient descent for least squares regression. In Conference On Learning Theory, pp. 545-604, 2018.
Galin L Jones, Murali Haran, Brian S Caffo, and Ronald Neath. Fixed-width output analysis for markov chain monte carlo. Journal of the American Statistical Association, 1037477) 2006.
Harry Kesten. Accelerated stochastic approximation. Annals of Mathematical Statistics, 29(1): 41-59, 1958.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Hunter Lang, Pengchuan Zhang, and Lin Xiao. Using statistics to automate stochastic optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
Erich L. Lehmann and Joseph P. Romano. Testing Statistical Hypotheses. Springer, 3rd edition, 2005.
Jerry Ma and Denis Yarats. Quasi-hyperbolli momentum and adam for deep learning. In Interna- fional Conference on Learning Representations, 2019.
Ashique Rupam Mahmood, Richard S. Sutton, Thomas Degris, and Patrick M. Pilarski. Tuning-free step-size adaption. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2121-2124, 2012.
Mirzoakhmedov and S. P. Uryasev. Adaptive step adjustment for stochastic optimization algo- rithm. Zh. Vychisl. Mat. Mat. Fiz, 23(6):1314-135) 1983. [U.S.S.R. Comput. Math. Math. Phys. 23:6, 1983].
Y. Nesterov. Gradient methods for minimizing composite objective function. Mathematical Pro- gramming, Series B, 140:125-161 2013.
Yurii Nesterov. Introductory Lecture Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, 2nd edition, 2006.
Georg Ch. Pflug. On the determination of the step size in stochastic quasigradient methods. Col- laborative Paper CP-83-025, International Institute for Applied Systems Analysis (IIASA), Lax- enburg, Austria, 1983.
Georg Ch. Pflug. Adaptive stepsize control in stochastic approximation algorithms. In Proceedings of 8th IFAC Symposium on Identification and System Parameter Estimation, pp. 787-792, Beijing, 1988.
Georg Ch. Pflug. Non-asymptotic confidence bounds for stochastic approximation algorithms with constant step size. Monatshefte für Mathematik, 110:297-314, 1990.
11

---

Under review as a conference paper at ICLR 2020
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Com- putational Mathematicss and Mathematical Physics, 4(5):1-17, 1964.
Boris T. Polyak. Comparison of the rates of convergence of one-step and multi-step optimization algorithms in the presence of noise. Engineering Cybernetics, 15:6-10, 1977.
Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging.
SIAM Journal on Control and Optimization, 30(4))838 -858858, 1992.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathemat- ical Statistics, 22(3):400-407, 1951.
Andrzej Ruszczyóski and Wojciech Syski. Stochastic approximation method with gradient averag- ing for unconstrained problems. IEEE Transactions on Automatic Control, 28(12) 1097-11055 1983.
Andrzej Ruszczyúski and Wojciech Syski. Stochastic approximation algorithm with gradient aver- aging and on-line stepsize rules. In Gertler and Keviczky (eds.), Proceedings of 9th IFAC World Congress, pp. 1023-1027, Budapest, Hungary, 1984.
Andrzej Ruszczyúski and Wojeiech Syski. On convergence of the stochastic subgradient method with on-line stepsize rules. Journal of Mathematical Analysis and Applications, 114:512-527, 1986a.
Andrzej Ruszczyúski and Wojeiech Syski. A method of aggregate stochastic subgradients with on-line stepsize rules for convex stochastic programming problems. Mathematical Programming Study, 28:1 1-1,,,11111111 1986b.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):33-112, 2017.
Nicol N. Schraudolph. Locaa gain adaptation in stochastic gradient descent. In Proceedings of Nineth International Conference on Artificial Neural Networks (ICANN), pp. 569-574, 1999.
David L Streiner. Unicorns do exist: A tutorial on proving the null hypothesis. The Canadian Journal of Psychiatry, 48(11):756-761 2003.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In Sanjoy Dasgupta and David McAllester (eds.), Pro- ceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 1139-1147, Atlanta, Georgia, USA, 17-19 Jun 2013, PMLR. In
Richard S. Sutton. Adapting bias by gradient descent: An incremental version of Delta-Bar Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI'92), pp. 171-176. The MIT Press, 1992.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26- 31, 2012.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julian. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Ad- vances in Neural Information Processing Systems, volume 32, 2019.
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. 4148 4158, 2017.
Sho Yaida. cnncuuation-disspaatin relations for stochastic gradient descent. arXiv preprint arXiv:1810.00004, 2018
12

---

Under review as a conference paper at ICLR 2020
A MCMC VARIANCE ESTIMATORS
Several estimators for the asymptotic variance of the history-average estimator of a Markov chain have appeared in work on Markov Chain Monte Carlo (MCMC). Joness al. (2006) gives nice example of such results. Here we simply list two common variance estimators, and we refer the reader that work and Lang et al. (2019) (from which we borrow notation) for appropriate context and formality.
Batch means variance estimator. Let En be the history average estimator with N samples, that is, given samples } from a Markov chain, nN N Σ i= Now form batches from the N (j+1)g11 for each batch j. Then
samples, each of size q. Compute the "batch means" 전 Σ L==ja compute the batch means estimator using:
2 N
2N)²
(15)
The estimator is just the variance of the batch means around the history average ËN. This statistic has p degrees of freedom. As in Jones et al. (0066) and Lang al. (2019), we take p = q = /N when using this estimator.
Overlapping batch means variance estimator. The overlapping batch means (OLBM) estimator Flegal & Jones (2010) has better asymptotic variance than the batch means estimator. The OLBM estimator is conceptually the same, but it uses N p+ overlapping batches of size (rather than disjoint batches) and has N p degrees of freedom. It can be computed as:
N-P
Np
Σ
[ēN
354))²
(16)
N
P)NN
1=0
B THE STATISTICAL TESTS IN SASA AND SASA+
As mentioned in our contributions, there are two main differences between SASA from Lang el al. (2019) and SASA+. First, SASA+ has a much more general "master stationary condition" (10). so can be applied to any stochastic optimization method with constant hyperparameters (e.g.. SGD, stochastic heavy-ball, NAG, QHM, etc.), while the stationary condition in Yaida (2018) and SASA proposed in Lang et al. (2019) (see Equation ITI) only applies to the stochastic heavy-ball method. Second, the statistical tests used in SASA and SASA+ are quite different, as we claborate below.
The difference starts from conceptual change from SASA SASA+. In SASA, one wants con- fidently detect stationarity. If stationarity detected, one decreases the learning rate, and otherwise keeps it the same. In SASA+, detected, one keeps the learning rate the same, and otherwise decreases. This conceptual change leads to simpler and more rigorous statistical test in SASA+.
wants to confidently detect non-stationarity. If non-statinn
B. EQUIVALENCE TEST SASA
To confidently detect stationarity, SASA has set non-stationarity null hypothesis and stationar- ity as the alternative hypothesis. one confidently rejects the null (non-stationaritty) then one can be confident that the process is stationarity. Instead of detecting stationarity, SASA simplifies to only detect the necessary but not sufficient stationarity condition (II). Formally, the test in SASA is
(17) where samples of A, i.e., A. (1t d+* I| 12 are collected along the training process. This kind of test called an equivalence test in statistics, see, e.g., eg../Streiner/ (200).. There is no power" in the equivalence test (17), i.e., one cannot confidently reject the null hypothesis and prove stationarity
Ho : E|A] + 0 vs. H1 E[A] = O,
In statistical hypothesis testing, power the ability to reject the null hypothesis when it is false.
13

---

Under review as a conference paper at ICLR 2020
at all! Intuitively, even when the process is stationary, with only finite number of (noisy) samples {Ax N; k== the sample mean AN * (with probability onc) is always more likely to be the true mean than the singleton O. In other words, one can not deny that the process probably infinitely close to stationary but still non-stationary.
To gain power in the equivalence test, one needs to use domain knowledge to define an equivalence interval. Formally, the true test in SASA is
Ho [[A]| > ÇV vs. H1 E[A] E (u),,
(18)
where ÇV/ is the equivalence interval. In English, instead of the usual null hypothesis of not-equal-to- zero in . now the null hypothesis is not-equal-to-zz to-zeoo by a margin Çv. In this case, when E A confidence interval is contained in the equivalence interval, i.e.,
ON AN 8-6/2
AN + 1-6/2
c Cl-CON. (Tx).
(19)
VN
we are confident to reject the null hypothesis and to prove/accept Hi (the stationary condition is met within an error tolerance). This exactly the test in SASA Lang et al. (2019), see its Equation (10). However, this equivalence test requires estimation of Ex (that estimates the magnitude of A) and an additional hyperparameter that controls the equivalence interval width, In SASA's notation, the equivalence width is denoted by 5.
Moreover, SASA makes the unjustified assumption that under their null hypothesis (Ho [|A] > (v), the Markov central limit theorem holds. Under their Ho. the process is non-stationary, while the construction of E[A]'s confidence interval in Eqn. (1) relies on the (asymptotic) stationarity of the Markov process. Therefore, despite the empirical success of SASA, its statistical test is intrinsically flawed because of this testing setup.
B.2 STANDARD TEST IN SASA+
In SASA+, want to confidently detect non-stationarity. If non-stationarity detected, one keeps the learning rate the same, and otherwise one decreases it. This conceptual change naturally removes the complication of the equivalence test and the intrinsic flaw in SASA.
To confidently detect non-stationarity, SASA+ sets stationarity as the null hypothesis and non- stationarity as the alternative:
Ho The process is staionary Hi The process is staionary.
(20)
The master stationary condition E[A] 0 is necessary condition for stationary of the process, and thus confidently rejecting E| = 0 is sufficient to confidently reject the null (stationarity) hypoth- esis. Moreover, under this null hypothesis, the Central Limit Theorem of Markov Processes exactly holds true (because the process is stationary). validating the construction of EjA] confidence in- terval. Therefore, the intrinsic flaw in SASA naturally solved in SASA+.
Now we describe the test in SASA+. When the confidence interval of E E[A] does not contain 0, i.e.,
0 E
An - 8/2
θN A
+
1 8/2
NN VN
(21)
then we reject the null (stationary) hypothesis and keep the learning rate the same. Otherwise, we decrease the learning rate. Notice that there is no additional hyperparameter Ç.
B.3 THE DIFFERENCE IN PRACTICE
Although SASA and SASA+ are conceptually quite different, they both use the same confidence interval (see 199 and 21 for E E] In practice, their difference illustrated in Figure 7 Their difference lies in Case (2) and (3). In Case (3), the process has not reached stationarity yet with high probability, according to the confidence interval E A (Red). SASA+'s 's test is confident to reject its (stationary) null hypothesis, learning rate because it is confident that the stationary condition holds true within its error tolerance (equivalence interval). In this case, SASA makes emror due to its relatively large equivalence
it keeps the learning rate the same. However, SASA decreases its
14

---

Under review as a conference paper at ICLR 2020
(1)
(2)
(3)
(4)
Equivalence
Confidence
Interval [-3v, [v]
Interval E[A]
Figure 7: Statistical tests in SASA and SASA+. Case (1): both SASA and SASA+ keep the learning rate. Case (4): both SASA and SASA+ decrease the learning rate. Case (2): SASA keeps the learning rate while SASA+ decreases. Case (3): SASA decreases the learning rate while SASA+ keeps.
interval. In Case (2), SASA+'s test is not confident to reject its (stationary) null hypothesis and it decreases its learning rate. On the contrary, SASA's test is not confident to claim that the stationary condition holds true within its error tolerance and thus keeps its learning rate. In this sense, SASA+ is more aggressive than SASA in decreasing learning rate.
In numerical experiments the CIFARIO and ImageNet datasets, the (width of) the equivalence interval Çv is typically much smaller than the (width of) the confidence interval of E A] see Figure 5(a), 7(a) and (a) in Lang al. (2019). Notice that in those figures, the yellow curve of Çv, and thus the equivalence interval is even smaller. Therefore, Case (3) happens very rarely in those experiments, and this explains the reason why SASA does not make obvious mistakes in decreasing the learning rate. In practice, Case (2) sometimes happens, and thus we can see that SASA+ seems to be slightly more aggressive at decreasing the learning rate than SASA. For example in Figure [ the black curve (SASA+) is faster at decreasing the learning rate than the green curve (SASA).
instead
15


Reviews:
[{"review_id": "SJlnmoD2Yr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors explore how stationarity tests can be leveraged to automatically tune the learning rate during training. Their algorithm also add a robust line search algorithm, to reduce the need to tune the initial learning rate. The paper is clear and the literature review is honest and thorough. However, it is unclear to me if the contribution of the authors is enough, as the method used and its presentation are very close to Lang and al. In particular:\n\n- First bullet point on page 2: Because of its conceptual and analytical simplicity, it greatly simplifies implementation and deployment in software packages. It is unclear why the approach proposed by Lang is more complicated to use\n- It is a recurrent theme in the paper that the proposed method is a simple interval test compared to a more complicated equivalence test in Lang et al. It is unclear to me what the authors mean by that, as pages 5 and 6 of Lang clearly details a confidence interval test too.\n- If SASA+ is indeed just a new presentation of the algorithm detailed by Lang, the line search contribution does not justify a paper in my opinion\n- In page 5, \"Another major difference is that they set non-stationarity as the null hypothesis and stationarity as the alternative hypothesis (opposite to ours).\" I am not sure how the authors arrived to the conclusion that non-stationarity was the null hypothesis in Lang and would appreciate some clarifications on this point. The test used in SASA is a simple t test with a variance corrected to account for the auto-correlation of the gradients.\n\nAbout the empirical work:\n\n- The experiments seems plausible. Hyper parameters were search for fairly for the competing methods. Adam could have benefited from a finer learning rate schedule, as it is only decreased once compared to several time for the SGD. I would indeed expect a performance gap between Adam and SGD, but I think most of it in this case comes from the one step schedule.\n- Line search is performed but no metrics were shown to discuss the computational overhead of evaluating the model and its gradients for different parameters during the search.\n\nSALSA appears to be an already existing algorithm on which a line search was plugged in. The line search part, which appears to be the only contribution, is not discussed enough in my opinion (in terms of computation cost for instance)\n\nTo conclude, I think the presented work is too close to the existing literature and that the progress made is very incremental.\n\nEDIT after rebuttal: My concerns have been addressed, I revise my rating from weak reject to weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByxuWGXCKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a heuristic method for selecting learning rate schedules for momentum-type methods and evaluates the proposed method on two image classification benchmarks including CIFAR10 and ImageNet. Statistical tests are presented to check the stationarity of the gradient updates. And stochastic line-search methods are proposed to warm up the optimization process during early phases.\n\nPros:\n\nThe main idea is to check the non-stationarity of the iterates and decrease the learning rate if stationarity is detected. To check stationarity, a quadratic approximation for the objective is used. Another procedure for how to decrease the learning rate is proposed using a stochastic line search. The idea makes sense to me.\n\nCons:\n\n-- The quadratic approximation simply assumes that the Hessian matrix of the objective is identity (Equation 10 in Section 2). I appreciate the simplicity of this formulation. Indeed quadratic forms are good local approximations for any general function. On the other hand, it is quite possible that the Hessian matrix has a low-rank structure or has a sharply decaying spectrum. This kind of scenario naturally arise in high-dimensional settings where the model has lots of parameters. Therefore, it seems to me that further justification (either empirical or theoretical) could help clarify the intuition better.\n\n-- The experimental results compare the proposed method to other well-known methods such as SGD and ADAM. From Figure 1 and Figure 5, it seems that the proposed method performs comparatively to both SGD and ADAM. In particular, it is not obvious from the experimental results that there is a huge benefit obtained from the proposed methods. Hence the experimental results seem a bit incremental to me, as far as I can tell.\n\nMore comments:\n-- Notation: using $\\xi$ to denote the data points seems a bit unconventional.\n-- Typos: \"Pflug also a devised\" -> \"Pflug also devised\".\n-- The current version is significantly over length (by more than 1 page).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "BkxTCIPAuH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new way of automatically scheduling the learning rate in stochastic optimization algorithms: Stochastic Approximation with Line-search and Statistical Adaptation (SALSA).\nBy first introducing a necessary condition for stationarity, the authors use this condition to make a simple statistical test for non-stationarity. Using this test, the authors propose the following strategy for the learning rate schedule in stochastic optimization problems:\n(1) They first apply a new Line-Search algorithm (Smoothed Stochastic Line-Search - SSLS) to increase a small initial learning rate until the process becomes stationary according to their statistical test. At this stage, the learning rate is assumed to be optimally initialized for the objective function considered.\n(2) The second step is to decrease the learning rate gradually every time the process is stationary again. For this, the authors derived their own version of a Statistical Adaptive Stochastic Approximation algorithm called SASA+ based on their statistical test.\nThe resulting strategy benefits from being simpler than previous statistical tests while being equally effective empirically.\nThe authors empirically demonstrated that their new learning rate scheduling mechanism achieves comparable, if not better, accuracy on two image classification tasks with ResNet-18 neural networks. It is important to note that the compared baselines got their parameters slightly fine-tuned, while (according to the authors) the proposed approach was not fine-tuned, and only the default parameters were used. This shows the robustness of the proposed approach against its various parameter settings.\n\nI would accept this submission because the authors propose a new learning rate scheduling mechanism that seems to perform well empirically while being robust against its different initial parameter settings (including the choice of the initial learning rate).\n\nThis paper has several novelties: first, it proposes a simpler, yet as effective as previous approaches, Statistical Adaptive Stochastic Approximation (SASA) algorithm based on a new statistical test for non-stationarity. Second, it manages to relax the dependence of SASA algorithms on their optimal initial learning rate by introducing a Smoothed Stochastic Line Search (SSLS) algorithm that is responsible for finding such an optimal initial learning rate. Combined together, these two sub-routine provide a robust mechanism to schedule the learning rate in stochastic optimization problems.\n\nOne improvement I could suggest to better motivate the proposed approach is to experiment it not only on Convolutional-based networks with image classification tasks but also on Recurrent-based networks with text datasets. For instance, keeping the ImageNet experiments, the CIFAR-10 experiments could be replaced by an NLP task. This would show that the proposed approach is robust to different types of deep learning problems.\n\nOverall I found the paper well written, and relatively easy to follow, even for non-theoretical practitioners. A few details listed below could improve even more the quality of this paper:\n- At the top of page 2, the last sentence of the top paragraph (\"However, these learning rate schedules are insufficient ...\") requires a citation.\n- In Figure 5: it is a little confusing to have the SASA+(NAG) algorithm in both rows: once in the top row, twice in the bottom row. The difference between the two SASA+(NAG) in the bottom row is well explained, but is there any difference between SASA+(NAG) in the top row and the ones in the bottom row?\n- In Figure 5 - bottom row, left graph: if all lines are SASA+ algorithm, the legend should be consistent: either add \"sasa+\" to all lines or remove it from all lines.\n- On page 9, ImageNet paragraph: a small typo: \"On the other hand, both both SASA+ and SALSA...\".", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an approach to automatically tune the learning rate by using a statistical test that detects the stationarity of the learning dynamics. It also proposes a robust line search algorithm to reduce the need to tune the initial learning rate. The statistical test uses a test function which is taken to be a quadratic function in the paper for simplicity, although any choice of test function is valid. Although the method itself is interesting, the empirical benefits over SGD/ADAM seem to be minor. 

Decision: Reject