Skip to main content

Approximation Hardness for A Class of Sparse Optimization Problems

Author(s): Chen, Yichen; Ye, Yinyu; Wang, Mengdi

To refer to this page use:
Abstract: In this paper, we consider three typical optimization problems with a convex loss function and a nonconvex sparse penalty or constraint. For the sparse penalized problem, we prove that finding an O(nc1dc2)-optimal solution to an n×d problem is strongly NP-hard for any c1,c2∈[0,1) such that c1+c2<1. For two constrained versions of the sparse optimization problem, we show that it is intractable to approximately compute a solution path associated with increasing values of some tuning parameter. The hardness results apply to a broad class of loss functions and sparse penalties. They suggest that one cannot even approximately solve these three problems in polynomial time, unless P = NP.
Publication Date: 2019
Electronic Publication Date: Feb-2018
Citation: Chen, Yichen, Yinyu Ye, and Mengdi Wang. "Approximation Hardness for A Class of Sparse Optimization Problems." Journal of Machine Learning Research 20, no. 38 (2019): 1-27.
ISSN: 1532-4435
Pages: 1 - 27
Type of Material: Journal Article
Journal/Proceeding Title: Journal of Machine Learning Research
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.