Timezone: »
Poster
Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
Yichen Chen · Dongdong Ge · Mengdi Wang · Zizhuo Wang · Yinyu Ye · Hao Yin
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$ less than 1. We also prove strong NP-hardness results for the sparsity-constrained optimizaiotn problem. These results apply to a broad class of loss functions and sparse penalty functions. They suggest that one cannot even approximately solve the sparse optimization problem in polynomial time, unless P $=$ NP.
[ PDF]
[
Summary/Notes]
Summary/Notes]
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)
-
2017 Talk: Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions »
Mon Aug 7th 01:24 -- 01:42 AM Room Parkside 2
More from the Same Authors
-
2021 Poster: Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient »
Botao Hao · Yaqi Duan · Tor Lattimore · Csaba Szepesvari · Mengdi Wang -
2021 Poster: The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks »
Xiaocheng Li · Chunlin Sun · Yinyu Ye -
2021 Spotlight: Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient »
Botao Hao · Yaqi Duan · Tor Lattimore · Csaba Szepesvari · Mengdi Wang -
2021 Oral: The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks »
Xiaocheng Li · Chunlin Sun · Yinyu Ye -
2021 Poster: Bootstrapping Fitted Q-Evaluation for Off-Policy Inference »
Botao Hao · Xiang Ji · Yaqi Duan · Hao Lu · Csaba Szepesvari · Mengdi Wang -
2021 Spotlight: Bootstrapping Fitted Q-Evaluation for Off-Policy Inference »
Botao Hao · Xiang Ji · Yaqi Duan · Hao Lu · Csaba Szepesvari · Mengdi Wang -
2020 Workshop: Theoretical Foundations of Reinforcement Learning »
Emma Brunskill · Thodoris Lykouris · Max Simchowitz · Wen Sun · Mengdi Wang -
2020 Poster: Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound »
Lin Yang · Mengdi Wang -
2020 Poster: Model-Based Reinforcement Learning with Value-Targeted Regression »
Alex Ayoub · Zeyu Jia · Csaba Szepesvari · Mengdi Wang · Lin Yang -
2020 Poster: Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation »
Yaqi Duan · Zeyu Jia · Mengdi Wang -
2019 Poster: Sample-Optimal Parametric Q-Learning Using Linearly Additive Features »
Lin Yang · Mengdi Wang -
2019 Oral: Sample-Optimal Parametric Q-Learning Using Linearly Additive Features »
Lin Yang · Mengdi Wang -
2018 Poster: Estimation of Markov Chain via Rank-constrained Likelihood »
XUDONG LI · Mengdi Wang · Anru Zhang -
2018 Oral: Estimation of Markov Chain via Rank-constrained Likelihood »
XUDONG LI · Mengdi Wang · Anru Zhang -
2018 Poster: Scalable Bilinear Pi Learning Using State and Action Features »
Yichen Chen · Lihong Li · Mengdi Wang -
2018 Oral: Scalable Bilinear Pi Learning Using State and Action Features »
Yichen Chen · Lihong Li · Mengdi Wang