Online Distributed Mirror Descent Algorithm Based on Bandit Feedback

用图G=(V，E)表示节点与节点之间的信息交换情况，其中V={1，…，N}表示由N个节点构成的集合，E表示相邻节点构成的边集，即(i，j)∈E当且仅当节点i从节点j直接获得信息，并用N_i={j|(i，j)∈E}来表示由节点i所有邻居构成的集合. 非负矩阵A为图G=(V，E)的权重矩阵，满足[A]_ij>0，当且仅当(i，j)∈E，否则[A]_ij=0. 若对于任意的i，j∈V，有$\sum\limits_{i = 1}^N {{{\left[ \mathit{\boldsymbol{A}} \right]}_{ij}}} = \sum\limits_{j = 1}^N {{{\left[ \mathit{\boldsymbol{A}} \right]}_{ij}}} $，则称图G=(V，E)为平衡图，反之为非平衡图. 若A^T=A，则称图G=(V，E)为无向图.

假设1^[1]   假设图G=(V，E)是连通的，即任意两个节点之间都存在一条路径. 假设图G=(V，E)对应的权重矩阵A是双随机矩阵，即A满足$\sum\limits_{j = 1}^N {{{\left[ \mathit{\boldsymbol{A}} \right]}_{ij}} = 1} {\rm{, }}\forall i \in V;\sum\limits_{i = 1}^N {{{\left[ \mathit{\boldsymbol{A}} \right]}_{ij}} = 1} {\rm{, }}\forall j \in V$.

定义1^[8] (μ^-强凸函数)   称一个函数h：$\chi \to \mathbb{R} $是μ^-强凸的，如果对于任意的x，y∈χ，有

定义2^[8](Bregman散度)   设h(·)是1-强凸函数，定义如下关于函数h的Bregman散度D_h(·，·)

Euclidean距离和Kullback-Leiber(KL)散度为两种常用的Bregman散度.

结合定义1和2可以得到有关Bregman散度的一个重要性质^[8]

引理1^[8]   设χ是${\mathbb{R}^m}$中的一个凸集，h：$\chi \to \mathbb{R} $是一个定义在χ中关于‖·‖的1-强凸函数. 定义$\mathit{\boldsymbol{\mathop x\limits^ \wedge }} = \mathop {{\rm{argmin}}}\limits_{\boldsymbol{\mathop x} \in \chi } \left\{ {\left\langle {\mathit{\boldsymbol{a, x}}} \right\rangle + {D_h}\left( {\mathit{\boldsymbol{x, }}{\rm{ }}\mathit{\boldsymbol{c}}} \right)} \right\}$，则有以下不等式成立

现有在线分布式算法大多是基于完全信息设计的，即节点可以获得其决策空间中任何一个位置的梯度信息. 而在许多应用场景中，节点一般获得的是带噪音的、有缺漏或有限的信息反馈，称这种不能直接获得损失函数梯度的情形为Bandit反馈机制^[9]，即节点只能访问自身损失函数在一些随机点上的函数值，但并不知道其梯度信息. 众所周知，大多数优化算法的设计是基于损失函数的梯度设计的，而在Bandit反馈中，面临着梯度信息不可用的问题. 为此，我们设计了仅利用损失函数值来逼近梯度的Bandit算法. 下面给出根据函数在随机点上的函数值来近似估计其梯度的一些结果.

给定一个函数f：${\mathbb{R}^m} \to \mathbb{R}$，对某个很小的数ξ>0，定义f(x)的一个光滑化近似函数如下

其中U(B)表示服从单位球$B = \left\{ {\left. {\mathit{\boldsymbol{x}} \in {\mathbb{R}^m}} \right|{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\| \mathit{\boldsymbol{x}} \right\| \le 1} \right\}$的均匀分布，E[·]表示期望.

引理2^[9]   设$S = \left\{ {\left. {\mathit{\boldsymbol{x}} \in {\mathbb{R}^m}} \right|{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\| \mathit{\boldsymbol{x}} \right\| \le 1} \right\}$表示${\mathbb{R}^m}$中的单位球面，有以下结果：

(ⅰ) $\nabla \mathop f\limits^ \wedge \left( \mathit{\boldsymbol{x}} \right) = \frac{m}{\xi }{E_{v \sim U\left( S \right)}}\left[ {f\left( {\mathit{\boldsymbol{x}} + \xi \mathit{\boldsymbol{v}}} \right)\mathit{\boldsymbol{v}}} \right], $，其中v为服从S上均匀分布的随机向量.

(ⅱ) 若f是凸的且G-Lipschitz连续的函数，则$\mathop f\limits^ \wedge $也是凸的且G-Lipschitz连续的函数.

(ⅲ) 对某些α∈(0，1)和任意的x∈(1-α)χ，有B(x，r)⊂χ，其中B(x，r)表示以x为中心r为半径的单位球，即$B\left( {\mathit{\boldsymbol{x}}, {\rm{ }}r} \right) = \left\{ {\left. {\mathit{\boldsymbol{Z}} \in {\mathbb{R}^m}} \right|{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\| {\mathit{\boldsymbol{Z}} - \mathit{\boldsymbol{x}}} \right\| \le r} \right\}$.

从$\mathop f\limits^ \wedge $的定义知，函数$\mathop f\limits^ \wedge $是f的一个光滑近似. 由引理2知，$\nabla \mathop f\limits^ \wedge $也可以看做是▽f的近似. 为此，本文主要思想是利用计算函数值$\frac{m}{{2\xi }}\left[ {f\left( {\mathit{\boldsymbol{x}} + \xi \mathit{\boldsymbol{v}}} \right) - f\left( {\mathit{\boldsymbol{x}} - \xi \mathit{\boldsymbol{v}}} \right)} \right]$来近似函数f的梯度.

假设T是一个事先给定的时间周期，在每一时刻t=1，…，T，网络中的每个节点i需要从凸的紧集$\chi \subseteq {\mathbb{R} ^m}$中给出一个本地估计x_i，t，进而对未知的本地凸损失函数f_i，t(x_i，t)进行观测^[10]. 在时刻t，节点i仅知道直到前t-1时刻的函数信息{f_i，s}_s=1^t-1，而不知道t时刻以后的函数信息{f_i，s}_s=t+1^T.

考虑图G=(V，E)上的在线分布式凸优化问题如下

其中：χ是一个凸紧集，${f_t}\left( \mathit{\boldsymbol{x}} \right) = \frac{1}{N}\sum\limits_{i = 1}^N {{f_{i, t}}\left( \mathit{\boldsymbol{x}} \right)} {\rm{ }}$，且函数f_i，t(x)：$\chi \to {\mathbb{R}}$仅节点i自己知道.

本文的目标是生成一系列的决策点{x_i，t|i∈V，t=1，…，T}相对于拥有完全信息而做出的最优决策${\mathit{\boldsymbol{x}}^*} \in \mathop {{\rm{argmin}}}\limits_{\boldsymbol{\mathop x} \in \chi } \sum\limits_{t = 1}^T {\sum\limits_{i = 1}^N {{f_{i, t}}\left( \mathit{\boldsymbol{x}} \right)} } $的Regret^[8]界

尽可能小. 通常要求Regret界R_T(x_i，t，x^*)相对于T是次线性的，即$\mathop {{\rm{lim}}}\limits_{T \to \infty } \left( {\frac{{{R_T}\left( {{\mathit{\boldsymbol{x}}_{i, t}}{\rm{, }}{\mathit{\boldsymbol{x}}^*}} \right)}}{T}} \right) = 0$. 随着T的增大，使其可以逼近最优决策x^*.

假设2   (ⅰ) 对∀i∈V和∀t∈{1，…，T}，f_i，t(·)在χ上是G-Lipschitz连续的，即对∀x，y∈χ，有|f_i，t(x)-f_i，t(y)|≤G‖x-y‖.

(ⅱ) 存在两个正常数γ和Γ使得：γB⊂χ⊂ΓB，其中$B = \left\{ {\left. {\mathit{\boldsymbol{x}} \in {\mathbb{R} ^m}} \right|{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\| \mathit{\boldsymbol{x}} \right\| \le 1} \right\}$.

由假设2知f_i，t(·)的次梯度▽f_i，t(·)在χ上是一致有界的，即‖▽f_i，t‖≤G.

由光滑化函数的定义(3)，我们给出问题(4)中节点i在时刻t的损失函数f_i，t的一个光滑化函数

根据引理2，我们可以得到$\nabla {\mathop f\limits^ \wedge }_{i,t}\left( \cdot \right)$在点x_i，t的一个无偏估计如下

在时刻t，只有x_i，t被确定后才可以获得f_i，t，进而才能估计f_i，t(x_i，t±ξu_i，t)，其中u_i，t~U(S).

定义如下的${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$为$\nabla {\mathop f\limits^ \wedge }_{i,t} \left( {{\mathit{\boldsymbol{x}}_{i, t}}} \right)$在点x_i，t的一个近似

对${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$的估计有以下两个结果^[9]：

算法1   ODMD-B算法

1) 输入：最大迭代次数T，步长η_t，收缩系数α，光滑化参数ξ;

2) 初始化：x_i，1∈(1-α)χ，y_i，1=x_i，1，∀i∈V;

3) for t =1，…，T do

4) for i =1，…，N do

5) 利用决策x_i，t，观测局部即时损失函数f_i，t(x);

6) 利用(8)式计算梯度估计${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$;

6) 更新${\mathit{\boldsymbol{x}}_{i, t + 1}} = \mathop {{\rm{argmin}}}\limits_{\boldsymbol{\mathop x} \in \left( {1 - \alpha } \right)\chi } \left\{ {\left\langle {\mathit{\boldsymbol{x}}, {\rm{ }}{\eta _t}{\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}} \right\rangle + {D_h}\left( {\mathit{\boldsymbol{x}}, {\rm{ }}{\mathit{\boldsymbol{y}}_{i, t}}} \right)} \right\}$;

7) 更新${\mathit{\boldsymbol{y}}_{i, t + 1}} = \sum\limits_{j = 1}^N {{{\left[ \mathit{\boldsymbol{A}} \right]}_{ij}}{\mathit{\boldsymbol{x}}_{j, {\rm{ }}t + 1}}} $;

8) end for

9) end for

10) 输出：{x_i，T+1}_i=1^N

注1   算法1中步2)初始化是为了保证(8)式的${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$在点x_i，t±ξu_i，t有定义. 结合算法1的步2)、步7)和引理2知，迭代序列{x_i，t}_t≥1保持在可行域χ中.

注2   算法1中步7)表示基于Bregman的镜面下降算法的局部更新，其中${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$是原来损失函数f_i，t光滑化后的一个梯度估计，它仅仅涉及便利的函数值计算.

这一部分主要论述本文提出的ODMD-B算法在局部损失函数为凸时的Regret界. 分析思路如下：首先，估计出各节点的网络化误差，见引理4; 然后，引入一个辅助函数并给出一个重要的引理，见引理5; 最后，根据已建立的结果得出主要结果.

引理3^[8]   如果假设1和2均成立，且D_h(x，y)关于第二个变量y是凸的，则

其中${R^2} = \mathop {{\rm{sup}}}\limits_{\boldsymbol{\mathop x, {\rm{ }}y} \in \chi } {D_h}\left( {\mathit{\boldsymbol{x, }}{\rm{ }}\mathit{\boldsymbol{y}}} \right)$.

引理4   如果假设1和2均成立，序列{x_i，t}是由算法1迭代产生的，则对任意的i∈V和t≥1，有

其中：${\mathit{\boldsymbol{\bar x}}_{t + 1}} = \frac{1}{N}\sum\limits_{i = 1}^N {{\mathit{\boldsymbol{x}}_{i, t + 1}}} $，{η_t}是非负的且关于t呈递减的步长序列，σ₂(A)∈(0，1)为权重矩阵A的第二大奇异值.

证   根据算法1的步7)和引理1，有

由(1)式可得

从而‖x_i，t+1-y_i，t‖≤mGη_t. 接下来，令e_i，t=x_i，t+1-y_i，t，${\mathit{\boldsymbol{\bar e}}_t} = \frac{1}{N}\sum\limits_{i = 1}^N {{\mathit{\boldsymbol{e}}_{i, t}}} $，根据算法1的步8)，有

由(13)式和假设1可得

于是由(13)式和(14)式有

利用双随机矩阵A的性质^[8]，即矩阵A满足

这样有

为了证明定理1的结果，对任意的x∈χ，作如下辅助函数

引理5   如果假设1和2均成立，序列{x_i，t}是由算法1迭代产生的，则

证   根据函数F_i，t的定义可得$\nabla {F_{i, t}}\left( {{\mathit{\boldsymbol{x}}_{i, t}}} \right) = {\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$. 由定义(17)式知，F_i，t(·)是凸的，进而有

接下来对(19)式最后一个不等式右边的三项分别进行估计. 对第一项，根据算法1的步8和引理4，有

对第二项，由(9)式有

其中(21)式的最后一个不等式由均值不等式得到. 对第三项，根据引理1和(1)式，有

最后，将(20)-(22)式代入(19)式，且在(19)式中对t=1，…，T求和，然后再对i=1，…，N求和，最后利用引理3可证得(18)式成立.

定理1   如果假设1和2均成立. 对T≥1，在算法1中，取$\xi = \frac{1}{T}{\rm{, }}\alpha = \frac{1}{{\gamma T}}, {\eta _t} = \frac{\beta }{{\sqrt t }}$，其中β>0是参数. 设序列{x_i，t}_t=1^T是由算法1迭代产生的，则对任意的i∈V，有如下期望Regret上界

其中

证   根据Regret界的定义(5)式及f_t的G-Lipschitz连续性，有

在(24)式中，利用引理4，可得

在(25)式中，先对t=1，…，T求和，然后再对i=1，…，N求和，可得

根据${\mathop f\limits^ \wedge }_{i, t}$的定义，有

从而

根据${\mathop f\limits^ \wedge }_{i, t}$的定义、假设2和(27)式，有

从而由(29)式可得

根据(28)式和(30)式，由(26)式右边的项得

由F_i，t(·)的定义，有

注意到$E\left[ {\left. {\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}} \right|{\mathit{\boldsymbol{x}}_{i, t}}} \right] = \nabla {\mathop f\limits^ \wedge }_{i, t}\left( {{\mathit{\boldsymbol{x}}_{i, t}}} \right)$，由(32)式可得

对(26)式取期望，结合(31)式和(33)式，再根据引理5，有

将定理中的$\xi = \frac{1}{T}{\rm{, }}\alpha = \frac{1}{{\gamma T}}, {\eta _t} = \frac{\beta }{{\sqrt t }}$代入(34)式即可得证.

注3   定理1的结果表明，算法1的收敛速度是$O\left( {\sqrt T } \right)$，这与文献[8]的在线分布式镜面梯度下降算法的收敛速度同阶，仅仅相差一个光滑化误差项$\left( {2 + \frac{\mathit{\Gamma }}{\gamma }} \right)G$. 通过对比，本文所提出的算法1仅需要计算损失函数的函数值，并没有涉及复杂的梯度计算，从而降低了复杂度，而且算法适用范围更加广泛.

为了说明算法的有效性，考虑一个不对股票市场进行任何统计假设的投资组合选择模型，被称为“通用投资组合选择”模型，它在在线学习中受到了特别的关注. 下面给出一个投资组合选择模型^[10]

其中Δ_m为m维的单纯形，参数${\mathit{\boldsymbol{r}}_{i, t}} \in \mathbb{R} _ + ^m$表示价格比率是时变的.

我们考虑一个具有N个节点的连通网络且满足假设1. 在ODMD-B算法中，取T=1 000，步长${\eta _t} = \frac{{0.06}}{{\sqrt {t + 1} }}$，取光滑化参数$\xi = \frac{1}{T}$，压缩系数$\alpha = \frac{{0.4}}{T}$. 由于约束集是m维的单纯形，故采用KL散度. 这样，算法1中步7)有如下形式的显式解^[5]

其中q=1，…，m. 对于ODMD-B算法的性能度量，考虑平均Regret界. 另外，将本文提出的ODMD-B算法与文献[8]提出的ODMD算法进行数值对比.

首先，考虑不同的问题维数对ODMD-B算法性能的影响. 图 1a和图 1b分别表示N=10，m=50和N=10，m=100的平均Regret界随着迭代次数变化的演化图. 从图 1a和图 1b可以看出，本文提出的ODMD-B算法与文献[8]提出的ODMD算法都可以收敛. 但ODMD-B算法的早期收敛速度稍微慢于ODMD算法，这是因为ODMD-B算法只使用了函数值信息，而ODMD算法是直接使用了梯度信息. 但随着迭代次数增大，ODMD-B算法的平均Regret界大致接近ODMD算法的平均Regret界. 另外，对比图 1a和图 1b中的ODMD-B算法，当T=700时，m=50和m=100平均Regret界分别为0.020 52和0.027 39，仅相差0.007左右. 这表明问题维数对所提算法性能的影响并不大，这主要是因为此问题在迭代过程中能够求得显示解.

然后，考虑不同的节点个数对ODMD-B算法性能的影响. 图 1c和图 1d分别表示N=50，m=100和N=100，m=100的平均Regret界随着迭代次数变化的演化图. 图 1c和图 1d进一步表明两种算法的平均Regret界随着迭代次数的增加而趋于一致. 另外，对比图 1c和图 1d可以发现，随着节点个数的增加，两种算法的平均Regret界随之增加. 相比ODMD算法，本文所提ODMD-B算法仅仅使用了函数值信息.

对于梯度获取困难且约束集较复杂的问题，本文提出了一种ODMD-B算法. 该算法与现有的ODMD算法的不同点在于将梯度信息反馈改进成基于函数值信息的Bandit反馈. 理论结果表明，ODMD-B算法具有与ODMD算法同阶的收敛速度，即达到$O\left( {\sqrt T } \right)$的Regret界. 但本文提出的ODMD-B算法仅仅使用了损失函数值信息，有效避免了梯度信息获取困难的问题. 未来研究方向可将本文提出的ODMD-B算法推广到非平衡有向图切换网络^[11-12]情形.