Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis

Abstract

Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent. Here we propose a general framework, which includes slightly modified versions of existing algorithms and also a new algorithm, which uses limited memory BFGS Hessian approximations, and provide a novel global convergence rate analysis, which covers methods that solve subproblems via coordinate descent.

References in corpus (2)

• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• Sparse Inverse Covariance Selection via Alternating Linearization Methods

Cited by in corpus (7)

• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Dual Extrapolation for Sparse Generalized Linear Models
• 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