Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis

Xiangfeng Wang, Jane J. Ye, Xiaoming Yuan, Shangzhi Zeng, Jin ZhangSet-Valued 2018 · arXiv

Abstract

This paper develops a novel perturbation framework for the convergence analysis of first-order algorithms applied to nonsmooth and nonconvex optimization problems. By constructing a perturbed stationary point set-valued map—where the perturbing parameter is defined by the difference between consecutive iterates—we establish that the "calmness" of this map, combined with a local separation of stationary values, is sufficient for linear convergence. We demonstrate that this calmness condition is equivalent to the calmness of canonically perturbed maps, allowing the application of modern variational analysis tools. Our findings reveal that the Proximal Gradient (PG) method converges to proximal stationary points, which are of higher quality than standard limiting stationary points. The framework is extended to provide linear convergence guarantees for the Alternating Direction Method of Multipliers (ADMM) and the Primal-Dual Hybrid Gradient (PDHG) method under mild assumptions.

Introduction

In the era of large-scale data processing, first-order methods have become the standard for optimization due to their low computational cost per iteration. While these methods frequently exhibit linear convergence in practice, providing rigorous mathematical proofs for this behavior in nonsmooth and nonconvex landscapes remains a significant challenge. Traditional analysis often relies on global error bounds, which are frequently difficult to verify for specific application models. This paper introduces a new analytical toolkit based on variational analysis to bridge the gap between numerical performance and theoretical understanding.

The Limitations of Existing Frameworks

Historically, proving the linear convergence of algorithms like the Proximal Gradient (PG) method has relied on the Luo-Tseng error bound or similar conditions. However, these approaches face two primary hurdles:

  1. Verifiability: These bounds are often abstract, making it nearly impossible for practitioners to determine if a specific model (e.g., a neural network or a complex statistical estimator) satisfies them.
  2. Solution Quality: Standard convergence theory typically only guarantees that an algorithm will reach a "limiting stationary point." In nonconvex optimization, these points can represent poor-quality solutions or even local maxima.

A Variational Analysis Approach

To overcome these limitations, we shift the focus from global error bounds to the local properties of set-valued maps. Our methodology centers on a new perturbation technique:

Algorithmic Perturbation

We analyze the iteration scheme of an algorithm (such as $x^{k+1} \in \text{Prox}(x^k - \nabla f(x^k))$) by treating the step difference, $x^k - x^{k+1}$, as a perturbation of the system's optimality conditions. This allows us to define a set-valued map that tracks how the set of "almost-stationary" points behaves as the algorithm progresses.

The Role of Calmness

The central concept in our analysis is calmness. In variational analysis, calmness measures the sensitivity of a set-valued map to small perturbations. We prove that the calmness of our algorithm-specific map is equivalent to the calmness of a "canonically perturbed" stationary point map. This equivalence is crucial because it allows us to leverage existing, sophisticated tools from variational analysis to verify convergence for concrete problems.

Key Theoretical Insights

Sharper Stationary Points

One of the most significant findings of this research is that the PG method converges to proximal stationary points. This is a more restrictive and "sharper" condition than the standard limiting stationary point. This discovery suggests that the PG method possesses an inherent bias toward finding higher-quality solutions in nonconvex landscapes than previously recognized by theory.

Localized Analysis

Unlike global error bounds, calmness is a point-based property. It only needs to hold in the neighborhood of the algorithm's accumulation point. This localization makes the condition significantly easier to verify for popular nonconvex penalties used in statistics and machine learning, such as the Smoothly Clipped Absolute Deviation (SCAD) and the Minimax Concave Penalty (MCP).

Relaxing Convex Assumptions

In the context of convex optimization, our framework allows for the proof of linear convergence without requiring the common assumption that the set of optimal solutions is compact (bounded). This broadens the applicability of the theory to a wider range of mathematical models.

Applications and Results

We establish a general Linear Convergence Theorem: if the induced set-valued map is calm and the objective function values are properly separated at stationary points, the algorithm is guaranteed to converge at a linear rate.

We successfully apply this "perturbation recipe" to several foundational algorithms:

  • Proximal Gradient (PG) Method: Enhanced convergence rates and solution quality guarantees.
  • ADMM and PDHG: We provide a unified framework showing that these methods also enjoy linear convergence under milder, calmness-based assumptions.

Conclusion

By introducing perturbation techniques rooted in variational analysis, this work provides a more flexible and verifiable framework for understanding the convergence of first-order methods. While verifying these conditions still requires expertise in variational geometry—specifically regarding limiting normal cones—the shift toward calmness-based analysis offers a clearer path for proving the efficiency of optimization algorithms in complex, nonsmooth, and nonconvex environments.

Summary updated

Abstract

We develop new perturbation techniques for conducting convergence analysis of various first-order algorithms for a class of nonsmooth optimization problems. We consider the iteration scheme of an algorithm to construct a perturbed stationary point set-valued map, and define the perturbing parameter by the difference of two consecutive iterates. Then, we show that the calmness condition of the induced set-valued map, together with a local version of the proper separation of stationary value condition, is a sufficient condition to ensure the linear convergence of the algorithm. The equivalence of the calmness condition to the one for the canonically perturbed stationary point set-valued map is proved, and this equivalence allows us to derive some sufficient conditions for calmness by using some recent developments in variational analysis. These sufficient conditions are different from existing results (especially, those error-bound-based ones) in that they can be easily verified for many concrete application models. Our analysis is focused on the fundamental proximal gradient (PG) method, and it enables us to show that any accumulation of the sequence generated by the PG method must be a stationary point in terms of the proximal subdifferential, instead of the limiting subdifferential. This result finds the surprising fact that the solution quality found by the PG method is in general superior. Our analysis also leads to some improvement for the linear convergence results of the PG method in the convex case. The new perturbation technique can be conveniently used to derive linear rate convergence of a number of other first-order methods including the well-known alternating direction method of multipliers and primal-dual hybrid gradient method, under mild assumptions.
BibTeX
@inproceedings{wang2018perturbation,
  author = {Xiangfeng Wang and Jane J. Ye and Xiaoming Yuan and Shangzhi Zeng and Jin Zhang},
  title = {{Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis}},
  booktitle = {Set-Valued},
  year = {2018},
}
Figure