A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip

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; and 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.

heading: 1 Introduction
text: In the last decades, the emergence of numerous applications in statistics, machine learning and signal processing has led to a 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 et 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∗ ∈ Rd. We assume throughout the paper that f is L-smooth, i.e.,
∀x, y ∈ Rd, f(y) 6 f(x) + 〈∇f(x), y − x〉+ L 2 ‖y − x‖2 . (1)
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In addition, we sometimes assume that f is µ-strongly convex for some µ > 0, i.e.,
∀x, y ∈ Rd, f(y) > f(x) + 〈∇f(x), y − x〉+ µ 2 ‖y − x‖2 . (2)
For the problem of minimizing f , gradient descent is well-known to achieve a rate f(xk)− f(x∗) = O(k−1) in the smooth case, and a rate f(xk)− f(x∗) = O((1− µ/L)k) 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−2) in the smooth convex case and with rate O((1− √ µ/L)k) 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 a 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, 2]. A large number of these works studied continuous time equivalents of Nesterov acceleration, obtained by taking the limit when stepsizes vanish, or from a 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 xt, zt ∈ Rd, t ∈ R>0, that continuously mix following a linear ordinary differential equation (ODE), and that take gradient steps at random times T1, T2, T3, . . . . 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 t. In particular, this leads to simple analytical expressions for the optimal parameters as functions of t, while the optimal parameters of Nesterov accelerations are defined by recurrence relations that are complicated to solve.
The discretization x̃k = xTk , z̃k = zTk , k ∈ N, of the continuized process can be computed directly and exactly: the result is a 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 a convergence rate similar to that of [30] and depends on the statistical condition number of the problem at hand. The two acceleration schemes are not directly comparable as we work in a 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 asynchronous 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 can 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 t and not k.
Gossip algorithms typically feature such asynchronous and distributed behaviors [11]. In gossip problems, nodes of a network aim at computing the global average of all their values by communicating 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, so 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 a 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-Polynomial 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 asynchronous 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 ∈ R>0. 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 a direct implementation as a discrete iteration. We thus hope to contribute to the understanding of Nesterov acceleration. In practice, the continuized framework is relevant for handling asynchrony in decentralized optimization, where agents of a network can not share a 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.
Structure of the paper. In Section 2, we recall standard results on gradient descent and Nesterov acceleration. In Section 3, we introduce a continuized variant of Nesterov acceleration. In Section 4, 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-multiplicative noise. We finally present accelerated asynchronous algorithms for the gossip problem in Section 6, as well as for decentralized optimization in Section 7.

heading: 2 Reminders on Nesterov acceleration
text: 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 τk, τ ′k, γk, γ ′ k, k > 0, of the form
yk = xk + τk(zk − xk) , (3) xk+1 = yk − γk∇f(yk) , (4) zk+1 = zk + τ ′ k(yk − zk)− γ′k∇f(yk) . (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 a set of parameter choices for achieving acceleration. Theorem 1 (Convergence of accelerated gradient descent). Nesterov accelerated scheme satisfies:
1. Choose the parameters τk = 1− AkAk+1 , τ ′ k = 0, γk = 1 L , γ ′ k = Ak+1−Ak L , k > 0, where the
sequence Ak, k > 0, is defined by the recurrence relation
A0 = 0 , Ak+1 = Ak + 1
2 (1 +
√ 4Ak + 1) .
Then
f(xk)− f(x∗) 6 2L‖x0 − x∗‖2
k2 .
2. Assume further that f is µ-strongly convex, µ > 0. Choose the constant parameters
τk ≡ √ µ/L
1+ √ µ/L
, τ ′k ≡ √ µ L , γk ≡ 1 L , γ ′ k ≡ 1√µL , k > 0. Then
f(xk)− f(x∗) 6 ( f(x0)− f(x∗) + µ
2 ‖z0 − x∗‖2
)( 1− √ µ
L
)k .
This result can be found as is in d’Aspremont et al. [14, Sections 4.4.1 and 4.5.3]. In the convex case, Nesterov acceleration achieves the rate O(1/k2), whereas gradient descent achieves a rate O(1/k)
(see [43, Corollary 2.1.2] for instance). In the strongly convex case, Nesterov acceleration achieves the rate O((1− √ µ/L)k), where gradient descent achieves a rate O((1−µ/L)k) (see [43, Theorem 2.1.15] for instance). In both cases, this results in a significant speedup in practice, see Figure 1.
From a high-level perspective, Nesterov acceleration iterates over several variables, alternating between gradient steps (always with respect to the gradient at yk) 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 1 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.

heading: 3 Continuized version of Nesterov acceleration
text: 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 xt, zt indexed by a continuous time t > 0, that are continuously mixing and that take gradient steps at random times. More precisely, let T1, T2, T3, . . . > 0 be random times such that T1, T2 − T1, T3 − T2, . . . are independent identically distributed (i.i.d.), of law exponential with rate 1 (any constant rate would do, we choose 1 to make the comparison with discrete time k straightforward). By convention, we choose that our stochastic processes t 7→ xt, t 7→ zt are càdlàg almost surely, i.e., right continuous with well-defined left-limits xt−, zt− (Definition 6 in Appendix C). Our dynamics are parametrized by functions γt, γ′t, τt, τ ′ t , t > 0. At random times T1, T2, . . . , our sequences take gradient steps
xTk = xTk− − γTk∇f(xTk−) , (6) zTk = zTk− − γ′Tk∇f(xTk−) . (7)
Because of the memoryless property of the exponential distribution, in a infinitesimal time interval [t, t+ dt], the variables take gradients steps with probability dt, independently of the past. Between these random times, the variables mix through a linear, translation-invariant, ordinary differential equation (ODE)
dxt = ηt(zt − xt)dt , (8) dzt = η ′ t(xt − zt)dt . (9)
Following the notation of stochastic calculus, we can write the process more compactly in terms of the Poisson point measure dN(t) = ∑ k>1 δTk(dt), which has intensity the Lebesgue measure dt,
dxt = ηt(zt − xt)dt− γt∇f(xt)dN(t) , (10) dzt = η ′ t(xt − zt)dt− γ′t∇f(xt)dN(t) . (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 a Markov chain indexed by a discrete time index k, one 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 t, 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 an 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 t. As dN(t) is a Poisson point process with rate 1, t is the expected number of gradient steps done by the algorithm. Thus t is analoguous to k in Theorem 1. In the theorem below, E denotes the expectation with respect to the Poisson point process dN(t), the only source of randomness.
Theorem 2 (Convergence of continuized Nesterov acceleration). The continuized Nesterov acceleration satisfies the following two points.
1. Choose the parameters ηt = 2t , η ′ t = 0, γt = 1 L , γ ′ t = t 2L . Then
Ef(xt)− f(x∗) 6 2L‖z0 − x∗‖2
t2 .
2. Assume further that f is µ-strongly convex, µ > 0. Choose the constant parameters ηt = η ′ t ≡ √ µ L , γt ≡ 1 L , γ ′ t ≡ 1√µL . Then
Ef(xt)− f(x∗) 6 ( f(x0)− f(x∗) + µ
2 ‖z0 − x∗‖2
) exp ( − √ µ
L t
) .
We give an elementary sketch of proof in Appendix D.1 and a complete proof in Appendix D.2. Many authors have proposed continuous-time versions of Nesterov acceleration using differential calculus, see the numerous references in the introduction. For instance, in 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 as 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 a 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 is fundamentally different from previous continuous-time equivalents. Remark 1. A similar Markovian structure can be obtained in a discrete setting by flipping i.i.d. coins to trigger gradient steps. By denoting p > 0 the probability to trigger a gradient step when flipping a coin, (i) p = 1 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.

heading: 4 Discrete implementation of the continuized acceleration with random parameters
text: 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
x̃k := xTk , ỹk := xTk+1− , z̃k := zTk ,
with the convention that T0 = 0. The three sequences x̃k, ỹk, z̃k, k > 0, satisfy a recurrence relation of the same structure as Nesterov acceleration, but with random weights. The resulting randomized discrete algorithm satisfies performance guarantees similar to those of Nesterov acceleration. Theorem 3 (Discrete version of continuized acceleration). For any stochastic process of the form (10)-(11), we have
ỹk = x̃k + τk(z̃k − x̃k) , (12) x̃k+1 = ỹk − γ̃k∇f(ỹk) , (13) z̃k+1 = z̃k + τ ′ k(ỹk − z̃k)− γ̃′k∇f(ỹk) , (14)
for some random parameters τk, τ ′k, γ̃k, γ̃ ′ k (that are functions of Tk, Tk+1, ηt, η ′ t, γt, γ ′ t).
1. For the parameters of Theorem 2.(1), τk = 1− (
Tk Tk+1 )2 , τ ′k = 0, γ̃k = 1 L , and γ̃ ′ k = Tk 2L .
Then
E [ T 2k (f(x̃k)− f(x∗)) ] 6 2L‖z0 − x∗‖2 .
2. For the parameters of Theorem 2.(2), τk = 12 ( 1− exp ( −2 √ µ L (Tk+1 − Tk) )) ,
τ ′k = tanh (√ µ L (Tk+1 − Tk) ) , γ̃k = 1L , and γ̃ ′ k = 1√ µL . Then
E [ exp (√ µ
L Tk
) (f(x̃k)− f(x∗)) ] 6 f(x0)− f(x∗) + µ
2 ‖z0 − x∗‖2 .
The law of Tk is well known: it is the sum of k i.i.d. random variables of law exponential with rate 1; this is called an Erlang or Gamma distribution with shape parameter k and rate 1. One can use well-known properties of this law, such as its concentration around its expectation ETk = 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.1, we provide simulations confirming that this discrete random algorithm has a performance similar to Nesterov’s original acceleration.

heading: 5 Continuized Nesterov acceleration of stochastic gradient descent
text: We now investigate the design of continuized accelerations of stochastic gradient descent. We assume that we do not have direct access to the gradient ∇f(x) but to a random estimate ∇f(x, ξ), where ξ ∈ Ξ is random of law P . In the continuized framework, the randomness of the stochastic gradient and its time mix in a 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-trivial errors. We avoid this problem here.
We keep the algorithms of the same form, replacing gradients by stochastic gradients. Let ξ1, ξ2, . . . be i.i.d. random variables of law P . We take stochastic gradient steps at the random times T1, T2, . . . ,
xTk = xTk− − γTk∇f(xTk−, ξk) , zTk = zTk− − γ′Tk∇f(xTk−, ξk) .
Between these random times, the variables mix through the same ODE
dxt = ηt(zt − xt)dt , dzt = η ′ t(xt − zt)dt .
This can be written more compactly in terms of the Poisson point measure dN(t, ξ) =∑ k>1 δ(Tk,ξk)(dt,dξ) on R>0 × Ξ, which has intensity dt⊗ P ,
dxt = ηt(zt − xt)dt− γt ∫
Ξ
∇f(xt, ξ)dN(t, ξ) , (15)
dzt = η ′ t(xt − zt)dt− γ′t ∫ Ξ ∇f(xt, ξ)dN(t, ξ) . (16)
Here, the discussion depends on the properties satisfied by the stochastic gradients ∇f(x, ξ). In Appendix B, we study the so-called additive noise case. We show that the continuized acceleration satisfies perturbed convergence rates with the same choices of parameters as in Theorem 2. We thus show some robustness of the above acceleration to additive noise. Instead, in this section, we focus on the so-called pure multiplicative noise case, as it is crucial for the study of asynchronous gossip that follows. In this setting, parameters need to be chosen differently for our proof technique to 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: ∀x ∈ Rd, f(x) = E(a,b)∼P [ 1
2 (b− 〈x, a〉)2
] , (17)
where ξ = (a, b) ∈ Rd × R is random of law P . We assume that our stochastic first order oracle is the gradient of one realization of the expectation, namely,
∇f(x, ξ) = −(b− 〈x, a〉)a , ξ = (a, b) . We investigate noiseless—or purely multiplicative—stochastic gradients, in the sense that almost surely, for ξ = (a, b) ∼ P:
b = 〈x∗, a〉, so that ∇f(x∗, ξ) = 0 . (18)
Noiseless stochastic gradients are relevant in several situations, such as coordinate gradient descent with randomly sampled coordinates [51, 44, 55] (where ∇f(x, ξ) = m〈∇f(x), ei〉ei with i uniformly random in {1, . . . , d}), over-parameterized regime for least squares regression [52], function interpolation and gossip algorithms [8].
For a symmetric non-negative matrix A and a vector x, we denote ‖x‖2A = x>Ax. Let H = E[aa>] be the Hessian of f . Let R2 be the smallest positive real number such that:
E [ ‖a‖2aa> ] 4 R2H . (19)
Further, similarly to Jain et al. [30], we define the statistical condition number of the problem as the smallest κ̃ > 0 such that: E [ ‖a‖2H−1aa > ] 4 κ̃H . (20)
Theorem 4 (Continuized acceleration with pure multiplicative noise). Assume that (18), (19) and (20) hold true. Then the continuized acceleration satisfies the following.
1. Choose the parameters ηt = 2t , η ′ t = 0, γt = 1 R2 , γ ′ t = t 2R2κ̃ . Then
1 2 E‖xt − x∗‖2 6 R2κ̃‖z0 − x∗‖2H−1 t2 .
2. Assume further that f is µ-strongly convex, i.e., all eigenvalues of H are greater or equal to µ, where µ > 0. The condition number of f is then defined as κ = R2/µ. For the parameters ηt = η′t = 1√ κκ̃ , γt = 1R2 and γ ′ t = 1 R2 √ κ κ̃ , we have:
1 2 E‖xt − x∗‖2 6
( 1
2 ‖x0 − x∗‖2 +
µ 2 ‖z0 − x∗‖2H−1
) exp ( − t√
κκ̃
) .
In the strongly convex case, the benefits of this acceleration are similar to those of Jain et al. [30] with classical discrete iterates: while stochastic gradient descent with stepsize 1/R2 is easily shown to achieve an exponential rate of convergence 1/κ, the acceleration enjoys a rate of convergence of 1/ √ κκ̃. Note that from the definitions, κ̃ 6 κ, thus the acceleration performs as least as well as the naive algorithm. However, depending on 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 κ̃ and on the possibility to accelerate. Below, we provide a complementary perspective on the statistical condition number in the context of gossip algorithms, where it can be interpreted in terms of effective resistances of graphs.
Albeit more restrictive in terms of assumptions, our analysis is much simpler than that of Jain et al. [30], as it relies on a 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 accelerated coordinate descent, which is another noiseless stochastic method.

heading: 6 Accelerating Randomized Gossip
text: The continuized framework allows designing accelerated decentralized algorithms requiring synchronized 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 is discussed in the next section.
Let G = (V, E) a connected graph representing a communication network of agents. Each agent v ∈ V is assigned a real number x0(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̄ = 1m ∑ v∈V x0(v) using only local communications, i.e., communications between adjacent agents in the network.
We formalize the communication model of randomized gossip [11]. Time t is indexed continuously in R>0. We generate a Poisson point measure dN(t, e) = ∑ k>1 δ(Tk,{vk,wk}) with intensity measure dt⊗P , where dt is the Lebesgue measure on R>0 and P = (P{v,w}){v,w}∈E is a probability measure on the set E of edges. For k > 0, Tk is a time at which edge {vk, wk} is activated: adjacent nodes vk
and wk can communicate and perform a pairwise update. The Poisson point measure assumption implies that edges are activated independently of one another and from the past: the activation times of edge {v, w} form a Poisson point process of intensity P{v,w}. To solve the gossip problem, Boyd et al. [11] proposed the following naive strategy: each agent v ∈ V keeps a local estimate xt(v) of the average and, upon activation of edge {vk, wk} at time Tk ∈ R>0, the activated nodes vk, wk average their current estimates
xTk(vk), xTk(wk) ←− xTk−(vk) + xTk−(wk)
2 .
In this section, we accelerate this naive procedure. Our strategy is to apply Section 5 as follows. Consider the energy function
f(x) = ∑
{v,w}∈E
P{v,w} 2 (x(v)− x(w))2 , x = (x(v))v∈V . (21)
This function is convex, smooth, and writes in the form (17): f(x) = E{v,w}∼P [ 1
2
〈 x, a{v,w} 〉2] , (22)
where a{v,w} = ev − ew and (ev)v∈V forms the canonical basis of RV . As in Section 5, a stochastic gradient of f is obtained by taking the gradient of one realization of the expectation, namely:
∇f(x, {v, w}) = 〈x, a{v,w}〉a{v,w} =  x(v)− x(w) at coordinate v, x(w)− x(v) at coordinate w, 0 at all other coordinates.
(23)
As a consequence, a stochastic gradient step with stepsize 1/2 corresponds to a local averaging alongside edge {v, w}, where {v, w} ∼ P . More generally, the randomized gossip algorithm as described by Boyd et al. [11] is the stochastic gradient descent:
dxt = − 1
2 ∫ R>0×E ∇f(xt, {v, w})dN(t, {v, w}) . (24)
Using Section 5, we can accelerate this algorithm if we know the strong convexity parameter of f and the constants R2 and κ̃ as defined in (19) and (20) respectively. These constants can be intepreted as graph-related quantities here.
Definition 1 (Graph-related quantities). The Laplacian matrix L ∈ RV×V of graph G with weights (P{v,w}){v,w}∈E on the edges is the matrix with entries Lv,w = −P{v,w} if {v, w} ∈ E , Lv,v = ∑ w∼v P{v,w}, and Lv,w = 0 if {v, w} /∈ E . We denote µgossip the second smallest eigenvalue of L, corresponding to its smallest positive eigenvalue. For {v, w} ∈ E , let Reff(v, w) = (e(v) − e(w))>L−1(e(v) − e(w)) be the effective resistance of edge {v, w}, and Rmax = max{v,w}∈E Reff(v, w) be the maximal resistance in the graph.
The function f is quadratic with Hessian L, and strongly convex with parameter µgossip on the hyperplane F = {x ∈ RV : ∑ v∈V x(v) = x̄}; hence we use the (perhaps abusive) notation µgossip throughout. Moreover, the conditions (19) and (20) are satisfied with R2 = 2, κ̃ = Rmax.
These parameters being given, the accelerated stochastic gradient descent updates (15)-(16) can be instantiated as follows. Each agent v ∈ V keeps two local estimates xt(v), zt(v) of x̄, initialized at x0(v). Upon activation of edge {vk, wk} at time Tk,
xTk(vk) = xTk(wk) = xTk−(vk) + xTk−(wk)
2 ,
zTk(vk) = zTk−(vk) + 1√
2µgossipRmax (xTk−(wk)− xTk−(vk)) ,
zTk(wk) = zTk−(wk) + 1√
2µgossipRmax (xTk−(vk)− xTk−(wk)) .
Between these updates, xt(v) and zt(v) locally mix at all nodes v ∈ V , according to the coupled ODE:
dxt(v) = √ 2µgossip Rmax (zt(v)− xt(v))dt,
dzt(v) = √ 2µgossip Rmax (xt(v)− zt(v))dt.
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 t ∈ R>0 is available at all nodes independently from the number of past updates, while a local pairwise update between adjacent nodes v and w only requires a local synchronization. Theorem 5 (Accelerated randomized gossip). Let (xt(v))v∈V,t>0 be generated with accelerated randomized gossip. For any t ∈ R>0:∑
v∈V
1 2 E [( xt(v)− x̄ )2] 6 2 (∑ v∈V 1 2 ( x0(v)− x̄ )2) exp ( − √ µgossip 2Rmax t ) .
Let θARG = √
µgossip 2Rmax be the rate of convergence of accelerated randomized gossip, and θRG =
µgossip be the rate of convergence of randomized gossip [11]. We have θARG > θRG/ √
2. Let us exhibit scenarios over which accelerated randomized gossip gains several orders of magnitude. Denoting Pmin = min{v,w}∈E P{v,w}, Ellens et al. [22] ensures that for {v, w} ∈ E , PminReff(v, w) 6 1, so that Rmax 6 P−1min. Corollary 1 (Comparison with randomized gossip). Accelerated randomized gossip achieves a rate satisfying: √
θRGPmin 2 6 θARG.
Assume furthermore that there exist some constants c > 0 such that for all {v, w} ∈ E , P{v,w} 6 cPmin and dv + dw 6 2d. Then, with C = 1/ √ 2cd:
C √ θRG |V| 6 θARG.
Assume now for simplicity that the Poisson intensities P{v,w} are all equal to 1/|E|. Denoting |V| = m, on the cyclic and the line graph, this gives us θARG = Ω(1/m2) while θRG 1/m3. On a d-dimensional grid, we have θARG = Ω(1/m1+1/d) and θRG 1/m1+2/d. However, on graphs with unbounded degrees, no improvements are observed, as illustrated in Figure 2, Appendix A.2. In the case of the complete graph, this is expected since at least θ−1RG m communications are needed to compute the average. We thus recover the same rates as Dimakis et al. [20] for the graphs they study, but generalized to any network.

heading: 7 Accelerating Asynchronous Decentralized Optimization
text: Our continuized framework for accelerating randomized gossip can be extended to the more general problem of decentralized optimization: each node v in the network G previously defined holds a function fv : Rd → R, µ-strongly convex and L-smooth. Nodes of the network collaborate to solve:
min x∈Rd
{ f(x) = 1
|V| ∑ v∈V fv(x)
} . (25)
As in gossip averaging, only local communications are allowed. Quantities related to fv can only be computed at node v. In the case of empirical risk minimization, fv represents the empirical risk related to node v’s local data. Setting fv(x) = 12‖x− x0(v)‖
2 leads to the averaging problem previously described. Similarly to Section 6, time is indexed continuously by t in R>0, and communications are
ruled by the same Poisson point measure dN(t, e) = ∑ k>1 δ(Tk,{vk,wk}) on R>0 × 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 it using a 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-independent ODE. At time Tk, adjacent nodes vk and wk use their local function in order to compute gradient conjugates ∇f∗v (x(v)),∇f∗w(x(w)). Since the local functions are not simple quadratics anymore, the stochastic gradients ∇f(x, {v, w}) from Equation (26) are replaced by terms proportional to:
G(y, {v, w}) =  ∇f∗v (y(v))−∇f∗w(y(w)) at coordinate v, −∇f∗v (y(v))−∇f∗w(y(w)) at coordinate w, 0 at all other coordinates.
(26)
Due to lack of space, we describe the iterations more in details in Appendix H, together with a relevant choice of parameters. The crucial point is that, similarly to the gossip averaging case, we do not require nodes to 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 (xt(v))v∈V = (∇f∗v (zt(v)))v∈V generated by the accelerated coordinate descent on the dual of Problem (25):∑
v∈V
1 2 E [ ‖xt(v)− x∗‖2 ] 6 C (∑ v∈V 1 2 ‖x0(v)− x∗‖2 ) exp ( −θ ′ ARG√ κ t ) ,
where κ = µ/L is an upper bound on the condition number of f , C is a constant that depends on the graph and κ, and θ′ARG is the rate of convergence of accelerated randomized gossip on the graph G as defined in Theorem 5 but with graph resistances are defined in a different way (see Theorem 10).

heading: 8 Conclusion
text: In this work, we introduced a continuized version of Nesterov’s accelerated gradients. In a nutshell, the method has two sequences of iterates which take gradient steps at 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 of this approach is that the method can be implemented without any approximation, as the differential equation governing the mixing procedure has a simple analytical solution. A discretization of the continuized method corresponds to 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 are 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 deterministic 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 as part of the “Investissements d’avenir” program, reference ANR-19P3IA-0001(PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063), from the DGA, and from the MSR-INRIA joint centre.

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

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.

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.

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.  Continuous-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.  Besides introducing this framework, the authors provide extensions to stochastic gradients with “additive” or “multiplicative” noise, as well as applications to accelerated gossip.