Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions

Proceedings of the 34th International Conference on Machine Learning

2017

70

Proceedings of Machine Learning Research

0

PMLR

Consider the regularized sparse minimization problem, which involves empirical sums of loss functions for $n$ data points (each of dimension $d$) and a nonconvex sparsity penalty. We prove that finding an $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to the regularized sparse optimization problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2<1$. The result applies to a broad class of loss functions and sparse penalty functions. It suggests that one cannot even approximately solve the sparse optimization problem in polynomial time, unless P $=$ NP.

inproceedings

chen17d

Strong {NP}-Hardness for Sparse Optimization with Concave Penalty Functions

Yichen Chen and Dongdong Ge and Mengdi Wang and Zizhuo Wang and Yinyu Ye and Hao Yin

740

747

740-747

740

false

given family Doina Precup

given family Yee Whye Teh

given family Yichen Chen

given family Dongdong Ge

given family Mengdi Wang

given family Zizhuo Wang

given family Yinyu Ye

given family Hao Yin

2017-07-17

Proceedings of the 34th International Conference on Machine Learning

inproceedings

date-parts
2017 7 17

label link Supplementary PDF http://proceedings.mlr.press/v70/chen17d/chen17d-supp.pdf