Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions

被引：0

作者：

Chen, Yichen ^{[1
]}

Ge, Dongdong ^{[2
]}

Wang, Mengdi ^{[1
]}

Wang, Zizhuo ^{[3
]}

Ye, Yinyu ^{[4
]}

Yin, Hao ^{[4
]}

机构：

[1] Princeton Univ, Princeton, NJ 08544 USA

[2] Shanghai Univ Finance & Econ, Shanghai, Peoples R China

[3] Univ Minnesota, Minneapolis, MN 55455 USA

[4] Stanford Univ, Stanford, CA 94305 USA

来源：

INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 70 | 2017年 / 70卷

关键词：

Nonconvex optimization; Computational complexity; NP-hardness; Concave penalty; Sparsity; VARIABLE SELECTION; PENALIZED LIKELIHOOD;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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(c1) d(c2)) -optimal solution to the regularized sparse optimization problem is strongly NP-hard for any c(1), c(2) is an element of [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.

引用

页数：8

共 28 条

[1] On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems [J].