Timezone: »

A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
Digvijay Boob · Qi Deng · Guanghui Lan · Yilin Wang

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #661

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.

Author Information

Digvijay Boob (Southern Methodist University)

I am **Digvijay**, an assistant professor at Southern Methodist University in EMIS department. My core area of research is development of algorithms for convex, non-convex optimization and saddle point problems, focusing primarily on first-order algorithms with provable convergence rates for large scale problems.

Qi Deng (Shanghai University of Finance and Economics)
Guanghui Lan (Georgia Tech)
Yilin Wang (Shanghai University of Finance and Economics)

More from the Same Authors