A Second-Order Method for Strongly Convex L1-Regularization Problems

Abstract

In this paper a robust second-order method is developed for the solution of strongly convex l1-regularized problems. The main aim is to make the proposed method as inexpensive as possible, while even difficult problems can be efficiently solved. The proposed approach is a primal-dual Newton Conjugate Gradients (pdNCG) method. Convergence properties of pdNCG are studied and worst-case iteration complexity is established. Numerical results are presented on synthetic sparse least-squares problems and real world machine learning problems.

30 pages, 13 figures, 1 table

References in corpus (1)

• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (8)

• Parallel Selective Algorithms for Big Data Optimization
• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
• Flexible Parallel Algorithms for Big Data Optimization
• Robust Block Coordinate Descent
• Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems
• Generalized Conjugate Gradient Methods for ${\ell }_1$ Regularized Convex Quadratic Programming with Finite Convergence
• An Algorithm for Quadratic ${\ell }_1$-Regularized Optimization with a Flexible Active-Set Strategy
• A Preconditioner for a Primal-Dual Newton Conjugate Gradients Method for Compressed Sensing Problems