{'fraction_non_alphanumeric': 0.04676104676104676, 'fraction_numerical': 0.011650748492853757, 'mean_word_length': 4.233987237059797, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees

The article discusses distributed gradient-descent algorithms for computing local and global minima in nonconvex optimization. For local optimization, we focus on distributed stochastic gradient descent (D-SGD)---a simple network-based variant of classical SGD. We discuss local minima convergence guarantees and explore the simple but critical role of the stable-manifold theorem in analyzing saddle-point avoidance. For global optimization, we discuss annealing-based methods in which slowly decaying noise is added to distributed gradient descent. Conditions are discussed under which convergence to global minima is guaranteed. Numerical examples illustrate the key concepts in the paper.


I. INTRODUCTION
Nonconvex optimization problems are prevalent in applications throughout control, signal processing, and machine learning. Modern applications involve unprecedented quantities of data generated by a multitude of interconnected devices including mobile phones, IoT devices, self-driving vehicles, and networked cyber-physical systems. Due to limitations of the communication infrastructure it can be infeasible to collect the enormous amount of data generated by these devices to a centralized location for processing.
This motivates the study of distributed (network-based) algorithms for nonconvex optimization. In a distributed optimization algorithm, a group of nodes (or agents) may communicate over an overlaid communication graph. Agents collaboratively optimize some collective function without any centralized coordination or data aggregation. 1 Distributed algorithms are flexible, robust, and efficient [1]- [4]. They play a critical role in, IoT, edge computing, and sensor network applications, as well as large-scale parallel computing [4].
While there are a wide variety of optimization techniques available, in this article we will focus on distributed implementations of simple first-order algorithms; namely, distributed gradient descent and variants thereof. Despite their simplicity, first-order methods are widely used in practice due to their ease of implementation, analytic tractability, and efficiency in practical large-scale problems.
We will consider the following setup: A group of N agents may communicate via an overlaid communication network. Each agent possesses some local objective function f n : R d → R. It is desired to optimize the sum-function Ideally, one would like to compute a global minimum of (1). However, when F is nonconvex, computation of global minima can be challenging, and, in some important applications of interest, local minima are known to perform nearly as well as global minima [7]- [9]. Thus, it is prudent to begin by focusing on the problem of computing local minima of (1).
Intuitively, gradient-based algorithms descend the objective function until they reach a point where the gradient is zero. That is to say, the set of limit points of gradient-based algorithms consists of the set of critical points. This set includes, of course, local minima, local maxima, and saddle points. Clearly, local maxima are not desirable limit points for an optimization algorithm, and it is easy to show that gradient-descent based methods do not actually converge to these points. However, gradient-based methods can converge to saddle points, which can be quite problematic. Saddle points can be highly suboptimal and, in problems of interest, the number of saddle points can proliferate exponentially relative to the number of local minima as the problem size scales [10].
The focus of this article will be on refined convergence guarantees for distributed gradient methods. Broadly, beyond simply understanding convergence to critical points, the article will focus on the following two fundamental questions: 1. Under what conditions can distributed gradient descent be guaranteed to converge to local minima (or not converge to saddle points)? 2. Can simple variants of distributed gradient descent converge to global minima? In classical (centralized) GD, the key to understanding saddle-point behavior lies in the so-called stable-manifold theorem [11], [12]. Simply put, the main idea of the stable-manifold theorem is the following: Given any saddle point, there exists an associated stable manifold-a special low-dimensional surface from which GD converges to the saddle point. In particular, GD converges to the saddle point if and only if initialized on this surface. The (classical) stable-manifold theorem ensures the existence of the stable manifold and provides the essential structural information that enables analysis of saddle-point nonconvergence in centralized settings [13]- [15].
In order to address the first question above, we will discuss stable-manifolds for distributed gradient descent (DGD). While the stable manifold for DGD differs in some structural respects from the centralized GD stable manifold, it serves the same essential role in facilitating analysis of saddle-point behavior. We note that, when discussing stable-manifold results, we will focus on continuous-time descent processes. Continuous-time processes (particularly in the context of saddle-point avoidance) are significantly easier to study than their discrete-time counterparts. Moreover, continuous-time stable manifold are not merely an intellectual curiosity-they will be the key analytical tool used to study discrete-time saddle-point avoidance. Despite our tangential discussion of continuous-time processes, we emphasize that the major focus of the article is on discrete-time algorithms.
After considering the stable-manifold theorem for (continuous-time) DGD, we will consider distributed stochastic gradient descent (D-SGD)-a simple distributed variant of classical SGD. Under mild assumptions, D-SGD avoids saddle points and converges to local minima with probability 1. We will discuss conditions under which saddle points are avoided and we will discuss the key role played by the stable-manifold theorem in analyzing the saddle-point behavior of distributed gradient algorithms.
Next, we turn to the problem of computing global minima of (1). Of course, the gradient of a function describes only a local property of the function and (stochastic) gradient descent is only capable of reliably locating local minima. In order to find global minima we must resort to other techniques. Simulated annealing (SA) is a popular method for locating global minima inspired by the annealing process in metallurgy wherein a metal is heated and then slowly cooled in order to freeze it into a low energy lattice configuration. Analogously, the premise of SA algorithms is that slowly-decaying noise may be added to a local search algorithm in order to escape local minima and seek out global minima. The slow reduction in added noise strength in SA corresponds to a slow "cooling" of the algorithm. Simulated annealing algorithms were originally introduced for discrete combinatorial optimization [16], with later variants being developed for continuous optimization in R d [17]- [20].
In order to address the second question above, we will discuss gradient-descent based annealing algorithms for global optimization in R d . In particular, we will focus on a very simple generalization of D-SGD mentioned earlier in which slowly decaying (annealing) noise is added to the algorithm at each iteration. The algorithm, referred to as D-SGD + annealing, converges in probability to the set of global minima of F . We remark that the annealing algorithms we consider in this article are in the spirit of [17] and are closely related to stochastic gradient Langevin dynamics [20]- [23] currently popular in machine learning applications.
Organization. The remainder of the article is organized as follows. In order to build intuition, we will begin in Section II by considering classical centralized gradient algorithms. We will review classical results on convergence to critical points including the stable-manifold theorem and nonconvergence to saddle points. We note that in this section we have put some emphasis on GD in continuous-time. While the focus of the article is on discrete-time algorithms, the continuous-time perspective adds key insight and the corresponding analysis tools are indespensible in characterizing discrete-time algorithms using stochastic approximation techniques [24]- [26]. We have taken efforts to ensure that the presentation is easily accessible to all with basic familiarity with differential equations. Next, in Section III we will discuss DGD in continuous time. Continuous-time DGD is simple to analyze and provides a clear picture of the behavior of distributed gradient algorithms near saddle points. Analogous to the centralized case, continuous-time DGD plays a key role in analyzing discrete-time saddle-point avoidance in distributed systems. The remainder of the article focuses explicitly on discrete-time algorithms. In Section IV we will consider D-SGD; we will discuss guarantees for avoiding saddle points and converging to local minima. In Section V we turn to the problem of locating global minima of (1). We will focus on the use of annealing methods. We review classical (centralized) results in Section V-A and discuss distributed algorithms in Section V-B. In Section VI we consider numerical examples illustrating the key concepts in the paper. Section VII concludes the article.
Notation. Throughout the paper, · denotes the standard Euclidean norm, dist(x, y) = x − y is the distance between points x and y, and dist(x, S) = inf y∈S dist(x, y) gives the distance between a point x and set S. Given a random process {y k } taking the general recursive form y k+1 = G(y k , ξ k ), where ξ k is a random variable, k is the iteration, and G(·, ·) : R d × R d → R d is the iteration map, we let F k = σ(ξ 1 , . . . , ξ k−1 ) denote the σ-algebra representing the information available at time k and let E(·|F k ) represent the associated conditional expectation. 2

II. CENTRALIZED GRADIENT ALGORITHMS: FOUNDATIONS AND INTUITION
Before studying properties of distributed algorithms in nonconvex optimization, it will be helpful to first review basic properties of centralized algorithms. In this section we will review classical results and develop two simple examples illustrating several key properties. In later sections, when we turn to distributed algorithms, we will discuss how these properties do (and do not) extend to the distributed setting.
We begin by considering classical continuous-time gradient descent.

A. Continuous-Time Gradient Descent
Given a differentiable function f : R d → R, stochastic gradient descent is given by the recursion where ξ k is a random variable satisfying E(ξ k |F k ) = 0, α k represents the step size, and F k represents the information available at iteration k. Taking an expectation on both sides and rearranging terms we have If the step size α k is taken to zero at an appropriate rate (see Assumption 3 below), then (3) represents an Euler discretization of the differential equation, given bẏ where we use bold x to denote a differentiable mapping x : [0, ∞) → R d . The relationship between (2) and (4) is made rigorous using tools from the field of stochastic approximation theory [27], which deals with analysis techniques for studying stochastic discrete-time systems (e.g., (2)) by considering the corresponding (deterministic) continuous time ODE (e.g., (4)).
In this section we will review the basic properties of (4) in nonconvex optimization. The following assumption gives a basic condition under which CT-GD is well defined [11]. We use the notation f ∈ C k for integer k ≥ 0 to indicate that f is k-times continuously differentiable.
Assumption 1. f is C 1 and has Lipschitz continuous gradient, i.e., there exists a constant K > 0 such that ∇f (x) − ∇f (y) ≤ K x − y for all x, y ∈ R d .
Note that the only points at which CT-GD may rest are points where the right hand size of (4) is zero. These are precisely the set of critical points of f . The following standard result shows that CT-GD converges to this set.
Theorem 1 (Convergence to Critical Points). Suppose that f satisfies Assumption 1 and x satisfies (4). Then x converges to the set of critical points of f .
Of course, the set of critical points of f consists of local maxima, local minima, and saddle points. Thus, some limit points permitted under Theorem 1 can be extremely suboptimal. We are interested in refinements of Theorem 1 that show that the CT-GD typically converges to local minima. It is not difficult to show that CT-GD does not converge to local maxima. However, saddle points require a subtler treatment. In order to build intuition, consider the following simple example.
. Note that f has a saddle point, which we will denote by x * , at the origin. A plot of this function is shown in Figure 1a, and a plot of the gradient-descent vector field is shown in Figure 1b.
We would like to characterize the set of initial conditions from which solutions to (4) converge to the saddle point x * . Formally, this set is given by {x 0 ∈ R 2 : x(0) = x 0 and x satisfies (4) =⇒ x(t) → x * }, and (for reasons soon to become clear) we will refer to it as the stable manifold associated with x * .
Since f is quadratic, the CT-GD system associated with f is given by the linear systemẋ(t) = −Ax(t) where A = diag(1, −1) is the diagonal matrix with 1 and −1 on the diagonal. Using basic tools from linear systems theory, we see that the solution to this system given an initial condition x(0) = x 0 is given by Note that if we initialize a CT-GD trajectory on the x 1 axis, i.e., with The next example is an extension of Example 1 that illustrates how the stable manifold depends on the dimension of the problem and the structure of the saddle point. Before presenting the example, we recall the following standard notation. For an integer p ≥ 1, 1 p is the p-dimensional vector of all ones. Given vectors a ∈ R d1 and b ∈ R d2 , diag(a, b) gives the (d 1 + d 2 ) × (d 1 + d 2 ) diagonal matrix with the elements of a and b on the diagonal.
(4) is given by the linear systemẋ = −Ax. Since A is diagonal, the solution to this system with initial condition x 0 ∈ R d is simply given by Given this form of the solution, it is clear that the stable manifold for x * is the set S = {x ∈ R d : Note that S is the subspace spanned by all eigenvectors of A with positive (or, more generally, nonnegative) eigenvalue. We are interested in understanding when the stable manifold will be a "small" set in some sense. One way to gauge the size of S is by it's dimension. Recalling that q is the number of negative eigenvalues and that S is the span of all eigenvectors with nonnegative eigenvalues, we have dim S = d − q.
The intuition garnered from these elementary examples will generalize to a wide range of saddle points. We highlight the following key observations from these examples: (i) While it is possible to converge to the saddle point x * , this can only be accomplished by initializing on a special low-dimensional surface (referred to as the stable manifold of x * ). (ii) The stable manifold is an invariant set. That is, if a trajectory x(t) lies in the stable manifold at some time t 0 ≥ 0, then x(t) remains in the stable manifold for all t ≥ t 0 . (iii) The stable manifold is a "repulsive" set. If a trajectory x(t) is not initialized precisely on the stable manifold (e.g., if x 2 (0) = ε > 0 in Example 1), then it is pushed away from the stable manifold. (iv) In the above examples, the CT-GD system was a linear system and the stable manifold was a linear subspace of R d . This occurred because we chose f to be quadratic. In general, when f is not quadratic, the stable manifold will be a smooth nonlinear surface. (v) The stable manifold has dimension d − q, where q is the number of negative eigenvalues in ∇ 2 f (x * ). This relationship was observed when S was a linear surface, but will hold generally when S is an arbitrary smooth surface.
These observations generalize, and typify the behavior of CT-GD near a broad class of saddle points known as regular saddle points, defined next. 3 Definition 1 (Regular Saddle Point). We say that a saddle point exists and is nonsingular.
Regular saddle points serve two purposes: (1) They ensure that ∇ 2 f (x * ) has at least one negative eigenvalue, which implies that f has at least one genuine descent direction at x * . (2) They greatly simplify the analysis. 4 The following theorem generalizes the intuition from the above examples and shows that a stable manifold exists near regular saddle points. A proof of the theorem can be found in [11].
Theorem 2 (Stable-Manifold Theorem for Continuous GD). Suppose that f is C 2 and satisfies Assumption 1 and that x * is a regular saddle point of f . Let q denote the number of negative eigenvalues of ∇ 2 f (x * ). Then there exists a smooth (d−q)-dimensional surface S such that a solution x to (4) can only converge to x * if it is initialized on S.
It is important to note that, in the above theorem, since x * is a regular saddle, we have q ≥ 1 and so S has dimension at most d − 1. Thus, S is a Lebesgue measure zero set in R d . An alternate, but intuitively satisfying way to restate the above result is that, if CT-GD is randomly initialized according to a "nice" distribution, 5 then CT-GD avoids regular saddle points with probability 1.
To illustrate the structure of the stable manifold near a function that is not quadratic but possesses a regular saddle point, suppose , and note that f has a regular saddle point at the origin. The CT-GD vector field for this function is displayed in Figure 1c. The stable manifold is illustrated in black.

B. Stochastic Gradient Descent
Stochastic gradient descent is given by the recursive process (2). The following is a standard assumption for the noise in SGD.
This setup is quite broad and includes, among other things, mini-batch variants of SGD common in machine learning and neural network training as well as SGD for online learning. Due to space constraints, we do not elaborate on these methods, but refer the reader to [28].
Because of the noise in SGD, the algorithm can only be guaranteed to converge if a decaying step size is used. We will assume that the step size takes the following form.
In the above assumption, we use the asymptotic notation α k = Θ(k τα ) to mean that for some constants c 1 , c 2 > 0, Step sizes in this range ensure that α k decays quickly enough to average out noise, but slowly enough so that x k can adequately explore the state space.
The following theorem establishes the convergence of SGD to critical points. The result follows using ODE stochastic approximation techniques [27]. Of course, convergence to critical points is rudimentary convergence criterion. We are interested refinements of this result, and, in particular, understanding the (non)convergence of SGD to saddle points.
In order to ensure nonconvergence to saddle points, we must make an additional assumption about the noise process. Informally, the following assumption states that the random variable ξ k in (2) "perturbs" in all directions.
The assumption ensures that the noise in SGD will knock the process off of any "bad" low-dimensional sets that could lead to a saddle point (i.e., a stable manifold). In the following assumption, the notation (a) + means (a) + = a if a ≥ 0 and (a) + = 0 otherwise. Assumption 4 (Minimum Excitation). The noise process satisfies E((ξ T k θ) + |F k ) ≥ C for some C > 0 and every unit vector θ.
The following theorem establishes that SGD does not converge to regular saddle points.
Theorem 4. Suppose that f is C 2 , that x * is a regular saddle point of f , and that Assumptions 1-4 are satisfied. Then P(x k → x * ) = 0.
A proof of Theorem 4 can be found in [25]. The proof of this result is fairly involved; however, the basic intuition underlying the proof is simple to grasp and elucidates the role of saddle-point structure and the stablemanifold theorem. We will briefly discuss this intuition now. We remark that the intuition underlying saddle-point nonconvergence of the distributed variant of SGD, to be discussed in Section IV, will be similar.
The main idea is that Theorem 4 follows as a consequence of the stable-manifold theorem for CT-GD (Theorem 2). This follows from two key observations. First, note that the mean update step for SGD satisfies (3). Thus, the mean update step of SGD is a discretization of (4) with decaying step size. Consequently, (4) is the asymptotic mean field for (2), and the asymptotic behavior of (2) is determined by properties of (4). The second key observation is that the stable manifold for CT-GD is a Lyapunov unstable set. That is, if a trajectory is not initialized precisely on the stable manifold, then it is pushed away from the stable manifold. This property was illustrated in the Example 1 and holds generally for the stable manifold near any regular saddle.
Intuitively then, the CT-GD stable manifold is precisely the object from which solutions to (2) are repelled near x * . Letting S denote the stable manifold established in Theorem 2, Theorem 4 follows by showing that (i) noise satisfying Assumption 4 pushes x k off of and away from S, then (ii) the instability of S eventually forces x k away from S forever. See [25] for more details.

III. CONTINUOUS-TIME DISTRIBUTED GRADIENT DESCENT
We now consider distributed gradient descent for locating local minima. Analogous to the centralized setting, it is advantageous to begin by considering continuous-time DGD. This builds intuition in a simple setting and sets up the use of continuous-time methods as an analysis technique for characterizing discrete-time nonconvergence to saddle points.

A. Continuous-Time DGD Algorithm
In DGD each agent maintains a local estimate of the solution to (1). We let x n (t) denote agent n's estimate of the solution to (1) at time t. CT-DGD is given by the differential equatioṅ The right hand side of (5) consists of two terms: A consensus term β t ∈Ωn (x (t) − x n (t)), and a local gradientdescent term −α t ∇f n (x n (t)). As suggested by the name, the consensus term encourages agents state estimates to tend towards a common value as t → ∞. (For example, if we suppose that f n ≡ 0 for all n then (5) reduces to classical consensus dynamics [29].) The gradient term encourages each agent to descent the gradient of their local objective f n . In order to ensure that solutions to (5) are well-defined, we will assume that each f n satisfies Assumption 1 with f = f n .

B. Consensus and Convergence to Critical Points
In order to guarantee the convergence of (5) we must make a few additional assumptions pertaining to the distributed setup. First, we assume that the communication graph is connected so that information may disseminate freely between nodes. 6 Assumption 5. The graph G = (V, E) is undirected and connected.
The next assumption pertains to each agent's local objective function f n , and is used to ensure that agents reach asymptotic consensus.
Assumption 6. Each f n is coercive. That is, f n (x) → ∞ as x → ∞.
Finally, we will assume that the weight sequences take the following form.
Note that in Assumption 7 the consensus weight β t decays more slowly than α t . Under the above assumptions, agents achieve consensus and agents' states x n (t) converge to a critical point of F , as stated in the following theorem. A proof of this theorem can be found in [26].
is a solution to (5) with arbitrary initial condition. Suppose that and Assumptions 5-7 hold and, for each n, Assumption 1 holds with f = f n . Then for each agent n we have: (i) lim t→∞ x n (t) − x (t) = 0, for all = 1, . . . , N , and (ii) x n (t) converges to the set of critical points of F , as given by (1).

C. Nonconvergence to Saddle Points
We will now consider a refinement of Theorem 5 showing that, while it is possible to converge to saddle points, CT-DGD typically avoids them. As in the case of CT-GD, this can be accomplished by studying stable manifolds.
The stable manifold for CT-DGD differs from the centralized case in a few important respects. First, in order to establish the existence of the stable manifold it is necessary to make the following assumption, which is quite mild, but somewhat technical.
Assumption 8 (Continuity of Eigenvectors). Let x = (x n ) N n=1 ∈ R N d and letf (x) := (f n (x n )) N n=1 . Suppose that x * ∈ R d is a saddle point of F . Letx := (x * , . . . , x * ) ∈ R N d be the N -fold repetition of x * . Assume that the eigenvectors of ∇ 2f (x) are continuous atx in the sense that, for each x nearx, there exists an orthonormal matrix U (x) that diagonalizes ∇ 2f (x) such that x → U (x) is continuous atx.
This assumption is relatively innocuous and should be satisfied by most functions encountered in practice; however, it is required to rule out certain pathological cases which can arise in the distributed setting (but not in the centralized) [26], [31].
In the case of CT-DGD, the structure of the stable manifold differs from the structure of the CT-GD stable manifold studied in Section II-A in a small but important way. To see this, note that the right-hand side of (5) depends not only on the state of the process x(t), but also on time via the time-varying weights α t and β t . As a result, the asymptotic behavior of a CT-DGD trajectory with initialization x n (t 0 ) = x n,0 , x 0 = {x n,0 } N n=1 depends not only on the initial state x 0 , but also on the initial time t 0 . Consequently, the stable manifold for CT-DGD will be dependent on initial time.
The following theorem establishes the existence of a stable manifold near regular saddle points and characterizes the structure of the stable manifold. A proof of this result can be found in [26] Theorem 6. Suppose that the hypotheses of Theorem 5 hold, Assumption 8 holds, and x * is a regular saddle point of F , as given by (1). Let q denote the number of negative eigenvalues of the Hessian ∇ 2 F (x * ). Then for all t 0 sufficiently large there exist a smooth surface S t0 ⊂ R N d with dimension (N d − q) such that the following holds: A solution (x n (t)) N n=1 to (5) may converge to x * in the sense that x n (t) → x * for some n, only if (x n (t)) N n=1 is initialized on S t0 , i.e., (x n (t 0 )) N n=1 = x 0 ∈ R N d with x 0 ∈ S t0 . The following corollary illustrates a simple condition under which CT-DGD converges to local minima. The corollary is an immediate consequence of Theorem 6. In the statement of the theorem, we remark that "almost every" is in the sense of the Lebesgue measure in R N d . (5), that F satisfies the hypotheses of Theorem 6 and that every saddle point of F is regular. Then, given any initial time t 0 , x(t) converges to the set of local minima from almost every initialization x 0 ∈ R N d .

IV. DISTRIBUTED STOCHASTIC GRADIENT DESCENT
We will now consider D-SGD-a simple distributed variant of the classical SGD algorithm (2). Due to space limitations, we cannot give a thorough treatment of all work on the topic of saddle-point evasion in distributed gradient algorithms. However, we will briefly review closely related work on this nascent topic. Reference [32] considers a variant of discrete-time DGD with constant step size and shows convergence to second order stationary points for sufficiently small step sizes for almost all initial conditions. A critical point x * of f is called second order stationary if ∇ 2 f (x * ) is positive semidefinite. Thus, for example, if all saddle points are regular per Definition 1, then this implies convergence to local minima. Reference [32] also considers distributed gradient tracking algorithms and saddle-point nonconvergence. References [33], [34] consider a variant of D-SGD with constant step size and show fast (polynomial-time) escape from saddle points. Reference [35] considers primal-dual based methods for distributed optimization and shows convergence to second order stationary points from almost all initializations.

A. D-SGD Algorithm
For integers k ≥ 1, let x n (k) ∈ R d denote the estimate that agent n maintains of an optimizer of (1) at iteration k. The D-SGD algorithm is given by the recursion x n (k + 1) = x n (k) + β k ∈Ωn (x (k) − x n (k)) − α k (∇f n (x n (k)) + ξ n (k)), for each agent n = 1, . . . , N , where ξ n (k) denotes a random variable. The random variable ξ n (k) typically represents gradient measurement noise but may also represent noise that is deliberately introduced to aid in escaping saddle points, e.g., [14]. Similar to (5), the right hand side of (6) consists of a consensus term β k ∈Ωn (x (k) − x n (k)) and a (stochastic) gradient-descent term −α k (∇f n (x n (k)) + ξ n (k)).

B. Consensus and Convergence to Critical Points
In studying the convergence of D-SGD, we will retain Assumptions 5-6 used for CT-DGD, and add two additional assumptions pertaining to the discrete-time weights and the noise process.
Assumption 9. α k = Θ (k −τα ) and β k = Θ (k −τβ ) with 0 ≤ τ β < τ α , τ α ∈ (1/2, 1]. This assumption differs from Assumption 7 in that it assumes a tighter range for τ α , necessary to ensure the noise in SGD is asymptotically damped. The assumption is similar to Assumption 3 from SGD, but here we also account for the consensus weight β k . We will also assume that for each n, the noise sequence {ξ n (k)} satisfies Assumption 2 with ξ k = ξ n (k).
Under the above assumptions, we obtain the following basic convergence result for D-SGD. The theorem is proved by using the stable manifold for (5) and using ODE-based stochastic approximation techniques [26], [27].
Theorem 7. Let {x n (k)} N n=1 be a D-SGD process (6). Suppose Assumptions 5-6 and 8-9 hold and assume that for each n, {ξ n (k)} is independent from {ξ (k)}, = n and satisfies Assumption 2 with ξ k = ξ n (k), and Assumption 1 holds with f = f n . Then with probability 1, for each agent n the following holds: (i) Asymptotic consensus is achieved in the sense that lim k→∞ x n (k) − x (k) = 0 for all = 1, . . . , N , and (ii) {x n (k)} N n=1 converges to the set of critical points of F .

C. Nonconvergence to Saddle Points
In the case of (centralized) SGD, we saw that under a minimum excitation condition (Assumption 4), the gradient noise knocked the process away from the underlying stable manifold, allowing the algorithm to escape from saddle points with probability one. The following result shows that D-SGD does not converge to saddle points under a similar minimum excitation assumption.
} is a D-SGD process (6) and that the hypotheses of Theorem 7 hold. Moreover, suppose that F ∈ C 3 , x * is a regular saddle point of F , and for each n, {ξ n (k)} satisfies Assumption 4 with ξ k = ξ n (k). Then, regardless of initialization, for each n, P(x n (k) → x * ) = 0.
Similar to the proof of Theorem 4 in the case of centralized SGD, the proof of Theorem 8 follows from the CT-DGD stable-manifold theorem established in Theorem 6 using stochastic approximation techniques. The basic idea is fundamentally the same as the proof of Theorem 4 discussed in Section II-B. Noise satisfying Assumption 4 at each agent perturbs the D-SGD process off of and away from the stable manifold. The stable manifold is inherently unstable (because x * is a regular saddle point). This inherent instability eventually pushes the D-SGD process away from the saddle point forever. See [26] for a complete proof of this result. The next result is an immediate corollary of Theorems 7 and 8.
Corollary 2. Suppose that {(x n (k)) N k=1 } is a D-SGD process and that the hypotheses of Theorem 8 are satisfied. Furthermore, suppose that every saddle point of F is regular. Then agents achieve asymptotic consensus, and {x n (k)} converges to the set of local minima of F for each agent n.

V. DISTRIBUTED ANNEALING METHODS
We will now consider first-order annealing algorithms for global optimization in R d . The distributed annealing algorithm we consider here is a simple and direct generalization of D-SGD (6). At each iteration, each agent simply adds annealing noise to (6). If the annealing noise cools at an appropriate rate, the algorithm converges to a global minimum of (1).
We remark that the annealing algorithm discussed here is closely related to stochastic gradient Langevin dynamics (SGLD), popular for nonconvex machine learning tasks [21]- [23]. The SGLD algorithm is a discretization of the Langevin diffusion [20]. Recent work has studied the constant-weight variant of SGLD and characterized nonasymptotic properties of the algorithm such as local-minimum hitting and recurrence times [21]- [23]. Similar properties for the decaying weight parameter variant of SGLD were studied in [23]. When decaying weight parameters are used then SGLD coincides with the annealing algorithms considered in this paper. Asymptotic properties of such algorithms including convergence to global minima and convergence rates were considered in [17], [18].

A. Centralized GD + Annealing
Before discussing the distributed annealing algorithm, it will be helpful to review centralized gradient-based annealing algorithms. In particular, we will see that if annealing noise is added to (centralized) SGD (2), then the process escapes from local minima and seeks out global minima.
Given a differentiable function f , the centralized SGD + annealing algorithm is given by the recursion where γ k denotes the annealing schedule and w k is i.i.d. d-dimensional Gaussian noise. Note that if the annealing noise is "turned off" (i.e., γ k is set to zero) then (7) simply becomes SGD (2), and so converges to local minima. In order to ensure the convergence of SGD + annealing, additional structure must be assumed on the function f .
Part (i) of the assumption ensures that a global minimum of the problem exists, while parts (ii)-(iii) are technical assumptions that ensure that, as the algorithm runs, the probability distribution corresponding to the position of x k cannot have mass escape out to infinity.
Our next assumption is a technical assumption regarding the structure of f . After presenting the assumption, we will discuss simple conditions under which it can be satisfied.
dx, and where dπ e denotes the Radon-Nikodym derivative of a measure π ε taken with respect to the Lebesgue measure. Assume f is such that π ε has a weak limit π as ε → 0.
In the above assumption, the limiting distribution π is constructed so as to place mass 1 on the set of global minima of f . The intuition underlying the assumption is that for fixed noise strength γ k = ε, the distribution of x k can be shown to converge towards the stationary distribution π ε defined above [17], [20]. When sending γ k → 0, we would like the limiting distribution to be well defined and concentrate on the set of global minima-this is the point of Assumption 11.
The following lemma, adapted from [36], Theorem 3.1, gives a simple condition on the Hessian of f under which Assumption 11 can be guaranteed to hold.
exists and equals zero, (iii) There exists ε > 0 such that {f (x) ≤ ε} is compact, (iv) f is C 3 . Assume that N consists of a finite set of isolated points and that the Hessian ∇ 2 f (x) is invertible for all x ∈ N . Then the limit π in Assumption 12 exists.
The next assumption imposes some asymptotic regularity on the objective f . Assumption 12. The following hold: We emphasize Assumption 12 holds asymptotically as x → ∞. In applications, if a global minimum is known a priori to lie in some compact set, then this assumption can be trivially satisfied by modifying the objective function outside of the set. See, for example [37].
We will assume that the noise process {ξ k } satisfies Assumption 2 and that the annealing noise satisfies the following assumption, where we recall that F k represents the information available at iteration k. 7 Assumption 13. w k is normally distributed, w k ∼ N (0, I d ), independent of F k .
Finally, we will assume that the weight sequences (and, in particular, the annealing schedule γ k ) take the following form.
SGD + annealing converges in probability to the set of global minima. This is formalized in the following theorem from [17].
Theorem 9. Let {x k } satisfy (7). Suppose that Assumptions 2 and 10-14 hold and assume c α and c γ in Assumption 14 satisfy c γ /c α > C 0 , where the constant C 0 is defined after (2.3) in [17]. Then x k converges in probability to the set of global minima of f in the sense that, for any initial condition x 0 , and for any ε > 0 there holds P(dist(x k , S) > ε) → 0 as k → ∞, where S = arg min f (x).

B. Distributed Gradient Descent + Annealing
We now consider distributed annealing algorithms for global optimization. The algorithm considered here is a distributed version of (7). Alternatively, the algorithm may be viewed as a slight generalization of D-SGD (6) in which annealing noise is added at each agent. Let x n (k) denote agent n's estimate of an optimizer of (1) at iteration k. The D-SGD + annealing algorithm is defined agentwise by the recursion for n = 1, . . . , N , where w n (k) is Gaussian noise injected independently at each agent and each time step, and γ k denotes the annealing schedule. Note that if γ k is set to zero, then (8) becomes (6) and the algorithm converges to local minima of (1).
In the distributed setting we will retain the assumptions from the centralized setting (but now applied to (1)) and add the following assumption which ensures that agents can reach consensus.
Assumption 15. For each n, there exists a C > 0 such that x, ∇f n (x) ≥ 0 for all x ≥ C.
We will also assume that the consensus weight sequence {β k } takes the following form.
Assumption 16. β k = cβ k τ β for k large, where c β > 0 and τ β ∈ [0, 1/2). Under the above assumptions, agents reach consensus and converge to the set of global minima of F , as stated next. A proof of this result can be found in [30], [38].
Theorem 10. Let {(x n (k)) N n=1 } satisfy (8) with arbitrary initial condition (x n (k)) N n=1 = x 0 ∈ R N d . Suppose that Assumptions 10-12 and 14 are satisfied with f = F , where F is defined in (1), and that Assumptions 15-16 hold. Suppose also that for each n, the noise sequences {ξ n (k)} and {w n (k)} are mutually independent for all agents and satisfy Assumptions 2 and 13 respectively, with ξ n (k) = ξ k and w n (k) = w k . Further, suppose that c α and c γ in Assumptions 14 satisfy c 2 γ /c α > C 0 , where C 0 is defined after (2.3) in [17]. Then, lim k→∞ x n (k) − x (k) = 0 with probability 1 for each n, . Moreover, for each agent n, {x n (k)} converges in probability to the set of global minima of F , i.e., for any ε > 0, P(dist(x k , S) > ε) → 0 as k → ∞, where S = arg min F (x).

VI. ILLUSTRATIVE EXAMPLES
We illustrate the D-SGD and D-SGD + annealing algorithms on two simple examples: a small image classifier and a simple linear regression problem.
The image classifier is trained on the Fashion-MNIST task [39]. This example simulates (on a smaller scale) the potential use-case of training large deep neural networks that require multiple machines to learn and where the training bottleneck is the communication bandwidth between machines. 8 The model is a convolutional neural network with two convolutional layers followed by two fully connected layers and ReLU activation functions. All agents have their own independently shuffled copy of the data and the objective f n at agent n is given by the empirical risk using the agent's data and the cross-entropy loss. Using the D-SGD algorithm, we train with batches of size 1000, a learning rate (parameter α k ) of 0.5 decaying by 70% each epoch, and the consensus term is set to β k = 0.1. Each node is allowed to make 10 full passes through the data. For the communication graph we  consider both a cycle on four vertices and a 3-regular graph with 8 nodes. The results are shown in Table I, where we observe that the additional nodes improve the accuracy on the test set demonstrating the usefulness of the distributed algorithm. As a further comparison, we train a second centralized model for four times as many epochs so that it is a fair comparison with the decentralized run on four nodes. In this case the decentralized run is still able to beat the centralized baseline. It is important to remark that not all of the assumptions for D-SGD discussed in the paper are satisfied by this example (in particular, because we use ReLU activation functions, the function is not everywhere smooth). However, we find that that algorithm still performs well. An important future research direction is characterizing properties of distributed stochastic gradient algorithms under more general assumptions. We now turn to the second example, an illustration of the D-SGD + annealing algorithm on a simple regression task. The linear regression model is uni-variate with no intercept (y = wx) with a non-convex loss function L(y,ŷ) = log(8(y −ŷ) 2 + 1) designed to give robustness to extreme outliers [40]. Synthetic data is generated by sampling x values uniformly in the interval (0, 12) and using a binomial distribution with p = 0.55 to pick between the "real data" y 1 = 0.7x + and an adversarial distractor y 2 = 0.1x + where ∼ N (0, 1). This distribution is contrived to have a sub-optimal local minimum near w = 0.1 and a global minimum near w = 0.7. The data and the loss curve are shown in Figure 2. The objective at each agent n is given by f n (w) = 1 N E x,y∼D (L(wx, y)) and the overall objective is given by F (w) = E x,y∼D (L(wx, y)), where D represents the distribution for drawing samples previously mentioned. In this example, we consider an online learning setup. Let (x n (k), y n (k)) denote the sample drawn by agent n in iteration k. The update step (6) is done by taking ∇f n (w n (k)) + ξ n (k) = ∇ 1 N L(w n (k)x n (k), y n (k)). We use two graphs: a cycle on four vertices and the Petersen graph, a 3-regular graph with 10 vertices and 15 edges. To implement D-SGD + annealing on this setup we use an exponentially decaying learning rate α k = 0.01(0.998 k ) and fix the consensus term as 9 β k = 4 and annealing parameter γ k = 20(0.9 √ k ). We found that, at least for this example, a more aggressive annealing schedule can be used than what is given in Assumption 14 in order to speed up convergence. We compare this to the case when there is no annealing term, γ k = 0 (i.e., D-SGD). The simulation is run 100 times for k = 5000 steps, and then we check to see which of the two minima it has converged to. In the case of the 4-Cycle graph, D-SGD with annealing converges to the global minimum in 90 out of 100 cases compared to 57 out of 100 when no annealing is used. For the Petersen graph, the global minimum is reached in 98 of 100 cases with annealing and 61 of 100 without.

VII. CONCLUSIONS
The paper considered refined convergence guarantees for distributed stochastic gradient algorithms. Convergence of D-SGD to local minima was discussed. The key role of the stable-manifold theorem in studying saddle-point nonconvergence was explored, along with the use of stochastic approximation techniques and continuous-time analysis methods. In order to obtain global optimality guarantees, the use of additive annealing noise was discussed. The topic of refined convergence guarantees for distributed algorithms is a relatively new area and there are many open avenues for future research. We highlight a few now. This article discussed algorithms with decaying step sizes. It may be of interest to study stable-manifold theorems for DGD with constant step sizes, analogous to the centralized results [12], [13]. It may also be of interest to study the use of momentum in distributed gradient algorithms. Convergence rates for D-SGD + annealing are not currently understood, though convergence rate estimates do exist in the centralized case [18]. If γ k in D-SGD + annealing is held constant, then the D-SGD + annealing algorithm is a distributed variant of SGLD. Nonasymptotic properties of these algorithms have been studied in the centralized setting [21]- [23], but not in the distributed setting.