{'fraction_non_alphanumeric': 0.045079454896967984, 'fraction_numerical': 0.014594237751685763, 'mean_word_length': 4.1157882040767095, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension

We consider distributed optimization under communication constraints for training deep learning models. We propose a new algorithm, whose parameter updates rely on two forces: a regular gradient step, and a corrective direction dictated by the currently best-performing worker (leader). Our method differs from the parameter-averaging scheme EASGD in a number of ways: (i) our objective formulation does not change the location of stationary points compared to the original optimization problem; (ii) we avoid convergence decelerations caused by pulling local workers descending to different local minima to each other (i.e. to the average of their parameters); (iii) our update by design breaks the curse of symmetry (the phenomenon of being trapped in poorly generalizing sub-optimal solutions in symmetric non-convex landscapes); and (iv) our approach is more communication efficient since it broadcasts only parameters of the leader rather than all workers. We provide theoretical analysis of the batch version of the proposed algorithm, which we call Leader Gradient Descent (LGD), and its stochastic variant (LSGD). Finally, we implement an asynchronous version of our algorithm and extend it to the multi-leader setting, where we form groups of workers, each represented by its own local leader (the best performer in a group), and update each worker with a corrective direction comprised of two attractive forces: one to the local, and one to the global leader (the best performer among all workers). The multi-leader setting is well-aligned with current hardware architecture, where local workers forming a group lie within a single computational node and different groups correspond to different nodes. For training convolutional neural networks, we empirically demonstrate that our approach compares favorably to state-of-the-art baselines. This work is a gentle extension of [2].


Introduction
As deep learning models and data sets grow in size, it becomes increasingly helpful to parallelize their training over a distributed computational environment. These models lie at the core of many modern machine-learning-based systems for image recognition [3], speech recognition [4], natural language processing [5], and more. This paper focuses on the parallelization of the data, not the model, and considers collective communication scheme [6] that is most commonly used nowadays. A typical approach to data parallelization in deep learning [7,8] uses multiple workers that run variants of SGD [9] on different data batches. Therefore, the effective batch size is increased by the number of workers. Communication ensures that all models are synchronized and critically relies on a scheme where each worker broadcasts its parameter gradients to all the remaining workers. This is the case for DOWNPOUR [10] (its decentralized extension, with no central parameter server, based on the ring topology can be found in [11]) or Horovod [12] methods. These techniques require frequent communication (after processing each batch) to avoid instability/divergence, and hence are communication expensive. Moreover, training with a large batch size usually hurts generalization [13,14,15] and convergence speed [16,17]. LARS [18] proposes a layer-wise learning rate scaling method to overcome the difficulties of large batch training, but this method does not guarantee accelerations of convergence when the batch size is not large enough.
Another approach, called Elastic Averaging (Stochastic) Gradient Decent, EA(S)GD [1], introduces elastic forces linking the parameters of the local workers with central parameters computed as a moving average over time and space (i.e. over the parameters computed by local workers). This method allows less frequent communication as workers by design do not need to have the same parameters but are instead periodically pulled towards each other. The objective function of EASGD, however, has stationary points which are not stationary points of the underlying objective function (see Proposition 8 in the Supplement), thus optimizing it may lead to sub-optimal solutions for the original problem. Further, EASGD can be viewed as a parallel extension of the averaging SGD scheme [19] and as such it inherits the downsides of the averaging policy. On non-convex problems, when the iterates are converging to different local minima (that may potentially be globally optimal), the averaging term can drag the iterates in the wrong directions and significantly hurt the convergence speed of both local workers and the master. In symmetric regions of the optimization landscape, the elastic forces related with different workers may cancel each other out causing the master to be permanently stuck in between or at the maximum between different minima, and local workers to be stuck at the local minima or on the slopes above them. This can result in arbitrarily bad generalization error. We refer to this phenomenon as the "curse of symmetry". Landscape symmetries are common in a plethora of non-convex problems [20,21,22,23,24], including deep learning [25,26,27,28]. This paper revisits the EASGD update and modifies it in a simple, yet powerful way which overcomes the above mentioned shortcomings of the original technique. We propose to replace the elastic force relying on the average of the parameters of local workers by an attractive force linking the local workers and the current best performer among them (leader). Our approach reduces the communication overhead related with broadcasting parameters of all workers to each other, and instead requires broadcasting only the leader parameters. The proposed approach easily adapts to a typical hardware architecture comprising of multiple compute nodes where each node contains a group of workers and local communication, within a node, is significantly faster than communication between the nodes. We propose a multi-leader extension of our approach that adapts well to this hardware architecture and relies on forming groups of workers (one per compute node) which are attracted both to their local and global leader. To reduce the communication overhead, the correction force related with the global leader is applied less frequently than the one related with the local leader.
Finally, our L(S)GD approach, similarly to EA(S)GD, tends to explore wide valleys in the optimization landscape when the pulling force between workers and leaders is set to be small. This property often leads to improved generalization performance of the optimizer [29,30].
The paper is organized as follows: Section 2 introduces the L(S)GD approach, Section 3 provides theoretical analysis, Section 4 contains empirical evaluation, and finally Section 5 concludes the paper. Theoretical proofs and additional theoretical and empirical results are contained in the Supplement.
2 Leader (Stochastic) Gradient Descent "L(S)GD" Algorithm 2.1 Motivating example Figure 1 illustrates how elastic averaging can impair convergence. To obtain the figure we applied EAGD (Elastic Averaging Gradient Decent) and LGD to the matrix completion problem of the form: min X 1 4 M − XX T 2 F : X ∈ R d×r . This problem is non-convex but is known to have the property that all local minimizers are global minimizers [20]. For four choices of the rank r, we generated 10 random instances of the matrix completion problem, and solved each with EAGD and LGD, initialized from the same starting points (we use 8 workers). For each algorithm, we report the progress of the best objective value at each iteration, over all workers. Figure 1 shows the results across 10 random experiments for each rank.
It is clear that EAGD slows down significantly as it approaches a minimizer. Typically, the center X of EAGD is close to the average of the workers, which is a poor solution for the matrix completion problem when the workers are approaching different local minimizers, even though all local minimizers are globally optimal. This induces a pull on each node away from the minimizers, which makes it extremely difficult for EAGD to attain a solution of high accuracy. In comparison, LGD does not have this issue. Further details of this experiment, and other illustrative examples of the difference between EAGD and LGD, can be found in the Supplement.

Symmetry-breaking updates
Next we explain the basic update of the L(S)GD algorithm. Consider first the single-leader setting and the problem of minimizing loss function L in a parallel computing environment. The optimization problem is given as where l is the number of workers, x 1 , x 2 , . . . , x l are the parameters of the workers andx are the parameters of the leader. The best performing worker, i.e.x = arg min , and ξ i s are data samples drawn from some probability distribution P. λ is the hyperparameter that denotes the strength of the force pulling the workers to the leader. In the theoretical section we will refer to E[f (x i ; ξ i )] as simply f (x i ). This formulation can be further extended to the multi-leader setting. The optimization problem is modified to the following form min x 1,1 ,x 1,2 ,...,x n,l L(x 1,1 , x 1,2 , . . . , x n,l ) := min where n is the number of groups, l is the number of workers in each group,x j is the local leader of the j th group (i.e.x j = arg min x j,1 ,x j,2 ,..., x is the global leader (the best worker among local leaders, i.e.x = arg min . , x j,l are the parameters of the workers in the j th group, and ξ j,i s are the data samples drawn from P. λ and λ G are the hyperparameters that denote the strength of the forces pulling the workers to their local and global leader respectively. The updates of the LSGD algorithm are captured below, where t denotes iteration. The first update shown in Equation 3 is obtained by taking the gradient descent step on the objective in Equation 2 with respect to variables x j,i . The stochastic gradient of E[f (x i ; ξ i )] with respect to x j,i is denoted as g j,i t (in case of LGD the gradient is computed over all training examples) and η is the learning rate.
wherex j t+1 andx t+1 are the local and global leaders defined above. Equation 3 describes the update of any given worker and is comprised of the regular gradient step and two corrective forces (in single-leader setting the third term disappears as λ G = 0 then). These

Algorithm 1 LSGD Algorithm (Asynchronous)
Input: pulling coefficients λ, λ G , searching scopes γ, γ G , learning rate η, local/global communication periods τ, τ G Initialize: Randomly initialize x 1,1 , x 1,2 , ..., x n,l Set iteration counters t j,i = 0 Setx j 0 = arg min for all j = 1, 2, . . . , n, i = 1, 2, . . . , l do Do in parallel for each worker Draw random sample ξ j,i Determine the local best workers Pull to the local best workers end if Determine the global best worker Pull to the global best worker end if end for until termination forces constitute the communication mechanism among the workers and pull all the workers towards the currently best local and global solution to ensure fast convergence. As opposed to EASGD, the updates performed by workers in LSGD break the curse of symmetry and avoid convergence decelerations that result from workers being pulled towards the average which is inherently influenced by poorly performing workers. In this paper, instead of pulling workers to their averaged parameters, we propose the mechanism of pulling the workers towards the leaders. The flavor of the update resembles a particle swarm optimization approach [31], which is not typically used in the context of stochastic gradient optimization for deep learning. Our method may therefore be viewed as a dedicated particle swarm optimization approach for training deep learning models in the stochastic setting and parallel computing environment.
Next we describe the LSGD algorithm in more detail. We rely on the collective communication scheme. In order to reduce the amount of communication between workers, it is desired to update the leaders less frequently than every iteration. Also, in practice each worker can have a different speed. To prevent waiting for the slower workers and achieve communication efficiency, we implement the algorithm in the asynchronous operation mode. In this case, the communication period is determined based on the total number of iterations computed across all workers and the communication is performed every nlτ or nlτ G iterations, where τ and τ G denote local and global communication periods, respectively. In practice, we use τ G > τ since communication between workers lying in different groups is more expensive than between workers within one group, as explained above. When communication occurs, all workers are updated at the same time (i.e. pulled towards the leaders) in order to take advantage of the collective communication scheme. Between communications, workers run their own local SGD optimizer to find a better solution nearby the leaders. The hyperparameters γ and γ G control the overall searching scopes of the workers around their local leaders and global leader, respectively. In practice, to encourage the workers to stay inside their search ranges, we pull the workers towards the leaders as well. The resulting LSGD method is very simple, and is depicted in Algorithm 1. Note that this algorithm is a slight modification of the algorithm from [2]. The modification is based on the observation that pulling the workers towards leaders could improve the performance even if the leaders become stale.
The next section provides a theoretical description of the single-leader batch (LGD) and stochastic (LSGD) variants of our approach.

Theoretical Analysis
We assume without loss of generality that there is a single leader. The objective function with multiple leaders is given by Proofs for this section are deferred to the Supplement.

Convergence Rates for Stochastic Strongly Convex Optimization
We first show that LSGD obtains the same convergence rate as SGD for stochastic strongly convex problems [32]. In Section 3.3 we discuss how and when LGD can obtain better search directions than gradient descent. We discuss non-convex optimization in Section 3.2. Throughout Section 3.1, f will typically satisfy: We write x * for the unique minimizer of f , and κ := M m for the condition number of f .

Convergence Rates
The key technical result is that LSGD satisfies a similar one-step descent in expectation as SGD, with an additional term corresponding to the pull of the leader. To provide a unified analysis of 'pure' LSGD as well as more practical variants where the leader is updated infrequently or with errors, we consider a general iteration where z is an arbitrary guiding point; that is, z may not be the minimizer of x 1 , . . . , x p , nor even satisfy f (z) ≤ f (x i ). Since the nodes operate independently except when updating z, we may analyze LSGD steps for each node individually, and we write x = x i for brevity.
Then the LSGD step satisfies Note the presence of the new term −ηλ(f (x)−f (z)) which speeds up convergence when f (z) ≤ f (x), i.e the leader is better than x. If the leader z k is always chosen so that The O( 1 k ) rate of LSGD matches that of comparable distributed methods. Both Hogwild [33] and EASGD achieve a rate of O( 1 k ) on strongly convex objective functions. We note that published convergence rates are not available for many distributed algorithms (including DOWNPOUR [10]).

Communication Periods
In practice, communication between distributed machines is costly. The LSGD algorithm has a communication period τ for which the leader is only updated every τ iterations, so each node can run independently during that period. This τ is allowed to differ between nodes, and over time, which captures the asynchronous and multi-leader variants of LSGD. We write x k,j for the j-th step during the k-th period. It may occur that f (z) > f (x k,j ) for some k, j, that is, the current solution x k,j is now better than the last selected leader. In this case, the leader term λ(x − z) may no longer be beneficial, and instead simply pulls x toward z. There is no general way to determine how many steps are taken before this event. However, we can show that if f (z) ≥ f (x), then so the solution will not become worse than a stale leader (up to gradient noise). As τ goes to infinity, LSGD converges to the minimizer of ψ(x) = f (x)+ λ 2 x−z 2 , which is quantifiably better than z as captured in Theorem 2. Together, these facts show that LSGD is safe to use with long communication periods as long as the original leader is good.
Theorem 2. Let f be m-strongly convex, and let x * be the minimizer of f . For fixed λ, z, define The theoretical results here and in Section 3.1.1 address two fundamental instances of the LSGD algorithm: the 'synchronous' case where communication occurs each round, and the 'infinitely asynchronous' case where communication periods are arbitrarily long. For unknown periods τ > 1, it is difficult to demonstrate general quantifiable improvements beyond (5), but we note that (4), Theorem 2, and the results on stochastic leader selection (Sections 3.1.3 and 7.6) can be combined to analyze specific instances of the asynchronous LSGD.
In our experiments, we employ another method to alleviate the issue of stale leaders. To increase the importance of the leader when it is good, we perform a larger LSGD step on the first step after a leader update, and take smaller LSGD steps for the remainder of the communication period ( γ τ < λ and γ G τ G < λ G ).

Stochastic Leader Selection
Next, we consider the impact of selecting the leader with errors. In practice, it is often costly to evaluate f (x), as in deep learning. Instead, we estimate the values f (x i ), and then select z as the variable having the smallest estimate. Formally, suppose that we have an unbiased estimator f (x) of f (x), with uniformly bounded variance. At each step, a single sample y 1 , . . . , y p is drawn from each estimator f (x 1 ), . . . , f (x p ), and then z = {x i : y i = min{y 1 , . . . , y p }}. We refer to this as stochastic leader selection. The stochastic leader satisfies is the true leader (see supplementary materials). Thus, the error introduced by the stochastic leader contributes an additive error of at most 4ηλ √ pσ f . Since this is of order η rather than η 2 , we cannot guarantee convergence with η k = Θ( 1 k ) 1 unless λ k is also decreasing. We have the following result: Theorem 3. Let f satisfy Assumption 1, and let g(x) be as in Theorem 1. Suppose we use stochastic . The communication period and the accuracy of stochastic leader selection are both methods of reducing the cost of updating the leader, and can be substitutes. When the communication period is long, it may be effective to estimate f (x i ) to higher accuracy, since this can be done independently.

Non-convex Optimization: Stationary Points
As mentioned above, EASGD has the flaw that the EASGD objective function can have stationary points such that none of x 1 , . . . , x p , x is a stationary point of the underlying function f . LSGD does not have this issue. Theorem 4. Let Ω i be the points (x 1 , . . . , x p ) where x i is the unique minimizer among (x 1 , . . . , x p ).
Moreover, it can be shown that for the deterministic algorithm LGD with any choice of communication periods, there will always be some variable x i such that lim inf ∇f (x i k ) = 0. Theorem 5. Assume that f is bounded below and M -Lipschitz-differentiable, and that the LGD step sizes are selected so that η i < 2 M . Then for any choice of communication periods, it holds that for every i such that x i is the leader infinitely often, lim inf k ∇f (x i k ) = 0.

Search Direction Improvement from Leader Selection
In this section, we discuss how LGD can obtain better search directions than gradient descent. In general, it is difficult to determine when the LGD step will satisfy f (x − η(∇f (x) + λ(x − z))) ≤ f (x−η∇f (x)), since this depends on the precise combination of f, x, z, η, λ, and moreover, the maximum allowable value of η is different for LGD and gradient descent. Instead, we measure the goodness of a search direction by the angle it forms with the Newton direction d N ( The Newton method is locally quadratically convergent around local minimizers with non-singular Hessian, and converges in a single step for quadratic functions if η = 1. Hence, we consider it desirable to have search directions that are close to d N . Let θ(u, v) denote the angle between u, v. Let We aim to show that a large subset of leaders in E belong to I θ (x, λ).
In this section, we consider the positive definite quadratic The first result shows that as λ becomes sufficiently small, at least half of E improves the angle. We use the n-dimensional volume Vol(·) to measure the relative size of sets: an ellipsoid E given by where S n is the unit ball. Theorem 6. Let x be any point such that Next, we consider when λ is large. We show that points with large angle between d G (x), d N (x) exist, which are most suitable for improvement by LGD. For r ≥ 2, define S r = {x : It can be shown that S r is nonempty for all r ≥ 2. We show that for x ∈ S r for a certain range of r, I θ (x, λ) is at least half of E for any choice of λ.
. If x ∈ S r for r ∈ R κ , then for any λ ≥ 0, Vol(I θ (x, λ)) ≥ 1 2 Vol(E). Note that Theorems 6 and 7 apply only to convex functions, or in the neighborhoods of local minimizers where the objective function is locally convex. In nonconvex landscapes, the Newton direction may point towards saddle points [34], which is undesirable; however, since Theorems 6 and 7 do not apply in this situation, these results do not imply that LSGD has harmful behavior. For nonconvex problems, our intuition is that many candidate leaders lie in directions of negative curvature, which would actually lead away from saddle points, but this is significantly harder to analyze since the set of candidates is unbounded a priori. Figure 2: CNN7 on CIFAR-10. Test error for the center variable versus wall-clock time (original plot on the left and zoomed on the right). Test loss is reported in Figure 9 in the Supplement.

Experimental setup
In this section we compare the performance of LSGD with stateof-the-art methods for parallel training of deep networks, such as DataParallel 3 (vanilla distributed data parallelization method), LARS, and EASGD (its pseudo-codes can be found in [1]), as well as sequential technique SGD. All methods use momentum. We use communication period equal to 1 for DataParallel and LARS in all our experiments as this is the typical setting used for these methods ensuring stable convergence. The experiments were performed using the CIFAR-10 data set [35] on three benchmark architectures: 7-layer CNN used in the original EASGD paper (see Section 5.1. in [1]) that we refer to as CNN7, VGG16 [36], and ResNet20 [37]; and ImageNet (ILSVRC 2012) data set [38] on ResNet50.  Figure 10 in the Supplement.
During training, we select the leader for the LSGD method based on the average of the training loss computed over the last 10 (CIFAR-10) and 64 (Ima-geNet) data batches. At testing, we report the performance of the center variable for EASGD and LSGD, where for LSGD the center variable is computed as the average of the parameters of all workers. [Remark: Note that we use the leader's parameter to pull to at training and we report the averaged parameters at testing deliberately. It is demonstrated in our paper (e.g.: Figure 1) that pulling workers to the averaged parameters at training may slow down convergence and we address this problem. Note that after training, the parameters that workers obtained after convergence will likely lie in the same valley of the landscape (see [39]) and thus their average is expected to have better generalization ability (e.g. [29,40]), which is why we report the results for averaged parameters at testing.] Finally, for all methods we use Nesterov momentum of 0.9 and weight decay with decay coefficient set to 10 −4 . In our experiments we use either 4 workers (single-leader LSGD setting) or 12 workers (multi-leader LSGD setting with 3 groups of workers). For all methods, we report the optimal choice of hyperparameters leading to the smallest achievable test error under similar convergence rates. Figure 4: ResNet20 on CIFAR-10. Test error for the center variable versus wall-clock time (original plot on the left and zoomed on the right). Test loss is reported in Figure 11 in the Supplement.
We use GPU nodes interconnected with Ethernet. Each GPU node has four GTX 1080 GPU processors where each local worker corresponds to one GPU processor. We use CUDA Toolkit 10.0 4 and NCCL 2 5 . We have developed a software package based on PyTorch for distributed training, which will be released (details are elaborated in Section 9.4).
Data processing and prefetching are discussed in the Supplement. The summary of the hyperparameters explored for each method are also provided in the Supplement. We use constant learning rate for CNN7 and learning rate drop (we divide the learning rate by 10 when we observe saturation of the optimizer) for VGG16, ResNet20, and ResNet50.

Experimental Results
4 https://developer.nvidia.com/cuda-zone 5 https://developer.nvidia.com/nccl Figure 5: ResNet20 on CIFAR-10. The identity of the worker that is recognized as the leader (i.e. rank) versus iterations (on the left) and the number of times each worker was the leader (on the right).
In Figure 2 we report results obtained with CNN7 on CIFAR-10. Our method consistently outperforms the competitors in terms of convergence speed (it is roughly 1.5 times faster than EASGD for 12 workers).
In Figure 3 we demonstrate results for VGG16 and CIFAR-10. LSGD obtains a much better solution than other methods. Furthermore, LSGD converges marginally faster than EASGD and it outperforms DataParallel and LARS significantly.
The experimental results obtained using ResNet20 and CIFAR-10 are shown in Figure 4. On 4 workers we converge comparably fast to EASGD but recover better test error. For this experiment in Figure 5 we show the switching pattern between the leaders indicating that LSGD indeed takes advantage of all workers when exploring the landscape. On 12 workers we converge roughly 1.5 times faster than EASGD and obtain significantly smaller error. In CNN7, VGG16 and this experiment, LSGD is consistently better than DataParallel and LARS in the aspect of convergence speed, as expected. Remark 1. We believe that these two facts together -(1) the schedule of leader switching recorded in the experiments shows frequent switching, and (2) the leader point itself is not pulled away from minima -suggest that the 'pulling away' in LSGD is beneficial: non-leader workers that were pulled away from local minima later became the leader, and thus likely obtained an even better solution than they originally would have. Finally, in Figure 6 we report the empirical results for ResNet50 run on ImageNet. In this experiment our algorithm behaves comparably to LARS but converges much faster than EASGD for 12 workers. Also note that for ResNet50 on ImageNet, SGD is consistently worse than all reported methods (training on ImageNet with SGD on a single GTX1080 GPU until convergence usually takes about a week and gives slightly worse final performance), which is why the SGD curve was deliberately omitted (other methods converge in around two days). Figure 6: ResNet50 on ImageNet. Test error for the center variable versus wall-clock time (original plot on the left and zoomed on the right). Test loss is reported in Figure 12 in the Supplement.

Conclusion
In this paper we propose a new algorithm called LSGD for distributed optimization in nonconvex settings. Our approach relies on pulling workers to the current best performer among them, rather than their average, at each iteration. We justify replacing the average by the leader both theoretically and through empirical demonstrations. We provide a thorough theoretical analysis, including proof of convergence, of our algorithm. Finally, we apply our approach to the matrix completion problem and training deep learning models and demonstrate that it is well-suited to these learning settings.

Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models (Supplementary Material) Abstract
This Supplement presents additional details in support of the full article. These include the proofs of the theoretical statements from the main body of the paper and additional theoretical results. We also provide a toy illustrative example of the difference between LSGD and EASGD. Finally, the Supplement contains detailed description of the experimental setup and additional experiments and figures to provide further empirical support for the proposed methodology. We consider the following non-convex optimization problem: min x,y L(x, y), where L(x, y) = sin( x 2 + y 2 · π)

Proofs of Theoretical Results
We provide omitted proofs from the main text.

Definitions and Notation
Recall that the objective function of Leader (Stochastic) Gradient Descent (L(S)GD) is defined as where x = arg min{f (x 1 ), . . . , f (x p )}. An L(S)GD step is a (stochastic) gradient step applied to L. Writing z = x at a particular (x 1 , . . . , x n ), the update in the variable x i is ) Observe that this reduces to a (S)GD step for the variable which is the leader.
Practical variants of the algorithm do not communicate the updated leader at every iteration. Thus, in our analysis, we will generally take z to be an arbitrary guiding point, which is not necessarily the minimizer of x 1 , . . . , x p , nor even satisfy f (z) ≤ f (x i ) for all i. The required properties of z will be specified on a result-by-result basis.
When discussing the optimization landscape of LSGD, the term 'LSGD objective function' will refer to (6) with x defined as the argmin.
Communication periods are sequences of steps where the leader is not updated. We introduce the notation x k,j for the j-th step in the k-th period, where the leader z is updated only at the beginning of each period. We write b i (k) for the number of steps that x i takes during the k-th period. The standard LSGD defined above has b i (k) = 1 for all i, k, in which case x i k,1 = x i k . In addition, let x k = argmin{f (x 1 k,1 ), . . . , f (x p k,1 )}, the leader for the k-th period.

Stationary Points of EASGD
The EASGD [1] objective function is defined as Observe that unlike LSGD, x is a decision variable of EASGD. A stationary point of EASGD is a point such that ∇L(x 1 , . . . , x p , x) = 0. Proposition 8. There exists a Lipschitz differentiable function f : R → R such that for every 0 < λ ≤ 1, there exists a point (x λ , y λ , 0) which is a stationary point of EASGD with parameter λ, but none of {x λ , y λ , 0} is a stationary point of f .
where p(x) = a 6 x 6 +. . .+a 1 x+a 0 is a sixth-degree polynomial. For f to be Lipschitz differentiable, we will select p(x) to make f twice continuously differentiable, with bounded second derivative. To make f twice continuously differentiable, we must have p(1) = 1, p (1) = −1, p (1) = 1 and p(−1) = −1, p (−1) = 1, p (−1) = −1. Since we aim to have f (0) = 0, we also will require f (0) = p (0) = 1. The existence of p is equivalent to the solvability of a linear system, which is easily checked to be invertible. Thus, we deduce that such a function f exists.

Technical Preliminaries
Recall the statement of Assumption 1: Assumption 1 f is M -Lipschitz-differentiable and m-strongly convex, which is to say, the gradient ∇f satisfies ∇f (x) − ∇f (y) ≤ M x − y , and f satisfies We write x * for the unique minimizer of f , and κ := M m for the condition number of f .
We will frequently use the following standard result.
Lemma 10. Let f be m-strongly convex, and let x * be the minimizer of f . Then and Proof. Equation (8) is the well-known Polyak-Łojasiewicz inequality. Equation (9) follows from the definition of strong convexity, and ∇f (x * ) = 0.
Lemma 11. Let f be M -Lipschitz-differentiable. If the gradient descent step size η < 2 M , then Proof. By Theorem 9, Rearranging yields the desired result.

Proofs from Section 3.1.1
Lemma 12 (One-Step Descent). Let f satisfy Assumption 1. Let g(x) be an unbiased estimator for ∇f (x) with Var( g(x)) ≤ σ 2 + ν ∇f (x) 2 . Let x be the current iterate, and let z be another point, with δ := x − z. The LSGD step x + = x − η( g(x) + λ(x − z)) satisfies: where the expectation is with respect to g(x), and conditioned on the current point x. Hence, for sufficiently small η, λ with η ≤ (2M (ν + 1)) −1 and ηλ ≤ (2κ Proof. The proof is similar to the convergence analysis of SGD. We apply Theorem 9 to obtain Taking the expectation and using E g(x) = ∇f (x), Using the definition of m-strong convexity, we have . Substituting this above, and splitting both the terms η ∇f (x) 2 , η 2 mλ δ 2 in half, we obtain We proceed to bound each line. For the first line, the standard bias-variance decomposition yields and so we have For the second line, we obtain For the third line, we apply the inequality a 2 + b 2 ≥ 2ab to obtain Using the Cauchy-Schwarz inequality, we then obtain Combining these inequalities yields the desired result.
Theorem 15. Let f be m-strongly convex, and let x * be the minimizer of f . Fix a constant λ and any point z, and define the function ψ(x) = f (x) + λ 2 x − z 2 . Since ψ is strongly convex, it has a unique minimizer w. The minimizer w satisfies Proof. The first-order condition for w implies that ∇f (w) + λ(w − z) = 0, so λ 2 w − z 2 = ∇f (w) 2 . Combining this with the Polyak-Łojasiewicz inequality, we obtain , which yields the first inequality. We also have ψ Finally, by Theorem 10, f (w) − f (x * ) ≥ m 2 w − x * 2 , which yields the result.

Proofs from Section 3.1.3
We first present two lemmas which consider the problem of selecting the minimizer from a collection, based on a single estimate of the value of each item. Lemma 16. Let µ 1 ≤ µ 2 ≤ . . . ≤ µ p . Suppose that Y 1 , . . . , Y p is a collection of random variables with EY i = µ i and Var(Y i ) ≤ σ 2 . Let µ = µ m where m = argmin{Y 1 , . . . , Y p }. Then Therefore, for any a ≥ 0, Pr( µ ≥ µ 1 + a) ≤ 4σ 2 p a 2 .
Proof. In order for µ m ≥ µ k , we must have Y j ≤ Y 1 for some j ≥ k. Thus, { µ ≥ µ k } is a subset of the event {Y 1 ≥ min{Y k , . . . , Y p }}. Taking the union bound, then this can be tightened to 2σ 2 ), we have Lemma 17. Let µ be defined as in Theorem 16. Then Proof. Recall that the expected value of a non-negative random variable Z can be expressed as EZ = ∞ 0 Pr(Z ≥ t)dt. We apply this to the variable µ − µ 1 . Using Theorem 16, we obtain, for any a > 0, The AM-GM inequality implies that a + 4σ 2 p a ≥ 4 √ pσ, with equality when a = 2 √ pσ.
We now apply this to stochastic leader selection in LSGD, where µ i corresponds to the true value f (x i ), and Y i is a function estimator. Lemma 18. Let f satisfy Assumption 1. Suppose that LSGD has a gradient estimator with Var( g(x)) ≤ σ 2 + ν ∇f (x) 2 and selects the stochastic leader with a function estimator f (x) with Var( f (x)) ≤ σ 2 f . Then, taking the expectation with respect to the gradient estimator and the stochastic leader z, we have Proof. From Theorem 12, we obtain Note that in the last line, we have Ef (z) because z is now stochastic. Applying Theorem 17 to the stochastic leader, we obtain Ef (z) ≤ f (z true ) + 4 √ pσ f . The true leader satisfies f (z true ) ≤ Theorem 19. Let f satisfy Assumption 1. If η, λ are fixed so that η ≤ (2M (ν + 1)) −1 and Proof. Interpret the term 4ηλ √ pσ f as additive noise. Note that if η k , λ k = Θ( 1 k ), then ηλ = Θ( 1 k 2 ). The proof is then similar to Theorem 13 and follows from Theorems 4.6 and 4.7 of [32]. 7.7 Proofs from Section 3.2 Theorem 20. Let Ω i be the set of points (x 1 , . . . , x p ) where x i is the unique minimizer among (x 1 , . . . , x p ) 7 . Let x * = (w 1 , . . . , w p ) ∈ Ω i be a stationary point of the LGD objective function (6).
Proof. This follows from the fact that on Ω i , ∂L ∂x i = ∇f i (x i ).
Lemma 21. Let f be M -Lipschitz-differentiable. Let x k denote the leader at the end of the k-th period. If the LGD step size is chosen so that Proof. Assume that x k−1 = x 1 k−1 . Since x 1 is the leader during the k-th period, the LGD steps for x 1 are gradient descent steps. By Theorem 11, η 1 has been chosen so that gradient descent on f is monotonically decreasing, so we know that f (

Theorem 22.
Assume that f is bounded below and M -Lipschitz-differentiable, and that the LGD step sizes are selected so that η i < 2 M . Then for any choice of communication periods, it holds that for every i such that x i is the leader infinitely often, lim inf k ∇f (x i k ) = 0. Note that there necessarily exists an index i such that x i is the leader infinitely often.

Proofs from Section 3.3
The cone with center d and angle θ c is defined to be We record the following facts about cones which will be useful.
If y is a point such that sy ∈ C for some s ≥ 0, then y ∈ cone(d, θ c ).
Proof. This follows immediately from the fact that θ(y, d) = θ(sy, d) for all s ≥ 0.
Proposition 24. Let C = cone(d, θ c ) with θ c > 0. The outward normal vector at the point x ∈ ∂C is given by N x = x − x cos(θc) d d. Moreover, if v satisfies N T x v < 0, then for sufficiently small positive λ, x + λv ∈ cone(d, θ c ).
Proof. The first statement follows from the second, by the supporting hyperplane theorem.

Low-Rank Matrix Completion Experiments
Low-rank matrix completion problem is an example of a non-convex learning problem whose landscape exhibits numerous symmetries. We consider the positive semi-definite case, where the objective is to find a low-rank matrix minimizing It is routine to calculate that ∇F (X) = (XX T − M )X. The EAGD and LGD updates for X can be expressed as For EAGD, Z = X, and X is updated by For LGD, Z = arg min{F (X 1 ), . . . , F (X p )}, and is updated at the beginning of every communication period τ .
The parameters were set to: The learning rate η = 5e-4 was selected from a set {1e-1, 5e-2, 1e-3, . . .} by evaluating on a sample problem until a value was found for which both methods exhibited monotonic decrease.
The dimension was d = 1000, and the ranks r ∈ {1, 10, 50, 100} were tested. For each rank, there were 10 random trials performed. In each trial, M and starting points {X i 0 } are sampled. M is generated by sampling U ∈ R d×r with i.i.d entries from N (0, 1), and taking M = U U T . Initial points for each worker node X i were also sampled from N (0, 1). The same starting points were used for EAGD and LGD.
Code for this experiment is available at https://github.com/wgao-res/lsgd_matrix_ completion. For CNN7 and ResNet20, we extract random crops of size 3 × 28 × 28 and present these to the network in batches of size 128. The test loss and test error are only computed from the center patch (3 × 28 × 28) of test images.
For VGG16 we pad the images to 3 × 40 × 40, extract random crops of size 3 × 32 × 32 and present these to the network in batches of size 128. The test loss and test error are computed from the test images.
For ImageNet experiments we normalize each image by mean (0.485, 0.456, 0.406) and standard deviation (0.229, 0.224, 0.225). We sample the training data in the same way as [41]. For each image, a crop of random size (chosen from 8% to 100% evenly) of the original size and a random aspect ratio (chosen from 3/4 to 4/3 evenly) of the original aspect ratio is made. Then we resize the crop to 3 × 224 × 224. We also augment the training data by horizontal flips with a probability of 0.5. Finally we present these to the network in the batches of size 32. The test images are resized so that the smaller edge of each image is 256. The test loss and test error are only computed from the center patch (3 × 224 × 224) of test images.

Data prefetching
We use the dataloader and distributed data sampler 9 from PyTorch. Each worker loads a subset of the original data set that is exclusive to that worker for every epoch. If the size of data set is not divisible by the batch size, the last incomplete batch will be dropped.

Hyperparameters
In Table 2 we summarize the learning rates and other hyperparameters explored for each method in the experiments on CIFAR-10. The setting of β for EASGD was obtained from the original paper (its authors use this setting for all their experiments). We do learning rate drop at 500 seconds by a factor of 0.1 for all the methods. In Table 3 we summarize the learning rates and other hyperparameters explored for each method in experiments on ImageNet. We do learning rate drop for every 30 epochs by a factor of 0.1 for all the methods.

Implementation Details
To take advantage of both the efficiency of collective communication and the flexibility of peer-to-peer communication, we incorporate two backends, namely NCCL and GLOO 10 , for GPU processors and CPU processors, respectively.
The global and local servers (running on CPU processors) control the training process and the workers (running on GPU processors) perform the actual computations. For each iteration each worker has only one of the following two choices: 1. Local Training: Each worker is trained with one batch of the training data; 2. Distributed Training: Each worker communicates with other workers and updates its parameters based on the pre-defined distributed training method.
To minimize the cost of communication over Ethernet, the global server is running on the first GPU node instead of a separate machine. Also, for a fair comparison, the center variable is being maintained and updated by the first GPU node as well 11 . Figure 8: At the beginning of each iteration, the local worker sends out a request to its local server and then the local server passes on the worker's request to the global server. The global server checks the current status and replies to the local server. The local server passes on the global server's message to the worker. Finally, depending on the message from the global server, the worker will choose to follow the local training or distributed training scheme.
10 More results from Section 4.2