Dynamic Regret of Distributed Online Frank-Wolfe Convex Optimization

Abstract

This paper considers distributed online convex constrained optimization, in which various agents in a multi-agent system cooperate to minimize a global cost function through communicating with neighbors over a time-varying network. When the constraint set of optimization problem is high-dimensional and complicated, the computational cost of the projection operation often becomes prohibitive. To handle this problem, we develop a distributed online Frank-Wolfe optimization algorithm combining with gradient tracking technique. We rigorously establish the dynamic regret bound of the proposed optimization algorithm as $\mathcal{O}(\sqrt{T(1+H_T)}+D_T)$, which explicitly depends on the iteration round $T$, function variation $H_T$, and gradient variation $D_T$. Finally, the theoretical results are verified and compared in the case of distributed online ridge regression problems.