【论文笔记】连续时间梯度跟踪算法收敛性分析

文章目录

• 写在前面
• 分布式优化问题
• • 问题描述和假设
  • 算法和变量定义
• 收敛性分析
• • 速度递减
  • 梯度递减
  • 均值一致
  • 最优误差

写在前面

原论文：Convergence Analysis of a Continuous-Time Distributed Gradient Descent Algorithm

本文是Zhang 2021¹的笔记，原论文将Qu 2018²的梯度跟踪算法扩展到连续时间版本，并对收敛性进行分析。我感觉原文变量定义方式不太主流，可能有些错误的地方，因此证明部分自己又重新推导了一遍。欢迎读者检查本文推导部分，如果发现有错误，请评论告诉我，谢谢！

分布式优化问题

问题描述和假设

问题描述
$$\underset{x\in {\mathbb{R}}^d}{\min }f(x)=\frac{1}{n}\sum _{i=1}^n{f}_i(x)$$

假设1：所有$f_i$是$\mu$-强凸函数，即$f_i(x)\ge f_i(y)+\nabla f_i(y{)}^T(x-y)+\frac{\mu }{2}\Vert x-y{\Vert }^2$对全部$x,y\in {\mathbb{R}}^d$成立；且为$L$-光滑，即$\Vert \nabla f_i(x)-\nabla f_i(y)\Vert \le L\Vert x-y\Vert$对任意$x,y$成立。

假设2：图无向连通。

强凸隐含条件：$\Vert \nabla f_i(x)-\nabla f_i(y)\Vert \ge \mu \Vert x-y\Vert$对任意$x,y$成立。

算法和变量定义

定义$x_i,s_i\in {\mathbb{R}}^d$，其中$s_i$是每一个智能体对$\frac{1}{n}\nabla f_i(x_i)$的估计。令$x=[x_1^T,\cdots ,x_n^T{]}^T\in {\mathbb{R}}^{nq}$。

定义$W=-\beta (L\otimes I_d)$。连续时间梯度跟踪算法的更新律如下：
$$\begin{array}{rl}\dot{x}& =Wx-s,\\ \dot{s}& =Ws+{\nabla }^2,\end{array}(1)$$
其中${\nabla }^2:=\mathrm{blkdiag}({\nabla }^2{f}_1,\cdots ,{\nabla }^2{f}_n)\dot{x}$，初始值为任意$x_i(0)$和$s_i(0)=\nabla f_i(x_i(0))$。因此${\sum }_i{s}_i(t)={\sum }_i\nabla f_i(x_i(t))$恒成立。（同样的后面的$w$也满足此性质。）

可以看出，式(1)直接由Qu 2018中的离散形式推导而来。

为了简化证明，定义$w=-s=\dot{x}-Wx$和$q=\dot{x}$。式(1)简化为
$$\begin{array}{rl}\dot{x}& =w+Wx,\\ \dot{w}& =Ww-{\nabla }^2,\end{array}(2)$$
和
$$\begin{array}{rl}\dot{x}& =q,\\ \dot{q}& =2Wq-W^{2}x-{\nabla }^2.\end{array}(3)$$

收敛性分析

理论分析分为以下四步。前三步证明了收敛性，最后一步证明了最优性。（由于我这里向量定义为列向量，原文向量均为行向量，最后计算出来一些系数不太相同。）

速度递减

令$Q=\frac{1}{2}\Vert q{\Vert }^2\ge 0$，$X=\frac{1}{2}\Vert Wx{\Vert }^2\ge 0$。直觉上看，当$x$收敛于一个固定值时，$\dot{x}$也就是$q$必然收敛于0。利用半正定函数$Q$和$X$，以下引理证明了$\Vert q\Vert$的指数收敛性。

引理1：在假设1、2下，有$\Vert q\Vert \le \sqrt{2Q(0)+2X(0)}{e}^{-\mu t}$。

证明：考虑类李雅普诺夫函数$V=Q+X$。对时间求导得到
$$\begin{array}{rl}\dot{V}& =q^T\dot{q}+(Wx{)}^{T}W\dot{x}\\ & =2q^{T}Wq-q^T{W}^{2}x-q^T{\nabla }^2+x^T{W}^{2}q\\ & =2q^{T}Wq-q^T{\nabla }^2\le -\mu q^{T}q=-2\mu Q.\end{array}$$
因此，$\dot{Q}+\dot{X}\le -2\mu Q$，即
$$\begin{array}{rl}Q(t)& \le -X(t)+X(0)+Q(0)+{\int }_0^t-2\mu Q(r)dr\\ & \le X(0)+Q(0)+{\int }_0^t-2\mu Q(r)dr\end{array}$$
由格朗沃尔不等式(Grönwall’s inequality)可得
$$Q(t)\le (X(0)+Q(0))e^{-2\mu t},$$
即$\Vert q\Vert \le \sqrt{2Q(0)+2X(0)}{e}^{-\mu t}$。

格朗沃尔不等式：假设$\alpha ,\beta ,u$为定义在实数区间$I=[a,b]$($b$可以为$\infty$)上的连续实函数，则有

（a） 如果$\beta$非负，且$u$满足如下积分不等式：
$$u(t)\le \alpha (t)+{\int }_a^t\beta (s)u(s)ds,t\in I,$$
​ 那么
$$u(t)\le \alpha (t)+{\int }_a^t\alpha (s)\beta (s)\exp ({\int }_s^t\beta (r)dr)ds,t\in I.$$
（b）如果在之前的条件下，$\alpha$是一个常数，那么
$$u(t)\le \alpha \exp ({\int }_a^t\beta (s)ds),t\in I.$$

梯度递减

令$\bar{x}=\frac{1}{n}{\sum }_i{x}_i$，$\bar{w}=\frac{1}{n}{\sum }_i{w}_i$和${\bar{\nabla }}^2=\frac{1}{n}{\sum }_i{\nabla }^2{f}_i(x_i){\dot{x}}_i$。

引理2：在假设1、2下，有$\Vert \bar{w}\Vert \le \sqrt{\frac{2}{n}(Q(0)+X(0))}{e}^{-\mu t}$。

证明：由式(2)得到，
$$\begin{array}{rl}\dot{\bar{x}}& =\bar{w}\\ \dot{\bar{w}}& =-{\bar{\nabla }}^2\end{array}$$
令$\Pi =\frac{1}{n}11^T\otimes I_d$。由于$\bar{q}=\dot{\bar{x}}=\bar{w}=-\frac{1}{n}{\sum }_i\nabla f_i(x_i)$，有
$$\begin{array}{r}n\Vert \bar{w}{\Vert }^2=n\Vert \bar{q}{\Vert }^2=\Vert \Pi q{\Vert }^2\le \Vert q{\Vert }^2.\end{array}$$

故$\Vert \bar{w}\Vert \le \sqrt{\frac{2}{n}(Q(0)+X(0))}{e}^{-\mu t}$。

均值一致

定义误差矩阵${\delta }_w=w-\Pi w$和${\delta }_x=x-\Pi x$。定义相应的李雅普诺夫函数${\Delta }_w=\frac{1}{2}\Vert {\delta }_w{\Vert }^2$和${\Delta }_x=\frac{1}{2}\Vert {\delta }_x{\Vert }^2$。

引理3（Olfati-Saber 2004³）：令图$\mathcal{G}$是无向图，其拉普拉斯矩阵为$L$。那么${\lambda }_2={\min }_{1^T\delta =0,\delta \ne 0}({\delta }^{T}L\delta /{\delta }^T\delta )$是$L$的第二小特征根。

引理4：在假设1、2下，$w,x$以指数速率达成一致，即
$$\begin{array}{rl}\Vert {\delta }_w\Vert & \le C_1(e^{-\beta {\lambda }_{2}t}+(1+t)e^{-\mu t}),\\ \Vert {\delta }_x\Vert & \le C_2((1+t)e^{-\beta {\lambda }_{2}t}+(1+t{)}^2{e}^{-\mu t}),\end{array}$$
其中$C_1,C_2$为正常数。

证明：（1）根据定义，有${\dot{\delta }}_w+\Pi \dot{w}=W{\delta }_w-{\nabla }^2$，和
$$\begin{array}{rl}{\dot{\Delta }}_w& ={\delta }_w^T(W{\delta }_w-{\nabla }^2)+{\delta }_w^T\Pi {\nabla }^2\\ & \le -2\beta {\lambda }_2{\Delta }_w-{\delta }_w^T{\nabla }^2\\ & \le -2\beta {\lambda }_2{\Delta }_w+L\Vert {\delta }_w\Vert \Vert q\Vert \\ & =-2\beta {\lambda }_2{\Delta }_w+2L\sqrt{{\Delta }_w}\sqrt{Q(0)+X(0)}{e}^{-\mu t}.\end{array}$$
即$\Vert {\delta }_w{\Vert }^{\prime }\le -\beta {\lambda }_2\Vert {\delta }_w\Vert +L\sqrt{2Q(0)+2X(0)}{e}^{-\mu t}$。

注意到$(\Vert {\delta }_w{\Vert }^{\prime }+\beta {\lambda }_2\Vert {\delta }_w\Vert )e^{\beta {\lambda }_{2}t}=(\Vert {\delta }_w\Vert e^{\beta {\lambda }_{2}t}{)}^{\prime }\le L\sqrt{2Q(0)+2X(0)}{e}^{\beta {\lambda }_{2}t-\mu t}$，可得
$$\begin{array}{rl}\Vert {\delta }_w\Vert & \le C_{11}(e^{-\beta {\lambda }_{2}t}+e^{-\mu t}),\beta {\lambda }_2\ne \mu ,\\ \Vert {\delta }_w\Vert & \le C_{12}(t{e}^{-\mu t}+e^{-\mu t}),\beta {\lambda }_2\ne \mu .\end{array}$$
取 C 1 = max ⁡ { C 11 , C 12 } C_1=\max\{C_{11},C_{12}\} C1​=max{C11​,C12​}，可得
$$\Vert {\delta }_w\Vert \le C_1(e^{-\beta {\lambda }_{2}t}+(1+t)e^{-\mu t}).$$
（2）根据定义，有${\dot{\delta }}_x=w+W{\delta }_x-\Pi w$，和
$$\begin{array}{rl}{\dot{\Delta }}_x& ={\delta }_x^T(w+W{\delta }_x-\Pi w)\\ & \le -2\beta {\lambda }_2{\Delta }_x+{\delta }_x^T{\delta }_w\\ & \le -2\beta {\lambda }_2{\Delta }_x+\Vert {\delta }_w\Vert \sqrt{2{\Delta }_x}\end{array}$$
由前面的结论，可得
$$\Vert {\delta }_x{\Vert }^{\prime }\le -\beta {\lambda }_2\Vert {\delta }_x\Vert +C_1(e^{-\beta {\lambda }_{2}t}+(1+t)e^{-\mu t}).$$
同理可得
$$\Vert {\delta }_x\Vert \le C_2((1+t)e^{-\beta {\lambda }_{2}t}+(1+t{)}^2{e}^{-\mu t}).$$

最优误差

最优性由最优状态误差给出，该误差指数收敛。

定理1：在假设1、2下，最优状态误差以指数速率收敛
$$\begin{array}{rl}\Vert x-1\otimes x^{\ast }\Vert & \le C_3((1+t)e^{-\beta {\lambda }_{2}t}+(1+t{)}^2{e}^{-\mu t}),\end{array}$$
其中$C_3$是正常数。

证明：定义$g={\sum }_i\nabla f_i(x_i)=-n\bar{w}$和$\bar{g}={\sum }_i\nabla f_i(\bar{x})$，有
$$\begin{array}{rl}\Vert g-\bar{g}{\Vert }^2& =\Vert \sum _i(\nabla f_i(x_i)-\nabla f_i(\bar{x})){\Vert }^2\\ & \le \sum _i\Vert \nabla f_i(x_i)-\nabla f_i(\bar{x}){\Vert }^2\\ & \le \sum _{i}L\Vert x_i-\bar{x}{\Vert }^2=L\Vert {\delta }_x{\Vert }^2.\end{array}$$
作为结果，我们得到
$$\begin{array}{rl}\Vert x^{\ast }-\bar{x}{\Vert }^2& \le 1/{\mu }^2\Vert \nabla f(x^{\ast })-\nabla f(\bar{x}){\Vert }^2\\ & =1/{\mu }^2\Vert \nabla f(\bar{x}){\Vert }^2=1/(n\mu {)}^2\Vert \bar{g}{\Vert }^2\\ & \le 1/(n\mu {)}^2(\Vert g-\bar{g}\Vert +\Vert g\Vert {)}^2\end{array}$$
注意到$\Vert g-\bar{g}\Vert$可用$\Vert {\delta }_x\Vert$表示，$\Vert g\Vert$可用$\Vert \bar{w}\Vert$表示。因此由引理2和引理5得到
$$\begin{array}{rl}\Vert x-1\otimes x^{\ast }\Vert & \le \Vert {\delta }_x\Vert +\Vert 1\otimes (x^{\ast }-\bar{x})\Vert \\ & \le C_3((1+t)e^{-\beta {\lambda }_{2}t}+(1+t{)}^2{e}^{-\mu t}).\end{array}$$

---

1. M. Zhang, X. Liu, and J. Liu, “Convergence Analysis of a Continuous-Time Distributed Gradient Descent Algorithm,” IEEE Control Syst. Lett., vol. 5, no. 4, pp. 1339–1344, Nov. 2021. ↩︎

2. G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Trans. Control Netw. Syst., vol. 5, no. 3, pp. 1245–1260, Sep. 2018. ↩︎

3. R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1520–1533, Sep. 2004. ↩︎