Distributed Online Convex Optimization with Long-Term Constraints: No Cumulative Constraint Violation

This paper investigates the problem of distributed online optimization with long-term constraints (LTC), where constraints are not required to be satisfied at each time step but only over a longer horizon. We first propose a baseline algorithm based on online regularized Lagrangian functions, achieving a regret bound of O(T3/4). By refining the Lagrangian functions and optimization strategies, we further improve the regret bound to O(T2/3). Notably, our results enforce strict satisfaction of LTC over time, in contrast to most existing works that focus solely on achieving sublinear cumulative constraint violations. Moreover, the obtained performance matches the optimal guarantees achievable in the centralized setting. Finally, we demonstrate the effectiveness of our approach through a distributed online regularized linear regression problem.