A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
This addresses the problem of efficient optimization for high-dimensional machine learning models with nonconvex sparsity constraints, offering a first-order method with complexity guarantees, though it is incremental as it builds on existing proximal point and constraint relaxation techniques.
The paper tackles nonconvex sparse-constrained optimization by proposing a proximal point algorithm that solves convex subproblems with gradually relaxed constraints, achieving asymptotic convergence to KKT solutions and establishing convergence complexities on par with gradient descent for unconstrained problems.
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.