Continuized Accelerations of Deterministic and Stochastic Gradient Descents, and of Gossip Algorithms
Authors: Mathieu Even
Raphaël Berthier
Francis Bach
Nicolas Flammarion
Hadrien Hendrikx
Pierre Gaillard
Laurent Massoulié
Adrien Taylor
Venue: NeurIPS 2021 Oral (2021)
Keywords: Convex optimization
Nesterov acceleration

Abstract: We introduce the ``continuized'' Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continuously mix following a linear ordinary differential equation and take gradient steps at random times. This continuized variant benefits from the best of the continuous and the discrete frameworks: as a continuous process, one can use differential calculus to analyze convergence and obtain analytical expressions for the parameters; but a discretization of the continuized process can be computed exactly with convergence rates similar to those of Nesterov original acceleration. We show that the discretization has the same structure as Nesterov acceleration, but with random parameters. 
We provide continuized Nesterov acceleration under deterministic as well as stochastic gradients, with either additive or multiplicative noise.  Finally, using our continuized framework and expressing the gossip averaging problem as the stochastic minimization of a certain energy function, we provide the first rigorous acceleration of asynchronous gossip algorithms.

A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
Mathieu Even!*, Raphaël Berthier",, Francis Bach', Nicolas Flammarion', Pierre Gaillard', Hadrien Hendrikx', Laurent Massoulié and Adrien Taylor'
Equal contributions
Inria Département d' d'informatique de I'ENS, PSL. Research University, Paris, France
School of Computer and Communication Sciences Ecole Polytechnique Fédérale de Lausanne
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
MSR-Inria Joint Centre
Abstract
We introduce the "continuized" Nesterov acceleration, close variant Nesterov acceleration whose variables are indexed by continuous time parameter. The two variables continuously mix following linear ordinary differential equation and take gradient steps at random times. This continuized variant benefits from the best of the continuous and the discrete frameworks: as a continuous process, can use differential calculus to analyze convergence and obtain analytical expressions for the parameters; and a discretization of the continuized process be computed exactly with convergence rates similar to those of Nesterov original acceleration. We show that the discretization has the same structure Nesterov acceleration, but with random parameters. We provide continuized Nesterov acceleration under deterministic as well as stochastic gradients, with either additive or multiplicative noise. Finally, using our continuized framework and expressing the gossip averaging problem as the stochastic minimization of a certain energy function, we provide the first rigorous acceleration of asynchronous gossip algorithms.
Introduction
In the last decades, the emergence of numerous applications in statistics, machine learning and signal processing has led to renewed interest in first-order optimization methods [10]. They enjoy a low iteration cost necessary to the analysis of large datasets. The performance of first-order methods was largely improved thanks to acceleration techniques (see the review by d' Aspremont al. [14] and the many references therein), starting with the seminal work of Nesterov [42].
Let f Rd + R be a convex and differentiable function, minimized at x, E Rd. We assume throughout the paper that L-smooth, i.c..
Vx, y E Rdd
f()) < f(x) (Vf()). |ll x
(1)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In addition, we sometimes assume that f is p-strongly convex for some μ > 0, i..,
Var, y IRd, f(y) (a) + (V/()). x) +
1 2 x11²
(2)
For the problem of minimizing f. gradient descent is well-known to achieve rate f(zx) f(x.) = O(k-1) in the smooth case, and a rate f'(xx) f(x)) = O((1-1/ ))) in the smooth and strongly convex case. In both cases, Nesterov introduced an alternative method with essentially the same iteration cost, while achieving faster rates: it converges with rate O(k 3) in the smooth convex case and with rate ((11 V (/) in the smooth and strongly convex case [43]. These rates are then optimal among all black-box first-order methods that access gradients and linearly combine them [43, 41].
Nesterov acceleration relies on several sequences of iterates-two or three, depending on the formulation and on clever blend of gradient steps and mixing steps between the sequences. Different interpretations and motivations underlying the precise structure of accelerated schemes were approached in many works, including [12. 24, 3. 32, 2J. A large number of these works studied continuous time equivalents of Nesterov acceleration, obtained by taking the limit when stepsizes vanish, or from variational framework. The continuous time index t of the limit allowed to use differential calculus to study the convergence of these equivalents. Examples of studies relying on continuous time interpretation include [50, 33, 54, 53, 9, 18, 48, 49, 4, 5, 57, 40].
Continuized Nesterov acceleration. In this paper. we propose another continuous time equivalent to Nesterov acceleration, which we refer to as the continuized Nesterov acceleration, which avoids vanishing stepsizes. It is built by considering two sequences se, 2t RRd / E Rgo. that continuously mix following a linear ordinary differential equation (ODE), and that take gradient steps at random times T1, T2, ....... Thus, in this modeling, mixing and gradient steps alternate randomly.
Thanks to the continuous index t and some stochastic calculus, one can differentiate averaged quantities (expectations) with respect to f. In particular, this leads to simple analytical expressions for the optimal parameters as functions of f, while the optimal parameters of Nesterov accelerations are defined by recurrence relations that complicated to solve.
The discretization ã = ITz 2 = TTz k N, of the continuized process can be computed directly and exactly: the result is recursion of the same form as Nesterov iteration, but with randomized parameters, and performs similarly to Nesterov original deterministic version both in theory and in simulations.
The continuized framework can be adapted to various settings and extensions of Nesterov acceleration. In what follows, we study how the continuized acceleration behaves in the presence of additive and multiplicative noise in the gradients. In the multiplicative noise setting, our acceleration satisfies convergence rate similar to that of [30] and depends on the statistical condition number of the problem hand. The two acceleration schemes are not directly comparable as we work in continuized setting and only deal with pure multiplicative noise. Our analysis is nevertheless much simpler, as it closely mimics that of Nesterov acceleration.
Application to accelerated gossip algorithms. The continuized modeling is natural in asyn- chronous parallel computing where gradient steps arrive at random times. More importantly, there are situations where the continuized version of Nesterov acceleration can be practically implemented while the original acceleration not. In distributed settings, for instance, the total number k of gradient steps taken in the network is typically not known to each particular node; an advantage of the continuized acceleration is that it requires to know only the time and not k.
Gossip algorithms typically feature such asynchronous and distributed behaviors [11]. In gossip problems, nodes of network aim at computing the global average of all their values by commu- nicating only locally (with their neighbors), and without centralized coordination. In this set-up, pairs of adjacent nodes communicate at random times, asynchronously, and in parallel, that the total number of past communications in the network at a given time is unknown to all nodes. In this paper, we formulate the gossip problem as stochastic optimization problem. Thanks to the continuized formalism, we naturally obtain accelerated gossip algorithms that can be implemented in an asynchronous and distributed fashion.
Synchronous gossip algorithms rely on all nodes to communicate simultaneously [19]. Accelerating synchronous gossip algorithms have been studied in previous works, including SSDA [47], Chebyshev

---

acceleration [39], Jacobi- Polynomal acceleration [7]. To that day, acceleration in the asynchronous setting has also been studied in a few works (see for instance geographic gossip [20], shift registers [37], ESDAC [25], and randomized Kaczmarz methods [38]). However, no algorithm in an asyn- chronous framework has been rigorously proven to achieve an accelerated rate for general graphs [21]. Other acceleration schemes [25, 38] relied on additional synchronizations between nodes, such as the knowledge of a global iteration counter. This departs from purely asynchronous operations, hence causing practical limitation. Our accelerated randomized gossip algorithm (Section 6) recovers the same accelerated rates, and only requires the knowledge of a common continuous-time t R30-
In this context, the continuized acceleration should be seen as a close approximation to Nesterov acceleration, that features both an insightful and convenient expression as a continuous time process and direct implementation as discrete iteration. We thus hope to contribute to the understanding of Nesterov acceleration. In practice, the continuized framework relevant for handling asynchrony in decentralized optimization, where agents of network can not share global iteration counter, preventing accelerated decentralized and asynchronous methods.
Notations. The index k always denotes a non-negative integer, while indices t, s always denote non-negative reals.
we recall standard results on gradient descent and Nesterov acceleration. In Section 3, we introduce a continuized variant of Nesterov acceleration. In Section we show that discretizing the continuized acceleration yields an iterative method similar to that of Nesterov but with random parameters. In Section 5, we study continuized Nesterov acceleration under pure-multplliative noise. We finally present accelerated asynchronous algorithms for the gossip problem in Section 6, as well as for decentralized optimization in Section 7.
Structure of the paper. In Section 2,
2 Reminders on Nesterov acceleration
For the sake of comparison, let us first recall the classical Nesterov acceleration. To improve the convergence rate of gradient descent, Nesterov introduced iterations of three sequences, parametrized by Thi The Th, The k 0, of the form
yk: = 3k + FA (2k= rkk,
(3)
2k+1 yk 7/ V f3x)
(4)
2k+1 2 + (3k 24) 7 fzx)).
(5)
Depending on whether the function f is known to be (1) convex, or (2) strongly convex with a known strong convexity parameter, Nesterov provided set of parameter choices for achieving acceleration.
Theorem (Convergence of accelerated gradient descent). Nesterov accelerated scheme satisfies:
1. Choose the parameters Tk = 1 sequence Au; k 2 0, defined by the recurrence relation
A T = 0, +.-% Aut1 Au k 2 0, where the A
Ao = 0,
AR+1 = Au + (1+ 4A4 +1)
Then
2L 200 x-
f(z)) f(x.) <
k22
2. Assume further that f is p-strongly conver, 0. Choose the constant parameters
La/L 1t/U/L' T/ VF. 7k = 7/2 = =/ k > 0. Then
The
M &
f(xx) f(x)) <
- f(x)) (f(x0)
11 11 xx113)
(1-V
This result can be found as is in Aspremont et al. [14, Sections 4.4.1 and 4.5.3). In the convex case, Nesterov acceleration achieves the rate O(1kk2), whereas gradient descent achieves rate O(1/k)
3

---

(see [43, Corollary 2.1.2] for instance). In the strongly convex case, Nesterov acceleration achieves the rate ((11 //)L)), where gradient descent achieves rate O((1 ///L)² (see [43, Theorem 2.1.15] for instance). In both cases, this results significant speedup in practice, see Figure 1.
From high-level perspective, Nesterov acceleration iterates over several variables, alternating between gradient steps (always with respect the gradient at yı)) and mixing steps, where the running value of a variable is replaced by a linear combination of the other variables. However, the precise way gradient and mixing steps are coupled is rather mysterious, and the success of the proof of Theorem relies heavily on the detailed structure of the iterations. In the next section, we try to gain perspective on this structure by developing a continuized version of the acceleration.
3 Continuized version of Nesterov acceleration
This paper uses several mathematical notions related to random processes. The following sections expose the results from heuristic considerations of those notions, rigorously defined in Appendix C.
We argue that the accelerated iteration becomes more natural when considering two variables Tt, St indexed by continuous time t > 0, that are continuously mixing and that take gradient steps at random times. More precisely, let Ti. T2, T3.... 3 be random times such that 71, T: Ti. T3 T2, are independent identically distributed (i.i.d),, of law exponential with rate 1 (any constant rate would do, we choose to make the comparison with discrete time k straightforward) By convention, we choose that our stochastic processes + Iz, t + 2; are càdlåg almost surely, i.e., right continuous with well-defined left-limits Tt-; -t- (Definition 6 Appendix C). Our dynamics are parametrized by functions Yt, Ve, Tay T/2 > 0. At random times T1, T2,.... ...,. our sequences take gradient steps
IT, IT 7TV V ((TT.-).
(6)
2T, 2T, M/. (xT..-)
(7)
Because of the memoryless property of the exponential distribution, in infinitesimal time interval [t, t + dé). the variables take gradients steps with probability dt, independently of the past. Between these random times, the variables mix through a linear, conslation-invaiiann ordinary differential equation (ODE)
dæ, = me( - xt)dt,
(8)
dz, = 1/((zr - 2t)
(9)
Following the notation of stochastic calculus, we can write the process more compactly in terms of the Poisson point measure (t) = Σx21 5r, (dt), which has intensity the Lebesgue measure dt,
dr,- (= z, 2,)df v ((2)))N((), dæ;- = = (x, 2 2, (V
(10)
(11)
Before giving convergence guarantees for such processes, let us digress quickly on why we can expect an iteration of this form to be mathematically appealing.
First, from Markov chain indexed by discrete time index k can associate the so-called continuized Markov chain, indexed by a continuous time t, that makes transition with the same Markov kernel, but at random times, with independent exponential time intervals [1]. Following this terminology, we refer to our acceleration (10)-(11) as the continuized acceleration. The continuized Markov chain is appreciated for its continuous time parameter while keeping many properties of the original Markov chain; similarly the continuized acceleration is arguably simpler to analyze, while performing similarly to Nesterov acceleration.
Second, it can also be compared with coordinate gradient descent methods, that are easier to analyze when coordinates are selected randomly rather than in ordered way [55]. Similarly, the continuized acceleration is simpler to analyze because the gradient steps (6)-(7) and the mixing steps (8)-(9) alternate randomly, due to the randomness of Tk. k > 0.
In analogy with Theorem 1, we give choices of parameters that lead to accelerated convergence rates, in the convex case (1) and in the strongly convex case (2). Convergence is analyzed as a function of I. As dl)(() is Poisson point process with rate 1, is the expected number of gradient steps done by the algorithm. Thus / analoguous to & in Theorem 1. In the theorem below, E. denotes the expectation with respect to the Poisson point process (t), the only source of randomness.

---

Theorem 2 (Convergence of continuized Nesterov acceleration). The continuized Nesterov accelera- tion satisfies the following two points.
1. Choose the parameters T/1 = 70 = =/:7
L 27.
Then
20/120 x.1
Ef(x)) f(x+) <
12
2. Assume further that f is p-sttrongly convex, μ 0. Choose the constant parameters
7/ = 1/1 = VT. 1. 7/6
= 1
L. 1/- Vit. Then
[((()) - ((x.) & (s(Zr)) - [(x.) + " ||=0 - x. x=al²) exp (-V )
We give an clementary sketch of proof in Appendix D.1 and a complete proof in Appendix D.2. Many authors have proposed continuous-time versions of Nesterov accelcration using differential calculus, see the numerous references in the introduction. For instance, Su et al. [50], an ODE is obtained from Nesterov acceleration by taking the joint asymptotic where the stepsizes vanish and the number of iterates is rescaled. The resulting ODE must be discretized to be implemented; choosing the right discretization is not straightforward it introduces stability and approximation errors that must be controlled [57, 49, 46].
On the contrary, our continuous time process (10)-(11) does not correspond to limit where the stepsizes vanish. However, in Appendix F, we check that the random continuized acceleration has the same deterministic ODE scaling limit as Nesterov acceleration. This sanity check emphasizes that the continuized acceleration fundamentally different from previous continuous-tims equivalents.
Remark 1. A similar Markovian structure be obtained in a discrete setting by flipping i.i.d. coins to trigger gradient steps. By denoting > the probability to trigger a gradient step when flipping coin, (i) p = gives the classical setting, and (ii) p - 0 while renormalizing time gives our continuized framework. In fact, this setting with updates triggered randomly is an interpolation between the classical and continuized frameworks, and consists in replacing exponential random variables by geometric random variables of parameter p for the waiting-time between updates. We thus believe the convergence guarantees described here and in the following can be adapted for this discrete scheme.
4 Discrete implementation of the continuized acceleration with random parameters
In this section, we show that the continuized acceleration can be implemented exactly as a discrete algorithm. This contrasts with the discretization of ODEs that introduces discretization errors; here, we compute exactly
fx TT.
ÿk 1T--1-1
ZT
with the convention that To 0. The three sequences 75; Uk. 2t. 3 0, satisfy a recurrence relation of the same structure Nesterov acceleration, but with random weights. The resulting randomized discrete algorithm satisfies performance guarantees similar to those of Nesterov acceleration. Theorem (Discrete version of continuized acceleration). For any stochastic process of the form (10)-(11), we have
i 3t + TA (2t Tx))
(12)
ē 1 = .b 7/ V (ūix)
(13)
Ex+1 Ex + 7/e (5k
Σn) -
V(
(14)
for some random parameters Tk, The 3k. 5% (that are are functions of Tk. T Tk+1, Me, Vec 76, (.)
1. For the parameters of Theorem 2.(1), Tk = =1- Then
Tki
T5
T/ 0, 5ル t, and 7/2 Te
27.
E T (f(Ex) f(xx))) < 2L x 12
5

---

2. For the parameters of Theorem 2.12), T = exe (-2v
(T&+1 - Tk))),
Tie tanh (VE(Te++ Te)), 9h- and A// VJT. Then
E exp (1 (f(āx) -f(z))))((())) < f(z0) - f(x.) + H 21120 - I 1.112.
The law of Tk is well known: is the sum of & i..d. random variables of law exponential with rate 1; this is called Brlang or Gamma distribution with shape parameter & and rate 1. One can well-known properties of this law, such as its concentration around its expectation E7₃ = k. to derive corollaries of the bounds above. The performance guarantees are proved in Appendix D.2, and the formula for the discretization is studied in E. In Appendix A.I, we provide simulations confirming that this discrete random algorithm has a performance similar Nesterov's original acceleration.
5 Continuized Nesterov acceleration of stochastic gradient descent
We now investigate the design continuized accelerations of stochastic gradient descent. We assume that we do not have direct access the gradient (x()) but to random estimate (xr, where E E E is random of law P. In the continuized framework, the randomness the stochastic gradient and its time mix particularly convenient way. For similar reasons, Latz studied stochastic gradient descent as a gradient flow on a random function that is regenerated at a Poisson rate [35]. However, this approach has the same shortcomings as the other approaches based on gradient flows: the subsequent discretization introduces non con-trivial errors. We avoid this problem here.
We keep the algorithms of the same form, replacing gradients by stochastic gradients. Let & E be i.i.d. random variables law P. We take stochastic gradient steps at the random times Tú, .2.....
STy = IT, "T, TT. = 2T, Vr, Vf(TT,,
Between these random times, the variables mix through the same ODE
dr. = (= - xe )lt
dæ = (/6 - 2, dt.
This can be written more compactly in terms the Poisson point measure dt(t,g) Σai1 o(n,e,) de) R Rzo x E, which has intensity di s P.
=
dæ. = n= - xz)dl - / V[(E,,))N((E))
(15)
dz 1/( 2ddt 7e J V
(16)
Here, the discussion depends on the propertics satisfied by the stochastic gradients (f In Appendix B, study the so-called additive noise case. We show that the continuized acceleration satisfies perturbed convergence rates with the same choices parameters as in Theorem 2. We thus show some robustness of the above acceleration to additive noise. Instead, in this section, focus on the so-called pure multiplicative noise case, as is crucial for the study of asynchronous gossip that follows. In this setting, parameters need to be chosen differently for our proof technique work. A continuized acceleration is still possible, depending on the statistical condition number.
We now focus on functions f is of the following form, typical to least-squares supervised learning:
1 (b (x, a))?
Vo TRd f(x) E(a,b)-
(17)
where ş = (a, b) E Rd x R is random of law P. We assume that our stochastic first order oracle is the gradient of one realization of the expectation, namely.
v f(z {) -(b- (x, a))a, (=,
We investigate noiseless or purely multiplicatie- stochastic gradients, in the sense that almost surely, for & = (a, P:
b a), so that (f(r,, 0.
(18)

---

Noiseless stochastic gradients are relevant in several situations, such as coordinate gradient descent with randomly sampled coordinates [51, 44, 55] (where Vf(x,, {) (=Vf(z), ex)e; with i uni- formly random in , d. weer-parameterized regime for least squares regression [52], function interpolation and gossip algorithms [8].
For symmetric non-negative matrix A and vector æ, we denote || - x AA.. Let H E[aa" be the Hessian of f. Let Ri be the smallest positive real number such that:
E
[aal
R
(19)
Further, similarly to Jain et al. [30], we define the statistical condition number of the problem the smallest & > O such that:
E
00
R...
(20)
Theorem 4 (Continuized acceleration with pure multiplicative noise). Assume that (18), (19) and (20) hold true. Then the continuized acceleration satisfies the the following.
1. Choose the parameters T) 2 m/ = 7,
V/
Then
R
2R
Eli - -1 2
xx1 Rs R 10
I- H-1
2. Assume further that is u-strronly convex, i.e., all eigenvalues of H are greater or equal to ps, where >> O. The condition number of f is then defined as = R2 pp. For the
parameters = 7/ VKR = R and 7/- πे / we have:
2 Bll - <
11100 2
+ ~ー 2200 x. 22 1020-1111=
11
exp
VKR
In the strongly convex case, the benefits this acceleration are similar to those of Jain et [30] with classical discrete iterates: while stochastic gradient descent with stepsize 1/R2 is easily shown to achieve an exponential rate of convergence 1/K, the acceleration enjoys a rate of convergence of 1/VRR. Note that from the definitions, & K, thus the acceleration performs as least as well as the naive algorithm. However, depending the distribution of a, the improvement might either be significant or null. We refer the reader to the rich discussion in Jain et al. [30] which provides insights on the interpretation of R and on the possibility to accelerate. Below, perspective on the statistical condition number in the context of gossip algorithms, where it can be interpreted in terms of effective resistances of graphs.
provide complementary
Albeit more restrictive terms of assumptions, our analysis much simpler than that of Jain et al. [30], as it relies on standard Lyapunov function, similar to that of the continuized acceleration (Theorem 2). In Appendix G, we use the same analysis framework to prove convergence of accelcrated coordinate descent, which is another noiseless stochastic method.
6 Accelerating Randomized Gossip
The continuized framework allows designing accelerated decentralized algorithms requiring syn- chronized clocks, but no synchronization of the communications. In this section, we illustrate this statement in the simple case of gossip algorithms; the more general case of decentralized optimization discussed in the next section.
Let G = E) a connected graph representing a communication network of agents. Each agent E V is assigned a real number zo 2v(v) R. The goal of the averaging (or gossip) problem is to design an iterative procedure allowing each agent of the network to know the average x = Evey xn (v) using only local communications, i.e., communications between adjacent agents in the network.
We formalize the communication model of randomized gossip [11]. Time is indexed continuously in Rz0- We generate a Poisson point measure d.V (t, e) Σ.>1 (va,o.) with intensity measure dt @ P. where dt is the Lebesgue measure Rzo and (P(n.w)) (E a probability measure on the set & of edges. For 0, Tj is time at which edge {uk, w is activated: adjacent nodes uk
7

---

and wy can communicate and perform pairwise update. The Poisson point measure assumption implies that edges are activated independently one another and from the past: the activation times of edge {v, w) form a Poisson point process of intensity P Ptv,w}-
To solve the gossip problem, Boyd et al. [11] proposed the following naive strategy: each agent V keeps a local estimate x+(v) of the average and, upon activation of edge {uk, wx at time Ti E R3o. the activated nodes Uk: wy average their current estimates
FT. - (Ux) + IT. (Tn-(ww)
Sr, (wk), 27y (wk)
In this section, we accelerate this naive procedure. Our strategy is to apply Section 5 as follows. Consider the energy function
f(z)
Σ
-
P P(v.a) (x(v) (oc(o)-r(w))) x(w))²
x = (x(U))vEV.
(21)
2
(D.WEE
This function convex, smooth, and writes the form (17):
1 (2. a (m,en)
)²
f(x) [m,wr)>>
(22)
2
where (w.ar) = Ee ew and (ee)eEv forms the canonical basis of R As in Section 5, stochastic gradient of f is obtained by taking the gradient of one realization of the expectation, namely:
x(v)) x(w) axw) xxv)
at coordinate e, at coordinate w; all other coordinates.
Vf(z, w)) = (z,, (1,w)))aen
(23)
0
As a consequence, a stochastic gradient step with stepsize 1/2 corresponds to a local averaging alongside edge {u, w), where {v,w} w) ~ P. More generally, the randomized gossip algorithm as described by Boyd al. [11] is the stochastic gradient descent:
dx,
Vf(ce, (u, (I) (v,
(24)
Using Section 5, we can accelerate this algorithm if we know the strong convexity parameter of f and the constants R² and R as defined in (19) and (20) respectively. These constants can be intepreted as graph-related quantities here.
Definition (Graph-related quantities). The Laplacian matrix L E RVVV of graph G with weights (Pta,et) (U,w)Eg on the edges is the matrix with entries Lu, = -P(www) if {v, w. E E, Cu,0 Enwo P(u,u). and f.,. est eigenvalue of L, corresponding to its smallest positive eigenvalue. For {u, w) E E, let Rea (v, (e(v) e(w)) -- - e(w)) be the effective resistance of edge {u, w), and Rmax = (a.wu..) Res (v, w) be the maximal resistance the graph.
if {u, [u,w}
E. We denote Pgussii the second small-
The function is quadratic with Hessian L, and strongly convex with parameter lggoesip the hyperplane F = {x E RV; Evey =u)) = :} hence we use the (perhaps abusive) notation Mggosiip throughout. Moreover, the conditions (19) and (20) are satisfied with R² 2, R Rmax-
These parameters being given, the accelerated stochastic gradient descent updates (15)-(16) can be instantiated as follows. Each agent E V keeps two local estimates zz(v), (v) of F, initialized at (v). Upon activation edge {uk, 3 at time Ti.
IT, (vx) IT, (wk)
IT, (vk) = IT, (wx)
1
2n. (vt) 2I -Vx) +
(IT (wk) IT (vx))
/ Pgosssip Rmax
2T, (wk) 2I2 2
(IT, (vx) -TT- (wk))
v (ppgossi Rmaxx
8

---

Between these updates, (1) and 2<(e) locally mix at all nodes V. according to the coupled ODE:
(r)( =V 2ugussip (z((1) - (t))dd,
Rmax
dzz(v) V /Pggosspp (se(()-=(())))
ze (())dd
Riax
This algorithm is asynchronous in the sense that it does not require global synchronous operations: the mixing of local variables does not require any synchronization since parameter i Rgo is available at all nodes independently from the number of past updates, while local pairwise update between adjacent nodes v and only requires a local synchronization.
Theorem (Accelerated randomized gossip). Let (zz(t)) be generated with accelerated randomized gossip. For any 1 E Ikzo:
Σ DEV
{ -2)² <
(<)(
Σ 2 =x)² exp (-1) Agossip ADEV
-x)?
(-V
2fmax
Let OARG V
Mggeer be the of convergence of accelerated randomized gossip, and ORG 2femax
Mgossiip be the rate of convergence of randomized gossip [11]. We have AARG 2 ORG/ V2. Let us exhibit scenarios over which accelerated randomized gossip gains several orders of magnitude. Denot- ing Punin = (w,we, P(y,a) Ellens et al. [22] ensures that for {v,w] E E, Pmii Rest (v, w) < so that Rmax Pmin-
Corollary (Comparison with randomized gossip). Accelerated randomized gossip achieves rate satisfying:
ORG P min 2
<
AARG.
Assume furthermore that there exist constants 0 such that for all {u, w) E E, P(w,w) &
Panin and dy + du & 2d. Then, with C = 11/V2od:
BnG MV
V
< OARG.
Assume now for simplicity that the Poisson intensitics P(n.w) are all equal to 1/|8). Denoting
[V] = m, on the cyclic and the line graph, this gives us AARG = 1211m2m1m while ARG = 1/m3 On a d-dimenssioal grid, we have AARG (111m111/// and ORG = 1 142/d However, on graphs with unbounded degrees, improvements are observed, illustrated in Figure 2, Appendix A.2. In the case of the complete graph, this is expected since least 0g) to compute the average. We thus recover the same rates as Dimakis et al. [20] for the graphs they study, but generalized any network.
communications
needed
7 Accelerating Asynchronous Decentralized Optimization
Our continuized framework for accelerating randomized gossip can be extended to the more general problem of decentralized optimization: each node in the network G previously defined holds function fo Rd + +R, j--ttrongly convex and L-smooth. Nodes of the network collaborate to solve:
((0) =
min ZER
Σ lo(a)) NEV
(25)
V
As in gossip averaging, only local communications are allowed. Quantities related to fo can only be computed at node In the case of empirical risk minimization, fo represents the empirical risk related to node v's local data. Setting fo( } - =n)x) leads to the averaging problem previously described. Similarly to Section 6, time is indexed continuously by in IR 200 and communications

---

ruled by the same Poisson point measure dN((t,) = oeT (m.)) on Rz0 x E. Yet, we no longer assume (as in Theorem 4) that the function f is quadratic. Instead, we write a dual formulation of Problem (25) and minimize using continuized version of accelerated coordinate descent [45] that we present in Appendix G. This leads to an accelerated decentralized algorithm to solve (25). Our algorithm mimics the behavior of accelerated randomized gossip: a node possesses two local parameters that mix continuously through a time- lime-independent ODE. At time Tı, adjacent nodes Up and wi use their local function in order to compute gradient conjugates V Sā (2(w)), V V. (x(()): Since the local functions are not simple quadratics anymore, the stochastic gradients V {u, w from Equation (26) are replaced by terms proportional to:
V((())) V (l((((w)) Vf
coordinate v, at coordinate w, at all other coordinates.
Gly. (v,
(26)
Due to lack of space, we describe the iterations more in details in Appendix H. together with relevant choice of parameters. The crucial point is that, similarly to the gossip averaging case, we do
not require nodes be aware of a global iteration counter. Yet, we still obtain the same convergence rate as [25]. as provided by the following theorem. The same approach can be used to "continuize" other accelerated randomized gossip algorithms for decentralized optimization, such as ADFS [26]. Theorem 6 (Accelerated asynchronous decentralized optimization). For (II(U)) =
(Z (z)())) generated by the accelerated coordinate descent on the dual of Problem (25):
[[l=((o)-x111 x110- & & Σ = =x.1?? NEVV
(-
[BARGG Vn
exp
BEV
where K. = po/L an upper bound on the condition number of f. C' is a constant that depends on the graph and K. and ARR the rate convergence of accelerated randomized gossip the graph G as defined in Theorem but with graph resistances are defined in a different way (see Theorem 10).
Conclusion
In this work, we introduced continuized version of Nesterov's accelerated gradients. In nutshell, the method has two sequences of iterates which take gradient steps random times. In between gradient steps, the two sequences mix following a simple ordinary differential equation, whose parameters are picked to ensure good convergence properties of the method.
As compared to other continuous time models of Nesterov acceleration, a key feature this approach is that the method can be implemented without any approximation, the differential equation governing the mixing procedure has a simple analytical solution. A discretization of the continuized method corresponds an accelerated gradient method with random parameters.
Continuization strategies were introduced in the context of Markov chains [1]. Here, they allow using acceleration mechanisms in asynchronous distributed optimization, where usually agents not aware of the total number of iterations taken so far. This is showcased in the context of asynchronous gossip algorithms.
Acknowledgements:
The authors thank Sam Power for pointing out the class of piecewise de- terministic Markov processes and related references, and an anonymous reviewer for suggesting Remark 1. This work was funded in part by the French government under management of Agence Nationale de la Recherche part of the "Investissements d' avveir"" program, reference ANR-19- (PRAIIIE 3IA Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063), from the DGA, and from the MSR-INRIA joint centre.
References
[1] David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs. 2002. Unfinished monograph, recompiled 2014, available at http: httt://wwwnr /ttp:///wwwwwee stat. berkeley. http://ssmmaaadoss..eo www.dddoouuu///////o bbokk html.
[2] Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. Proceedings of the 8th Innovations Theoretical Computer Science, ITCS 17, 2017.
10

---

[3] Yossi Arjevani, Shai Shalev-Shwarke and Ohad Shamir. On lower and upper bounds in smooth and strongly convex optimization. Journal of Machine Learning Research, 17(126):1-51, 2016.
[4] Hedy Attouch, Zaki Chbani, Juan Peypouquet, and Patrick Redont. Fast convergence inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming, 168(1):123-115 175, 2018.
[5] Hedy Attouch, Zaki Chbani, and Hassan Riahi. Rate of convergence of the Nesterov accelerated gradient method in the suberitical case a & 3. ESAIM: Control, Optimisation and Calculus of Variations, 25:2, 2019.
[6] Neodet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. Robust accel- erated gradient methods for smooth strongly convex functions. SIAM Journal on Optimization, 30(1):717-751, 2020.
[7] Raphaël Berthier, Francis Bach, and Pierre Gaillard. Accelerated gossip in networks of given dimension using jacobi polynomial iterations. SIAM Journal on Mathematics of Data Science, 2(1):24-47, 2020.
[8] Raphaël Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. In Advances in Neural Information Processing Systems, volume 33, pages 2576-2586, 2020.
[9] Michael Betancourt, Michael Jordan, and Ashia Wilson, On symplectic optimization. arXiv preprint arXiv: 1802.03000 2018.
[10] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-33) 1, 2018.
[11] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2530) 2006.
[12] Sébastien Bubeck, Yin Tat Lee, and Mohit Singh. A geometric alternative to Nesterov's accelerated gradient descent. arXiv preprint arXiv:1506.08// 2015.
[13] Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia. On acceleration with noise- coruppeed gradients. In Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1019-1028. PMLR, 2018.
[14] Alexandre A'Apremoot,, Damien Scieur, and Adrien Taylor. Acceleration methods. 2021.
[15] Mark HA Davis. Piecewise-dettermnistte markov processes: a general class of non-diffusion stochastic models. Journal of the Royal Statistical Society: Series B (Methodological), 46(3): 353-376, 1984.
[16] Mark HA Davis. Markov models & optimizution. Routledge, 2018
[17] Olivier Devolder. Stochastic first order methods in smooth convex optimization. Technical report, CORE, 2011.
[18] Jelena Diakonikolas and Lorenzo Orecchia. The approximate duality gap technique: A unified theory of first-order methods. SIAM Journal on Optimization, 29(1):660-66) 689, 2019.
[19] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione. Gossip algorithms for distributed signal processing. Proceedings of the IEEE, 188411488741884 2010.
[20] Alexandros D. G. Dimakis, Anand D. Sarwate, and Martin J. Wainwright. Geographic gossip: Efficient averaging for sensor networks. IEEE Transactions on Signal Processing, 56(3): 1205-1216. 2008. ISSN 1053-587X. doi: 10.1109/tsp.2001 2007999996 URL http://dx.doi. org/10. 1et.i11199//9 /TPP 2007 908946.
[21] Alexandros DG Dimakis, Anand D Sarwate, and Martin J Wainwright. Geographic gossip: Efficient averaging for sensor networks. IEEE Transactions on Signal Processing, 56(3): 1216-121, 2008.
11

---

[22] W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, and R.E. Kooij. Effective graph resistance. Linear Algebra and its Applications, 435(10):2411-256, 2011. ISSN 0024-3795. doi: https///ooioogg//00000o.aaa2222. 202.004. URL https: //www. sciencedi com/ cctpsee/aattiaa//////0227711111. Special Issue in Honor of Dragos Cvetkovic.
[23] Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié. Decentralized optimization with heterogeneous delays: a continuous-time approach. arXiv preprint arXiv:2106.0355, 2021.
[24] Nicolas Flammarion and Francis Bach. From averaging to acceleration, there is only step-size. In Conference on Learning Theory, pages 658-695. PMLR, 2015.
[25] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Accelerated decentralized optimiza- tion with local updates for smooth and strongly convex objectives, 2018.
[26] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. An accelerated decentralized stochas- tic proximal algorithm for finite sums. arXiv preprint arXiv: 1394, 2019.
[27] Chonghai Hu, Weike Pan, and James Kwok. Accelerated gradient methods for stochastic optimization and online learning. In Advances in Neural Information Processing Systems, volume 22, pages 781-789, 2009.
[28] Nobuyuki Ikeda and Shinzo Watanabe, Stochastic differential equations and diffusion processes. Elsevier, 2014.
[29] Jean Jacod and Albert Shiryaev. Limit theorems for stochastic processes, volume 288. Springer Science Business Media, 2013.
[30] Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Ac- celerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pages 545-604, 2018
[31] Sham Kakade, Shai Chalev-Shwartz and Ambuj Tewari. On the duality of strong convexity and strong smoothness:
Learning applications and matrix regularization. Unpublished Manuscript, http: // ttic. uchicago. edu/ shai/ paciss/ppprs///eee KakadeSha wwweeehaawwwwwwaaaae evTewari09. pdf. 2009.
[32] Donghwan Kim and Jeffrey A Fessler. Optimized first-order methods for smooth convex minimization. Mathematical programming, 159(1):1-107, 2016.
[33] Walid Krichene, Alexandre Bayen, and Peter Bartlett. Accelerated mirror descent in continuous and discrete time. Advances in Neural Information Processing Systems, 28:2845-2888 2853, 2015.
[34] Guanghui Lan. An optimal method for stochastic composite optimization. Math. Program., 133 (1-2, Ser. A):365-395 0006655377,00 2012.
[35] Jonas Latz. Analysis of stochastic gradient descent in continuous time. Statistics and Computing, 31(4):1-25, 2021.
[36] Jean-François Le Gall. Brownian Motion, Martingales, and Stochastic Calculus, volume 274. Springer, 2016.
[37] Liu, Brian D.O. Anderson, Ming Cao, and A. Stephen Morse. Analysis of accelerated gossip algorithms. Automatica, 49(4):873 - 883, 2013. ISSN 0005-1098, doi: https://doi. wtg/:00.006f//aatomaticuu... article/pii/50051999100000
URL http: httt::://www... /www.//wwccoo////o wciencedirectt.................. com/sciens
[38] Nicolas Loizou. Michael Rabbat, and Peter Richtárik. Provably accelerated randomized gossip algorithms. In ICASSP 2019-2019 ieee international conference on acoustics, speech and signal processing (icassp), pages 7505-7509. IEEE, 2019.
[39] Eduardo Montijano, Juan Montijano, and C. Sagues. Chebyshev polynomials in distributed consensus applications. IEEE Transactions on Signal Processing, 61, 11 2011. doi: 10.1 109/ TSP.2012.2226173.
12

---

[40] Michael Muchlebach and Michael Jordan. A dynamical systems perspective on Nesterov acceleration. In International Conference on Machine Learning, pages 4656 4666-666.. PMLR. 2019.
[41] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley- Wiley--nterscience, 1983.
[42] Yurii Nesterov. A method of solving a convex programming problem with convergence rate O(1/k2). Dokl. Akad. Nauk SSSR, 27 376, 1983.
[43] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2003.
[44] Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):311366 2012.
[45] Yurii Nesterov and Sebastian U. Stich. Efficiency the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimizaation, 27(1): (0::):110-22,,,, 2017 doi: 10. 10.1137/16M1060182. URL attps://doi. org/10..//ooooo http://...........1////1//000000 1137/16M1000188.
[46] Jesús María Sanz-Serna and Konstantinos Zygalakis. The connections between Lyapunov functions for some optimization algorithms and differential equations. arXiv preprint vrXiv:2009.00673, 2020.
[47] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithmss for smooth and strongly convex distributed optimization networks. In International Conference on Machine Learning. 2017.
[48] Bin Shi, Simon Du, Michael Jordan, and Weijie Su. Understanding the acceleration phenomenon via high-resolution differential equations. arXiv preprint arXiv:1810 08907, 2018.
[49] Bin Shi, Simon Du, Weijie Su, and Michael Jordan. Acceleration via symplectic discretization of high-resolution differential equations. In Advances in Neural Information Processing Systems, volume 32, pages 5744-5752, 2019.
[50] Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling Nes- terov's accelerated gradient method: theory and insights. Advances in neural information processing systems, 27:2510-2511 2014.
[51] Paul Tseng and Sangwoon Yun. A coordinate gradient descent method for nonsmooth separable minimization. Mathematical Programming. 117(1):387 -23,, 2009.
[52] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1195-1204. PMLR, 2019.
[53] Andre Wibisono, Ashia Wilson, and Michael I Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, (334)))E7331- E7358, 2016.
[54] Ashia Wilson, Benjamin Recht, and Michael Jordan. A Lyapunov analysis of momentum methods in optimization. arXiv preprint arXiv:1611.02633, 2016.
[55] Stephen Wright, Coordinate descent algorithms. Math. Program., 151(1, Ser. B):3-34, 2015.
[56] Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. 2010.
J. Mach. Learn. Res.,
[57] Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct Runge- Kutta discretiza- tion achieves acceleration. In Advances in Neural Information Processing Systems, volume 31, pages 3900-3909, 2018.
13


Reviews:
[{"review_id": "ikG3taYSiDa", "reviewer": "Reviewer_gPzr", "summary": "The authors introduce a novel idea to analyze accelerated methods from a continuized point of view, which allows to have a type of \"random learning rates\". In particular, this allows to be oblivious of the iteration in an asynchronous network, as long as you have a common synchronized clock for the nodes. The analysis shows accelerated rates for their deterministic and stochastic methods, one of which can be applied to obtain acceleration in an asynchronous gossip algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "This is a good paper. The idea of using a continuized analysis for accelerated methods is quite original and it is shown to have some applications that improve, in some domains, the previous state of the art. In my opinion, part of the magic is on Proposition 2, that allows to ignore a term when checking that the Lyapunov functions are supermartingales (otherwise one could just do the regular analysis of accelerated methods, that usually only sets the parameters' values at the end of it, and one could consider which random variables they need to be in order for a final inequality to be satisfied. Because authors use proposition 2, the analysis becomes quite clean and simple).\n\nThe experiments are good showcases of the theory and the examples given as applications are a good addition to check that this analysis gets some gains with respect to non-continuized approaches.\n\nI would have liked to see a comment on the synchronized clocks and the implications of working with them (not how to implement the clocks). In accelerated randomized gossip it is perfectly clear that each step happens when a communication step happens and that in that case the clock is used to set the parameters of the mixing of the two local variables. \n\nHowever in the other cases, like that of acceleration of asynchronous decentralized optimization, a gradient step only happens \"when the clock ticks\", which is something that depends on the communication. This is as opposed to locally computing gradients as fast as your local processor can. So it seems that in these other cases that the paper describes the local nodes would be idle (without computing any gradients) until a communication step happens, which is not realistic. Please clarify to me if I am missing something and if this is not the case.\n\nStill, I think the theoretical contributions of this paper and the other applications are enough for this paper to be published at Neurips. \n\n\nMinor comments:\n\nl213 rephrase\n\nFigure 2: runes -> runs\n\nPost-rebuttal: I thank the authors for their detailed response and willingness to add a comment on the idleness of the nodes due to the setting and the clock\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "--", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "13"}, "extra_text": {}}, {"review_id": "QS8KKCab2ip", "reviewer": "Reviewer_ges3", "summary": "This paper studies accelerated gradient descent algorithm for convex optimization from a continuous-time perspective. The authors introduce the continuized version of Nesterov's accelerated gradient descent (AGD) algorithm, which takes gradient steps at random times with exponentially distributed intervals. The authors show the continuized AGD has accelerated convergence rates in expected function values similar to the standard Nesterov's AGD. The authors derive an exact discretization of the continuized AGD which resembles Nesterov's AGD with random parameters, and show the algorithm has accelerated convergence rates similar to the rates in continuous time. The authors extend their algorithms and analysis to stochastic gradient descent with additive and multiplicative noise. The authors apply their framework to derive accelerated randomized gossip algorithm which can be implemented in a decentralized way.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper introduces the continuized version of Nesterov's accelerated gradient descent (AGD) which takes gradient steps at random times with exponentially distributed intervals. Equivalently, the continuized AGD is modeled as a system of stochastic differential equations driven by Poisson noise. This is a novel perspective that is different from previous works on continuous-time acceleration, which take the limit of step size going to 0 to recover second-order differential equations (or a pair of first-order ODEs). The continuized version of AGD introduced in this work has many advantages, as described in this paper. The continuized AGD in continuous time has accelerated convergence rates similar to the rates for AGD. Furthermore, the continuized AGD can also be discretized exactly (whereas typical discretization of ODEs have errors that need to be controlled carefully), and the resulting algorithm looks like AGD with random parameters with similar convergence rates. The authors extend their algorithms and analysis to stochastic gradient descent, and they also apply their framework to accelerate decentralized randomized gossip algorithm.\n\nThis is an excellent paper that makes a novel conceptual contribution to the study of accelerated gradient descent algorithm. The authors propose a new continuous-time perspective of AGD which will likely influence future work in this area. This paper is well-written, with a good review of previous works and background materials, and a clean presentation of results. The authors prove strong theoretical results in a variety of settings, and the proofs seem rigorous. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "EgAzwzDmggV", "reviewer": "Reviewer_v413", "summary": "This paper introduces a \"continuized\" randomized variant of the Nesterov acceleration scheme for convex optimization. In particular, \"updates\" are triggered at random i.i.d. exponential intervals of rate 1, leading to Markovian dynamics. The implications of this scheme are investigated in terms of streamlining, simplifying and improving the Nesterov acceleration.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found the paper interesting. It may be a variant of the Nesterov scheme, but it introduces new useful insights. In looking though the proofs, it appears that one key point is the randomized triggering of \"updates\" at random i.i.d. exponential intervals of rate 1, using Poisson measures that lead to Markovian dynamics. I am wondering whether the same effect could be obtained in a discretized fashion, that is, flipping i.i.d. coins to trigger the updates. A similar Markovian structure would emerge, but in discrete time now. I think it would be useful for the authors to address this point, because it arises naturally in the reader's mind. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BHoD1oCJovB", "reviewer": "Reviewer_ZD1t", "summary": "This paper introduces a new continuous-time framework for understanding Nesterov’s accelerated gradient descent. The authors consider the following dynamics for two variables (x, z): at the jump times of a Poisson process, each of the two variables x and z takes a step in the negative gradient of the objective function. In between these jumps, the variables x and z mix continuously according to an ODE. The authors show that with appropriate choices for the parameters, this process exhibits similar guarantees as Nesterov’s algorithm.\n\nContinuous-time versions of Nesterov’s algorithm have been considered before, but usually from the perspective of letting the step size of the algorithm tend to zero and thus recovering an ODE. Although it is usually much simpler to study the resulting ODE, it is quite non-trivial to start with an ODE and find a suitable discretization that preserves its convergence guarantees; thus, many of these prior works simply reverse-engineer Nesterov’s algorithm without providing an understanding of how to produce discretized accelerated algorithms. The main novelty in the present approach is that there is no need to discretize the continuous-time dynamics; the gradient steps already happen at discrete times (the jumps of a Poisson process) which can be simulated (with the caveat that the algorithm is now randomized). In between the jumps, the pair (x, z) evolves according to an ODE which does not depend on the objective function (besides the smoothness/convexity parameters). For the parameter choices leading to accelerated rates for convex-smooth and strongly convex-smooth classes, the authors show that in fact this ODE can be solved in closed form. Even if this were not the case, it is noteworthy that this ODE can be implemented in the usual oracle model of optimization.\n\nBesides introducing this framework, the authors provide extensions to stochastic gradients with “additive” or “multiplicative” noise, as well as applications to accelerated gossip.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Despite the immense amount of prior work attempting to decipher Nesterov’s algorithm, I believe this current work is novel and interesting. Indeed, passing from the continuous-time framework to an implementable algorithm is much more straightforward, making this a promising method for bridging continuous-time analysis with optimization algorithms.\n\nSpecific Comments:\n- In Thm. 6, one of the two expectation symbols seems redundant.\n- There is an extraneous factor of 2 in eq. (36).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
A fine paper that provides an original and refreshing perspective on one of the most enigmatic algorithmic cornerstones in convex optimization, namely, accelerated gradient descent.
Decision: Accept (Oral)