A proximal-gradient homotopy method for the sparse least-squares problem
From MaRDI portal
Abstract: We consider solving the -regularized least-squares (-LS) problem in the context of sparse recovery, for applications such as compressed sensing. The standard proximal gradient method, also known as iterative soft-thresholding when applied to this problem, has low computational cost per iteration but a rather slow convergence rate. Nevertheless, when the solution is sparse, it often exhibits fast linear convergence in the final stage. We exploit the local linear convergence using a homotopy continuation strategy, i.e., we solve the -LS problem for a sequence of decreasing values of the regularization parameter, and use an approximate solution at the end of each stage to warm start the next stage. Although similar strategies have been studied in the literature, there have been no theoretical analysis of their global iteration complexity. This paper shows that under suitable assumptions for sparse recovery, the proposed homotopy strategy ensures that all iterates along the homotopy solution path are sparse. Therefore the objective function is effectively strongly convex along the solution path, and geometric convergence at each stage can be established. As a result, the overall iteration complexity of our method is for finding an -optimal solution, which can be interpreted as global geometric rate of convergence. We also present empirical results to support our theoretical analysis.
The authors deal with the \(l_1\)-regularized least squares problem, proposing and analyzing an efficient numerical method for solving it. An approximate homotopy continuation method is used, solving the \(l_1\)-regularized least squares problem with a large parameter \(\lambda\) first and gradually decreasing \(\lambda\) until the targeted regularization is obtained. For each \(\lambda\), the problem is solved by a proximal gradient method up to the desired precision, getting a solution, which is the initial point in the next iteration corresponding to the next value \(\lambda\). The resulting technique is called proximal gradient homotopy method in this paper. The method has a provable low iteration complexity in specific algorithmic conditions. The overall iteration complexity and the overall computational cost are theoretically evaluated. Empirical results, which support the authors' theoretical analysis, are finally presented.
Recommendations
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- A simple homotopy proximal mapping algorithm for compressive sensing
- Decomposable norm minimization with proximal-gradient homotopy algorithm
- Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
- An efficient proximal block coordinate homotopy method for large-scale sparse least squares problems
Cited in
(45)- A unified approach to error bounds for structured convex optimization problems
- Complexity and applications of the homotopy principle for uniformly constrained sparse minimization
- Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Weighted thresholding homotopy method for sparsity constrained optimization
- Nonregular and minimax estimation of individualized thresholds in high dimension with binary responses
- Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
- A geometric proximal gradient method for sparse least squares regression with probabilistic simplex constraint
- A data-driven line search rule for support recovery in high-dimensional data analysis
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- A simple homotopy proximal mapping algorithm for compressive sensing
- A sparse proximal implementation of the LP dual active set algorithm
- On convergence rates of linearized proximal algorithms for convex composite optimization with applications
- A multilevel framework for sparse optimization with application to inverse covariance estimation and logistic regression
- Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
- scientific article; zbMATH DE number 6982301 (Why is no real title available?)
- Fast and reliable parameter estimation from nonlinear observations
- On semiparametric exponential family graphical models
- The homotopy method revisited: computing solution paths of \(\ell_1\)-regularized problems
- Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
- Decomposable norm minimization with proximal-gradient homotopy algorithm
- A fast homotopy algorithm for gridless sparse recovery
- An efficient proximal block coordinate homotopy method for large-scale sparse least squares problems
- Generalized conjugate gradient methods for _1 regularized convex quadratic programming with finite convergence
- An homotopy method for l p regression provably beyond self-concordance and in input-sparsity time
- Randomized block proximal damped Newton method for composite self-concordant minimization
- IMRO: A proximal quasi-Newton method for solving _1-regularized least squares problems
- Proximal variable metric method with spectral diagonal update for large scale sparse optimization
- Accelerate the warm-up stage in the Lasso computation via a homotopic approach
- Newton-type methods with the proximal gradient step for sparse estimation
- Joint sparse optimization: lower-order regularization method and application in cell fate conversion
- Homotopic policy mirror descent: policy convergence, algorithmic regularization, and improved sample complexity
- Nonconvex regularizer and homotopy-based sparse optimization: convergent algorithms and applications
- Communication-Efficient Distributed Sparse Learning with Oracle Property and Geometric Convergence
- A Riemannian conjugate gradient method for solving the tensor fixed-rank least-squares problem
- On convergence of iterative thresholding algorithms to approximate sparse solution for composite nonconvex optimization
- Iterative mix thresholding algorithm with continuation technique for mix sparse optimization and application
- High-dimensional variable selection with heterogeneous signals: a precise asymptotic perspective
- Decentralized sparse linear regression via gradient-tracking
- Optimal group thresholding algorithms for group sparse optimization with convergence guarantee
- A conditional gradient homotopy method with applications to semidefinite programming
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Iteratively weighted thresholding homotopy method for the sparse solution of underdetermined linear equations
- A primal dual active set with continuation algorithm for the \(\ell^0\)-regularized optimization problem
This page was built for publication: A proximal-gradient homotopy method for the sparse least-squares problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848186)
