On the Linear Convergence of the Approximate Proximal Splitting Method for Non-smooth Convex Optimization
By Mojtaba Kadkhodaie, Maziar Sanjabi, Zhi-Quan Tom Luo. 2014
18 citations recorded by the source corpus.
Consider the problem of minimizing the sum of two convex functions, one being smooth and the other non-smooth. In this paper, we introduce a general class of approximate proximal splitting (APS) methods for solving such minimization problems. Methods in the APS class include many well-known algorithms such as the proximal splitting method, the block coordinate descent method (BCD), and the approximate gradient projection methods for smooth convex optimization. We establish the linear convergence of APS methods under a local error bound assumption. Since the latter is known to hold for compressive sensing and sparse group LASSO problems, our analysis implies the linear convergence of the BCD method for these problems without strong convexity assumption.
Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Mark W. Schmidt
- Julie Nutini
- Hamed Karimi
- Nicolas Loizou
- Simon Lacoste-Julien
- Peter Richtárik
- Issam Hadj Laradji
- Sharan Vaswani
In Computational Mechanics
- Mark W. Schmidt
- Julie Nutini
- Hamed Karimi
- Nicolas Loizou
- Peter Richtárik
- Simon Lacoste-Julien
- Sebastian U. Stich
- Sharan Vaswani
In Mathematical Physics
- Mark W. Schmidt
- Hamed Karimi
- Julie Nutini
- Nicolas Loizou
- Simon Lacoste-Julien
- Sharan Vaswani
- Issam Hadj Laradji
- Mehrdad Mahdavi
Citations in the corpus
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, background): “⊓⊔ While other conditions have been proposed to show linear convergence rates of proximal-gradient methods without SC [Kadkhodaie et al., 2014, Zhang, 2015], their analyses tend to be much more complicated than the above while, as we discuss in the next section, the proximal-PL inequality includes…”