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

2014/02/09 by Yuchen Zhang, Martin J. Wainwright, Zhang, Yuchen +3 · 5 citations
Computer Science · Engineering · #Blind Source Separation Techniques #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1402.1918

openalex publication_date 2014/02/09 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Computational Lower Bounds for Sparse PCA
• Atomic Decomposition by Basis Pursuit
• Sparse Approximate Solutions to Linear Systems

Cited by

• Sparse Linear Regression is Easy on Random Supports
• Optimality and computational barriers in variable selection under dependence
• Probabilistic and nonlinear compressive sensing
• Approximate l₀-penalized estimation of piecewise-constant signals on graphs
• Some exercises with the Lasso and its compatibility constant

Related

• The Fine-Grained Hardness of Sparse Linear Regression
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
• Online Sparse Linear Regression
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions