Open AccessRandomised block‐coordinate Frank‐Wolfe algorithm for distributed online learning over networks
Author(s) -
Li Jingchao,
Wu Qingtao,
Zheng Ruijuan,
Zhu Junlong,
Ge Quanbo,
Zhang Mingchuan
Publication year - 2020
Publication title -
cognitive computation and systems
Language(s) - English
Resource type - Journals
ISSN - 2517-7567
DOI - 10.1049/ccs.2020.0007
Subject(s) - regret , computer science , algorithm , block (permutation group theory) , online algorithm , mathematical optimization , distributed algorithm , convex function , regular polygon , upper and lower bounds , mathematics , combinatorics , machine learning , distributed computing , mathematical analysis , geometry
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 O ( T ) , 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.