Name
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. |
Year | Venue | DocType |
|---|---|---|
2020 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS (NEURIPS 2020) | Conference |
Volume | ISSN | Citations |
33 | 1049-5258 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Digvijay Boob | 1 | 1 | 1.70 |
| Qi Deng | 2 | 0 | 0.34 |
| Guanghui Lan | 3 | 1212 | 66.26 |
| Yilin Wang | 4 | 0 | 0.34 |