分布式在线条件梯度优化算法

Distributed Online Conditional Gradient Optimization Algorithm

针对现有分布式在线优化算法所面临的高维约束难以计算的问题,提出一种分布式在线条件梯度优化算法(Distributed Online Conditional Gradient Optimization Algorithm,DOCG)。首先,通过多个体网络节点间的相互协作进行数据采集,并通过共享采集的信息更新局部估计,同时引入反映环境变化的局部即时损失函数。然后,该算法利用历史梯度信息进行加权平均,提出一种新的梯度估计方案,其用线性优化步骤替代投影步骤,避免了投影运算在高维约束时难以计算的问题。最后,通过分析表征在线估计性能的Regret界,证明了所提DOCG算法的收敛性。利用低秩矩阵填充问题进行仿真验证,结果表明,相比于现有分布式在线梯度下降法(DOGD),所提DOCG算法具有更快的收敛速度。

In order to overcome the problem that the high-dimensional constraints in existing distributed online optimization algorithms are hard to be calculated,a distributed online conditional gradient optimization algorithm (DOCG) was proposed in this paper.Firstly,data collection is carried out through mutual cooperation among nodes of the muti-agent distributed network,and then each node updates its local iterate based on new local data,together with an instantaneous local cost functions that reflects the environmental changes.Secondly,by virtue of the historical gradient information for weighted averaging, a new gradient estimation scheme is proposed,in which the sophisticated projection step is replaced by the linear optimization step and thus avoids the disadvantages of the projection operator that is hard to be calculated.Finally,by defining the corresponding Regret bound to characterize the performance of online estimation, the convergence of the DOCG algorithm is proved.Simulation results are conducted on low-rank matrix completion problems,which clearly show that the proposed algorithm has faster convergence rate than the existing distributed online gradient method(DOGD).