基于条件梯度的Adam分布式在线优化算法

张宇衡，李德权，李苏木

（安徽理工大学 数学与大数据学院，安徽 淮南 232001）

近年来，分布式优化在机器学习中的使用受到了较多关注。许多经典问题本质上是分布式优化问题，如数据管理问题、分布式学习问题、资源分配问题等[1]，其主要思想是将大型优化问题分解为更小的、易于处理的子问题，这些子问题由一组具有空间分布特征的节点，通过与其邻近节点相互通信耦合成网络，从而协同合作来解决优化问题。因此，分布式优化算法具有网络规模的可展性、网络拓扑的鲁棒性等优点，并保护了自主决策者的数据隐私。目前流行的分布式算法有分布式次梯度法[2-3]、对偶平均法[4]等。

分布式优化方法通常假设有一个静态的网络目标函数，其要求收集网络中所有节点的数据后再进行决策优化，这种离线的学习方法会带来高昂的通信代价。而网络系统通常处于动态变化和不确定的环境中，目标函数可能是时变的。尤其在线学习情形下，目标函数可以表述为学习者与对手间的重复博弈，学习者使用实时数据流来更新决策，对手则向学习者揭示损失函数，因而目标函数通常是时变的，其本质也是随机优化方法的一种扩展。这种在线学习或优化处理的优点，是可以利用任意改变的代价函数来表示网络系统的不确定性，同时也方便对节点的动态数据流进行实时处理[5-6]。在线优化算法的性能通常用Regret界来表达。根据研究问题的不同，目前提出了两类Regret界的概念。例如，如果估计的参数为固定序列，且所有损失函数都是事后才知道，一般使用静态Regret界来衡量在线优化算法与离线优化器所造成的额外损失。而若感兴趣的参数是时变的，动态Regret界则是一个更为合适的度量，可以衡量瞬时损失与最小损失之间的累积差[7]。

受经典的随机梯度下降算法[8]启发，Diederik等提出了一种可以代替传统随机梯度下降过程的一阶优化算法（Adam）[9]，该算法通过计算梯度的一阶矩估计和二阶矩估计，为不同的参数设计独立的自适应学习率。Adam算法不仅获得了AdamGrad[10]和RMSProp[11]算法的优点，而且能够很好地解决稀疏梯度和噪声问题。同时Adam算法的调参相对简单，因此其在深度学习领域内十分流行，已有许多成功应用。以时变目标函数为特征的分布式优化问题也得到了广泛的研究，DAdam[12]算法将Adam算法扩展到分布式在线优化中，分别对有约束的凸函数和非凸函数进行了收敛性分析。文献[13]提出了基于梯度跟踪的Adam分布式算法，主要研究无约束的在线优化问题，并给出了动态Regret界的收敛性分析。

条件梯度算法在处理大规模机器学习问题上效率较高，近年来引起了大家的关注。条件梯度算法（Frank-Wolfe）主要用于解决一般的约束优化问题。分布式在线学习环境中，文献[14]提出分布式在线条件梯度算法，利用简单的线性优化步骤，避免了代价昂贵的投影运算问题。文献[15]提出的FWAdam算法主要考虑集中式情形下的在线约束问题，优点是将Adam算法与Frank-Wolfe算法相结合来求解带约束的优化问题常见的代价昂贵的投影操作问题，实验结果显示是可行的。

1 分布式在线凸优化问题

1.1 网络拓扑

在分布式计算框架下，网络不需要任何中央协调器，只需各节点通过局部通信来求解带约束的分布式在线优化问题。网络节点间交互信息可建模成图，通过邻接矩阵或者Laplacian矩阵来刻画该网络拓扑。通常使用加权图G=(V,E,W)表示网络，V={1,2,3,…,N}表示节点集合，E=V×V表示网络中所有无向边的集合，W∈RN×N表示图的权重邻接矩阵，wij表示权重矩阵W第i行、第j列的元素。节点i的邻近节点用Ni={j∈V|(j,i)∈E}表示。若矩阵W为双随机矩阵，其特征值为0 ≤σn(W)≤σn-1(W) ≤σn-2(W)≤…≤σ2(W)≤1。文献[4]表明算法收敛速度依赖于刻画网络拓扑的双随机矩阵W的第二大奇异值σ2(W)，由此定义网络谱间隙1-σ2(W)。

1.2 分布式在线优化

在分布式在线优化问题中，在迭代时刻t，以学习者i产生决策xi,t∈κ作为局部估计，提交决策后，学习者可观测到对手返回的fi,t:κ→R，并且每个学习者i仅知道其自身的fi,t。分布式在线优化的目标是生成一系列决策xi,t使得所有代价函数之和最小，即

2 Frank-Wolfe Adam分布式在线算法

2.1 基本假设

定义1对任意x,y∈κ,α∈[0,1]，函数f:κ→R 是凸函数，需满足f(αx+(1-α)y)≤αf(x)+(1-α)f(y)。

定义2对任意x,y∈κ,函数f:κ→R若满足

假设1局部损失函数fi,t对于L2范数是Lipschitz连续的，即存在一个正常数L，有

假设2设D∞为约束可行集κ的直径上界，即对任意的x,y∈κ，有：‖x-y‖ ≤D∞。

2.2 DFWAdam算法

分布式优化相对于集中式优化的优点是提供了一个灵活解决问题的框架。在该框架下，只需要计算各个节点的损失函数，通过节点间相互信息通信来解决最小化全局目标函数，方便对海量数据进行分布式储存和计算。本文主要将文献[15]提出的基于Frank-Wolfe的Adam集中式在线算法拓展到分布式的情形，使用加权平均的方法更新梯度，提出了一种新的基于Frank-Wolfe的Adam分布式在线算法来解决问题（1）。算法1给出了DFWAdam算法的具体步骤：首先采用加权平均的方法来更新局部损失函数的梯度，该方案通过和邻居节点交互信息得到，具体实现见第14行；第8-10行表示更新得到梯度的一阶矩估计和二阶矩估计；然后定义一个新的函数，使用Frank-Wolfe避免投影操作，最后输出更新的决策点xi,t+1，实现步骤见算法1第11-13行。

算法1DFWAdam算法

3 收敛性分析

4 实验与结果

本文分别在合成数据集和真实数据集上进行了仿真实验，并通过和一些先进的算法比较来评估DF‐WAdam算法的性能。在SGDLibrary[17]数据集Mushrooms和MNIST上进行实验，使用支持向量机（SVM）来解决二值分类问题；利用卷积神经网络（CNN）来解决多元分类问题。然后使用Metropolis constant edge权重矩阵W，在合成数据集和真实数据集中随机生成N=10个节点的连通网络，连通性比为0.5。

使用SVM来解决二值分类问题，训练集D={(x1,y1),(x2,y2),(x3,y3),…,(xm,ym)}，标签yi∈{-1,1}，则SVM的损失函数为

合成数据集和真实数据集的数值结果图1所示。可以看出，该算法的收敛速度优于其他算法。这说明利用简单的线性优化步骤来避免算法所需要的昂贵投影操作是可行的。在DAdam算法上运用Frank-Wolfe算法来避免代价昂贵的投影操作，实验结果令人满意。并且本文提出的算法对局部函数的梯度进行了加权平均，达到了加速效果。

图1 不同算法在数据集上10个epoch的收敛性。（a）Mushrooms；（b）MNIST

5 总结

针对分布式网络中实时更新数据流进行决策这一实际问题，本文提出了基于Frank-Wolfe的Adam分布式在线优化算法，理论分析表明DFWAdam算法具有O(T3/4)的Regret界。数值实验结果进一步显示DFWAdam算法具有较好的收敛性能。实际网络通常是时变、有向的，因此下一步的研究将把本文所提算法推广到时变有向网络。