THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
Yichen Chen · Dongdong Ge · Mengdi Wang · Zizhuo Wang · Yinyu Ye · Hao Yin

Sun Aug 06 06:24 PM -- 06:42 PM (PDT) @ Parkside 2
in Continuous optimization 1 »
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.
[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Yichen Chen (Princeton University)
Dongdong Ge (Shanghai University of Finance and Economics)
Mengdi Wang (Princeton University)
Zizhuo Wang (University of Minnesota)
Yinyu Ye (Standord)
Hao Yin (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors