Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions

摘要

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(n~(c_1)d~(c_2))-optimal solution to the regularized sparse optimization problem is strongly NP-hard for any c_1, c_2 ∈ [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.