近年来, 学术界和工业界对分布式优化产生了浓厚的兴趣^[1-3]. 实际应用中的许多经典问题本质上都是分布式优化问题. 例如数据管理问题^[4-5]、资源分配问题^[6-7]、目标检测与跟踪问题^[8-9]、智能电网^[10]等. 在这些应用中, 数据总量规模庞大, 分散在不同的数据中心; 节点计算能力有限, 分散在不同的物理位置. 为了提高这些系统的工作效率, 均离不开分布式优化算法^[11-13].

当前, 多数分布式优化算法的局部代价函数是非时变的. 然而, 在许多动态变化环境中, 局部代价函数可能是时变的. 例如, 传感器网络中的估计问题, 由于受干扰和噪声影响, 每个传感器的观察结果随时间变化. 因此, 动态变化环境的分布式优化须考虑局部代价函数的时变性, 即为分布式在线优化. 在分布式在线优化中, 智能体仅在每一轮动作结束之后才能获得其局部代价函数值, 即智能体无法获取其未来代价函数. 从这个意义上说, 分布式在线优化本质上不同于分布式优化.

近十年来, 机器学习领域主要关注集中式在线优化问题^[14], 定义了一个衡量在线优化算法性能的“悔函数”, 即算法代价与事后最佳行为代价之差^[15]. 受分布式优化的启发, 一些学者开始研究分布式在线优化算法^[16-21]. 具体而言, 针对无约束优化问题, 当代价函数是凸函数时, 可达到悔界$ {\rm O}(\sqrt{T}) $^[16-17]; 当代价函数是强凸函数时, 可达到悔界$ {\rm O}((\log T)^2) $^[18]或悔界$ {\rm O}(\log T) $^[16-17]. 但在实际应用中, 大部分优化问题是受约束的^[22]. 因此针对约束优化问题, 当代价函数是凸函数时, 可达到悔界$ {\rm O}(\sqrt{T}) $^[19-21]; 当代价函数是强凸函数时, 可达到悔界$ {\rm O}(\log T) $^[21].

随着各类智能设备的广泛使用, 许多应用中出现了大数据集, 为了避免在线优化算法投影算子造成的大数据计算瓶颈, 就需要考虑高维约束优化问题^[23]. 为此, 针对高维约束优化的无投影算法应运而生, 即Frank-Wolfe 算法^[24]. 在Frank-Wolfe 算法中, 使用了一个线性优化步骤替代投影算子. 近年来, Frank-Wolfe算法^[25-26]在许多领域广受关注. 此外, 多种Frank-Wolfe算法的变体^[27-31]也相继提出以解决各种类似问题. 但是这些算法都是针对集中式场景, 难以适应分布式应用. 为此, 针对非时变的代价函数提出一种分布式Frank-Wolfe算法^[32]. 但在实际中, 代价函数通常是随时间变化的. 针对此问题提出了无投影分布式在线算法^[33-34], 可以达到凸局部代价函数的悔界$ {\rm O}(T^{3/4}) $. 但这个悔界劣于分布式在线优化算法领域公认的悔界$ {\rm O}(\sqrt{T}) $.

因此, 进一步优化分布式在线学习算法的悔界仍然是一个亟待解决的问题. 本文针对多智能体网络中的高维约束优化问题, 使用Frank-Wolfe步骤替代投影算子, 提出了一种分布式条件梯度在线学习算法, 主要贡献如下:

1) 提出了Frank-Wolfe在线学习算法, 每个智能体仅利用自己及从邻居接收的信息进行分布式在线学习, 解决了某些场景无法使用集中式学习的应用需求.

2) 分析了所提算法的性能. 当局部代价函数为凸时, 算法的悔界为$ {\rm O}(\sqrt{T}) $; 当局部代价函数为非凸时, 算法以速率$ {\rm O}(\sqrt{T}) $收敛于平稳点. $ {\rm O}(\sqrt{T}) $是当前同类算法能够达到的最好性能.

3) 通过仿真实验验证了所提出算法的性能和理论分析的结论.

本文其余部分安排如下: 第1节给出一些预备知识; 第2节对所研究问题进行形式化描述, 并提出了一种分布式条件梯度在线学习算法; 第3节给出了一些假设和主要结果; 第4节对主要结果进行详细证明; 第5节描述了仿真实验与仿真结果; 最后, 对本文进行了总结.

1.   符号及定义

为了方便描述, 本节介绍一些符号约定和数学基础. 在本文中, 所有向量都是列向量, 符号$ {\bf{ R}} $和$ {\bf{ R}}^d $分别表示实数集和$ d $维实欧几里得空间; 符号$ {\bf{ R}}^+ $和$ {\bf{ Z}}^+ $分别表示正实数集和正整数集; 符号$ \langle \cdot, \cdot \rangle $表示实欧几里得空间的内积; 符号$ \left\|\cdot\right\|_2 $表示标准欧几里得范数. 设$\boldsymbol{1}$表示向量中所有元素为1的列向量; $ D $表示约束集$ X $相对于标准欧几里得范数$ \left\|\cdot\right\|_2 $的直径, 例如 $ D = \sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in X}\left\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\right\|_2 $. $ {\rm{E}}\left[X\right] $表示随机变量$ X $的期望值. 设凸紧集$ X $是$ {\bf{R}}^d $的一个子集. 此外, 与函数$ f $相关的一些定义表述如下.

定义 1^[35]. 对于任意的$ \boldsymbol{x}, \boldsymbol{y}\in X $, $ \alpha\in\left[0,1\right] $, 若有$ f\left(\alpha \boldsymbol{x}+\left(1-\alpha\right)\boldsymbol{y}\right)\leq \alpha f\left(\boldsymbol{x}\right)+\left(1-\alpha\right)f\left(\boldsymbol{y}\right) $, 则称函数$ f: X \mapsto \bf{R} $为凸的.

定义 2^[32]. 对于任意的$ \boldsymbol{x}, \boldsymbol{y}\in X $, 若有

则称函数$ f: X \mapsto \bf{R} $为$ \mu $-强凸的, 其中$ \mu $是一个非负常数.

定义 3^[32]. 对于任意的$ \boldsymbol{x}, \boldsymbol{y}\in X $, 若有

则称函数$ f: X \mapsto \bf{R} $为$ \beta $-光滑, 其中$ \beta $是一个正常数. 另外, 式(2)等价于以下关系式

定义 4^[32]. 对于任意的$ \boldsymbol{x}, \boldsymbol{y}\in X $, 若有

则称函数$ f:X \mapsto \bf{R} $为$ L $-Lipchitz, 其中$ L $是一个正常数.

如果函数$ f $是强凸的并且$\boldsymbol{x}^{\ast} = \arg\min_{\boldsymbol{x} \in X} f\left(\boldsymbol{x}\right)$, 则有

此时, 若式(1)中的$ \mu = 0 $, 则称函数$ f $为凸函数.

2.   问题形式化和算法

本文考虑一个由$ N $个智能体组成的网络, 表示为图$ G\left(V,E\right) $, 其中, $ V = \left\{1,\cdots,N\right\} $表示智能体的集合, $ E\subseteq V\times V $表示边的集合. 假设图是固定无向图, 符号$ \left(i,j\right)\in E $表示对于所有的$ i,j\in V $, 智能体$ j $可以直接向智能体$ i $发送信息. 若两个智能体可以直接交换信息, 则它们是邻居. $ { N}_j $表示包括智能体$ j $本身的$ j $的邻居集合. 此外, 使用一个$ N $-by-$ N $邻接矩阵$ \boldsymbol A $表示通信模式, 并假设$ \boldsymbol A $为双随机的, 定义为$ \boldsymbol A = \left[a_{ij}\right] $, $ i,j = 1,\cdots,N $.

本文主要研究分布式在线优化问题, 即每个智能体的局部代价函数随时间变化. 在每轮时隙$ t = 1,\cdots,T $中, 智能体$ i\in\left\{1,\cdots,N\right\} $必须从凸紧集$ X\subset{\bf{R}}^d $中选择一个点$ {\boldsymbol x}_i\left(t\right) $. 此时环境生成一个代价函数$ f_t^i: X\mapsto\bf{R} $作为回报, 并且智能体$ i $产生了代价$ f_t^i\left(\boldsymbol x_i\left(t\right)\right) $. 这样, 就转化为在一个时间范围$ T $内协作优化全局代价函数

其中, 代价函数$ f_t^i: X \mapsto\bf{R} $是凸的或是潜在非凸的, 并对于智能体$ i\in V $在$ t\in\left\{1,\cdots,N\right\} $轮选择动作$ \boldsymbol{x}_i\left(t\right) $后依然是有效的. 由于每个智能体只能利用其本地信息及其与邻居交换的信息, 因此需要设计分布式在线学习算法解决在线优化问题(6).

悔函数是衡量在线算法性能的重要指标, 定义为^[21]

这样, 研究目标转化为设计一个能够解决问题(6)的分布式在线算法, 可以在$ T $时间达到次线性悔界, 即 $ \lim\sup_{T\to\infty}R\left(T\right)/T = 0 $.

本文借鉴集中式Frank-Wolfe在线学习算法^[28], 提出了分布式无投影在线学习算法. 在该算法中, 每一个智能体$ i\in\left\{1,\cdots,N\right\} $线性地组合它自己的估计值和它从邻居接收的估计值, 然后计算一个能够替代局部梯度的聚合梯度. 最后, 每个智能体$ i $执行一个Frank-Wolfe步骤更新它的估计值. 在该算法中, 每个智能体只知道自己的局部信息, 并只采取局部计算和局部通信. 具体算法描述如算法1所示. 相关的更新过程见式(8) ~ (12).

算法1. 基于条件梯度的加速分布式在线学习算法

1) 输入. 起始点$ \boldsymbol{x}_i\left(1\right) $, $ i = 1,\cdots,N $; 最大时间范围$ T $; 双随机矩阵$ \boldsymbol A = \left[a_{ij}\right]\in{\bf{R}}^{N\times N} $; 智能体个数$ N $.

2) for $ t = 1,\cdots,T $ do

3) 　for 每个智能体$ i = 1,\cdots,N $ do

4) 　　　一致性步骤: 与邻居节点$ \boldsymbol{x}_i\left(t\right) $交互, 即执行式(8).

5) 　　　聚合步骤: 计算聚合梯度代替平均梯度, 即执行式(9)和式(10).

6) 　　　Frank-Wolfe步骤: 计算式(11), 并根据式(12)更新估计值$ \boldsymbol{x}_i\left(t\right) $.

7) 　end for

8) end for

9) 输出. 对于所有$ i\in V $, $ \{\boldsymbol{x}_i\left(t\right): 1\leq t\leq T\} .$

算法$1 $中, 一致性步骤为

聚合步骤为

Frank-Wolfe步骤为

其中, $ \gamma\left(t\right)\in\left(0,1\right) $是学习速率.

3.   假设和主要结果

本节首先给出一些算法的假设, 然后描述本文的主要结果. 假设邻接矩阵$ \boldsymbol A = \left[a_{ij}\right]\in{\bf{R}}^{N\times N} $满足以下假设.

假设1. 图$ G $是强连通图, 对于任意的$i,j\in\{1, \cdots, N\}$, 有$ a_{ii}>0 $; 如果$ \left(i,j\right)\in E $, 则$ a_{ij}>0 $, 否则$ a_{ij} = 0 $. 并假设矩阵$ \boldsymbol A $是双随机矩阵, 即对于所有的$ i,j\in V $, 有$ \sum\nolimits_{j = 1}^Na_{ij} = 1 $和$ \sum\nolimits_{i = 1}^Na_{ij} = 1 $.

假设1是为了保证智能体$ i $的信息能直接或间接传输至其他智能体. 该假设在分布式优化领域中是一个标准假设^{[21, 32, 36]}. 需要注意$ \rho\left(\boldsymbol A-\left({1}/{N}\right)\boldsymbol{1}\boldsymbol{1}^{\rm T}\right)<1 $, 其中$ \rho\left(\cdot\right) $是矩阵的谱半径. 因此, $ \exists \lambda\in\left(0,1\right) $, 对于任意$ \boldsymbol{x}\in{\bf{R}}^{N} $, 有

其中, $ \bar{\boldsymbol{x}} = \left(1/N\right)\boldsymbol{1}^{\rm T}\boldsymbol{x} $. 当$ \exists \ t_0\in\bf{Z}^+ $且$ \kappa\in\left(0,1\right] $时, $ \lambda $的上界满足

同时, 从式(14)可以得出

为了分析算法1的收敛性能, 本文分别给出假设2和假设3^{[28, 32]}.

假设 2. 约束集$ X $是凸紧集, 最优集$ X^{\ast} $是非空集. $ \boldsymbol{x}^{\ast}\in X^{\ast} $是函数$ f $的最小值, 其中$ \boldsymbol{x}^{\ast} $是$ X $的内部点, 即$\eta = \inf_{\boldsymbol{x}\in\partial X}\left\|\boldsymbol{x} - \boldsymbol{x}^{\ast}\right\|_2 > 0$, 其中$ \partial X $表示约束集$ X $的边界集.

假设2确保可以有效地求解一个线性函数的最小值.

假设 3. 对于所有的$ i\in\left\{1,\cdots,N\right\} $和$t\in\{1,\cdots, T\}$, 局部代价函数$ f_t^i $是$ \beta $-光滑和$ L $-Lipschitz的.

在Frank-Wolfe算法中, 假设3是一个标准假设^{[28, 30, 32-34]}, 便于理论分析算法的性能. 因此, 本文也采用该假设.

定义$\Delta\left(t\right) = F_t\left(\overline{\boldsymbol{x}}\left(t\right)\right)-F_t\left(\boldsymbol{x}^{\ast}\left(t\right)\right)$, $F_t = \left(1/t\right)\times \sum\nolimits_{\tau = 1}^t f_{\tau},$ $f_t = \left(1/N\right) \sum\nolimits_{i = 1}^N f_t^i ,$ $\boldsymbol{x} ^{\ast} \left(t\right) \in \arg\min_{\boldsymbol{x}\in X} F_t \left(\boldsymbol{x} \right) .$ 这样, 可以通过获取$ \Delta\left(t\right) $的上界得到悔界.

定理 1. 基于假设1 ~ 3, 令步长$\gamma\left(t\right) = 2/ \left(t+2\right)$, 对于任意的智能体$ i\in\left\{1,\cdots,N\right\} $和 $t\in \left\{1,\cdots,T\right\}$, 假设每个代价函数$ f_t^i $都是一个带正常数$ \mu $的$ \mu $-强凸函数. 则$ \exists \ t_0\in\bf{Z}^+ $, 对于所有的$ t\geq t^{\ast} $, 其中$ t^{\ast} $定义为

则有

其中, $C_2 = \sqrt{N}\{[\delta + \dfrac{\beta\left(D+2C_1\right)}{1-\kappa}]+ 2\beta\left(D + 2C_1\right)\}t_0^\kappa\,,$ 且$ \kappa\in\left(0,1\right) $ 和$\delta \in \bf{R}^+\,;$$C_1 = \sqrt{N Dt_0^\kappa } \,,$ $C' = 2\beta D^2\,+$$4 D\beta C_1+4 DC_2 \,,$ $ \theta>1 $.

定理1的证明详见第4节. 由定理1可知, $ F_t(\overline{\boldsymbol{x}}(t)) $以速度$ {\rm O}(1/(t+1)) $收敛到$ F_t(\boldsymbol{x}^{\ast}(t)) $, 而且收敛速度受网络智能体个数以及网络拓扑结构的影响. 由定理1可以得到算法1任意时刻的界, 同时得到算法1的悔界如下.

定理 2. 基于假设1和假设2, 假设对于所有的$ i\in \left\{1,\cdots,N\right\} $和$ t\in\left\{1,\cdots,T\right\} $, 每个代价函数$ f_t^i $是$ L $-Lipchitz和凸的, 并且$ f_t^i $可能是非光滑的. 则对于任意$ \boldsymbol{x}^{\ast}\in X $, 可以得到

其中,

定理2的证明详见第4节. 根据定理2, 可以得到强凸条件下的平方根悔界, 即算法1可实现悔界$ {\rm O}(\sqrt{T}) $, 其中$ T $是一个时间范围. 同时, 可以看到悔界由约束集$ X $的直径$ D $和局部代价函数梯度的上界$ L $决定. 此外, 悔界也受通信网络连通性的影响. 与文献[33]和文献[34]相比, 本文使用了梯度追踪技术^[13]以提高算法的收敛速度. 在文献[33] 和文献[34]中, 它们的悔界都为$ {\rm O}(T^{3/4}) $, 而本文所提算法的悔界为$ {\rm O}(\sqrt{T}) $, 明显优于以上两个工作. 具体比较见表1.

表 1  不同算法的比较

Table 1  Comparison of different algorithms

算法	凸代价函数	非凸代价函数
D-OCG[33]	${\rm O}(T^{3/4})$	—
D-BOCG[34]	${\rm O}(T^{3/4})$	—
本文算法	${\rm O}(\sqrt{T})$	${\rm O}(\sqrt{T})$

下载: 导出CSV 

| 显示表格

当代价函数可能是非凸时, 为了分析算法1的收敛性, 引入对偶间隙的定义为

其中, $\hat{\boldsymbol{v}}(t) \in \arg\min_{\boldsymbol{v}\in X}\langle\nabla F_t(\overline{\boldsymbol{x}}(t)),\boldsymbol{v}\rangle\,.$ 如果$\psi\left(t\right) =$ $0\,, $ 则估计值$ \overline{\boldsymbol{x}}\left(t\right) $是$ \min_{\boldsymbol{x}\in X}F_t\left(\boldsymbol{x}\right) $的固定点. 因此, 本文使用类似文献[25]和文献[30] 的方法分析对偶间隙, 非凸代价函数的收敛结果如下.

定理 3. 基于假设1 ~ 3, 令步长$ \gamma\left(t\right) = 1/t^\kappa $, 其中$ \kappa\in\left(0,1\right) $. 假设每个代价函数$ f_t^i $是非凸的, 并且时间范围$ T $是均等的. 则$ \exists \ t_0\in\bf{Z}^+ $, 对于所有的$ t\geq t_0 $和$ T\geq 13 $, 当$ \kappa\in\left[1/2,1\right) $时, 可以得到

其中,

当$ T\geq 6 $且$ \kappa\in\left(0,1/2\right) $时, 可以得到

其中,

定理3的证明详见第4节. 根据定理3可以得出, 如果$ \kappa\in\left[1/2,1\right) $, 算法1可以在每轮$t\in[T/2\;+ 1,T]$得到收敛速率$ {\rm O}(1/T^ {1-\kappa}) $; 如果当$ \kappa\in\left(0,1/2\right) $, 算法1可以得到收敛速率$ {\rm O}(1/T^\kappa) $. 此外, 当设置$ \kappa = 1/2 $时, 算法可以得到最快的收敛速率$ {\rm O}(1/\sqrt{T}) $. 可以看出, 收敛速率受梯度上界$ L $和约束集直径$ D $的影响.

4.   性能分析

本节分析当代价函数为凸函数或潜在非凸函数时算法1的性能, 并给出主要结果的详细证明. 为了分析算法1的性能, 引入下面3个辅助向量, 并给出几个引理.

引理 1. 对于所有的$ t = 1,\cdots,T $, 有以下关系:

a) $ \bar{\boldsymbol{s}}_{t+1}\left(t+1\right) = \boldsymbol{g}_{t+1}\left(t+1\right) $;

b) $ \overline{\boldsymbol{x}}\left(t+1\right) = \left(1-\gamma\left(t\right)\right)\overline{\boldsymbol{x}}\left(t\right)+\gamma\left(t\right)\overline{\boldsymbol{v}}\left(t\right) $, 其中$\overline{\boldsymbol{v}}\left(t\right) = \left(1/N\right)\sum\nolimits_{i = 1}^N\boldsymbol{v}_i\left(t\right)$.

引理1的证明见附录A. 从引理1可以看出, 更新关系由平均序列$ \bar{\boldsymbol{s}}_t\left(t\right) $和$ \overline{\boldsymbol{x}}\left(t\right) $决定. 下面给出$ \left\|\boldsymbol{z}_i\left(t\right)-\overline{\boldsymbol{x}}\left(t\right)\right\|_2 $的有界性.

引理 2. 基于假设1, 对于某些$ \kappa\in\left(0,1\right] $使$ \gamma\left(t\right) = 1/t^\kappa $, 则对于所有的$ i = 1,\cdots,N $和$ t\geq t_0 $, 有

其中, $ C_1 = \sqrt{N} Dt_0^\kappa $.

引理2的证明见附录B. 从引理2可以看出, 当$ t $趋于无穷大, $ \boldsymbol{z}_i\left(t\right) $和$ \overline{\boldsymbol{x}}\left(t\right) $的均方差趋近于零. 对于所有的$ i\in\left\{1,\cdots,N\right\} $, 下面给出$ \left\|\boldsymbol{S}_t^i\left(t\right)-\boldsymbol{g}_t\left(t\right)\right\|_2 $的有界性.

引理 3. 基于假设1, 存在$ \kappa\in\left(0,1\right) $使得$\gamma\left(t\right) = 1/t^\kappa$, 则对于所有的$ i = 1,\cdots,N $和$ t\geq t_0 $, 有

其中, $C_2 = \sqrt{N} \left\{\left[\delta + \dfrac{\beta\left(D + 2C_1\right)}{1-\kappa}\right]+2\beta(D + 2C_1) \right\} t_0^{\kappa}$, 且对于所有的$ i = 1,\cdots,N $ 和 $ t\geq 1 $, $ \delta $ 满足 $\delta\geq \left\|\boldsymbol{s}_{t+1}^i\left(1\right)-\boldsymbol{\phi}_{t+1}\left(1\right)\right\|_2$.

引理3的证明见附录C. 从引理3可以得出, 当$ t $趋于无穷大时, $ \boldsymbol{S}_t^i\left(t\right) $和$ \boldsymbol{g}_t\left(t\right) $的均方误差趋近于零. 下面利用引理1 ~ 3证明定理 1.

定理 1 证明. 为了描述方便, 首先定义辅助变量$ f_t = \left(1/N\right)\sum\nolimits_{i = 1}^Nf_t^i $和$ F_t = \left(1/t\right)\sum\nolimits_{\tau = 1}^tf_\tau $, 并将常数$ C $定义为

其中, $ \theta>1 $, $ C' = 2\beta D^2+4 D\beta C_1+4 DC_2. $ 显然, 当$ t = t^{\ast} $时, 定理1成立. 然后, 假设对于某些$ t\geq t^{\ast} $, $\Delta\left(t\right)\leq C/({t+1})$成立, 其中$ t^{\ast} $的定义见式(16). 从假设2可知函数$ F_t $是$ \beta $-光滑的, 因此根据引理1中的b), 可以得出

其中, 第1个不等式可由$ F_t $是$ \beta $-光滑函数得出, 第2个不等式依据引理1的b)得出, 第3个不等式根据$ X $的有界性得到. 此外, 对于所有$ i = 1,\cdots,N $和$ \boldsymbol{v}\in X $, 可以得出

其中, 第1个不等式通过在等式加上$ S^i_t (t)$再减去$ \boldsymbol{S}_t^i\left(t\right) $, 由$ \boldsymbol{v}_i\left(t\right)\in\arg\min_{\boldsymbol{v}\in X}\left\langle \boldsymbol{v},\boldsymbol{S}_t^i\left(t\right)\right\rangle $确定; 最后一个不等式通过加上再减去$ \nabla F_t\left(\overline{\boldsymbol{x}}\left(t\right)\right) $得到. 为了得到式(29)的有界性, 需要得到$\left\|\boldsymbol{S}_t^i\left(t\right)- \nabla F_t\left(\overline{\boldsymbol{x}}\left(t\right)\right)\right\|_2$的上界. 根据$ \boldsymbol{g}_t\left(t\right) $的定义, 可以得出

其中, 第1个不等式可依据三角形不等式获得, 第2个不等式由范数的凸性和引理3得出, 第3个不等式利用函数$\left\{f_{\tau}^1,\cdots,f_{\tau}^N\right\}_{\tau = 1}^T$的$ \beta $-光滑性得到, 第4个不等式根据引理2得出. 将式(29)和式(30)代入式(28), 则对任意$ \boldsymbol{v}\in X $, 有

同时, 还可以得到

其中, 第1个不等式依据$ \boldsymbol{x}^\ast\left(t\right) = \arg\min_{\boldsymbol{x}\in X}F_t\left(\boldsymbol{x}\right) $获得, 最后一个不等式依据式(31)和$\hat{\boldsymbol{v}}\left(t\right)\in \arg\min_{\boldsymbol{v}\in X}\left\langle \boldsymbol{v},\nabla F_t\left(\overline{\boldsymbol{x}}\left(t\right)\right)\right\rangle$得到. 此外, 根据$\Delta\left(t\right) = F_t\left(\overline{\boldsymbol{x}}\left(t\right)\right)-F_t\left(\boldsymbol{x}^\ast\left(t\right)\right)$, 可以得出

其中, 最后一个不等式根据式(32)得出.

另外, 假设$ F_t $是$ \mu $-强凸的且$ \boldsymbol{x}^{\ast}\left(t\right) \in \text{int}\left(X\right) $, 其中, $ \text{int}\left(X\right) $表示$ X $的内点集. 则对于某些 $\xi\in \left[0,1\right)$, $ \boldsymbol{x}^{\ast}\left(t\right) $为

其中, $ \boldsymbol{w}\left(t\right)\in\partial X $. 由于$ F_t $是$ \mu $-强凸的, 可以得出

其中, 最后1个不等式根据$\hat{\boldsymbol{v}}\left(t\right)\in\arg\min_{\boldsymbol{v}\in X}\langle\nabla F_t\times \left(\overline{\boldsymbol{x}}\left(t\right)\right),\boldsymbol{v}\rangle$得出. 此外, 还可以得出

其中, 第1个不等式依据下式得出

最后一个不等式根据$ \eta $的定义得出. 根据式(35)和式(36), 可以得到

其中, 最后一个不等式通过设$\xi = \left\langle\nabla F_t\left(\overline{\boldsymbol{x}}\left(t\right)\right), \overline{\boldsymbol{x}}\left(t\right)-\hat{\boldsymbol{v}}\left(t\right)\right\rangle/\left(\mu\eta^2\right)$获得. 因此, 根据式(37), 可以有

为了获得$ \Delta\left(t+1\right) $的上界, 需要得出$f_{t+1}(\overline{\boldsymbol x}(t\;+ 1))-f_{t+1}\left(\boldsymbol{x}^{\ast}\left(t+1\right)\right)$的上界. 由于对于所有的$ i\in \left\{1,\cdots,N\right\} $和$ t\in\left\{1,\cdots,T\right\} $, 每个代价函数$ f_t^i $都是$ \mu $-强凸的, 那么根据$ F_t $的定义, 函数$ F_t $也是$ \mu $-强凸的. 类似地, 假设3表明$ F_t $是$ \beta $-光滑和$ L $-Lipschitz的. 由于$ \boldsymbol{x}^{\ast}\left(t\right)\in\arg\min_{\boldsymbol{x}\in {X}}F_t\left(\boldsymbol{x}\right) $, 则根据$ F_t $的强凸性, 可以得出

其中, 最后一个不等式根据归纳假设得出. 这样, 依据式(39), 还可得出

根据$ F_t $的定义, 有

其中, 第1个不等式由$ F_t\left(\boldsymbol{x}^{\ast}\left(t\right)\right)\leq F_t\left(\boldsymbol{x}^{\ast}\left(t+1\right)\right) $得出, 第2个不等式依据$ F_t $是$ L $-Lipschitz的获得, 最后一个不等式根据$ X $的有界性得到. 依据式(41), 得出

其中, 最后一个不等式根据$ C\geq LD $得到. 由于$ \left\|\overline{\boldsymbol{x}}\left(t\right)-\boldsymbol{x}^{\ast}\left(t+1\right)\right\|_2\leq D $, 可以得出

其中, $ C\geq \max\left\{324L^2/\mu, 9LD\right\} $. 此外, 还可以得到

其中, 最后一个不等式根据不等式$2/(t+2)\leq \sqrt{1/(t+1)}$对所有的$ t\geq 2 $都成立得出. 因此, 根据式(43)和式(44), 得出

其中, 最后一个不等式根据三角不等式得到. 此外, 由于$ f_{t+1} $是$ L $-Lipschitz的, 可以得出

将式(38)和式(46)代入式(33), 可以得到

当$ \Delta\left(t\right)-\gamma\left(t\right)\sqrt{2\mu\eta^2\Delta\left(t\right)}\leq 0 $, 由式(47)得

其中, 最后一个不等式依据$ n\geq 1 $时成立的不等式$\dfrac{1}{n+t-1}\leq\dfrac{n+1}{n}\times\dfrac{1}{n+t}$得出. 根据$ C $的定义, 可得

因此, 得出

当$ \Delta\left(t\right)-\gamma\left(t\right)\sqrt{2\mu\eta^2\Delta\left(t\right)}> 0 $, 根据式(47), 有

其中, 第2个不等式依据不等式$1/\left(t+1\right)- 1/(t\;+ 2)\leq 1/\left(t+1\right)^2$得出, 最后一个不等式根据$ C $的定义得到. 由于函数$ 1/\sqrt{t+1} $是一个单调递减函数, 因此$ t^{\ast} $定义可由式(16)给出.

由于若$ \theta>1 $, 则$ t^{\ast} $值存在. 因此, 如果$ t>t^{\ast} $, 则式(50)的右侧是非正的, 即

则得到算法1任意时刻的界. □

定理1给出了算法1任意时刻的界. 利用定理1, 下面给出定理2的证明.

定理2证明. 引入一个辅助函数:

其中, $ \nabla f_t^i\left(\overline{\boldsymbol{x}}\left(t\right)\right) $表示$ f_t^i $在$ \overline{\boldsymbol{x}}\left(t\right) $处的梯度或次梯度满足$ \left\|\nabla f_t^i\left(\overline{\boldsymbol{x}}\left(t\right)\right)\right\|_2\leq L $. 因此, 可得

由于$ \left\|\nabla f_t^i\left(\overline{\boldsymbol{x}}\left(t\right)\right)\right\|_2\leq L $ 和 $ \left\|\boldsymbol{x}-\boldsymbol{x}^{\ast}\right\|_2\leq D $, 则$ \left\|\nabla \tilde{f}_t^i\left(\boldsymbol{x}\right)\right\|_2\leq 3L $. 因此, 对于所有的$ i\in\left\{1,\cdots,N\right\} $和$ t\in\left\{1,\cdots,T\right\} $, 函数$ \tilde{f}_t^i $是$ 3L $-Lipschitz. 根据$ \tilde{f}_t^i $的定义, 可得

因此, $ \tilde{f}_t^i $是$ \left(L/D\right) $-强凸和$ \left(L/D\right) $-光滑的. 根据定理1, 可得

其中,

且

和

因此, 对任何$ \boldsymbol{x}^{\ast}\in{X} $, 可得

其中, $\tilde{f}_t = \left(1/N\right)\sum\nolimits_{i = 1}^N\tilde{f}_t^i$. 由于$ \tilde{F}_t $是$ \left(L/D\right) $-强凸且$ \boldsymbol{x}^{\ast}\left(t\right) = \arg\min_{\boldsymbol{x}\in{X}}\tilde{F}_t\left(\boldsymbol{x}\right) $, 可得

根据式(54)和式(56), 可得

因此, 对于所有的$ t\geq t^{\ast} $, 可以得出

其中, 利用了$ \tilde{f}_t^i $是$ 3L $-Lipschitze的特性. 从$ t = 1 $到$ t = T $对式(58)求和, 可得

其中, 不等式根据式(55)和以下不等式得出

因此, 根据式(59), 可以得到

其中, 使用了不等式

依据$ f_t $是凸函数, 可以得出

根据式(60)和式(61), 可以得到

□

最后, 本文分析非凸函数时算法1的收敛性能, 即分析对偶间隙的上界, 具体结果如定理3所述. 下面给出定理3的证明.

定理3证明. 根据$ \psi\left(t\right) $的定义, 即式(19), 利用式(33)和$ \gamma\left(t\right) = 1/t^{\kappa} $, 可以得到

其中, 不等式根据引理2和引理3得出. 因此, 根据式(63), 可得

另外, 根据$ \Delta\left(t\right) $的定义, 可得

结合式(64)和式(65), 可以得出

根据$ F_t $的定义, 还可以得到

这样, 根据式(67), 可以得出

其中, 第1个不等式根据$ F_t $和$ f_t $是$ L $-Lipschitz得出, 第2个不等式由$ D $的定义得到, 第3个和第4个不等式依据$\sum\nolimits_{t = T/2+1}^Tt^{-1}\leq \log 2T/\left(T+4\right)\leq \log 2 \leq 1$获得.

从$ t = T/2+1 $到$ t = T $对式(66)求和, 可得

由于$ \gamma\left(t\right) = t^{-\kappa} $, 则当$ \kappa\in\left[1/2,1\right) $, 可以得到

由$ \psi\left(t\right)\geq 0 $和$ \gamma\left(t\right)\geq 0 $, 还可以得到

因此, 对于所有的$ T\geq 6 $, 可得

将式(72)代入式(71), 则对所有的$ T\geq 6 $, 有

其中,

当$ \kappa\in\left(0,1/2\right) $时, 有$ t^{-2\kappa}>t^{-1} $. 因此, 可以得出

利用式(74), 可得

将式(75)代入式(69), 并除以$(1-\kappa)^{-1}(1- (2/3)^{1-\kappa})T^{1-\kappa}$, 可得

其中,

□

5.   仿真实验

仿真实验考虑一个数据平均分布的多智能体网络, 每个节点通过局部通信和局部计算, 与邻居节点协作完成网络中的全局任务, 使用算法1解决网络系统的多分类问题.

在多分类问题中, 每个局部代价函数为

其中, $ \boldsymbol{e}_i\left(t\right)\in{\bf{R}}^d $是类型$ {C} = \left\{1,\cdots,c\right\} $的一个元素, 表示节点$ i $的一个数据实例; $\boldsymbol {X}_i\left(t\right) = [\boldsymbol{x}_1^{\rm T},\cdots, \boldsymbol{x}_c^{\rm T}]\in{\bf{R}}^{c\times d}$表示节点$ i $的一个决策矩阵; 定义${X} = \left\{{X}\in{\bf{R}}^{c\times d}|\left\|{X}\right\|_*\leq \zeta\right\}$, 其中$ \left\|{X}\right\|_* $是$ {X} $的核范数; 学习率设为$ 2/(t+2) $.

本实验在aloi和news20数据集上验证了算法1的性能. 实验1考察节点数对算法1的影响, 当节点分别为4、64、128 和256时算法1的性能如图1所示. 从图1可以看出, 悔界随着节点数量的增加而增加, 且在不同节点数时算法1都是收敛的. 实验2采用64个节点比较算法1与D-OCG^[33]算法的性能, 结果如图2所示. 从图2可以看出, 算法1均比D-OCG算法具有更快的收敛速率. 实验3考察不同网络拓扑对算法1性能的影响, 采用64个节点组成完全图、随机图和循环图三种网络拓扑, 算法1性能如图3所示. 从图3可以看出, 采用完全图拓扑时算法的收敛速率略快于采用随机图^[37]和循环图拓扑时算法的收敛速率.

图 1  在news20和aloi数据集上不同节点数下本文算法的性能

Fig. 1  Performance of the proposed algorithm at different nodes on news20 and aloi datasets

下载: 全尺寸图片 幻灯片

图 2  在news20和aloi数据集上64节点下本文算法和D-OCG算法的性能比较

Fig. 2  The performance comparison between the proposed algorithm and the D-OCG algorithm at 64 nodes on news20 and aloi datasets

下载: 全尺寸图片 幻灯片

图 3  本文算法在具有固定64个节点和不同拓扑结构的news20和aloi数据集上的性能

Fig. 3  Performance of the proposed algorithm on news20 and aloi datasets with fixed 64 nodes and different topologies

下载: 全尺寸图片 幻灯片

6.   结束语

本文研究了多智能体网络系统中的分布式在线约束优化问题, 其中全局代价函数是局部代价函数之和, 且局部代价函数是时变的. 为了解决这个问题, 本文提出了一种分布式条件梯度在线学习算法, 以避免代价高昂的投影算子. 理论分析表明, 对于凸代价函数, 所提算法可以达到悔界$ {\rm{O}}(\sqrt{T}) $, 其中$ T $表示时间范围; 对于非凸代价函数, 所提算法以 $ {\rm{O}}(\sqrt{T}) $的速率收敛到平稳点. 仿真实验验证了所提算法的性能和理论分析的结果. 该算法可为多智能体网络系统的资源分配、数据管理、调度控制等问题提供参考.

附录 A.   引理1的证明

证明. 1) 关系 a) 的证明. 对式(9)从$i = 1,\cdots, N$求和, 其中$ t\geq 1 $, 除以$ N\left(t+1\right) $得到

由于邻接矩阵$ \boldsymbol A $是一个双随机矩阵, 即$\boldsymbol{1}^{\rm T}\boldsymbol A = \boldsymbol{1}^{\rm T}$. 由式(A1)可得

其中, $\boldsymbol{g}_{t+1}\left(0\right) = \frac{1}{N\left(t+1\right)}\sum\nolimits_{\tau = 1}^{t+1}\sum\nolimits_{i = 1}^N\nabla f_{\tau}^i\left(\boldsymbol{z}_i\left(0\right)\right)$. 由于对所有的$i = 1,\cdots,N$和$\tau \geq 1$, 有$\boldsymbol{s}_{\tau}^i\left(0\right) = \nabla f_{\tau}^i \left(\boldsymbol{z}_i\left(0\right)\right)$, 则$ \bar{\boldsymbol{s}}_{t+1}\left(0\right) = \boldsymbol{g}_{t+1}\left(0\right) $.

2)关系 b) 的证明. 根据$ \overline{\boldsymbol{x}}\left(t\right) $的定义以及式(8)和式(12), 可以得出

其中, 最后一个等式根据矩阵$ \boldsymbol A $由双随机矩阵得出, 即$ \boldsymbol{1}^{\rm T}{\boldsymbol A} = \boldsymbol{1}^{\rm T} $, 且$ \overline{\boldsymbol{v}}\left(t\right) = \left(1/N\right)\sum\nolimits_{i = 1}^N\boldsymbol{v}_i\left(t\right) $. □

附录 B.   引理2的证明

证明. 根据范数的性质, 有

为了证明引理2, 只需要证明不等式

下面对$ t $使用归纳法证明式(B2). 可以看出, 从$ t = 1 $到$ t = t_0 $, 式(B2)成立. 假设对于某些$t\geq t_0$, 式(B2)也成立. 由于当$\kappa\in\left(0,1\right],$ 有$ \gamma\left(t\right) = t^{-\kappa} $, 则有$\boldsymbol{x}_i(t+1) = (1-t^{-\kappa})\boldsymbol{z}_i(t) + t^{-\kappa}\boldsymbol{v}_i\left(t\right)$. 因此, 根据引理1 的b), 可以得到

其中, 最后一个不等式依据式(13)得到. 为了获得$ \sum\nolimits_{i = 1}^N\left\|\boldsymbol{z}_i\left(t+1\right)-\overline{\boldsymbol{x}}\left(t+1\right)\right\|_2^2 $的上界, 需要得到

的上界. 为此, 首先有

其中, 第1个不等式依据柯西−施瓦兹不等式、约束集$ X $的有界性和不等式$ \sum\nolimits_{i = 1}^N\left|w_i\right|\leq\sqrt{N}\sqrt{\sum\nolimits_{i = 1}^Nw_i^2} $得到. 第2个和第3个不等式由归纳假设得到. 因此, 根据式(14), 对于所有的$ t\geq t_0 $, 有

其中, 第2个不等式根据函数$ \varphi\left(\nu\right) = \left(\nu/\left(1+\nu\right)\right)^\kappa $是关于$ \nu $的单调递增函数得到. 结合式(14)和式(B5), 可以得到

因此, 式(B2)成立. □

附录 C.   引理3的证明

证明. 首先, 利用范数的性质, 有

为了证明式(25), 只需证明式(C2)

其中, $C_2 = \sqrt{N}[[\delta+\frac{\beta\left(D+2C_1\right)}{1-\kappa}]+2\beta\left(D+2C_1\right)]\times t_0^{\kappa}$, 且对于所有的$ i = 1,\cdots,N $和$ t\geq 1 $, $ \delta $是一个满足$\delta\geq\left\|\boldsymbol{s}_{t+1}^i\left(1\right)- \boldsymbol{\phi}_{t+1}\left(1\right)\right\|_2$的正常数.

下面采用归纳法证明式(C2). 可以看出, 从$ t = 1 $到$ t = t_0 $, 式(C2)成立. 假设对于某个$ t $, 式(C2)成立. 引入一个辅助变量$\sigma f_{\tau}^i\left(t+1\right) = \nabla f_{\tau}^i\left(\boldsymbol{z}_i\left(t+1\right)\right)- \nabla f_{\tau}^i\left(\boldsymbol{z}_i\left(t\right)\right)$, 将其代入式(9), 可以得到

根据$ \boldsymbol{S}_t^i\left(t\right) $的定义, 有

其中, 不等式依据式(9)和式(13)得出. 根据$ \boldsymbol{g}_t\left(t\right) $的定义, 可以得到

其中, ${\boldsymbol \phi}_{t+1}\left(t+1\right) = \left(1/N\right)\sum\nolimits_{i = 1}^N\nabla f_{t+1}^i\left(\boldsymbol{z}_i\left(t+1\right)\right)$. 并且可以进一步得到

其中, 第1个不等式依据三角不等式得出, 最后一个不等式根据式(13)获得. 另外, $\|\sigma f_{t+1}^i(t+1)\,- [\boldsymbol\phi_{t+1}(t+1)- \boldsymbol\phi_{t+1}\left(t\right)]\|_2$由式(C7)进行计算

其中, 最后一个不等式依据$ \boldsymbol\phi_{t+1}\left(t+1\right) $的定义得出. 将式(C7)代入式(C6), 得到

根据$ \sigma f_{t+1}^i\left(t+1\right) $的定义, 可以得到

其中, 第1个不等式根据式(4)得到, 第2个不等式可由欧几里得范数的凸性和三角不等式推出, 第3个不等式依据式(12)和三角不等式获得, 第4个不等式从引理1推出. 将式(C9)与(C8)合并, 可以得到

其中, 最后一个不等式根据下面不等式得出

其中, $\lambda\in\left(0,1\right) .$ 此外, 还可以得到

其中, 第1个不等式根据欧几里得范数的凸性推出, 第2个不等式依据三角不等式获得, 第3个不等式从式(C9)推出, 第4个不等式依据$ N $是一个正整数得到. 将式(C10)和式(C11)代入式(C4), 并使$ \left\|\boldsymbol{s}_{t+1}^i\left(1\right)-\boldsymbol\phi_{t+1}\left(1\right)\right\|_2\leq \delta $, $ \delta $是一个正常数. 则对于所有的$ i\in\left\{1,\cdots,N\right\} $, 可以得到

其中, 第1个不等式依据三角不等式、柯西−施瓦兹不等式和不等式$ \sum\nolimits_{i = 1}^N\left|w_i\right|\leq\sqrt{N}\sqrt{\sum\nolimits_{i = 1}^Nw_i^2} $推出, 第2个不等式根据归纳假设获得, 最后一个不等式从$ C_2 $的定义得到. 依据式(14), 对于所有的$ t\geq t_0 ,$ 可以得出

由此, 对式(C12)两边取平方根完成归纳. 然后, 将式(C1)和式(C2)结合, 即完成引理3的证明. □