A second-order method for strongly convex _1-regularization problems
From MaRDI portal
Publication:263191
DOI10.1007/S10107-015-0875-4zbMATH Open1364.90255arXiv1306.5386OpenAlexW2164449950MaRDI QIDQ263191FDOQ263191
Kimon Fountoulakis, Jacek Gondzio
Publication date: 4 April 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: In this paper a robust second-order method is developed for the solution of strongly convex l1-regularized problems. The main aim is to make the proposed method as inexpensive as possible, while even difficult problems can be efficiently solved. The proposed approach is a primal-dual Newton Conjugate Gradients (pdNCG) method. Convergence properties of pdNCG are studied and worst-case iteration complexity is established. Numerical results are presented on synthetic sparse least-squares problems and real world machine learning problems.
Full work available at URL: https://arxiv.org/abs/1306.5386
\(\ell_1\)-regularizationiteration complexityNewton conjugate-gradients methodsecond-order methodsstrongly convex optimization
Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Analysis of algorithms (68W40)
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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Templates for convex cone problems with applications to sparse signal recovery
- Coordinate descent algorithms for lasso penalized regression
- Convergence of a block coordinate descent method for nondifferentiable minimization
- A coordinate gradient descent method for nonsmooth separable minimization
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Parallel coordinate descent methods for big data optimization
- A mathematical view of interior-point methods in convex optimization
- Accelerated block-coordinate relaxation for regularized optimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- A Nonlinear Primal-Dual Method for Total Variation-Based Image Restoration
- Analysis of bounded variation penalty methods for ill-posed problems
- Multiple View Geometry in Computer Vision
Cited In (24)
- A robust computational framework for variational data assimilation of mean flows with sparse measurements corrupted by strong outliers
- Mathematical optimization in classification and regression trees
- On sparse ensemble methods: an application to short-term predictions of the evolution of COVID-19
- Linesearch Newton-CG methods for convex optimization with noise
- Optimal randomized classification trees
- On the convergence rate of scaled gradient projection method
- A fast active set block coordinate descent algorithm for \(\ell_1\)-regularized least squares
- Second-order orthant-based methods with enriched Hessian information for sparse \(\ell _1\)-optimization
- Visualizing data as objects by DC (difference of convex) optimization
- Gradient-based method with active set strategy for $\ell _1$ optimization
- A flexible coordinate descent method
- Visualizing proportions and dissimilarities by space-filling maps: a large neighborhood search approach
- A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems
- Interior-point solver for convex separable block-angular problems
- Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems
- An active set Newton-CG method for \(\ell_1\) optimization
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- A multilevel method for self-concordant minimization
- An inexact dual logarithmic barrier method for solving sparse semidefinite programs
- Generalized Conjugate Gradient Methods for ℓ1 Regularized Convex Quadratic Programming with Finite Convergence
- On partial Cholesky factorization and a variant of quasi-Newton preconditioners for symmetric positive definite matrices
- Title not available (Why is that?)
- Continuation methods for approximate large scale object sequencing
- Sparse Approximations with Interior Point Methods
Uses Software
Recommendations
- A family of second-order methods for convex \(\ell _1\)-regularized optimization 👍 👎
- The method of iterative second order regularization for convex problems of conditional minimization 👍 👎
- Title not available (Why is that?) 👍 👎
- Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems 👍 👎
- A second-order gradient method for convex minimization 👍 👎
- Title not available (Why is that?) 👍 👎
- A second-order method for convex1-regularized optimization with active-set prediction 👍 👎
- A regularization smoothing method for second-order cone complementarity problem 👍 👎
- Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems 👍 👎
- Title not available (Why is that?) 👍 👎
This page was built for publication: A second-order method for strongly convex \(\ell _1\)-regularization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263191)
