@inproceedings{a4f70d2368b14f4baca2481c5c9849ce,

title = "Strong NP-hardness for sparse optimization with concave penalty functions",

abstract = "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 O(nC1dC2)-optimal solution to the regularized sparse optimization problem is strongly NP-hard for any C1, C2 ∈ [0, 1) such that C1 + C2 < 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.",

keywords = "Computational complexity, Concave penalty, NP-hardness, Nonconvex optimization, Sparsity",

author = "Yichen Chen and Dongdong Ge and Mengdi Wang and Zizhuo Wang and Yinyu Ye and Hao Yin",

year = "2017",

month = jan,

day = "1",

language = "English (US)",

series = "34th International Conference on Machine Learning, ICML 2017",

publisher = "International Machine Learning Society (IMLS)",

pages = "1230--1251",

booktitle = "34th International Conference on Machine Learning, ICML 2017",

note = "34th International Conference on Machine Learning, ICML 2017 ; Conference date: 06-08-2017 Through 11-08-2017",

}