Approximation Hardness for A Class of Sparse Optimization Problems

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 $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to an $n\times d$ problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2 [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

Authors

• Yichen Chen
• Yinyu Ye Stanford University
• Mengdi Wang Princeton University

Keywords

No keywords are indexed for this paper.