A convergence framework for inexact nonconvex and nonsmooth algorithms and its applications to several iterations

Tao Sun, Hao Jiang, Lizhi Cheng, Wei Zhu

Abstract

This paper establishes a robust mathematical framework for analyzing the convergence of inexact nonconvex and nonsmooth algorithms. By introducing "pseudo" sufficient descent and relative error conditions linked to an auxiliary sequence, the authors provide a generalized theory that accommodates numerical noise and calculation errors common in real-world iterations. Under the assumption of the Kurdyka-Łojasiewicz (KŁ) property and a summable noise sequence, we prove that the generated iterates converge to a critical point of the objective function. The core of this analysis is a novel Lyapunov function that buffers the objective function against non-monotonicity. Finally, the framework is applied to several classical iterations, including ADMM and Proximal Gradient methods, providing new convergence guarantees for their inexact variants.

Introduction

In the landscape of nonconvex and nonsmooth optimization, proving that an algorithm will actually reach a solution is a fundamental challenge. Since approximately 2013, researchers have largely relied on a standard framework requiring three strict criteria: sufficient descent (the objective must decrease at every step), relative error (the gradient must be bounded by the step size), and continuity.

However, there is a significant gap between this idealized theory and algorithmic reality. In practice, algorithms are often "inexact." They may involve stochastic gradients, approximate solutions to sub-problems, or floating-point errors. These perturbations frequently violate the strict sufficient descent rule—a noisy step might occasionally increase the objective function. This paper bridges that gap by introducing a framework that remains robust even when traditional descent conditions fail.

The Limitations of Classical Descent

Traditional convergence proofs are "non-robust" because they require noise to be strictly bounded by the change in iterates. If the step size is small, even tiny amounts of noise can break the proof. The authors address this by replacing strict requirements with "pseudo" conditions.

Instead of requiring the objective function $F(x)$ to decrease at every step, the framework allows for a noise term $\eta_k$. As long as this noise sequence is "summable"—meaning the total error accumulated over time is finite—the algorithm can still be proven to converge. This shift allows for a much more realistic modeling of modern iterative solvers.

Technical Innovation: The Noise-Buffered Lyapunov Function

The primary technical hurdle in analyzing non-descent algorithms is that the objective function no longer acts as a reliable "energy" measure that decreases toward a minimum. To solve this, the authors construct a new Lyapunov function:

$$\xi(z) = F(x) + \frac{t^\theta}{\theta}$$

In this construction, $F(x)$ is the objective function, and $t$ is an auxiliary term representing the remaining cumulative noise in the system. While $F(x)$ might fluctuate, this combined Lyapunov function $\xi(z)$ is guaranteed to decrease monotonically. This "noise buffer" trick effectively transforms a chaotic, non-monotone process into a structured one that is amenable to analysis.

The Kurdyka-Łojasiewicz (KŁ) Property

To ensure the algorithm doesn't just slow down but actually settles at a specific point, the authors leverage the KŁ property. This geometric condition is satisfied by most "tame" functions used in machine learning, such as semi-algebraic functions. By applying the KŁ property to the new Lyapunov function, the authors prove that the sequence of iterates has a finite total length, preventing the algorithm from wandering indefinitely and ensuring convergence to a critical point.

Broad Algorithmic Applications

A major strength of this framework is its generality. The authors demonstrate that their "pseudo" conditions are satisfied by the inexact versions of five major algorithmic classes:

  1. Inexact Proximal Gradient: Handling errors in the proximal operator.
  2. Inexact PALM (Proximal Alternating Linearized Minimization): Used in matrix factorization.
  3. Inexact Proximal Reweighted Algorithms: Common in sparse recovery.
  4. Inexact DC (Difference of Convex) Algorithms: Used in nonsmooth optimization.
  5. Inexact ADMM (Alternating Direction Method of Multipliers): A staple of distributed optimization.

For many of these, this paper provides the first formal proof of convergence for their inexact implementations under such relaxed conditions.

Conclusion and Future Directions

This research provides a unified lens through which we can view a wide variety of optimization algorithms. It establishes that as long as noise vanishes at a sufficient rate—specifically $O(1/k^\alpha)$ where $\alpha > 1$—convergence is maintained.

While the framework is powerful, it currently focuses on global convergence (the "if" and "where") rather than the specific rate of convergence (the "how fast"). Future work may extend these Lyapunov techniques to derive convergence rates for inexact methods and further relax the parameter constraints required for complex algorithms like ADMM.

Summary updated

Abstract

In this paper, we consider the convergence of an abstract inexact nonconvex and nonsmooth algorithm. We promise a pseudo sufficient descent condition and a pseudo relative error condition, which are both related to an auxiliary sequence, for the algorithm; and a continuity condition is assumed to hold. In fact, a lot of classical inexact nonconvex and nonsmooth algorithms allow these three conditions. Under a special kind of summable assumption on the auxiliary sequence, we prove the sequence generated by the general algorithm converges to a critical point of the objective function if being assumed Kurdyka- Lojasiewicz property. The core of the proofs lies in building a new Lyapunov function, whose successive difference provides a bound for the successive difference of the points generated by the algorithm. And then, we apply our findings to several classical nonconvex iterative algorithms and derive the corresponding convergence results
BibTeX
@misc{sun2017convergence,
  author = {Tao Sun and Hao Jiang and Lizhi Cheng and Wei Zhu},
  title = {{A convergence framework for inexact nonconvex and nonsmooth algorithms and its applications to several iterations}},
  year = {2017},
  eprint = {1709.04072},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.04072},
}
Figure