Harnessing Smoothness to Accelerate Distributed Optimization

I Introduction

using local communication and local computation. The local communication is defined through an undirected communication graph $\mathcal{G}=(V,E)$, where the nodes $V=\mathcal{N}$ and the edges $E\subset V\times V$. Agent $i$ and $j$ can send information to each other if and only if $i$ and $j$ are connected in graph $\mathcal{G}$. The local computation means that each agent can only make his decision based on the local function $f_{i}$ and the information obtained from his neighbors.

This problem has recently received much attention and has found various applications in multi-agent control, distributed state estimation over sensor networks, large scale computation in machine/statistical learning , etc. As a concrete example, in the setting of distributed statistical learning, $x$ is the parameter to infer, and $f_{i}$ is the empirical loss function of the local dataset of agent $i$. Then minimizing $f$ means empirical loss minimization that uses datasets of all the agents.

The early work of this problem can be found in . Recently, (see also ) proposes a consensus-based distributed (sub)gradient descent (DGD) method where each agent performs a consensus step and then a descent step along the local (sub)gradient direction of $f_{i}$. Reference applies a similar idea to develop a distributed dual averaging algorithm. Extensions of these work have been proposed that deal with various realistic conditions, such as stochastic subgradient errors , directed or random communication graphs , linear scaling in network size , heterogeneous local constraints . Overall speaking, these DGD (or DGD-like) algorithms are designated for nonsmooth functions and they achieve the same convergence speed $O(\frac{\log t}{\sqrt{t}})$ as centralized subgradient descent. They can also be applied to smooth functions, but when doing so they either do not guarantee exact convergence when using a constant step size , or have a convergence rate of at most $\Omega(\frac{1}{t^{2/3}})$ when using a diminishing step size , slower than the normal Centralized Gradient Descent (CGD) method’s $O(\frac{1}{t})$. Therefore, DGD does not fully exploit the function smoothness and has a slower convergence rate compared with CGD. In fact, we prove in this paper that for strongly convex and smooth functions, it is impossible for DGD-like algorithms to achieve the same linear convergence rate as CGD (Theorem 6). Alternatively, suggest that it is possible to achieve faster convergence for smooth functions, by performing multiple consensus steps after each gradient evaluation. However, it places a larger communication burden. These drawbacks pose the need for distributed algorithms that effectively harness the smoothness to achieve faster convergence, using only one communication step per gradient evaluation iteration.

In this paper, we propose a distributed algorithm that can effectively harness the smoothness, and achieve a convergence rate that matches CGD, using only one communication step per gradient evaluation. Specifically, our algorithm achieves a $O(\frac{1}{t})$ rate for smooth and convex functions (Theorem 3), and a linear convergence rate ($O(\gamma^{t})$ for some $\gamma\in(0,1)$) for smooth and strongly convex functions (Theorem 1).A recent paper also achieves similar convergence rate results using a different algorithm. A detailed comparison between our algorithm and will be given in Section III-C. The convergence rates match the convergence rates of CGD, but with worse constants due to the distributed nature of the problem. Our algorithm is a combination of gradient descent and a novel gradient estimation scheme that utilizes history information to achieve fast and accurate estimation of the average gradient. To show the necessity of history information, we also prove that it is impossible for a class of distributed algorithms like DGD to achieve a linear convergence rate without using history information even if we restrict the class of objective functions to be strongly convex and smooth (Theorem 6).

Moreover, our scheme can be cast as a general method for obtaining distributed versions of many first-order optimization algorithms, like Nesterov gradient descent . We expect the distributed algorithm obtained in this way will have a similar convergence rate as its centralized counterpart. Some preliminary results on applying the scheme to Nesterov gradient descent can be found in our recent work .

Besides that studies an algorithm with similar performance, we note that variants of the algorithm in this paper have appeared in a few recent work, but these work has different focus compared to ours. Reference focuses on uncoordinated step sizes. It proves the convergence of the algorithm but does not provide convergence rate results. Reference focus on (possibly) nonconvex objective functions and thus have different step size rules and convergence results compared to ours. More recently, prove a linear convergence rate of the same algorithm for strongly convex and smooth functions, with focusing on time-varying graphs and focusing on uncoordinated step sizes. At last, and have studied a variant of the algorithm for directed graphs. To the best of our knowledge, our work is the first to study the $O(\frac{1}{t})$ convergence rate of the algorithm without the strongly convex assumption (with only the convex and smooth assumption). Also, our way of proving the linear convergence rate is inherently different from that of .

At last, we would like to emphasize that the focus of this paper is the consensus-based, first-order distributed algorithms. We note that there are other types of distributed optimization algorithms, like second-order distributed algorithms , Alternating Direction Method of Multipliers (ADMM) etc. However these methods are inherently different from the algorithms studied in this paper, and thus are not discussed in this paper.

The rest of the paper is organized as follows. Section II formally defines the problem and presents our algorithm and results. Section III reviews previous methods, introduces an impossibility result and motivates our approach. Section IV proves the convergence of our algorithm. Lastly, Section V provides numerical simulations and Section VI concludes the paper.

II Problem and Algorithm

using local communication and local computation. The local communication is defined through an undirected and connected communication graph $\mathcal{G}=(V,E)$, where the nodes $V=\mathcal{N}$ and edges $E\subset V\times V$. Agent $i$ and $j$ can send information to each other if and only if $(i,j)\in E$. The local computation means that each agent can only make its decision based on the local function $f_{i}$ and the information obtained from its neighbors.

Throughout the paper, we assume that the set of minimizers of $f$ is non-empty. We denote $x^{*}$ as one of the minimizers and $f^{*}$ as the minimal value. We will study the case where each $f_{i}$ is convex and $\beta$-smooth (Assumption 1) and also the case where each $f_{i}$ is in addition $\alpha$-strongly convex (Assumption 2). The definition of $\beta$-smooth and $\alpha$-strongly convex are given in Definition 1 and 2 respectively.

$\forall i,f_{i}$ is convex and $\beta$-smooth.

$\forall i$, $f_{i}$ is $\alpha$-strongly convex.

Since $f$ is an average of the $f_{i}$’s, Assumption 1 also implies $f$ is convex and $\beta$-smooth, and Assumption 2 also implies $f$ is $\alpha$-strongly convex.

II-B Algorithm

For any $(i,j)\in E$, we have $w_{ij}>0$. For any $i\in\mathcal{N}$, we have $w_{ii}>0$. For other $(i,j)$, we have $w_{ij}=0$.

Matrix $W$ is doubly stochastic, i.e. $\sum_{i^{\prime}}w_{i^{\prime}j}=\sum_{j^{\prime}}w_{ij^{\prime}}=1$ for all $i,j\in\mathcal{N}$.

where $[w_{ij}]_{n\times n}$ are the consensus weights and $\eta>0$ is a fixed step size. Because $w_{ij}=0$ when $(i,j)\notin E$, each node $i$ only needs to send $x_{i}(t)$ and $s_{i}(t)$ to its neighbors. Therefore, the algorithm can be operated in a fully distributed fashion, with only local communication. Note that the two consensus weight matrices in step (2) and (3) can be chosen differently. We use the same matrix $W$ to carry out our analysis for the purpose of easy exposition.

The update equation (2) is similar to the algorithm in (see also (5) in Section III), except that the gradient is replaced with $s_{i}(t)$ which follows the update rule (3). In Section III and IV-B, we will discuss the motivation and the intuition behind this algorithm.

The key of our algorithm is the gradient estimation scheme (3) and it can be used to obtain distributed versions of many other gradient-based algorithms. For example, suppose a centralized algorithm is in the following form,

where $x(t)$ is the state, $\mathcal{F}_{t}$ is the update equation. We can write down a distributed algorithm as

Our conjecture is that for a broad range of centralized algorithms, the distributed algorithm obtained as above will have a similar convergence rate as the centralized one. Our ongoing work includes applying the above scheme to other centralized algorithms like Nesterov gradient method. Some of our preliminary results are in .

II-C Convergence of the Algorithm

To state the convergence results, we need to define the following average sequences.

Under the smooth and strongly convex assumptions (Assumption 1 and 2), when $\eta$ is such that the matrix

has spectral radius $\rho(G(\eta))<1$, then $\forall i$, $\|\bar{x}(t)-x^{*}\|$ (distance to the optimizer), $\|x_{i}(t)-\bar{x}(t)\|$ (consensus error), and $\|s_{i}(t)-g(t)\|$ (gradient estimation error) are all decaying with rate $O(\rho(G(\eta))^{t})$. Moreover, we have $f(x_{i}(t))-f^{*}$ (objective error) is decaying with rate $O(\rho(G(\eta))^{2t})$.

The following lemma provides an explicit upper bound on the convergence rate $\rho(G(\eta))$.

When $0<\eta<\frac{1}{\beta},$ we have $\rho(G(\eta))\leq\max(1-\frac{\alpha\eta}{2},\sigma+5\sqrt{\eta\beta}\sqrt{\frac{\beta}{\alpha}})$. Specifically, when $\eta=\frac{\alpha}{\beta^{2}}(\frac{1-\sigma}{6})^{2}$, $\rho(G(\eta))\leq 1-\frac{1}{2}(\frac{\alpha}{\beta}\frac{1-\sigma}{6})^{2}<1$.

If we drop the strongly convex assumption, we have the following result.

Under the smooth assumption (Assumption 1), when $0<\eta\leq\frac{(1-\sigma)^{2}}{160\beta}$, the following is true.

where $\hat{x}_{i}(t+1)$ is the running average of agent $i$ defined to be $\hat{x}_{i}(t+1)=\frac{1}{t+1}\sum_{k=0}^{t}x_{i}(k+1)$.

Since the objective error is nonnegative, we have for each $i\in\mathcal{N}$, $f(\hat{x}_{i}(t+1))-f^{*}\leq n\times\frac{1}{n}\sum_{j=1}^{n}[f(\hat{x}_{j}(t+1))-f^{*}]$. This leads to the following simple corollary of Theorem 3 regarding the individual objective errors $f(\hat{x}_{i}(t+1))-f^{*}$.

Under the conditions of Theorem 3, we have $\forall i=1,\ldots,n$,

Our algorithm preserves the convergence rate of CGD, in the sense that it has a linear convergence rate when each $f_{i}$ is strongly convex and smooth, and a convergence rate of $O(\frac{1}{t})$ when each $f_{i}$ is just smooth. However, we note that the linear convergence rate constant $\rho(G(\eta))$ is usually worse than CGD; and moreover, in both cases, our algorithm has a worse constant in the big $O$ terms. Moreover, compared to CGD, the step size rules depend on the consensus matrix $W$ (Lemma 2 and Theorem 3).

By Lemma 2 and Theorem 3(a), the convergence rate of our algorithm does not explicitly depend on $n$ but depends on $n$ through the second largest singular value $\sigma$ of the consensus matrix $W$. In Theorem 3(a) we consider the quantity $\frac{1}{\sqrt{n}}\|s(0)-\mathbf{1}g(0)\|$ (and similarly $\frac{1}{\sqrt{n}}\|x(0)-\mathbf{1}\bar{x}(0)\|$) to be not explicitly dependent on $n$, since this quantity equals $\sqrt{\frac{1}{n}\sum_{i=1}^{n}\|s_{i}(0)-g(0)\|^{2}}$ and is essentially an average of some initial condition across the agents. The relationship between $\sigma$ and $n$ is studied in for a general class of $W$, and in Lemma 4 of when $W$ is selected using the Lapalcian method (to be introduced in Section V-A).

In Lemma 2 and Theorem 3, the step sizes depend on the parameter $\sigma$ which requires global knowledge of graph $\mathcal{G}$ to compute. To make the algorithm fully distributed, we now relax the step size rules such that each agent only needs to know an upper bound $U$ on the number of agents $n$, i.e. $U\geq n$. To achieve this, we require each agent select the weights $W$ to be the lazy Metropolis matrix , i.e.

In (4), $d_{i}$ denotes the degree of agent $i$ in graph $\mathcal{G}$, and $N_{i}$ denotes the set of neighbors of agent $i$. Note that the $W$ in (4) can be computed distributedly, since each agent only needs to know its own degree and its neighbor’s degree to compute $w_{ij}$. Moreover, Lemma 2.1 in shows that if $W$ is selected according to (4), $\sigma<1-\frac{1}{71n^{2}}\leq 1-\frac{1}{71U^{2}}$. Combining this with our original step size rules in Lemma 2 and Theorem 3, we have the following corollary in which the step size rules are relaxed to only depend on $U$.

Under the assumptions of Theorem 1, if $W$ is chosen according to (4) and $\eta=\frac{\alpha}{\beta^{2}}(\frac{1}{426U^{2}})^{2}$, then $\rho(G(\eta))\leq 1-\frac{1}{2}(\frac{\alpha}{\beta}\frac{1}{426U^{2}})^{2}$ and the convergence results in Theorem 1 hold.

Under the assumptions of Theorem 3, if $W$ is chosen according to (4) and $0<\eta\leq\frac{1}{160\beta(71U^{2})^{2}}$, then the statements in Theorem 3 and Corollary 4 hold.

III Algorithm development: Motivation

In this section, we will briefly review distributed first-order optimization algorithms that are related to our algorithm and discuss their limitations which motivates our algorithm development. In particular, we will formally provide an impossibility result regarding the limitations. Lastly we will discuss the literature that motivates the idea of harnessing the smoothness from history information.

To solve the distributed optimization problem (1), consensus-based DGD (Distributed (sub)gradient descent) methods have been developed, e.g., , that combine a consensus algorithm and a first order optimization algorithm. For a review of consensus algorithms and first order optimization algorithms, we refer to references and respectively. For the sake of concrete discussion, we focus on the algorithm in , where each agent $i$ keeps an local estimate of the solution to (1), $x_{i}(t)$ and it updates $x_{i}(t)$ according to,

where $g_{i}(t)\in\partial f_{i}(x_{i}(t))$ is a subgradient of $f_{i}$ at $x_{i}(t)$ ($f_{i}$ is possibly nonsmooth), and $\eta_{t}$ is the step size, and $w_{ij}$ are the consensus weights. Algorithm (5) is essentially performing a consensus step followed by a standard subgradient descent along the local subgradient direction $g_{i}(t)$. Results in show that the running best of the objective $f(x_{i}(t))$ converges to the minimum $f^{*}$ with rate $O(\frac{\log t}{\sqrt{t}})$ if using a diminishing step size $\eta_{t}=\Theta(\frac{1}{\sqrt{t}})$. This is the same rate as the centralized subgradient descent algorithm up to a $\log t$ factor.

When the $f_{i}$’s are smooth, the subgradient $g_{i}(t)$ will equal the gradient $\nabla f_{i}(x_{i}(t))$. However, as shown in , even in this case the convergence rate of (5) can not be better than $\Omega(\frac{1}{t^{2/3}})$ when using a vanishing step size. In contrast, the CGD (centralized gradient descent) method,

converges to the optimum with rate $O(\frac{1}{t})$ if the stepsize $\eta$ is a small enough constant. Moreover, when $f$ is further strongly convex, CGD (6) converges to the optimal solution with a linear rate. If a fixed step size $\eta$ is used in DGD (5), though the algorithm runs faster, the method only converges to a neighborhood of the optimizer . This is because even if $x_{i}(t)=x^{*}$ (the optimal solution), $\nabla f_{i}(x_{i}(t))$ is not necessarily zero.

To fix this problem of non-convergence, it has been proposed to use multiple consensus steps after each gradient descent . One example is provided as follows:

For each gradient descent step (LABEL:eq:dist_grad_mult_1), after $c_{t}$ consensus steps ($c_{t}=\Theta(\log t)$ in , and $c_{t}=\Theta(t)$ in ), the agents’ estimates $x_{i}(t+1)$ are sufficiently averaged, and it is as if each agent has performed a descent along the average gradient $\frac{1}{n}\sum_{i}\nabla f_{i}(x_{i}(t))$. As a result, algorithm (7) addresses the non-convergence problem mentioned above. However, it places a large communication burden on the agents: the further the algorithm proceeds, the more consensus steps after each gradient step are required. In addition, even if the algorithm already reaches the optimizer $x_{i}(t)=x^{*}$, because of (LABEL:eq:dist_grad_mult_1) and because $\nabla f_{i}(x^{*})$ might be non-zero, $y_{i}(t,0)$ will deviate from the optimizer, and then a large number of consensus steps in (LABEL:eq:dist_grad_mult_2) are needed to average out the deviation. All these drawbacks pose the need for alternative distributed algorithms that effectively harness the smoothness to achieve faster convergence, using only one (or a constant number of) communication step(s) per gradient evaluation.

III-B An Impossibility Result

To compliment the preceding discussion, here we provide an impossibility result for a class of distributed first-order algorithms which include algorithms like (5). We use notation $-i$ to denote the set $\mathcal{N}/\{i\}$. The class of algorithms we consider obey the following updating rule, $\forall i\in\mathcal{N}$

Here both $\mathcal{H}$ and $\mathcal{F}$ denote general functions with the following properties. Function $\mathcal{H}$ captures how agents use their neighbors’ information, and $\mathcal{H}$ is assumed to be a continuous function of the component $x_{j}(t)$, $j\in\mathcal{N}$. Note that $\mathcal{H}$ can be interpreted as the consensus step. Function $\mathcal{F}$ is a function of $\mathcal{H}$ and the scaled gradient direction $\eta_{t}\nabla f_{i}(x_{i}(t-1))$, and $\mathcal{F}(\cdot,\cdot)$ is assumed to be $L$-Lipschitz continuous in its second variable (when fixing the first variable). Note that $\mathcal{F}$ can be interpreted as a first-order update rule, such as the (projected) gradient descent, mirror descent, etc. Parameter $\eta_{t}$ can be considered as the step size, and we assume it has a limit $\eta^{*}$ as $t\rightarrow\infty$. We will show that for strongly convex and smooth cost functions, any algorithm belonging to this class will not have a linear convergence rate, which is in contrast to the linear convergence of the centralized methods.

In the rest of the proof we focus on a restricted scenario in which $f_{1}=f_{2}$ and $x_{1}(0)=x_{2}(0)$. In this scenario, we can easily check $x_{1}(t)$ always equals $x_{2}(t)$ by induction. Firstly $x_{1}(0)=x_{2}(0)$. Then if assuming $x_{1}(t)=x_{2}(t)$, using $f_{1}=f_{2}$ we have $x_{1}(t+1)=\mathcal{F}(\mathcal{H}(x_{1}(t),x_{2}(t)),\eta_{t}\nabla f_{1}(x_{1}(t)))=\mathcal{F}(\mathcal{H}(x_{2}(t),x_{1}(t)),\eta_{t}\nabla f_{2}(x_{2}(t)))=x_{2}(t+1)$. In light of this, we introduce notation $x(t)\triangleq x_{1}(t)=x_{2}(t)$ and also $f\triangleq f_{1}=f_{2}$. Using the new notation, the update equation for $x(t)$ becomes

Now we are ready to prove the Theorem. Notice that for any objective function $f$, if we start from $x(0)\neq x^{*}$ ($x^{*}$ is the unique minimizer of $f$), then the generated sequence $x(t)$ satisfies

III-C Harnessing Smoothness via History Information

Motivated by the previous discussion and the impossibility result, we seek for alternative methods to exploit smoothness to develop faster distributed algorithms. Firstly we note that one major reason for the slow convergence of DGD is the decreasing step size $\eta_{t}$. This motivates us to use a constant step size $\eta$ in our algorithm (2). But we have discussed that a constant $\eta$ will lead to optimization error due to the fact that $\nabla f_{i}(x_{i}(t))$ could be very different from the average gradient $g(t)=\frac{1}{n}\sum_{i}\nabla f_{i}(x_{i}(t))$. However, because of smoothness, $\nabla f_{i}(x_{i}(t+1))$ and $\nabla f_{i}(x_{i}(t))$ would be close (as well as $g(t+1)$ and $g(t)$) if $x_{i}(t+1)$ and $x_{i}(t)$ are close, which is exactly the case when the algorithm is coming close to the minimizer $x^{*}$. This motivates the second step of our algorithm (3), using history information to get an accurate estimation of the average gradient $g(t)$ which is a better descent direction than $\nabla f_{i}(x_{i}(t))$. Similar ideas of using history information trace back to , in which the previous gradient is used to narrow down the possible values of the current gradient to reduce communication complexity for a two-agent optimization problem.

A recent paper proposes an algorithm that achieves convergence results similar to our algorithm. The algorithm in can be interpreted as adding an integration type correction term to (5) while using a fixed step size. This correction term also involves history information in a certain way, which is consistent with our impossibility result. Our algorithm and are similar in the sense that they are both dynamical systems with order $2nN$, and take difference of gradients as inputs. But they are different in the sense that they are dynamical systems with different parameters, which result in different behaviors. The differences between our algorithm and are summarized below. Firstly, in our algorithm, the state $s_{i}(t)$ serves as an estimator of the average gradient and can be used as a stopping criterion, like in many centralized methods where the norm of gradients is used as a stopping criterion. Secondly, in our algorithm, the update rule can be clearly separated into two parts, the first part being the update corresponding to centralized gradient descent, and the second part being the gradient estimator. With the separation, our algorithm can be easily extended to other centralized methods (see also Remark 1). Thirdly, the two consensus matrices in need to be symmetric and also satisfy a predefined spectral relationship, whereas our algorithm has a looser requirement on the consensus matrices. Fourthly, without assuming the strong convexity, achieves a $O(\frac{1}{t})$ convergence rate in terms of the optimality residuals, which can be loosely defined as $\|\nabla f(x_{i}(t))\|^{2}$ and $\|x_{i}(t)-\bar{x}(t)\|^{2}$. Our algorithm not only achieves $O(\frac{1}{t})$ for the optimality residuals, but also achieves $O(\frac{1}{t})$ in terms of the objective error $f(\hat{x}_{i}(t))-f^{*}$, which is a more direct measure of optimality. At last, one downside of our current results is that gives a step size bound that only depends on $\beta$, whereas our step size bounds also depend on $W$ (Lemma 2 and Theorem 3).

IV Convergence Analysis

In this section, we prove our main convergence results Theorem 1, Lemma 2, and Theorem 3.

We can compactly write the update rule in (2) and (3) as

and also $s(0)=\nabla(0)$. We start by introducing two straightforward lemmas. Lemma 7 derives update equations that govern the average sequence $\bar{x}(t)$ and $\bar{s}(t)$. Lemma 8 gives several auxiliary inequalities. Lemma 7 is a direct consequence of the fact $W$ is doubly stochastic and $s(0)=\nabla(0)$, and Lemma 8 is a direct consequence of the $\beta$-smoothness of $f_{i}$. The proofs of the two lemmas are postponed to Appendix--A.

$\bar{s}(t+1)=\bar{s}(t)+g(t+1)-g(t)=g(t+1)$

$\bar{x}(t+1)=\bar{x}(t)-\eta\bar{s}(t)=\bar{x}(t)-\eta g(t)$

Under Assumption 1, the following inequalities hold.

$\|\nabla(t)-\nabla(t-1)\|\leq\beta\|x(t)-x(t-1)\|$

$\|g(t)-g(t-1)\|\leq\beta\frac{1}{\sqrt{n}}\|x(t)-x(t-1)\|$

$\|g(t)-h(t)\|\leq\beta\frac{1}{\sqrt{n}}\|x(t)-\mathbf{1}\bar{x}(t)\|$

IV-B Why the Algorithm Works: An Intuitive Explanation

We provide our intuition that partially explains why the algorithm (9) can achieve a linear convergence rate for strongly convex and smooth functions. In fact we can prove the following proposition.

Assuming $\|s(t)-\mathbf{1}g(t)\|$ decays at a linear rate, then $\|x(t)-\mathbf{1}x^{*}\|$ also decays at a linear rate.

Assuming $\|x(t)-\mathbf{1}x^{*}\|$ decays at a linear rate, then $\|s(t)-\mathbf{1}g(t)\|$ also decays at a linear rate.

The proof of the above proposition is postponed to Appendix--B. The above proposition tells that the linear decaying rates of the gradient estimation error $\|s(t)-\mathbf{1}g(t)\|$ and the distance to optimizer $\|x(t)-\mathbf{1}x^{*}\|$ imply each other. Though this circular argument does not prove the linear convergence rate of our algorithm, it illustrates how the algorithm works: the gradient descent step (LABEL:eq:algo_xs_1) and the gradient estimation step (LABEL:eq:algo_xs_2) facilitate each other to converge fast in a reciprocal manner. This mutual dependence is distinct from many previous methods, where one usually bounds the consensus error at first, and then use the consensus error to bound the objective error, and there is no mutual dependence between the two. In the next two subsections, we will rigorously prove the convergence.

IV-C Convergence Analysis: Strongly Convex

We start by introducing a lemma that is adapted from standard optimization literature, e.g. . Lemma 10 states that if we perform a gradient descent step with a fixed step size for a strongly convex and smooth function, then the distance to optimizer shrinks by at least a fixed ratio. For completeness we give a proof of Lemma 10 in Appendix--C.

where $\lambda=\max(|1-\eta\alpha|,|1-\eta\beta|)$.

Proof of Theorem 1: Our strategy is to bound $\|s(k)-\mathbf{1}g(k)\|$, $\|x(k)-\mathbf{1}\bar{x}(k)\|$, and $\|\bar{x}(k)-x^{*}\|$ in terms of linear combinations of their past values, and in this way obtain a linear system inequality, which will imply linear convergence.

Step 1: Bound $\|s(k)-\mathbf{1}g(k)\|$. By the update rule (LABEL:eq:algo_xs_2),

Taking the norm, noticing that the column-wise average of $s(k-1)$ is just $g(k-1)$ by Lemma 7(a), and using the averaging property of the consensus matrix $W$, we have

Combining this with (10) and using Lemma 8 (a), we get

Step 2: Bound $\|x(k)-\mathbf{1}\bar{x}(k)\|$. Considering update rule (LABEL:eq:algo_xs_1) and using Lemma 7(b) and the property of $W$, we have

Step 3: Bound $\|\bar{x}(k)-x^{*}\|$. Notice by Lemma 7(b), the update rule for $\bar{x}(k)$ is

Since the gradient of $f$ at $\bar{x}(k-1)$ is $h(k-1)$, therefore, by Lemma 10 and Lemma 8(c), we have

where $\lambda=\max(|1-\eta\alpha|,|1-\eta\beta|)$.

Step 4: Bound $\|x(k)-x(k-1)\|$. Notice that by Assumption 1,

Combining the above and Lemma 8(c), we have

Step 5: Derive a linear system inequality. We combine the previous four steps into a big linear system inequality. Plugging (14) into (11), we have

where ‘$\leq$’ means element wise less than or equal to. Since $z(k)$ and $G(\eta)$ have nonnegative entries, we can actually expand (26) recursively, and get

Since $G(\eta)$ has nonnegative entries and $G(\eta)^{2}$ has all positive entries, by Theorem 8.5.1 and 8.5.2 of , each entry of $G(\eta)^{k}$ will be $O(\rho(G(\eta))^{k})$. Hence, the three entries of $z(k)$, $\|s(k)-\mathbf{1}g(k)\|$, $\|x(k)-\mathbf{1}\bar{x}(k)\|$, and $\|\bar{x}(k)-x^{*}\|$ will converge to in the order of $\rho(G(\eta))^{k}$. By $\beta$-smoothness of $f$, we have

Since $\nabla f(x^{*})=0$, the above implies that $f(\bar{x}(k))-f^{*}=O(\rho(G(\eta))^{2k})$. Again by $\beta$-smoothness and Cauchy-Schwarz inequality,

Since $\|\nabla f(\bar{x}(k))\|=\|\nabla f(\bar{x}(k))-\nabla f(x^{*})\|\leq\beta\|\bar{x}(k)-x^{*}\|=O(\rho(G(\eta))^{k})$, and $\|x_{i}(k)-\bar{x}(k)\|\leq\|x(k)-\mathbf{1}\bar{x}(k)\|=O(\rho(G(\eta))^{k})$, the above inequality implies that $f(x_{i}(k))-f(\bar{x}(k))=O(\rho(G(\eta))^{2k})$. This further leads to $f(x_{i}(k))-f^{*}=f(x_{i}(k))-f(\bar{x}(k))+f(\bar{x}(k))-f^{*}=O(\rho(G(\eta))^{2k})$. $\Box$

Proof of Lemma 2: Since $\eta<\frac{1}{\beta}$, it is easy to check $1-\alpha\eta\geq 1-\beta\eta>0$, and hence $\lambda=1-\alpha\eta$. We first write down the charasteristic polynomial $p(\zeta)$ of $G(\eta)$,

where $p_{0}(\zeta)=(\zeta-\sigma-\eta\beta)(\zeta-\sigma)-\eta\beta(\eta\beta+2)$. The two roots of $p_{0}$, $\zeta_{1}$ and $\zeta_{2}$ are $\frac{2\sigma+\eta\beta\pm\sqrt{5\eta^{2}\beta^{2}+8\eta\beta}}{2}$. Since $0<\eta\beta<1$, both roots are real numbers less than $\sigma+3\sqrt{\eta\beta}$. This implies

Let $\zeta^{*}=\max(1-\frac{\alpha\eta}{2},\sigma+5\sqrt{\eta\beta}\sqrt{\frac{\beta}{\alpha}})>\sigma+3\sqrt{\eta\beta}$, then

Since $p(\zeta)$ is a strictly increasing function on $[\max(1-\alpha\eta,\sigma+3\sqrt{\eta\beta}),+\infty)$ (this interval includes $\zeta^{*}$), $p(\zeta)$ does not have real roots on $(\zeta^{*},\infty)$. Since $G(\eta)$ is a nonnegative matrix, by Perron-Frobenius Theorem (Page 503, Theorem 8.3.1 of ), $\rho(G(\eta))$ is an eigenvalue of $G(\eta)$. Hence $\rho(G(\eta))$ is a real root of $p(\zeta)$, so we have $\rho(G(\eta))\leq\zeta^{*}$. $\Box$

We now comment on how $\beta$-smoothness of $f_{i}$ is used in the proof of Theorem 1 and not used in the proof of DGD-like algorithms, e.g. , and how this difference would affect the convergence rates of the two algorithms. In DGD-like algorithms, (sub)gradients are usually assumed to be bounded. Whenever a (sub)gradient is encountered in the proof, it is replaced by its bound and the resulting inequalities usually involve many additive constant terms. To control the constant terms, a vanishing step size is required, which slows down the convergence. In the proof of Theorem 1, whenever gradients appear, they appear in the form of the difference of two gradients (like (10)). Therefore we can bound it using the $\beta$-smoothness assumption. The resulting inequalities (like (11)) do not involve constant terms, but linear combinations of some variables instead. After carefully arranging these inequalities, we can get a contraction inequality (26) and hence the linear convergence rate.

IV-D Convergence Analysis: Non-strongly Convex Case

Proof of Theorem 3: The proof will be divided into 4 steps. In step 1, we derive a linear system inequality (38) similar to (26), but this time with input. In step 2, we use the linear system inequality (38) to bound the consensus error. In step 3, we show that $g(t)$, is actually an inexact gradient of $f$ at $\bar{x}(t)$ with the inexactness being characterized by the consensus error. Therefore, the update equation for the average sequence $\bar{x}(t)$ (Lemma 7(b)) is essentially inexact gradient descent. In step 4, we apply the analysis method for CGD to the average sequence $\bar{x}(t)$ and show that the $O(\frac{1}{t})$ convergence rate is preserved in spite of the inexactness.

Step 1: A linear system inequality. We prove the following inequality,

It is easy to check that (11) and (12) (copied below as (39) and (40)) still holds if we remove the strongly convex assumption.

Combining the above and (40) yields (38).

where $A_{1}$, $A_{2}$ and $\theta$ are defined as follows.

To prove (43), we first notice that by (38), we have

Step 4: Follow the proof of CGD. Define $r_{k}=\|\bar{x}(k)-x^{*}\|^{2}$. Then

where in (a) we have used $\bar{x}(k+1)-\bar{x}(k)=-\eta g(k)$. In (b) we have used two inequalities. The first one is $\langle g(k),\bar{x}(k)-x^{*}\rangle\geq\hat{f}_{k}-f^{*}$ (by (45) with $\omega=x^{*}$), and the second one is

which follows from (46) (with $\omega=\bar{x}(k+1)$) and the fact $\bar{x}(k+1)-\bar{x}(k)=-\eta g(k)$. Summing up (47) for $k=0,\ldots,t$, we get

where in the second inequality we have used $\hat{f}_{k}\leq f(\bar{x}(k))$, which can be derived from (45) by letting $\omega=\bar{x}(k)$. Hence,

By Gershgorin Circle Theorem , this shows that $\rho(X)\leq\frac{3}{(1-\theta)^{2}}$. Since $\mu^{T}X\mu\leq\rho(X)\|\mu\|^{2}$, we get

Combining this with (49), and plugging in the value of $A_{2}$, we get

where in the last inequality, we have used

which follows from $\theta=(1+\sigma)/2$, and the step size rule $0<\eta\leq\frac{(1-\sigma)^{2}}{160\beta}$. Recall that $\hat{x}_{i}(t+1)=\frac{1}{t+1}\sum_{k=1}^{t+1}x_{i}(k)$, then by convexity of $f$ we have $f(\hat{x}_{i}(t+1))\leq\frac{1}{t+1}\sum_{k=0}^{t}f(x_{i}(k+1))$. Combining this with (51) leads to

which gives part (a) of the Theorem. For part (b), we consider the second inequality in (51). Notice the left hand side of (51) is nonnegative, and $\frac{10\beta\eta^{2}}{(1-\theta)^{2}}-\frac{\eta}{2}\leq-\frac{1}{4}\eta$ (by (52)). We have,

Also notice that $\sum_{k=0}^{t}\|x(k)-\mathbf{1}\bar{x}(k)\|^{2}\geq t\min_{0\leq k\leq t}\|x(k)-\mathbf{1}\bar{x}(k)\|^{2}$. Combining this with (53) leads to part (b). $\Box$

V Numerical Experiments

Case I and case II satisfy Assumption 1 and 2, while case III only satisfies Assumption 1. In case I and II, we plot the average objective error, i.e. $\frac{1}{n}\sum_{i}f(x_{i}(t))-f^{*}$. For case I and III, there are closed form expressions for $f^{*}$ and we compute $f^{*}$ using the closed form expressions. For case II, we compute $f^{*}$ using centralized gradient descent until the gradient reaches the smallest value (almost ) that MATLAB can handle. Case III is intended to test the sublinear convergence rate $\frac{1}{t}$ of the algorithm (Theorem 3), therefore in addition to the average objective error, we also plot $t\times(\frac{1}{n}\sum_{i}f(x_{i}(t))-f^{*})$ to check if the objective error decays as $O(\frac{1}{t})$. The results are shown in Figure 1, 2 and 3.

V-B Experiments with different graph sizes

As pointed out by Remark 3, the convergence rates of our algorithm depend on $\sigma$ (not directly on $n$). Therefore for graphs with different sizes $n$ but similar $\sigma$, our algorithm should have roughly the same convergence rate, and therefore is ‘scale-free’. This section will test this property through simulation. We choose random $3$-regular graphs with sizes $n=50,100,150,\ldots,500$. A $3$-regular graph is a graph in which each node is adjacent to $3$ other nodes. We generate the random $3$-regular graphs using the method in . To ensure the connectivity of the generated graphs, we discard the graphs that are not connected, which happen very rarely (see Theorem 2.10 of ). We obtain $W$ by the Laplacian method. It is known that with a high probability, a random regular graph is a regular expander graph (see Section 7.3.2 of ), and thus with a high probability, $\sigma$ is free of the size $n$ of the graph (see Corollary 1(d) and Lemma 4 of ). Therefore, our algorithm should be ‘scale-free’ for those graphs. We choose the objective functions using the same method as Case I in the previous subsection. For each graph size, we list the parameter $\sigma$ along with the strongly-convex parameter $\alpha$, the smooth parameter $\beta$ in Table I. Each element of $x_{i}(0)$ is drawn from i.i.d. Gaussion distribution with mean and variance $25$. We plot the number of iterations it take for the average objective error ($\frac{1}{n}\sum_{i}f(x_{i}(t))-f^{*}$) to reach a predefined error level $1\times 10^{-10}$ versus the graph size $n$. The results are shown in Figure 4.

VI Conclusion

In this paper, we have proposed a method that can effectively harness smoothness to speed up distributed optimization. The method features a gradient estimation scheme. It achieves a $O(\frac{1}{t})$ convergence rate when the objective function is convex and smooth, and achieves a linear convergence rate when the function is strongly convex and smooth. Both rates are comparable to the centralized gradient methods except for some constants. Future work includes applying the gradient estimation scheme to other first order optimization algorithms, like Nesterov gradient descent.

References

-A Proof of Lemma 7 and Lemma 8

Proof of Lemma 7: Since $W$ is doubly stochastic, we have $\mathbf{1}^{T}W=\mathbf{1}^{T}$. Therefore,

Do this recursively, we can get $\bar{s}(t+1)=\bar{s}(0)+g(t+1)-g(0)$. Since $s(0)=\nabla(0)$, we have $\bar{s}(0)=g(0)$. This finishes the proof. $\Box$

-B Proof of Proposition 9

Proof of Proposition 9: On one hand, assume the gradient estimation error $\|s(t)-\mathbf{1}g(t)\|$ decays at a linear rate, i.e. $\|s(t)-\mathbf{1}g(t)\|\leq C_{1}\kappa_{1}^{t}$ for some constant $C_{1}>0$ and $\kappa_{1}\in(0,1)$. Then, the consensus error satisfy

where in the first inequality we have used Lemma 7(b), and in the second inequality we have used the averaging property of $W$. Therefore, the consensus error also decays at a linear rate. Then, by Lemma 8 (c), $\|g(t)-h(t)\|$ also decays at a linear rate, i.e. we have $\|g(t)-h(t)\|\leq C_{2}\kappa_{2}^{t}$ for some $C_{2}>0$ and $\kappa_{2}\in(0,1)$. By Lemma 7(b), $\bar{x}(t)=\bar{x}(t-1)-\eta h(t-1)-\eta(g(t-1)-h(t-1))$. Since $h(t-1)=\nabla f(\bar{x}(t-1))$, $\bar{x}(t-1)-\eta h(t-1)$ is a standard gradient step for function $f$. Since $f$ is strongly convex and smooth, a standard gradient descent step shrinks the distance to the minimizer by a least a fixed ratio (see Lemma 10), hence we have

Therefore $\|\bar{x}(t)-x^{*}\|$, the distance of the average $\bar{x}(t)$ to the minimizer decays at a linear rate. Combining this with the fact that the consensus error $\|x(t)-\mathbf{1}\bar{x}(t)\|$ decays at a linear rate and using the triangle inequality, we have $\|x(t)-\mathbf{1}x^{*}\|$, the distance to the optimizer, decays at a linear rate.

On the other hand, assume $\|x(t)-\mathbf{1}x^{*}\|$ decays at a linear rate, then $\|x(t)-x(t-1)\|$ also decays at a linear rate, i.e. $\|x(t)-x(t-1)\|\leq C_{3}\kappa_{3}^{t-1}$ for some $C_{3}>0$ and $\kappa_{3}\in(0,1)$. Then,

where in the second inequality we have used Lemma 8(a)(b). Hence the gradient estimation error $\|s(t)-\mathbf{1}g(t)\|$ decays at a linear rate. $\Box$

-C Proof of Lemma 10

In the proof of Lemma 10 we will use the following result, which is the same as Lemma 3.11 of in which the proof can be found.

As a special case, let $y=x^{*}$ be the unique optimizer of $f$. Since $\nabla f(x^{*})=0$, we have

Proof of Lemma 10: If $0<\eta\leq\frac{2}{\alpha+\beta}$, then $\frac{2}{\eta}-\alpha\geq\beta$. Let $\alpha^{\prime}=\alpha$, $\beta^{\prime}=\frac{2}{\eta}-\alpha\geq\beta$, then $f$ is also $\alpha^{\prime}$-strongly convex and $\beta^{\prime}$-smooth. Then, we have

where the first inequality is due to Lemma 11 and the last equality is due to $|1-\alpha\eta|\geq|1-\beta\eta|$, which follows from $\alpha<\beta$ and $0<\eta\leq\frac{2}{\alpha+\beta}$. The case $\frac{2}{\beta}>\eta>\frac{2}{\alpha+\beta}$ follows from a similar argument (but with $\alpha^{\prime}=\frac{2}{\eta}-\beta$ and $\beta^{\prime}=\beta$) and the details are omitted. $\Box$

-D Derivation of (43)

with $\theta_{1}=\frac{2\sigma+\eta\beta-\sqrt{\eta^{2}\beta^{2}+8\eta\beta}}{2}$ and $\theta_{2}=\frac{2\sigma+\eta\beta+\sqrt{\eta^{2}\beta^{2}+8\eta\beta}}{2}$. Matrix $V$ and $V^{-1}$ are given by