Year: 2019

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 statistical test apply 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.

heading: 1 INTRODUCTION
text: We study adaptive stochastic optimization methods in the context of large-scale machine learning. Specifically, we consider the stochastic optimization problem
minimize x∈Rp
F (x) , Eξ [ fξ(x) ] , (1)
where ξ is a random variable representing data sampled from some (unknown) probability distribution, x ∈ Rp represents the parameters of the machine learning model (e.g., the weight matrices in a neural network), and fξ is the loss function associated with data ξ. The objective function F is the expectation of fξ over the distribution of the data.
Many stochastic optimization methods for solving problem (1) can be written in the form of
xk+1 = xk − αkdk, (2) where dk is a (stochastic) search direction and αk > 0 is the step size or learning rate. In the classical stochastic gradient descent (SGD) method,
dk = gk , ∇fξk(xk), (3) where ξk is a training example (or a mini-batch of examples) randomly generated at iteration k. This method traces back to the seminal work of Robbins & Monro (1951), and it has become very popular in machine learning (e.g., Bottou, 1998; Goodfellow et al., 2016). Many modifications of SGD aim to improve its theoretical and practical performance. For example, Gupal & Bazhenov (1972) studied a stochastic analog of the heavy-ball method (Polyak, 1964), where
dk = (1− βk)gk + βkdk−1, (4) and βk ∈ [0, 1) is the momentum coefficient. Sutskever et al. (2013) proposed to use a stochastic variant of Nesterov’s accelerated gradient method (Nesterov, 2004), where
dk = ∇fξk(xk − αkβkdk−1) + βkdk−1. (5) Other recent variants include, e.g., Jain et al. (2018) and Ma & Yarats (2019).
Theoretical conditions for the asymptotic convergence of SGD are well studied, and they mostly focus on polynomially decaying learning rates of the form αk = a/(b + k)c for some a, b > 0
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, 1977). 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 on the fly have been developed in both the stochastic optimization literature (e.g., Kesten, 1958; Mirzoakhmedov & Uryasev, 1983; Ruszczyń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 et al., 2018). More recently, adaptive algorithms that use diagonal scaling—replacing αk in (2) with an adjustable diagonal matrix—have become very popular (Duchi et al., 2011; 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). Pflug (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. Pflug (1983; 1990) also devised a sequential statistical test to detect stationarity; when the test fires, the step size is decreased by a constant factor. Ruszczyński & Syski (1983) 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-dissipation 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 a more rigorous statistical test for Yaida’s conditions and obtained robust and competitive performance on common deep learning tasks.
Our contributions in this paper are threefold:
• 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 necessary condition (than Yaida’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 analytical 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 a simple statistical test for checking stationarity based on 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 et al. (2019). 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 to 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 a highly autonomous algorithm called SALSA (Stochastic Approximation with Line-search and Statistical Adaptation). We conduct extensive experiments on several deep learning tasks to test its training and testing perfromance as 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.

heading: 2 NECESSARY CONDITIONS FOR STATIONARITY
text: We consider general stochastic optimization methods in the form of (2) with a constant learning rate: xk+1 = xk − αdk. (6)
We assume that the stochastic search direction dk 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-Hyperbolic Momentum (QHM) methods (Ma & Yarats, 2019):
hk = (1− β)gk + βhk−1, dk = (1− ν)gk + νhk,
(7)
where 0 ≤ β < 1 and 0 ≤ ν ≤ 1. With β = 0 or ν = 0, it recovers the SGD direction (3). With ν = 1, it recovers the stochastic heavy-ball direction (4). With 0 < β = ν < 1, it is equivalent to the direction with Nesterov momentum given in (5) (Sutskever et al., 2013; Gitman et al., 2019). We assume that the dynamics of (6), e.g., driven by the stochastic gradients gk through (7), is stable. Stability regions of the hyperparameters in QHM are characterized by Gitman et al. (2019).
In addition, we assume that the stochastic process {xk}, as k → ∞, becomes stationary. Recall that {xk} 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 a direct consequence, for any deterministic function φ : Rp → R, we have
Eπ [ φ(xk+1) ] = Eπ [ φ(xk) ] , ∀ k, (8)
where π denotes the stationary distribution of {xk}. If the test function φ is smooth, then we use Taylor expansion to obtain
φ(xk+1) = φ(xk − αdk) = φ(xk)− α 〈 ∇φ(xk), dk 〉 + α 2
2
〈 ∇2φ(xk)dk, dk 〉 +O(α3).
Taking expectations on both sides of the above equality and applying (8), we have Eπ [〈 ∇φ(xk), dk 〉 − α2 〈 ∇2φ(xk)dk, dk 〉] = O(α2). (9) For an arbitrary smooth function φ, it is very hard in practice to characterize or approximate the O(α2) term on the right-hand side. In addition, computing the Hessian-vector product ∇2φ(xk)dk can be very costly. Therefore, we only consider simple quadratic functions for which the O(α2) term in (9) vanishes. In particular, the choice of φ(x) = (1/2)‖x‖2 results in
Eπ [〈 xk, dk 〉 − α2 ‖d k‖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 a quadratic function of the state (e.g., Dembo, 2013, Section 3.2.3). Beyond stationarity, it requires no specific assumption on the loss function or 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 gk , ∇fξk(xk) to obtain his “master equation” Eπ [ φ(xk − αgk) ] = Eπ [ φ(xk) ] , ∀ k.
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 dk = (1− β)gk + βdk−1, the master equation leads to (Yaida, 2018)
Eπ
[〈 xk, gk 〉 − α2 1+β 1−β ‖d k‖2 ] = 0. (11)
It is a simple exercise to show that this is equivalent to our master condition (10). For the QHM update (7), a more complex stationarity condition may also be derived, but it will still be equivalent to (10). In practice, the single, simple master condition (10) is much more preferred.
If {xk} starts with a nonstationary distribution and converges to a stationary state, we have lim k→∞ E [〈 xk, dk 〉 − α2 ‖d k‖2 ] = 0. (12)
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-stationarity (i.e., the dynamics may be approximately stationary), we would like to reduce the learning rate α to allow for finer convergence.
Algorithm 1: SASA+: SASA with master condition and simple statistical testing 1 input: x0 ∈ Rp, α0 > 0, Nmin > 0, Ktest > 0, δ ∈ (0, 1), θ ∈ (0, 1), τ ∈ (0, 1) 2 α← α0 3 ko ← 0 4 for k = 0, ..., T − 1 do 5 Randomly sample ξk and compute stochastic search direction dk (e.g., using QHM) 6 xk+1 ← xk − αdk 7 ∆k ← 〈 xk, dk 〉 − α2 ‖d
k‖2 8 N ← dθ(k − ko)e 9 if N > Nmin and k mod Ktest == 0 then
10 (µ̂N , σ̂N )← sample mean and BM/OLBM variance of {∆k−N+1, . . . ,∆k} 11 if 0 ∈ µ̂N ± t∗1−δ/2 σ̂N√ N
then 12 α← τα 13 ko ← k 14 end 15 end 16 end 17 output: xT (or the average of last epoch)

heading: 3 STATISTICAL TESTS OF (NON-)STATIONARITY
text: In order to test if the master condition (10) holds approximately, we collect the simple statistics ∆k , 〈 xk, dk 〉 − α2 ‖d k‖2 = 〈 xk+1, dk 〉 + α2 ‖d k‖2.
Here the second expression for ∆k is obtained using the direct substitution xk+1 = xk−αdk, which can be more convenient to implement if ∆k is collected after the state updates to xk+1.
In the language of statistical hypothesis testing (e.g., Lehmann & Romano, 2005), we make as our null hypothesis that the dynamics (6) have reached a stationary distribution π. If we haveN samples {∆k}, we know from equation (10) and the Markov chain CLT (see its application in Jones et al. (2006)) that asN →∞, under the null hypothesis the mean statistic ∆̄ follows a normal distribution with mean 0 and variance σ2∆/ √ N . Our alternative hypothesis is that the dynamics (6) have not reached stationarity. To test these hypotheses, we adopt the classical confidence interval test. More specifically, we use the most recent N samples {∆k−N−1, . . . ,∆k} to compute the sample mean µ̂N and a variance estimator σ̂2N for σ 2 ∆. Then we can form the (1− δ)-confidence interval
(µ̂N − ωN , µ̂N + ωN ) with half width ωN = t∗1−δ/2 σ̂N√ N , (13)
where t∗1−δ/2 is the (1 − δ/2) quantile of the Student’s t-distribution with degrees of freedom corresponding to that in the variance estimator σ̂2N . Because the sequence {∆k−N+1, . . . ,∆k} are highly correlated due to the underlying Markov dynamics, the classical formula for the sample variance (obtained by assuming i.i.d. samples) does not work for σ̂2N . We need to use more sophisticated batch mean (BM) or overlapping batch mean (OLBM) variance estimators developed in the Markov chain Monte Carlo literature (e.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 A.
Algorithm 2: Smoothed Stochastic Line-Search (SSLS) 1 input: x0 ∈ Rp, α−1 > 0, sufficient decrease coefficient c ∈ (0, 1/2), line-search factors
ρinc ≥ 1, ρdec ∈ (0, 1), smoothing parameter γ ∈ [0, 1] and maximum LS count m 2 for k = 0, ..., T − 1 do 3 Sample ξk, compute gk ← ∇fξk(xk) and search direction dk (e.g., using QHM) 4 ηk ← ρincαk−1 5 while fξk(xk − ηkgk) > fξk(xk)− c · ηk‖gk‖2 and ηk > ρmdecαk−1 do 6 ηk ← ρdecηk 7 end 8 αk ← (1− γ)αk−1 + γηk 9 xk+1 ← xk − αkdk
10 end 11 output: xT
If the confidence interval in (13) contains 0, 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 general framework of SASA (Statistical Adaptive Stochastic Approximation) proposed by Lang et al. (2019). Algorithm 1 is our new variant called SASA+. Table 1 lists its hyperparameters and their default values (where n 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 as the null hypothesis and stationarity as the alternative hypothesis (opposite to ours). This leads to a more complex “equivalence test” that requires an additional hyperparameter. Our test is simpler and more straightforward, and computationally as robust.

heading: 4 SMOOTHED STOCHASTIC LINE SEARCH
text: SASA+ can automatically decrease the learning rate to refine the last phase of the optimization process, but it relies on an appropriate setting of the starting learning rate α0 for sufficient initial exploration. 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 gradient methods, adaptive or not.
Several recent works (e.g., Schmidt et al., 2017; Vaswani et 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 a smoothed stochastic line-search (SSLS) procedure listed in Algorithm 2.
During each step k, SSLS uses the classical Armijo line-search to find an appropriate step size ηk for the randomly chosen function fξk (initialized by αk−1), then sets the overall learning rate to be
αk = (1− γ)αk−1 + γηk, where γ ∈ [0, 1]. When γ = 1, SSLS reduces to the stochastic Armijo line-search used by Vaswani et al. (2019). A good choice is to set γ = b/n where n is the total number of training examples and b is the mini-batch size. Suppose ρinc = 2 and ηk = 2αk−1 is accepted at step k, then
αk = (1− γ)αk−1 + γ(2αk−1) = (1 + γ)αk−1. If this happens at every iteration over one epoch (of dn/be iterations) and n b, then
αk+dn/be = (1 + b/n) dn/beαk ≈ e · αk. (14)
Therefore, the most aggressive growth of the learning rate is by a factor of e over one epoch. Such a growing factor is reasonable for line search in deterministic optimization (e.g., Nesterov, 2013).
Algorithm 3: SALSA: SASA+ with warmup by SSLS 1 input: x0 ∈ Rp, number of steps for warmup Twu and total number of steps T > Twu 2 for k = 0, ..., Twu do 3 Run SSLS (Algorithm 2) 4 end 5 for k = Twu + 1, ..., T do 6 Run SASA+ (Algorithm 1) 7 end 8 output: xT
Setting γ = √ b/n leads to maximum growth of e2 over one epoch. A similar smoothing effect holds for decreasing the learning rate as well. The smoothing scheme allows us to use standard increasing and decreasing factors, such as ρinc = 2 and ρdec = 1/2. Without the smoothing scheme, Vaswani et al. (2019) set ρinc = 2b/n to restrict dramatic growth of αk = ηk (equivalent to γ = 1 in SSLS). However, the decreasing of αk = ηk can be excessive and premature, even with ρdec = 0.9.
Following the theoretical framework of Vaswani et al. (2019), it may be possible to show that SSLS has similar convergence properties as stochastic Armijo line-search under the smooth and interpolation assumptions, which we leave as a future research project. In this paper, we are mainly interested in investigating its performance in 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 in 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 ηk > ρmdecηk for staying in the line-search loop. By default, we set m = 10 together with ρdec = 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 on 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 Twu 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 Twu to be equivalent to a few tens of epochs. According to the calculation in (14), using 30 epochs would allow a potential growth factor up to a reasonable fraction of e30, which is 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 αk, 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 optimization 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 is only 0.15 of the original total training time.

heading: 5 EXPERIMENTS
text: We evaluate the performance of SASA+ (Algorithm 1), SSLS (Algorithm 2) and SALSA (Algorithm 3) by conducting several experiments on two common deep learning datasets. We compare SALSA to the following baselines: SGD with a hand-tuned constant-and-cut learning rate schedule and Adam with a tuned warmup phase (e.g., Wilson et al., 2017; 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.
CIFAR-10 We trained an 18-layer ResNet model (He et al., 2016) on CIFAR-10 (Krizhevsky & Hinton, 2009) with random cropping and random horizontal flipping for data augmentation and weight decay 0.0005. Row 1 of Figure 1 compares the best performance of each method. Here SGM-hand uses α0 = 1.0 and β = 0.9 and drops α by a factor of 10 every 50 epochs. Adam has a tuned global learning rate α0 and a “warmup” phase of 50 epochs. With only a tuned α0 = 1e−4 (the optimal value in our grid search of {1e−5, 1e−4, 1e−3, 1e−2}), Adam is only able to 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 is 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 using the default parameters in Table 1. Between two jumps, the statistics ∆k 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 Figure 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 2. The middle row shows the effect of statistical parameter δ. Smaller δ leads to wider confidence interval, and makes easier and thus earlier to fire the statistical test. The bottom row shows the effect of θ, the fractions of samples to keep after reset. Smaller θ 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 β = ν = 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 to 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 augmentation and weight decay 0.0001. Row 1 of Figure 5 compares the performance of the different optimizers. Even with a tuned α0 = 1e−4 (the optimal value in our grid search of {1e−5, 1e−4, 1e−3, 1e−2}) 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-tuned SGM using the default values of its parameters. Although both SASA+ and SALSA are using the NAG (equivalent to QHM (7) with β = ν = 0.9),
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 a consequence, SASA+(Nag) reaches a stationary state much faster. Nevertheless, their final performances are nearly the same, with SALSA(Nag) even slightly higher.
Row 2 of Figure 5 shows that SASA+ is simple and general enough to work with different stochastic optimization methods with constant hyperparameters, i.e., SGM with β = 0.9, NAG, and the recommended QHM setting (β = 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 6 shows the sensitivity analysis of SSLS. From the left and middle panels, we can see that the SSLS always converges to a large learning rate (1.806 in 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 c is, the smaller the maximal learning rate is and the slower SSLS reaches to its maximal learning rate. This is intuitive because larger c puts more limits on 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 to SASA+ after SLSS reaches a stable learning rate.

heading: 6 CONCLUSIONS
text: We presented SASA+, a simpler yet more powerful variant of the statistical adaptive stochastic approximation (SASA) method proposed by Lang et al. (2019). SASA+ is equipped with a single statistical test for (non-)stationarity that works for a broad family of stochastic optimization methods 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 better 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, is highly autonomous and robust over variations of its hyperparameters. Using the same default setting, SALSA obtained state-of-the-art performance on several common deep learning models that is competitive with the best hand-tuned optimizers.

heading: A MCMC VARIANCE ESTIMATORS
text: 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). Jones et al. (2006) gives a nice example of such results. Here we simply list two common variance estimators, and we refer the reader to that work and Lang et al. (2019) (from which we borrow notation) for appropriate context and formality.
Batch means variance estimator. Let z̄N be the history average estimator with N samples, that is, given samples {zi} from a Markov chain, z̄N = 1N ∑i0+N i=i0 zi. Now form p batches from the N
samples, each of size q. Compute the “batch means” z̄j = 1q ∑(j+1)q−1 i=jq zi for each batch j. Then compute the batch means estimator using:
σ̂2N = q
p− 1 p−1∑ j=0 (z̄j − z̄N )2. (15)
The estimator is just the variance of the batch means around the history average z̄N . This statistic has p−1 degrees of freedom. As in Jones et al. (2006) and Lang et 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+ 1 overlapping batches of size p (rather than disjoint batches) and has N − p degrees of freedom. It can be computed as:
σ̂2N = Np
(N − p)(N − p+ 1) N−p∑ j=0 (z̄N − 1 p p∑ i=1 zj+i) 2. (16)

heading: B THE STATISTICAL TESTS IN SASA AND SASA+
text: As mentioned in our contributions, there are two main differences between SASA from Lang et al. (2019) and SASA+. First, SASA+ has a much more general “master stationary condition” (10), so it 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 (11)) only applies to the stochastic heavy-ball method. Second, the statistical tests used in SASA and SASA+ are quite different, as we elaborate below.
The difference starts from a conceptual change from SASA to SASA+. In SASA, one wants to confidently detect stationarity. If stationarity is detected, one decreases the learning rate, and otherwise keeps it the same. In SASA+, one wants to confidently detect non-stationarity. If non-stationarity is detected, one keeps the learning rate the same, and otherwise decreases. This conceptual change leads to a simpler and more rigorous statistical test in SASA+.
B.1 EQUIVALENCE TEST IN SASA
To confidently detect stationarity, SASA has to set non-stationarity as null hypothesis and stationarity as the alternative hypothesis. If one confidently rejects the null (non-stationarity), 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 (11). Formally, the test in SASA is H0 : E[∆] 6= 0 vs. H1 : E[∆] = 0, (17) where samples of ∆, i.e., ∆k , 〈 xk, dk 〉 − α2 ‖d
k‖2, are collected along the training process. This kind of test is called an equivalence test in statistics, see, e.g., Streiner (2003). There is no power1 in the equivalence test (17), i.e., one cannot confidently reject the null hypothesis and prove stationarity
1In statistical hypothesis testing, power is the ability to reject the null hypothesis when it is false.
at all! Intuitively, even when the process is stationary, with only a finite number of (noisy) samples {∆k}N1k=0, the sample mean ∆̄N 6= 0 (with probability one) is always more likely to be the true mean than the singleton 0. In other words, one can not deny that the process is 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
H0 : |E[∆]| > ζν vs. H1 : E[∆] ∈ [−ζν, ζν], (18)
where ζν is the equivalence interval. In English, instead of the usual null hypothesis of not-equal-tozero in (17), now the null hypothesis is not-equal-to-zero by a margin ζν. In this case, when E[∆]’s confidence interval is contained in the equivalence interval, i.e.,[
∆̄N − t∗1−δ/2 σ̂N√ N , ∆̄N + t ∗ 1−δ/2 σ̂N√ N
] ⊂ [−ζν̄N , ζν̄N ]. (19)
we are confident to reject the null hypothesis and to prove/acceptH1 (the stationary condition is met within an error tolerance). This is exactly the test in SASA Lang et al. (2019), see its Equation (10). However, this equivalence test requires estimation of ν̄N (that estimates the magnitude of ∆) and an additional hyperparameter ζ that controls the equivalence interval width. In SASA’s notation, the equivalence width ζ is denoted by δ.
Moreover, SASA makes the unjustified assumption that under their null hypothesis (H0 : |E[∆]| > ζν), the Markov central limit theorem holds. Under theirH0, the process is non-stationary, while the construction of E[∆]’s confidence interval in Eqn. (19) 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+, we want to confidently detect non-stationarity. If non-stationarity is 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 nonstationarity as the alternative:
H0 : The process is staionary vs. H1 : The process is not staionary. (20)
The master stationary condition E[∆] = 0 is a necessary condition for stationary of the process, and thus confidently rejecting E[∆] = 0 is sufficient to confidently reject the null (stationarity) hypothesis. Moreover, under this null hypothesis, the Central Limit Theorem of Markov Processes exactly holds true (because the process is stationary), validating the construction of E[∆]’s confidence interval. Therefore, the intrinsic flaw in SASA is naturally solved in SASA+.
Now we describe the test in SASA+. When the confidence interval of E[∆] does not contain 0, i.e., 0 6∈ [ ∆̄N − t∗1−δ/2
σ̂N√ N , ∆̄N + t ∗ 1−δ/2 σ̂N√ N
] , (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 (19) and (21)) for E[∆]. In practice, their difference is 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 of E[∆] (Red). SASA+’s test is confident to reject its (stationary) null hypothesis, so it keeps the learning rate the same. However, SASA decreases its learning rate because it is confident that the stationary condition holds true within its error tolerance (equivalence interval). In this case, SASA makes an error due to its relatively large equivalence
interval. In Case (2), SASA+’s test is not confident to reject its (stationary) null hypothesis and so 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 on the CIFAR10 and ImageNet datasets, the (width of) the equivalence interval ζν is typically much smaller than the (width of) the confidence interval of E[∆], see Figure 5(a), 7(a) and 9(a) in Lang et al. (2019). Notice that in those figures, the yellow curve is ν instead of ζν, 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 1, the black curve (SASA+) is faster at decreasing the learning rate than the green curve (SASA).

Review summaries:
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: