On the expected running time of nonconvex optimization with early stopping
Authors: Thomas Flynn
Kwang Min Yu
Abid Malik
Shinjae Yoo
Nicholas D'Imperio
Venue:  (2020)
Keywords: non-convex
stopping times
statistics
gradient descent
early stopping

Abstract: This work examines the convergence of stochastic gradient algorithms that use early stopping based on a validation function, wherein optimization ends when the magnitude of a validation function gradient drops below a threshold. We derive conditions that guarantee this stopping rule is well-defined and analyze the expected number of iterations and gradient evaluations needed to meet this criteria. The guarantee accounts for the distance between the training and validation sets, measured with the Wasserstein distance. We develop the approach for stochastic gradient descent (SGD), allowing for biased update directions subject to a Lyapunov condition. We apply the approach to obtain new bounds on the expected running time of several algorithms, including Decentralized SGD (DSGD), a variant of decentralized SGD, known as \textit{Stacked SGD}, and the stochastic variance reduced gradient (SVRG) algorithm. Finally, we consider the generalization properties of the iterate returned by early stopping.

Under review as a conference paper at ICLR 2020
ON THE EXPECTED RUNNING TIME OF NONCONVEX OPTIMIZATION WITH EARLY STOPPING
Anonymous authors Paper under double-blind review
ABSTRACT
This work examines the convergence of stochastic gradient algorithms that use early stopping based on validation function, wherein optimization ends when the magnitude of a validation function gradient drops below threshold. We derive conditions that guarantee this stopping rule is well-defined and analyze the expected number of iterations and gradient evaluations needed to meet this criteria. The guarantee accounts for the distance between the training and validation sets, measured with the Wasserstein distance. We develop the approach for stochastic gradient descent (SGD), allowing for biased update directions subject a Lyapunov condition. We apply the approach to obtain new bounds on the expected running time of several algorithms, including Decentralized SGD (DSGD), variant of decentralized SGD, known as Stacked SGD, and the stochastic variance reduced gradient (SVRG) algorithm. Finally, we consider the generalization properties of the iterate returned by early stopping.
INTRODUCTION
This work considers the minimization of a differentiable and possible nonconvex objective function:
min f(x)).
=ER
A generally accepted success criteria for algorithms that use only first-order information is that an R which the function f has small gradient. In typical machine learning scenario, I is the average loss over a dataset of training examples, and the method of choice involves using some form of stochastic gradient method, for instance, stochastic gradient descent, or SGD (see Algorithm learning problems has led to many extensions of the algorithm, including variance-reduced and distributed variants (reviewed in Section 1.1).
approximate stationary point generated. These are points
[]] The success of SGD in machine
common approach to stopping optimization in practice to use early stopping based on validation function. In this scenario, stopping criterion is periodically evaluated on the validation function, and the algorithm stops once this criterion met. The validation and training sets often are disjoint (although this is not required in the present work). Although this approach is used frequently, there little theoretical work on the runtime of nonconvex optimization using early stopping based on validation function. In general, the runtime and performance will depend on several factors, including the relation between the validation and training functions, and the desired level of solution accuracy. In this work, the stopping criterion that the algorithm has generated point, which is an approximate stationary point for the validation function. Our analysis focuses on bounding the number of iterations and gradient evaluations used until the algorithm meets the stopping criteria. Formally. we consider the stopping time defined as the first time an iterate has the property of being an approximate stationary point for the validation function, and we derive upper bounds on the expected value of this stopping time. Using bounds the Wasserstein distance between the training and validation sets, we also may derive bound on the stationary gap of the training function at the resulting iterate. As an extension, used to bound the stationarity gap with respect to the testing distribution to which both the training and validation datasets drawn.
also describe how Wasserstein concentration bounds can be
We apply our analysis to several settings, including stochastic gradient descent (SGD), stochastic variance reduced gradient (SVRG), decentralized SGD (DSGD) and stacked SGD (SSGD). The

---

Under review as a conference paper at ICLR 2020
result is new bounds on the expected number of Incremental First-order Oracle (IFO) calls needed to generate approximate stationary points for some known algorithms (SGD; DSGD; SVRG), as well as new algorithm (SSGD).
Main contributions Our main contributions include:
We present non-asymptotic analysis of SGD with early stopping that leads bound on the expected number of gradient evaluations needed to find approximate stationary points of the training function (Corollary 3.5). The analysis allows for biases in the update direction, subject to a Lyapunov-type inequality on the error terms.
We rigorously analyze the expected running time of two distributed SGD algorithms: Decen- tralized SGD, and Stacked SGD (Algorithm{) 2). a new decentralized form of SGD designed to exploit connectivity patterns consisting of a network of parameter-server type clusters (Corollary 4.4
We apply the analysis to nonconvex SVRG to obtain a bound on the expected number of IFO calls for this algorithm (Corollary 6.2)
We demonstrate how Wasserstein concentration bounds can be leveraged to bound the general- ization performance of parameters returned by SGD with early stopping (Corollary 7.2)
1.1 RELATED WORK
The study of stochastic optimization goes back (at least) to the pioneering efforts of Robbins and Monro Robbins & Monro (195T). Subsequent developments include the ordinary differential equation (ODE) method 1977) and stochastic approximation Kushner & Clark 1978), which
emphasizes the asymptotic behavior of the algorithms.
The subject of non-asymptotic performance guarantees has attracted interest as well, including lower bounds on algorithm performance Nemirovski & Yudin (1983). For review of non-asymptotti guarantees for convex SGD, the reader may consult Nemirovski et al.| (2009); Rakhlin et al. (2012); Bach & Moulines (013).. Extensions such as distributed Zinkevich al. (2010) and asynchronous
Zhang et al. (2015); Agarwal & Duchi] (2011) variants of the algorithms also have been investigated.
Many machine learning optimization problems involve an objective represented as finite sum of
functions, and, for this case, variance reduction techniques lead to improved rates of convergence
over SGD JJhnson & Zhang (2013): L. Roux al. (2012): Defazio et al. (2014).
The randomized stochastic gradient (RSG) method Ghadimi & Lan (2013) uses randomization to obtain a non-asymptotic performance guarantee for SGD. The randomization technique has became a standard tool for analyzing optimization algorithms in the nonconvex setting Ghadimi & Lan (2016);
Lian et al. (011) 7); Allen-Zhu (2018a by; Reddi et al. (2016b a): Zhang et al. (2016); Reddi et al. (2016b); Lei al. (2017): Lian al. (2013). Follow-up works have included analysis of nonconvex optimization in more sophisticated algorithmic settings, such as asynchronous Lian et al. (2015) and decentralized Lian al. (2017) optimization. Analysis of variance reduced optimization has extended beyond convex functions beginning with an application to principal components analysis Shamir (2015) and later to general nonconvex functions Allen-Zhu
Hazan (2016); Reddi al. (2016b a);
Lei et al. (2017). A highlight in this area is that the IFO complexity of SVRG for nonconvex Functions superior to that of RSG Allen-Zhu & Hazan (016); Reddi et al.
(201 6a). Algorithms with better
convergence rates than SVRG also have been developed Allen-Zhu 201 8a b).
We are particularly interested in results for biased SGD, e.g., Bertsekas & Tsitsiklis (2000) which considers the asymptotic convergence of biased SGD to stationary points. In this work, we are interested in a similar scenario but instead focus on the non-asymptotic behavior of the algorithm.
Several recent works also have explored the average amount of resources needed to reach desired performance level in optimization. The expected running time of a stochastic trust region algorithm (STORM) is given in Blanchet et al. (2016). A similar methodology also has been used to analyze stochastic line search methods Paquette & Scheinberg (2018). Our convergence analysis is similar in spirit to these works required to meet the performance guarantce. However, the algorithms and assumptions in this work differ.
also are interested in the expected amount of time other resources
2

---

Under review as a conference paper at ICLR 2020
Other recent work has analyzed the theoretical aspects of early stopping. For instance, Duvenaud ct al. (0166 developed an interpretation of early stopping in terms of variational Bayesian inference. Early stopping for least squares problem in reproducing kernel Hilbert space has been treated in Lin & Rosasco (016). The implications of early stopping generalization were studied in Hardt et al. 60. However, to knowledge, this work is the first to analyze the algorithms' runtimes when
using a validation function for early stopping in nonconvex optimization.
2 PRELIMINARIES
Let f: RR IR + R be loss function whose value we denote by f(v. 2). Intuitively, the variable represents input/output pair, and æ represents the model parameters. Throughout, we shall assume the gradient of the objective function with respect to æ is Lipschitz continuous (defined as follows).
R2 x Rd + R is bounded from below by f IR, and the derivative of f with respect to is L-Lipschitz continuous:
Assumption 2.1. The function
Vy E R2 F1, E R., [V, V. S T. x2l1-
At times, we will make a distinction between the training function fr, which is used to calculate gradients, and a validation function fv used to decide when to stop training.
Assumption 2.2. The training function fT is defined using set Yr C Rs of nr elements as fr(x) oy Egerr fly, and the validation function fv is defined using a set Yv C RR ny elements as fv(x)= 1 Eyery f1,x)).
To guarantee that the early stopping rule leads to a well-defined algorithm, we will assume a relation between the training and validation functions. Intuitively, the functions fo and fv will be similar when the datasets Yr and Yv are similar. Formally, the datasets YT and Yv determine probability measures fT and jay, defined as PT ny 5y is the delta measure 5y(4) = 1yEA for all sets A. We can compare these measures using the Wasserstein distance as in:
- Eyevt by and By by _ Σvery 6y, respectively, where
For 2 1, 2 1, we denote by (R9) the probability measures on R&9 with finite moments of order p. Recall that coupling of probability measures μn and μ22 a probability measure 7 R99 R such that for all measurable sets A, r(A x R²) = (A) and 7(R x A) = P2(A). Intuitively, coupling transforms data distributed like μ1 into dataset that is distributed according to p2. The Wasserstein distance on (RR)), denoted by dp. is defined as:
1/2
(11,, (2) = inf
E
[[| - xall!]
gET()1)1))
(=1:
where I(μ,, U2) is the set of all couplings of μ1 and #2. For more details the reader is referred to Villani (2008). Assumption 2.3. There is constant G 2 0 such that
Va e Rd,
[V - fz)ll Cuy.uv.n
There are several cases in which this assumption will satisfied. It is trivially satisfied if the training and validation sets are the same nr μvy As consequence of the Kantorovich duality formula (Villani (0088), Remark 6.5), it is also satisfied if the function + VzJ(y, x) is a G-Lipschizz function, uniformly for all x. Consider the following example:
Example 2.4. Suppose that g R2 Rd + IR is a smooth function. Let h Rd + R be the function that applics the hyperbolic tangent function to each of its components: h(x) = (tanh(x) ...,,, ... tanh(za)). and define f(y, æ) g(y. h(z)). Further suppose that the training data are bounded: || < J for all y E Yy. Then Assumption 2.3 is satisfied because + Vzf(x, y) is
Lipschitz function with SuP
8 (y. x.
Twdy
In our analyses the notion of success that an algorithm generates an approximate stationary point: Definition 2.5. A point d is e-approximate stationary point of f [[V](>))] <c.
3

---

Under review as a conference paper at ICLR 2020
We measure the complexity of algorithms according to how many function value and gradient queries they make. Formally, an IFO) is defined as follows (Agarwal & Bottou 2015):
Definition 2.6. An IFO takes a parameter and an input y and returns the pair (f(y. (z. (y.x)) x)).
we briefly recall the notion of filtration, stopping times, and other concepts from stochastic processes that will used in our analyses. We also refer readers to Williams (1991) for more details.
In Appendix A.1
3 BIASED SGD
This section details our analysis of SGD with early stop- ping shown on the right in Algorithm [ Starting from an initial point Z1, at each iteration, the parameter is updated with an approximate gradient h, using a step-size 7). The gradient norm of the validation function is evaluated ery m iterations, and the algorithm ends when the norm decreases below a threshold e.
Algorithm 1 SGD with early stopping
1: input: Initial point #1 IRd
2: t ==1
3:
while (ma)) > do
4:
for n / to + do
5:
In++1 = Xn 1//1n
end
We assume that the update direction he is a sum of two components, 1/ and A,, that represent an unbiased gradi- ent estimate and an error term, respectively:
7:
t == -=++m m
end
9: return 2z
h4 Ut + A..
(3)
Let (Fihe2o be a filtration such that 2ı is Fo-measurable, and for all t t>> 1. the variables ut, A, are Fe-eesurabll. Our assumptions on the U are as follows.
Assumption 3.1. For any 2 1, it holds that
E [0 fr(())
[ =0,
(4)
|10
Vr((z)))
| S oo
(5)
Assumption 3.1 states that the update directions v are valid approximations to the gradient V fr(:))) and it also bounds the error in the approximation. For the variables A, we assume the following: Assumption 3.2. There is a sequence of random variables V1, V2,..., and U1, U2,... such that for all 2 1 the variables V, and Ut are F-mmaasurable, || 1|2 < Vt, and the V2 satisfy the following Lyapunov-type inequality: For constants a E [0, 1) and $ 2 0,
V B, Vt 2 2, V/ S aV-1 + U,-1, Vt 2 1, EIU, Fi-1l 8.
(6)
(8)
Assumption 3.2 models a scenario where the gradient error dynamics is combination of contracting
and expanding behaviors. Contraction shrinks the error and represented by a factor a. External noise, represented by the U, terms, prevents the error from vanishing completely. Note that the assumption would be satisfied in the unbiased case by simply setting V, =
We can now state our result on the expected number of iterations for SGD with early stopping:
Proposition 3.3. Let (re) be as in Algorithm Let Assumptions 2./ 2.2 2.3 3. and 3.2 hold. c).
For é > 0, let r (c) be the stopping time T(e) = inf | (mod m) and /Jv (x,,
Suppose that < I and e - 22mmoo? - 22m3/(1
dddi ( > 0. Then
+2( fo) ) + nc/m + +2n3/11 a)) Blr(E)) < 77/mm 10mm-22jp33 - a) di (pv, HT)
(9)
Furthermore, it holds with probability 1 that (V)(( < 2. + 2G di (
This result can be strengthened by assuming a coupling between the step-size and the expansion bound B3 then the result can be strengthened demonstrated in the next corollary.
4

---

Under review as a conference paper at ICLR 2020
Corollary 3.4. Let Assumptions 2.1 the constant 3 be of the form 3 F for some
2.2 2.3
3.1 and 3.2 hold. In the context of Proposition
3.3
let
R 2 0, and suppose that e G d2y, , PT
Let
E (0, 1) and let the step-size be
t- e- G (wv, WT)² m(2Lo² + 2R/(1 - a))
= c. min
(10)
Then
m² (1+ [[[(e)]= = ()-c) ( G2d (JVV, )2)3
(1(1-a)) a))
(11)
See the appendix for the complete formula, including lower order terms.
From this corollary we see that when 3 is proportional to the step-size 1, the complexity bound is of the order (1)/e). As we shall see below, this coupling assumption is satisfied for Stacked SGD.
For the case of using SGD to minimize a finite sum using unbiased, we obtain the following:
Corollary 3.5. Let Assumptions 2.7 and by selecting data point y: Yr uniformly at random and setting U, Vx (yt( x4) and that there
2id22.holl hold. Suppose each gradient estimate is obtained
Eyey, V x)) I o². If the step-sizes are defined according to Equation equation 20using e. 1/2 then the expected number of IFO calls used by SGD before reaching e-approximate stationary point is
a ot 2 0 such that V of E Yr, x ERR, V=f(y',z)
E LIFO (e)) - -e]]
may m² (T-- (PFd((v )1) + +nv)
-
See the appendix for the complete formula, including lower-order terms.
Note that when d(uv, (())))rr) is on the order of VT, this result states that the expected IFO complexity is ())((2)). This can be compared with the RSG algorithm, where ((1((2)) iterations are sufficient the expected (squared) norm of the gradient at a random iterate to at most (Cor. 2.2 in
Ghadimi & Lan (203)).
STACKED SGD
Chaster 2
In this section, we introduce SSGD for decentralized optimiza- tion, which involves distributed system with two types of
nodes: workers and communicators. The communication pat- tern is shown on the right for hypothetical system consisting of 16 workers and 4 communicators. Workers (circles) are grouped into clusters, each containing communicator (trian- gles).
Chaster
Chuster
Algorithm depicts the steps of SSGD. For every epochs, the gradient of the validation function is computed at the mean of the communication node parameters. The algorithm stops when the norm of this gradient drops below threshold. This step is naturally carried out by one of the communication nodes because they can store the average computed during Line of the algorithm. For workers, each iteration begins Line 6 with one step of SGD. Then, on Line 7, an averaging step is performed to partially synchronize the model parameters within the local cluster. The steps for communication node begin in Line 9 with averaging step, among the other communication nodes from each cluster. On Line 10, there a partial synchronization with the worker nodes in the cluster.
Claster
The key to the algorithm's efficiency is that the averaging among communication nodes can happen in parallel with the gradient descent step as it occurs within the cluster. In the naive approach to parallelizing SGD, all nodes must block after each iteration for synchronization of their parameters.
We assume there are M 2 1 clusters, each containing K 2 1 computation nodes and 1 communi- cation node. Thus, there are M(K 1) total nodes. Given worker node < i < K K.M, we let
5

---

Under review as a conference paper at ICLR 2020
- SGD
S3GD
Algorithm SSGD with early stopping
1: input: Node id initial parameters
Dara por socond
2 (for workers), 2j (for communicators)
2: 1=1
3: while Vfv N E
cd
dd
4:
for n. 1 m do
5:
if node i is a computation node then r #+ x 170
6:
(ze(t)
201
7:
2+ K+1 n+3
1=1
n+!
8:
else (node i is communication node)
9:
2+ M Σ 1== 2/
M
SGD
10:
2z K+T n+
+ +E xd
Djec-1(() (() n+
SSGD
11:
end if
12: end
13:
== -=++m m7
250
14: end
Number of nodes
15: return Z
SSGD results for climate modeling task.
Top: throughput vs number of nodes.. Bot-
tom: comparison of the loss of the algo- rithms.
c(i) fI,....,M' denote the index of the communication node of the group containing worker i. For analysis, we define the filtration {Fih120 as follows:
Fo Fo=o((af 1
و KM) u ( Ms) (
121, < 1 1sis KM) ( M))
We assume that the gradient estimates used in SSGD are unbiased and have bounded variance: Assumption 4.1. For any 2 1 and 1 <is KM,
E Tut
fr(x) [[-1]] = 0, E ||u Vzz (x))) 11 F(-1] 5
(12)
(13)
The first step in our analysis a bound on the dispersion of the parameters across the system.
Proposition 4.2. Let Assumption 2.7 2.2 and 4.7 hold, and let the variables 3. be defined in Line of Algorithm 2 Suppose the step size satisfies 1/(2KK). Define the variables V1, U1, V2, U2.... and the constants a, 3 as follows:
2
V
(14a)
2
j=1
U (K + 3/8) M
TKT.
M
Σ kEC 1())
& / (14b)
- Vir
kEc 1(0)
(K +K4)
(14c)
(K + 1)2
4Lo2
8= 1) (K + 5/8)
(14d)
Then, for all 1. > it holds that V aV, U, and BU F.-1] s

---

Under review as a conference paper at ICLR 2020
In the preceding definitions, Vi represents the dispersion of the parameter values across different nodes. An averaging step tends to reduce the dispersion by a factor of a, while the independent gradient updates each node may increase parameter dispersion by amount B. This result allows us to model SSGD as form biased SGD, leading to the following:
Proposition 4.3. Let Assumptions 2.7
2.2
2.3 and 4. hold. Assume that the initial parameters at
every node are equal: zi f all
S 1 S
KM and Ø 3 for 1 S i,j M. For some
< ZK. suppose that the step-size 7)
{
G (dv, UT))
c cin
(15)
m(2Lo?/K + ( + ( 5
Let Te be the average of the communicator states at time t: T. M -i=
EM F/. For > define r())
be the stopping time T(c) inf(n 2 1 n (mod m) and [V )1? S c). Then,
B[[(e)] = ( ( G (uv, (
m²
Refer to the Appendix for the complete formula, including lower-order terms.
This leads to bound on the expected IFO complexity to minimize a finite sum using SSGD:
Corollary 4A. Let Assumptions 2.7 2.2 and 2.3 hold. Suppose each gradient estimate is obtained by selecting a data point vi Yr uniformly at random and setting of = I xt) and that there is o² 2 O, such that y E Yr, E Rd,
V ,x) 1 Eyer (=)(v.=) S o If the
step-sizes are defined as in Equation equation 15 with c 1/(KK), then the expected number of IFO calls used by SSGD before reaching an e-approximate stationary point is
mk (n.Knn++ + mK) + nV
[[F(())
((
Experimental Result SSGD has been implemented to train neural network model as part of research into spatio-temporal data analysis for climate research. The model LSSNet, neural network architecture that includes convolutional neural network to extract short-term local depen- dency patterns from spatial variables and a recurrent neural network component to discover long-term patterns from time series trends Lai et al. (218)). LSTNet is trained for the prediction of solar radiation from past sensor measurements. Fig. shows results from the experiment. The upper plot compares the throughput of SGD and SSGD the number of nodes increases. We see that the performance of SGD degrades after 64 nodes, while SSGD maintains near-linear scalability. The lower plot shows that although SSGD involves biased gradients, it does sacrifice accuracy, and yields similar prediction eπrors compared to SGD. See Appendix G.I for more details about the experimental methodology.
DECENTRALIZED SGD
In this section show how methodology can be applied to Decentralized SGD (DSGD) which another variant of distributed SGD. Recently, DSGD was analyzed using randomization Lian et al. (2017). In this section complement that analysis by studying the expected running time of the algorithm.
The steps of DSGD are shown in Algorithm 3 The procedure involves M > 0 worker nodes that participate in the optimization. A communication matrix describes the connectivity among the workers: di,j > 0 means that workers i and will communicate after each gradient descent step. At each step of optimization, every node computes a weighted average of the parameters in its local neighborhood, as determined by the connectivity matrix. This is combined with local gradient approximation to obtain the new parameter at the worker. The data that is returned by the algorithm (assuming the termination criteria is met) is the average of the parameters throughout the system, denoted Fz:
M
0;
(16)
M
1=1
7

---

Under review as a conference paper at ICLR 2020
Every m epochs, the norm of gradient of the validation function is evaluated at the average parameter and the algorithm terminates when this norm falls below a threshold.
The intuitive justification for DSGD is that it may be more efficient compared to naive approaches to parallelizing SGD, since whenever d..j 0 then the nodes and need not communicate. In Lian et al.] (2017) those authors offer theoretical support for the superiority of DSGD. In the present work, our goal is to analyze the expected running time of DSGD as an example of our the abstract theory developed above may be applied in practice. We leave comparisons of the algorithms for future work.
Algorithm 3 DSGD with early stopping
1: input: Initial point #1 E Rd. initial parameters æi.
2: t=1
while [ > c do
4: for 1 = t to + - 11 do
M
Fat1 Σ atjoy nuu
5=1
end
For the analysis, we define the filtration (Fr)ezo as fol- lows:
7:
1= 1
end
Fo
9: return Tz
121, === is Ssnst,isisN
The connectivity matrix a subject the same conditions as in Lian et al. (2017):
Assumption 5.1. The M x M connectivity matrix is symmetric and stochastic. The spectral gap, denoted by p and defined as p (max (am))) is assumed to satisfy p 1.
To make the proofs clear and concise, we make the assumption the parameters at each node are single real-numbers. That is, throughout this section we assume d = 1 in Assumption ??.
We also assume that the gradient estimates used at each worker at unbiased and have bounded variance.
Assumption 5.2. For any 2 1 and 1 S i M,
E Tot (f((z)
Fi-1] 0, [| ST( Fr-1] 1] S oz-
(17)
E
(18)
For the analysis, we show that the sequence of averages x; for = =, 2. can be modeled as being generated by a biased version of SGD, using the tools from Section This involves showing that the distance between local parameter values xf and the system average can be controlled, as shown in the following.
Proposition 5.3. Let Assumptions 2.1 (1 - (A))L)) Define the variables V1, U1, V2, U2.... and the constants a, 3 as follows:
2.2 5. and 5.2 hold. Suppose the step-size satisfies rj S
2 V
M
F, P.
(19a)
M
1=1
U, 8 2 + p)
Σ
(19b)
M(1 P)
p)
vp VP+1>
(19c)
2p
LV2
3 11 Dv
(19d)
Then all t 2 it holds that V S aV, + U2 and EUU [. < 8.
Using this result on the dispersion of the parameters, we can move to the main result on decentralized SGD. The result gives conditions that guarantee the expected time B[r(c)) is finite, and also bounds this time terms of the problem data. Notably, it shows a dependence on p. which is the mixing rate of the connectivity matrix.
5.7 2.3 and 5.2 hold. Assume that the initial parameters at every node are equal: z) 2 for all 1 S i,j $ M. Let < 1-ve and define R. LV20?, / p)
Proposition 5.4. Let Assumptions 2.7
2.2
4//2
8

---

Under review as a conference paper at ICLR 2020
Algorithm 4 SVRG with early stopping
1: input: Initial point im E Rd
IFO Calls
5.0
SGD SVRG
2: for 1,2.... do
2.5
3: 20 2
4: gºt
L E.Eer, (V,
10-6
10-5
10a
5: if 11 S then return +++ do
6: for t 0 to
IFO Calls
5.0
7:
Sample vÊ uniformly random from YT
SVRG
8:
"i Vy x7 x (v(i, 25+ g*+
9:
21+1 = z; -7o
10a
10:
end
IFO calls to approximate stationarity for MNIST (top) and CIFAR-10 (bot.).
11: end
and let a as in Equation equation 19c Let the step-size be
G-G2di(pv,
1 min
(20)
L' m(2Lo? 2R/(1 ([2/(1-a)) ai)
For define T(E) to be the first time the norm of the gradient of the validation funiiattioooniiinnn falls below E; That is, T(e) inf(n 2 1 (mod m) and [V S <e. Then
m² (1+ R/(1-o0) [[[(()] = (1-c) ( GPd
(21)
Note that in the above result, the order of the convergence is the same as for regular SGD and stacked SGD. An interesting avenue for future work would be explore whether it is possible to obtain bounds where the step-size condition does not depend on the epoch length m.
6 SVRG
We demonstrate how the method can applied to a variant of the SVRG Johnson & Zhang 2013) with early stopping, shown in Algorithm 4 Each epoch begins with full gradient computation (Line 4), and then an inner loop runs for m steps. The first step of the inner loop is to choose random data point (Line Then, the update direction is computed (Line 8) and used obtain the next parameter (Line 9).
Combining some existing bounds for SVRG with our stopping time approach yields the following bound on the expected number of iterations until SVRG with early stopping terminates:
Proposition 6.1. Let Assumptions 2.1 and 2.2 hold and consider the variables x defined by E/(Ln 2/3 and the epoch length m | (3E)]- For e > O, define r(c) to be the stopping time T(c)
Algorithm 4 Let 5 1/4 and suppose that the step-size is set to
inf / < }) Then, [E[[(c) 1 1 (4 -
Note that Proposition 6. counts the number of epochs until an approximate stationary point is generated. A bound the number of IFO calls can be obtained by multiplying by the number of IFO calls per epoch, which is nr + 2m. This immediately leads to the following result:
Corollary 6.2. Let Assumptions 2.7 and 2.2 hold and suppose the step-size and epoch length m are defined as in Proposition 6..1 T Then, the expected number of IFO calls until SVRG returns an 5/3
approximate stutionary point is E IFO (e)) O(1 /e) +r).
This result may be compared with Cor. 4 of Reddi et al. (016a)). which concerns an upper bound on the IFO calls for the expected (squared) norm of the gradient at randomly selected iterate to be less than e. Our result concerns the expected number of IFO calls before the algorithm terminates with an iterate that is guaranteed be approximate stationary point with probability stronger property.

---

Under review as a conference paper at ICLR 2020
Fig. 6 jillustrates the expected IFO complexity of SVRG and SGD. The top plot shows the results of an experiment using a simple logistic classifier on the MNIST dataset, and the bottom shows the result of training one-layer neural net the CIFAR- 10 dataset. The error bands represent the standard deviation of the measurements over five independent runs. Appendix [..2 includes more details about the experimental methodology- In each case, SVRG is better at obtaining accurate solutions, while, for SGD, the expected IFO calls seem to become unbounded for sufficiently small e.
7 GENERALIZATION PROPERTIES
Typically, the training and validation sets made from independent samples of a test distribution j4, and it is of interest to estimate the model performance on samples from this test distribution. Define fa: : _ + IR f(x) Ey (y, x}}. In this section, we derive bound on [ (x+(e))) where the expectation is not only over the variates generated by optimization, but also over the random choice of the datasets Yv and Yr. We will show how Wasserstein concentration bounds, which concern the average distance between and its empirical versions, can be used for this task. Consider the following from Dereich et al. (2013).
Theorem 7.1 (Dereich et al. (2013). Special case of Theorem 1). Let d 2 3 and let be a measure
on TR. such that J = y [|y]| 1/3
< 00. Then, there a constant E.g, such that E|d2 (1), Jvy )²] S
kaJnyy 3/d
This leads bound on the generalization performance of the iterates returned by SGD with early stopping, whose proof is deferred to the Appendix.
Corollary 7.2. Let the conditions of Proposition 3.3 hold. Further assume that J E [| 1/3 0o, the validation set Yv is empirical version of μ4, and + Vz Vz ) is uniformly G-Lipschitz. If (c) is the output of Algorithm 1, then E|[l (x( S 2 + 2G 2Ga Jny 3//
Note that for strongly convex optimization, it is possible to obtain rates of convergence of the test error that are independent of the dimension Hsu & Sabato (2016). Corollary 7.2 interesting as accounts for data distribution properties (via the Trd moment J) and does not depend on the number of iterations used SGD. This result could be compared with Harddt et al. (2016), where the authors proved a bound on the generalization gap for function values in terms of the number of iterations T and samples in the training set nt. There, the bound is independent of d but increasing with T, while our bound is independent of the number of iterations in SGD. It will be interesting to determine if these two analyses can be combined.
DISCUSSION
This work presents analysis of several stochastic gradient methods that use early stopping based on a validation function. We demonstrated that by blending existing analysis techniques with some basic tools related to stopping times, it is possible to bound the expected number of iterations and gradient evaluations to generate approximate stationary points. We also considered decentralized optimization and introduced new algorithm, SSGD, that proved amenable to analysis in our framework. For SSGD, we obtained a convergence rate using our results for biased SGD, and experiments showed that the algorithm has favorable scaling properties compared basic parallel SGD. Our application to SVRG demonstrated that the theoretical approach can be applied in various settings. We also considered the generalization properties of the output of early stopping. We hope these efforts inspire other works that investigate the theoretical and practical aspects of early stopping.
REFERENCES
Agarwal, A. and Bottou, L. lower bound for the optimization of finite sums. Proceedings of the 32nd International Conference International Conference Machine Learning- Volume 37, pp. 76. JMLR. org, 2015.
Agarwal, A. and Duchi, J. C. Distributed delayed stochastic optimization. In Shawe-Tayy Taylor, J., Zemel, R. S., Bartlett, P. L., Pereira, F., and Weinberger, K. Q. (eds.). Advances in Neural Information Processing Systems 24, pp. 873-881. Curran Associates, Inc., 2011.
10

---

Under review as a conference paper at ICLR 2020
Allen-Zhu, Z. Natasha 2: Faster Non-Conver Optimization Than SGD. In Proceedings of the 32nd Conference on Neural Information Processing Systems, NIPS 18, 2018a.
Allen-Zhu, Z. How To Make the Gradients Small Stochastically. In Proceedings of the 32nd Conference on Neural Information Processing Systems, NeurIPS '8, 2018b.
Allen-Zhu, Z. and Hazan, E. Variance reduction for faster non-convex optimization. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML' 16, pp. 699-707. JMLR.org. 2016.
Bach, F. and Moulines, E. Non-stronglyycomee smooth stochastic approximation with convergence rate o (1/n). In Advances in neural information processing systems, pp. 773-781, 2013.
Bertsekas, D. P. and Tsitsiklis, J.N. N. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10(3):27-642,, 2000.
Blanchet, J., Cartis, C., Menickelly, M., and Scheinberg, K. Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales. ArXiv e-prints, September 2016.
Defazio, A., Bach, F., and Lacoste-Julien, S. Saga: fast incremental gradient method with support for non-strongly convex composite objectives. In Ghahramani, Z., Welling, M., Cortes, C.,, Lawrence, N. D., and Weinberger, Q. Advances Neural Information Processing Systems 27, pp. 1646-1654. Curran Associates, Inc., 2014.
Dereich, S., Scheutzow, M., and Schottstedt, R. Constructive quantization: Approximation by empirical measures. Ann. Inst. H. Poincar Probab. Statist., 49(4):1183-12033 11 2013. doi: 10.1214/12-AHHP48))
Duvenaud, D., Maclaurin, D., and Adams, R. Farly stopping as nonparametric variational inference. In Gretton, A. and Robert, C. C. (eds.), Proceedings the 19th International Conference Artificial Intelligence and Statistics, volume 51 Proceedings of Machine Learning Research, pp. 1070-1077, 2016.
Ghadimi, S. and Lan, G. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-23) -26688 2013. doi: 10. 1377120880811
Ghadimi, S. and Lan, G. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99, 2016.
Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, pp. 1225-1234. JMLR.org, 2016.
Hsu, D. and Sabato, S. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(18):1-40, 2016. URL http:// htpp:///mmr.../m wtg.papers/vv11
14-273. 21-3273.hm
Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. In Burges, J. C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 26, pp. 315-323.. Curran Associates, Inc., 2013.
Kushner, and Clark, D. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Number v. 26 in Applied Mathematical Sciences. Springer-Verlape 1978.
L. Roux, N., Schmidt, M., and Bach, R. stochastic gradient method with exponential convergence rate for finite training sets. In Pereira, F,, Burges, C. J. C., Bottou, L., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 25, pp. 2663-2671. Curran Associates, Inc., 2012.
Lai, G., Chang, W.-C., Yang. Y.. and Liu, H. Modeling long-and and short-term temporal patterns with deep neural networks. The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 95-104. ACM, 2018
11

---

Under review as a conference paper at ICLR 2020
Lei, L., Ju, C., Chen, J., and Jordan, M. I. Non-convex finite-sum optimization via sesg methods. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H.., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp. 2348-2335555 Curran Associates, Inc., 2017.
Lian, X., Huang, Li, Y., and Liu, J. Asynchronous parallel stochastic gradient for nonconvex opti- mization. In Proceedings of the 28th International Conference on Neural Information Processing Systems- - Volume 2, NIPS' 15, pp. 2737-2745, Cambridge, MA, USA, 2015. MIT Press.
Lian, X., Zhang, C., Zhang, H., Hsich, C.-J., Zhang, W., and Liu, J. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp. 5330-5340. Curran Associates, Inc., 2017.
Lin, J. and Rosasco, L. Optimal learning for multi stochastic gradient methods. In Advances in Neural Information Processing Systems, pp. 4556-45644 2016.
Ljung. L. Analysis of recursive stochastic algorithms. IEEE transactions automatic control, 22 (4):551-575, 1977.
Nemirovski, A. and Yudin, D. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust stochastic approximation approach stochastic programming. SIAM Journal on Optimization, 19(4):1574-1609) 2009. doi: 10.1137/ 070704277.
Paquette, C. and Scheinberg, K. A Stochastic Line Search Method with Convergence Rate Analysis. arXiv e-prints, art. 10KKvv1807.07994 July 2018.
Rakhlin, A., Shamir, O., and Sridharan, K. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, pp. 1571-1578, USA, 2012. Omnipress. ISBN 978-1-4503--128-1.
Reddi, S., Hefny, A., Sra, S., Poczos, B., and Smola, Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pp. 314-323, 201
Reddi, J., Sra, S., Pezos, B., and Smola, A. Fast incremental method for smooth nonconvex optimization. In 2016 IEEE 55th Conference Decision and Control (CDC), pp. 1971-1977, Dec 2016b. doi: 10. 199/CDDC.2016..799555
Robbins, H. and Monro, A stochastic approximation method. Ann. Math. Statist., 22(3):400-4077 09 1951. doi: 10.1214/aoms/1 1777795867
Shamir, stochastic pea and svd algorithm with an exponential convergence rate. Proceedings of the 32Nd International Conference International Conference Machine Learning Volume 37, ICML' 15, pp. 144-152. JMLR.org, 2015.
Villani, C. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008
Williams, D. Probability with Martingales. Cambridge mathematical textbooks. Cambridge Univer- sity Press, 1991. ISBN 9780521406055.
Zhang, H., J. Reddi, S., and Sra, S. Riemannian svrg: Fast stochastic optimization on riemannian manifolds. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29, pp. 4592-4600 Curran Associates, Inc., 2016.
Zhang, S., Choromanska, A., and LeCun, Y. Deep learning with elastic averaging sgd. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, pp. 685-693, Cambridge, MA, USA, 2015. MIT Press.
Zinkevich, M., Weimer, M., Li, L., and Smola, A. J. Parallelized stochastic gradient descent. In Advances in neural information processing systems, pp. 2595-2603, 2010.
12

---

Under review as a conference paper at ICLR 2020
APPENDIX: ON THE EXPECTED RUNNING TIME OF NONCONVEX OPTIMIZATION WITH EARLY STOPPING
A PRELIMINARIES
Our analyses make use a quadratic bound for the training function which follows from Assumption
21
V2, fr(z+ fr(()) (fr(x) o+ - 11111
(22)
A.1 STOCHASTIC PROCESSES
The formal setting of stochastic optimization algorithm involves probability space (2, P), consisting of a sample space Ω2 o-algebra FF subsets of and a probability measure on the subsets of Ω that are in F. The algorithm takes an initial point and defines sequence of random variables (w)(w)))>> Intuitively S2 represents the random data used by the algorithm, such as indices used define mini-batches. For of notation will omit the dependence of random variates in the algorithms on E Q. A filtration {Fe)t= is an increasing sequence of o-algebras, with the interpretation that F, represents the information available an algorithm up to and including time A random variable x Ω + Rd is said to be F, measurable if it can be expressed in terms of the state of the algorithm up and including time stopping time, which is random variable 7 Ω + {0, 1, oo) with the property that the decision of whether to stop or continue time n made based on the information up to and including time n.
rule for stopping an algorithm represented as
The following proposition will be used through out our analysis of the different algorithms.
Proposition A.1. Let T be stopping time with respect a filtration {Fe)==o11.... Suppose there is a number с 0o such that T with probability one. Let 3ı, Ø2.... .. be any sequence of random variables such that each v, F--measurable and B[[[2 [I]
Then
E
E
Σ E [aa
Fe-1)
(23)
Proof. This a consequence of the optional stopping theorem (Theorem 10.10 in Williams (9911).
Define So 0 and for 2 let S,
(x:-Eiz E| F(-I)). Then So, St... martingale with
respect the filtration (Jr t=0.1.... and the optional stopping theorem implies E [S]] [E[S) But
E[Sa] = 0, and therefore E S = 0, which is equivalent to Equation equation 23
B ANALYSIS OF BIASED SGD
PROOF OF PROPOSITION 3.3
Proof. For convenience, define the random variables ò, for t = 1,,, as Ut fx,))). From
equation 22 it holds that
[r( < fr(x)) - -VV (V/T(())))) + A.) L + ((\ + A.1
13

---

Under review as a conference paper at ICLR 2020
Summing this over t = I,.... yields
[T(Mm41) S [T(
(VSr(a)) Ar)
( + 8z + 2.12
2
1=1
1. 2-
m
= =f((1)) - Σ 17
1 -
[V
Σ
711 -
(24)
t=1
m
L "1 |166|1
Σ 111 Ln)
m
m
2 " |.12
L
Σ Taj
A..
t=1
Note that, in general, for any numbers b it is the case that |ab| s _aa² + 2.... Then
1 Axl S 6 | S 1 1 + 2 211
(25)
and
[T (..) < [VS(())]]]AA]]) S |
+
1 2 14.11
(26)
Combining Equations equation
24
equation
25 and equation
26
we obtain
fr(Em+1) S ((11 -(x1)-
Σn 71
1
L
1 211 Lm)
2
m
11 [n fI (x:) + Σ
N
L
2 1/² Imp
|10.11
t=1
N
2 " + 2 n1(1 - -In))= + Tnp² 1
|| 1|2
2
1=1
m
1
m
m
f(a))
Σ
Σ
111 (n)
Lyy 1,72118012
+ Σ マ
?
1=1
Rearranging terms and noting that [T(m++1) 2 Sr, this yields
1 2
[V]T(()))1 < (t(21) -
(11 (T) +
Tay² 11881
t=1
1=1
+ Σ 2 (1 + An
(27)
m
m
$ f((1) f" Σ 711 (z),)
> Lo
V
where in the second inequality we used the assumptions that < 1/L and || < V.. Based on our assumption that fv fz)())| s Gd, (Hv. it follows that
[v < 20 di (wv,p)) V
(28)
14

---

Under review as a conference paper at ICLR 2020
Also note that
n
n
1=1 (mod m) =
-
+ 1.
(29)
m
t=1
Combining equation and
and equation
results
Am
Ae)An
1i (snod m) [Vv(v <
L (mod my G (Hv,
r(e)n
1 (mod m)
[fr(x))]1
(30)
Te)An
(T(()) +1 Σ
d2 (uv, (pv,
[V
m
For each n 2 1 define An) to be the stopping time which is the minimum of T(E) and the constant it holds that
n. Applying Proposition A.1 and Assumption 4
A(e)An
E
Vfr(z,)
(31)
and using Proposition A.1 with Assumption gives
7e))An
Σ
||&e112 S [))(((()) ^ A...
(32)
Next, according to conditions equation 6 and equation 7 it holds for any m 2 1 and with probability one that
V1 v
V4 +
Us + 3
(33)
and by equation 8 together with Proposition A.I
F(()Aa
E
Σ U,
s B|r(e) A n13.
(34)
Combining equation
33
and equation then
7(c)An
T(cAA
E
Σ
V
S aF
Σ V/ + (B] 11/
which, upon rearranging, results in
Te)An
B
E
Σ
V4
< (E[T(E) A n] + +1)
(35)
1-a
t=1
Furthermore, by definition of T,
Ac)An
(r(c)An)-1 -1
E
E (mod m)) (x:)):)
> E
Σ
1 (mod m) V VV
(36)
> B((((c) An) - 1]
Here we used that
n
1 (mod m)
15

---

Under review as a conference paper at ICLR 2020
Combining equation 27
equation 30
equation
31
equation
32
equation 35 and equation 36 results in
[l((e) nl
(Bl
S G uT))
+ +
+ fT((I) -
2m
m
8
+ Laf 2 o + "
(E|T(e) [
This can be rearranged into
2n8
D G² d'd [BT(()) An] n/ (uv,
m
1-a a
m
B + 2(fr(z)) -1¹) + 21)
1
which in turn is equivalent
A S n )² 2(r((1)())))))))))) 14) + ne/m + 2n8/(1 -
(37)
me/m 2LrPo? - 2n8/(1 a) - 7/ (pv,)dddv,rr) /r)2/m
Note that the sequence of random variables ((T(c) A m=m_112 is monotone increasing, and converges pointwise to Te)). Then the claimed relation equation 9 follows from equation 37 by the monotone convergence theorem.
Finally, by applying equation 28 with the roles of fv and fr reversed, and using the definition of T(c), follows that
V s (2 + 2G di (uv, pT)²
2 22e+2G2d
PROOF OF COROLLARY 3.4
Proof. According to the assumption on the step-size (Equation equation[0))
1) v[( 1 G (m) n2Loo + 2R/(1 - -+)]] 2 7/(1 c)(e 3Tm)
(38)
and
1 1 - m(2o 22
(39)
c c(E- G2d, (Wv, HT)
Combining these inequalities with the conclusion of Proposition 3.3 (relation equation 9 yields
El7(+)) S gG PT)2 ((fr(z)) f*) n/
2n 2
(r) - || G2dd (uv,, pT) --) me/ 2v a))
r/(
(40)
n/cc (pv, m 2 2
a)
"T pT) 2 (21) -() 2n (1-
1 c) (e - G2d, (o),
Step A was established by Proposition 3.3 Step B uses the assumption that B = nR. Step C is an application of equation 38, Next, we will upper-bound bound the final inequality in three steps. First, using Inequality equation 39 we that
2(fr((1)) f²)
2(fr
(1 (s (Dv.))1m))))
c) Gad (VT,)))m)))))
m(2Lo² + +2R/(1 - a:) c(c G2d (NV (/V,,Hp , )2
2m(fr(x1)- -f)
c)clc G (HV, L
(fr(((())) -1)
c)c(c - (2 (2Lo² + 2R/(1 -a]).
(41)
16

---

Under review as a conference paper at ICLR 2020
Next,
2xy R/(R - a) 111 c) (6 Ghd, (MV, ,T) 11/m
2/ -a)
(1-c)
G2d (T)
2cR2(1 -a)
Gi nT)²
$
(1 (c G2d (
m(2Lo² + -R/ a))
2R/(1 - a)
x
(1-c)
(2Lo² + 2R/(1 a))
$ (1 cc
(42)
Finally,
di (UT)2 + ne/m 7(1 - c) (e (uv.
Gddilvv ( + e/m
(1- (c- G2d, ( Hr)3//m
(43)
mcG d1 (uv, PT ) ce
c)clE - G²d (uv )T)
Combining equation 40 with equation 41 equation
42
and equation 43
we find that
4m (fr f*) (Lo (R(11-((1)))
B[r(e)] S
(1 c) cle ( uT))2
(44)
2Lm(fu(11) f²) +
+
(1 (1- c) G (uv,
1-c
PROOF OF COROLLARY 3.5
Proof. If the algorithm runs until iteration T(e). then the number of times that the full gradient fy is calculated is [r(e)/m] < r(c)/m + and the number of IFO calls for the training function is
T(c) 1. Therefore
IFO())
((())
+1 ny (7(c) - 1) r(c) (") ("Y +1) nv.
(45)
Note that under our assumption on the gradient estimates Ut. are in the unbiased setting where R = 0. Combining equation 44 with R = ( and equation 45 we obtain
4m 4m² (fr(i))) Lo)
B[IFO(e)]
(1- G2d, (uv (MT) 2212
(46)
+ 2mm( - + mcG (IV, ce
ny x
+1) + ny.
c)
PT)
1 1
m
Using c = 1/2 and neglecting lower-order terms, then,
mnv + m² [[[FO(()) = (e-GGdd HI )2)2 + mv)
C ANALYSIS OF STACKED SGD
PROOF OF PROPOSITION 4.2
Proof. Note that the variables inside the stacked algorithm satisfy the following identities: For all
1 < i < MK,
(0
x
(47)
17

---

Under review as a conference paper at ICLR 2020
and for all pairs communication nodes nodes 1 S j M, and 1 S k s M, and t 2
+ x [+ 2+3
(48)
Let 1 S i M and S j S M be arbitrary indices of communication nodes. By the definitions in Algorithm we can see that for any 2 1,
|+t+1 11
Σ
1+t
*
1
Σ (EC
fetb
K +
K +1
kEE-1(()
Σ
( - muttt
Σ
(z+ muttt
K ++1
K +1
REC (8)
kEe (5)
(49)
C
1
Σ
(3) mottt
1
a mott
K ++
K +1
kEE (2)
kEC-
D
K
mu + K+1
Σ
not
++
K
++1
kEe 1()
kEC
(1)
E
K
1
Σ
+1
K+1
K
K+1
kEC
(A)
kEE
Step A follows from the definition of 11+1, Fi. in Algorithm 2 and Equation equation
48
Step B
follows from the definition of x in Algo. 2
Step follows from Equation equation
47
Step D
follows from rearranging terms the previous step, and noting that there are K workers cluster.
Finally, Step E is simply the triangle inequality.
For the second term on the right of the final inequality above,
Σ
K+ +1
K
kEE
(1)
kE
(f)
K
Vf(T:) - v)(H)
K +
-x Σ of (2)) ||
o - -
(50)
K
K
kt)-1(t)
kEE-1()
KL
|ل |
K +
1
K
of -
1
Σ
(z)
Σ of V
K+1
K
K
kE6-1(0)
kEc '())
where the last inequality uses the Lipschitz gradient property (Assumption inequality. Combining equation 49 and equation yields
2.1 and the triangle
-
(1 + Ln) ||
K
(51)
πバK
1
Σ
oe
V
Σ
-
K+1
K
K
(i)
kEa- (t)
Note that for any h > 0 and all b we have
+ b/2 < (1 + )a +
1 ko
b².
(52)
18

---

Under review as a conference paper at ICLR 2020
Combining equation 51
and equation
52
while using the assumption that 1/((2)) results in
|8 2/4 112 -
(1 + ki k?
+
1
- 2
(K + 1)2
2K
+ 11 (1 h1n) K
Σ
of
v
-(Z
E
uf
)|
(53)
Ki(K + 1)2 2L
K
K
kE)
kEC- (5)
(K+3/4)2 (K+1/2)²
Let K1
1. Then by the definition of a,
(1 (1+k))K² k=²
1
(1 ki)(kKK + 1/2)2
(K+ +3/4)²
(54)
(K + 1)2
2K
(K 1)2
(K + 1/2)2 = ax
Furthermore,
+ kn
(K + 1)2
$
h1
K/2 + 5/16
SO
(1 + K1)
(K + 1)² K 1
" (K 1)2
$
(K/2 5/16) K
(K + 1)2 2L
(55)
"K/2 + 5/16) 2T.
K
L((K + 5/8)
Multiplying each side of equation 53 by L2/M², summing the resulting inequality over i = 1,..., M
and ,,...,,, M. and using the relations equation 54 equation 55 we see that for all >
V41 S VV + Ur.
It remains confirm that E(U, Fi-1) for all t 2 1.
Taking expectations in equation 14b while noting that x-(kk) equation 13 along with the inequality ||a bll2 I 2 (Ila)2 + []b(2) it holds for all t > that
r and applying the variance bound
E UU Fi-1]
KL
<
(K + 5/8)
( of VST(T)
[
ΣΣR
Σ E
V
x M j=
K
kEC 1()
kEc 1(1)
KL
ΣΣ 2
2
o3
=((K 5/8) M
K
K
=1
B.
PROOF OF PROPOSITION
Proof. Note that according Line of SSGD,
T T 2+
=
M
(56)
and Lines 7 and 10 mean that for all j with c(j) = i,
xt = .od
(57)
19

---

Under review as a conference paper at ICLR 2020
Using these equations, together with the definitions in the SSGD algorithm, obtain that
1
Σ
K +
144
jEc
1
Σ
(of (o(-mmt) mpm
T1
K K+1
M
K+1
jEC (())
+
1
Σ
[ m715))
K+1
M
K+1
i=1
(Ec
K
3t
Σ
K+
K+1
M
K+1
JEC (6)
Σ
Tt 1l
M K
K+
JEC
For Step A, note that T. is the average the Et, and then use definition of the क from Line of the SSGD algorithm. Step B follows from equation 56 and the definition of the r++ from Line 5 of SSGD. Step C follows from equation 57 Step follows by rearranging terms in the previous step, and again noting the definition of is the average of the T.. Step E follows by grouping terms.
Continuing, we can express this recursion as an approximate form of gradient descent:
M
Ro41 = -1
Σ
M
K
-
i=1
jEc
1())
M
K
= Tt
K +
M i=1
K
jEc
n
i +
(ve Ae)
where and A, are
04 =
VV
Σ
Σ
of
VTT(ET)
(58)
M 1=1
K
(E0-1(1)
and
1 M
A
Σ
(e))
Vfr(
(59)
Based on the definition of 02 Equation equation 58 and on Assumption 4.1 for all > 1 i holds that
Ft-1= 0, E Elee - (f.
- (f,(11
F
<
K
Thus Assumption 3.J is confirmed. Next we consider the Lyapunov condition of Assumption 3.2 Let the variables U,, V. for 2 1 and the constants a, 3 be defined in equation eqaattin 14d
20

---

Under review as a conference paper at ICLR 2020
Then by Assumption 2.1
M
1
1 1
V fr(2))
vf(ã.)
M
1=1
$ 1,2
(3) 34
M 1=1
M
M Σ
L
M
M
j=1
1,2
34
M
M
S L
2 -
M
The second line uses the Lipschitz gradient property, and the second to last line follows from Jensen's inequality (Section 6.6, WWllliams (1991)).
By our assumption that each node has the same initial state, then 1/2 = 0, hence Inequality equation
holds. The Inequalities equation 7 and equation 8 are established by Prop 4.1 According to the
definition of 3 (Equation equation 14d. we may write 3 = n/l where R ALo. /K + 5/8).
Note that 1/(1 a)) 2(K 1)² /K 5/8). Therefore,
R
8Lo (K + 1)K/(K + 5/8)² < 32L
(60)
a
According to Corollary 3.4 then, step-size of
e- (-G2di(HV,HHy HT)²
= c. min
L' m(2LLo K 1 + 1)2 + 5/8)3)
leads to
B[r(c)] < 4m 4m²(fr(01) - 14) (Lo K + 32To?)
d2 ( 22)
(61)
2Lm(sT(X1) - 1r) + mc di (NV HT) C6 + 1-6
c
(1- c(c G (NV. )2)
Dropping the lower order terms, we see that
m B[r(c)] (iii--0(aa-eee- -l1-c)o(e= (Nv, (pV,
(62)
PROOF OF COROLLARY 4.4
Proof. SSGD runs until iteration r(e), then number of times that the full gradient fv is calculated is [r(e)/m] S T(e)/m + 1,, and the number of IFO calls for the training function is (r(e) 1)K. Therefore
IFO(e) <
T(E)
1 ny + (T(e) - 1)K S T(6)
(AVV m
TVV
+ K)
nv.
(63)
Next, note that (1 - c)c = (1
1 1 1K-1 which implies
4K Z {4K)z.
16K²
16K
4K - <
(64)
(1 - c)e
21

---

M Under review as a conference paper at ICLR 2020
Combining equation 62
equation 63 and equation 64 see that
mK (ny + mk)
E [IFO(e)] = o (ie- (TV,
+ my)
D ANALYSIS OF DECENTRALIZED SGD
The following result is a restatement of Lemma 5 of Lian et al. (017))
Lemma D.1. Under Assumption 5.1 the matrix limg- at well well-defined and has entries 0... M
for 1 S i,j & M. Furthermore,, for all k 2 1, bound on the spectral gap implies ||a - a²11² S pr.
PROOF OF PROPOSITION 5.3
Proof. For ease of notation, for each 2 1 let Ve and 2t be the M-dimensional vectors with components defined as
vi x Ft,
(65)
2 o
(66)
M j=1
Let a be the M M matrix with entries
Algorithm 3 the y satisfy the recursion ". (see Lemma D.1
Then according Line 5 of
Mo+1 = (a a )yr + 1.a.
(67)
Note that 2 can be expressed
fxx)) fxx,)
1 M oo f((i)) + M
1 M
(68)
+ + fzxt))
Σ
-
- fT.))
M
j=1
Using the Lipschitz property (Assumption 2.1 then,
M
| S L/z./ Tal + 10
VS(x
1og V((2a)) +
Fz
(69)
M
M
j=1
Squaring and summing Equation equation 69
2
M
M
L
M
Σ
L|r
Fnl + 10
v((x
1 - -(())
+
Enl
M
M
j=1
4 44 >
Jnnh Iz 12 +
2
M M
4L2 M
M
1, vf(2a))
+
Σ
|o4 Fnl 1
M
M
1=1
1=1
L'881
2 +
Σ 10
Taking square roots on each sides of this equation yields
||
128 + 8
M log {)
(70)
M
/
VT.88 +
8
Σ
[)(+))12
22

---

Under review as a conference paper at ICLR 2020
Combining equation and equation 70 then,
M
11 $ (Ia- a + nLV8) l1 + +m
2
i=1
M
$ <(p= (VD+)LV8) l1 + +
V2(2))
In the second step have applied Assumption equation 5.1 and Lemma D.I Squaring this equation, for any 1, > it holds that
11 11 s (1 (1+ k1) (VD nLV8) 1 +1²
(1
8
ff()))
(71)
K1
Let 11- = I-e (in which case 1 + ko
Multiplying each side of 71 by 1.2/M and noting that
V Ar llvel? (12 it follows that
(1 (1+ (VD+NLV8) Vj U..
Vi+1 S
(72)
2p
It follows from the variance bound in Assumption
5.2 that
F:-1] s 8 L + + Po2 03
E B
(73)
Using the assumption that 1) S
1-v0 ALV2'
then equation 72
and equation 73 become, respectively,
(1+ p)
<p </++1>
V/+1 S
V/, + U,
2p
2
and
1 S v2n(1 - vp) L 1 P
S LV2 0,
PROOF OF PROPOSITION 5.4
Proof. To begin, note that the system average z, satisfies the recursion
M
77
Tt+1 Iz +
U
(74)
M
Define the variables i, and A,, for 2 1, as
1 M
= Vf(xz) +
Σ v((x))
M
i=1
1 M
A,
[)(())) vs(x)))
M
Then express the recursion equation 74
T++1 1) (v. A.)
23

---

Under review as a conference paper at ICLR 2020
We will show that this can be interpreted form of biased SGD and therefore may apply Corollary 3.4
For the unbiased component vt, observe that
M
E 10 (x+( Fe-1l =
(ut - vf((a)))
Fi-1 =
(75)
M
1=1
and
1 M
E [[lee Vfr(2))
Fi-1 1
S
luf v
=
(76)
M
For the bias term, note that
L M
|
Σ
20
Vı
Assumption equation 3.1 follows from equation 75 and equation 76 while Assumption equation 3.2 The result then follows from Corollary 3.4
follows from Proposition 5.3
E ANALYSIS OF SVRG
For the analysis of SVRG, define the filtration {Fitt=o,1.... as follows. Fo =o=((=))) and for all
o(x)))
F. =- (f (f
- ostsm-
We will leverage some prior results concerning the behavior of SVRG. The following is adapted from Reddi et al. (2016a).
O and define the constants Cm Cm-1..... Co as followws Cm = 0, and for 0 < S m 1, let = (1c111+13+111 22) +12 L3. S the analysis constant 8 are chosen so that r, 0 for 0 S < m and set y infogeem Tt-
Proposition F.1. Let Assumptions 2.7 and 2.2 hold. Let
Define L, for
r 2411 17 20++177 Suppose that the step-size y and
Then for all 2 1,
fr(x")) B[fr(=nt Fs-1]
E Fo-1]
(77)
?
Furthermore, if is of the form n 7 E/(n/ for some & E (0,1) and if the epoch length set to v(E)
(n/((E)), then there is value for B such that 7 Lnf73 where v(g) is constant dependent only E. In particular, i = 1/4 then
(78)
2/3
Proof. The proof of equation 77 follows from nearly the same reasoning used to establish Equation 10 in (Section B, |Reddi et al. (2016a)) the only difference being that conditional expectations replace expectations in all of the relevant formulas. The details are left to the reader.
Formula equation 78 is a numerical inequality whose proof can be derived from the proof of Theorem 3 given in in (Appendix B, Reddi et al. (2016))).
PROOF OF PROPOSITION 6.
Proof. First, note that 7(E) is well-defined stopping time with respect to the filtration {F.)==0..... For 8 = 1,2,.. define the random variables 6, as
fr( - (x
6, =
fT +1 122
?
24

---

Under review as a conference paper at ICLR 2020
It holds trivially that for all 2 1,
fr(mm) (r(ami)) 0z
IV (x
(79)
7
t=0
and by Proposition E.1
for all 2 1,
fr(mm) (x Fs-1l
6|6,
Fa-1]
E
V (2. |F-11
7
(80)
S 0.
Summing Equation equation 79 over = =1, 1.....9 yields
(1; fr(mm)) - fr(1tt1)
Σ Sa.
(81)
Rearranging terms and noting that fr (zft1) 2 f results in
m
v [T +1 1|2 S (T((m)) 8 +
8,.
(82)
follows that
fT (10 |1 < fT(( - 8..
(83)
For 2 1, let r(C) A be the stopping time which is the minimum of 7()) and the constant value r.
Applying Proposition A.1 together with Equation it holds that
80
T()Ar Σ
6
00
(84)
s=1
Furthermore, by definition of
(e)Ar
(r(c))r)-1
(F(e)
|V (x (10
2E E
Σ
| Iv 11
ZE
Σ
(85)
(B(((())
Combining equation 83 equation
84 and equation 85 yields
(E((T(c) A n) 1] S fr((m)))))))) -
Rearranging terms in the above yields
E[T(c) An] < fr fr
+ 1.
7E
Applying the monotone convergence theorem, then,
fx +
[[[(E)]
7E
Next, specialize and m to 1 E/ and m = [n/(3E)) with & = 1/4. Then by Proposition E.1 2 1/(40Lm2/3) Therefore,
1/3n2/3 (fr f*) +
E[r(e)) <
25

---

Under review as a conference paper at ICLR 2020
F GENERALIZATION ANALYSIS
PROOF OF COROLLARY 7.2
Proof. Under our assumption on the Lipschitz property of V ( a)) it holds that
(=+(())) & (z+(e)))) Gd1 (p, Hv).
Squaring and taking expectations, while noting that d1 S d2 (see Villani 2008), Remark 6.6),
( < 2 /v (v + 2G EE vv)*
Using the Wasserstein concentration bound from Theorem 7.1 and the definition of T(e), we obtain
E|| (f v 2E + 2G KaJna 3/d
G EXPERIMENTAL METHODOLOGY
G.1 SSGD EXPERIMENTS
The neural network model used for these experiments is LSTNer el. (2)1) withh CUDA-aware MPI and extended to use the Stacked SGD training method. The objective function the squared error between the prediction and the true sensor measurement, averaged over the dataset of training instances.
Our experiments compared SSGD (Algorithm 2 and SGD (I. For SSGD, each cluster has 4 worker nodes and 1 communication node. Hence, K and M is varied from to 64. Since one physical node has four GPU devices, each physical node in the HPC environment is modeled single local cluster in SSGD. The scalability SSGD is compared with the basic parallel implementation of SGD, where all node synchronize with all-reduce collective communication call after each parameter update.
The experiment is conducted in high performance computing environment that is equipped with 108 nodes. Each node has dual Intel Xeon E5-2695v4 (Broadwell) CPU, four NVidia K40 GPUs, SAS-based local storage, and 256 GB of memory. The nodes are inter-connected with a non-bloc Infiniband EDR fabric.
G.2 SVRG EXPERIMENTS
For the first experiment in this section, we trained a neural network with no hidden layer (i.e., a logistic classifier) for the MNIST classification task. For the second experiment, trained neural network with one hidden layer of n 100 nodes on the CIFAR-10 classification task. The activation function in the hidden layer objective function the average cross entropy loss.
the logistic function (Ix) (1 + -=---1
In both cases, the
Our experiments compared SVRG (Algorithm 4 and SGD (Algorithm) 1. The only modification to the algorithms was that mini-batches were used to make the gradient estimates. For each algorithm determined the values of the learning rate and mini-batch size using validation learning rate, we searched over the values 7 E {0.001, 0.01, 0.1, 1.0). For the mini-batch size, we considered values in (32, 64, 1283. The values used for full training were determined by running the training procedure for several epochs and evaluating the resulting model on a held-out portion of the training dataset. The parameters that gave best performance on this held-out dataset were used for full training. Using the found settings, we ran five independent runs of training, and report the mean and confidence bands (representing one standard deviation) for the expected IFO calls.
For the
26


Reviews:
[{"review_id": "rJgTmIO6Kr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors consider stochastic optimization in the setting where a validation function is used to guide the termination of the algorithm. In more details, the algorithm terminates if the gradient of the validation function at an iterate is smaller than a threshold. In this framework, the authors consider several variants of SGD, including distributed variant and SVRG, for each of which the authors study the expected number of iterations for a prescribed accuracy under an assumption between the training and validation set.\n\nWhile the use of a validation function is useful for early stopping, it introduces additional cost.\n\nWhile bounds on the expected number of iterations are derived for several variants of SGD, it seems that most arguments are adapted from the existing analysis to take into account the validation function.\n\nIn Corollary 3.4 and Corollary 3.5, the bound is an increasing function of m. This suggests that the best choice would be m=1. However, in this case, one needs to calculate the gradient of the validation function at each iteration, which may wastes a lot of computation.\n\nThe authors consider constant step sizes. In practice, step sizes are often decreasing along the optimization. Can the analysis be extended to cover the case with decreasing step sizes?\n\nIn eq (30), there is a missing factor of 2.\n\nThere is a required $\\epsilon>G62d_1(\\mu_V,\\mu_T)^2$ in the results. Therefore, to achieve a high accuracy we need $d_1(\\mu_T,\\mu_T)$ to be small. How many numbers of sample size to make $d_1(\\mu_V,\\mu_T)$ small? This has an influence on the computational cost.\n\n\n----------------------\nAfter rebuttal:\n\nThe authors do not respond. I would like to keep my original score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "r1gFw9KcFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the problem of the number of first-order-oracle calls for the SGD type of algorithms to find a stationary point of the objective function. The main results in the paper are built upon a new, general framework to analyze the SGD type of algorithms.\n\n\nThe main framework can be summarized as follows: At each iteration, the algorithm receives h_t, a (potentially biased) estimator of the gradient at a given point x_t, and performs a simple update x_{t + 1} = x_t - \\eta * h_t. The framework says that as long as the norm (V_t) of \\Delta_t = h_t - v_t (where v_t is an unbiased estimator of the true gradient with bounded variance) satisfies a particular Lyapunov-type inequality, then the algorithm can find an epsilon-stationary point as long as epsilon is not too small. \n\n\nThe analysis of the framework is quite standard, one only needs to write the decrement in function value at each iteration into the following three terms: the norm of the true gradient of the function, \\delta_t: the difference between v_t and the true gradient (so E[\\delta_t] = 0) and \\Delta_t: the difference between the received gradient h_t and v_t.\n\n\nThe authors showed some application of this framework in Stacked SGD and decentralized SGD. The main intuitions of these applications are (1). \\Delta_t comes from the synchronization difference of the nodes when computing the gradient. (2). The shrinking of V_t is due to the  (better) synchronization at each iteration. (3). The increment of V_t is due to the gradient update. \n\nOverall, I find the general framework quite interesting and potentially useful for future research and could be used as a guide for choosing the proper algorithm in distributed computation.  The bounds in this paper are also in principle tight. The only question I have about this result is the dependency of m (the number of iterations between each evaluation of the gradient norm of the underlying function). (1). How can this (the evaluation of the gradient norm of the underlying function)) be done in a decentralized environment? What is the computation overhead?  (For example in DSGD, how can we compute \\bar{x}_t?) (2). It seems that the computation cost (number of IFO) scales quadratically with respect to m. What is the intuition for this scaling? It appears to me that the scaling should be linear or better (the worst case is that within the \"m\" iterations, only one iteration has gradient >= epsilon). The authors should elaborate more on this point.\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1ghnfO49B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an optimization approach in which the optimizer computes the gradient on a given function yet uses another to decide a stopping time. Conceptually those functions are empirical errors on train and validation folds in the most common setting, although the authors seem to use other settings later in the paper to consider decentralized optimization schemes. The authors introduce a bound on the Wasserstein distance between the train and validation distributions in their analysis which plays a crucial role in their results. The authors use these results to motivate variants of existing optimization algorithms. \n\nThe paper is interesting but its message is a bit blurred to me. I had trouble pinpointing one main contribution, since the paper is split as theory (with some results) and a collection of slightly modified SGD type algorithms that are now impacted by this \"gradient somewhere / monitor progress elsewhere\". The theoretical results are worth reading and the idea appealing. \n\nThe paper also requires a *lot* of polishing. It has been sloppily written. For these reasons I am inclined to reject the paper and encourage the authors to improve their draft with a better formulation.\n\n\nMinor comments:\n- I have found the \"main contributions\" paragraph to be poorly phrased. Since the authors only monitor the validation loss and not the training loss, I do not think this falls into the \"standard\" definition of early stopping. \n- please use citet and citep consistently. \n- please add labels to figures and format them properly (e.g. SSGD on p.6) \n- unsure about the format used to display f_T(x_t) in p.6\n- Villani 2008 has over 900 pages. any page in particular?\n- Assumption 2.3 requires significantly more work... All bounds scale as G^2 (e.g. eq.9, 10,11), therefore an idea of what G's impact on the analysis sounds crucial. In Example 2.4 the authors start working out an example, but wouldn't it be more interesting to carry that out completely, e.g. for the KL? What kind of bound would that result in?\n- I find it disturbing that important comments on some of the crucial quantities (such as descent direction Eq.3) are left out of the algorithmic box... This defeats the purpose of having an algorithmic box.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors made no response to reviewers. Based on current reviews, the paper is suggested a rejection as majority.
Decision: Reject