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

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

    Apr 10, 2026Sifan Yang, Dan-Yue Li, Lijun ZhangError FeedbackOnline Convex Optimization

  2. Revisiting Decentralized Online Convex Optimization with Compressed Communication

    Jul 2, 2026Hao Zhou, Xiaoyu Wang, Chang Yao +2Online Convex OptimizationFollow-the-Regularized-Leader

  3. Optimal Regret for Communication-Efficient Decentralized Online Learning

    Oct 28, 2026Sifan Yang, Wenhao Yang, Wei Jiang +2Decentralized OptimizationOnline Convex Optimization