The Condition-Number Barrier in Sparse Least Squares

arXiv:2608.02588v1 Announce Type: cross Abstract: 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 randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed gammain(0,1], there is no randomized polynomial-time algorithm that, with probability at least 2/3, returns a vector x such that, writing s=lVert xrVert_0, [ lVert Ax-brVert_2^2 leq min_{lVert zrVert_0leq k}lVert Az-brVert_2^2+arepsilon quadext{and}quad s=O!left(k,kappa_{s+k}^{,1-gamma}right), ] where kappa_r is the restricted condition number at sparsity level r. The result holds even on rational instances with A of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.

Source: arXiv cs.LG | 2026-08-04