Decentralized Online Learning with Hard Constraints: A Doubly-Bounded Queue Approach

We consider decentralized online convex optimization with time-varying constraints and conduct performance analysis using two stringent metrics: network dynamic regret with respect to the online global solution benchmark, and hard constraint violation that does not allow any compensated violation over time and learners. We propose an efficient algorithm called Constrained Online Learning with Doubly-bounded Queue (COLDQ), which introduces a novel virtual queue that is both lower and upper bounded, allowing tight control of the constraint violation without needing the Slater’s condition. We prove via a new Lyapunov drift analysis that COLDQ provides O(T 1+Vx/2 ) network dynamic regret and O(min{T 3+Vx/4 ; TVg }) hard constraint violation, where Vx and Vg capture the dynamics of the loss and constraint functions. For the first time, the two bounds smoothly approach to the best-known O(T 1/2 ) regret and O(1) violation, as the dynamics of the losses and constraints diminish, under both centralized and decentralized settings. For strongly convex loss functions, COLDQ provides O(log T) static regret and O(min{T1/2 (log T)1/2 , TVg }) hard constraint violation. Simulation results based on synthetic and canonical datasets demonstrate that COLDQ substantially outperforms the state-of-the-art approaches for both convex and non-convex loss functions.