Timezone: »

 
Poster
Projection-free Distributed Online Convex Optimization with $O(\sqrt{T})$ Communication Complexity
Yuanyu Wan · Wei-Wei Tu · Lijun Zhang

Thu Jul 16 05:00 PM -- 05:45 PM & Fri Jul 17 04:00 AM -- 04:45 AM (PDT) @ Virtual
in Poster Session 49 »
To deal with complicated constraints via locally light computation in distributed online learning, a recent study has presented a projection-free algorithm called distributed online conditional gradient (D-OCG), and achieved an $O(T^{3/4})$ regret bound, where $T$ is the number of prediction rounds. However, in each round, the local learners of D-OCG need to communicate with their neighbors to share the local gradients, which results in a high communication complexity of $O(T)$. In this paper, we first propose an improved variant of D-OCG, namely D-BOCG, which enjoys an $O(T^{3/4})$ regret bound with only $O(\sqrt{T})$ communication complexity. The key idea is to divide the total prediction rounds into $\sqrt{T}$ equally-sized blocks, and only update the local learners at the beginning of each block by performing iterative linear optimization steps. Furthermore, to handle the more challenging bandit setting, in which only the loss value is available, we incorporate the classical one-point gradient estimator into D-BOCG, and obtain similar theoretical guarantees.
Keywords: Convex Optimization · Parallel and Distributed Learning · Online Learning / Bandits · Online Learning, Active Learning, and Bandits
[ Slides] 

Author Information

Yuanyu Wan (Nanjing University)
Wei-Wei Tu (4Paradigm Inc.)
Lijun Zhang (Nanjing University)

More from the Same Authors