List-Decodable Regression via Expander Sketching

Abstract

We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $\tilde{O}((d+\log (1/\hat{I}´))/\hat{I}\pm )$, list size $O(1/\hat{I}\pm )$, and near input-sparsity running time $\tilde{O}(\mathrm{nnz}(X)+d^3/\hat{I}\pm )$ under standard sub-Gaussian assumptions. Our method uses lossless expanders to synthesize lightly contaminated batches, enabling robust aggregation and a short spectral filtering stage that matches the best known efficient guarantees while avoiding SoS machinery and explicit batch structure.