Accelerated Distributed Nesterov Gradient Descent

I Introduction

using local communication and local computation. The local communication is defined through an undirected connected communication graph. In the past decade, this problem has received much attention and has found various applications in multi-agent systems, sensor networks, machine learning, etc .

Many distributed optimization algorithms have been developed based on different local computation schemes for individual agents. For instance, in Alternating Direction Method of Multipliers (ADMM) based distributed methods, e.g., , each agent needs to solve a sub-optimization problem at each iteration. Another example is the line of work in which each agent needs to use the dual gradient, i.e. gradient of the Fenchel conjugate of the local cost function. These methods assume that the sub-optimization or computation problem associated with ADMM or dual gradient is easy to solve, limiting their applicability. When it is not the case, it is preferable to use only local (sub-)gradient evaluation of the local objective $f_{i}$. The focus of this paper is such primal-only gradient based distributed optimization. Here “primal-only gradient” means that the gradient of functions $f_{i}$, as opposed to the “dual gradient” used in .

There is also a large literature on such gradient based distributed optimization, , most of which are distributed (sub)gradient algorithms based on a consensus/averaging scheme . At each iteration, each agent performs one or multiple consensus steps plus one local gradient evaluation step. These methods have achieved sublinear convergence rates for convex functions. When the convex functions are nonsmooth, the sublinear convergence rate matches the Centralized subGradient Descent (CGD) method. More recent work , have improved these results to achieve linear convergence rates for strongly convex and smooth functions, or $O(\frac{1}{t})$ convergence rates for convex and smooth functions, which match the centralized gradient descent method as well. For example, the EXTRA method in , and the class of methods in , can all achieve a linear convergence rate for strongly-convex and smooth functions. Further, among these work, some have additional focus beyond convergence rate, like time-varying graph , directed graph , uncoordinated step sizes , and stochastic gradient .

It is known that among all centralized gradient based algorithms, centralized Nesterov Gradient Descent (CNGD) achieves the optimal convergence rate in terms of first-order oracle complexity. Specifically, for convex and $L$-smooth problems, the convergence rate is $O(\frac{1}{t^{2}})$, which improves over centralized gradient descent (CGD)’s $O(\frac{1}{t})$ rate; for $\mu$-strongly convex and $L$-smooth problems, the convergence rate is $O((1-\sqrt{\frac{\mu}{L}})^{t})$ whose dependence on condition number $\frac{L}{\mu}$ improves over CGD’s rate $O((1-\frac{\mu}{L})^{t})$ in the large $\frac{L}{\mu}$ regime. The nice convergence rates naturally lead to the following question: how to achieve similar rate as CNGD in the realm of gradient-based distributed optimization? To the best of our knowledge, for $\mu$-strongly convex and $L$-smooth functions, existing gradient-based distributed methods have the same or worse dependence on condition number compared to CGD. For convex and $L$-smooth functions, paper has developed Distributed Nesterov Gradient (D-NG) method and shown that it has a convergence rate of $O(\frac{\log t}{t})$.The convergence rate for strongly convex and smooth functions is not studied in . From our simulation results in Section VI, the convergence rate for strongly convex and smooth functions is sublinear. Paper also studies an algorithm that achieves almost $O(\frac{1}{t^{2}})$ convergence rate but it contains an inner loop of multiple consensus steps per iteration. The inner loop places a larger communication burden and needs extra coordination among agents (e.g., agreeing on when to terminate the inner loop), while communication burden has been recognized as the major bottleneck for distributed optimization .See Section III-B for a more detailed comparison between our methods and , as well as a discussion on why we avoid using the inner loop. In light of the above discussions, the aim of this paper is to design distributed Nesterov gradient methods that only use one communication step per gradient evaluation but achieve fast convergence rates to bridge the gap between distributed gradient methods and centralized ones, in particular reaching the same level of convergence rate as CNGD in the realm of distributed optimization, for both $\mu$-strongly convex, $L$-smooth functions and convex, $L$-smooth functions.

In this paper, we propose an Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD) algorithm. Our algorithm has two versions. The first version Acc-DNGD-SC is designated for $\mu$-strongly convex and $L$-smooth functions. It achieves a convergence rate of $O((1-C(\frac{\mu}{L})^{5/7})^{t})$, where $C$ is a constant that does not depend on $L$ or $\mu$ and the value of $C$ will be clear in Theorem 3. We emphasize here that the dependence on the condition number $L/\mu$ in our convergence rate ($[1-C(\frac{\mu}{L})^{5/7}]^{t}$ ) is strictly better than that of CGD ($(1-\frac{\mu}{L})^{t}$), and to the best of our knowledge, the asymptotic dependence on condition number in the large $\frac{L}{\mu}$ regime is the best among all primal gradient-based distributed algorithms proposed so far for the class of $\mu$-strongly convex and $L$-smooth functions.If dual-gradients are available, the dependence on $\frac{L}{\mu}$ can be better . The second version Acc-DNGD-NSC works for convex and $L$-smooth functions. It achieves a $O(\frac{1}{t^{1.4-\epsilon}})$ ($\forall\epsilon\in(0,1.4)$) convergence rate if a vanishing step size is used. We further show that the convergence rate can be improved to $O(\frac{1}{t^{2}})$ when we use a fixed step size and the objective function is a composition of a linear map and a strongly-convex and smooth function. Both rates are faster than CGD ($O(\frac{1}{t})$). To the best of our knowledge, the $O(\frac{1}{t^{1.4-\epsilon}})$ rate is also the fastest among all existing primal gradient-based distributed algorithms that use one or a constant number of consensus steps per iteration for the class of convex and $L$-smooth functions. In summary, for both function classes, we have achieved rates that are strictly better than CGD but still slower than CNGD, hence we have partially bridged the gap between centralized gradient methods and distributed ones. How to fully close the gap remains an open question.

The major technique we use in our algorithm is a gradient estimation scheme , and we combine the scheme with CNGD. Briefly speaking, the scheme tracks the average gradient in an efficient way, and it avoids the use of an inner loop as in . We will explain the intuition of the gradient estimation scheme in Section III-B.

Finally, we note that our proof uses the framework of inexact Nesterov method . It is known that inexact Nesterov methods accumulate error and are prone to divergence [39, Sec. 6] [40, Sec 5]. One key step in our proof is to show that when the error has a special structure, we can still get exact convergence. This proof technique may be of independent interest in general inexact Nesterov methods. See Remark 5 and 6 for more details.

Notations. In this paper, $n$ is the number of agents, and $N$ is the dimension of the domain of the $f_{i}$’s. Notation $\|\cdot\|$ denotes $2$-norm for vectors and Frobenius norm for matrices, while $\|\cdot\|_{*}$ denotes spectral norm for matrices, $\|\cdot\|_{1}$ denotes $1$-norm for vectors, and $\langle\cdot,\cdot\rangle$ denotes inner product for vectors. Notation $\rho(\cdot)$ denotes spectral radius for square matrices, and $\mathbf{1}$ denotes a $n$-dimensional all one column vector. All vectors, when having dimension $N$ (the dimension of the domain of the $f_{i}$’s), will all be regarded as row vectors. As a special case, all gradients, $\nabla f_{i}(x)$ and $\nabla f(x)$ are treated as $N$-dimensional row vectors. Notation “$\leq$”, when applied to vectors of the same dimension, denotes element wise “less than or equal to”.

II Problem and Algorithm

using local communication and local computation. The local communication is defined through a connected and undirected communication graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$, where the nodes are the agents, and edges $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$. Agent $i$ and $j$ can send information to each other if and only if $(i,j)\in\mathcal{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.

As a result, $f$ is also $L$-smooth. We assume $f$ has at least one minimizer $x^{*}$ with $f(x^{*})=f^{*}$.

Other Assumptions. We will use the following assumptions in different parts of the paper, and those will be stated explicitly.

As a result, $f$ is also $\mu$-strongly convex.

II-B Centralized Nesterov Gradient Descent (CNGD)

The following theorem (adapted from [36, Theorem 2.2.1, Lemma 2.2.4]) gives the convergence rate of CNGD-SC.

Under Assumption 1, when $0<\eta\leq\frac{1}{L}$, in CNGD-SC (2) we have $f(x(t))-f^{*}=O((1-\sqrt{\mu\eta})^{t})$.

where $(\alpha_{t})_{t=0}^{\infty}$ is defined by an arbitrarily chosen $\alpha_{0}\in(0,1)$ and the update equation $\alpha_{t+1}^{2}=(1-\alpha_{t+1})\alpha_{t}^{2}$. Here $\alpha_{t+1}$ always takes the unique solution in $(0,1)$. The following theorem (adapted from [36, Theorem 2.2.1, Lemma 2.2.4]) gives the convergence rate of CNGD-NSC.

In CNGD-NSC (3), when $0<\eta\leq\frac{1}{L}$, we have $f(x(t))-f^{*}=O(\frac{1}{t^{2}})$.

II-C Our Algorithm: Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD)

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

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

where $[w_{ij}]_{n\times n}$ are the consensus weights, $\eta>0$ is a fixed step size and $\alpha=\sqrt{\mu\eta}$.

The second version, Acc-DNGD-NSC, is designated for convex (not necessarily strongly convex) and $L$-smooth functions. Similarly as Acc-DNGD-SC, each agent keeps variable $x_{i}(t)$, $v_{i}(t)$, $y_{i}(t)$ and $s_{i}(t)$. The initial condition is $x_{i}(0)=v_{i}(0)=y_{i}(0)=0$ and $s_{i}(0)=\nabla f(0)$,We note that the initial condition $s_{i}(0)=\nabla f(0)=\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(0)$ requires the agents to conduct an initial run of consensus averaging. We impose this initial condition for technical reasons, while we expect the results of this paper to hold for a relaxed initial condition, $s_{i}(0)=\nabla f_{i}(y_{i}(0))$ which does not need initial coordination. We use the relaxed condition in numerical simulations. and the algorithm updates as follows:

where $[w_{ij}]_{n\times n}$ are the consensus weights and $\eta_{t}\in(0,\frac{1}{L})$ are the step sizes. Sequence $(\alpha_{t})_{t\geq 0}$ is generated as follows. First we let $\alpha_{0}=\sqrt{\eta_{0}L}\in(0,1)$. Then given $\alpha_{t}\in(0,1)$, we select $\alpha_{t+1}$ to be the unique solution in $(0,1)$ of the following equation,Without causing any confusion with the $\alpha_{t}$ in (3), in the rest of the paper we abuse the notation of $\alpha_{t}$.

We will consider two variants of the algorithm with the following two step size rules.

Vanishing step size: $\eta_{t}=\eta\frac{1}{(t+t_{0})^{\beta}}$ for some $\eta\in(0,\frac{1}{L})$, $\beta\in(0,2)$ and $t_{0}\geq 1$.

In both versions (Acc-DNGD-SC (4) and Acc-DNGD-NSC (5)), because $w_{ij}=0$ when $(i,j)\notin\mathcal{E}$, each node $i$ only needs to send $x_{i}(t)$, $v_{i}(t)$, $y_{i}(t)$ and $s_{i}(t)$ to its neighbors. Therefore, the algorithm can be operated in a fully distributed fashion with only local communication. The additional term $s_{i}(t)$ allows each agent to obtain an estimate on the average gradient $\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(y_{i}(t))$. Compared with distributed algorithms without this estimation term, it improves the convergence rate. We will provide intuition behind the gradient estimator $s_{i}(t)$ in Sec. III-B. Because of the use of the gradient estimation term, we call this method as Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD) method.

II-D Convergence of the Algorithm

Consider algorithm Acc-DNGD-SC (4). Under the strongly convex assumption (Assumption 1), when $0<\eta<\frac{\sigma^{3}(1-\sigma)^{3}}{250^{2}L}(\frac{\mu}{L})^{3/7}$, we have (a) $f(\bar{x}(t))-f^{*}=O((1-\sqrt{\mu\eta})^{t})$; (b) For any $i$, $f(y_{i}(t))-f^{*}=O((1-\sqrt{\mu\eta})^{t})$.

The upper bound on the step size $\eta$ given in theorem 3 results in a convergence rate of $O([1-C(\frac{\mu}{L})^{5/7}]^{t})$ with $C=\frac{\sigma^{1.5}(1-\sigma)^{1.5}}{250}$. In this convergence rate, the dependence on the condition numberThe quantity $\frac{L}{\mu}$ is called the condition number of the objective function. For a convergence rate of $O((1-(\frac{\mu}{L})^{\delta})^{t})$, it takes $O((\frac{L}{\mu})^{\delta}\log\frac{1}{\epsilon})$ iterations to reach an accuracy level $\epsilon$. Therefore, the smaller $\delta$ is, the better the convergence rate is. $\frac{L}{\mu}$ is strictly better than that of CGD ($O((1-\frac{\mu}{L})^{t})$), and hence CGD based distributed algorithms . This means that when the condition number $\frac{L}{\mu}$ is sufficiently large, our method can outperform CGD and CGD-based distributed methods. This is particularly appealing because in many machine learning applications, the condition number $\frac{L}{\mu}$ can be as large as the sample size [42, Section 3.6]. We also highlight that in the conference version of this paper , the dependence on condition number was $(\frac{\mu}{L})^{1.5}$, worse than that of CGD. Compared to , this paper conducts a sharper analysis on our algorithm.

We next provide the convergence result for Acc-DNGD-NSC in Theorem 4.

Consider algorithm Acc-DNGD-NSC (5). Suppose Assumption 2 is true and without loss of generality we assume $\bar{v}(0)\neq x^{*}$ where $\bar{v}(0)=\frac{1}{n}\sum_{j=1}^{n}v_{j}(0)$. Let the step size be $\eta_{t}=\frac{\eta}{(t+t_{0})^{\beta}}$ with $\beta=0.6+\epsilon$ where $\epsilon\in(0,1.4)$. Suppose the following conditions are met.

where $D(\beta,t_{0})=\frac{1}{(t_{0}+3)^{2}e^{16+\frac{6}{2-\beta}}}$ and $R$ is the diameter of the $(2f(\bar{x}(0))-f^{*}+2L\|\bar{v}(0)-x^{*}\|^{2})$-level set of $f$.Here we have used the fact that by Assumption 2, all level sets of $f$ are bounded. See [44, Proposition B.9].

Then, we have (a) $f(\bar{x}(t))-f^{*}=O(\frac{1}{t^{2-\beta}})=O(\frac{1}{t^{1.4-\epsilon}})$; (b) $\forall i$, $f(y_{i}(t))-f^{*}=O(\frac{1}{t^{1.4-\epsilon}})$.

The step size condition in Theorem 4 may be difficult to implement since constant $R$ may be unknown to the individual agents. However, we believe the exact value of $\eta>0$ and $t_{0}>0$ do not actually matter, and in simulations we simply set $\eta=\frac{1}{2L}$ and $t_{0}=1$. The reason is as follows. The most important condition we need on $\eta_{t}$ is that $\eta_{t}$ is monotonically decaying to in the order of $O(\frac{1}{t^{\beta}})$ with $\beta\in(0.6,2)$. The condition $\beta>0.6$ is important in the proof as it makes $\eta_{t}$ converge to sufficiently fast to control the error. Other than that, the condition (i)(ii)(iii) on $\eta$ and $t_{0}$ in Theorem 4 is to ensure $\eta_{0}$ is small, and $\frac{\eta_{t}}{\eta_{t+1}}$ is close to $1$, which are needed only for some technical reasons in the proof. In fact, in the literature that uses vanishing step sizes, it is not uncommon that only the order of decaying matters, while other constants are not as important [37, Theorem 5 (b)]. Lastly, in Figure 6 in the simulations, we verify the stability of step size rule $\frac{1}{2L(t+1)^{\beta}}$ (i.e. $\eta=\frac{1}{2L}$ and $t_{0}=1$) under randomly generated problem instances.

While in Theorem 4 we require $\beta>0.6$, we conjecture that the algorithm will converge with rate $O(\frac{1}{t^{2-\beta}})$ even if we choose $\beta\in[0,0.6]$, with $\beta=0$ corresponding to the case of fixed step size. In Section VI we will use numerical methods to support this conjecture.

In the next theorem, we provide a $O(\frac{1}{t^{2}})$ convergence result when a fixed step size is used and the objective functions belong to a special class.

where $L=L_{0}\nu$ with $\nu=\max_{i}\|A_{i}\|_{*}^{2}$; and $\mu=\mu_{0}\gamma$ with $\gamma$ being the smallest non-zero eigenvalue of matrix $A=\frac{1}{n}\sum_{i=1}^{n}A_{i}A_{i}^{T}$. Then, we have (a) $f(\bar{x}(t))-f^{*}=O(\frac{1}{t^{2}})$; (b) $\forall i$, $f(y_{i}(t))-f^{*}=O(\frac{1}{t^{2}})$.

The reason we can prove a faster convergence rate under the assumption in Theorem 5 is that, when $f_{i}=h_{i}(xA_{i})$, we have $\nabla f_{i}=\nabla h_{i}(xA_{i})A_{i}^{T}$ which lies in the row space of $A=\frac{1}{n}\sum_{i=1}^{n}A_{i}A_{i}^{T}$.To see this, let (column) vector $y$ be such that $Ay=0$. Then we have $\langle y,Ay\rangle=\frac{1}{n}\sum_{j=1}^{n}\|A_{j}^{T}y\|^{2}=0$, implying $A_{i}^{T}y=0$. Hence, $\langle\nabla f_{i}(x),y\rangle=\nabla h_{i}(xA_{i})A_{i}^{T}y=0$, implying $\nabla f_{i}(x)$ is orthogonal to any vector in $A$’s (right) kernel space. As a result, $x_{i}(t)-y_{i}(t)$ also lies within the row space of $A$ as $x_{i}(t)-y_{i}(t)$ is a linear combination of such gradients. With this property, and the fact that $h_{i}$ is strongly convex, we can show $f$ behaves like a strongly convex function around $x_{i}(t)$ and $y_{i}(t)$. It is this “local strong convexity” property that helps us obtain a faster convergence result.

An important example of functions $f_{i}(x)$ in Theorem 5 is the square loss for linear regression (cf. Case I in Section VI) when the sample size is less than the parameter dimension.

Here we provide a few remarks on the strongly-convex parameter $\mu$, smooth parameter $L$, graph parameter $\sigma$, and the numerical constants in the step size bounds in Theorem 3,4, and 5.

Parameter $\mu$, $L$: though we have assumed each function $f_{i}$ has the same strongly convex and smooth parameter $\mu,L$, in reality each function $f_{i}$ may have heterogeneous $\mu_{i}$ and $L_{i}$ parameters. In this case, our results still hold if we take $L$ to be an upper bound of the $L_{i}$’s, and $\mu$ to be a lower bound of the $\mu_{i}$’s. This may require additional coordination among the agents before running the distributed algorithms. Recently, techniques have been proposed that allow each $f_{i}$ to have heterogeneous $\mu_{i}$ and $L_{i}$, and each agent only needs to know their local $\mu_{i},L_{i}$ as opposed to the global $L$, $\mu$ . How to incorporate such techniques into our method remains our future work.

Parameter $\sigma$: though the graph parameter $\sigma$ is not directly available to each agent, there have been techniques in the literature to replace the $\sigma$ in the step size bounds with some locally accessible surrogates when the agents have an estimate on the total number of agents in the network [27, Corollary 5].

Numerical Constants: all numerical constants in the step size bounds (like the $250^{2}$ in Theorem 3) provided in this section are conservative. In the proof, we have been intentionally loose on the numerical constants to keep the analysis simple and only focus on getting the tightest asymptotic dependence on critical parameters (e.g. the $(\frac{\mu}{L})^{3/7}$ in the step size bound in Theorem 3). In the numerical simulations, we use much larger step sizes than the bounds in this section. How to find tighter bounds remains our future work.

III Algorithm Development

In this section, we will discuss the proof idea in Section III-A and then compare our algorithm to a class of methods that use an inner-loop of consensus iterations in Section III-B. Specifically, we will explain why we avoid the use of the inner loop idea and instead use the gradient estimator $s_{i}(t)$ in our algorithm (4) (5).

We now explain the intuition behind Acc-DNGD-SC (4) whereas the intuition for Acc-DNGD-NSC (5) is similar. The main idea is that the distributed algorithm imitates the centralized one. Since we conduct averaging steps (“$\sum_{j=1}^{n}w_{ij}y_{j}(t)$”, “$\sum_{j=1}^{n}w_{ij}v_{j}(t)$” and “$\sum_{j=1}^{n}w_{ij}s_{j}(t)$”) in (LABEL:eq:alg:update_elementwise_1), (LABEL:eq:alg:update_elementwise_2), (LABEL:eq:alg:update_elementwise_3), we expect that $x_{i}(t)\approx\bar{x}(t):=\frac{1}{n}\sum_{j=1}^{n}x_{j}(t)$, $y_{i}(t)\approx\bar{y}(t):=\frac{1}{n}\sum_{j=1}^{n}y_{j}(t)$, $v_{i}(t)\approx\bar{v}(t):=\frac{1}{n}\sum_{j=1}^{n}v_{j}(t)$, and also $s_{i}(t)\approx\bar{s}(t):=\frac{1}{n}\sum_{j=1}^{n}s_{j}(t)$ which can easily shown to be equal to $\frac{1}{n}\sum_{j=1}^{n}\nabla f_{j}(y_{j}(t))\approx\nabla f(\bar{y}(t))$. Therefore, we expect (4) to imitate the following update,This “imitation” argument will be made more precise using inexact Nesterov Gradient Descent framework in Lemma 2.

which is precisely CNGD-SC (2). However, we emphasize that the distributed algorithm does not exactly follow (7) due to consensus errors, i.e. how close each individual’s $x_{i}(t)$, $y_{i}(t)$, $v_{i}(t)$, $s_{i}(t)$ are to their average, $\bar{x}(t)$, $\bar{y}(t)$, $\bar{v}(t)$, $\bar{s}(t)$. With these observations, the proof can be mainly divided into two steps. The first is to bound the consensus errors. It turns out that bounding $\|y_{i}(t)-\bar{y}(t)\|$ is sufficient for our purpose (cf. Lemma 3 and 10). Secondly, with the bounded consensus error, we treat the distributed algorithm as an inexact version of (7) and then use the framework of inexact Nesterov gradient descent to prove convergence.

It is well known Nesterov Gradient method is prone to accumulating noise and divergence . Therefore, in the literature, when adapting Nesterov Gradient Descent to inexact settings, it usually requires nontrivial error bounds and sophisticated proof techniques to show convergence (e.g. in stochastic setting ). From this perspective, our contribution can be viewed as adapting Nesterov Gradient Descent to a distributed setting and show its convergence, which is nontrivial for the reasons above. Further, our proof technique may be of independent interest in general inexact Nesterov methods. See Remark 5 and 6 for more details.

This section will compare this work and the methods that use an inner loop of consensus steps , in particular . Ref. proposes two algorithms, the first of which is named “D-NG”, which is described as follows [37, eq. (2) (3)] using the notations of this paper (cf. (10) Section IV-A),

where $x(t)$, $y(t)$, $\nabla(t)$ are the local quantities $x_{i}(t)$, $y_{i}(t)$, $\nabla f_{i}(y_{i}(t))$ stacked together as defined in (10).

The problem with (8) is that the descent direction for $x_{i}(t)$ is local gradient $\nabla f_{i}(y_{i}(t))$, which is incorrect. To see this, note when $x_{i}(t)$ and $y_{i}(t)$ reach an optimizer $x^{*}$ of $f$, $\nabla f_{i}(y_{i}(t))$ is in general non-zero. As a result, $x_{i}(t)=y_{i}(t)=x^{*}$ may not even be a fixed point of $\eqref{eq:jakovetic_dng}$. On the contrary, the correct direction is the average gradient, i.e. $\frac{1}{n}\sum_{j=1}^{n}\nabla f_{j}(y_{j}(t))$, which will be zero when $y_{i}(t)=x^{*}$. As a result of the incorrect descent direction, a $O(\frac{1}{t})$ step size is used in (8) to force $x^{*}$ be a limit point of algorithm (8). However, the diminishing step size also causes the convergence rate of (8) to be $O(\frac{\log t}{t})$, slower than $O(\frac{1}{t^{2}})$ of CNGD.

The inner-loop approach is proposed to fix the incorrect descent direction issue. Specifically, proposes a second algorithm named “D-NC” [37, eq. (9)(10)] as follows,

where $\tau_{x}(t)$ and $\tau_{y}(t)$ are both integer functions of $t$ that grow in the order of $\Omega(\log t)$. Briefly speaking, at each iteration $t$, D-NC first moves along the (incorrect) local gradient direction $\nabla f_{i}(y_{i}(t))$ in (LABEL:eq:jakovetic_dnc_x), and then conducts an inner loop of $\tau_{x}(t)$ consensus steps (the multiplication of matrix $W^{\tau_{x}(t)}$ in (LABEL:eq:jakovetic_dnc_x)). This effectively make the descent direction approximately the average gradient $\frac{1}{n}\sum_{j=1}^{n}\nabla f_{j}(y_{j}(t))$, and hence the descent direction is approximately correct, and a constant step size can be used, achieving a $O(\frac{1}{T^{2-\epsilon}})$ (for arbitrarily small $\epsilon>0$) rate where $T$ is the total number of consensus steps.

Despite the improved convergence rate, there are a few disadvantages of the inner-loop approach. Firstly, the implementation of the inner loop places extra coordination burden on the agents, e.g. they need to agree on when to terminate the inner-loop. Secondly, the work in (also in ) requires to assume the gradients $\nabla f_{i}(\cdot)$ are uniformly bounded. This is a strong assumption since even the simple quadratic functions do not meet this assumption. Further, as [37, Sec VII-B] shows, without the bounded gradient assumption the results in no longer holds. Thirdly, the inner loop approach does not work well when the cost functions are strongly convex. Though neither nor studies the strongly convex case, it can be shown that if applying the inner loop approach to the strongly convex case, at outer iteration $t$, to obtain a sufficiently accurate estimate of average gradient, the number of inner loop iterations needs to grow at least in the order of $\Omega(t)$. The large number of inner loop iterations slows down the convergence, resulting in a sublinear convergence rate.

For the above reasons, in this paper we do not use an inner loop. Instead, we use a gradient estimation sequence recently proposed in , which is a more efficient use of consensus steps to get the correct descent direction. Briefly speaking, our algorithm uses descent direction $s_{i}(t)$, which has its own update formula (LABEL:eq:alg:update_elementwise_4) (LABEL:eq:nsc:update_elementwise_4), and can be shown to asymptotically converge to the average gradient, the correct descent direction. The way it works is that, at each time $t$, $s_{i}(t+1)$ averages over neighbors’ $s_{j}(t)$, which itself is an estimate of the average gradient at time $t$, and then $s_{i}(t+1)$ adds “incremental information”, i.e. the difference between the new gradient and the previous gradient ($\nabla f_{i}(y_{i}(t+1))-\nabla f_{i}(y_{i}(t))$). The incremental information makes sure the estimator tracks the latest gradient, and the incremental information is expected to be “small”, since $\|\nabla f_{i}(y_{i}(t+1))-\nabla f_{i}(y_{i}(t))\|\leq L\|y_{i}(t+1)-y_{i}(t)\|$ and we can make $\|y_{i}(t+1)-y_{i}(t)\|$ small by carefully controlling the step size. Given the small incremental information, $s_{i}(t)$ asymptotically gives a good estimate of the average gradient, which allows us to use a larger step size than (8) and improve the convergence rate. The use of such gradient estimator has gained popularity recently and our earlier work provides more details explaining how it works. Using this gradient estimator $s_{i}(t)$, we have avoided the disadvantages associated with the inner loop approach. Our algorithms are easier to implement, do not need the bounded gradient assumption, and achieve linear convergence rates for strongly convex and smooth functions. This being said, we acknowledge that for convex and smooth functions, our algorithm’s rate $O(\frac{1}{t^{1.4-\epsilon}})$ (Theorem 4) is slower than that of the inner-loop approach D-NC ’s rate $O(\frac{1}{t^{2-\epsilon}})$, as our method requires smaller step size (Theorem 4). With the additional assumption on the functional form, our method can also achieve a $O(\frac{1}{t^{2}})$ rate (Theorem 5) matching that of [37, D-NC]. Though we need the additional assumption, we comment that [37, D-NC] relies on the bounded gradient assumption which we do not need. To sum up, for the class of convex and smooth functions, the comparison between our proposed method and D-NC is complicated - one should take into account the type of functions and whether they meet the assumptions in our paper or the ones in [37, D-NC], and one should also consider the complexity in implementation - e.g. the inner-loop approach would require additional coordination including agreeing on when to switch between the inner-loop and the outer-loop.

IV Convergence Analysis of Acc-DNGD-SC

In this section, we will provide the proof of Theorem 3. We will first provide a proof overview in Section IV-A and then defer a few steps of the proof to the rest of the section.

Now the algorithm Acc-DNGD-SC (4) can be written as

Apart from the average sequence $\bar{x}(t)=\frac{1}{n}\sum_{i=1}^{n}x_{i}(t)$ that we have defined, we also define several other average sequences, $\bar{v}(t)=\frac{1}{n}\sum_{i=1}^{n}v_{i}(t)$, $\bar{y}(t)=\frac{1}{n}\sum_{i=1}^{n}y_{i}(t)$, $\bar{s}(t)=\frac{1}{n}\sum_{i=1}^{n}s_{i}(t)$, and $g(t)=\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(y_{i}(t))$. We would like to remind here that all quantities associated with each agent like $x_{i}(t)$, $v_{i}(t)$, $y_{i}(t)$, $s_{i}(t)$, $\nabla f_{i}(y_{i}(t))$, as well as their average $\bar{x}(t)$, $\bar{v}(t)$, $\bar{y}(t)$, $\bar{s}(t)$, $g(t)$, are row vectors of dimension $N$ where $N$ is the dimension of the domain of the $f_{i}$’s. As a result, quantity $x(t),v(t),y(t),s(t)$, $\nabla(t)$, are matrices of dimension $n$-by-$N$.

Overview of the Proof. In our proof, we firstly derive the update formula for the average sequences (Lemma 1). Then, it turns out that the update rule for the average sequences is in fact CNGD-SC (4) with inexact gradients , and the inexactness is characterized by “consensus error” $\|y(t)-\mathbf{1}\bar{y}(t)\|$ (Lemma 2). The consensus error is then bounded in Lemma 3. With the bound on consensus error, we can roughly apply the same proof steps of CNGD-SC (see e.g. ) to the average sequence and finish the proof of Theorem 3.

Proof: We omit the proof since these can be easily derived using the fact that $W$ is doubly stochastic. For (LABEL:eq:nes:update_ave_d) we also need to use the fact that $\bar{s}(0)=g(0)$. $\Box$

From (LABEL:eq:nes:update_ave_a)-(LABEL:eq:nes:update_ave_c) we see that the sequences $\bar{x}(t)$, $\bar{v}(t)$ and $\bar{y}(t)$ follow a update rule similar to the CNGD-SC in (2). The only difference is that $g(t)$ in (LABEL:eq:nes:update_ave_a)-(LABEL:eq:nes:update_ave_c) is not the exact gradient $\nabla f(\bar{y}(t))$ in CNGD-SC. In the following Lemma, we show that $g(t)$ is an inexact gradient with error $O(\|y(t)-\mathbf{1}\bar{y}(t)\|^{2})$.

The consensus error $\|y(t)-\mathbf{1}\bar{y}(t)\|$ in the previous lemma is bounded by the following lemma whose proof is deferred to Section IV-B.

When $0<\eta<\min(\frac{1}{L}\frac{(1-\sigma)^{3}}{512},\frac{1}{L}\frac{\sigma^{3}}{64})$, we have

With the above preparations, we are ready to provide the proof of Theorem 3. Following similar techniques in , we recursively define a series of functions $\Phi_{t}(\omega)$. We first define $\Phi_{0}(\omega)=f(\bar{x}(0))+\frac{\mu}{2}\|\omega-\bar{v}(0)\|^{2}$ and given $\Phi_{t}(\cdot)$, we define $\Phi_{t+1}(\cdot)$ by,

The following lemma gives a few properties on $\Phi_{t}(\cdot)$. Its proof is almost identical to the techniques used in the proof of Nesterov Gradient Descent in textbook [36, Lemma 2.2.3].

where $\phi_{0}^{*}=f(\bar{x}(0))$, and given $\phi_{t}^{*}$, $\phi_{t+1}^{*}$ is defined as,

Proof of Lemma 4: We first show part (a). By (IV-A), $\Phi_{t}$ is always a quadratic function. Since $\nabla^{2}\Phi_{0}(\omega)=\mu I$ and $\nabla^{2}\Phi_{t+1}(\omega)=(1-\alpha)\nabla^{2}\Phi_{t}(\omega)+\alpha\mu I$, we get $\nabla^{2}\Phi_{t}(\omega)=\mu I$ for all $t$. We next show by induction that $\Phi_{t}(\cdot)$ achieves its minimum at $\bar{v}(t)$. Firstly, $\Phi_{0}$ achieves its minimum at $\bar{v}(0)$. Assume $\Phi_{t}(\cdot)$ achieves minimum at $\bar{v}(t)$. Since $\Phi_{t}$ is a quadratic function with Hessian $\mu I$, we have $\nabla\Phi_{t}(\bar{v}(t+1))=\mu(\bar{v}(t+1)-\bar{v}(t))$. Then by (IV-A), we have

where the last equality follows from (LABEL:eq:nes:update_ave_b) and the fact $\frac{\eta}{\alpha}=\frac{\alpha}{\mu}$. Hence $\Phi_{t+1}$ achieves its optimum at $\bar{v}(t+1)$. Now we have shown that $\Phi_{t}(\cdot)$ is a quadratic function that achieves minimum at $\bar{v}(t)$ with Hessian $\mu I$. This implies (16) is true. It remains to calculate $\phi_{t}^{*}$. Clearly, $\phi_{0}^{*}=f(\bar{x}(0))$. Setting $\omega=\bar{y}(t)$ in (IV-A), we get $\Phi_{t+1}(\bar{y}(t))=(1-\alpha)\Phi_{t}(\bar{y}(t))+\alpha\hat{f}(t)$. Combining this with (16), we can get (17).

We next show part (b). Clearly (18) is true for $t=0$. Assuming it’s true for $t$, then for $t+1$, we have by (IV-A) and (13),

The major step of proving Theorem 3 is to show the following inequality,

If (19) is true, then combining (19) with (18), we have

which implies $f(\bar{x}(t))-f^{*}=O((1-\alpha)^{t})$, that is part (a) of the theorem. We put the proof of (19) in Section IV-C. We will also derive part (b) of the theorem (i.e. $f(y_{i}(t))-f^{*}=O((1-\sqrt{\mu\eta})^{t})$) in Section IV-C, which will be an easy corollary of (19).

In the context of inexact Nesterov method for strongly convex and smooth functions, the final part of our proof essentially shows that for any inexact Nesterov method for sequence $\bar{x}(t)$, $\bar{y}(t)$, $\bar{v}(t)$ with inexact gradient $g(t)$ and step size $\eta$, when the error at time $t$ depends on past iterates of the form $A_{1}(\eta)\theta^{t}+A_{2}(\eta)\sum_{k=0}^{t}\theta^{t-k}(\|\bar{x}(k)-\bar{y}(t)\|+\eta\|g(k)\|)$ for some $\theta\in[0,1)$, where $A_{2}(\eta)$ is a positive constant that depends on $\eta$ and satisfies $\lim_{\eta\rightarrow 0}A_{2}(\eta)<\infty$, then the algorithm can have exact convergence if $\eta$ is small enough. This stands in contrast to the results in [40, Sec. 5.3] where only approximate convergence can be obtained when the error is a constant throughout the iterations.

IV-B Proof of the Bounded Consensus Error (Lemma 3)

We now give the proof of Lemma 3. We will frequently use the following two lemmas, whose proofs are deferred to Appendix-A-A.

The proof of Lemma 3 is separated into two steps. In step 1, we treat the algorithm (11) as a linear system and derive a linear system inequality (23). In step 2, we analyze the state transition matrix in (23) and prove its spectral properties, from which we conclude the lemma.

We now prove (23). By (LABEL:eq:nes:update_vector_a) and (LABEL:eq:nes:update_ave_a), we have

By (LABEL:eq:nes:update_vector_b) and (LABEL:eq:nes:update_ave_b), we have

By (LABEL:eq:nes:update_vector_c) and (LABEL:eq:nes:update_ave_c), we have

where we have used (24) and (25) in the second inequality, and the fact that $\frac{1}{1+\alpha}<1$ in the third inequality.

By (LABEL:eq:nes:update_vector_d) and (LABEL:eq:nes:update_ave_d), we have

where in (a) we have used the fact that by $g(t)=\frac{1}{n}\mathbf{1}^{T}\nabla(t)$,

where in the last inequality we have used (20) (Lemma 5). Combining the above with (27), we get

Combining (25) (26) (28) gives the linear system inequality (23).

Step 2: Spectral Properties of $G(\eta)$. We give the following lemma regarding $G(\eta)$. We provide a proof-sketch here while the complete proof can be found in Appendix-A-B.

When $0<\eta<\min(\frac{1}{L}(\frac{1-\sigma}{8})^{3},\frac{\sigma^{3}}{L64})$, the following holds.

We have $\sigma+(\sigma\eta L)^{1/3}<\rho(G(\eta))<\sigma+4(\eta L)^{1/3}<\frac{1+\sigma}{2}=\theta.$

The $(2,3)$th entry of $G(\eta)^{t}$ is upper bounded by $[G(\eta)^{t}]_{2,3}\leq\frac{39(\eta L)^{1/3}}{(\sigma)^{2/3}}\rho(G(\eta))^{t}.$

The entries in the 2nd row of $G(\eta)^{t}$ are all upper bounded by $\frac{39}{(\sigma\eta L)^{2/3}}\rho(G(\eta))^{t}.$

Notice in Lemma 7 (b), the constant $\frac{39(\eta L)^{1/3}}{(\sigma)^{2/3}}$ converges to as $\eta\rightarrow 0$. This fact is crucial in the proof of eq. (19) in Sec. IV-C (cf. (32) and the argument following it).

The step size condition in Lemma 3 ensures the condition of Lemma 7. By (23),

Recall the second entry of $z(t)$ is $\|y(t)-\mathbf{1}\bar{y}(t)\|$, and $b(t)=[0,0,\sqrt{n}a(t)]^{T}$. Hence the above inequality implies,

IV-C Proof of (19)

where (a) is due to $\bar{v}(t)-\bar{y}(t)=\frac{1}{\alpha}(\bar{y}(t)-\bar{x}(t))$ and (b) is due to (13) (for $\omega=\bar{x}(t)$). In (c), we have used $(1-\alpha)\alpha(\bar{v}(t)-\bar{y}(t))+(1-\alpha)(\bar{x}(t)-\bar{y}(t))=(1-\alpha)[\alpha\bar{v}(t)+\bar{x}(t)-(1+\alpha)\bar{y}(t)]=0$. In (d), we have used $f(\bar{x}(t+1))\leq\hat{f}(t)+(\eta^{2}L-\eta)\|g(t)\|^{2}+\frac{L}{n}\|y(t)-\mathbf{1}\bar{y}(t)\|^{2}$, which follows from (14) (for $\omega=\bar{x}(t+1)$). We expand (29) recursively,

By Lemma 3 (the step size in Theorem 3 implies the condition of Lemma 3 holds), we have $\|y(k)-\mathbf{1}\bar{y}(k)\|\leq\nu^{T}\pi_{k}$, and hence $\|y(k)-\mathbf{1}\bar{y}(k)\|^{2}\leq\nu^{T}\pi_{k}\pi_{k}^{T}\nu$. Therefore,

By the step size in Theorem 3 we have $\eta<\frac{(1-\sigma)^{2}}{4\mu}$, and hence $\alpha<\frac{1-\sigma}{2}=1-\theta$. Therefore, $\frac{\theta}{\sqrt{1-\alpha}}<\sqrt{\theta}<1$, and $1-\frac{\theta}{\sqrt{1-\alpha}}>1-\sqrt{\theta}>\frac{1-\theta}{2}=\frac{1-\sigma}{4}$. Therefore,

Hence, by Gershgorin Disk Theorem, $\rho(\Pi)\leq\max_{p}(\sum_{q=1}^{t+1}\Pi_{pq})\leq 32/(1-\sigma)^{2}.$ Combining the above with (31),

where in the last step, we have used by definition, $a(k)^{2}=(\|\bar{y}(k)-\bar{x}(k)\|+2\eta\|g(k)\|)^{2}\leq 2\|\bar{y}(k)-\bar{x}(k)\|^{2}+8\eta^{2}\|g(k)\|^{2}$. Now returning to (30), we get,

To prove (19), it remains to check $A_{3}(\eta)$ and $A_{4}(\eta)$ are positive. Plugging in $A_{2}(\eta)=\frac{39\sqrt{n}(\eta L)^{1/3}}{(\sigma)^{2/3}}$ into $A_{3}(\eta)$ and using $(1-\alpha)>\frac{1}{2}$ (equivalent to $\eta<\frac{1}{4\mu}$ using $\alpha=\sqrt{\mu\eta}$, and implied by the step size condition in Theorem 3) , we have

where in the second inequality we have used by the step size condition in Theorem 3, $\eta L<\frac{1}{4}$, and $\frac{512\times 39^{2}(\eta L)^{5/3}}{(1-\sigma)^{2}(\sigma)^{4/3}}<\frac{1}{4}$ ($\Leftarrow\eta<\frac{(1-\sigma)^{1.2}\sigma^{0.8}}{7872L}$). For $A_{4}(\eta)$, similarly plugging in $A_{2}(\eta)$ and using $1-\alpha>\frac{1}{\sqrt{2}}$ ($\Leftarrow\eta<\frac{1}{25\mu}$) and $\alpha=\sqrt{\mu\eta}$, we have

where in the last inequality we have used by the step size condition in Theorem 3, $\frac{\mu}{2}\geq\frac{128\times 39^{2}}{(1-\sigma)^{2}\sigma^{4/3}}\sqrt{L\mu}(\eta L)^{7/6}$ ($\Leftarrow\eta<\frac{\sigma^{8/7}(1-\sigma)^{12/7}}{61909L}(\frac{\mu}{L})^{3/7}$). So we have proven (19).

At last we will prove part (b) of Theorem 3. Using (18), $\phi_{t}^{*}\leq\Phi_{t}(x^{*})\leq f^{*}+O((1-\alpha)^{t})$. Hence $\phi_{t+1}^{*}-f(\bar{x}(t+1))\leq\phi_{t+1}^{*}-f^{*}=O((1-\alpha)^{t})$. Using (32), we have $A_{3}(\eta)\|g(t)\|^{2}+\frac{1-\alpha}{\alpha}A_{4}(\eta)\|\bar{y}(t)-\bar{x}(t)\|^{2}=O((1-\alpha)^{t})$. Therefore, both $\|g(t)\|^{2}$ and $\|\bar{y}(t)-\bar{x}(t)\|^{2}$ are $O((1-\alpha)^{t})$. Then, the $a(t)$ defined in Lemma 3 is $O((1-\alpha)^{t/2})$. By Lemma 3, we also have $\|y(t)-\mathbf{1}\bar{y}(t)\|=O((1-\alpha)^{t/2})$ (where we have used an easy-to-check fact: $\sqrt{1-\alpha}>\theta$). Since $f$ is $\mu$ strongly convex, we have $f(\bar{x}(t))-f^{*}\geq\frac{\mu}{2}\|\bar{x}(t)-x^{*}\|^{2}$ which implies $\|\bar{x}(t)-x^{*}\|=O((1-\alpha)^{t/2})$. Since $\|\bar{x}(t)-x^{*}\|$, $\|\bar{y}(t)-\bar{x}(t)\|$ and $\|y(t)-\mathbf{1}\bar{y}(t)\|$ are all $O((1-\alpha)^{t/2})$, by triangle inequality we have $\|y(t)-\mathbf{1}x^{*}\|=O((1-\alpha)^{t/2})$. Hence, for each $i$, $\|y_{i}(t)-x^{*}\|=O((1-\alpha)^{t/2})$, and therefore by $L$-smoothness of $f$ we have $f(y_{i}(t))-f^{*}=O((1-\alpha)^{t})$.

V Convergence Analysis of Acc-DNGD-NSC

In this section, we will prove Theorem 4 and Theorem 5. We will first provide a proof overview in Section V-A and then defer the detailed proof to the rest of the section.

Overview of the Proof. We derive a series of lemmas (Lemma 8, 9, 10 and 11) that will work for both the vanishing and the fixed step size case. We firstly derive the update formula for the average sequences (Lemma 8). Then, we show that the update rule for the average sequences is in fact CNGD-NSC (3) with inexact gradients , and the inexactness is characterized by “consensus error” $\|y(t)-\mathbf{1}\bar{y}(t)\|$ (Lemma 9). The consensus error is bounded in Lemma 10. Then, we apply the proof of CNGD (see e.g. ) to the average sequences in spite of the consensus error, and derive an intermediate result in Lemma 11. Lastly, we finish the proof of Theorem 4 and Theorem 5 in Section V-C and Appendix-A-I respectively.

As shown above, the proof is similar to that of Acc-DNGD-SC in Section IV. The main difference lies in how we bound the consensus error (Lemma 10) and how we apply the CNGD proof in Section V-C. In what follows, we will mainly focus on the different parts while putting details for the parts that are similar to Acc-DNGD-SC into the Appendix.

We first derive Lemma 8 that characterizes the update rule for the average sequences.

Proof: We omit the proof since these equalities can be easily derived using the fact that $W$ is doubly stochastic and the fact that $\bar{s}(0)=g(0)$. $\Box$

From (LABEL:eq:nsc:update_ave_a)-(LABEL:eq:nsc:update_ave_c) we see that the sequences $\bar{x}(t)$, $\bar{v}(t)$ and $\bar{y}(t)$ follow a update rule similar to the CNGD-NSC in (3). The only difference is that the $g(t)$ in (LABEL:eq:nsc:update_ave_a)-(LABEL:eq:nsc:update_ave_c) is not the exact gradient $\nabla f(\bar{y}(t))$ in CNGD-NSC. In the following Lemma, we show that $g(t)$ is an inexact gradient.

where $\hat{f}(t)=\frac{1}{n}\sum_{i=1}^{n}[f_{i}(y_{i}(t))+\langle\nabla f_{i}(y_{i}(t)),\bar{y}(t)-y_{i}(t)\rangle].$

Proof: We omit the proof since it’s almost identical as the proof of Lemma 2. $\Box$

We then bound in Lemma 10 the consensus error $\|y(t)-\mathbf{1}\bar{y}(t)\|$. The proof of Lemma 10 is given in Section V-B.

$\eta_{0}<\min(\frac{\sigma^{2}}{9^{3}L},\frac{(1-\sigma)^{3}}{6144L})$,

$\sup_{t\geq 0}\frac{\eta_{t}}{\eta_{t+1}}\leq\min((\frac{\sigma+3}{\sigma+2}\frac{3}{4})^{\sigma/28},\frac{16}{15+\sigma})$.

We next provide the following intermediate result, which essentially uses the same construction and derivations in the standard CNGD proof in textbook [36, Lemma 2.2.3].

where $\lambda_{t}$ is defined through $\lambda_{0}=1$, and $\lambda_{t+1}=(1-\alpha_{t})\lambda_{t}$. Further, we have function $\Phi_{t}(\omega)$ can be written as

where $\gamma_{t}$ is defined through $\gamma_{t+1}=\gamma_{t}(1-\alpha_{t})$, and $\phi_{t}^{*}$ is some real number that satisfies $\phi_{0}^{*}=f(\bar{x}(0))$, and

Proof: The proof is almost the same as that of Lemma 4 in the proof of Theorem 3. For completeness we include a proof in Appendix-A-C. $\Box$

Lemma 11 has laid the ground work for proving the convergence of the inexact Nesterov Gradient descent (34) for sequence $\bar{x}(t),\bar{y}(t),\bar{v}(t)$. What remains to be done is to follow the proof strategies of Nesterov Gradient descent, and in the meanwhile carefully control the error caused by the inexactness in Lemma 10. With this guideline, we will finish the proof of Theorem 4 (vanishing step size case) in Section V-C and Theorem 5 (fixed step size case) in Appendix-A-I.

In the context of inexact Nesterov method for convex and smooth functions, the final part of our proof for Theorem 4 essentially shows that for any inexact Nesterov method for sequence $\bar{x}(t)$, $\bar{y}(t)$, $\bar{v}(t)$ with inexact gradient $g(t)$ and step size $\eta_{t}$, when the error at time $t$ depends on past iterates of the form $A(\eta_{t})(\|\bar{x}(t)-\bar{y}(t)\|+\eta_{t}\|g(t)\|)$, where $A(\eta_{t})$ is a constant that depends on $\eta_{t}$ and satisfies $\lim_{\eta\rightarrow 0}\frac{A_{2}(\eta)}{\eta^{2/3}}<\infty$, then the algorithm can have exact convergence if $\eta_{t}=\frac{\eta}{(t+1)^{\beta}}$ for small enough $\eta$ and $\beta\in(0.6,2)$. This stands in contrast to the results in [39, Sec. 6.2] where inexact Nesterov methods diverge when the error is fixed throughout the iterations.

V-B Proof of the Bounded Consensus Error (Lemma 10)

We will frequently use the following straightforward lemma, whose proof can be found in Appendix-A-D. We will also use Lemma 6 in Section IV-B, which still holds under the setting of this section.

Overview of the proof. The proof is divided into three steps. In step 1, we treat the algorithm (33) as a linear system and derive a linear system inequality (46). In step 2, we analyze the state transition matrix in (46) and prove a few spectral properties. In step 3, we further analyze the linear system (46) and bound the state by the input, from which the conclusion of the lemma follows. Throughout the proof, we will frequently use an easy-to-check fact: $\alpha_{t}$ is a decreasing sequence.

in which $\lambda\triangleq\frac{4}{1-\sigma}>1$. Then, we have the following linear system inequality holds.

The derivation of (46) is almost the same as that of (23) (in the proof of Lemma 3) and is deferred to Appendix-A-E.

Step 2: Spectral Properties of $G(\cdot)$. When $\eta$ is positive, $G(\eta)$ is a nonnegative matrix and $G(\eta)^{2}$ is a positive matrix. By Perron-Frobenius Theorem ([48, Theorem 8.5.1]) $G(\eta)$ has a unique largest (in magnitude) eigenvalue that is a positive real with multiplicity $1$, and the eigenvalue is associated with an eigenvector with positive entries. We let the unique largest eigenvalue be $\theta(\eta)=\rho(G(\eta))$ and let its eigenvector be $\chi(\eta)=[\chi_{1}(\eta),\chi_{2}(\eta),\chi_{3}(\eta)]^{T}$, normalized by $\chi_{3}(\eta)=1$. We give bounds on the eigenvalue and the eigenvector in the following lemmas. We defer the proof to Appendix-A-F.