An inexact successive quadratic approximation method for L-1 regularized optimization
From MaRDI portal
Publication:301652
DOI10.1007/S10107-015-0941-YzbMATH Open1342.49037arXiv1309.3529OpenAlexW2162870776MaRDI QIDQ301652FDOQ301652
Figen Oztoprak, R. H. Byrd, Jorge Nocedal
Publication date: 1 July 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1309.3529
Numerical mathematical programming methods (65K05) Methods of successive quadratic programming type (90C55) Methods of quasi-Newton type (90C53) Newton-type methods (49M15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Templates for convex cone problems with applications to sparse signal recovery
- Numerical Optimization
- Sample size selection in optimization methods for machine learning
- Representations of quasi-Newton matrices and their use in limited memory methods
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Inexact coordinate descent: complexity and preconditioning
- A family of second-order methods for convex \(\ell _1\)-regularized optimization
- An inexact interior point method for \(L_{1}\)-regularized sparse covariance selection
- Nonlinear programming and variational inequality problems. A unified approach
- Inexact Newton Methods
- A comparison of optimization methods and software for large-scale L1-regularized linear classifi\-cation
- Convergence of inexact Newton methods for generalized equations
- Cost Approximation: A Unified Framework of Descent Algorithms for Nonlinear Programs
- A Semismooth Newton Method with Multidimensional Filter Globalization for $l_1$-Optimization
Cited In (44)
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- A family of second-order methods for convex \(\ell _1\)-regularized optimization
- Inexact successive quadratic approximation for regularized optimization
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- Sub-sampled Newton methods
- An Inexact Semismooth Newton Method on Riemannian Manifolds with Application to Duality-Based Total Variation Denoising
- Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates
- Inexact proximal DC Newton-type method for nonconvex composite functions
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- An Iterative Reduction FISTA Algorithm for Large-Scale LASSO
- Fused Multiple Graphical Lasso
- Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
- An active-set proximal quasi-Newton algorithm for ℓ1-regularized minimization over a sphere constraint
- Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
- A flexible coordinate descent method
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- Second order semi-smooth proximal Newton methods in Hilbert spaces
- Globalized inexact proximal Newton-type methods for nonconvex composite functions
- Inexact proximal Newton methods in Hilbert spaces
- A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization
- Inexact proximal Newton methods for self-concordant functions
- Practical inexact proximal quasi-Newton method with global complexity analysis
- FaRSA for ℓ1-regularized convex optimization: local convergence and numerical experience
- An inexact quasi-Newton algorithm for large-scale \(\ell_1\) optimization with box constraints
- Inexact proximal stochastic second-order methods for nonconvex composite optimization
- Stochastic proximal quasi-Newton methods for non-convex composite optimization
- Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems
- A globally convergent proximal Newton-type method in nonsmooth convex optimization
- An active set Newton-CG method for \(\ell_1\) optimization
- Title not available (Why is that?)
- Concave Likelihood-Based Regression with Finite-Support Response Variables
- A Reduced-Space Algorithm for Minimizing $\ell_1$-Regularized Convex Functions
- A VMiPG method for composite optimization with nonsmooth term having no closed-form proximal mapping
- Local convergence analysis of an inexact trust-region method for nonsmooth optimization
- An inexact regularized proximal Newton method without line search
- A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- Adaptive Quadratically Regularized Newton Method for Riemannian Optimization
- A proximal stochastic quasi-Newton algorithm with dynamical sampling and stochastic line search
- Optimization Methods for Large-Scale Machine Learning
- An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
- Efficient proximal subproblem solvers for a nonsmooth trust-region method
- An Efficient Proximal Block Coordinate Homotopy Method for Large-Scale Sparse Least Squares Problems
- An active-set proximal-Newton algorithm for \(\ell_1\) regularized optimization problems with box constraints
Uses Software
This page was built for publication: An inexact successive quadratic approximation method for L-1 regularized optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q301652)
