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

Technical Report ERGO-13-011

K. Fountoulakis and J. Gondzio

In this paper a second-order method for the solution of large-scale strongly convex L1-regularized problems is developed. The proposed method is a Newton-CG (Conjugate Gradients) algorithm with backtracking line-search embedded in a doubly-continuation scheme. Worst-case iteration complexity of the proposed Newton-CG is established. Based on the analysis of Newton-CG; worst-case iteration complexity of the doubly-continuation scheme is obtained. Numerical results are presented on large-scale problems for the doubly-continuation Newton-CG algorithm, which show that the proposed second-order method competes favourably with state-of-the-art first-order methods. In addition, L1-regularized Sparse Least-Squares problems are discussed for which a parallel block coordinate descent method stagnates.

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

PDF ERGO-13-011.pdf.

Written: June 20, 2013.
A major revision of this paper was prepared in April 1, 2014.
It was accepted for publication in Mathematical Programming.