朱小梅

（重庆师范大学数学科学学院，重庆 401331）

引言

分布式优化理论及应用是目前系统和控制科学的重要研究方向之一，在分布式网络中，节点之间通过相互协调合作，可以有效解决如智能电网、传感器网络等大规模现实问题，并能提高数据传递效率，增强网络鲁棒性［1-2］。但在实际应用中，分布式网络一般都运行在动态环境下，分布式优化算法不能实时处理网络数据流，而在线学习能够根据数据的变化动态地调整模型［3-4］，进而更高效地完成对大量实时数据的处理，并且分布式在线优化算法已经在机器学习、在线推荐系统和资源分配等方面有着重要的应用价值。

分布式优化算法已成为有效求解大规模优化问题的热点算法之一。现有的分布式优化算法主要分为三类：第一类是文献［5］最早提出的一种分布式次梯度算法来求解无约束的分布式优化问题，第二类是文献［6］提出的一种分布式对偶平均算法，给出算法的收敛性，并得出了收敛率依赖于网络规模和拓扑结构的结论，第三类是文献［7］基于拉格朗日对偶方法提出的分布式原始对偶算法来求解一类带约束的优化问题。虽然文献［6］提出的分布式对偶平均算法已经成为可以解决大规模问题的热点算法，但由于环境的不确定性以及目标函数具有时变性和不确定性，导致分布式优化算法并不能对网络中产生的大量分布式数据流进行实时处理，这造成网络资源和时间的浪费。针对上面的情形，一种有效的解决方法是在线学习，因为在线学习可以利用时变的目标函数来表示多个体网络系统的不确定性，同时还可以方便地对网络节点的动态数据流进行实时处理。最近，对于成本和网络结构不确定的凸优化问题，文献［8］提出了分布式加权对偶平均算法。李德权等人提出的一种快速的分布式在线对偶平均算法，即通过对底层网络依次添边，提高了分布式在线优化算法的收敛速率［9］。为更好的解决多智能体的在线优化问题，文献［10］设计了Nesterov对偶平均算法的两个去中心化的随机变体，即SODA-C和SODA-PS。文献［11］考虑了正则化随机学习和在线优化问题，开发了一种正则化的对偶平均算法，可以在在线环境中更有效的利用正则化结构。这充分说明分布式在线对偶平均方法可以有效的解决分布式在线优化问题。

现有的分布式在线对偶平均算法都是基于目标函数的梯度可以有效计算的情况，但在现实生活中，梯度信息一般获取困难。由此看来，现有的分布式在线对偶平均算法面临着一个梯度计算瓶颈。因此，设计出一种无梯度计算方法是十分有价值的。受文献［12］的启发，本文提出了一种基于Bandit反馈的分布式在线对偶平均算法。不同于分布式在线对偶平均算法，本文提出的算法只需要计算损失函数的值，即主要是利用损失函数在一些随机点的函数值信息去逼近损失函数原来的梯度信息，从而避免了直接计算损失函数的梯度。

1 准备工作

1.1图论

设G=（v，ε）表示一个无向图，其中v=｛1，2，…，n｝表示由n个节点构成的集合，ε⊆v×v表示相邻节点构成的边集，边（i，j）∈ε表示节点i可以从节点j接收数据信息。并记Ni=｛j|（i，j）∈ε｝表示节点i所有邻居构成的集合。非负矩阵A为图G=（v，ε）的权重矩阵，满足［A］ij＞0，当且仅当 （i，j）∈ ε，否则［A］ij=0。

假设1［2］设图G=（v，ε）是连通的，非负矩阵A∈Rn×n为图G=（v，ε）的权重矩阵，设权重矩阵是双随机的，即

1.2 Bandit反馈

在已有的分布式在线对偶平均算法的研究中，节点之间都是通过梯度信息进行通信反馈的，但在实际应用场景中，更一般的情况是不能够直接得到梯度信息的，所以本文提出了一种新的梯度信息反馈的改进方法，即Bandit反馈，该方法只显示当前时刻的损失函数的值，而不是显示整个函数的值。在Bandit设置中，节点只能访问一些点上的代价函数上的值并且不知道函数的梯度。由于大多数优化算法需要相关函数的梯度，因此，下面给出根据函数在有限点上的函数值来估计梯度的一些结果。

给定一个函数fi，t（x）：Rm→R，对∀x∈（1-ξ）χ，χ⊂Rm及某个很小的数δ＞0，定义fi，t（x）的一个光滑化近似函数，如下［8］

为梯度估计，其中u是满足均匀分布的随机向量。

引理 1［13］（I）即使fi，t（x）不可微，均匀光滑化函数^f i，t（x）在 （1-ξ）χ是可微的，对 ∀x∈ （1-ξ）χ有

（II）若fi，t（x）在 χ上是凸的，则^fi，t（x）在 （1-ξ）χ上也是凸的，且对 ∀x∈ （1-ξ）χ，fi，t（x）≤^fi，t（x）。

（III）若fi，t（x）在 χ上是 L-Lipschitz连续的，则）在 （1-ξ）χ上也是 L-Lipschitz连续的，且对 ∀x∈ （1-ξ）χ有）≤Lδ。

（IV）若fi，t（x）在 χ上是 L-Lipschitz连续的，则对∀x∈ （1-ξ）χ有mL。

2 问题与算法

2.1问题

考虑图G=（v，ε）上的分布式在线凸优化问题，如下

本文的最终目标是得到一系列的决策点｛xi，t｝使得对于每一个节点i∈v与最佳的固定决策点x*的Regret界［14］。

假设2（I）对任意的i∈v和任意的t∈｛1，2，…，T｝，fi，t（x）在 χ是 L-Lipschitz连续的，即对任意的x∈ χ和y∈ χ都有）-fi，t（y）Lx-y。

（II）存在正常数r和R使得rB⊂χ⊂RB，其中B=｛x∈x≤1｝。

由假设 2知，fi，t（·）的次梯度 ▽fi，t（·）在上是一致有界的，即 ▽fi，t≤L。

2.2 基于Bandit反馈的分布式在线对偶平均算法

算法1DODA-B算法

1.输入：最大迭代轮数T，步长αt，收缩系数ξ，光滑化参数δ和近端函数ψ（·）；

2.初始化：xi，1∈ （1-ξ）χ，∀i∈v，zi，1=0；

3.fort=1，2，…，Tdo

4.fori=1，2，…，ndo

5.观测fi，t（·），由式（2）计算梯度估计^gi，t；

8.输出：xi，t+1；

9.end for

10.end for

注记：（I）算法1给出了所提算法的伪代码，每个节点i都有如下两个局部序列：局部原始决策变量序列｛xi，t｝⊆χ，局部对偶变量序列 ｛zi，t｝⊆（1-ξ）χ，通过算法1的步6和步7更新。

（II）算法1中的步7中的 Πψ（1-ξ）χ（·）是在 （1-ξ）χ上的正则投影，这个投影可以表示为

其中ψ（x）是一个近端函数。

3 收敛性分析

这部分提出一个带两点梯度估计的在线分布式对偶平均算法来解决所考虑的优化问题，然后给出Regret界。下面主要陈述对算法1的主要结果。下面的定理描述基于一些特别选择的步长，压缩系数和光滑化参数等等。首先给出几个重要的引理：

引理2［13］对任意的常数k∈ ［0，1），且s≤T∈R+，有

引理3［15］设假设1成立，则存在常数 λ∈ （0，1）及C＞0，对 ∀i，j∈v，∀t≥1有

引理4设假设1-2成立，对任意的i∈v和t∈R+，｛zi，t｝是由算法 1产生的序列，则

再对式（10）两边取对偶范数可得

第二个不等式由引理1的（IV）和引理3得到。

引理5设假设1-2成立，｛xi，t｝是由算法1产生的序列，则对任意的i∈v，x*∈（1-ξ）χ有

证明根据fi，t（x）的L-Lipschitz连续性，对x*∈（1-ξ）χ和由 φ（t）=，αt）定义的序列 ｛φ（t）｝，有

将（13）式右边最后一个等式的第一项重新写为

根据引理1的（III）可知

从而在式（19）两边对t=1，2，…，T求和得

于是将式（23）代入式（18）可得

由式（17）和式（24）可得

于是将式（26）代入式（13）可得

将引理4代入上式即可得结论，式（12）得证。

定理1设假设1-2成立，对任意的T∈ R+，｛x｝是由算法 1产生的序列，取 α=，δ，ξ=i，tt，ψ（x）≤D2，有

从而结论得以证明。

注记：定理1的结果表明，算法1的收敛速度是O（Tmax｛k，1-k｝），当k=时，算法1的收敛速度与已往的分布式在线对偶平均算法的收敛速度同阶。通过对比，本文所提出的算法1只需要计算损失函数的函数值，避免了花费较大的梯度计算，从而节省了计算成本，并且算法适用范围更加广泛。

4 数值模拟计算

在本节中，考虑一个分布式在线传感器问题，对于每个节点i∈v都有自己的测量方程qi，t=Uix+ei，t，其中qi，t∈Rn，Ui∈Rn×m是测量数据，x∈Rm是未知的，ei，t∈Rn是未知的噪音，问题最终的目标在于估计x，使用所提出的DODA-B算法去解决如下问题［16］

考虑一个节点n的随机网络，对于任意的节点i∈v。假设 χ=Rm，实矩阵Ui∈ Rn×m且qi，t∈ Rn在（0，2）中产生，设ui，t是在欧式单位球S上随机产生，且服从均匀分布。取T=500，R=5，，λ=0.5，步长α=。取光滑参数δ，压缩系数ξ=。考虑平t均Regret界，将本文的DODA-B算法与现有的DODA算法进行对比。

图1和图2表示节点总数n分别为50和100的平均Regret界的演化图。根据定理1的理论结果分析，可以从图1观察到，当迭代时间T达到100时，两种算法的平均Regret界均会收敛到0，并且DODA-B算法的收敛率和DODA算法收敛率同阶，因为它们仅相差一个由函数值信息近似梯度信息产生的光滑化误差项。另外，从图2可以观察到，当节点n=100时，也可以得到同样的结果。

图1 DODA-B与DODA算法平均化Regret界的比较（n=50）

图2 DODA-B与DODA算法平均化Regret界的比较（n=100）

5 结论

针对分布式在线优化中一类损失函数梯度难以获取的问题，通过Bandit设置，本文提出了一种基于Bandit反馈的分布式在线对偶平均（DODA-B）算法，将DODA算法改进成无梯度的DODA-B算法。理论分析表明，DODA-B算法具有O(Tmax{k，1-k})的Regret界。数值模拟计算结果进一步表明两种算法的收敛率同阶，并且DODA-B算法仅仅用到计算量较小的函数值信息，这要比DODA算法更节约成本。未来可以将所提的DODA-B算法推广到有向网络中，或推广到时变网络中。