A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
arXiv:2010.12169
Abstract
Nonconvex sparse models have received significant attention in high-dimensional machine learning. In this paper, we study a new model consisting of a general convex or nonconvex objectives and a variety of continuous nonconvex sparsity-inducing constraints. For this constrained model, we propose a novel proximal point algorithm that solves a sequence of convex subproblems with gradually relaxed constraint levels. Each subproblem, having a proximal point objective and a convex surrogate constraint, can be efficiently solved based on a fast routine for projection onto the surrogate constraint. We establish the asymptotic convergence of the proposed algorithm to the Karush-Kuhn-Tucker (KKT) solutions. We also establish new convergence complexities to achieve an approximate KKT solution when the objective can be smooth/nonsmooth, deterministic/stochastic and convex/nonconvex with complexity that is on a par with gradient descent for unconstrained optimization problems in respective cases. To the best of our knowledge, this is the first study of the first-order methods with complexity guarantee for nonconvex sparse-constrained problems. We perform numerical experiments to demonstrate the effectiveness of our new model and efficiency of the proposed algorithm for large scale problems.
arXiv commentAccepted at NeurIPS 2020
References in corpus (17)
- Scikit-learn: Machine Learning in Python
- Least Angle Regression
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Rejoinder to "Least angle regression" by Efron et al
- Nearly unbiased variable selection under minimax concave penalty
- A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
- Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted Balls
- Convergence guarantees for a class of non-convex and non-smooth optimization problems
- A unified variance-reduced accelerated gradient method for convex optimization
- Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization