有向网络分布式优化的Barzilai-Borwein梯度跟踪方法

高 娟,刘新为

(1.河北工业大学人工智能与数据科学学院,天津 300401;2.河北工业大学数学研究院,天津 300401)

1 引言

随着大数据时代的到来和多智能体系统协调技术的发展,分布式优化受到了学术界和工业界越来越多的关注,现已被广泛应用于分布式机器学习[1]、编队控制[2]、多智能体目标搜索[3]、无线网络[4]和协调控制[5]等领域.这些实际问题通常被建模为最小化网络上多个局部损失函数的平均值.网络中智能体之间的通信通常可以抽象为一个图.由于实际中许多网络的拓扑结构是复杂的且不是双向的,如基于广播的通信协议[6],所以基于有向图的分布式优化问题受到了众多学者的关注和青睐[7–8].本文主要关注基于有向图的分布式优化问题以及求解这类问题的优化算法.

分布式梯度下降(distributed gradient descent,DG D)算法[9–10]已经成为求解多智能体网络优化问题最流行的方法之一.当采用衰减步长时,DGD方法可以次线性收敛到最优解,但是收敛速度较慢;当使用固定步长时,DGD方法可以达到线性收敛速度,但是只能收敛到最优解的邻域内.近年来,该算法得到了显著的改进并发展了许多变形,可参考文献[11–18].例如,Shi等[11]通过利用两次连续的DGD迭代的差构造了精确的一阶算法(exact first-order algorithm,EXTR A).当使用固定步长时,该算法可以线性收敛到精确解.然而,该算法要求权重矩阵是对称双随机矩阵.进一步,Xu 等[12]首次将基于动态平均一致性[19]的梯度跟踪技巧与DGD方法相结合提出了分布式梯度跟踪方法.该算法中每个智能体使用不一致固定步长,并且权重矩阵可以是非对称双随机矩阵.当目标函数是光滑和强凸函数时,Nedić等[13]和Qu等[14]证明了该算法线性地收敛到最优解.另外,Berahas等[15]结合了多次一致步技巧和DGD算法,提出了改进的DGD方法.当多次一致步数随着迭代次数增加时,该方法在采用固定步长的情况下可以精确线性地收敛到最优解.最近,Li和Lin[16]进一步研究了EXTRA方法并对其进行了复杂性分析.同时,Li和Lin[16]也将Catalyst加速技巧应用到EXTRA中提出了加速的EXTRA算法,并分析了该算法的通信和计算复杂性.Qu和Li[17]提出了加速的分布式Nesterov梯度跟踪算法,并且分析了该算法的线性收敛性质.Li等[18]提出了两种基于惩罚方法的分布式加速梯度算法.

上述文献中的算法仅适用于基于无向图的分布式优化问题,这些算法要求构造双随机权重矩阵.然而对于基于有向图的分布式优化问题,网络拓扑结构可能是非平衡的,因此构造双随机权重矩阵是件不切实际的事情.于是,Nedić和Olshevsky[20–21]将Push-sum技巧[22]与DGD方法结合提出了求解有向网络优化问题的分布式梯度推力(gradient-push,GP)算法.该方法采用了列随机权重矩阵并且利用Push-sum方法学习该矩阵的特征向量来消除有向图的非平衡性.然而在GP方法中,由局部梯度引起的误差,学习特征向量所需要的迭代以及衰减步长都可能恶化算法的性能表现.

为了消除由局部梯度引起的误差,许多学者提出了改进的方法,如参考文献[23–28].结合EXTRA和GP算法,Zeng等[23]和Xi等[24]提出了快速的分布式算法,并证明了其线性收敛性质.然而该分布式算法的步长范围比较严格,即步长的最大下界严格大于0.文献[25–28]提出了基于梯度跟踪的方法.对于光滑和强凸函数来说,与GP算法的次线性收敛不同,这些方法[25–28]被证明可以线性地收敛到最优解.例如,Xi等[25]提出了加速的基于有向图的分布式优化方法(accelerated distributed directed optimization,ADD-O PT).ADD-OPT算法结合了列随机权重矩阵,Push-su m技巧和梯度跟踪策略,并放宽了对步长的限制.另一些算法(参见文献[27–28])则使用了行随机权重矩阵,Push-sum技巧和梯度跟踪策略.其中Xin等[28]提出基于不一致固定步长的快速行随机优化算法(fast row-st ochastic optimization with uncoordinated step sizes,FR OST).上述所有的基于有向图的方法都需要专门的迭代来学习行或列随机矩阵的特征向量,这导致此类算法需要额外的计算和通信.最近,通过同时地使用行随机和列随机权重矩阵,Xin和Khan[29]提出了AB算法(文献[30]也研究了该算法).该算法的一个显著特点是它避免了由特征向量估计引起的计算与通信.当目标函数是光滑和强凸函数时,Xin和Khan[29]证明了AB算法的线性收敛性质.进一步,Xin和Khan[31]将AB和Heavy-ball动量加速技巧相结合,提出了分布式Heavy-ball动量加速算法,并证明了该算法对于光滑强凸函数可达到线性收敛速度.Gao等[32]提出了带有参数的分布式动量方法,并证明了其线性收敛性质.该方法是分布式Heavy-ball动量加速算法的一种推广.Li等[33]提出了Nesterov和Heavy-ball双动量加速的分布式异步优化算法,并分析了其收敛性质.

众所周知,梯度类算法中步长的选取对算法的表现起着重要作用.上面提到的算法[9–18,20–21,23–33]涉及两类步长: 一类是一致或者不一致固定步长,在实验中它们被手动调试使得算法达到最佳表现;另一类是衰减步长,当迭代点靠近最优解时,它使得算法收敛速度很慢.这些分布式梯度类方法[9–18,20–21,23–33]没有考虑如何充分利用局部信息为每个智能体选择合适的步长,以此改善算法的数值表现.最近,Gao等[34]将Barzilai-Borwein(BB)方法[35]引入基于无向图的分布式优化中,提出了带有BB步长的分布式梯度方法并证明了该方法具有几何收敛速度.进一步,结合行随机权重矩阵和Push-sum技巧,Hu等[36]将该方法推广到有向图上,提出了ADBB(accelerated distributed BB)算法.此外,这两篇文献中提出的分布式BB方法都需要结合多次一致步内循环技术,这大大地增加了智能体之间的通信成本.

受以自适应截断循环方式生成的BB步长[37]改善梯度法表现的启发,本文给出该BB步长的分布式形式,然后将其引入到AB算法中,从而提出了一种求解基于强连通有向图的优化问题的分布式Barzilai-Borwein梯度跟踪方法,简称AB-BB.该方法中每个智能体利用其局部梯度信息自动地计算步长.与现有的分布式BB方法[34,36]相比,AB-BB方法不需要使用多次一致步内循环技巧.所以,该方法在保证不增加每次迭代的计算和通信成本的基础上通过采用分布式的BB步长策略提高了AB算法的性能.与只采用行随机或列随机权重矩阵的分布式梯度算法[25–28,36]相比,AB-BB算法避免了估计特征向量,从而降低了计算和通信成本.本文在与AB算法相同的假设下,证明了AB-BB算法可以线性地收敛到最优解.最后,本文对所提出的AB-BB算法进行了数值仿真.仿真结果表明了本文所提出的算法的有效性.

本文其余部分结构安排为:第2节描述了所求解的优化问题;第3节提出了新算法;第4节给出了新算法的收敛性结果;第5节为仿真实验;第6节为本文结论.

记智能体i在第k次迭代时的变量为∈Rp.用1n代表元素全为1的n维列向量,In表示n×n阶的单位矩阵,X ⊗Y定义为矩阵X和Y的克罗内克积,ρ(X)表示方阵X的谱半径,diag{x}代表以向量x的元素生成的对角矩阵.给定矩阵S ∈Rn×n,S∞表示为它的无限次幂(如果它存在),即.对于一个本原行随机矩阵A ∈Rn×n,它的特征值为1的左特征向量和右特征向量分别记为πr和1n,且满足1n=1.相应地,对于一个本原列随机矩阵B ∈Rn×n,它的特征值为1的左特征向量和右特征向量分别记为1n和πc,且满足πc=1.由Perron-Frobenius定理[38]有A∞=1n和B∞=πc.符号‖·‖表示为向量或矩阵的欧氏范数.

2 问题描述

考虑由n个智能体组成的有向网络,网络中智能体之间的信息通信通过有向图G=(V,E)来刻画.其中V={1,2,···,n}是所有智能体(节点)构成的集合,E是有向边集且代表智能体之间的通信链路.记={j ∈V|(j,i)∈E}为智能体i的入邻居集合,即该集合中的每个智能体可以将信息发送给智能体i.相应地,记={j ∈V|(i,j)∈E}为智能体i的出邻居集合,即该集合中的每个智能体可以接收智能体i发送的信息.注意,在这里包含智能体i本身.所有智能体协同地求解下列分布式优化问题:

其中:x ∈Rp是全局决策变量;局部损失函数fi:Rp→R是连续可微的,且仅被智能体i所知.本文对目标函数和通信图作出以下标准假设.

假设1对于每个i∈V,它的目标函数fi是Li光滑的,即对∀x,y ∈Rp,存在常数Li>0,使得

假设2对于每个i ∈V,它的目标函数fi是µi强凸的,即对∀x,y ∈Rp,存在常数µi>0,使得

假设3通信图G是强连通的.

3 算法

本节首先介绍了分布式的Barzilai-Borwein步长,然后将其引入到AB算法中并提出了AB-BB算法.

3.1 分布式的Barzilai-Borwein步长

本小节首先回顾原始的Barzilai-Borwein方法.求解问题(1)的原始的BB方法[39]的迭代格式为

文献[37,40–41]中的数值仿真表明,BB方法以交替或自适应的方式使用长BB步长和一些短BB步长,比原始的BB方法[39]的性能要好得多.所以,本文考虑以自适应截断循环方式生成的BB步长[37].显然,直接将该BB步长应用到分布式优化中是一件不切实际的事情.因为它需要计算全局梯度∇f(xk).因此,本文给出该BB步长的分布式形式.

对于每个智能体i,定义

本文给出的分布式BB步长有下列形式:

其中h>0是间隔参数,k≥1是迭代次数,

3.2 Barzilai-Borwein梯度跟踪方法

4 收敛性分析

本节证明了AB-BB算法具有R-线性收敛速度.

以下引理给出了分布式BB步长的取值范围.

引理1设假设1–2成立.对所有的k≥1和i∈V,AB-BB算法中的BB步长满足

下面两个引理对收敛性证明有着重要作用,可参考文献[29].

引理2考虑增广的权重矩阵A和B.对于0<σA<1和0<σB<1,存在向量范数‖·‖A和‖·‖B,对∀a ∈Rnp,有

其中σA=A-A∞A,σB=B-B∞B,以及·A和·B分别是与上述两个向量范数相容的矩阵范数.

根据有限维线性空间中任意两种向量的等价性,存在正数r,l,t,u使得

类似于AB算法的收敛性证明思路,本文也考虑下列3个量:

1)一致误差,‖xk+1-A∞xk+1‖A;

2)最优间隙,‖A∞xk+1-1n ⊗x∗‖;

3)梯度跟踪误差,‖zk+1-B∞zk+1‖B.

本文首先建立了关于上述3个量的一个线性不等式,然后结合该线性不等式和引理1的结果证明了AB-BB算法具有R-线性收敛速度.

为了证明AB-BB算法的线性收敛性质,本文首先需要给出跟踪梯度的上界.

引理4[29]对所有的k≥0,有

其中vk ∈R3和Gc ∈R3×3有下列定义:

上述矩阵中的常数ai,i=1,2,3,4,5和di,i=1,2由下列式子计算得到:a1=σAl‖Inp-A∞‖,a2=(πc)n,a3=‖A∞‖,a4=r‖A-Inp‖,a5=‖A‖,d1=L‖B∞‖,d2=uLσB‖Inp-B∞‖.

证首先,给出一致误差‖xk+1-A∞xk+1‖A的上界.注意到A∞A=A∞.由引理2和式(6a)可知

结合引理4可得

其次,给出最优间隙‖A∞xk+1-1n ⊗x∗‖的上界.由式(6a)有

考虑式(11)的右边第1项,令

其中第1个等式利用了引理3.

考虑θ1.利用文献[14]中的引理10,可知如果0<,则

结合式(11)–(14),可得到

最后,给出梯度跟踪误差‖zk+1-B∞zk+1‖B的上界.根据B∞B=B∞,引理2、假设1和式(6b),得

考虑式(16)的右边第2项.由AA∞=A∞可知,AA∞-A∞是零矩阵.又由式(6a)有

将式(17)代入式(16)并使用引理4,可得

结合式(10),式(15)和式(18)即可得证.以下定理给出了AB-BB算法的主要收敛性结果.

定理1设假设1–3成立.令Ψ=rd1ψ1+d1ψ2+tψ3.定义

证根据文献[38]中的推论8.1.29,本文推导保障参数c的范围和正向量ψ=[ψ1ψ2ψ3]T的值使得Gcψ<ψ.上式可等价地写为

其中Ψ=rd1ψ1+d1ψ2+tψ3.由于式(21)的右边项必须为正,则有

注1定理1表明,当保障参数c满足某个下界时,所提出的AB-BB算法可以线性地收敛到问题(1)的最优解.由定理1可知,最大步长满足,其中πr和πc是元素和为1的正向量.当智能体的个数n比较大时,πc的值相当小.因此,参数c的值不必取为n,并且可以是更小的.从这一点来看,本文所提出的BB步长比ADBB算法中使用的BB步长更加灵活,甚至可能更大.当然,参数c的取值还依赖于一些其他信息,例如范数等价常数和收缩系数,这些信息通常是无法获取的.因此,在实际中,c的上界是不可计算的,本文通过手动调整c的值使得算法达到满意的表现.

注2本文所提出的算法和AB算法在理论上都保证了线性收敛性质,但是它们的收敛速度并不能显式表达.因此无法在理论上明确比较本文的算法与已有算法的收敛速度的快慢.与使用固定步长的AB算法相比,本文所提出的算法的亮点在于每个智能体利用其局部迭代点信息和梯度信息自动地计算其步长.本文通过仿真实验验证了所提出的算法极大地改善了AB算法的数值表现.

5 数值仿真

本节通过测试实际数据集上的分布式逻辑回归问题来验证所提出的AB-BB算法的有效性,并且将其性能与其他算法进行对比.问题模型有下列形式:

图1 不同的参数c对AB-BB算法的影响Fig.1 Comparison of AB-BB with different parameter c

为了研究初始步长对算法的影响,基于a9a数据集,图2对比了AB-BB算法在取不同的初始步长时的结果.从图2中可以看出,AB-BB算法的性能对初始步长的选取并不敏感.

图2 不同的初始步长对AB-BB算法的影响Fig.2 Comparison of AB-BB with different initial step sizes

为了观察间隔参数h对算法的影响,基于a9a数据集,本文针对h=1,2,3,5,8,10对AB-BB算法进行了测试.当h=1时,AB-BB算法中的BB步长退化为BB1步长.从图3可以看出,与h=1相比,当h=2,3,5,8,10时,AB-BB算法的表现更好,这也说明了算法往往比采用单个BB1步长效果好.

图3 不同的间隔参数h对AB-BB算法的影响Fig.3 Comparison of AB-BB with different parameter h

为了进一步说明所提出的算法的有效性,基于a9a和w8a数据集,本文将AB-BB算法与GP[21],ADD-OP T[25],FROST[28],AB[29]和ADBB[36]算法作了比较.

需要注意的是ADD-OPT和FROST每次迭代都有3次信息通信,而GP,AB和AB-BB每次迭代只有2次信息通信.为了公平起见,对于ADBB算法,取多次一致步内循环迭代次数为1,这样ADBB每次迭代有3次信息通信.对于a9a和w8a数据集,AB-BB算法分别选取初始步长=1.5,i ∈V和=2.4,i ∈V,其他算法通过多次手动调试得到最优的步长.图4和图5在2个数据集上对比了所有算法的迭代次数、通信次数和运行时间.平均残差与迭代次数的关系图直观地反映了算法的收敛速度.从图4(a)和图5(a)可以看出,本文所提出的算法实现了线性收敛速度,并且比采用固定步长的分布式算法的收敛速度更快.由图4和图5可以看出,本文所提出的AB-BB算法在迭代次数,通信次数和时间方面都比使用固定步长的算法的表现好很多;与现有的BB方法相比ADBB在迭代次数方面有相似的数值表现,但是在通信次数和时间方面,本文算法的表现比ADBB算法更好些.这是因为本文算法不需要特征向量学习所需的计算和通信成本.

图4 AB-BB算法与其他算法在a9a上的对比Fig.4 Comparison of AB-BB and other methods on a9a

图5 AB-BB算法与其他算法在w8a上的对比Fig.5 Comparison of AB-BB and other methods on w8a

进一步,本文对算法进行了定量分析.基于数据集a9a和w8a,本文对比了所提出的算法与其他算法在平均残差的精度达到10-12时所需迭代次数,通信次数和运行时间.表1给出了所有算法的实验对比数据,其中“–”表示未统计数据.GP算法是次线性收敛,收敛速度较慢,耗时太长,所以本文没有给出关于GP算法的相关数据.从表1中可以观察到,当平均残差达到某个精度时,与其他算法相比,本文所提出的算法需要最少的迭代次数,通信次数和运行时间.这反映了本文所提出的算法比其他算法更加具有优势.

表1 不同算法的实验数据结果Table 1 Experimental data of different algorithms

6 结论

本文提出了一种求解基于强连通有向图的优化问题的分布式Barzilai-Borwein梯度跟踪方法.该方法是在同时使用行和列随机矩阵的AB算法的基础上加入分布式的BB步长得到的方法.本文所提出的方法中每个智能体利用局部梯度信息自动地计算步长,使得算法在不增加计算和通信成本的情况下获得更好的数值表现.当目标函数是光滑和强凸函数时,本文证明了该算法可以线性地收敛到最优解.仿真实验表明,本文算法比使用最优固定步长的AB算法的表现好很多,并且优于一些常用的分布式梯度算法.