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
Authors: 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
Recommendations
- Inexact successive quadratic approximation for regularized optimization
- Semismooth Newton and quasi-Newton methods in weighted \(\ell^1\)-regularization
- An algorithm for quadratic \(\ell_1\)-regularized optimization with a flexible active-set strategy
- A reduced-space algorithm for minimizing \(\ell_1\)-regularized convex functions
- A family of second-order methods for convex \(\ell _1\)-regularized optimization
Numerical mathematical programming methods (65K05) Methods of successive quadratic programming type (90C55) Methods of quasi-Newton type (90C53) Newton-type methods (49M15)
Cites Work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Templates for convex cone problems with applications to sparse signal recovery
- Numerical Optimization
- Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
- Sample size selection in optimization methods for machine learning
- An improved GLMNET for L1-regularized logistic regression
- Title not available (Why is that?)
- 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
- Inexact and accelerated proximal point algorithms
- A semismooth Newton method with multidimensional filter globalization for \(l_1\)-optimization
Cited In (49)
- Semismooth Newton and quasi-Newton methods in weighted \(\ell^1\)-regularization
- 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 highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
- 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 variable metric proximal point algorithm for generic quasi-Newton acceleration
- 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 efficient proximal block coordinate homotopy method for large-scale sparse least squares problems
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- Optimization methods for large-scale machine learning
- Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
- Descentwise inexact proximal algorithms for smooth optimization
- 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
- Inexact proximal Newton methods for self-concordant functions
- Adaptive quadratically regularized Newton method for Riemannian optimization
- An inexact semismooth Newton method on Riemannian manifolds with application to duality-based total variation denoising
- Practical inexact proximal quasi-Newton method with global complexity analysis
- An inexact quasi-Newton algorithm for large-scale \(\ell_1\) optimization with box constraints
- An inexact coordinate descent method for the weighted \(l_{1}\)-regularized convex optimization problem
- 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
- Concave Likelihood-Based Regression with Finite-Support Response Variables
- Fused multiple graphical lasso
- 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
- An iterative reduction FISTA algorithm for large-scale LASSO
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- A proximal stochastic quasi-Newton algorithm with dynamical sampling and stochastic line search
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- Efficient proximal subproblem solvers for a nonsmooth trust-region method
- Efficient evaluation of scaled proximal operators
- An active-set proximal-Newton algorithm for \(\ell_1\) regularized optimization problems with box constraints
- A reduced-space algorithm for minimizing \(\ell_1\)-regularized convex functions
- FarRSA for \(\ell_1\)-regularized convex optimization: local convergence and numerical experience
- IMRO: A proximal quasi-Newton method for solving \(\ell_1\)-regularized least squares problems
- Stochastic proximal gradient method FOR \(\ell_1\) regularized optimization over a sphere
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)
