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:
- 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.
- 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