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

Distributed Online Dual Average Algorithm Based on Bandit Feedback

为解决梯度信息难以获取的分布式在线优化问题,提出了一种基于Bandit反馈的分布式在线对偶平均(DODA-B)算法。首先,该算法对原始梯度信息反馈进行了改进,提出了一种新的梯度估计,即Bandit反馈,利用函数值信息去近似原损失函数的梯度信息,克服了求解复杂函数梯度存在的计算量大等问题。然后,给出了该算法的收敛性分析,结果表明,Regret界的收敛速度为O(Tmax{k,1-k}),其中T是最大迭代次数。最后,利用传感器网络的一个特例进行了数值模拟计算,计算结果表明,所提算法的收敛速度与现有的分布式在线对偶平均(DODA)算法的收敛速度接近。与DODA算法相比,所提出算法的优点在于只考虑了函数值信息,使其更适用于梯度信息获取困难的实际问题。

In order to solve the distributed online optimization problem that is difficult to obtain gradient information,a distributed online dual average(DODA-B)algorithm based on bandit feedback is proposed.First,the algorithm improves the feedback of the original gradient information,and proposes a new gradient estimation,bandit feedback,which uses the function value information to approximate the gradient information of the original cost function,and overcomes the amount of calculation to solve the existence of complex function gradients major issues.Then,the convergence analysis of the algorithm is given.The results show that the convergence speed of the regret bound is O(Tmax{k,1-k}),Where T is maximum number of iterations.Finally,a special case of sensor network is used to carry out numerical simulation experiments.The experimental results show that the convergence speed of the proposed algorithm is close to the convergence speed of the existing distributed online dual average(DODA)algorithm.Compared with the DODA algorithm,the advantage of the proposed algorithm is that it only considers the function value information with a small amount of calculation,making it more suitable for optimization problems that have difficulty in obtaining gradient information.