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

Kimon Fountoulakis (K.Fountoulakissms.ed.ac.uk)
Jacek Gondzio (J.Gondzioed.ac.uk)

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 a synthetic sparse least-squares problem and two real world machine learning problems.

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

Category 1: Convex and Nonsmooth Optimization

Citation: Technical Report ERGO-13-011

Download: [PDF]

Entry Submitted: 06/22/2013
Entry Accepted: 06/22/2013
Entry Last Modified: 01/11/2015

Modify/Update this entry