Handling Delayed Feedback in Distributed Online Optimization : A
  Projection-Free Approach
Tuan-Anh Nguyen Nguyen Kim Thang Denis Trystram
Learning at the edges has become increasingly important as large quantities
of data are continually generated locally. Among others, this paradigm requires
algorithms that are simple (so that they can be executed by local devices),
robust (again uncertainty as data are continually generated), and reliable in a
distributed manner under network issues, especially delays. In this study, we
investigate the problem of online convex optimization under adversarial delayed
feedback. We propose two projection-free algorithms for centralised and
distributed settings in which they are carefully designed to achieve a regret
bound of O(\sqrt{B}) where B is the sum of delay, which is optimal for the OCO
problem in the delay setting while still being projection-free. We provide an
extensive theoretical study and experimentally validate the performance of our
algorithms by comparing them with existing ones on real-world problems.