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 $\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.

References in corpus (3)

• Nearly unbiased variable selection under minimax concave penalty
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Variable Selection is Hard

Cited by in corpus (5)

• Compressing Neural Networks using the Variational Information Bottleneck
• Graph Neural Networks Inspired by Classical Iterative Algorithms
• Learning non-smooth models: instrumental variable quantile regressions and related problems
• Variational Bayesian Dropout with a Hierarchical Prior
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators