中文翻译是：非协调步长行随机优化
个人认为在仔细研读了Distributed那篇文章后，再看这篇文章时，会对双随机、列随机、行随机的算法分别有哪些有一个很好的认识。
Abstract
本文讨论了构造不出双随机权值的有向图上的分布优化问题。
现有算法大多采用推和共识算法，利用列随机权值来克服这一问题。列随机权值的形成要求每个代理(至少)知道其输出度，这在诸如基于广播的通信协议中可能是不切实际的。
与此相反，我们描述了一种适用于不要求出度知识的有向图的快速行随机优化算法。
该方法的实现很简单，因为每个代理在本地为传入的信息分配权重，并在本地选择合适的步长。我们证明了对于光滑且强凸函数，在最大步长为正且足够小的前提下，算法线性收敛到最优解。
1. Introduction
第2节阐述了问题和假设。第3节回顾了使用双随机或列随机权值的相关算法，并展示了这些类型算法分析背后的直觉。在第4节中，我们提供了本文提出的主要算法FROST。在第5节中，我们发展了FROST的收敛性质。第6节给出了仿真结果，第7节总结了本文。
下面是Notation：
对于行随机矩阵\(\underline{A}\)，\(\pi_r, 1_n\)分别是其左右Perron特征向量，满足\(\pi_r^T1_n = 1\)
对于列随机矩阵\(\underline{B}\) ，\(1_n, \pi_c\)分别是其左右Perron特征向量，满足\(1_n^T\pi_c = 1\)
\(\|\|_F\)是Frobenius范数，\(\|\|_2\)是欧几里得范数，\(\|\|\)也是一个范数，具体含义看具体那部分的文章
\({\otimes}\)表示Kronecker积。
2. Problem formulation
如果 j 连向 i ，则\((i, j) \in \mathcal{E}\) 另外，目标是最小化总花费，即： \[ \min_{\mathbf{x}}F(\mathbf{x})\triangleq\frac{1}{n}\sum_{i=1}^{n}f_{i}(\mathbf{x}) \]
Assumption 1
图G是无向联通图。
Assumption 2
图G是有向强连通图。
Assumption 3
\(f_i\)是凸函数，且具有有界次梯度。
Assumption 4
\(f_i\)是光滑，且强凸的。（光滑定义：具有连续的导数）
即满足以下式子： \[ \left\|\nabla f_i(\mathbf{x})-\nabla f_i(\mathbf{y})\right\|_2\leq l\|\mathbf{x}-\mathbf{y}\|_2 \\ f_i(\mathbf{y})\geq f_i(\mathbf{x})+\nabla f_i(\mathbf{x})^\top(\mathbf{y}-\mathbf{x})+\frac{\mu}{2}\|\mathbf{x}-\mathbf{y}\|_2^2 \] 第一个就是导数满足Lipschitz连续，所以\(f_i\)肯定光滑。
第二个就是凸函数的定义，因为有不等号右边最后一项的存在，所以\(f_i\)是个强凸函数。
Assumption 5
网络中的每个玩家都知道自己的编号。
Assumption 6
每个玩家知道它的出度。
补充
看到这里。我想先停一下。来看一道题：假设每个玩家有一个初始值xi。如果他们都想知道所有玩家初始值的平均值是多少，应该怎么做？
如果图是平衡的，则用平均一致性算法即可。即类似于：\(\tilde{\sigma}_i^{k+1}=\sum_{j=1}^Na_{ij}\tilde{\sigma}_j^k\)。
如果图不平衡，则采用推和算法。 \[ \begin{aligned} &\nu_{k+1}^{i} =\sum_{j=1}^nb_{ij}\nu_k^j, \\ &\mathbf{x}_{k+1}^{i} =\sum_{j=1}^nb_{ij}\mathbf{x}_k^j \\ &\mathbf{z}_{k+1}^{i} =\frac{\mathbf{x}_{k+1}^i}{\nu_{k+1}^i}, \end{aligned} \] 每一个点维护两个值：x、v（都是一维的）。所谓推，就是点 j 把值xj / 出度推给邻居，把权重vj / 出度推给邻居。所谓和，就是点 i 把所有邻居 j 推来的值加一起得到vi，把所有邻居 j 推来的权重加一起得到xi。
注意到，对于任意时刻k，有：\(\frac{\sum{x_i}}{\sum{v_i}} = \frac{x1 + x2 + ... + xn}{n} = avg\)
当迭代的次数足够大时，信息已经在网络中充分流转。第 i 个点的\(x_i\)会收敛到\(n[\boldsymbol{\pi}_c]_i * avg\)，\(v_i\)会收敛到\(n[\pi_c]_i\)，所以\(\frac{x_i}{v_i} = avg\)。（\(\pi_c\)是列随机矩阵的右Perron特征向量）
即每个点的xi / vi都收敛到全局平均值。
这是一维的情况。
如果每个玩家的初始值是一个向量xi（权重vi仍然不变初始值为1），则一样的，经过推和算法后，每个玩家的zi都收敛到avg（此时avg就是一个向量）。
在推和共识上稍加改动，就可以得到下面这个算法： \[ \begin{aligned} &\nu_{k+1}^{i} =\sum_{j=1}^nb_{ij}\nu_k^j, \\ &\mathbf{x}_{k+1}^{i} =\sum_{j=1}^nb_{ij}\mathbf{x}_k^j-\alpha_k\nabla f_i\left(\mathbf{z}_k^i\right), \\ &\mathbf{z}_{k+1} =\frac{\mathbf{x}_{k+1}^i}{\nu_{k+1}^i}, \end{aligned} \] 下面这个算法只在更新x时加了一个梯度项。
这样的话，当迭代次数足够多时，第 i 个点的\(x_i\)会收敛到\([\boldsymbol{\pi}_c]_i * x^*\)，\(v_i\)会收敛到\(n[\pi_c]_i\)，所以\(\frac{x_i}{v_i} = x^*\)。
Personal Summary
首先是由推和协议衍生出来的算法，推和协议用列随机矩阵可以求出全局平均值（如果玩家动作是动态更新的话，更新sigma时记得+x[i] - xx[i]）。
因此套一个梯度下降就可以解决聚合游戏问题。
如果已知最优解都会收敛到一个值的话，可以直接在推和协议中修改加一个梯度项，使得收敛到最优解。为了加快速度，还可以将普通的梯度项改为考虑全局的梯度项。