Optimal and Efficient Algorithms for Decentralized Online Convex Optimization

We investigate decentralized online convex optimization (D-OCO), in which a set of local learners are required to minimize a sequence of global loss functions using only local computations and communications. Previous studies have established O(n5/4ρ-1/2√T) and O(n3/2ρ-1log T) regret bounds for convex and strongly convex functions respectively, where n is the number of local learners, ρ<1 is the spectral gap of the communication matrix, and T is the time horizon. However, there exist large gaps from the existing lower bounds, i.e., Omega(n√T) for convex functions and Omega(n) for strongly convex functions. To fill these gaps, in this paper, we first develop a novel D-OCO algorithm that can respectively reduce the regret bounds for convex and strongly convex functions to tildeO(nρ-1/4√T) and tildeO(nρ-1/2log T). The primary technique is to design an online accelerated gossip strategy that enjoys a faster average consensus among local learners. Furthermore, by carefully exploiting spectral properties of a specific network topology, we enhance the lower bounds for convex and strongly convex functions to Omega(nρ-1/4√T) and Omega(nρ-1/2log T), respectively. These results suggest that the regret of our algorithm is nearly optimal in terms of T, n, and ρ for both convex and strongly convex functions. Finally, we propose a projection-free variant of our algorithm to efficiently handle practical applications with complex constraints. Our analysis reveals that the projection-free variant can achieve O(nT3/4) and O(nT2/3(log T)1/3) regret bounds for convex and strongly convex functions with nearly optimal tildeO(ρ-1/2√T) and tildeO(ρ-1/2T1/3(log T)2/3) communication rounds, respectively.