-
开放科学(资源服务)标志码(OSID):
-
随着数据规模的爆炸式增长,集中式优化算法因受限于单机的计算瓶颈而难以求解大规模优化问题. 而多机协作的分布式机制可以大大降低单机的计算负担. 同时,在分布式网络中,节点之间通过相互协作,可以有效解决诸如智能电网、传感器网络等大规模问题,并能提高数据传递效率,增强网络鲁棒性[1]. 但在应用中,分布式网络通常是动态变化的,而在线学习具有实时更新模型的特性,能够根据数据的变化动态地调整模型[2],进而可高效地完成对大量实时数据的处理,已经在机器学习、在线推荐系统和资源分配等方面体现出了重要的应用价值.
分布式优化算法已成为有效求解大规模优化问题的热点算法之一,如分布式次梯度算法[3-4]、分布式对偶平均算法和分布式ADMM算法[1]等等,但这些算法是基于Euclidean距离设计的,仅能处理一些带有简单约束的优化问题. 文献[5]提出了一类镜面梯度下降算法,该算法是将传统的基于Euclidean距离的梯度投影算法推广到更一般的基于Bregman散度的一类投影算法. 针对约束的几何特性,通过适当选择Bregman散度,使得镜面梯度下降算法能有效地解决诸如带有单纯形约束的高维优化问题. 文献[6]研究表明,镜面梯度下降算法在大规模优化问题中极为有效. 文献[7]提出了一种分布式镜面随机梯度下降算法. 虽然该算法能够有效处理海量数据,但由于环境的不确定性,损失函数具有时变性和不确定性,导致分布式镜面随机梯度下降算法并不能对网络产生的大量分布式数据流进行实时处理,造成网络资源和时间的浪费. 针对损失函数是时变的情形,一种有效的处理方式是在线学习,因为在线学习不仅可以利用具有时变的损失函数来模型化多节点网络系统的不确定性,而且可以方便地对网络节点的动态数据流进行实时处理. 最近,文献[8]提出了一种在线分布式镜面梯度下降(ODMD)算法,并给出了Regret界的估计是
$O\left( {\sqrt T } \right)$ ,这里T是迭代次数.然而,上述大多数算法都需要计算梯度. 但在许多实际应用场景中,梯度信息往往难以获取. 因此,设计出一种免梯度计算的有效算法显得非常有意义. 受文献[9]的启发,本文提出了一种基于Bandit反馈的免梯度在线分布式镜面下降算法. 不同于ODMD算法,我们提出的算法只需要简单计算函数值,主要是利用损失函数在一些随机点的函数值信息去逼近损失函数的梯度,从而避免了直接计算损失函数的梯度. 我们设计的算法主要有两个优点:①能有效解决梯度信息难以获取的困难; ②能有效处理约束集较复杂(如单纯形约束集)的优化问题.
全文HTML
-
用图G=(V,E)表示节点与节点之间的信息交换情况,其中V={1,…,N}表示由N个节点构成的集合,E表示相邻节点构成的边集,即(i,j)∈E当且仅当节点i从节点j直接获得信息,并用Ni={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)为平衡图,反之为非平衡图. 若AT=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散度Dh(·,·)
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的梯度.
1.1. 图论
1.2. Bregman散度
1.3. Bandit反馈
-
假设T是一个事先给定的时间周期,在每一时刻t=1,…,T,网络中的每个节点i需要从凸的紧集
$\chi \subseteq {\mathbb{R} ^m}$ 中给出一个本地估计xi,t,进而对未知的本地凸损失函数fi,t(xi,t)进行观测[10]. 在时刻t,节点i仅知道直到前t-1时刻的函数信息{fi,s}s=1t-1,而不知道t时刻以后的函数信息{fi,s}s=t+1T.考虑图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{ }}$ ,且函数fi,t(x):$\chi \to {\mathbb{R}}$ 仅节点i自己知道.本文的目标是生成一系列的决策点{xi,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界RT(xi,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},fi,t(·)在χ上是G-Lipschitz连续的,即对∀x,y∈χ,有|fi,t(x)-fi,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知fi,t(·)的次梯度▽fi,t(·)在χ上是一致有界的,即‖▽fi,t‖≤G.
-
由光滑化函数的定义(3),我们给出问题(4)中节点i在时刻t的损失函数fi,t的一个光滑化函数
根据引理2,我们可以得到
$\nabla {\mathop f\limits^ \wedge }_{i,t}\left( \cdot \right)$ 在点xi,t的一个无偏估计如下在时刻t,只有xi,t被确定后才可以获得fi,t,进而才能估计fi,t(xi,t±ξui,t),其中ui,t~U(S).
定义如下的
${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$ 为$\nabla {\mathop f\limits^ \wedge }_{i,t} \left( {{\mathit{\boldsymbol{x}}_{i, t}}} \right)$ 在点xi,t的一个近似对
${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$ 的估计有以下两个结果[9]:算法1 ODMD-B算法
1) 输入:最大迭代次数T,步长ηt,收缩系数α,光滑化参数ξ;
2) 初始化:xi,1∈(1-α)χ,yi,1=xi,1,∀i∈V;
3) for t =1,…,T do
4) for i =1,…,N do
5) 利用决策xi,t,观测局部即时损失函数fi,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) 输出:{xi,T+1}i=1N
注1 算法1中步2)初始化是为了保证(8)式的
${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$ 在点xi,t±ξui,t有定义. 结合算法1的步2)、步7)和引理2知,迭代序列{xi,t}t≥1保持在可行域χ中.注2 算法1中步7)表示基于Bregman的镜面下降算法的局部更新,其中
${\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$ 是原来损失函数fi,t光滑化后的一个梯度估计,它仅仅涉及便利的函数值计算.
2.1. 问题
2.2. 基于Bandit反馈的在线分布式镜面下降算法
-
这一部分主要论述本文提出的ODMD-B算法在局部损失函数为凸时的Regret界. 分析思路如下:首先,估计出各节点的网络化误差,见引理4; 然后,引入一个辅助函数并给出一个重要的引理,见引理5; 最后,根据已建立的结果得出主要结果.
引理3[8] 如果假设1和2均成立,且Dh(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均成立,序列{xi,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呈递减的步长序列,σ2(A)∈(0,1)为权重矩阵A的第二大奇异值.证 根据算法1的步7)和引理1,有
由(1)式可得
从而‖xi,t+1-yi,t‖≤mGηt. 接下来,令ei,t=xi,t+1-yi,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均成立,序列{xi,t}是由算法1迭代产生的,则
证 根据函数Fi,t的定义可得
$\nabla {F_{i, t}}\left( {{\mathit{\boldsymbol{x}}_{i, t}}} \right) = {\mathop {\boldsymbol{g}}\limits^ \wedge {}_{i,t}}$ . 由定义(17)式知,Fi,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是参数. 设序列{xi,t}t=1T是由算法1迭代产生的,则对任意的i∈V,有如下期望Regret上界其中
证 根据Regret界的定义(5)式及ft的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)式右边的项得
由Fi,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]情形.