Randomised block-coordinate Frank-Wolfe algorithm for distributed online learning over networks

Abstract

The distributed online algorithms which are based on the Frank-Wolfe method can effectively deal with constrained optimisation problems. However, the calculation of the full (sub)gradient vector in those algorithms leads to a huge computational cost at each iteration. To reduce the computational cost of the algorithms mentioned above, the authors present a distributed online randomised block-coordinate Frank-Wolfe algorithm over networks. Each agent in the networks only needs to calculate a subset of the coordinates of its (sub)gradient vector in this algorithm. Furthermore, they make a detailed theoretical analysis of the regret bound of this algorithm. When all local objective functions satisfy the conditions of strongly convex functions, the authors’ algorithm attains the regret bound of [inline-formula], where T is the total number of iterations. Furthermore, the theorem results are verified via simulation experiments, which show that the algorithm is effective and efficient.

Keywords

• convex programming
• learning (artificial intelligence)
• gradient methods
• randomised algorithms
• computational complexity
• distributed online algorithms
• frank-wolfe method
• constrained optimisation problems
• distributed online learning
• randomised block-coordinate frank-wolfe algorithm
• full gradient vector
• subgradient vector
• convex functions