Abstract
In this paper, we study the local linear convergence properties of a versatile class of Primal-Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework we first show that (i) the sequences generated by Primal-Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal-Dual splitting can be specialized to cover existing ones on Forward-Backward splitting and Douglas-Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning, etc. The demonstration not only verifies the local linear convergence behaviour of Primal-Dual splitting methods, but also the insights on how to accelerate them in practice.
Introduction
Many modern problems in image processing, machine learning, and inverse problems are formulated as non-smooth convex optimization tasks. Because the objective functions are often non-differentiable—for instance, when using the $\ell_1$ norm to promote sparsity—standard gradient descent techniques are inapplicable. Instead, researchers rely on "splitting" methods, which decompose complex problems into simpler, manageable proximal steps.
While these methods are theoretically known to converge globally at sublinear rates (typically $O(1/k)$), practitioners frequently observe a "speed up" to linear convergence as the algorithm approaches the solution. This paper addresses the lack of a unified theoretical framework to explain this behavior for the broad class of Primal-Dual (PD) splitting methods, particularly in cases where strong convexity is absent.
The Primal-Dual Splitting Framework
The authors analyze a versatile class of Primal-Dual splitting algorithms, including the widely used Chambolle-Pock and Condat-Vũ schemes. The general iterative structure of these methods is captured in Algorithm 1.
As shown in the figure, the algorithm involves alternating proximal updates for primal ($x$) and dual ($v$) variables, linked by a linear operator $L$ and a relaxation parameter $ heta$. This structure allows for the efficient handling of composite objectives involving smooth and non-smooth terms.
Theoretical Analysis via Partial Smoothness
The core of the proposed analysis leverages the concept of Partial Smoothness (PSF). The authors' approach involves several key theoretical steps:
- Manifold Identification: They prove that under a "non-degeneracy" condition, the algorithm's iterates will land on specific smooth manifolds—representing the "active" structure of the solution, such as a specific sparsity pattern—after a finite number of iterations.
- The Product Space Trick: By reformulating the Primal-Dual algorithm as a Forward-Backward splitting method in a specifically constructed Hilbert space, they apply geometric analysis tools to the combined primal and dual variables.
- Linearization: Once the algorithm identifies the active manifolds, the previously non-linear iteration behaves like a linear operator. This allows the convergence rate to be characterized using the spectral properties (eigenvalues) of that operator.
Key Insights and Results
The study provides several critical insights into the behavior of PD methods:
- Finite Identification: The most significant finding is that non-smoothness is often highly structured. The algorithm doesn't merely wander; it "discovers" the geometry of the solution (e.g., which pixels constitute an edge in an image) in finite time.
- The Role of $\theta$: The paper highlights the importance of the relaxation parameter $\theta$. While $\theta=1$ is a standard choice, the authors demonstrate that locally, choosing $\theta > 1$ can significantly accelerate convergence, though it requires careful tuning to maintain stability.
- Explaining Oscillations: The theory explains why Primal-Dual methods often exhibit "spiraling" or oscillatory behavior near a solution. This is attributed to the presence of complex eigenvalues in the linearized iteration matrix, a phenomenon typically absent in simpler Forward-Backward methods.
- Empirical Validation: Numerical experiments on linear inverse problems and Total Variation (TV) denoising show a perfect match between practical error observations and the theoretical slope predicted by eigenvalue analysis.
Conclusion and Future Work
This work provides a rigorous explanation for the observed local linear convergence of Primal-Dual splitting methods. By showing that these methods are part of a larger geometric family including Forward-Backward and ADMM, the authors offer a unified perspective on splitting algorithms.
However, the analysis remains strictly local, providing no bound on the number of iterations required to reach the linear regime. Additionally, the reliance on a "non-degeneracy" condition suggests that identification may be less clean if a solution lies in an unstable region of the non-smooth constraints. Future research may focus on developing robust adaptive versions of these algorithms to automatically find optimal local parameters like $\theta$.
Summary updated