Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic
Authors: Matteo Sordello
Hangfeng He
Weijie J Su
Venue:  (2021)
Keywords: Optimization
Deep Learning
Stationarity
Adaptive

Abstract: This paper proposes SplitSGD, a new dynamic learning rate schedule for stochastic optimization. This method decreases the learning rate for better adaptation to the local geometry of the objective function whenever a stationary phase is detected, that is, the iterates are likely to bounce at around a vicinity of a local minimum. The detection is performed by splitting the single thread into two and using the inner product of the gradients from the two threads as a measure of stationarity. Owing to this simple yet provably valid stationarity detection, SplitSGD is easy- to-implement and essentially does not incur additional computational cost than standard SGD. Through a series of extensive experiments, we show that this method is appropriate for both convex problems and training (non-convex) neural networks, with performance compared favorably to other stochastic optimization methods. Importantly, this method is observed to be very robust with a set of default parameters for a wide range of problems and, moreover, yields better generalization performance than other adaptive gradient methods such as Adam.

Under review as a conference paper at ICLR 2021
ROBUST LEARNING RATE SELECTION FOR STOCHAS- TIC OPTIMIZATION VIA SPLITTING DIAGNOSTIC
Anonymous authors Paper under double-bling review
ABSTRACT
This paper proposes SplitSGD, new dynamic learning rate schedule for stochastic optimization. This method decreases the learning rate for better adaptation to the local geometry of the objective function whenever a stationary phase is detected, that is, the iterates are likely bounce at around a vicinity of a local minimum. The detection is performed by splitting the single thread into two and using the inner product of the gradients from the two threads as a measure of stationarity. Owing to this simple yet provably valid stationarity detection, SplitSGD is easy- to-implement and essentially does not incur additional computational cost than standard SGD. Through series of extensive experiments, show that this method is appropriate for both convex problems and training (non-convex) neural networks, with performance compared favorably other stochastic optimization methods. Importantly, this method is observed to be very robust with set of default parameters for wide range of problems and, moreover, yields better generalization performance than other adaptive gradient methods such as Adam.
INTRODUCTION
Many machine learning problems boil down to finding a minimizer 0" E IRd of a risk function taking the form
F(0) = E [f Z)
where f denotes loss function, O is the model parameter, and the random data point 7 (X, y) contains a feature vector X and its label y. In the case of a finite population, for example, this problem is reduced to the empirical minimization problem. The touchstone method for minimizing (I) is stochastic gradient descent (SGD). Starting from an initial point Gg SGD updates the iterates according to
l++1 0 TJ g(O,, Zz+1)
for t 2 O, where n7 is the learning rate, {- are i.i.d. copies of Z and g(8, Z) is the (sub-) gradient of f(0, Z) with respect to 0. The noisy gradient g(0, 2) is an unbiased estimate for the true gradient V (()) in the sense that E [g(0, Z) V F(0) for any 0.
The convergence rate of SGD crucially depends on the learning rafe-often recognized as "the single most important hyper-parameter" in training deep neural networks (Bengio 2012) and, accordingly, there is a vast literature on how to decrease this fundamental tuning parameter for improved convergence performance. In the pioneering work of Robbins and Monro (1951), the learning rate 77 is set to (11/t) ) for convex objectives. Later, it was recognized that slowly decreasing learning rate in conjunction with iterate averaging leads to faster rate of convergence for strongly convex and smooth objectives (Rupperi 1988: Polyak and Juditsky 1992). More recently, extensive effort has been devoted to incorporating preconditioning/Hesiin into learning rate selection rules Duchi et al. 2 I: Dauphin al.) 2015 Tan et al. 2016). Among numerous proposals, simple yet widely employed approach is to repeatedly halve the learning rate after performing a pre-determined number of iterations (see, for example, Bottou et al. 2018).
In this paper, we introduce a new variant of SGD that we term SplitSGD with a novel learning rate selection rule. At high level, our method is motivated by the following fact: optimal learning rate should be adaptive to the informativeness of the noisy gradient g(,, Z,+1). Roughly speaking, the informativeness is higher if the true gradient V F(.).) is relatively large compared with the noise

---

Under review as a conference paper at ICLR 2021
VF(()) g(0,. Z++1) and vice versa. On the one hand, if the learning rate is too small with respect to the informativeness of the noisy gradient, SGD makes rather slow progress. On the other hand, the iterates would bounce around region of an optimum of the objective if the learning rate is too large with respect to the informativeness. The latter case corresponds to a stationary phase in stochastic optimization (Murata 1998: Chee and Toulls 2018), which necessitates the reduction of the learning rate for better convergence. Specifically, let Th be the stationary distribution for 0 when the learning one has that Eg [g(0, 2) O, and consequently that
rate is constant and set v) From (2)
(g((())),
20 =0 for 800, iid. Knp
20),ee i.dd Z
(3)
SplitSGD differs from other stochastic optimization procedures its robust stationarity phase detection, which we refer to as the Splitting Diagnostic. In short, this diagnostic runs two SGD threads initialized at the same iterate using independent data points (refers to Z1+1 in ( and then performs hypothesis testing to determine whether the learning rate leads to a station- ary phase or not. The effectiveness of the Splitting Diagnostic is illustrated in Figure I which reveals different patterns of dependence between the two SGD threads with difference learning rates. Loosely speaking, in the stationary phase (in purple), the two SGD threads behave as if they are independent due to a large learning rate, and SplitSGD subsequently de- creases the learning rate by some factor. contrast, strong positive dependence is exhibited in the non stationary phase (in orange) and, thus, the learning rate remains the same after the diagnostic. In essence, the robustness of the Splitting Diagnostic is attributed its adaptivity to the local geometry of the objec- tive, thereby making SplitSGD tuning-inseen insensitive method for stochastic optimization. Its strength is confirmed by our experimental results in both convex and non-convex settings. In the latter, SplitSGD showed robustness with respect the choice of the initial learning rate, and remarkable success in improving the test accuracy and avoiding overfitting compared to classic optimization procedures.
leamiin rate
Freqancy
0.10
0.08
0.00
-.0
Figure 1: Normalized dot product of averaged noisy gradients over 100 iterations. Stationar- ity depends on the learning rate: 7) = 1 corre- sponds stationarity (purple), while 7 0.1 corresponds to non stationarity (orange). De- tails in Section 2
1.1 RELATED WORK
There is a long history detecting stationarity or non-stationarity in stochastic optimization to improve convergence rates (Yin 1989 Pilug] 1990, Delyon and Juditsky 1993 Murata 1998 Pesme ct al. 2020). Perhaps the most relevant work in this vein to the present paper is Chee and Toulis (2018). which builds top of PPlug 1990) for general convex functions. Specifically, this work uses the running sum of the inner products of successive stochastic gradients for stationarity detection. However, this approach does not take into account the strong correlation between consecutive gradients and, moreover, is not sensitive to the local curvature of the current iterates due to unwanted influence from prior gradients. In contrast, the splitting strategy, which is akin HiGrad (Su and Zhu 2018), allows our SplitSGD to concentrate on the current gradients and leverage the regained independence of gradients to test stationarity. Lately, Yaida (2019) and Lang al. (2019) derive stationarity detection rule that is based on gradients of mini-batch to tune the learning rate in SGD with momentum.
From a different angle, another related line of work is concerned with the relationship between the informativeness of gradients and the mini-batch size (Keskar et al. 2016 Yin et al. 2017 Li et al. 2017 Smith et al., 2017). Among others, it has been recognized that the optimal mini-batch size should be adaptive to the local geometry of the objective function and the noise level of the gradients, delivering growing line of work that leverage the mini-batel gradient variance for learning rate selection (Byrd et al. 2012 Balles et al. 2016 Balles and Hennig 2017 De et al. 2017 Zhang and Mitliagkas 2017 McCandlish al. 2018).
2

---

Under review as a conference paper at ICLR 2021
=
NON STATIONARY
7)
= 7:77
STATIONARY
4
41
[11/7]
2
Figure 2: The architecture of SplitSGD. The initial learning rate is and the length of the first single thread 11. the diagnostic does not detect stationarity, the length and learning rate of the next thread remain unchanged. If stationarity is observed, decrease the learning rate by factor y and proportionally increase the length.
THE SPLITSGD ALGORITHM
In this section, we first develop the Splitting Diagnostic for stationarity detection, followed by the introduction of the SplitGGD algorithm in detail.
2.1 DIAGNOSTIC VIA SPLITTING
Intuitively, the stationarity phase occurs when two independent threads with the same starting point are no longer moving along the same direction. This intuition is the motivation for our Splitting Diagnostic, which is presented in Algorithm [ and described in what follows. We call Og the initial value, even though later it will often have different subscript based on the number of iterations already computed before starting the diagnostic. From the starting point, we run two SGD threads, each consisting of windows of length For each thread k 1, define gr. and the iterates are
(k) g(O{A) 2
e(4)
0!h
77 9t (k)
(4)
where E ......, wl 1}. On every thread we compute the average noisy gradient in each window, indexed by i 1, .,., W. which
(k) (C-
(K)
0.41 Σ
(1-
1)
1.
2-1+1
(5)
The length of each window has the same function as the mini-batch parameter in (Li al., 2014), in the sense that a larger value of aims capture more of the true signal by averaging out the errors. At the end of the diagnostic, we have stored two vectors, each containing the average noisy gradients the windows in each thread.
SGD
Definition 2.1. For ,,., W. we define the gradient coherence with respect to the starting point of the Splitting Diagnostic Og the learning rate 1), and the length of each window as
Q.(0.. (0(2) -0:2)).
(6)
We will drop the dependence from the parameters and refer to it simply as Q+-
The gradient coherence expresses the relative position of the average noisy gradients, and its sign indicates whether the SGD updates have reached stationarity. In fact, if in the two threads the noisy gradients are pointing on average in the same direction, means that the signal is stronger than the noise, and the dynamic is still in its transient phase. On the contrary. as ( suggests, when the gradient coherence on average very close to zero, and also assumes negative values thanks its stochasticity, this indicates that the noise component in the gradient is now dominant, and stationarity has been reached. Of course these values, no matter how large / is, are subject to some randomness. Our diagnostic then considers the signs of Q1. Qu and returns result based on the proportion of negative Q,- One output is a boolean value TD. defined as follows:
Dm sign (Q:))/2 2 w
To
N if E sign (Q:))/2 < w.
where TD = S indicates that stationarity has been detected, and Tp = N means non-stationarity. The parameter g E [0, 1] controls the tightness of this guarantee, being the smallest proportion of negative Q; required to declare stationarity. In addition to TD. we also return the average last iterate of the two threads starting point for following iterations. We call it Op
(0(2) + /(2))22.
3

---

Under review as a conference paper at ICLR 2021
2.2
THE ALGORITHM
Algorithm SplitSGI
The Splitting Diagnostic can be employed in a more sophisticated SGD procedure, which call SplitSGD. We start by running the standard SGD with constant learning rate rj for t itera- tions. Then, starting from 6t,, we use the Split- ting Diagnostic to verify if stationarity has been reached. If stationarity is not detected, the next single thread has the same length y and learn- ing rate 1j the previous one. On the contrary, if TD = S, we decrease the learning rate by factor y E (0, 1) and increase the length of the thread by 1/7,, as suggested by [Bottou et al. 2018 in their SGD procedure. Notice that, if O, then the learning rate gets determin- istically decreased after each diagnostic. On the other extreme, if we set q = 1, then the procedure maintains constant learning rate with high probability. Figure
SplitSGD(7, w. 1,,, B, 00.
1: 71 17
2: 01" 00
3: for b I,... B do
4:
Run SGD with constant step size 1/6 for
la steps, starting from 0g
Let the last update be ofaat
5:
6:
Do = Diagnostic( n7, w, L, g, Ofast)
7:
0 0D.
8:
if TD S then
9:
7 7 77 and to+1 Lto//l
10: else
11: M = nu and to+1 = to
12: end
13: end for
2 iillustaates what hap- pens when the first diagnostic does not detect stationarity, but the second one does. SplitSGI puts together two crucial aspects: it employs the Splitting Diagnostic at deterministic times, but does not deterministically decreases the learning rate. We will see in Section ! how both of these features come into play in the comparison with other existing methods. A detailed explanation of SplitSGD presented in Algorithm 1
Diagnostic(n) n, w, li))
14: 00' =0(²) gin
15: for prri= = i w do
for 1,2 do
17:
for j = 0, ..., I 1 do
18:
ind (i - 1) -(+
((k)
ind+1 0(h)]
(k)
19:
gind
20:
end for
21:
9,
(0
(i-1)-411 0,41 //1-
(k)
3 THEORETICAL GUARANTEES FOR STATIONARITY DETECTION
22:
end for
Q: (g 9i (2)
23:
24: end for
This section develops theoretical guarantees for the validity of our learning rate selection. Specif- ically, in the case of a relatively small learning rate, we can imagine that, if the number of iter- return 0p = (0th + //, Tb Tb=N ations is fixed, the SGD updates are not too far from the starting point, so the stationary phase has not been reached yet. On the other hand, however, when - and the learning rate is fixed, we would like the diagnostic have reached stationarity, since we know that in this case the updates will oscillate around 0*, Our first assumption concerns the convexity the function F()). will not be used Theorem in which we focus our attention on neighborhood of Oo-
25: if
D>=n T0
(1
sign (Q.))/2 2 9.9. then
26: return 0p (0 + )/2 TD =
27: else
28:
29:
end if
tell us that we
Assumption 3.1. The function F is strongly convex, with convexity constant > 0. For all O, Oz.
F(I.) 2 F(2.) + (VF((2). 82) + "/" 100 A2ll
and also VF(()) VF(02)) 2 μ [|0 0211- Assumption 3.2. The function F is smooth, with smoothness parameter L > 0. For all 0,, 82.
[VF())) - FF()) S L 110 -21l.
We said before that the noisy gradient is an unbiased estimate of the true gradient. The next assumption that we make is on the distribution of the errors.
Assumption 3.3. We define the error in the evaluation of the gradient in 0 as
E = cl -1 7x) g(0r-1, 7,) F((..))
(8)
4

---

Under review as a conference paper at ICLR 2021
Linear Regr regression with 50
Logistc Regression with
Linear Regression with vy 0.01
Logisiic Regression on with v 0.06
0.29
0.5
E11
411
C09
ECV
Figure 3: Histogram of the gradient coherence Qi (for the second pair of windows, normalized) of the Splitting Diagnostic for linear and logistic regression. The two left panels show the behavior in Theorem 3.1 the two right panels the one in Theorem 3.2 In orange we see non stationarity, while in purple distribution that will return stationarity for appropriate choice of and q.
and the filtration Fz === oZi,... Z.). Then e, E Fr and {= ) a martingale difference sequence with respect to {Filee) which means that
= 0. The covariance of the errors satisfies
Ouin I
[eac [i-1]] 3 mmax
where 0 < min max 00 for any 0.
Our last assumption on the noisy functions f0, Z) and on an upper bound on the moments of their gradient. We do not specify here since different values used in the next two theorems, but the range for this parameter is m E {2, 4].
Assumption 3.4. Each function [0, Z) convex, and there exists constant G such that E (f,, Z Fil S G for any 0g.
We first show that there exists learning rate sufficiently small such that the standard deviation of any gradient coherence Q; is arbitrarily small compared to its expectation, and the expectation is positive because +1 is not very far from 0.. This implies that the probability of any gradient coherence to be negative, (QQ; < 0), is extremely small, which means that the Splitting Diagnostic will return Tp = N with high probability.
Theorem 3.1. Assumptions 3.2 3.3 and 3.4 with m hold, |[FF()))] 0 and run t iterations before the Splitring Diagnostic, then for any i {1, w we can set 1] small enough to guarantee that
sd((i) S () E (Q.).
where (1, O(1/VD +O(nt( +1). Proof in Appendix
B
In the two left panels of Figure S we provide visual interpretation of this result. When the starting point of the SGD thread is suffcientlyy far from the minimizer 0" and is sufficiently small, then all the mass of the distribution of Qi is concentrated on positive values, meaning that the Splitting Diagnostic will not detect stationarity with high probability. In particular we can use Chebyshev inequality to get a bound for P(Q; < 0) of the following form:
P(Q. < 0) < P(QQ: E[Q.] E(Q,)) < /E(Q.)/E(Q.) I 1)),1)²
Note that to prove Theorem 3.1 we do not need to use the strong convexity Assumption 3. since, when rt1 + 1) is small, 0,, + is not very far from 0g. In the next Theorem we show that, we let the SGD thread before the diagnostic run for long enough and the learning rate is not too big, then the splitting diagnostic output is Tb = probability that can be made arbitrarily high. This is consistent with the fact that, as t oc, the iterates will start oscillating in neighborhood of 6".
Theorem 3.2. If Assumptions
3.7
3.2
3.3 and 3.4 with m hold, then for any S #, IEN
and (I,..., w) as b +
have
IE [Q:] S C2(1) sd().)
where C2(n) C2 17 o(n). Proof in Appendix C
The result of this theorem is confirmed by what we see in the right panels of Figure 5 There, most of the mass of Q: is positive values if O. since the learning rate is sufficiently small and the
5

---

Under review as a conference paper at ICLR 2021
Linear Ragrossion, q
10"
Logistic Ragression, q 10
Linear Regression
Logistic Regression
1000
Sye8c0
Seniio opodee
730
600
24:4 020 iiai Leaining Part
CAT CB3
022
SpRt
pfug
Sclt
(i8il Lobriing Rars
Figure 4: (left) comparison between Splitting and pflug Diagnostics on linear and logistic regression. The red bands are the epochs where stationarity should be detected. (right) comparison of the log(loss) achieved after 100 epochs between SplitSGD, SGD (Half) and SGD with constant or decreasing learning rate on linear and logistic regression. More details are in Section 4.1
starting point is not too close to the minimizer. But when we let the first thread run for longer, we that the distribution of Qi is now centered around zero, with expectation that is much smaller than its standard deviation. An appropriate choice of te and makes the probability that Tn = S arbitrarily big. In the proof of Theorem 3.2 make of result that is contained in Moulines and Bach T) and then subsequently improved in Needell et al. 2014). representing the dynamic of SGD with constant learning rate.
Lemma 3.3. If Assumptions 3.1
3.2
3.3 and 3.4 with m 2 hold, and n S #.. then for any t
G² E [10] - - 1-] S (1 2n(e - 12m))* E [116 - 1- + μ- L2
The simulations in Figure 3 show us that, once stationarity is reached, the distribution of the gradient coherence is fairly symmetric and centered around zero, its sign will be approximately a coin flip. In this situation, if is large enough, the count of negative gradient coherences is approximately distributed as a Binomial with wo number of trials, and 0.5 probability of success. Then we can set g to control the probability of making type I error - rejecting stationarity after it has been reached - 1
by making 2w -i= (v) sufficiently small. Notice that very small value for q makes the type I error rate decrease
makes it easier to think that stationarity has been reached too early. In the Appendix E. we provide simple visual interpretation to understand why this trade-off gets weaker as w becomes larger. Finally, we provide a result on the convergence SplitSGD. We leave for future work to prove the convergence rate of SplitSGD, which appears be very challenging problem.
Proposition 3.4. If Asssumppiins 3.7 3.2 3.3 and 3.4 with 2 hold, and S Hs. then SplitSGD guaranteed to converge with probabulity lending to as the number of diagnostics B - cc. Proof in Appendix D
4 EXPERIMENTS
4.1 CONVEX OBJECTIVE
The setting is described in details in Appendix E. We use a feature matrix X E Rnxd with standard normal entries and = 1000, d = 20 and f7 5 e- 1/2 for 1...., 20. The key parameters are I 4, 20, = 50 and q 0.4. A sensitivity analysis is in Section 4.3
Comparison between splitting and pf diagnostic. In the left panels of Figure we compare the Splitting Diagnostic with the pflug Diagnostic introduced in Chee and Toulis 20188. The boxplots are obtained running both diagnostic procedures from a starting point 0g = 6. e. where è' ~ (0, 0.011a) is multivariate Gaussian and 0g has the same entries of 0* but in reversed order, so 0., = 5- (d--))/2 for 1, ... 20. Each experiment is repeated 100 times. For the Splitting Diagnostic, we run SplitSGD and declare that stationarity has been detected at the first time that a diagnostic gives result Tp = S, and output the number of epochs up to that time. For the pflug diagnostic, we stop when the running sum of dot products used in the procedure becomes negative at the end of epoch. The maximum number of epochs is 1000, and the red horizontal bands represent

---

Under review as a conference paper at ICLR 2021
CNN on Fashion MNSST
Resnet on CIFAR-10 1D
LSTM on Pann Treebank
-500
+500 (=03
Adam 21am0=00000
91
190)
+ (DR
Spt BSG4 n- 11.1
Acaracy
Tos Poounoo
Tos Parpkody
Sppfl IAdamt +-00000
-000
A 0.003
80D -001
FDR 0.001
%
SGD eu- 0.01
Spre520) u1-11 U.1
FER
FDR n y-0000 0.01
ip 0100000
120
Sul 1930 D.11
Gpl ISGD 0.000
SGD manual deCat)
50
100
1003
2000
300
300
Epodro
100
150
Figure 5: Performance of SGD, Adam, FDR and SplitSGD in training different neural networks. SplitSGD proved to be beneficial in (i) better robustness to the choice of initial learning rates, (ii) achieving higher test accuracy when possible, and (iii) reducing the effect of overfitting. Details of each plot are in Section 4.2
the approximate values for when we can assume that stationarity has been reached, based on when the loss function of SGD with constant learning rate stops decreasing. We can see that the result of the Splitting Diagnostic is close to the truth, while the pflug Diagnostic incurs the risk of waiting for too long, when the initial dot products of consecutive noisy gradients are positive and large compared to the negative increments after stationarity is reached. The Splitting Diagnostic does not have this problem, as a checkpoint is set every fixed number of iterations. The previous computations are then discarded, and only the new learning rate and starting point are stored. In Appendix F.2 more configurations of learning rates and starting points.
we show
Comparison between SplitSGD and other optimization procedures. Here we set the decay rate to the standard value 7 = 0.5, and compare SplitSGD with SGD with constant learning rate 17, SGD with decreasing learning rate т7 x 1/vł (where the initial learning rate is set to 20n). and SGD!/2 (Bottou et al. 2018), where the learning rate is halved deterministically and the length of the next thread is double that of the previous one. For S/ we set the length of the initial thread to be 41. the same as for SplitSGD. In the right panels of Figure 4 we report the log of the loss that we achieve after 100 epochs for different choices of the initial learning rate. It is clear that keeping the learning rate constant is optimal when its initial value is small, but becomes problematic for large initial values. On the contrary, deterministic decay can work well for larger initial learning rates but performs poorly when the initial value is small. Here, SplitSGD shows its robustness with respect to the initial choice of the learning rate, performing well on a wide range of initial learning rates.
4.2 DEEP NEURAL NETWORKS
To train deep neural networks, instead of using the simple SGD with constant learning rate inside the SplitSGD procedure, we adopt SGD with momentum QQian 1999). where the momentum parameter is set to 0.9. SGD with momentum is popular choice in training deep neural networks (Sutskever et al. 2013), and when the learning rate is constant, it still exhibits both transient and stationary phase. We introduce three more differences with respect the convex setting: (i) the gradient coherences are defined for each layer of the network separately, then counted together to globally decay the learning rate for the whole network, (ii) the length of the single thread is not increased if stationarity is detected, and (iii) we consider the default parameters q = 0.25 and w = 4 for each layer. We expand on these differences in Appendix E. As before, the length of the Diagnostic is set to be one epoch, and t = 4. We compare SplitSGD with SGD with momentum, Adam (Kingma and Ba 2014) and FDR (Yaida 2019) with different learning rates, and report the ones that show the best results. Notice that, although 17 3e-4 is the popular default value for Adam, this method is still sensitive to the choice of the learning rate, so the best performance can be achieved with other values. For FDR, we tested each setting with the parameter L_daptivee E {100, 1000 which gave similar results. It has also been proved that SGD generalizes better than Adam (Keskar and Socher 2017] Luo al. 2019. We show that in many situations SplitSGD, using the same default parameters, can outperform both. In Figure 5 we report the average results of 5 runs In Figure [0 in the appendix we consider the same plot but also add 90% confidence bands, omitted here for better readability.
7

---

Under review as a conference paper at ICLR 2021
Convolutional neural networks (CNNs). We consider CNN with two convolutional lay- ers and a final linear layer trained on the Fashion-MNIST dataset (iiao et al. 2017). We set 17 E (3e-4, le-3, 3, 3e-3e.. 3, 1e-2) for Adam. In the first panel of Figure 5 we see the interesting fact that SGID, FDR and Adam all show clear signs of overfitting, after reaching their peak in the first 20 epochs. SplitSGD, on the contrary, does not incur in this problem, but for a combined effect of the averaging and learning rate decay able to reach better overall performance without overfitting. We also notice that SplitSGD is very robust with respect to the choice of the initial learning rate, and that its peak performance is better than the one of any of the competitors.
1e-1] 1} for SGD and SplitSGD, 1) 1le-2.1e-11 for FDR and 1 e
Residual neural networks (ResNets). For ResNets, we consider 18-layer ResNe and eval- uate it on the CIFAR-10 dataset (Krizhevsky et al. 2009). We use the initial learning rates E (1e-3, le 2, 1e-1) for SGD and SplitGGD, "
(1e-2, 1e-1) for FDR and v E (3c-5,3e 3e-5,,3,,00 3 3} for Adam, and also consider the SGD procedure with manual decay that consists in setting 17 1e-1 and then decreasing it by a factor 10 at epoch 150 and 250. In the second panel of Figure 5 we clearly see a classic behavior for SplitSGD. The averaging after the diagnosties makes the test accuracy peak, but the improvement is only momentary as the learning rate is not decreased. When the decay happens, the peak is maintained and the fluctuations get smaller. We can see that SplitSGD, with both initial learning rate 1 le-2 and 1/ le-1 is better than both SGD and Adam and that one setting achieves the same final test accuracy of the manually tuned method in less epochs. The FDR method showing excellent performance when n) 0.01 and worse result when = 0.1. In Appendix E.4 VGG19.
we see a similar plot obtained with the neural network
Recurrent neural networks (RNNs). For RNNs, we evaluate two-layer LSTM (Hochreiter
and Schmidhuber 1997) model on the Penn Treebank (Mareus et al., 1993) language modelling
task. We use 17 E f0.1, 0.3, 1.0} for both SGD and SplitSGD, 17 {0.1, 0.3} for FDR. 17 E {1e-4,3e-44 1e-3) for Adam and also introduce SplitAdam, a method similar to SplitSGD, but with Adam in place of SGD with momentum. As shown in the third panel of Figure []] we can see that SplitSGD outperforms SGD and SplitAdam outperforms Adam with regard to both the best performance and the last performance. FDR is not showing any improvement compared to standard SGD, meaning that in this framework it is unable to detect stationarity and decay the learning rate accordingly. Similar to what already observed with the CNN, we need to note that our proposed splitting strategy has the advantage of reducing the effect of overfitting, which is very severe for SGD, Adam and FDR while very small for SplitAdam and SplitSGD. We postpone the theoretical understanding for this phenomena as our future work.
For the deep neural networks considered here, SplitSGD shows better results compared SGD and Adam, and exhibits strong robustness to the choice of initial learning rates, which further verifies the effectiveness of SplitSGD in deep neural networks. The Splitting Diagnostic is proved to be beneficial in all these different settings, reducing the learning rate to enhance the test performance and reduce overfitting of the networks. FDR shows a good result when used on ResNet with specific learning rate, but in the other setting is not improving over SGD, suggesting that its diagnostic does not work on a variety of different scenarios.
4.3 SENSITIVITY ANALYSIS FOR SPLITSGD
In this section, we analyse the impact of the hyper- hyper-parameters in the SplitSGD procedure. We focus on and w, while I changes so that the computational budget of each diagnostic is fixed at one epoch. In the left panels of Figure S we analyse the sensitivity of SplitSGD to these two parameters in the convex setting, for both linear and logistic regression, and consider w {10, 20, 40) and q E {0.35, 0.40, 0.45). The data are generated in the same way as those used in Section 4.1 On the y-axis we report the log(loss) after training for 100 epochs, while on the x-axis we consider the different (w, q) configurations. The results are as expected; when the initial learning rate is larger, the impact of these parameters is very modest. When the initial learning rate small, having a quicker decay (i.e. setting y smaller) worsen the performance.
In the right panels of Figure 6 we see the same analysis applied the FeedForward Neural Network
(FNN) described in Appendix E.4 and the CNN used before, both trained on Fashion-MNIST. Here
Mooe details can be found in
/n/ html
8

---

Under review as a conference paper at ICLR 2021
Reggnoston
sic feegeaaion
Pac poott
Figure 6: Sensitivity analysis for SplitSGD with respect to the parameters w and g. appearing as the labels of the x-axis in the form (w, q). In the convex setting (left) we consider the log loss achieved after 100 epochs, while for deep neural networks (right) we report the maximum of the test accuracy. Details in Section
report the maximum test accuracy achieved when training for 100 epochs, and the x-axis we have various configurations for {0.15, 0, 25, 0.35) and w E {2, 4. 8). The results are very encouraging, showing that SplitSGD robust with respect to the choice of these parameters also non-convex settings.
CONCLUSION AND FUTURE WORK
We have developed an efficient optimization method called SplitSGD,, by splitting the SGD thread for stationarity detection. Extensive simulation studies show that this method is robust to the choice of the initial learning rate variety of optimization tasks, compared classic non-adaptive methods. Moreover, SplitSGD on certain deep neural network architectures outperforms classic SGD, Adam and FDR terms of the test accuracy, and can sometime limit greatly the impact of overfitting. As the critical element underlying SplitSGD, the Splitting Diagnostic is a simple yet effective strategy that can possibly be incorporated into many optimization methods beyond SGD, as we already showed training SplitAdam on LSTM. One possible limitation of this method is the introduction of new relevant parameter q, that regulates the rate at which the learning rate adaptively decreased. Our simulations suggest the of two different values depending
the context. A slower decrease, = 0.4, in convex optimization, and a more aggressive one, q = 0.25, for deep learning. In the future, we look forward to seeing research investigations toward boosting the convergence of SplitSGD by allowing for different learning rate selection strategies across different layers of the neural networks.
REFERENCES
Balles, L. and Hennig, P. (2017). Dissecting adam: The sign, magnitude and variance of stochastic gradients. arXiv preprint arXiv:
Balles, L., Romero, J., and Hennig, P. (2016). Coupling adaptive batch sizes with learning rates. arXiv preprint arXiv: 1612.006..
Bengio, Y. (2012). Practical recommendations for gradient- basde training of deep architectures. In Neural networks: Tricks of the trade, pages 437-478. Springer.
Bottou, L., Curtis. F. E., and Nocedal, J. (2018). Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3)
Byrd, R. H.. Chin, G. M.. Nocedal, J., and Wu, Y. (2012). Sample size selection in optimization methods for machine learning. Mathematical programming, 132-15:
Chee, J. and Toulis, P. (2018). Convergence diagnostics for stochastic gradient descent with constant learning rate. Proceedings of the Twenty-Fin First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1476-1485. PMLR.
Dauphin, Y.. De Vries, H., and Bengio, Y. (2015). Equilibrated adaptive learning rates for non-conver optimization. In Advances in neural information processing systems, pages 1504-1512.

---

Under review as a conference paper at ICLR 2021
De, S., Yadav, A., Jacobs, D., and Goldstein, T. (2017). Automated inference with adaptive batches. In Artificial Intelligence and Statistics, pages 1504-1513.
Delyon, B. and Juditsky, A. (1993). Accelerated stochastic approximation. SIAM Journal on Optimization, 3(4):868 -81.
Duchi, J., Hazan, E.,, and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Uul:2121-2153
Hochreiter, and Schmidhuber, J. (1997). Long short-term memory. Neural computation, 98):1733 1780.
Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. 'T. P. (2016). On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint /609.04836.
Keskar, N. S. and Socher, R. (2017). Improving generalization performance by switching from adam to sgd. arXiv preprint arXiv: 1712.06628.
Kingma, D. P. and Ba, J. (2014), Adam: A method for stochastic optimization. arXiv preprint 1rXiv::412.6990
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images. Technical report, Citeseer.
Lang, H., Zhang, and Xiao, L. (2019). Using statistics automate stochastic optimization. arXiv preprint arXiv:1909.0973
Li, J., Li, L., Qian, J., and Liu, J.-G. (2017). Batch size matters: A diffusion approximation framework on nonconvex stochastic gradient descent. stat, 1050:22.
Li, M., Zhang, T., Chen, Y., and Smola, A. J. (2014). Efficient mini-bated batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 661-670. ACM.
Luo, L., Xiong, Y., Liu, Y., and Sun, X. (2019). Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv:1902.09843
Marcus, M., Santorini, B., and Marcinkiewizz, M. A. (1993). Building a large annotated corpus of english: The penn treebank.
McCandlish, S., Kaplan, J., Amodei, D., and Team, O. D. (2018). An empirical model of large-batch training. arXiv preprint arXiv: /0/2.061//000/2
Moulines, E. and Bach, F. R. (2011). Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pages 451-459.
Murata, N. (1998). A statistical study of on-line learning. Online Learning and Neural Networks. Cambridge University Press, Cambridge, UK, pages 63-92.
Needell, D., Ward, R., and Srebro, N. (2014). Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in Neural Information Processing Systems, pages 1017-1025.
Pesme, S., Dieuleveut, A., and Flammarion, N. (2020), On convergencee-diannotiie based step sizes for stochastic gradient descent. arXiv preprint arXiv:2007.00534.
Pflug. G. C. (1990). Non-asymptotic confidence bounds for stochastic approximation algorithms with constant step size. Monatshefte für Mathematik, 1 10(3-4))297-314
Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838 855.
Qian, N. (1999). On the momentum term in gradient descent learning algorithms. Neural networks, 1551511
10

---

Under review as a conference paper at ICLR 2021
Robbins, H. and Monro, S. (1951). A stochastic approximation method. The annals of mathematical statistics, pages 400-407.
Ruppert, D. (1988). Efficient estimations from a slowly convergent Robbins-Monro process. Techni- cal report, Operations Research and Industrial Engineering, Cornell University, Ithaca, NY.
Smith, L., Kindermans, P.-.., Ying, C., and Le, Q. V. (2017). Don't decay the learning rate, increase the batch size. arXiv preprint arXiv: 1 1.00489.
Su, W. J. and Zhu, Y. (2018). Uncertainty quantification for online learning and stochastic approxi- mation via hierarchical incremental gradient descent. arXiv preprint 1002::180.00433
Sutskever, I., Martens, J., Dahl, G., and Hinton, G. (2013). On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1 1139-1145
Tan, C., Ma, S., Dai, Y.-H., and Qian, Y. (2016). descent. In Advances in Neural Information Processing Systems, pages 685-693
step size for stochastic gradient
Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747.
Yaida, S. (2019). Fluctuation-dissipation relations for stochastic gradient descent. In ICLR.
Yin, D., Pananjady, A., Lam, M., Papailiopoulos, D., Ramchandran, K., and Bartlett, P. (2017). Gradi- diversity: a key ingredient for scalable distributed learning. arXiv preprint arXiv: 1eee117060005550
Yin. G. (1989). Stopping times for stochastic approximation. Conference in Honor of Solomon Lefschetz and Joseph P. LaSalle, pages 409-420.
Modern Optimal Control:
Zhang, J. and Mitliagkas, I. (2017). Yellowfin and the art of momentum tuning. arXiv preprint 1706.0770


Reviews:
[{"review_id": "zbr3riF783t", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a sign-based test to determine if a stochastic process is in its stationary state or not. Unlike Pflug test, this test uses two independent trajectories to build its test. It divides each trajectory into w parts and averages the gradients insides each part. Then measure the similarity of each average of one trajectory to the corresponding average from the other trajectory via dot product and then counting the negative signs and positive signs. When the negative signs are above a threshold then the process is its stationary station. Then it shrinks the step size of SGD for future iterations. \n\n\nComments: \n1- Several parts of the paper needs more clarification and explanations: \nIt is not clear what the statistical intuition behind the splitting test is and why we should expect a more robust test. \nThe notion of informativeness is mentioned in the introduction but it is not used in the rest of the paper. Besides in its definition, it doesn’t say how they measure the “relatively largeness” of gradient w.r.t. the noise.\nFig 3 just represent eq 3 and gives no extra information. If it means something else such as the inner product for nonstationary is positive with high probability it should be mentioned clearly \n In related work: 1- Le Roux et. al. don’t detect stationarity. Why do you mention it? 2-  This work “Scott  Pesme,  Aymeric  Dieuleveut,  and  Nicolas  Flammarion.   On  convergence-diagnostic\nbased step sizes for stochastic gradient descent. ICML20” is highly relevant which is not mentioned. \nIn assumption 4, there is a parameter m which is not clear what it is or there is a limit on it, for example, can m be infinity?. In Thm 3.1. It doesn’t say what sd(Q_i) is.\nIt is not clear the connection between the result of Thm, 3.1. And the line above it which says with high probability P(Q_i <0) is small. It would be nice to mention how small the \\eta should be to guarantee the ineq. in this theorem. Besides we know that in a stationary state E(Q_i) is zero ( assuming after t_i steps we are in the stationary state ). Then what does this result mean?      \nFor both Thm’s 3.1 and 3.2 it would be helpful to add an interpretation for their result. \n2- For the empirical results \nI think you should compare against  “Lang, H., Zhang, P., and Xiao, L. (2019). Using statistics to automate stochastic optimization” instead of FDR since FDR test has high variance. \nYou should add a comparison against “Scott  Pesme,  Aymeric  Dieuleveut,  and  Nicolas  Flammarion.   On convergence-diagnostic based step sizes for stochastic gradient descent” which is a distance-based test instead of sign-based. \nFig 4 shows that your test does not work when the step size is too small. However, all your theories hold when the step size is small. SGD ½ is as good as yours. \nFor your DNN results, are this results average of several runs? If yes, you should add the std bar into the graph, If not why should we rely on the results? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "w5coYaCSRAH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 paper introduces SplitSGD method that detects the stationary phase in the stochastic optimization process and shrinks the learning rate. The SplitSGD is based on the observation that before reaching the stationary phase, two random batches of data will likely to have the gradient aligned as the noise between different batches is dominated by the shared gradient, whereas after reaching the stationary phase, two random batches should have misaligned gradient as the gradient has become mainly noise. This observation is intuitive, and some theoretical results show that (a) at the beginning, the algorithm determines non-stationary with high probability, and (b) more important, the SplitSGD algorithm is guaranteed to converge with probability tending to 1. The experiment reveals the advantage of the SplitSGD method over alternative SGD algorithms for CNN, Resnet, and LSTM.\n\nPersonally, I feel this paper is good enough to be accepted. The intuition is neat, and the new approach, as supported by both the theoretical and empirical results, should merit significant values to be widely known to other scholars. The paper has made enough contributions and has high clarity in terms of writing.\n\nHere are some concerns that I would suggest the author to consider:\n1. The theoretical results are of course important, however, the proven results could appear expected and not have surprise, despite the many technical challenges. The proven results are either for the initial steps, or for the final state on whether the algorithm converges. To further enhance the significance of the theoretical results, it could seem better to establish results on the convergence process, such as the convergence rate analysis that the author in this paper already states would be “left for future work” and the analysis “appears to be a very challenging problem”.\n2. The datasets in the empirical evaluation seem not to have large sizes, especially considering the availability of large datasets nowadays. It would make the paper more convincing if the authors can add larger datasets for comparison of methods.\n3. The proposed method has gains over a number of alternatives in the simulation. The gap between the new method and the other methods appears not really large. More comparison could be helpful, although I do not think it is fully critical.\n4. For the simulation results, as far as I understand, the SplitSGD has better test metrics and results in less overfitting. It would be very helpful if the authors could provide an intuitive explanation of why this is the case. Also, could early stopping achieve a similar performance?\n5. Here is a typo: in Eq (5) and in line 21 of algorithm 1, $\\theta^{(k)}_{i\\cdot l}$ should have $i\\cdot l +1$ rather than $i\\cdot l$ in the subscript, to match the definition in Eq (4).", "extra_scores": {}, "extra_text": {}}, {"review_id": "lLFCYBmjqcj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "**Summary**:\n\nThe paper focuses on estimating when stochastic gradient dynamics have reached a stationary phase by considering the inner product of pairwise stochastic trajectories referred to as threads. The chosen approach avoids strongly correlated estimates which leads to better mixing and more reliable identification of a stationary phase than previous work for certain problems. The proposed algorithm is specifically adapted for Deep Learning problems and performs well on the presented synthetic and real world problems.\n\n**Reason for score**:\n\nA prevalent problem of ML/DL is laid out and solution is provided that is backed by theory, intuition, simulations and empirical experiments and altogether presented in a systematic comprehensible manner. These are all constituents of a great paper that I also think provides a valid contribution to the field. \n\n\n\n\n**Pros**:\n\n- The paper is well-written and makes good use of visual media to convey results and intuition.\n- A drawback of previous methods for stationarity detection is the (potentially) correlated samples obtained from successive gradient steps. This did not seem to be a problem in the DL case presented in the experiments but would be for more general problems. The paper presents a clever way to address this problem. \n- All decisions regarding parameters and modifications to the algorithm are properly backed up with good arguments, empirical evidence and theory.\n\n**Questions**:\n\n- There is also one question regarding the implementation of SplitSGD for the Deep Learning experiments that I might have missed. Is it the case that each epoch of SplitSGD requires 2 passes through the training set or is it alternating between 1 epoch standard training and 1 epoch diagnostic?\n\n- SplitSGD is generalized to use different optimizers such as SGD with momentum and Adam and I see no reason why other first-order methods could not be incorporated as well. In ML these optimizers often rely on a diagonal preconditioning (call it $P_t$) where the update $\\theta_{t+1}= \\theta_t - \\eta_t P_t g_t$ is used. If we assume $P_t=P$ to be constant during the diagnostic we end up with average gradients of $P\\bar{g}_i$ and $Q_i=<P\\bar{g}_i^{(1)},P\\bar{g}_i^{(2)}>=<\\bar{g}_i^{(1)},\\bar{g}_i^{(2)}>_{P^2}$. Do you know how this affects the estimates $Q_i$ and whether it would be necessary to invert the preconditioning for such adaptive methods? How was this handled for SplitAdam?\n\n- In theorem 3.1 and 3.2 and by extension figure 3 the effects of large learning rates and long time-horizons for the diagnostic are compared. Let's assume the horizon $t_1$ is fixed to a \"suitable\" value. It then looks as if a more general adaptation scheme could be constructed from the condition in Eq.7. Denote the sum on the LHS of Eq.7 as $\\Sigma$. If the learning rate is too small, the red histogram of Figure 1 is expected -> $\\Sigma$ would be small, which for the chosen $t_1$ has not lead to stationarity. Would it then be possible to slightly increase the learning rate to bring the next diagnostic closer to stationarity? An extreme case of which could be to replace lines 8-12 of the algorithm with:\n```\nif S:\n\tdecrease eta by factor gamma \nelse:\n\tincrease eta by factor gamma/2\n```\n\nDid you consider such an adaptation or see any advantages/disadvantages of such a procedure?\n\n\n\n**Tips**:\n\n- In figure 3 you could flip the colors in the left pair of histograms to have \"stationary distribution as blue\" consistently.  \n- The x-labels of figure 6 are difficult to read. You could replace such a label with just a pair of parameters in larger size. Ex. \"w=10, q=0.35\" -> \"(10, 0.35)\" and explain the ($w$,$q$) setup in the caption.\n- Search for \"improvement is only mandatory is\" and replace last \"is\" with \"as\"\n- At the end of section 4.3 the values for $w$ and $q$ got mixed up.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CCHr9BBwDVc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review: This paper proposes SplitSGD, a novel heuristic for adapting the learning rate. This novel learning rate schedule is based \non the identification of stationary phases, where for stationary phases the authors refer to the training stage where the noise\nin the gradient estimate becomes dominant and therefore the iterates start jumping around a stationary point.\nThe authors develop an heuristic to detect such phases. When a stationary phase is detected, the learning rate is \ndecreased of a factor $\\gamma$. Under some assumptions, the authors provide a theoretical analysis for the\nstationary phase detection mechanism which also underlines the relation with the learning rate value. SplitSGD is then benchmarked and compared against some of the standard learning rate decaying heuristics generally adopted \nin combination with SGD or other first order stochastic methods.\n___________________________________________________________________________________________________________________ \n\n+ Overall the paper is well-written and clear.\n\n___________________________________________________________________________________________________________________\n \nConcerns: \n\n1. The learning rate, also called step-size, can be interpreted as a brutal approximation of the local curvature with a scaled identity matrix. All the work on second-order methods attempts to refine this brutal approximation with better estimates of the local curvature. Despite being the learning rate and how to adjust it the central topic of this paper, nothing is mentioned regarding the\nfundamental relation of the learning rate and the local curvature.\n\n\n2. There are some wrong statements here and there in the paper, i.e.\n\"\"\"\nSpecifically, in the case of a relatively small learning rate, we can imagine that, if the number of iterations is fixed, the SGD updates are not too far from the starting point, so the stationary phase has not been reached yet.\n \"\"\"\n\n\n3. The authors claim to propose an optimization method while what they are proposing is an heuristic to decrease the learning rate in an adaptive fashion. \n\n\n4. The costs of the stationary phase check are not discussed but the authors just briefly mention that SplitSGD comes with no significant extra costs. This does not seem to be the case though.\n\n\n5. The literature on increasing the batch size toward the final part of training is not discussed at all, as well as other state-of-the-art heuristics to deal with the noisy gradient estimate.\n\n\n6. The benchmarks are limited as the authors are not considering state-of-the-art learning rate  decaying heuristics such as the cosine decaying schedule. In addition, they could show more solid empirical results by letting an hyperparameter optimizer such as BOHB choose for the best learning schedule. Otherwise it is hard to say that the superior performance of SplitSGD is not a consequence of a wrong hyperparameter tuning of the competitors.\n\n\n7. I think the deep learning community at this stage needs less work on learning rate heuristics and more attentions on the theoretical analysis of the geometry of the landscape, novel optimization methods with theoretical guarantees and solid work on generalization properties, as there has been enough works on such heuristics which often ends up 'adding extra noise' and therefore constitute an obstacle in the process of bringing clarity and understanding in the field.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to automatically determine when the SGD step-size should be decreased, by running two "threads" of SGD for a bunch of iterations, divide those into windows, and then look at the average inner-product of the gradients in the two threads in each window. If the inner-product tends to be high, that indicates that there is still "signal" in the gradient and it should not be decreased. If it is low, that indicates that the gradient is mostly "noise". In the latter case, the learning rate is decreased by a factor of gamma and the length of the next phase is increased by gamma.

Theorem 3.1 essentially assumes smoothness, a bounded fourth moment for the stochastic gradient, and that the stochastic gradient error is not too far from isotropic. Then it shows that if the step-size is set small enough, the standard deviation of the diagnostic (Q_i) can be upper-bounded in terms of the expected value of Q_i. It follows that the probability of Q_i being negative cannot be too large (bounded in terms of the step size eta and the length of the windows l).

Theorem 3.2 adds the assumption of strong convexity and weakens the assumption on the gradient to a bounded second moment. Then it upper-bounds the expected value of the diagnostic in terms of its standard deviation.

Proposition 3.4 gives a proof of convergence. As far as I can tell the proof is essentially that the learning rate decay can't be much worse than what would happen if the diagnostic *always* set to decrease. In particular: (1) It's impossible for the learning rate to decay too quickly, since the length of each phase is increased by gamma whenever the learning rate is decreased by gamma. (This is a "non-adaptive result.) (2) The learning rate will eventually decay with probability 1.

Various concerns were brought up by the reviewers. Perhaps the most strongly voiced concern was that the proposed method is a heuristic rather than a method with a rigorous guarantee. For my part I am in agreement with the authors and other reviewers that heuristic methods for decreasing the learning rate are worthy of study given the large practical importance of this problem.

I concur with the concern raised by some reviewers that the theoretical component of the paper may not have little explanatory value for the results that are given. The assumption of strong convexity is not a major concern to me. (Though not true it can still give intuition.) More concerning is that theory essentially takes a fixed step-size scheme (repeatedly decrease the step size by gamma and increasing the length of a phase by gamma) and then shows that the diagnostic can’t be too much worse. This isn’t in keeping with the motivation of being adaptive.

The reviewers were also concerned about the explanation of better results due to less overfitting. This may be true, but the theory makes no mention of overfitting.

There was a consensus that the experimental results were promising, though some minor issues were raised.

While the direction explored in the paper has value, there are enough open questions about the relationship of the theory to the experimental results to warrant another round of review.

Small thoughts, not significant to acceptance:

The current heuristic runs two separate threads and looks at the inner-product of those gradients. An alternative to this would be to run a single thread along with a "ghost" thread that computes a different gradient at each iteration. It would be great to comment on the difference and why one might be superior to the other. A more radical alternative would be to run a single thread, but then compute the diagnostic on each half of the minibatch. A more radical alternative still would be to analytically do that splitting many times and average the results. This seems like it might simultaneously reduce the variance of the diagnostic and also reduce the computational cost.

2. The current heuristic runs two threads. Is there a tradeoff if you run more?

3. The statement of theorems could be more user-friendly. To understand Thm 3.1, I needed to search o find the definitions of: eta, l, i, w, Q_i. With a small amount of effort this could be re-written to remind the reader that w is the number of windows, l is the length, eta is the stepsize, etc. It is particularly unfortunate that sd() is never formally defined (only by reading the appendix did I discover that this was the standard deviation.)

4. The fact that the length of threads is always increased by a factor of gamma whenever the step size is reduced by gamma seems contrary to the spirit of the proposed diagnostic. After all, this "bakes in" a kind of "fastest possible" decay schedule. If the diagnostic were fully reliable, shouldn't this not be necessary? The decision to add this doe not get nearly enough discussion in the paper in my view.

5. I think it might be clearer to re-state theorem 3.1 including the Chebyshev result after it.
Decision: Reject