Constrained Optimization with Compressed Gradients: A Dynamical Systems Perspective

Zhaoyue Xia, Jun Du, Chunxiao Jiang, H. Vincent Poor, Yong Ren

Abstract

Gradient compression is of growing interests for solving constrained optimization problems including compressed sensing, noisy recovery and matrix completion under limited communication resources and storage costs. Convergence analysis of these methods from the dynamical systems viewpoint has attracted considerable attention because it provides a geometric demonstration towards the shadowing trajectory of a numerical scheme. In this work, we establish a tight connection between a continuous-time nonsmooth dynamical system called a perturbed sweeping process (PSP) and a projected scheme with compressed gradients. Theoretical results are obtained by analyzing the asymptotic pseudo trajectory of a PSP. We show that under mild assumptions a projected scheme converges to an internally chain transitive invariant set of the corresponding PSP. Furthermore, given the existence of a Lyapunov function $V$ with respect to a set $\Lambda$, convergence to $\Lambda$ can be established if $V(\Lambda)$ has an empty interior. Based on these theoretical results, we are able to provide a useful framework for convergence analysis of projected methods with compressed gradients. Moreover, we propose a provably convergent distributed compressed gradient descent algorithm for distributed nonconvex optimization. Finally, numerical simulations are conducted to confirm the validity of theoretical analysis and the effectiveness of the proposed algorithm.

Introduction

In modern machine learning—especially federated learning and decentralized optimization—gradients are often compressed (quantized or sparsified) to reduce transmission overhead and storage costs. However, analyzing the convergence of these "noisy" algorithms in a constrained setting, where the solution must stay within a specific set $C$, is notoriously difficult. Traditional numerical analysis provides convergence rates but often lacks geometric intuition. Furthermore, the projection step used to keep iterations within the constraint set introduces nonsmoothness, making standard calculus-based proofs break down.

This paper bridges the gap between discrete constrained optimization and continuous-time dynamical systems by linking compressed gradient schemes to a mathematical framework called "perturbed sweeping processes" (PSP). The authors provide a unified theoretical template to prove the convergence of popular algorithms even when gradients are heavily compressed.

Methodology: The Dynamical Systems Perspective

Instead of looking only at discrete steps ($x_{k+1}$), the researchers analyze the continuous-time "shadow" of the algorithm. The core of this approach involves several key components:

  • Perturbed Sweeping Process (PSP): The optimization is modeled as a differential inclusion where the "velocity" of the system is pushed by the gradient but "swept" back by the boundaries of the constraint set using normal cones.
  • Asymptotic Pseudo Trajectories: The authors prove that the discrete iterations of a compressed gradient algorithm closely follow the continuous-time trajectory of a PSP.
  • Nonsmooth Lyapunov Theory: To prove stability, they utilize "Lyapunov pairs"—functions that represent the "energy" of the system—adapted for nonsmooth, time-varying dynamics.

Theoretical Framework

The most significant insight is that discrete projected iterations with vanishing step sizes are essentially discretized versions of continuous sweeping processes. This allows researchers to use the rich toolkit of dynamical systems to analyze optimization.

Convergence analysis framework linking the continuous-time Perturbed Sweeping Process to discrete iterative schemes.

As shown in the framework above, the process begins with the Perturbed Sweeping Process. By checking specific conditions (Assumption 1) and establishing the existence of a Lyapunov pair, the discrete scheme derived via Euler discretization is proven to converge to a set $\Lambda$. This framework isn't just for one algorithm; it provides a "recipe" to prove convergence for Stochastic PGD, Projected Nesterov Accelerated Gradient (PNAG), and Projected Optimized Gradient Methods (POGM) under a single theoretical roof.

The DPCGD Algorithm and Numerical Validation

The authors propose a new Distributed Projected Compressed Gradient Descent (DPCGD) algorithm. It allows multiple agents to compute noisy gradients, compress them, and send them to a central server while maintaining provable convergence to a Karush-Kuhn-Tucker (KKT) point. The theory was validated using several benchmarks:

  • Six-Hump Camel Back Function: In this nonconvex landscape, the authors found that the "noise" introduced by gradient compression can actually help momentum-based methods escape saddle points that would otherwise trap them.
  • Wireless Power Allocation: In a practical simulation of a wireless network, the authors demonstrated that using a 6-bit compressor achieved nearly identical performance to full 32-bit precision while significantly reducing the data transmitted over the network.

Key Results and Conclusion

The authors proved that under mild assumptions, the sequence of iterates converges to an "internally chain transitive invariant set"—essentially the set of stationary points of the problem. Simulations showed that momentum-based methods (PNAG, POGM) maintain their $O(1/k^2)$ convergence advantage even with projections and compression.

While the current theory relies on the constraint set $C$ being compact and convex, it provides a robust foundation for future work. The authors suggest moving toward even more aggressive compression, such as 1-bit quantization, and exploring decentralized optimization on time-varying graphs.

Summary updated

Abstract

Gradient compression is of growing interests for solving constrained optimization problems including compressed sensing, noisy recovery and matrix completion under limited communication resources and storage costs. Convergence analysis of these methods from the dynamical systems viewpoint has attracted considerable attention because it provides a geometric demonstration towards the shadowing trajectory of a numerical scheme. In this work, we establish a tight connection between a continuous-time nonsmooth dynamical system called a perturbed sweeping process (PSP) and a projected scheme with compressed gradients. Theoretical results are obtained by analyzing the asymptotic pseudo trajectory of a PSP. We show that under mild assumptions a projected scheme converges to an internally chain transitive invariant set of the corresponding PSP. Furthermore, given the existence of a Lyapunov function $V$ with respect to a set $Λ$, convergence to $Λ$ can be established if $V(Λ)$ has an empty interior. Based on these theoretical results, we are able to provide a useful framework for convergence analysis of projected methods with compressed gradients. Moreover, we propose a provably convergent distributed compressed gradient descent algorithm for distributed nonconvex optimization. Finally, numerical simulations are conducted to confirm the validity of theoretical analysis and the effectiveness of the proposed algorithm.
BibTeX
@misc{xia2024constrained,
  author = {Zhaoyue Xia and Jun Du and Chunxiao Jiang and H. Vincent Poor and Yong Ren},
  title = {{Constrained Optimization with Compressed Gradients: A Dynamical Systems Perspective}},
  year = {2024},
  eprint = {2407.18469},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.18469},
}
Figure