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

吴庆涛 朱军龙 葛泉波 张明川

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

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

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

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

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

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

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

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

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

1 符号及定义

为了方便描述,本节介绍一些符号约定和数学基础.在本文中,所有向量都是列向量,符号 R 和Rd分别表示实数集和d维实欧几里得空间;符号R+和 Z+分别表示正实数集和正整数集;符号〈·,·〉表示实欧几里得空间的内积;符号‖·‖2表示标准欧几里得范数.设 1 表示向量中所有元素为1 的列向量;D表示约束集X相对于标准欧几里得范数‖·‖2的直径,例如D=supx,x′∈X‖x-x′‖2.E [X] 表示随机变量X的期望值.设凸紧集X是 Rd的一个子集.此外,与函数f相关的一些定义表述如下.

定义 1[35].对于任意的x,y ∈X,α∈[0,1],若有f(αx+(1-α)y)≤αf(x)+(1-α)f(y),则称函数f:XR 为凸的.

定义 2[32].对于任意的x,y ∈X,若有

则称函数f:XR 为μ-强凸的,其中μ是一个非负常数.

定义 3[32].对于任意的x,y ∈X,若有

则称函数f:XR 为β-光滑,其中β是一个正常数.另外,式(2)等价于以下关系式

定义 4[32].对于任意的x,y ∈X,若有

则称函数f:XR 为L-Lipchitz,其中L是一个正常数.

如果函数f是强凸的并且x*=arg minx∈X f(x),则有

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

2 问题形式化和算法

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

本文主要研究分布式在线优化问题,即每个智能体的局部代价函数随时间变化.在每轮时隙t=1,···,T中,智能体i∈{1,···,N}必须从凸紧集X ⊂Rd中选择一个点xi(t).此时环境生成一个代价函数:R 作为回报,并且智能体i产生了代价(xi(t)).这样,就转化为在一个时间范围T内协作优化全局代价函数

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

这样,研究目标转化为设计一个能够解决问题(6)的分布式在线算法,可以在T时间达到次线性悔界,即 l im supT→∞R(T)/T=0.

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

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

算法 1 中,一致性步骤为

聚合步骤为

Frank-Wolfe 步骤为

其中,γ(t)∈(0,1) 是学习速率.

3 假设和主要结果

本节首先给出一些算法的假设,然后描述本文的主要结果.假设邻接矩阵A=[aij]∈RN×N满足以下假设.

假设1.图G是强连通图,对于任意的i,j ∈{1,···,N},有aii＞0 ;如果 (i,j)∈E,则aij＞0,否则aij=0 .并假设矩阵A是双随机矩阵,即对于所有的i,j ∈V,有

假设1 是为了保证智能体i的信息能直接或间接传输至其他智能体.该假设在分布式优化领域中是一个标准假设[21,32,36].需要注意ρ(A-(1/N)11T)＜1,其中ρ(·) 是矩阵的谱半径.因此,∃λ ∈(0,1),对于任意x∈RN,有

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

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

假设 2.约束集X是凸紧集,最优集X*是非空集.x*∈X*是函数f的最小值,其中x*是X的内部点,即η=infx∈∂X‖x-x*‖2＞0,其中∂X表示约束集X的边界集.

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

假设 3.对于所有的i∈{1,···,N}和t ∈{1,···,T},局部代价函数是β-光滑和L-Lipschitz 的.

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

定理 1.基于假设1～3,令步长γ(t)=2/(t+2),对于任意的智能体i∈{1,···,N}和t ∈{1,···,T},假设每个代价函数都是一个带正常数μ的μ-强凸函数.则∃t0∈Z+,对于所有的t≥t*,其中t*定义为

则有

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

定理 2.基于假设1 和假设2,假设对于所有的i ∈{1,···,N}和t ∈{1,···,T},每个代价函数是L-Lipchitz 和凸的,并且可能是非光滑的.则对于任意x*∈X,可以得到

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

表1 不同算法的比较Table 1 Comparison of different algorithms

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

定理 3.基于假设1～3,令步长γ(t)=1/tκ,其中κ∈(0,1).假设每个代价函数是非凸的,并且时间范围T是均等的.则∃t0∈Z+,对于所有的t≥t0和T≥13,当κ∈[1/2,1) 时,可以得到

当T≥6 且κ∈(0,1/2) 时,可以得到

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

4 性能分析

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

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

引理1 的证明见附录A.从引理1 可以看出,更新关系由平均序列(t) 和(t) 决定.下面给出‖zi(t)-(t)‖2的有界性.

引理 2.基于假设1,对于某些κ∈(0,1] 使γ(t)=1/tκ,则对于所有的i=1,···,N和t≥t0,有

引理2 的证明见附录B.从引理2 可以看出,当t趋于无穷大,zi(t) 和(t) 的均方差趋近于零.对于所有的i∈{1,···,N},下面给出的有界性.

引理 3.基于假设1,存在κ∈(0,1) 使得γ(t)=1/tκ,则对于所有的i=1,···,N和t≥t0,有

引理3 的证明见附录C.从引理3 可以得出,当t趋于无穷大时,(t) 和gt(t) 的均方误差趋近于零.下面利用引理1～3 证明定理 1.

定理 1 证明.为了描述方便,首先定义辅助变量,并将常数C定义为

其中,θ＞1,C′=2βD2+4DβC1+4DC2.显然,当t=t*时,定理1 成立.然后,假设对于某些t≥t*,Δ(t)≤C/(t+1) 成立,其中t*的定义见式(16).从假设2 可知函数Ft是β-光滑的,因此根据引理1中的b),可以得出

其中,第1 个不等式可由Ft是β-光滑函数得出,第2 个不等式依据引理1 的b)得出,第3 个不等式根据X的有界性得到.此外,对于所有i=1,···,N和v∈X,可以得出

其中,第1 个不等式可依据三角形不等式获得,第2 个不等式由范数的凸性和引理3 得出,第3 个不等式利用函数的β-光滑性得到,第4 个不等式根据引理2 得出.将式(29)和式(30)代入式(28),则对任意v∈X,有

同时,还可以得到

其中,第1 个不等式依据x*(t)=arg minx∈X Ft(x)获得,最后一个不等式依据式(3 1) 和(t)∈arg minv∈X〈v,∇Ft((t))〉 得到.此外,根据Δ(t)=Ft((t))-Ft(x*(t)),可以得出

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

另外,假设Ft是μ-强凸的且x*(t)∈int(X),其中,i nt(X) 表示X的内点集.则对于某些ξ ∈[0,1),x*(t) 为

其中,w(t)∈∂X.由于Ft是μ-强凸的,可以得出

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

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

为了获得 Δ (t+1) 的上界,需要得出ft+1((t+1))-ft+1(x*(t+1)) 的上界.由于对于所有的i ∈{1,···,N}和t∈{1,···,T},每个代价函数都是μ-强凸的,那么根据Ft的定义,函数Ft也是μ-强凸的.类似地,假设3 表明Ft是β-光滑和L-Lipschitz的.由于x*(t)∈arg minx∈X Ft(x),则根据Ft的强凸性,可以得出

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

根据Ft的定义,有

其中,第1 个不等式由Ft(x*(t))≤Ft(x*(t+1))得出,第2 个不等式依据Ft是L-Lipschitz 的获得,最后一个不等式根据X的有界性得到.依据式(41),得出

其中,最后一个不等式根据C≥LD得到.由于‖(t)-x*(t+1)‖2≤D,可以得出

其中,C≥max{324L2/μ,9LD}.此外,还可以得到

其中,最后一个不等式根据不等式2/(t+2)≤对所有的t≥2 都成立得出.因此,根据式(43)和式(44),得出

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

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

其中,最后一个不等式依据n≥1 时成立的不等式得出.根据C的定义,可得

因此,得出

其中,第2 个不等式依据不等式1/(t+1)-1/(t+2)≤1/(t+1)2得出,最后一个不等式根据C的定义得到.由于函数是一个单调递减函数,因此t*定义可由式(16)给出.

由于若θ＞1,则t*值存在.因此,如果t＞t*,则式(50)的右侧是非正的,即

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

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

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

因此,对任何x*∈X,可得

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

因此,对于所有的t≥t*,可以得出

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

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

其中,使用了不等式

依据ft是凸函数,可以得出

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

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

定理3 证明.根据ψ(t) 的定义,即式(19),利用γ(t)=1/tκ式(33)和,可以得到

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

另外,根据 Δ (t) 的定义,可得

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

根据Ft的定义,还可以得到

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

其中,第1 个不等式根据Ft和ft是L-Lipschitz 得出,第2 个不等式由D的定义得到,第3 个和第4 个不等式依据获得.

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

由于γ(t)=t-κ,则当κ∈[1/2,1),可以得到

由ψ(t)≥0 和γ(t)≥0,还可以得到

因此,对于所有的T≥6,可得

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

利用式(74),可得

将式(75) 代入式(69),并除以(1-κ)-1(1-(2/3)1-κ)T1-κ,可得

5 仿真实验

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

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

本实验在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 结束语

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

附录 A 引理1 的证明

证明.1) 关系 a) 的证明.对式(9)从i=1,···,N求和,其中t≥1,除以N(t+1) 得到

由于邻接矩阵A是一个双随机矩阵,即1TA=1T.由式(A1)可得

其中,最后一个等式根据矩阵A由双随机矩阵得出,即 1TA=1T,且

附录 B 引理2 的证明

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

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

下面对t使用归纳法证明式(B2).可以看出,从t=1 到t=t0,式(B2)成立.假设对于某些t≥t0,式(B2)也成立.由于当κ∈(0,1],有γ(t)=t-κ,则有xi(t+1)=(1-t-κ)zi(t)+t-κvi(t).因此,根据引理1 的b),可以得到

的上界.为此,首先有

其中,第1 个不等式依据柯西-施瓦兹不等式、约束集X的有界性和不等式得到.第2 个和第3 个不等式由归纳假设得到.因此,根据式(14),对于所有的t≥t0,有

其中,第2 个不等式根据函数φ(ν)=(ν/(1+ν))κ是关于ν的单调递增函数得到.结合式(14)和式(B5),可以得到

因此,式(B2)成立.

附录 C 引理3 的证明

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

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

下面采用归纳法证明式(C2).可以看出,从t=1 到t=t0,式(C2) 成立.假设对于某个t,式(C 2) 成立.引入一个辅助变量,将其代入式(9),可以得到

其中,不等式依据式(9)和式(13)得出.根据gt(t)的定义,可以得到

其中,第1 个不等式依据三角不等式得出,最后一个不等式根据式(13) 获得.另外,‖σ(t+1)-[φt+1(t+1)-φt+1(t)]‖2由式(C7)进行计算

其中,最后一个不等式依据φt+1(t+1) 的定义得出.将式(C7)代入式(C6),得到

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

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

其中,λ∈(0,1).此外,还可以得到

其中,第1 个不等式根据欧几里得范数的凸性推出,第2 个不等式依据三角不等式获得,第3 个不等式从式(C9)推出,第4 个不等式依据N是一个正整数得到.将式(C10)和式(C11)代入式(C4),并使,δ是一个正常数.则对于所有的i∈{1,···,N},可以得到

其中,第1 个不等式依据三角不等式、柯西-施瓦兹不等式和不等式推出,第2 个不等式根据归纳假设获得,最后一个不等式从C2的定义得到.依据式(14),对于所有的t≥t0,可以得出

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