Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

Abstract

Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity.

References in corpus (1)

• Computational Lower Bounds for Sparse PCA

Cited by in corpus (29)

• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Statistical and computational trade-offs in estimation of sparse principal components
• Provable Meta-Learning of Linear Representations
• High Dimensional Robust Sparse Regression
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• On Bayes Risk Lower Bounds
• Variable Selection is Hard
• Minimax Estimation of Conditional Moment Models
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Rank-one Convexification for Sparse Regression
• Sparse and Smooth Signal Estimation: Convexification of L0 Formulations
• Average-case Hardness of RIP Certification
• Bayesian Sparse Linear Regression with Unknown Symmetric Error
• Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• High-dimensional robust regression and outliers detection with SLOPE
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• Statistical Limits of Convex Relaxations
• Iterative Alpha Expansion for estimating gradient-sparse signals from linear measurements
• Some exercises with the Lasso and its compatibility constant
• Inference Without Compatibility
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements
• Convergence Rates of Empirical Bayes Posterior Distributions: A Variational Perspective
• Rank-Constrained Least-Squares: Prediction and Inference
• The Fine-Grained Hardness of Sparse Linear Regression
• On sure early selection of the best subset