Abstract: 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).

Key words: Conditional gradient, Distributed network, Online learning, Projection-free, Regret bound