{'fraction_non_alphanumeric': 0.04303694681282988, 'fraction_numerical': 0.01364190012180268, 'mean_word_length': 4.326989619377162, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Sharp Convergence Rate for the Asynchronous Stochastic Gradient Descent

We give a sharp convergence rate for the asynchronous stochastic gradient descent (ASGD) algorithms when the loss function is a perturbed quadratic function based on the stochastic modified equations introduced in [An et al. Stochastic modified equations for the asynchronous stochastic gradient descent, arXiv:1805.08244]. We prove that when the number of local workers is larger than the expected staleness, then ASGD is more efficient than stochastic gradient descent. Our theoretical result also suggests that longer delays result in slower convergence rate. Besides, the learning rate cannot be smaller than a threshold inversely proportional to the expected staleness.


Introduction
Thanks to the availability of large datasets and modern computing resources, optimizationbased machine learning has achieved state-of-the-art results in many applications of artificial intelligence. As the datasets continue to increase, distributed optimization algorithm have received more attention for solving large scale machine learning problems. Parallel stochastic gradient descent (SGD) is arguably the most popular one among them.
Based on the interaction between different working nodes, there are two types of parallel SGD algorithms: synchronous v.s. asynchronous SGD (SSGD v.s. ASGD). Both methods compute the gradient of the loss function for a given mini-batch on local workers. In SSGD, the local workers pause the training process until the gradients from all local works have been added into the shared parameter variable. While in ASGD, the local workers interact with the shared parameter independently without any synchronization, i.e., each local worker continues to compute the next gradient right after their own gradients have been added to the shared parameter. Therefore, ASGD is presumably more efficient than SSGD since the overall training speed is not affected by the slow local workers. On the other hand, ASGD can potentially suffer from the problem of delayed gradients, i.e., the gradients that a local worker sends to the shared parameter are often computed with respect to the parameter of an older version of the model. Therefore, extra stochasticity is introduced in ASGD due to this delay. An interesting mathematical problem is how the delayed gradient affects the training process.
There have been a few papers in the literature that analyze the convergence rate of ASGD, but most of them from an optimization perspective. For example, [11,4,9] proved that ASGD can achieve a nearly optimal rate of convergence when the optimization problem is sparse; [10] studies the relationship between ASGD and momentum SGD.
This note follows a perspective based on partial differential equation (PDE) and stochastic differential equation (SDE). In [7], Li et al first introduced the stochastic modified equations (SME) for modeling the dynamics of SGD in a continuous time approximation. Following this work, there have been quite a few papers along this direction [6,8,3,5] for SGD. Recently, in [1], An et al applied the SME approach to the study of ASGD.
This note studies the convergence rate of the time-dependent probability distribution function (PDF) of ASGD to its steady state distribution by using PDE techniques of the stochastic modified equation. The main focus is on the case where the loss function is a perturbed quadratic function. There are mainly two difficulties in this analysis. The first one is that asynchrony results in a degenerate diffusion operator in the corresponding PDE. No trivial analysis is able to give an exponential decay rate for the convergence to the steady state. Thanks to the association of a degenerate diffusion operator and a conservative operator, the decay rate can be recovered through "hypocoercivity" [12]. The key here is to construct a Lyapunov functional to prove the exponential decay of this functional. The second difficulty is to obtain a sharp convergence rate. Such a sharp rate is important to understand the influence of the asynchrony quantitatively. Though our analysis is based on the framework introduced by [2], the current case is more complicated because one has to bound extra terms introduced by the perturbed loss function around the quadratic function. The main observations of this paper are the following: • We give a sharp convergence rate for ASGD when the loss function is a perturbed quadratic function.
• For a fixed learning rate, longer delays result in slower convergence rate.
• The learning rate should not be smaller than a threshold and the threshold is inversely proportional to the staleness rate. See Remark 3.3 for details.
• When the number of local workers is larger than the expectated staleness, then ASGD is more efficient than SGD. See Remark 3.4 for details.
The rest of the paper is organized as follows. Section 2 summarizes the results of [1] and derives the PDE for the probability density function (PDF) of ASGD based on these results. Section 3 presents the main results, while the proof of the main theorem is given in Section 4.

PDE for the probability density function of ASGD
We consider the minimization problem, where θ represents the model parameters, f i (θ) denotes the loss function at the i-th training sample and n is the size of the training sample set. In the asynchronous stochastic gradient descent (ASGD) algorithm, the parameter θ is updated with where γ k is i.i.d. uniform random variable from {1, 2, · · · , n} and θ k−τ k is the delayed read of the parameter θ used to update θ k+1 with a random staleness τ k .
In [1], An et al derived the modified stochastic differential equation for the algorithm, under the assumption that τ k follows the geometric distribution, i.e., τ k = l with probability (1 − κ)κ l for κ ∈ (0, 1). We call κ the staleness rate. Note that if κ is larger, then there are a longer delay. Besides, the expectation of the random staleness τ k is 1 1−k , so we call 1 1−k the expected staleness. By introducing when the learning rate η is small, (θ k , y k ) can be approximated by time discretizations of a continuous time stochastic process , and Σ is the covariance matrix conditioned on τ k , which is assumed to be a constant. We first formally derive the partial differential equation for the probability density function ψ(t, θ, y) of (Θ t , Y t ). For any compactly supported C ∞ function φ(θ t , y t ), by Itô's formula, Taking expectation of this equation and integrating over [t, t + h] leads to which further gives, Integrating by parts and letting h → 0 results in which is true for any test function. Therefore, the PDF ψ(t, θ, y) satisfies In what follows, we consider the case where ∇f is a perturbed linear function, A further change-of-variable of

Main results and proof sketch
When ε = 0, the steady state M (x, v) of (2.4), However, for general f (θ), unfortunately there is no explicit form of the steady state. By denoting F (x, v) as the steady state of (2.4), the weighted fluctuation function satisfies the following equation, 3) The above equation (3.2) is typically called the microscopic equation in the literature. It is also convenient for the forthcoming analysis to define the inner product ·, · and the norm · * as In addition, · 2 is the standard L 2 norm with respect to the Lebesgue measure.
Under the above Gaussian measure M , the following Poincare inequality holds The following key assumption ensures various bounds of the perturbation ε(θ).
There exists a small constant ǫ 0 > 0, such that, The following theorem states an exponential decay bound for the fluctuation h.
(3.6) More specifically How the learning rate and staleness affect the convergence rate? When the perturbation ǫ 0 is small, the decay rate is dominated by e −2µt . By the definition of δ t , one has t = kδ t = k η(1 − κ) with k the number of steps, η the learning rate and κ the staleness rate. Inserting the definition of γ = ((1 − κ)/η) into (3.6), the dominated decay rate e −2µt can also be written as, (3.7) From the above discussion, we make two observations: -The learning rate should not be smaller than 1 . For a fixed staleness rate κ, when the learning rate is larger than the threshold 1 4ω 2 0 (1 − κ), the convergence rate is a constant only depending on (1 − κ). While the learning rate is smaller than this threshold, the convergence rate will become slower as the learning rate becomes smaller.
-Longer delays result in slower convergence rate. For a fixed learning rate, the optimal decay rate e −2(1−κ)k only relates to the staleness of the system. If the system has more delayed readings from the local workers, i.e., (1 − κ) is smaller, then the convergence rate is slower.
All the above discussion is based on the assumption that η is small enough so that the SME-ASGD is a good approximation for ASGD. In other words, we assume ω 0 is large here, hence the threshold 1 Remark 3.4. When is ASGD more efficient than SGD? Assume we have m local workers and the learning rate is larger than the threshold η > 1 4ω 2 0 (1 − κ). When the perturbation ǫ 0 is small, for single batch SGD, the decay rate is e −2k after k steps, while for ASGD, the decay rate is e −2(1−κ)k after calculating k gradients. Since now we have m local workers, for the same amount of time, the decay rate for ASGD becomes e −2(1−κ)mk . Therefore, as long as (1 − κ)m > 1, ASGD will be more efficient than SGD. Since the expectation of the random staleness τ k is 1 1−κ , in other words, when the number of local workers is larger than the expected staleness, then ASGD is more efficient than SGD.
The proof of the theorem is given in Section 4. The main ingredient of the proof is the following Lyapunov functional H(t), where C,Ĉ are constants to be determined later. Note that, The first two terms can be estimated with an energy estimation given in Lemma 4.2 of ∇ x (3.2), ∇ v (3.2), while the estimation of the last term is given in Lemma 4.3. Combining the result in Lemmas 4.2 and 4.3 leads to, Finally, the exponential decay of h(t) 2 * can be derived from this inequality and the relationship between H(t) and h(t) 2 .

Proof of Theorem 3.2
The following proposition summarizes a few equalities and inequalities, which will be used frequently in the proof of the main theorem. The proofs are provided in Appendix A.
The following lemma is the energy estimation of ∇ x (3.2) and ∇ v (3.2).
Proof. After taking ∇ x and ∇ v to (3.2), multiplying them with ∇ x hM and ∇ v hM respectively, and integrating over dxdv, one obtains By invoking Proposition 4.1/(a), the second term of the LHS of each equation vanishes. Multiplying these two equations with 1 and C respectively and adding them together gives rise to After applying Proposition 4.1/(b),(d),(e), one obtains Proof.
Taking ∇ x and ∇ v to (3.2), multiplying them by ∇ v hM and ∇ x hM respectively, and integrating over dxdv, one obtains From Proposition 4.1/(a), the sum of the second terms on the LHS of both equations vanishes. Applying Proposition 4.1/(b) to the first term on the RHS of both equations combine them into a single term. Finally, summing the above two equations and applying Proposition 4.1/(f) to the last terms leads to The proof of Theorem 3.2 By combining the results in Lemma 4.2 and Lemma 4.3, one concludes that where Note that K can be decomposed as, (4.6) By invoking Lemma 4.3 in [2], we know that there exists a positive definite matrix P such that, The value of µ, C, andĈ can be separated into three cases.
Inserting K ≥ 2µP and using the fact that we can bound the second term in (4.4) from below by 2µH(t). By the positive definiteness of P , the third term is always positive. Therefore, The RHS is less than 0 for all ∇ x h, which implies that as long as ǫ 0 is sufficiently small one has for ǫ = 11 + 11C + 15Ĉ ǫ 0 C 2 2 max{1,C} C−Ĉ 2 . By integrating (4.8) over time and applying Grownwall's inequality to it, we obtain By the Poincare inequality (3.5) and the positive definiteness of P , one can bound H(t) from below by h 2 * up to a constant, Therefore, we can conclude h(t) 2

Appendices
A The proof of Proposition 4.1 Proof. (a) The first equation can be proved via integration by parts, The second equation is directly followed by T h, h * = − T h, h * .