Constrained Optimization with Compressed Gradients: A Dynamical Systems Perspective

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.