Proximal Newton-Type Methods for Minimizing Composite Functions
By Jason D. Lee, Yuekai Sun, Michael A. Saunders. SIAM Journal on Optimization, 2012
340 citations recorded by the source corpus.
We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing smooth functions, even when search directions are computed inexactly. Many popular methods tailored to problems arising in bioinformatics, signal processing, and statistical learning are special cases of proximal Newton-type methods, and our analysis yields new convergence results for some of these methods.
Subfields: Computational Mechanics, Rheumatology
View Paper: https://www.semanticscholar.org/paper/2bb68a922f767a2da45e0f4b796b020e4ebf0750
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
- Peter Richtárik
- Francis R. Bach
- Robert Tibshirani
- Martin Jaggi
- Martin J. Wainwright
- Yuchen Zhang
- Martin Takác
- Stephen J. Wright
In Rheumatology
- Francis R. Bach
- Dmitrii Ostrovskii
- James T. Kwok
- Sebastian Pokutta
- Shusen Wang
- Lin Xiao
- Alejandro Carderera
- Martin J. Wainwright
Citations in the corpus
- A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization (2018, background): “[10] focused on using∇2 f̃ asH , and proved local convergence results under certain additional assumptions.”
- Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “Proximal Newton (Lee, Sun, and Saunders 2014), a second-order method, was developed to solve the problem, and later on, sub-sampling was incorporated to speed up computation (Liu et al. 2017).”
- Asynchronous Multi-task Learning (2016, background): “It was shown that the proposed algorithm has a linear convergence rate for a suitable step size under the assumption that the optimal strong convexity holds.”
- Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, methodology): “le proximal mapping. We modify Algorithm 1 and Algorithm 2 to minimize the composite function F(w). To modify Algorithm 1, we update wk+1 using an inexact version of the proximal-Newton method (e.g., [24, 50]). More specifically, the two steps in each iteration of Algorithm 1 are replaced with: 1. Fi”
- Finite-sample Analysis of M-estimators using Self-concordance (2018, methodology): “This observation can be exploited to accelerate computation of the estimator (38) when using proximal Newton-type methods (see [29]) via Hessian sketching, i.”
- Loss-aware Binarization of Deep Networks (2016, methodology): “The proximal Newton algorithm (Lee et al., 2014) has been popularly used for solving composite optimization problems of the form min x f(x) + g(x),”
- Statistical Learning with Sparsity: The Lasso and Generalizations (2015, background): “56)) defines a proximal Newton map (see the paper (Lee et al. 2014) for details).”
- Second-order Conditional Gradients (2020, methodology): “This has resulted in numerous inexact Quasi-Newton methods, which inherit many of the favorable properties of Newton methods (Scheinberg & Tang, 2016; Lee et al., 2014).”