标题：Linear convergence in optimization over directed graphs with row-stochastic matrices
中文翻译：行随机矩阵有向图优化的线性收敛性
Abstract
本文研究的是一个多智能体网络（有向图）上的分布式优化问题，其中目标函数是每个玩家成本函数的总和。
现存的在有向图上的分布式优化算法都至少需要每个玩家知道其邻居的出度。但本文不需要。而且最佳收敛速度为\(O(\mu^{k}), 0 < \mu < 1, k\) is the number of 迭代。
前提是目标函数为强凸函数，且具有Lipschitz连续梯度。
1. Introduction
近年来出现了许多分布式优化方法，最初的方法是基于梯度下降，这种方法直观且计算简单，但由于算法使用的步长逐渐减小，通常速度较慢。证明了任意凸函数的收敛速度为\(O(\frac{\ln k}{\sqrt{k}})\)，强凸函数的收敛速度为\(O(\frac{\ln k}k)\)。
后来，发展出基于拉格朗日对偶变量的方法，例如分布式对偶分解[15]、分布式实现交替方向乘法器[16 - 18]。对于强凸函数收敛速度将达到\(O(\mu^k)\)，缺点是计算代价比较高。
再后来，为了兼顾收敛速度和计算简易性，一些分布式算法在保持步长不变的前提下，不使用对偶变量。例如分布式Nesterov-based方法，对于任意满足有界和Lipschitz梯度的凸函数，收敛速度达到\(O(\frac{\ln k}{k^2})\)。还例如[20], [21]中的方法，用固定步长和历史梯度信息实现了对一般凸函数\(O(\frac{1}{k})\)，强凸函数\(O(\mu^k)\)的收敛速度。
但是上面这些方法都是在基于无向图或者权重平衡图上考虑的。但是实际中更多的是权重不平衡有向图的情况，所以这篇论文就是来解决这个问题的。
怎么解决呢？一般分布式优化中通常需要双随机矩阵，可是有向图中得不到双随机矩阵，只能得到行随机矩阵或者列随机矩阵。本文提出的算法参考了[36]。
Notation：
小写字母是标量，小写粗体是向量，大写字母是矩阵
The spectral radius of a matrix A is \(\rho(A)\)。谱半径就是A的特征值绝对值的最大值
\(\lambda_{i}(A)\) denotes the \(i-th\) largest eigenvalue of A.
对于一个最简的行随机矩阵A，将其特征值1的右特征向量记为\(1_n\)，左特征向量记为\(\pi ^T\)，使得\(\pi ^T \cdot 1_n = 1\)。
\(\|\cdot\|\)被定义为一个特殊的矩阵范数，在Lemma2中会讲到
\(\|\cdot\|_2\)就是普通的向量或者矩阵的二范数
有性质： \[ \begin{aligned}c'\|\cdot\|\leq\|\cdot\|_2\leq c\|\cdot\| \\d'\|\cdot\|_2\leq\|\cdot\|\leq d\|\cdot\|_2\end{aligned} \\ c', c, d', d\,are\,some\,positive\,constants \]
更多关于向量和矩阵范数的知识，参考[37]
2. Problem, Assumptions, Algorithm
Problem：
把问题描述为一个强连通有n个玩家的有向图：\(\mathcal{G}=(\mathcal{V},\mathcal{E})\)。注意若\((i, j) \in \mathcal{E}\)，则\(j\)可以发信息给\(i\)。定义\(\mathcal{N}_i^{in}\)为\(i\)自己加上\(i\)的邻居，这个集合也就是能发信息给\(i\)的玩家集合。
我们要的目标函数是这个：\(min\,f(\mathbf{x})=\sum_{i=1}^nf_i(\mathbf{x})\)
需要注意\(f_i\)是凸且可微的，并且只有玩家\(i\)知道。
Assumption 1：有向图是强连通的。
Assumption 2：每个\(f_i\)是可微且强凸的。且对x导数（梯度）具有Lipschitz连续。具体来说，\(f_i\)满足如下两个定义：
\(f_i(\mathbf{x}_1)-f_i(\mathbf{x}_2)\leq\nabla f_i(\mathbf{x}_1)^\top(\mathbf{x}_1-\mathbf{x}_2)-\frac{s}{2}\|\mathbf{x}_1-\mathbf{x}_2\|_2^2\)，s是正整数
\(\|\nabla f_i(\mathbf{x}_1)-\nabla f_i(\mathbf{x}_2)\|_2\leq l\|\mathbf{x}_1-\mathbf{x}_2\|_2\)，l是正整数
因为\(f\)是所有\(f_i\)之和，所以\(f\)也是满足强凸和Lipschitz梯度连续的，也就是满足上面那俩式子。显然常数分别为\(ns, nl\)。
Algorithm： \[ \begin{gathered} \mathbf{x}_{k+1,i} =\sum_{j=1}^{n}a_{ij}\mathbf{x}_{k,j}-\alpha\mathbf{z}_{k,i}, \left.\left(\begin{matrix}{1}{\mathrm{a}}\\\end{matrix}\right.\right) \\ \mathbf{y}_{k+1,i} =\sum_{j=1}^{n}a_{ij}\mathbf{y}_{k,j}, (1\mathrm{b}) \\ \mathbf{z}_{k+1,i} =\sum_{j=1}^{n}a_{ij}\mathbf{z}_{k,j}+{\frac{\nabla f_{i}(\mathbf{x}_{k+1,i})}{[\mathbf{y}_{k+1,i}]_{i}}}-{\frac{\nabla f_{i}(\mathbf{x}_{k,i})}{[\mathbf{y}_{k,i}]_{i}}} \left.\left(\begin{matrix}{1}{\mathrm{c}}\\\end{matrix}\right.\right) \end{gathered} \] \(a_{ij}\) 满足下面这个条件： \[ a_{ij}=\begin{cases}&>0,&j\in\mathcal{N}_i^\mathrm{in},\\&0,&\mathrm{otw.},\end{cases}\quad\sum_{j=1}^na_{ij}=1,\forall i \]
\(\alpha > 0\) is a constant step-size
\(\nabla f_{i}(\mathbf{x}_{k,i})\in\mathbb{R}^{p}\) is the gradient of \(f_i\) at \(x_{k, i}\)
\(x_0\) is arbitrary, \(\mathbf{y}_{0,i}=\mathbf{e}_i, \quad \mathbf{z}_{0,i}=\nabla f_i(\mathbf{x}_{0,i})\)
上面的算法中
根据[38]中的Perron-Frobenius定理，(1b)将收敛到矩阵A的左特征向量\(\pi ^T\)。
(1c)使用(1b)来缩放梯度，从而消除了行随机矩阵引起的不平衡。
而且，为了简化证明，其实可以把\(x_{k, i}, z_{k, i}, \nabla f_i(x_{k,i})\),$看成一维的。只要一维的得证了，后续套一个Kronecker production notation就可以把p维的证出来了。
为了简化表达，我们定义下面式子： \[ \begin{aligned} \mathbf{x}_{k}& =[x_{k,1},\cdots,x_{k,n}]^{\top}, \\ \mathbf{Z}_{k}& =[z_{k,1},\cdots,z_{k,n}]^{\top}, \\ \nabla\mathbf{f}_{k}& =\left[\nabla f_1(x_{k,1}),\cdots,\nabla f_n(x_{k,n})\right]^\top, \\ Y_{k}& =[\mathbf{y}_{k,1},\cdots,\mathbf{y}_{k,n}]^\top, \\ \widetilde{Y}_{k}& =\operatorname{diag}(Y_k). \end{aligned} \] 则algorithm 1可以写成以下形式： \[ \begin{gathered} \mathbf{x}_{k+1}= A\mathbf{x}_{k}-\alpha\mathbf{z}_{k}, (2\mathrm{a}) \\ Y_{k+1}= AY_{k}, (2\mathrm{b}) \\ \mathbf{z}_{k+1}= A\mathbf{z}_{k}+\widetilde Y_{k+1}^{-1}\nabla\mathbf{f}_{k+1}-\widetilde Y_{k}^{-1}\nabla\mathbf{f}_{k}, \text{(2c)} \end{gathered} \]
3. Main results
定义：\(Y_\infty=\lim_{k\to\infty}Y_k\)
因为\(Y_k = AY_{k-1} = A^2Y_{k-2} = ...\)
所以\(\operatorname*{lim}_{k\to\infty}Y_{k}=\operatorname*{lim}_{k\to\infty}A^{k}\)（\(Y_1=I_n\)）
又由[38]中的Perron-Frobenius定理，\(Y_k\)将收敛到\(1_n\pi ^ T\)
即\(Y_\infty=\lim\limits_{k\to\infty}Y_k=\operatorname*{lim}\limits_{k\to\infty}A^k=1_n\pi^T\) 继续定义： \[ \begin{aligned} \mathbf{x}^{*}& =x^{*}\mathbf{1}_{n}, \\ \widehat{\mathbf{x}}_{k}& =Y_{\infty}\mathbf{x}_{k}, \\ \widehat{z}_{k}& =Y_{\infty}\mathbf{z}_{k}, \\ \nabla\mathbf{f}^{*}& =[\nabla f_{1}(x^{*}),\cdots,\nabla f_{n}(x^{*})]^{\top}, \\ \nabla\widehat{\mathbf{f}}_{k}& =\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\left[\nabla f_{1}(\widehat{x}_{k}),...,\nabla f_{n}(\widehat{x}_{k})\right]^{\top}, \end{aligned} \]
\[ \begin{aligned} &\tau=\left\|A-I_{n}\right\|_{2}, \\ &\epsilon=\left\|I_{n}-Y_{\infty}\right\|_{2}, \\ &\eta=\operatorname*{max}\left(\left|1-\alpha nl\right|,\left|1-\alpha ns\right|\right) \end{aligned} \]
\(l, s\)出自这： $$ f_i(_1)-f_i(_2)f_i(_1)^(_1-_2)-|_1-_2|_2^2$，s是正整数 \
|f_i(_1)-f_i(_2)|_2l|_1-_2|_2$，l是正整数 \[ 继续定义： \] \[\begin{aligned} &y=\operatorname*{sup}_{k}\left\|Y_{k}\right\|_{2}, \\ &\widetilde{y}=\operatorname*{sup}_{k}\left\|\widetilde{Y}_{k}^{-1}\right\|_{2}. \end{aligned}\]$$
Lemma 1
\(\left\|Y_k-Y_\infty\right\|_2\leq T\gamma_1^k,\quad\forall k.\quad(3) \\ 0 < \gamma < 1 \, and \, 0 < T < \infty\)
推导参考[22]
Lemma 2
For any \(a \in \mathbb{R^n}\), define \(\widehat{\mathbf{a}}=Y_{\infty}\mathbf{a}\). Then there exists \(0<\sigma<1\) such that \[ \left\|A\mathbf{a}-\widehat{\mathbf{a}}\right\|\leq\sigma\left\|\mathbf{a}-\widehat{\mathbf{a}}\right\| \qquad (4) \] Proof:
由[38]中的Perron-Frobenius定理，得\(\rho(A)=1\) and every eigenvalue of A other than 1 is strictly less than \(\rho(A)\)。
We now have： \[ \begin{array}{rcl}AY_\infty&=&A\mathbf{1}_n\pi^\top&=&\mathbf{1}_n\pi^\top&=&Y_\infty,\\Y_\infty Y_\infty&=&\mathbf{1}_n\pi^\top\mathbf{1}_n\pi^\top&=&\mathbf{1}_n\pi^\top&=&Y_\infty,\end{array} \] and thus \(AY_{\infty}-Y_{\infty}Y_{\infty}\) is a zero matrix. Therefore, \[ A\mathbf{a}-Y_\infty\mathbf{a}\quad=\quad(A-Y_\infty)(\mathbf{a}-Y_\infty\mathbf{a}). \]
右边打开：Aa - AYa - Ya + Y^2a = Aa - AYa - Ya + Ya = Aa - AYa = Aa - Ya = 左边
所以 \[ \left\|A\mathbf{a}-Y_\infty\mathbf{a}\right\|\quad\leq\quad\left\|A-Y_\infty\right\|\left\|\mathbf{a}-Y_\infty\mathbf{a}\right\|,\quad\left(5\right) \] 又\(\|A - Y_\infty\| < 1\) 为啥
所以
\(\left\|A\mathbf{a}-\widehat{\mathbf{a}}\right\|\leq\sigma\left\|\mathbf{a}-\widehat{\mathbf{a}}\right\|\)，\(\sigma=\left\|A-Y_{\infty}\right\|\)，且\(0 < \sigma < 1\)
Lemma 3
There exists some constant \(\widetilde{T}\) such that the following inequalities hold for all k >= 1 \[ (a)\left\|\widetilde{Y}_k^{-1}-\widetilde{Y}_\infty^{-1}\right\|_2\leq\widetilde{y}^2\widetilde{T}\gamma_1^k \\ (b)\left\|\widetilde{Y}_{k+1}^{-1}-\widetilde{Y}_{k}^{-1}\right\|_{2}\leq2\widetilde{y}^{2}\widetilde{T}\gamma_{1}^{k} \] Proof:
先推(a) \[ \begin{aligned} \left\|\tilde{Y}_{k}^{-1}-\tilde{Y}_{\infty}^{-1}\right\|_{2}& \leq\left\|\tilde{Y}_{k}^{-1}\right\|_{2}\left\|\tilde{Y}_{k}-\tilde{Y}_{\infty}\right\|_{2}\left\|\tilde{Y}_{\infty}^{-1}\right\|_{2}, \\ &\leq\tilde{y}^{2}\widetilde{T}\gamma_{1}^{k}, \end{aligned} \] 第一个不等号推导见“Distributed Nash Equilibrium Seeking for...”的Lemma 1证明
第二个不等号用了\(\widetilde{y}\)的定义和Lemma 1
再推(b)，用推(a)一样的方法，先推出：
\(\left\|\widetilde{Y}_{k+1}^{-1}-\widetilde{Y}_{k}^{-1}\right\|_2 \le \|\widetilde{Y}_{k+1}\| \cdot \|\widetilde{Y}_{k}^{-1}\| \cdot \|\widetilde{Y}_{k+1} - \widetilde{Y}_k\| \le \widetilde{y}^2 \cdot \|\widetilde{Y}_{k+1} - \widetilde{Y}_k\|\)
又\(\|\widetilde{Y}_{k+1} - \widetilde{Y}_k\| = \|\widetilde{Y}_{k+1} - \widetilde{Y}_{\infty}\ - (\widetilde{Y}_{k} - \widetilde{Y}_{\infty})\| \le \|\widetilde{Y}_{k+1} - \widetilde{Y}_{\infty}\| + \|\widetilde{Y}_{k} - \widetilde{Y}_{\infty}\| \le 2\widetilde{T}\gamma_{1}^{k}\)
所以
\(\left\|\widetilde{Y}_{k+1}^{-1}-\widetilde{Y}_{k}^{-1}\right\|_2 \le 2\widetilde{y}^2\widetilde{T}\gamma_{1}^{k}\)，得证。
剩下来的内容不继续看了，因为需要的知识已经找到了，就是Lemma 3