Distributed Constrained Online Nonconvex Optimization with Compressed Communication

Kunpeng Zhang, Lei Xu, Xinlei Yi, Ming Cao, Karl Henrik Johansson, Tianyou Chai, Tao Yang

Introduction

In the era of large-scale decentralized systems—ranging from autonomous drone swarms to massive sensor networks—agents are frequently required to solve complex optimization problems in real-time. These tasks are characterized by three primary challenges: they are online (data arrives sequentially), distributed (lacking a central coordinator), and nonconvex (possessing complex, non-linear landscapes). Furthermore, these systems must operate under time-varying constraints and strict communication bandwidth limitations.

Existing literature has addressed these components in isolation, but a unified framework handling nonconvexity, dynamic constraints, and compressed communication over time-varying networks has remained elusive. This paper introduces a novel Distributed Online Primal–Dual Algorithm with Compressed Communication that bridges this gap, proving that communication efficiency does not have to come at the cost of optimization performance.

Problem Statement

The research focuses on a network of agents represented by a time-varying graph. Each agent aims to minimize a local, potentially nonconvex objective function while adhering to local constraints that may change at each time step. The global objective is to minimize the aggregate cost across the network while ensuring that the cumulative constraint violations remain sublinear over time.

Two specific hurdles are addressed:

  1. Dynamic Constraints: Real-world rules, such as obstacle avoidance or battery thresholds, are rarely static.
  2. Communication Bottlenecks: Continuous high-precision data exchange is energy-intensive. While compression techniques exist, they often fail when the network topology is dynamic.

Methodology

The proposed solution utilizes a Distributed Online Primal–Dual Algorithm integrated with a sophisticated communication compression strategy.

Primal-Dual Framework

To avoid the high computational cost of "projection" operations (mapping variables back into a feasible set at every step), the algorithm employs a primal-dual approach. It maintains primal variables for decision-making and dual variables that act as dynamic penalties for constraint violations. This allows the system to satisfy constraints over the long term (on average) rather than strictly at every millisecond.

Difference Compression

A key innovation is the use of difference compression. Instead of broadcasting full state vectors, agents transmit a compressed version of the difference between their current state and an estimate of their previous state. This significantly reduces the bits transmitted per round. To handle the errors introduced by compression, the algorithm incorporates a compensation mechanism that ensures information eventually propagates correctly across the network.

Dynamic Network Handling

The algorithm is designed for time-varying undirected graphs. By utilizing a doubly stochastic mixing matrix, the framework ensures that even as links appear and disappear, the agents can still reach a consensus and optimize the global objective.

Theoretical Results

The authors provide rigorous proofs demonstrating that their algorithm achieves state-of-the-art performance despite the use of lossy compression.

Regret and Constraint Violation

For nonconvex functions, finding a global optimum is NP-hard. Therefore, the paper evaluates performance using Stationary Point Regret, which measures how quickly the agents converge to a first-order optimal (stable) point.

  • Network Regret: The algorithm achieves a bound of $O(\sqrt{T})$, matching the performance of uncompressed distributed nonconvex optimization algorithms.
  • Constraint Violation: The general bound is $O(T^{3/4})$. However, if the problem satisfies Slater’s condition (the existence of a point that strictly satisfies all constraints), the bound improves to $O(\sqrt{T})$.

The most significant takeaway is that compression is "theoretically free": the sublinear bounds for regret and violation are identical to those achieved with perfect, uncompressed communication.

Experimental Evaluation: Sensor Localization

The algorithm was tested on a Distributed Online Localization Problem involving 100 sensors tracking a moving target. The simulation used a time-varying network where connections were generated randomly.

The results confirmed the theoretical findings: the proposed algorithm achieved nearly identical tracking accuracy and constraint satisfaction as uncompressed methods while using a fraction of the communication bandwidth. This demonstrates the algorithm's practical utility for resource-constrained hardware in dynamic environments.

Conclusion and Future Directions

This work establishes a robust framework for distributed nonconvex optimization under communication constraints. By proving that compression does not degrade the fundamental convergence rates, the authors provide a strong theoretical foundation for more efficient decentralized AI.

Future research may explore:

  • Bandit Feedback: Adapting the method for scenarios where agents only receive a scalar reward rather than a full gradient.
  • Asynchronous Communication: Moving beyond synchronized rounds to accommodate networks with significant latency or "straggler" nodes.
  • Global Optimality: Investigating specific classes of nonconvex functions where global optima might be reachable.

Summary updated

BibTeX
@inproceedings{zhang2025distributed,
  author = {Kunpeng Zhang and Lei Xu and Xinlei Yi and Ming Cao and Karl Henrik Johansson and Tianyou Chai and Tao Yang},
  title = {{Distributed Constrained Online Nonconvex Optimization with Compressed Communication}},
  booktitle = {CDC},
  year = {2025},
  doi = {10.1109/cdc57313.2025.11312327},
}
Figure