Consider the consensus problem of minimizing $f(x)=\sum_{i=1}^n f_i(x)$ where
each $f_i$ is only known to one individual agent $i$ out of a connected network
of $n$ agents. All the agents shall collaboratively solve this problem and
obtain the solution subject to data exchanges restricted to between neighboring
agents. Such algorithms avoid the need of a fusion center, offer better network
load balance, and improve data privacy. We study the decentralized gradient
descent method in which each agent $i$ updates its variable $x_{(i)}$, which is
a local approximate to the unknown variable $x$, by combining the average of
its neighbors' with the negative gradient step $-\alpha \nabla f_i(x_{(i)})$.
The iteration is $$x_{(i)}(k+1) \gets \sum_{\text{neighbor} j \text{of} i}
w_{ij} x_{(j)}(k) - \alpha \nabla f_i(x_{(i)}(k)),\quad\text{for each agent}
i,$$ where the averaging coefficients form a symmetric doubly stochastic matrix
$W=[w_{ij}] \in \mathbb{R}^{n \times n}$. We analyze the convergence of this
iteration and derive its converge rate, assuming that each $f_i$ is proper
closed convex and lower bounded, $\nabla f_i$ is Lipschitz continuous with
constant $L_{f_i}$, and stepsize $\alpha$ is fixed. Provided that $\alpha <
O(1/L_h)$ where $L_h=\max_i\{L_{f_i}\}$, the objective error at the averaged
solution, $f(\frac{1}{n}\sum_i x_{(i)}(k))-f^*$, reduces at a speed of $O(1/k)$
until it reaches $O(\alpha)$. If $f_i$ are further (restricted) strongly
convex, then both $\frac{1}{n}\sum_i x_{(i)}(k)$ and each $x_{(i)}(k)$ converge
to the global minimizer $x^*$ at a linear rate until reaching an
$O(\alpha)$-neighborhood of $x^*$. We also develop an iteration for
decentralized basis pursuit and establish its linear convergence to an
$O(\alpha)$-neighborhood of the true unknown sparse signal.

本文研究了基于对等网络的去中心化梯度下降方法，分析了参数收敛性与收敛速率，提出了分布式基 pursuit 迭代方法及其收敛性分析。

分散梯度下降的收敛性

On the Convergence of Decentralized Gradient Descent

This paper considers the average consensus problem on a network of digital
links, and proposes a set of algorithms based on pairwise ''gossip''
communications and updates. We study the convergence properties of such
algorithms with the goal of answering two design questions, arising from the
literature: whether the agents should encode their communication by a
deterministic or a randomized quantizer, and whether they should use, and how,
exact information regarding their own states in the update.

本文研究基于成对 “流言” 通信和更新的数字链接网络上的平均共识问题，并提出一组算法。我们研究了这些算法的收敛性质，旨在回答两个设计问题：代理应该通过确定性或随机量化器编码其通信，以及他们应该如何使用自己状态的精确信息来更新。

通过量化通信的流言共识算法

Gossip consensus algorithms via quantized communication

We study the convergence speed of distributed iterative algorithms for the
consensus and averaging problems, with emphasis on the latter. We first
consider the case of a fixed communication topology. We show that a simple
adaptation of a consensus algorithm leads to an averaging algorithm. We prove
lower bounds on the worst-case convergence time for various classes of linear,
time-invariant, distributed consensus methods, and provide an algorithm that
essentially matches those lower bounds. We then consider the case of a
time-varying topology, and provide a polynomial-time averaging algorithm.

本文研究了分布式迭代算法在共识问题和平均问题中的收敛速度，重点是平均问题。首先考虑了固定通信拓扑的情况。证明了一种简单的共识算法适应于平均算法，并且对于各种线性、时不变和分布式共识方法的最坏情况收敛时间提供下界，并提供一种基本匹配这些下界的算法。之后，我们考虑了时变拓扑的情况，并提供了一个多项式时间的平均算法。