An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization

Abstract

We study a Newton-like method for the minimization of an objective function that is the sum of a smooth convex function and an l-1 regularization term. This method, which is sometimes referred to in the literature as a proximal Newton method, computes a step by minimizing a piecewise quadratic model of the objective function. In order to make this approach efficient in practice, it is imperative to perform this inner minimization inexactly. In this paper, we give inexactness conditions that guarantee global convergence and that can be used to control the local rate of convergence of the iteration. Our inexactness conditions are based on a semi-smooth function that represents a (continuous) measure of the optimality conditions of the problem, and that embodies the soft-thresholding iteration. We give careful consideration to the algorithm employed for the inner minimization, and report numerical results on two test sets originating in machine learning.

References in corpus (1)

• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation

Cited by in corpus (8)

• Parallel Selective Algorithms for Big Data Optimization
• A Unified Successive Pseudo-Convex Approximation Framework
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Flexible Parallel Algorithms for Big Data Optimization
• Robust Block Coordinate Descent
• A Second-Order Method for Convex ${\ell }_1$-Regularized Optimization with Active Set Prediction
• Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems
• A Reduced-Space Algorithm for Minimizing ${\ell }_1$-Regularized Convex Functions