Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis

2013/11/26 by Katya Scheinberg, Scheinberg, Katya, Xiaocheng Tang +1 · 10 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Iterative Methods for Nonlinear Equations #Sparse and Compressive Sensing Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1311.6547

arxiv created 2015/07/14 · arxiv updated 2015/07/15

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.

Cited by

• A Second-Order Method for Convex ℓ₁-Regularized Optimization with Active Set Prediction
• Dual Extrapolation for Sparse Generalized Linear Models
• CaCuTe: Casual Cubic-Model Technique for Faster Optimization
• A Reduced-Space Algorithm for Minimizing ℓ₁-Regularized Convex Functions
• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• General Proximal Quasi-Newton Methods based on model functions for nonsmooth nonconvex problems
• Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Robust Block Coordinate Descent
• Convergence rates of regularized quasi-Newton methods without strong convexity

Related

• Efficient Regularized Proximal Quasi-Newton Methods for Large-Scale Nonconvex Composite Optimization Problems
• Newton-type Methods with the Proximal Gradient Step for Sparse Estimation
• A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees