DC Proximal Newton for Nonconvex Optimization Problems
Authors:
- 21 April 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks and Learning Systems
- Vol. 27 (3) , 636-647
Abstract
We introduce a novel algorithm for solving learning problems where both the loss function and the regularizer are nonconvex but belong to the class of difference of convex (DC) functions. Our contribution is a new general purpose proximal Newton algorithm that is able to deal with such a situation. The algorithm consists in obtaining a descent direction from an approximation of the loss function and then in performing a line search to ensure a sufficient descent. A theoretical analysis is provided showing that the iterates of the proposed algorithm admit as limit points stationary points of the DC objective function. Numerical experiments show that our approach is more efficient than the current state of the art for a problem with a convex loss function and a nonconvex regularizer. We have also illustrated the benefit of our algorithm in high-dimensional transductive learning problem where both the loss function and regularizers are nonconvex.Keywords
All Related Versions
Funding Information
- Agence Nationale de la Recherche (12-BS02-004, 09-EMER-001, 12-BS03-003)
This publication has 30 references indexed in Scilit:
- Optimization with Sparsity-Inducing PenaltiesFoundations and Trends in Machine Learning, 2012
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- $\ell_{p}-\ell_{q}$ Penalty for Sparse Linear and Sparse Multiple Kernel Multitask LearningIEEE Transactions on Neural Networks, 2011
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse ProblemsSIAM Journal on Imaging Sciences, 2009
- The Adaptive Lasso and Its Oracle PropertiesJournal of the American Statistical Association, 2006
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solutionCommunications on Pure and Applied Mathematics, 2006
- The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization ProblemsAnnals of Operations Research, 2005
- Asymptotics for lasso-type estimatorsThe Annals of Statistics, 2000
- A D.C. Optimization Algorithm for Solving the Trust-Region SubproblemSIAM Journal on Optimization, 1998
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998