cs.LGNov 9, 2026

KKT-Perturbation-Aware Communication for Fully Distributed Online Convex Optimization with Nonseparable Coupling

Authors: Zhaoye Pan, Tao Li, Yunjie Guo, Guanpu Chen

Organizations: Department of Systems Engineering, City University of Hong Kong, Hong Kong SAR, China · State Grid Electric Power Research Institute, Nanjing, China · School of Automation, Southeast University, Nanjing, China

Abstract

Nonseparable costs and coupled constraints in distributed online convex optimization often arise when system performance and operational constraints depend on the joint configuration of all agents and cannot be decomposed into individual contributions. Such nonseparability leads to fully distributed decision-making with challenging partial local information, where each agent evaluates its local primal-dual update using estimated global information via a local belief of the joint action and the shared Lagrange multiplier to be exchanged with neighbors. While the belief consensus established by prior works ensures no-regret learning, exchanging beliefs comprising full-dimensional primal and dual states at every round imposes a communication overhead that scales with both the joint decision dimension and the network size. Existing event-triggered schemes typically activate communication according to state variation or consensus error. Under nonseparable coupling, however, errors of equal magnitude can produce markedly different perturbations after passing through the KKT operator. We therefore propose a randomized KKT-perturbation-aware communication mechanism, where the triggering of each agent's primal and dual communication channels depends on their impact on the KKT operator. The proposed mechanism transfers the adaptive-sampling principle of coordinate descent from allocating computation across decision blocks to allocating communication across information channels: channels with larger estimated perturbations receive greater priority for refresh. Under standard regularity assumptions, the resulting algorithm achieves O(T2/3)O({T}^{2/3}) expected static regret and O(T2/3)O({T}^{2/3}) expected cumulative constraint violation. Numerical experiments demonstrate improved learning and constraint-enforcement performance per transmitted bit over belief consensus baselines.

Figures & tables

Explore similar work

Apr 10, 2026

Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications

Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial in large-scale applications. To alleviate this bottleneck, we initiate the study of D-OCO with compressed communication. Firstly, to quantify the compression impact, we establish the Ω(δ−1/2T)Ω(δ^{-1/2}\sqrt{T}) and Ω(δ−1log⁡T)Ω(δ^{-1}\log{T}) lower bounds for convex and strongly convex loss functions, respectively, where δ∈(0,1]δ\in (0,1] is the compression ratio. Secondly, we propose an optimal algorithm, which enjoys regret bounds of O(δ−1/2T)O(δ^{-1/2}\sqrt{T}) and O(δ−1log⁡T)O(δ^{-1} \log T) for convex and strongly convex loss functions, respectively. Our method incorporates the error feedback mechanism into the Follow-the-Regularized-Leader framework to address the coupling between the compression error and the projection error. Furthermore, we employ the online compression strategy to mitigate the accumulated error arising from the bidirectional compression. Our online method has great generality, and can be extended to the offline stochastic setting via online-to-batch conversion. We establish convergence rates of O(δ−1/2T−1/2)O(δ^{-1/2}T^{-1/2}) and O(δ−1T−1)O(δ^{-1} T^{-1}) for convex and strongly convex loss functions, respectively, providing the first guarantees for distributed non-smooth optimization with compressed communication and domain constraints.
Jul 2, 2026

Revisiting Decentralized Online Convex Optimization with Compressed Communication

Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.
Oct 28, 2026

Optimal Regret for Communication-Efficient Decentralized Online Learning

In this paper, we investigate decentralized online convex optimization with compressed communication, where nn learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are O(ω−1/2nρ−1Tln⁡n)O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n}) and O(ω−1nρ−2ln⁡nln⁡T)O(ω^{-1}nρ^{-2}\ln n\ln T) for convex and strongly convex loss functions, respectively, where ρ∈(0,1)ρ\in(0,1) is the spectral gap of the communication matrix and ω∈(0,1]ω\in(0,1] is the compression quality factor. Compared with the corresponding lower bounds of Ω(ω−1/2nρ−1/4T)Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T}) and Ω(ω−1nρ−1/2ln⁡T)Ω(ω^{-1}nρ^{-1/2}\ln T), these upper bounds exhibit polynomial gaps in their dependence on ρ−1ρ^{-1}. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of O~(ω−1/2nρ−1/4T)\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T}) and O~(ω−1nρ−1/2ln⁡T)\widetilde O(ω^{-1}nρ^{-1/2}\ln T) for convex and strongly convex loss functions, respectively. Up to logarithmic factors in nn and ρ−1ρ^{-1}, these results match the lower bounds in terms of TT, nn, ρρ, and ωω.