### 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(n^{C1}d^{C2})-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.

Original language | English (US) |
---|---|

Title of host publication | 34th International Conference on Machine Learning, ICML 2017 |

Publisher | International Machine Learning Society (IMLS) |

Pages | 1230-1251 |

Number of pages | 22 |

ISBN (Electronic) | 9781510855144 |

State | Published - Jan 1 2017 |

Event | 34th International Conference on Machine Learning, ICML 2017 - Sydney, Australia Duration: Aug 6 2017 → Aug 11 2017 |

### Publication series

Name | 34th International Conference on Machine Learning, ICML 2017 |
---|---|

Volume | 2 |

### Other

Other | 34th International Conference on Machine Learning, ICML 2017 |
---|---|

Country | Australia |

City | Sydney |

Period | 8/6/17 → 8/11/17 |

### All Science Journal Classification (ASJC) codes

- Computational Theory and Mathematics
- Human-Computer Interaction
- Software

### Keywords

- Computational complexity
- Concave penalty
- NP-hardness
- Nonconvex optimization
- Sparsity

## Fingerprint Dive into the research topics of 'Strong NP-hardness for sparse optimization with concave penalty functions'. Together they form a unique fingerprint.

## Cite this

Chen, Y., Ge, D., Wang, M., Wang, Z., Ye, Y., & Yin, H. (2017). Strong NP-hardness for sparse optimization with concave penalty functions. In

*34th International Conference on Machine Learning, ICML 2017*(pp. 1230-1251). (34th International Conference on Machine Learning, ICML 2017; Vol. 2). International Machine Learning Society (IMLS).