Optimization Online


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

Kimon Fountoulakis (K.Fountoulakis***at***sms.ed.ac.uk)
Jacek Gondzio (J.Gondzio***at***ed.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society