The Condition-Number Barrier in Sparse Least Squares
By Honghao Lin · Paper · cs.DS
In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the