List-Decodable Regression via Expander Sketching
This work provides an efficient and robust method for list-decodable linear regression, which is important for applications dealing with corrupted data, particularly for practitioners in machine learning and statistics.
This paper tackles list-decodable linear regression, achieving a sample complexity of O((d+log(1/δ))/α), a list size of O(1/α), and a running time of O(nnz(X)+d^3/α). The method leverages lossless expanders for robust aggregation and spectral filtering.
We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $\tilde{O}((d+\log(1/δ))/α)$, list size $O(1/α)$, and near input-sparsity running time $\tilde{O}(\mathrm{nnz}(X)+d^{3}/α)$ 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.