Nearly Optimal Regret 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 (n^5/4^-1/2T) and O (n^3/2^-1 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. , (nT) for convex functions and (n) for strongly convex functions. To fill these gaps, in this paper, we first develop novel D-OCO algorithms that can respectively reduce the regret bounds for convex and strongly convex functions to O (n^-1/4T) and O (n^-1/2 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 the spectral properties of a specific network topology, we enhance the lower bounds for convex and strongly convex functions to (n^-1/4T) and (n^-1/2), respectively. These lower bounds suggest that our algorithms are nearly optimal in terms of T, n, and.