这篇文章在对比 C-PSGD 和 D-PSGD 有什么区别。文章采用的是静态的环链路。计算复杂度相同，但是通讯复杂度，C-PSGD 是 $O(n)$，而 D-PSGD 是与图结构相关的复杂度。
贡献：
- 发现当 $n$ 足够大时，由于没有中心资源调度的问题，所以速度会比 C-PSGD 快，而且是线性倍数。
- 当边缘不稳定（宽带带宽非常小或者延迟非常高），那么 D-PSGD 会快很多。
$K$ 表示迭代次数, $n$ 表示节点数，考虑收敛率：
- SGD 对于凸问题 $O(\frac 1 {\sqrt K})$，强凸问题 $O(1/ K)$
- C-PSGD 有 $O(1/ \sqrt{Kn})$
- D-PSGD 一致，但是计算复杂度是凸问题 $O(n / \epsilon^2)$ ，强凸问题是 $O(n / \epsilon)$。提出的算，使得通信和计算可以并行执行，也就是说，可以让通信的时间被覆盖，使得计算速度优于 C-PSGD。
算法步骤（对于每一个节点设备来说）：
- 初始化
- 随机采样若干本地数据
- 计算本地的随机梯度和下降参数 $\nabla$
- 计算相邻设备的参数平均 $x_{k + \frac 1 2, i}$
- 计算新一轮的参数：$x_{k + 1, i} = x_{k + \frac 1 2, i} - \gamma \nabla$
- 迭代足够的次数（回到 2）
- 最终输出 $x_{k, i}$ 的平均。
如果说让全局参数聚合到一个矩阵表示，那么每一轮算法其实就是在：
$$X_{k + 1} = X_k W - \gamma \partial F(X_k ; \xi_k) $$
我们说，这个算法给出了一个 $\epsilon$ 近似解，如果：
$$K^{-1} \left( \sum_{k = 0}^{K - 1} {\mathbb E} \left \| \nabla f\left(\frac {X_k {\bf 1}_n}{n}\right) \right\|^2 \right) \le \epsilon $$
其中 $f(x) = {\mathbb E}_{\xi \sim D} F(x ; \xi)$，也就是在数据集上的平均损失。
如何证明收敛？
根据神秘言论：D-PSGD 收敛性证明的核心逻辑是“共识误差与优化进展解耦”：将去中心化迭代拆解为虚拟中心化 SGD 动力学与节点分歧误差，利用图拉普拉斯谱间隙控制共识收缩，再将分歧误差作为扰动项注入光滑下降不等式，最终通过 telescoping 求和导出非凸优化下的 $O(1/ \sqrt{K})$ 速率。
看不懂思密达
关键假设：
| 假设 | 数学表述 | 作用 |
|---|---|---|
| $L$-Smoothness | $\|\nabla f(x)-\nabla f(y)\| \le L\|x-y\|$ | 保证二次上界与下降步长可控 |
| 有界方差 | $\mathbb{E}[\|g_{i,k}-\nabla f_i(x_{i,k})\|^2] \le \sigma^2$ | 控制随机噪声累积 |
| 双随机图网络 | $W\mathbf{1}=\mathbf{1}, \mathbf{1}^\top W=\mathbf{1}^\top$ | 保证平均序列 $\bar{x}_k$ 无偏漂移 |
具体证明过程暂略，有点复杂（论文 11 页？？？？？？？？？？？？。
结论是，D-PSGD 的收敛速率是 $O(\frac 1 K + \frac 1 {\sqrt{nK}})$，当 $K$ 足够大时，以后者为主导，这说明，如果需要达到一个 $\epsilon$ 近似解，需要 $O(\frac 1 {\epsilon^2})$ 的计算复杂度。
对于图网络，作者设为了：
$$W = \begin{pmatrix} 1 /3 & 1/3 & & & & 1/3 \\ 1/3 & 1/3 & 1/3 & & & \\ & 1/3 & 1/3 & \ddots & & \\ & & \ddots & \ddots & 1/3 & \\ & & & 1/3 & 1/3 & 1/3 \\ 1/3 & & & & 1/3 & 1/3 \end{pmatrix} $$