Support–accuracy tradeoffs for sparse least squares
Follow the latest progress by email.
Can polynomial-time sparse least-squares algorithms improve the linear condition-number dependence in their support bound while retaining additive ε accuracy? The proposed barrier concerns all randomized polynomial-time algorithms on rational inputs.
Why it matters and what counts as progress
Why it matters: A general barrier would explain a limitation previously established only for particular optimization methods.
What counts as progress: A better algorithm or a conditional hardness theorem ruling out support O(kκ^(1−γ)) for fixed γ>0, retaining the randomized rational-weighted exact-volume Small-Set Expansion premise.
How the problem developed
- 2021 · Algorithmic upper bound [1]
Kyriakos Axiotis and Maxim Sviridenko Introduced adaptively regularized hard thresholding with an accuracy-independent support bound linear in the restricted condition number, and conjectured that polynomial-time algorithms cannot improve its exponent for sparse convex optimization.
- 3 Aug 2026 · Conditional lower bound [2]
Honghao Lin, Vahab Mirrokni, and David P. Woodruff; proof first obtained by an internal Gemini-based agent Under a randomized rational-weighted exact-volume Small-Set Expansion hypothesis, ruled out randomized polynomial-time algorithms that simultaneously achieve additive accuracy and support O(kκₛ₊ₖ^(1−γ)) for any fixed γ∈(0,1]; the hard matrices have full column rank and at most two nonzeros per row.
AI contribution
The Condition-Number Barrier in Sparse Least Squares
Assuming the randomized rational-weighted exact-volume Small-Set Expansion Hypothesis, no randomized polynomial-time algorithm can guarantee both additive ε accuracy in rational sparse least squares and support O(k κₛ₊ₖ^(1−γ)) for any fixed γ∈(0,1]. The hard matrices have full column rank and at most two nonzeros per row.
Sources
Website timeline
Publication dates and editorial changes.
Gemini-origin proof gives a conditional sparse least-squares barrier