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

Technical Report ERGO-14-005

K. Fountoulakis and J. Gondzio

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 method 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.

Key words: L1-regularization, Strongly convex optimization, Second-order methods, Iteration Complexity, Newton Conjugate-Gradients method.


Text
PDF ERGO-14-005.pdf.

History:
Written: April 1, 2014, revised October 14, 2014 and December 30, 2014.
to appear in: Mathematical Programming A (accepted for publication, February 10, 2015).
Published online 01 March 2015.

Related Software:
pdNCG primal-dual Newton Conjugate Gradients.