Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic
Authors: Matteo Sordello
Niccolo Dalmasso
Hangfeng He
Weijie J Su
Venue: Accepted by TMLR ()

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, can yield better generalization performance than other adaptive gradient methods such as Adam.

Published in Transactions on Machine Learning Research (02/2024)
Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic
Matteo Sordello
mattea.sordello91 @gmaal. com
Deportment of Statistics and Data Science Wharton School, University of Pennsylvania Philadelphia, PA, USA
Niccolò Dalmasso
niccolo.dalmassso@@nee
Deportment of Statistics & Data Science Cornegie Mellon University
Pillsburyh, PA, USA
Hangfeng He
hangfeng Caeaas www.eeasss.eeee.eee...
Department of Computer and Information Science University of Pennsylvania Philadelphía, PA, USA
Weijie Su
sww@wharton.com www.rnttoooooeeeecc.cmm edu
Deportment of Statistics and Data Science Wharton School, University of Pennsylvania Philadelphia, PA, USA
Reviewed on OpenReview: https: // openreview. net/ formm? id- 3PbzuMNQkp
Abstract
This paper proposes SplitSGD, dynamic learning rate schedule for stochastic optimiza- lion. This method decreases the learning rate for better adaplation to the local geometry of the objective function whenever a stationary phase is detected, that is, the iterates are likely local minimum. The detection is performed by splitting
to bounce at around a vicinity 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 sonariiy detection, SplitSGD is easy-to-im iin-t--mmmleeeett and essentially does not incur additional computational cost than standard SGD. Through scries of extensive experiments, show that this method is appropriate for both convex problems and training (non-convex) neural nelworks, 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 wide range of problems and, moreover, can yield better generalization performance than other adaptive gradient methods such as Adam.
1 Introduction
Many machine learning problems boil down to finding a minimizer 0* E Rd of a risk function taking the form
F(0) = E[
(1)
where f denotes loss function, 0 is the model parameter, and the random data point 2 = (X,v) contains feature vector X and its label In the case of finite population, for example, this problem is reduced to the empirical minimization problem. The touchstone method for minimizing (1] is stochastic gradient. descent (SGD). Starting from an initial point 0, SGD updates the iterates according to
O 0r T) g(,,, 7
(2)

---

Published in Transactions on Machine Learning Research (02/2024)
learning rate
0.15
Frequency
0.10
0.05
0.00
-1.0
-0.5
0.0
0.5
1.0
Figure Normalized dot product of averaged noisy gradients over 100 iterations. Stationarity depends on the learning rate: 1 corresponds to stationarity (purple), while n 0.1 corresponds to non stationarity (orange). Details in Section 2
for 2 0, where Th is the learning rate, { are i.i.d. copies of Z and g(0 Z) is the (sub-) gradient of f(0, 2) with respect to 0. The noisy gradient g(0, Z) is an unbiased estimate for the true gradient VF(0) in the sense that E [g Z)] = (F) for any
The convergence rate 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 vast literature on how to decrease this fundamental tuning parameter for improved convergence performance. In the pioneering work of Robbins & Monro (1951), the learning rate is set to O(1/t) for convex objectives. Later, it was recognized that a slowly decreasing learning rate in conjunction with iterate averaging leads to a faster rate of convergence for strongly convex and smooth objectives (Rupperi 1988 Polyak & Juditsky)
1992p. More recently, extensive effort has been devoted to incorporating preconditioning Seaiitioonnnn/Hessiaannn Hessians into learning rate selection rules (Duchi et al. [2011] Dauphin al.] 2015 Tan et al.) 2016). Among numerous proposals, simple yet widely employed approach to repeatedly halve the learning rale afler performing pre-determined number of iterations (see, for example, Bottou et al. 2018).
In this paper, we introduce new variant of SGD that we term SplitSGD with novel learning rate selection rule. At a high level, our new method is motivated by the following fact: an optimal learning rate should be adaptive to the informativeness of the noisy gradient g(O,, 1++ Roughly speaking, the informativeness is higher if the true gradient F(.)) is relatively large compared with the noise (F,))) g(O,, Zz+1) and vice versa. On the one hand, if the learning rate too small with respect the informativeness of the noisy gradient, SGD ma neses rather slow progress. On the other hand, the iterates would bounce around region of optimum of the objective if the learning rate is too large with respect the informativencss. The latter case corresponds to stationary phase in stochastic optimization (Murata] 1998 Chee & Toulis 2018), which necessitates the reduction of the learning rate for better convergence. Specifically, let тr be the stationary distribution for f when the learning rate is constant and set to From (2) one has that Eo-T, [g(0, Z)] = 0, and consequently that
(l((0)))) 2(0)). 201y =0
(3)
for ((1) (( Lidd nn and z(1, (22) s.d.d Z.
SplitSGD differs from other stochastic optimization procedures in its robust stationarity phase detection, which we refer to as the Splitting Diagnoslic. In short, this diagnostic runs two SGD threads initialized at the same iterate using independent data points (refers to Z in 2 and then performs hypothesis testing determine whether the learning rate leads to a stationary phase or not. The offectiveness of the Splitting Diagnostic is illustrated in Figure which reveals different patterns of dependence between the SGD threads with difference learning rates. Loosely speaking, in the stationary phase (in purple), the two SGD
2

---

Published in Transactions on Machine Learning Research (02/2024)
NON STATIONARY
STATIONARY
N6 77-
4
41
[1/77]
2
W
The architecture of SplitSGD. The initial learning rate is and the length of the first single thread is t1. If the diagnostic does not detect stationarity, the length and learning rate of the next thread remain unchanged. If stationarity is observed, we decrease the learning rate by factor and proportionally increase the length.
Figure 2:
threads behave as if they are independent due a large learning rale, and SplitSGD subsequently decreases the learning rate by some factor. In 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 to its adaptivity to the local geometry of the objective, thereby amning-insensitiee method for stochastic optimization. Its strength is confirmed by our
making SplitSGD experimental results in both convex and non-convex settings. In the latter, SplitSGD showed robustness with respect to the choice of the initial learning rate, and remarkable success in improving the test accuracy and avoiding overfitting compared to classic optimization procedures.
1.1 Related work
There is long history of detecting stationarity non-stationarity in stochastic optimization to improve
convergence rates (Yin 1989 Pflug 1990 Delyon & Juditsky 1993 Murata 1998). Perhaps the most relevant
work in this vein to the present paper is Chee & Toulis (2018). which builds on top of Pflug (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 consccutive gradients and, morcover, is not sensitive the local curvature of the current iterates due to unwanted influence from prior gradients. In contrast, the splitting stralegy, which is akin to HiGrad (Su & Zhu, 2018), allows our SplitSGD to concentrate
the current gradients and leverage the regained independence of gradicnts to test stationarity. Lately, Yaida (2019) and Lang et al. (2019) derive a stationarity detection rule that is based on gradients of mini-batch to tune the learning rate in SGD with momentum while Pesme et al. (2020) base their diagnostic on the distance between the current iterate and the last iterate where learning rate reduction happened.
From a different angle, another related line of work is concerned with the relationship between the informa- tiveness of gradients and the mini-hatch size (Keskar et al., 2016 Yin et al.. 2017 T.i 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 geomelry of the objective function and the noise level of the gradients, delivering a growing line of work that leverage the mini- batch gradient variance for learning rate selection (Byrd et al.) 2012; Balles et al. 2016
Balles & Hennig
2017
De et al. 2017 Zhang & Mitliagkas 2017
McCandlish ot al. 2018
2
The SplitSGD algorithm
In this section, we first develop the Splitting Diagnostic for stationarity detection, reported in Algorithm D followed by the introduction of SplitSGD, detailed in Algorithm 2
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 fg the initial value, even though later it will often have a different subscript based on the number of iterations already computed before starting the diagnostic. From the starting point, we two SGD threads, each consisting of windows of length i. For
3

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm Diagnostic(n, w, g, 0*))
1: e =00 = 8'
2: for = 1,..., w do
for 1,2 do
for j 0 .... I do
5: ((
(k)
(1-1)+1++1 (1-1)-45 96-1-111
6: end for
9." (0(h)
(1-1)++1 /l.)/l.1.
7:
end for
Q (
(1) (
9i
10: end for
11: if Ei= sign (Q:))/2 / 2 q: then
12: return OD (0 + 0 /2) TD =}
13: else
14: return 0D ( + (1) To =N} N}
15: end if
each thread k = 1,2, we define De (k)
_(0,0) z(41) and the iterates are
(k) 00 (K)
(4)
where E {0, .... wl 13. A similar splitting strategy can be also found in the HiGrad procedure introduced in Su & Zhu 2018). There, the authors the estimates produced by several parallel threads to obtain a confidence interval around 0*, keeping the learning rate constant and using decorrelating procedure. Here, instead, on every thread we compute the average noisy gradient in each window, indexed by i = 1,... w. which is
((h) (1-1)+11 1141
(K)
1-14)
2.
5
1=1
The length of cach window has the same function the mini-batch parameter mini-batch SGD Li et al., 2014), in the sense that a larger value of I aims to 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 in the windows in each thread.
Definition 1 For 1...., w, we define the gradient coherence with respect to the starting point of the Splitting Diagnostic for the learning rate n, and the length of each window I, as
Q.(0o, n. =( .9 -.)
(1)
(6)
We will drop the dependence from the parameters and refer to it simply as Qu.
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, it mcans that the signal is stronger than the noise, and the dynamic is still in its transient phase. On the contrary, as (3) suggests, when the gradient coherence is on average very close to zero, and it also assumes negative values thanks to its stochasticity, this indicates that the noise component in the gradient now dominant, and stationarity has been reached. Of course these values, no matter how large is, are subject some randomness. Our diagnostic then considers the signs of Q1.... Qu and returns result based on the proportion of negative Qi One output boolean value Tp, defined
4

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm SplitSGD( w. 4, B, 00
1: !/1 =
2: 01"h = -00
for b b= L,,,, B do
Run SGD with constant step size tis for to steps, starting from 0g
5:
Let the last update be ogaa
6: Dj = Diagnostic(no. w, (
7:
0- p..
8:
Tn, = then
Mb+1 . Th and 1o+1 L40/>]
10: elsc
11:
11 Tbb and 1d+1 to
12: end if
13:
end for
follows:
To { S if Σ sign (Q:))/2 w
N if E. sign (Q:))/2 < W.
where TD= = S indicates that stationarity has been detected, and TD = 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 as a starting point for following itcrations. We call it 0D == (0() + 0 (2) The gradient coherence has a similar flavor to the pflug diagnostic that is used in Chee & Toulis (2018). There, a running sum of the dot products of consecutive gradients from a single thread is stored, and stationarity declared when such statistic becomes negative. A downside of such strategy is that the initial positive dot products can have large impact the rest of the procedure. Because of an ill selected initial learning rate, it can happen that the running sum of the dot products approaches zero very slowly, making the stationarity detection less practical. We show in Section 4.1 how the Splitting Diagnostic improves on the pflug diagnostic by avoiding such problem.
2.2 The Algorithm
The Splitting Diagnostic can be employed in more sophisticated SGD procedure, which we call SplitSGD. We start by running the standard SGD with constant learning rate 17 for fixed number of iterations 61 Then, starting from o,, we use the the next 2/w updates verify if stationarity has been reached, using the Splitting Diagnostic. II stationarity is not detected, the next single thread has the same length 4 and learning rate as the previous one. On the contrary, if TD S, we realize that it is the time to decrease the learning rate by a factor E (0, At the same time we also increase the length of the single thread by a factor 1/2, as suggested by Bottou et al. (2018) in their procedure, later analyzed under the name of 1/D by (Chee& Toulis (2018). Notice that, if = O, then the learning rate gets deterministically decreased after each diagnostic since every Splitting Diagnostic will return Tn S. On the other extreme, if we set q q= 1, then the procedure maintains constant learning rate with high probability, since the only chance to decay the learning rate happens when all the gradient coherences are negative. Figure 2 illustrates what happens when the first diagnostic does not detect stationarity, but the second one does. SplitSGD puts together two crucial aspects: it employs the Splitting Diagnostic at deterministic times, but it does not deterministically decreases the learning rate. We will see in Section ! how both of these features combine to give advantage over existing methods. is important to notice that SplitSGD does not add relevant computational cost compared classic SGD. Although there are two threads that are used in some parts of the SplitSGD procedure, we i) decide their length in advance that they do not use the majority of the iterates compared to the single
5

---

Published in Transactions on Machine Learning Research (02/2024)
threads and fi) use averaging at the end of the Splitting Diagnostic, which makes the second thread useful in the computation of the minimizer, we will see in the experiment section. Moreover, the computation of the gradient coherence is small compared to the cost of training the model. A detailed explanation of SplitSGD is presented in Algorithm 2
3 Theoretical Guarantees for Stationarity Detection
This section develops theoretical guaranlees for the validity of our learning rate selection. Specifically, in the case of relatively small learning rate, we can imagine that, the number of iterations 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 t - and the learning rate is fixed, we would like the diagnostic to tell that we have reached stationarity, since we know that in this case the updates will oscillate around 0" Our first assumption concerns the convexity of the function F(0). It will not be used in Theorem in which we focus our attention on a neighborhood of 0g.
Assumption 3.1 The function F is strongly convex, with converity constant μ > 0. For all 01, 1,,
F(O1) 2 F(02) + (VF(0))) 02) + - 101 0211
and also VF())) VF 2 p 1101 82l1.
Assumption 3.2 The function is smooth, with smoothness parameter L> For all 0,, 02,
[VF())) LL- -22l.
<
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--1 as
E = ==0((11,, = g(0=-1, 2z) FF(0,-1)
(8)
and the filtration F;= oZI..... Z,). Then Et E F, and {etre= is a martingale difference sequence with respect to (F.) which means that E(c, [- 0. The covariance of the errors satisfies
[ [Fr-1] I m
min
where Omin S Tmax < 00 for any 0.
Our last assumption is on the noisy functions f(0, Z) and upper bound the moments of their gradient. We do not specify here since different values are used in the next two theorems, but the range for this parameter is m (2,4).
Assumption 3.4 Each function f(0, 7) is convex, and there erists a constant G such that E [0,g II1" Fi] < G for any O,.
Note that Assumption 3.3 imposes that the cigenvalue of a rank-one matrix finite, which relatively mild assumption, and Assumption 3.4 correspond to assumption H7 in Moulines & Bach (2011). We first show that there exists a learning rate sufficiently small such that the standard deviation sd(Q)) of any gradient. coherence is arbitrarily small compared to its expectation, and the expectation is positive when 0,,+1 is not very far from 6y. This implics that the probability of any gradient coherence to be negative, P(Q: < 0). is extremely small, which means that the Splitting Diagnostic will return Tn = N with high probability.
3.3 and 3.4 with m 4 hold, [[V) > 0 and we run t1 iterations before Splitting Diagnostic with w windows of length 1, then for any E (1, w) we can set n small enough to guarantee that
Theorem If Assumptions 3.2
sd(Q.) & (1(1.)) [Q.),

---

Published in Transactions on Machine Learning Research (02/2024)
Linear Regression with t 50
Logistic Regression with t, 50
0.3
0.05
0.01
0.05
0.15
Frequency
Frequency
0.10
0.05
0.0
0.00
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Normalized Qę
Normalized Q₂
Linear Regression with r 0.01
Logistic Regression with n 0.05
t
t
5000
0.20
5000
Frequency
0.3
Frequency
0.15
0.2
0.10
0.1
0.0
0.00
-1.0
0.0
1.0
-1.0
0.5
1.0
Normalized Qg
Normalized Q2
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 top panels show the behavior in Theorem 2 the two bottom panels the one in Theorem 3 In orange see non stationarity, while in purple distribution that will return stationarity for appropriate choice of w and q-
where (1, - -0 +0( +0) The proof is in Appendir
provide visual interpretation of this result. When the starting point of the SGD thread is sufficiently far from the minimizer 0r and 17 is sufficiently small, then all the mass of the distribution of Q; is concentrated positive values, meaning that the Splitting Diaguostic will not detect stationarity with high probability. In particular we can use Chebyshev inequality to get bound for TP(2 < 0) of the following form:
In the two top panels of Figure
P(Q: < 0) P(Q,, -(.
S <d(())//E(ej) 1i(
Cni 1) also depends on || [[F)() Fmax: and

---

Published in Transactions on Machine Learning Research (02/2024)
Note that to prove Theorem 2 we do not need to use the strong convexity Assumption 3.1 since, when 17(1 + is small, +1 is not very far from Og. In the next. Theorem we show that, if 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 To= = S with probability that can be made arbitrarily high. This is consistent with the fact that, as t + 0o, the iterates will start oscillating in a neighborhood of 0".
Theorem If Assumptions 3.1
3.2
3.3
and 3.4 with m 2 hold, then for any n S to. L N and
E (1..., w); t -> 00 we have
IE [QiIl S C2(1) sd sQ.),
where C2(n)= C2 + o(n). The proof is in Appendiz G
The result of this theorem is confirmed by what see in the bottom panels of Figure 3 There, most of the mass of Qi is on positive values if t1 = O, since the learning rate is sufficiently small and the starting point is not too close to the minimizer. But when we let the first thread run for longer, we see that the distribution of Qi is now centered around zero, with an expectation that is much smaller than its standard deviation. An appropriate choice of w and makes the probability that TD = S arbitrarily big. In the proof of Theorem B we make use of a result that is contained in Moulines & Bach (2011) and then subsequently improved in Needell et al. (2014) representing the dynamic of SGD with constant learning rate. For completeness we report its prool in Appendix
Lemma 4 If Assumptions 3.1
3.2
3.3
and 3.4 with m = hold, and S #B then for any t 2 0
E
[|0, 1-]
s (1
2n( 1.21))) E [110- 001 [|2]
G2
+ # L2'n'
The simulations in Figure show us that, once stationarity is reached, the distribution of the gradient coherence is fairly symmetric and centered around zero, so its sign will be approximately coin flip. In this situation, if l is large enough, the count of negative gradient coherences is approximately distributed as a Binomial with w number of trials, and 0.5 probability of success. Then we can set to control the probability of making a type I error rejecting stationarity after has been reached by making 2- sufficiently small. Notice that a very small value for q makes the type I error rate decrease but makes it easier to think that stationarily has been reached too early. In the Appendix [ we provide a simple visual becomes larger, while show in Figure !
1 >i (*)
interpretation to understand why this trade-off gets weaker with a simple experiment how the Splitting Diagnostic is detecting stationarity with the correct probability once stationarity is actually been reached. What we see is that when w is small the agreement is not perfect, but as it gets larger the theoretical and observed probabilities nearly overlap perfectly.
Finally, we provide a result on the convergence of SplitSGD. We leave for future work to prove the convergence rate of SplitSGD, which appears to be a very challenging problem.
Proposition 5 If Assumptions
3.3 and 3.4 with guaranteed to converge with probubility tending to 1 the number of diagnostics B + 0o.
3.1
3.2
2 hold, and n S th. then SplitSG is
Proof We first notice that the averaging at the end of each diagnostic can be ignored, and replaced by simply considering each diagnostic as a single thread made of wl iterates. For the first diagnostic, for example, we have that
E 10, - 1]
< E
(1) 21 4od
+ 022)
+
-20-
-13
2
[1le(1) [1 - -81 + E (1) tu
8" [|
4
+ - E ((0(2)
1
0-, 02) +00 8+)
+0t
2
< EE [110
80 2]
tut
+wo
8

---

Published in Transactions on Machine Learning Research (02/2024)
Linear Regression with n 0.05
Logistic Regression with 1) = 0.5
1.00
1.00
10
10
25
25
Probability of type lerrrr
Probability of type errrr
0.75
0.75
100
100
0.50
0.50
0.25
0.25
0.00
0.00
0.25
0.50
0.75
0.25
0.50
0.75
q
q
Figure 4: The probability of making type I error using the Splitting Diagnostic (thick lines) closely matches with the respective theoretical probability (thin lines), in both linear and logistic regression settings. In both settings considered 1000 experiments for each value of and we initialize Oo to be close to 0", with / = 10 and 17 sufficiently large to guarantee stationarity.
where we have used the fact that each thread identically distributed, together with the Cauchy- Scheaar incquality. The same inoquality, with appropriate indexes, is true for all the diagnostics.
Our proof is divided in two parts. First. we show that, in the extreme stationarity deterministically; the learning rate does not decay too fast and we still have convergence to 0* Then we prove that eventually the learning rate decreases to zero when the number of diagnostics goes to infinity. We initially notice that
where each diagnostic detects
(1 (1-2 1m7 12mb)) 2017 2 C1
where e₁ (0, 1). We also have
G2m G2i p L'mm
C2.8
We define L, to be the expected square distance from the minimizer, [[ 0-]]]] at the end of the h diagnostic, and Lo E [l|60 8" [1 If the learning rate decreases deterministically, then have that after the tt diagnostic, the learning rate is n7 and the length of the single thread is [4//"]]. By recursion, using Lemma in the main text, we have that
Gmm
L s (1 10-2-21 (p- Lou-L3ma 1) Lo +
1 L2
S c1 L, + C2 -/
1+1 To C2 big
c
$ ct h+1 Lo + 02 max c
Since C1 E (0, 1), this proves that LG + as the number diagnostics oc.
To prove that it is impossible for the learning rate to remain fixed on certain value for infinite many iterations, show that the probability that the learning rate reaches point where it never decreases is zero.

---

Published in Transactions on Machine Learning Research (02/2024)
We assume by contradiction that there exists point in the SplitSGD procedure where the learning rate is
'f and, from that moment, on, it is never reduced again. Following Dieuleveut et. al. (2017), we know that
the Markov chain { in (2) with constant learning rate ry" will converge in distribution to its stationary distribution Ty.. This mcans that
sup 8.2
[[O
E +
as T +
(10)
and if we let s ++1 we realisc that [E|g(0, 1++1)]1 + 0 as t + oc. Notice that also the Markov chain {g(Or, Z++1)) converges to a stationarity distribution when {0,} does, so we can use the Central Limit Theorem for Markov chains (Maxwell & Woodroofe 2000 to get that
VI Σ g(0t+s Z45+1) 4 N(O,0²)
as + oo
(11)
where o² > 0. We are now going use the fact that sign (Qt) sign (1 Q+). Thanks to write
we can now 11
1.Q, 1)14) Vi 1=1
1
(2) 1+11-111+k
(Xi + 0p (1), o,)) -X1, + (1)
where X1, are independent o²) (the independence being true for | + oo and i= 2,.,, w) and the 0p(1) are defined as + op. Since 1 Qi is approximately distributed as (Xi, X2), which has mean zero and positive variance, then for any choice of q < (w - 11//w we know that there is a positive probability a > that the proportion of negative gradient coherences observed is greater than g. which means that stationarity is detected. The probability that the learning rate 11* never decays is then bounded above by lim;- a²d 0, the learning rate gets eventually reduced with probability 1.
4
Experiments
We now compare the Splitting Diagnostic and SplitSGD procedure with other diagnostic and optimization techniques in both convex and non-convex settings.
4.1 Convex Objective
The setting is described in details in Appendix We use feature matrix X gaxd with standard normal entries and 1000, d = 20 and 07 1-2-1/2 1/2 for j 1,..., 20. The key parameters are 4, = 20, 1 50 and q 0.4. For both linear and logistic regression, use the streaming version of SGD where the batch size is set to 1, meaning that each data point in the training set is observed individually. A sensitivity analysis is in Section
Comparison between splitting and pflug diagnostic. In the top panels of Figure we compare the Splitting Diagnostic with the pflug Diagnostic introduced in Chee & Toulis (2018). The boxplots are obtained rumning both diagnostic procedures from a starting point 0, = 0, + where e' (0, 0.01 is multivariate Gaussian and f, has the same entries of 6* but in reversed order, so 0x.j 5 e- (d-1))/ for = 1,.., 20. Each experiment is repeated 100 times. For the Splitting Diagnostic, stationarity has been detected at the first time that a diagnostic gives result Tn S, and output the number of epochs up to that time. For the lul diagnostic, we stop when the running sum of dot products used in the procedure becomes negative at the end of an epoch. The maximum number of epochs is 1000, and the red horizontal bands represent 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
run SplitSGD and declare that
10

---

Published in Transactions on Machine Learning Research (02/2024)
Linear Regression, - 10
Logistic Regression, n =10²
1000
300
750
200
500
100
250
pflug
Split
pflug
Split
Linear Regression
Logistic Regression
2.5
-0.4
SplitSGD
SplitSGD
Half
Half
log(loss) after 100 epochs
2.0
Decreasing
log(loss) after 100 epochs
Decreasing
Constant
Constant
1.5
.0.8
10
0.5
-1.0
1e-05 3e-05 1e-04 3e-04 0.001 0.003
0.01 0.03
1e-04 3e-04 0.001 0.003 0.01
0.03
0.1
0.3
Initial Learning Rate
Initial Leaming Rate
Figure 5: (Top) Comparison between Splitting and pflug Diagnosties on linear and logistic regression. The y-axis represents the epochs and the red bands are the epochs where stationarity should be detected, while the boxplots represent the distribution of when the method actually detects stationarity. The pflug Diagnostics incurs in the risk of waiting too long after stationarity is reached, while the Splitting Diagnostic does not as a checkpoint is set every fixed number of iterations. (Bottom) comparison of the log(loss) achieved after 100 epochs between SplitSGD, S/ (Half) and SGD with constant or decreasing learning rate on linear and logistic regression. More details are in Section
risk of waiting for too long, when the initial dot products of consocutive noisy gradicnts are positive and large compared to the negative increments after stationarity is reached. The Splitting Diagnostic does not have this problem, then discarded, and only the new learning rate and starting point are stored. In Appendix B we show more configurations of learning rates and starting points.
checkpoint is set every fixed number of iterations. The previous computations are
Comparison between SplitSGD and other optimization procedures. Here we set the decay rate the standard value 7 0.5, and compare SplitSGD with SGD with constant learning rate n, SGD with decreasing learning rate 7) o 1/VE (where the initial learning rate is to 20n), and SGD (Bottou et al, 2018), where the learning rate is halved deterministically and the length of the next thread is double that of
11

---

Published in Transactions on Machine Learning Research (02/2024)
CNN on Fashion-MNIST
Resnet on CIFAR-10
91
90
Test Accuracy
Test Accuracy
90
SGD -
SGD n -
SGD 0.01
SGD - 0.03
85
Adam 1 0
FDR n 1
89
Adam 0.003
-DR -
FDR n 0.01
SplitGG 0.1
FDR 11 0.03
SplitSGD 0.01
SplitSG 0.01
SGD manual decay
SplttSG 0.03
88
80
50
75
100
100
200
300
Epochs
Epochs
Resnet CIFAR-100
LSTM Penn Treebank
180
SGD n
SGD 1-
70
Adam n 0.0003
160
FDR 0.1.1
* FDR n 0.3
SplitSGD 0.1
Test Test Accuracy
Test Perplexity
* SplitSGD n 0.3 0.3
60
140
SplitAdam - 0.0003
Adam 0.01
Adam 1l 0.005
120
SGD 0.1 0.1
SGD n 0.01
SpitSGD 0.1
SpliSGD n 0.01
100
40
100
200
300
50
100
150
Epochs
Epochs
Figure 6: Performance of SGD, Adam, FDR and SplitSGD in training various neural networks across different tasks and datasets: (top left) convolutional neural network 10-class computer vision task Fashion-MNIST, (lop right.) Resnet-18 on 10-class computer vision task on CIFAR-10, (bottom left) a Resnet-18 on a 100-class computer vision task on CIFAR-100, and (bottom right) an LSTM on a NLP prediction task on Penn Treebank. 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 Section
the previous one. For S/ set the length of the initial thread to be ti, the same for SplitSGD. In the bottom pancls of Figure 5 we report the log of the loss that we achieve after 100 epochs for different choices of the initial learning rate. It 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 the initial choice of the learning rate, performing well on wide range of initial learning rates.
12

---

Published in Transactions on Machine Learning Research (02/2024)
4.2 Deep Neural Networks
To train deep neural networks, instead of using the simple SGD with a. constant learning rate inside the SplitSGD procedure, we adopt SGD with momentum (Qian 1999), where the momentum parameter is set to 0.9. SGD with momentum is a 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 to 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 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 C As before, the length of the Diagnostic is set to be one epoch, and t 4. We compare SplitSGD against SGD with momentum and two other optimization methods widely used in practice. Adam (Kingma & Ba 2014], which has been developed as an improvement over AdaGrad (Duchi et al. 2011) and RMSprop (Tieleman et al., 2012), stores the decaying averages of the first and sccond moment of the past gradicnts and uses them to compute an adaptive learning rate for each parameter. FDR (Yaida) 2019), instead, uses a stationariy detection rule based on two fluctuationdiisiiaaton relations to decay the constant learning rate of SGD with momentum. We train our models using a range of different learning rates for all these mothods, and report the ones that show the best results. Notice that, although 77 = 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 t adaptive E {100, 1000], which gave similar results. It has also been proved that SGD generalizes better than Adam (Keskar & Socher 2017 Luo et al. 2019). We show that in many situations SplitSGD, using the same default parameters, can outperform both. In Figure D we report the average results of 5 runs. In Figure 12 in the appendix we consider the same plot but also add 90% confidence bands, omitted here for better readability.
Convolutional neural networks (CNNs). We consider a CNN with two convolutional layers and a final lincar layer trained on the Fashion-MNIST dataset (Xiao ct al. 2017). We set 17 E 2, 1e-1) 1) for SGD and SplitSGD, E (1e-2, 1e for FDR and 1/ E (3e-4, 4, le- 3, 3, 1e-2] for Adam. The batch size is 64 across all models. In the first panel of Figure [ we see the interesting fact that SGD, 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 docay is able to reach a belter 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.
Residual neural networks (ResNets) on Cifar-10. We consider a 18-layer ResNe and evaluate it on the CIFAR-10 dataset (Krizhevsky et al. 2009). We use the initial learning rates 1) E (le-3, 1e-2, 2, 1e-1} for SGD and SplitSGD, 1) E {1e-2, 1} for FDR and / E (3e-5, 3,-4, 3e333 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 at epoch 150 and 250. For consistency, we set the batch size to 128 across all models. In the second panel of Figure 0 we see classic behavior for SplitSGD. The averaging after the diagnostics makes the test accuracy peak, but the improvement is only momentary 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 17 = 1e-2 and 17 1c-1 is better than both SGD and Adam and that one setting achieves the same final (est accuracy of the manually tuned method in less epochs. The FDR method is showing excellent performance when 7 = 0.01 and a worse result when 1j = 0.1. In Appendix D similar plot obtained with the neural network VGG19.
we see a
Residual neural networks (ResNets) on Cifar-100. To show the performance of SplitSGD on a more complex classification task, we have also evaluated 18-layer ResNet on the CIFAR-100 dataset. Here only compared SplitSGD with SGD and Adam, and for all considered E (5e-3, 1e-2, 3e-1, le-1). As with CIFAR-10, we set the batch size to 128 across all models. In the third panel of 6 we reported the two best runs for each method, and from those we can see that SplitSGD is able to achieve a higher peak accuracy compared to the other methods. Here the Splitting Diagnostic appears to work slightly better when 7j = 0.01,
More details htte::///yyeccasee//////////lllr
13

---

Published in Transactions on Machine Learning Research (02/2024)
0.3
SGD SpinsGD
SGD SpirtGD
Frequency
Frequency
0.2
0.1
0.1
0.0
0.0
Figure 7: Histogram of the proportion of times that SplitSGD and SGD converged to the global minimum, which shows SplitSGD achieving the global minimum significantly more often. We run 100 simulations and evaluate the proportion 100 times each. We consider 1000 updates with r = 0.01 and SplitSGD averages its two threads every 200 updates. We consider a 2.1 (left) and (right...
but also for r) = 0.1 we can see at the very end that the method stabilizes to a higher test accuracy than the competitors.
Recurrent neural networks (RNNs). For RNNs, we evaluate two-layer LSTM (Hochreiter & Schmidhu- ber 1997) model on the Penn Treebank (Mareus et al. 1993) language modelling task. We use 17 E {0.1, 0.3,, 1.0] f1c-4, 1c-3) 3) for Adam and also introduce
for both SGD and SplitSGD, 17 E 0.3) } for FDR, AplitAdam, a method similar to SplitSGD, but with Adam in place of SGD with momentum. Here we set, the batch size to 20 across all models. As shown in the fourth panel of Figure 0 we can see that SplitSGD outperforms SGD and AplitAdam 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, 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 AplitAdain and SplitSGD, We postpone the theoretical understanding for this phenomena as our future work, but we make an attempt to develop an intuition on why this could be the case with an example.
We focus on the effect of averaging the two threads, and consider very simple polynomial loss landscape dimension with local minimum and global minimum. The loss surface f(x y) (a² + y² 14-11 -)) (a² y - a(x + y) 1) and the parameter regulates the distance and the difference in depth of the two minima. When 2 both minima global, when a > 2 the minimum located in the positive quadrant becomes the only global one and its basin of attraction gets larger. The histograms in Figure 7 refer to the proportion of times that the convergence happened to the global minimum instead of the local one when starting exactly on the saddle point located between them. In the left panel we set a = 2.1, while in the right we set a = 4, and we see that as a grows the advantage of averaging the two threads becomes more relevant, since the new starting point falls into the basin of attraction of the global minimum more often. This example is not intended to completely explain the difference in overfitting between SplitSGD and the other methods that we see in Figure 6 but just to provide intuition why the averaging could be beneficial.
For the deep neural networks considered here, SplitSGD shows better results compared to SGD and Adam, and exhibits strong robustness lo the choice of initial learning rates, which further verifies the effectiveness of SplitSGD in deep neural networks. The Splitting Diagnostic 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 a specific learning rate, but in the other setting is not improving over SGD, suggesting that its diagnostic does not work variety of different scenarios.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Linear Regression
Logistic Regression
38-4
1e-2 1| -
0.
1
log(/oss) after 100 epochs
- 30-5
--- 10-3
gpoce
0.05
aifa 100
0.00
-0.05
110 0.35)
(10 0.40)
110 0.40
1a000 (2))
[OP10
[SP0 oz)
(90'0
(0P0
(SP (9)
1se') 01)
00900 00)
1SP0 oL)
I98'0 02)
(0010 o2)
(s+00 oz)
(sc' op)
0 (P)
(str 'P)))
FNN
CNN
ResNet
92
1111--1
n-
1 0.03
* 111100.0
maxtie accurooy
m9000000 2000rat:
02
88
0.35
4.0030
200
14 966
14.0110
12.0200
0290
14.000
P 6/9)
Figure 8: Sensitivity analysis for SplitSGD with respect to the parameters w and q, appearing as the labels of the x-axis the form (w.q). In the convex setting (top plots) we consider the log loss achieved after 100 epochs, while for deep neural networks (bottom plots) we report the maximum of the test accuracy in 100 epochs. For ResNet, we add confidence band to highlight the stability of the results over different runs. Overall, SplitSGD achieves stable performance across various hyper-paramette parameterss setups; for details, see Section
4.3 Sensitivity Analysis for SplitSGD
In this section, analyse the impact of the byrem-parameters in the SplitSGD procedure. We focus q and w, while I changes so that the computational budget of each diagnostic is fixed at one epoch. In the top panels of Figure we analyse the sensitivity of SplitSGD to these two parameters in the convex setting, for both linear and logistic regression, and consider w E (10, 20,40) 40) and q E (0.35, 0.40, 0.45). The data are generated in the same way as those used 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 larger, the impact of these parameters very modest. When the initial learning rate is small, having quicker decay (i.. setting smaller) worsen the performance.
In the bottom pancls of Figure g we see the same analysis applied to the FeedForward Neural Network (FNN) described in Appendix D and the CNN used before, both trained on Fashion-MMNIST. Here we report the maximum test accuracy achieved when training for 100 epochs, and on the x-axis we have various configurations for g E (0.15,0) 0, 25, 0.35) and E (2,4,8) The results are very encouraging, showing that SplitSGD robust with respect the choice of these parameters also in non-convex settings. In the last plot of the bottom we also run four simulation with each pair of and q that different from the
15

---

Published in Transactions on Machine Learning Research (02/2024)
default values used in Figure 6 For each run compute the maximum test accuracy 350 epochs and for each (w, we report both the median (solid line) and a shaded region corresponding to the minimum and maximun over the four experiments. What we observe is that the variability is in general pretty small, confirming that the goodness the SplitSGD performance not to be attributed to a fine tuning of these two parameters.
5 Conclusion and Future Work
We have developed a novel optimization method called SplitSGD, that works by splitting the SGD thread for stationarity detection. Extensive simulation studies show that this method robust to the choice of the initial learning rate variely of optimization lasks, compared to classic adaptive and non-adaptive methods. Moreover, SplitSGD on certain deep neural network architectures outperforms classic SGD, Adam and FDR in terms of the test accuracy, and can sometime limit greatly the impact of overfitting. As the critical element underlying SplitSGD, the Splitting Diagnostic is 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 a new relevant parameter that regulates the rate at which the learning rate is adaptively decreased. Our simulations suggest the use of two different values depending on the context. slower decrease, g = 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 strategics across different layers of the neural networks.
References
Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. arXiv preprint arxiv: 705. 07770777, 2017.
Lukas Balles, Javier Romero, and Philipp Hennig. Coupling adaptive batch sizes with learning rates. arXiv preprint trXi::1612.00000 050066, 2016.
Yoshua Bengio. Practical recommendations for gradient-based training of deep architectures. In Neural nelworks: Tricks of the trade, pp. 437 478. Springer, 2012.
Leon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31 311, 2018.
Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning. Mathematical programming, 134(1):127 -55, 2012.
Jerry Chee and Panos Toulis. Convergence diagnostics for stochastic gradient descent with constant learning rate. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Stotistics, volume 84 of Proceedings of Machine Learning Reseorch, pp. 1476-1485. PMLR, 09-11 Apr 2018.
Yann Dauphin, Harm De Vries, and Yoshua Bengio. Equilibrated adaptive learning rates for non-convex optimization. In Advances in neural information processing systems, pp. 1504-15051 1512,,11,411 2015.
Soham De, Abhay Yadav, David Jacobs, and Tom Goldstein. Automated inference with adaptive batches. In Artificial Intelligence and Statistics, pp. 1504-1513, 2017.
Bernard Delyon and Anatoli Juditsky, Accelerated stochastic approximation. SIAM Journal on Optimization, 34)):868-881, 1993.
Aymeric Diculeveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. orXiv preprinl urXiv:1707.06336 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 22(Jul):121-2133 2011.
16

---

Published in Transactions on Machine Learning Research (02/2024)
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735-178) 1997.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint IrXii:1712.076:0 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On barce-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arxi 1roX::6609.000 048964436, 2016.
Diederik P Kingma and Jimmy Ba. Adam:
method for stochastic optimization. arXiv preprinl
arXiv:1412.6986 6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Hunter Lang, Pengchuan Zhang, and Lin Xiao. Using statistics to automate stochastic optimization. arXiv preprinl Xiv: 09785, 2019.
Chris Junchi Li, Lei Li, Junyang Qian, and Jian-Guo Liu. Batch size matters: diffussio approximation framework on nonconvex stochastic gradient descent. stat, 1050:22, 2017.
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J Smola. Efficient mini-batch training for stochastic oplimization. In Proceedings of the 20th ACM SIGKDD internalional conference Knowledge discovery and data mining, pp. 661-670. ACM, 2014.
Liangehen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: 1902 1904.0944, 2019.
Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building large annotated corpus of english: The penn treebank. 1993.
Michael Maxwell and Michael Woodroofe. Central limit theorems for additive functionals of markov chains. Annals of probability, pp. 113-724, 2000.
Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAl Dota Team. An empirical model of large- training. Xiv preprint N81:1812.06100 2018.
Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pp. 451 459, 2011.
Noboru Murata. statistical study of on-line learning. Online Learning and Neural Networks. Cambridge University Press, Cambridge, UK, pp. 63 18-92, 1998.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in Neural Information Processing Systems, pp. 1017-1025, 2014.
Scott Pesme, Aymeric Dieuleveut, and Nicolas Flammarion. On convergence-diaggootie based step sizes for stochastic gradient descent. arXiv preprint orXiw:2007.0053) 2020.
Georg Ch Pflug. Non-asymptotic confidence bounds for stochastic approximation algorithms with constant. step size. Monatshefte für Mathematik, 110(3-4):297 314, 1990.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-85) 855, 1992.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12(1):145-115 151, 1999.
17

---

Published in Transactions on Machine Learning Research (02/2024)
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annols of mathematical stalislics, pp. 400-407, 1951.
David Ruppert. Efficient estimations from a slowly convergent Robbins Bobbins-Moonro process. Technical report, Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1988.
Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V Le. Don't decay the learning rate, increase the batch size. arXiv preprint arXft:1711.004889 2017.
Weijie J Su and Yuancheng Zhu. Uncertainty quantification for online learning and stochastic approximation via hierarchical incremental gradient descent. aiv preprint arXiv: 018.8800888887 2018.
Tla Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139 1147, 2013.
Conghui Tan, Shiqian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 685-693, 2016.
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26 31, 2012.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.077. 2017.
Sho Yaida. Fluetuation
relations for stochastic gradient descent. In ICLR, 2019.
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. Gradient diversity: key ingredient for scalable distributed learning. arXiv preprint arXiv: 706.06996606 2017.
George Yin. Stopping times for stochastic approximation. In Modern Optimal Control: A Conference in Honor of Solomon Lefschetz and Joseph P. LaSalle, pp. 409 420, 1989.
Jian Zhang and loannis Mitliagkas. Yellowfin and the art of momentum tuning. arXiv preprint Xiv: 0tl::7706000 770600371., 2017.
A Description of the convex setting and choice of the tolerance parameter q
For the experiments in the convex setting we use a feature mairix X E Rexd with standard normal entries and n = 1000, 20. We set 07 = 5 -j/2 for j = 1.., 20 to guarantee some difference in the entries. We generate the linear data as y/ = X, 0* + ei, where E; ~ (O, 1), and the data for logistic regression from a Bernoulli with probability (1 + xx-0'' )-1 The other parameters that are used through all Section 4.1 are 20 of size = 50 (so that each diagnostic consists of one epoch), the length of
the numbers of windows the first single thread t = 4 epochs, and the acceptance proportion q= 0.4.
As we say in the main text, in general we would like w, I, t1 and the number of diagnostics B to be as large as possible, given the computational budget that we have. The tolerance g, instead, is more tricky. In Theorem 3 and Figure g we shown that, as 6 + 0o, the distribution of the sign of the gradient coherence is approximately coin flip, provided that 7) is small enough. This means that, once stationarity is reached, we want q not be too big, so that we will not observe a proportion of negative gradient coherences smaller than q just by chance too often (and crroncously think that stationarity has not been reached yet). If we were then to assume independence between the Qi, we should set y to control the probability of type I error (returning Tp N even though stationarity has been reached), which is
[w-g1= -1
Σ
w
2
i
0=0
18

---

Published in Transactions on Machine Learning Research (02/2024)
0.12
0.09
Denruhy
0.05
045
0.00
0.00
0.0
0.4 2.5 0.6
32
0.0
33
0.4 2.5
0.5
Figure 9: Contimuous representation of the probability mass function of Binomial distributions. On the left. we set w = 30 and g = 0.4, on the right w = 75 and q= 0.4, for both the probability of success (observing a negative gradient coherence) is p E {0.2, 0.25,,.5.5. When p = 0.5 (stationarity) the type error happens with probability approximated by the shaded blue region. When p 0.5 (non stationarity) we erroneously declare stationarity with probability approximated by the shaded red and orange region.
However, we set q to be too small, then in the initial phases of the procedure we might think that we have already reached stationarity only because by chance observed a proportion of negative dot products larger than q. This trade-off, represented in Figure g is particularly relevant if we cannot afford a large nunber of windows w, but it loses importance as grows.
B Comparison with pflug Diagnostic with different parameters
In Figure 10 and Figure we see other configurations for the experiment reported in the top pancls of Figure There, the starting point was set to be around 6s, where 8s., = 5 e (d--)// for j = 1,..., 20. Here we consider the same starting point for the panels on the right. (for both linear and logistic regression) but a smaller learning rate. In both cases it is extremely clear that the pflug Diagnostic is detecting stationarity too late, and often (in the case of linear regression) running to the end of the budget. This can be big problem in practice, because after stationarity has been reached all the iterations that keep using the same learning rate are not going to improve convergence, and are fundamentally wasted. In the left and middle panel of both figures we consider a starting point for the procedures around the minimizer 0* In this scenario, for both larger and smaller learning rates, we see that both procedure are either very precise or detect stationarity bit too early. This a smaller problem in practice, since at that point the learning rate is reduced but the SGD procedures keep running, even if with a smaller learning rate. The speed of convergence is then slower, but the steps that we make are still important towards convergence.
C Changes to the SplitSGD procedure in deep learning
The differences between the SplitSGD procedure that we analysed in Scction 2 and its adaptation to deep learning are the following:
momentum of SGD: while in the convex setting study the behavior of vanilla SGD, when training deep neural networks the standard choice is to use SGD with momentum (Sutskever et al. 2013), which updates as
Ad, 13.08_1 Th g(0, Ze+1)
0,+1 0, A0t
(12)
19

---

Published in Transactions on Machine Learning Research (02/2024)
Linear Regression, 10
Linear Regression, 10
Linear Regression, 10
1000
50
40
100
750
30
500
20
250
10
pflug
Split
pflu
Split
pflug
Split
Figure 10: (left) starting around 8", large learning rate. (middle) starting around 0", small learning rate. (right) starting around Og, small learning rale.
Logistic Regression, n= 10
Logistic Regression, 1
Logistic Regression, 1
125
1000
100
750
40
75
500
60
20
250
20
pflug
Split
pfug
Split
pflug
Split
Figure 11: (left) starting around 8", large learning rate. (middle) starting around 0*, small learning rate. (right) starting around 0s, small learning rate.
20

---

Published in Transactions on Machine Learning Research (02/2024)
If the learning rate is kept constant, SGD with momentum still goes through transient phase before reaching stationarity. Even in this case, we already saw in (3), we have that Bø [g( 2) 0 since we see from (12) that Egwa, [A0] = 0. This justifies the use of the gradient coherence as defined in ( also when considering SGD with momentum.
gradient coherence on layers: when considering a parameter space of dimension d, the gradient coherence is dot product of two d-dimensional vectors. In deep learning, the parameter space is usually extremely large, so we decided to divide these vectors into pieces to try to extract more information about the stationarity of the SGD updates, by computing the dot product of each of the pieces. In practice, let's divide the vectors u and into p pieces not necessarily of equal length, so that e (#1, v2...., Up) and u = (u1, U2, "pp..)). Instead of computing the single dot. product (v, u) we store the p dot products ut), In this way, we can also relax the trade-off between and w (remember that want to allocate single epoch to the diagnostic, that 2/w is fixed to be the size of the training set). By computing more than single value of Q for each pair of vectors, allow to set w smaller.
A natural division of the parameter space into smaller pieces comes from the layers of the network, each time compule the gradient coherence of the two threads we actually compute a separate value for each layer and then store all of them together. In the final count, as we did in the non-convex setting, we look at the proportion of these values that are negative to decide whether to decay the learning rate.
length of the single thread: since training deep neural networks is usually computationally expensive, we decided not to increase the length of the single thread after stationarity was detected. This is made simply to avoid situations where stationarity is detected early and the length of the single thread increases so fast that we do not have time to decay the learning rate by much before reaching the end of the computational budget that we allocated.
hyperparameters for the diagnostic: we set the relevant peprpaarametess w and to take value w = 4 and = 0.25. The value of w is much smaller than the one used in the convex setting for the reason explained above that we compute the gradient coherence separately for each layer. With this choice, we can dedicate 1/8 of the updates each epoch to compute for each thread the average of The gradients and be sure that we averaged out a lot of the noise. The choice of setting y = 0.25 comes from the empirical results that we observed, and a deeper study of this parameter is probably needed. We performed sensitivity analysis on these two paramcters in Section 4.3 and noticed that departure from these values is not changing the performance by much.
Other experiments in deep learning
We add here the description of two more experiments in Deep Learning that did not fit in the main body of
the paper, together with the plots that we already included in Figure 6 but this time with the addition of the 90% confidence bands. We see that the Splitting Diagnostic increases the variability of SplitSGD with respect other methods in some settings, but the interpretation that we gave in Section 4.2 of the better performance of SpDitSGD and the lack of overfitting holds.
21

---

Published in Transactions on Machine Learning Research (02/2024)
CNN on Fashion-MNIST
Resnet on CIFAR-10
LSTM on Penn Treebank
-
n 0.3
Adam 0,0003
FDR q --
FDR n - 0.3
Spitt 0.11
Test Accuracy
Tedt Accuracy
Perpleslyy
SpitBGD 0-0.3
140
SpitAdam -0000m 0.0003
0.1
Adam 1) 000003
S3D - 0.03
80
Adam -
FDR n- 0.01
FDR n- 0.1
120
FDR 1 -10.01
FDR y 0.03
Sp - 0.01
SpirsGD 1y 0.1
SplisGD n 0.01
SpinSGD 0.03
SGD manual decay
25
50
75
100
100
200
300
50
100
150
Epochs
Epochs
Epochs
Figure 12: This is the same Figure 6 but here we also added 90% confidence bands for each method.
Feedforward neural networks (FNNs). We train FNN with three hidden layers of size 256, 128 and 64 on the Fashion-MNIST dataset (Xiao et al. 2017). The network is fully connected, with ReLu activation functions. The imitial learning rates are E 11e-2,30 3e 2, 1e-1} for SGD and SplitSGD and (3e-4, 1e-3,3e-33 for Adam. In the first panel of Figure 13 we see that most methods achieve very good accuracy, but SplitSGD reaches the overall best test accuracy when 7j = lc-1 and great accuracy with small oscillations when 1j = 3. The peaks in the SplitSGD performance are usually due the averaging, while the smaller oscillations are due to the learning rate decay.
VGG19. When training the neural network VGG1 CIFAR-10, observe similar behavior to what already shown when training ResNet (second panel of Figure 6 SplitSGD, with both learning rates 1e-1 and 1c-2 achieves the same test accuracy of the manually tuned SGD, but in less epochs, and beats the performance of SGD and Adam. Also here it is possible to see the spikes given by the averaging, followed by the smoothing caused by the learning rate decay.
FNN on Fashion-MNIST
VGG19 on
90
Accurscy
85
85
80
85
90
85
100
80
SGD - 0.1
80
SGD - 0.1
SGD 0.01
SGD 0.03
Adam 0.0003
Adam 0.003
75
SplrtGD n
Sp 0.1
SpiriGD n 0.01
SpiniGD 0.03
SGD manusl decay
75
70
25
50
75
100
100
200
300
Epochs
Epochs
Figure 13: Compare the accuracy of SGD, Adam and SplitSGD in training FNN MaSSI (left) and VGG19 on CIFAR-10 (right).
E
Lemmas
Proof of Lemma
More details be found in http::////pcccccoo/////////tttts
22

---

Published in Transactions on Machine Learning Research (02/2024)
Proof This proof can be easily adapted from Moulines & Bach 2011
From the recursive definition of 0g
one has
E |10, 0- 0- - (1 - 2n( - L L))) E [1|0--1- 0 + 22
This inequality can be recursively applied to obtain the desired result
t-1
E 1100 0-|13] - (1- 1--10 -2n(1 - I²n1))² [100 - 0-1
20
Σ
(1 - 21/u - I,21))²
1=0
G²n
s (1 2n(w L2 [100 0-1131
1 - 11
This lemma represents the dynamic of SGD with constant learning rate, where the dependence from the starting point vanishes exponentially fast, but there a term dependent on yJ that is not vanishing even for large
Lemma 6 If Assumplion 3.4 with m holds, then for any 1, E N one has
E [1101++ 0ell* Fil 1ndaa
Proof For any j I,...,, let By be vector of length n. Applying Cauchy-Schwand inequality twice, we get
2
1
11
1
2111
Σ
Σ
||5
3
i=1
jml
j
2
12
Σ || 112
<
13
Σ
|
(13)
j=1
Since
i-1
Octi = O, - Σ
g(0e+ji Zz4j+1);
j=U
then we can use the fact that F& S Fk+1 for any k together with Assumption 3.4 and 13 to get that
E [1100++ 0111 Fi] = = E
Σ 1=0
g(0r+j. Ze+f+1)ll Fe
S $n'²'
E [1l Z+s+1)ll Fi]
j=0
i-1
1/ 4,3 Σ
E E [1lg((0+5))) Z1+++1)1
Fetsl [i]
1=0
SG4
S 4 G
Note that this is a bound that considers the worst case in which all the noisy gradient updates point in the same direction and are of norm G.
Remark 7 We can obviously use the same bound for the unconditional squared norm, since
E [[]0 0e11*] E [B[ 0.11" [i]]] s "/A
23

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma 8 If Assumption 3.2 and 3.4 with 2 hold, then for any i= 1, 1..., and l 1,2 have that
[IVF -F (0))) Fi] - (T.1 - Ooll + LnGrre
Proof By adding and subtracting (F:))), and by Lemma we get.
E [IVF((0 VF F. - |IVF( (4) VF(0.) - VF |
IIVF((.) VF
[|VF(( VF(0)) F
+ +2/ VF -
VF(00)II Fr
$ L2 - 20 + L' [10 -
Fi + +222 - Poll
[1044] - Pell Fi)
< 10 0o11 + 13 22 0o Ir
(L| 0oll + LnjGi)
Remark 9 When we consider the unconditional distance of the gradients, we can simply use smoothness and Remark to get
E VF(0 VFF(0)) < LE [10 - 00ll3| s (t +
which is the same result that we obtain from Lemma 8 if at the end bound ||0: Boll with its expectation, and use the fact that E [1|0, Ooll] S T/GL.
Lemma 10 If Assumption 3.2 and 3.4 with 2 hold, then for any i I,..., l and k 1,2 have that
1) E |IF
F
s (II) + L10, Poll + LnGi)²
i) |IVE
F
- (4110, 0|
+ LnGii²
Proof We add and subtract (F.))) to the gradient on the left hand side, and apply Lemma 6
E
F. = E (F - VF(O) Fi || +
VF()))1 Fr [VF(( (F Fr
+ +
|VF 1.2 [10 0.11 F. + 2 E [10
0.11 Fi]
|| -
LnGi
(14)
To get part i) we repeat the same trick, this time adding and subtracting VF((o) to the terms that contain
V F()))
14
- VF(A)]
+ +1 VF(()) -F LnGi
< |1226///--211000000-222221111110 0oll
112 L
=(IVF(00)] L|)0 - Ln) Lny
24

---

Published in Transactions on Machine Learning Research (02/2024)
To get part ii), instead, we can add f and get
14
12 8- + 121) +210, 0011 L
(L| 8*11 + LnGi)²
Remark 11 For the unconditional squared norm of the gradient we again obtain the some bound as if in we were considering El| - Oall] I r/Gt instead of just the argument of the expectation.
Lemma 10
= = [E - VF(0)
E
(1VFFO(4)11
(|V + E VF - - VF((6)1
+ +2 (1VF(00 VF
[ +1 +
1))²
F Proof of Theorem 2
To slightly simplify the notation, we consider only Q1. For the following windows, the calculations are equal and just involve some more terms, that are negligible if v is small enough. We assume that the Splitting Diagnostic starts after t iterations have already been made. We use the idea that, for a fixed 6, if the learning rate is sufficiently small, the SGD iterate 9, and 6g will not be very far apart. In particular we will use n small enough such that 17- (t + I) is small, making every term of order Of7² + t)*) negligible for Thanks to the conditional independence of the errors, the expectation of Q1 can be written only in terms of the true gradients.
E [Q1
Σ
Σ
E ((000)))0001)
12
i=0
|-1
+ + vFO + +c
12
Σ
(VF(O vF(.
(15)
12 1=0
1=0
25

---

Published in Transactions on Machine Learning Research (02/2024)
We now add and subtract (F6))), and use L-smoothness and Remark to provide lower bound for E [Q1].
From 15 we get.
E
[Q1]
VF((O) + (VF( VF(()))
-V (F(O))) -
+E
(FF()))
- (VF( - [F(W)))
+E
2 ||
3ΣΣ
[I - VF(())] - -VF(6]]
1
[|VF((0)] /IVF(( VF
E
E
(1FF(80)I- - -
(16)
2 ||VF(00)11
ΣΣ
B [10 0011]]
E [1000] -0013)
==
2L
Σ
|VF
E [110 061l
7
> ||VF(00)11
(17)
Notice that, in the extreme case where 77 = O, we simply have E[Q:] 2
|/F(())]] which actually an
equality, since would have 0, Og and the noisy gradient step would be g(On, Zz), whose expectation
26

---

Published in Transactions on Machine Learning Research (02/2024)
is just FF(o)). We now expand the second moment, and there are lot of terms to be considered separately.
1 E [ E
((0 142.
Σ
((0())) (11)))))
j=U
27
E
(F(O
((0
/F(O (++)) + c(0
1=
E
FF
VF(O2))
+E
VF
((0
11
)7
1-1
(
VF(O
((07))
E
+E
5=0
j=
111
IV
2E
Σ (
(00
(2)
t+k
k=0
22
FF 444)
VF(O
(+h)
(F(O(()) (
k=0
VS
2E
V M4
2
E
VII
2E
(2)
Σ
VFOO
1=
k=0
VIII
-2
c(0()))
11) t-)
c(012)
(+kk
1=0
k=
1x
+2E
FF(O
Σ
>
1=0
In the squared terms to IV, the errors are independent from the other argument of the dot product, conditional on F,, since they are evaluated on different threads. However, in the double products (V to X), some errors are used to generate the subsequent values of the SGD iterates on the same thread. This means that cannot just ignore them, but we instead have to carefully find upper bound for each one.
27

---

Published in Transactions on Machine Learning Research (02/2024)
In I we use the Cauchy-Sor Sahucy-Schhwrz inequality and Lemma 10 after exploiting the independence of the two threads conditional on Ft.
)7
(VFIOH)). |
E
V
S max E
$ 11 max E
E
| (
[i]
E [ |r]]]
< 1 E -10 Lm
2 1 E [1
+6ll+ LnGa]
+ +1 (t+)
In the first approximate incquality denoted by S. we have included most of the terms of the expansion in the (177(1 + 1)²), even lechnically we could have done it only after taking the expected value. Notice that here it was important to have a bound in Remark 7 up to the fourth order.
Terms II and III are equal, since the two threads are identically distributed, and the errors in one thread are a martingale difference sequence independent from the updates in the other thread. We will use the bound for the error norm
E || Fi| = E |/. F.] E [tr(cee)
Fi S d maar
(18)
which is a consequence of Assumption the last line we use Remark
3.3 and condition on Ft to use independence of the errors.
I
27
E
VF
(2)
ΣE
F (10)) (tt)
1=0
2
max
2 ||
6 max E E [|e 11
Fi
E
|F
do damaz max E
||
13 do maz (1IV)(0))l1 + 2/ (000//00)))(((((( +0) 1)3))
In IV, we use the conditional independence of the two threads, and the fact that the errors are a martingale difference sequence, to cancel out all the cross products. An upper bound is then
Σ C0
(2) } (ct.)
E
E
1=0
E
12
1|<:3311
E
E
[i
I [1 1P P1F.)
< l Pooo mar
Now we start dealing with the double products. The problem here is that these terms are not all null, since the errors are used in the subsequent updates in the same thread, and they are then not independent.
28

---

Published in Transactions on Machine Learning Research (02/2024)
V and VI are distributed in the same way. We can cancel out some terms using the conditional independence given Ft. and use the conditional version of Cauchy-Schward inequality separately on the two threads.
Σ v
WoroH. Ea00)) )
E
B
(Fr(O
1-1
Σ
E
=[((r(8)) + -vr(e)))))(
ve(ew)) vV((0) + (Vr(O - vr((o))
x (VVF(8))+ + (FF(O)) VF(00) -c0021aa
Σ
E
[-]
(FF(B)), (F(O()) -
((FTE))))) -
(VF((0).
B
- vF(O.T) vr(e))) x
E
- -V10).)))
|1
|IF - vr(O)) (1:
+(]VF((001
E -
V - -F((0)) -|(00)
k=A
+ +1/60)
Σ
-11F(00)) v=(0))I -(000)1-11((00))) 1K(0001)
Σ
-
-
-
VF(O))I
1|< (1(
We bound the four pieces soparately. For the first, we can just apply Cauchy-Schwarz and L- smoothness, logether with Remark 7
E [IVF(O - VF(Ob)I [|(00[00]]
-1001) < I E [ - -bb1p] .E [[lk(0[_)11))
/
S dar LnGG(t +1)
29

---

Published in Transactions on Machine Learning Research (02/2024)
The bound for the second and third term is equal. We use the conditional independence of the two threads and Lemma g
E
- -1F( - VF((6)] ||e(0
(4)
E
E
[IVE( - |IE
Fi]
[F 24h - VF(6))] [i]]
X
E
(I - VF(00)1 Fi
E
[1 (102))11 1 Fr)
x E
(V - VF(O6)]| Fi
da
- [L]]0 0oll + L
< da (1++1)
The last term again makes use of conditional independence and Lemma S
E
(F(0)) VF(0))]
(1)
E
E
VF(B))] 1
E
VF(ON)I V 11000 FA
E
||VF
VF(06) | E - VF(00)112 IFr
E (FF( VF(O0)|2 F.] E (c(o(())1 Fi]
domar [[[L]]0; - 0oll + LnG())]]
v domar G² + 1)3
The last inequality follows from the use of Remark 7 to bound the moments of ||0 -foll up to order three.
The upper bound for VII and VIII the same, even if the error terms are different positions. Again invoke conditional independence to get rid of the dot products that only contain F
30

---

Published in Transactions on Machine Learning Research (02/2024)
and subsequently apply Cauchy-Schwarz inequality.
1-1 ((0 H4th E
)
E
==
[[(F((0)) + (FFe))))))) (c(o
VF((6) + (VE(O
Σ e
[((VFIO!!) VF((.), VF(()).VF(0))) -VF(6)) (10Tt))
S 2
Σ
E
[100 8oll 2011-1102 - Boll ||c( (I<((
kj,bkk=
S 2
Σ
E
E [1004] -boll ||c( Fi] x
xB
[1004]
-
Boll - Tell-Ilee0 1|((o Fi]
< 2
Σ
E
E [1o0 0011 Fi] E [|e(o(Hh)1e Fi]x x
kmm
XV E
|1000
0u Fi|]
E [|c Fi
< G + +12dda do maz
Also the upper bounds for IX and X are equal. In the first one, when k fj we can condition on Fll) and F (t.5 to get that the expectation is null. Then we are only left with a sum on three indexes i,j, h k j. In the last passage we again condition on the appropriate o-algebras to bound separately the two threads.
I
E
Σ
Σ
(
(00))) Σ
( 2tt
1=0
Σ
E
(FF(0)) + (VF(O -vF())))))))))))))))))))) .(022)) (<10th))
ij.
1-1
Σ
K (FF(O!))) - VF(O)), ( (c(0
E
i.j.
1-1
Σ k
E
[VF
E E ( (+)) - VF( - (I((0 Fi] E
[Ic(0[@])11 [i]]]
i.j.
< 13 LmG + l) (domaz) 3/2
31

---

Published in Transactions on Machine Learning Research (02/2024)
We put together all these upper bounds, leaving in extended form all the terms that are more significant than (11) + 1)?). We get
Var (Q1) = E [Q]] E 1Q12
2 V F ((0)) (0o) do
d maz
12
4do Addo VF(OO))LC((+)) + 2LG(L + ()n 33/2
+ n.
+ / (SLGIV 2
1)V do do + O1 + 1)3)
which immediately translates to a bound for the standard deviation of the following form
V (0o)] 2d
doman
sd (Q11) S
(19)
vi
1/2
+ -カ. (SLGIIVF(OO)) +00 1) do mar
(Ado [FF()
2LG(t + () max )3/2
1/2
+ +O((t (()(()))))
We combine desired incquality
19 with the fact, consequence of 16 that E[Q.// 2 1 O(n( + ()), to get the
sd(Q1) $ (1, [[Q1)
where
1
V 2do max
do dōmax
()
vi
1/2
-カ. (SLGI + + l) do
.j. (Ado VF LG(t +1) 2LG(t () max) 33/2
1/2
This confirms that (i(n,)) -1/V/ -(o+))==00////++0/>+++)+
G Proof of Theorem
As before, we only consider Q1 for simplicity. To provide an upper bound for [E[Qi]], we use the fact that FF((") = 0 together with Assumption 3.2 Starting from 15 we have
H 1
(VF(O (VF
E
[[Qi]
E
K=
E
IVF( - VF(O')]]
p2
[1o82 - 0'l1 -10 - 8r]]
E
12
122
[1002 - 011 [1000] 111
<
12
1=
32

---

Published in Transactions on Machine Learning Research (02/2024)
Now we use Lemma that states that, for 17 S 12:
E [100 0--13] 2 (1 - 22(( - L2) E [110 0-11 + G
(20)
1 122m)
As t + oo we have that E [100, 1-]] < ب L-smoothness combined with (20) also gets
G2
E [[VE((})]]]
as t + co.
(21)
Lin
Since the first term of 20 is decreasing in t, bound the expectation of Q1 is
E [Q1]] s L2 (11 2n L2r))) E
- - 0- + G²
(22)
11 12
To deal with the second moment, introduce the notation
(0)) S = Σ g (K) 440 ((
Σ VF
Σ
((0 = Gp + Ck-
where G is the true signal in the first window of thread le and 6 the related noise. Conditional on Fr, the random variables S1 and S2 are independent and identically distributed. Then we can wrile
1 E = E [(S1, = [ STST 82) =E (f
E
(B Tr (E{E [S Fi] E [S2 Fi]))
Tr (B(B [F((²)
The goal is now to show that the matrix E [ Fi] is positive definite, and provide lower bound for its second moment using the fact that if A AI for X 2 then 2 = X²T. We write
E SSSST F = E [G]
+
e1 (G1 + e1) [FF
E
G
FF E G F + E [e [F]]
+
E [eee [F]
We immediately have that E G
F
0, because, for any E Rd,
E
G
F
E
G.G & F E || Gil 1F 2 0.
Moreover we can also find an easy lower bound for the error term using Assumption
3.3
)
E Teee
FF]
=
E
Σ
(4t)
(
F
E T.
(100))
((
==0
I Fmin
To lower bound the remaining terms we introduce a simple Lemma.
Lemma 12 If u. RRd, then uh + out -2|]u]] ||o|I-T
33

---

Published in Transactions on Machine Learning Research (02/2024)
Proof We apply the Cauchy-Schwarz inequality and get, for any R
xt (wv" + vu" + +|||u|| ||o|| T)x x" x='un" x + x" vu" a + 2||u|| - ||a|| ||o|l=""
(z, u) x) + (z, (u, x) + 2||14|| -|01| 20
Using Lemma 12 and Lemma 10 ir) in the last inequality, we immediately get that
E Gie [Fi + +E
[F G
2B G1ll
||alll [Fl
-1000)
[=:]
2
2
Σ
E [IVF |.:] E [1le(0(H))1 )12 [Fi
1=
212 da (L|10, - 0- + LnGl)
Notice that we could improve the bound using the fact that c(0())) is independent from ( for any j 2 Putting the pieces together we get that
E [SIST [F]] = (lamin - -2,2 do (L| 8*11 - T.(Gii) 1
E [
FF|? z (lamin - -212 .Vdo (L 8*11 LnGI))
1 1 Pomin + 41 do (L|10, 0*11 + LnI
48 min v do dazaz (T.100, - 00 + TnjGl) }
and then, using the asymptotic bound in 20
[ [F) =
Po
413 omn v daxar (L E [11, - 0*11 + LnGit)
}
Poomsn 0 V dax
LGVT
+ LYGI) }
VH- L'n
which finally gives the bound on the socond moment, which is
E[Qi Z d. (Pommn 40 min v do
+ +(77) ) ( 12
1
2 dl 02 0
K21 KTT--- - Kzltn
Using the fact shown before, that
LAG41²
E S
as t 00,
(μ - 1211)2
we can bound the variance of Qi from below with
do min
Ki Kiv
L²
Var(Q1) = -
K2ll (n- - L211)²
12
and then Var(Q1) 2
dd
Kiv π
+ 0mm)
EQQ1 L?n1² LAG4,
min
12
34

---

Published in Transactions on Machine Learning Research (02/2024)
The desired incquality is finally
B[Qill & C2(1) sQ))
with
G2 C2(1) = (11 I2Tn)
do min
KIv
-1/2 + 0(n))
= = -c-
1
1
35


Reviews:
[{"review_id": "iRjahfyqHS", "reviewer": "Reviewer_5Pef", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Major comments/concerns**\n\n1. The simple experiments (e.g., logistic and least squares) are all done in the under-parameterized regime (i.e., the number of samples is larger than the dimension). One would expect with Gaussian data that in the over-parameterized regime that a \\textit{fixed} stepsize is sufficient for convergence. I don't this algorithm would beat the best fixed stepsize (i.e., the one that converges in this regime). Can the authors comment on this and produce some figure? \n2. One should also make sure things are \"dimension-independent\". For instance, take two iid Gaussian of length $d$, there inner product on average is $1/\\sqrt{d}$. Things should be normalized so that as dimension grows you are not just getting the orthogonality effects just because of dimension.  \n3.  In the experiments, it is not clear exactly what algorithm is used w.r.t. the data (i.e., streaming or multi-pass) and mini-batching? I would expect that as the mini-batch increases the stepsize should not decrease and a fixed stepsize is used. Is this correct? \n\n1. The simple experiments (e.g., logistic and least squares) are all done in the under-parameterized regime (i.e., the number of samples is larger than the dimension). One would expect with Gaussian data that in the over-parameterized regime that a \\textit{fixed} stepsize is sufficient for convergence. I don't this algorithm would beat the best fixed stepsize (i.e., the one that converges in this regime). Can the authors comment on this and produce some figure? \n2. One should also make sure things are \"dimension-independent\". For instance, take two iid Gaussian of length $d$, there inner product on average is $1/\\sqrt{d}$. Things should be normalized so that as dimension grows you are not just getting the orthogonality effects just because of dimension.  \n3.  In the experiments, it is not clear exactly what algorithm is used w.r.t. the data (i.e., streaming or multi-pass) and mini-batching? I would expect that as the mini-batch increases the stepsize should not decrease and a fixed stepsize is used. Is this correct?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary:** This paper constructs an adaptive schedule for the learning rate that detects when a fixed stepsize SGD hits a stationary distribution and then geometrically decreasing the stepsize. The authors consider this in the setting, $\\min_{\\theta} F(\\theta) = E[ f(\\theta, Z)]$ where Z ~ (X,y) is a datapoint and provides theoretical guarantees when $F$ is strongly convex and smooth ($L$-Lipschitz gradients) with $f$ convex. In addition, it is assumed that the gradient $\\mathbb{E}[ \\| g(\\theta_t, Z_t+1)\\|^4 \\, | \\, Z_1,..., Z_t] $ is bounded and the error $\\epsilon_t = g(\\theta_{t-1}, Z_t) - \\nabla F(\\theta_{t-1})$ between the stochastic gradient, $g(\\theta_{t-1}, Z_t)$ and its mean has mean $0$ and covariance bounded above and away from $0$.  \\\\\n\nThe main algorithm called SplitSGD runs two SGD threads initialized at the same iterate using independent data points and then performs a hypothesis test to determine if SGD with fixed stepsize has reached stationarity. The two threads each run $w$ windows of length $\\ell$ and compute the average gradient over $\\ell$ with the fixed stepsize. Then the similarity between the two averaged gradient threads is computed, $Q_i$ is the inner product between (avg.) $g_i^1$ and $g_i^2$ where $i = 1,..., w$.  The idea being that if one is at stationarity then these two gradients will be nearly $0$ (i.e., orthogonal) and otherwise (not near stationarity) point in the same direction. Essentially, $Q_i$ is trying to approximate $\\|\\nabla F(\\theta_t)\\|^2$.To avoid the issue of determining what nearly $0$ means, the authors instead consider the $\\text{sign}(Q_i)$:\n\n$$\nT_D =  S \\text{ if $\\sum_{i=1}^w (1-\\text{sign}(Q_i)) /2 \\ge q \\cdot w$ and } N,  \\text{otherwise},\n$$\n\nwhere $q \\in [0,1]$. \nIf $T_D = S$ is returned, then one is near stationarity and the window $w$ is increased and stepsize is decreased. On the other hand, if $N$ is returned then all is kept the same. This idea is similar to other works including [Chee and Toulis].\n\nThe authors prove that SplitSGD is guaranteed to converge with probability $1$ provided the number of diagnostics is going to $\\infty$. They do not have a convergence rate. The authors also provide numerical experiments showing good performance of their algorithm against other similar \"stationary\" distribution detection algorithms. \n\nThe proofs are correct (as far as I could tell). The idea is quite similar to [Chee and Toulis] and so this should be taken into account, but the authors did address the differences namely the windows and \"forward\" instead of \"along the way\" computing the gradients. My biggest concern is twofold: 1). This idea, I suppose, should fail for the least squares problem when the number of samples is larger than parameter, i.e., over-parameterized regime (see below) and 2). Missing in the experiments and theory is the actual algorithm being employed, for instance is one using \"streaming\" (or one pass of the data)?, Mini-batching?\n\nOverall, I believe the paper is good with an interesting idea. The main convergence theorem is not there yet, but it is a sufficient idea. I would stress that the experiments should be made more precise especially given that the main theorem is not proven yet.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Some (small) comments/suggestions below**\n1. The presentation of the paper could be better. It was a little difficult to follow the windows, diagonistic, and how it all fits together to update the iterates. \n2. As mentioned above the experiment, should be made more precise. The captions of the Figures do include enough details to follow and the figures themselves do not say enough. For instance, in Figure 5, the y-axis is missing on the top figures. Moreover the caption for them just reads comparison between Splitting and pflug diagonsitic. Not enough explanation for what the reader is suppose to learn from this figure.", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "t7xROAn4qO", "reviewer": "Reviewer_ocBo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is written in a clear way.\n\n- The paper seems to come up with an interesting way of encapsulating the somewhat complex step size selection schedule problem into a single parameter $q$. This potentially simplifies the hyperparameter selection process without making significant compromises in its optimization efficacy.\n\n\nWeaknesses:\n\n- While I appreciate the theoretical work done in the paper, it only seems to provide an initial understanding of SplitSGD (namely, proof of its asymptotic convergence) under strong assumptions. In light of this missing theoretical understanding, I believe the main criteria to judge the paper by is its experimental parts, however I also found this part of the paper to be somewhat lacking:\n\n- Unfortunately, I didn't find the experimentation in the paper convincing enough to merit acceptance. It is difficult to assess the practical performance of a new algorithm based on the experiments performed in the scope of a single paper in such an instance. See requested changes section below for further detail.\n\n- While the parameter $q$ encapsulates the step size selection schedule in a neat way, the algorithm does introduce other new hyperparameters that might require some amount of tweaking (e.g. $w$ and $l$). It is therefore not clear if this indeed simplifies the optimization process beyond that of other algorithms that require finetuning the step size schedule.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a heuristic to detect proximity to stationarity in a stochastic optimization setting. The main idea is to start two simultaneous threads of SGD and measure the correlation between the directions of the gradients, where no correlation indicates proximity to stationarity. While measuring the correlation was done in previous works, the main novelty in this paper stems from the method in which stationarity is detected, which evaluates the percentage of negative versus positive correlations. Experimentation is performed to test the performance of the proposed algorithm SplitSGD compared to other commonly used optimization algorithms.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In a few figures in the paper (e.g. Figure 1), much of the text explaining the figures appears in the body of the text but not in the caption of the figures which I find to be inconvenient.\n\n- The nature of Assumptions 3.3 and 3.4 isn't clear. When should we expect these assumptions to hold? Why are they not extremely limiting?\n\n- While the experiments highlight certain cases in which SplitSGD is preferable over the compared methods, it is not obvious that this is indeed an indication of a broader phenomenon. For example, this can just be an artifact of fine-tuning the hyperparameters of SplitSGD to the point where they outperform other methods, whereas it is possible that a similar refinement for other methods could yield better performance. Specifically, I wasn't convinced that the experimental part on neural networks provides better performance overall, and I think it would be better to first experiment and study this algorithm in a simpler setting (e.g. a setting which mildly relaxes the theoretical assumptions in Section 3).\n\n- The summary states that \"We have developed an efficient optimization method called SplitSGD\" -- I wouldn't argue that this optimization method is efficient based solely on the experiments performed in this paper and I would suggest to omit the word \"efficient\".", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "j5r4cwdSx6", "reviewer": "Reviewer_dxDg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The method is demonstrated to work well, along with some theory that analyzes the theory for convex problems. Since the main motivation is about applying the method to deep learning, I personally do not think the theory aspect is relevant or convincing. Theoretical works suggested that the dynamics of SGD is predominantly saddle-to-saddle, whereas there is no saddle point in a convex landscape. However, I do not think there is any problem as long as the method is demonstrated to work well\n\nSee the requested changes section", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a learning rate selection method with the suggested gradient coherence criterion", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the same experiment in Figure 6 on ImageNet for resnet", "broader_impact_concerns": "It is fine", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has been reviewed by three reviewers: two recommend "leaning accept" (5Pef and ocBo), and one recommends "leaning reject" (dxDG). The main criticism of dxDG was that the simulations were not extensive enough. The authors have provided results on Cifar100, during the rebuttal phase, which i think is reasonable. However, these results should now be included in the final version of the paper.
As reviewers 5Pef and ocBo, I believe that the paper proposes an interesting idea. Although the available convergence results are not as strong as I would like (they rely on very strong assumptions), they are still of interest.

I thus recommend acceptance of the paper subject to the authors including (and discussing) the simulation results  presented in the rebuttal in the final version of the paper.
Decision: Accept (poster)