# List-Decodable Regression via Expander Sketching

arXiv: https://arxiv.org/abs/2511.22524 · HTML: https://mlsanity.com/paper/2511.22524/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 11 references that are in the map.
- First posted on arXiv 27 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)

## Abstract (arXiv)

We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity tildeO((d+log(1/δ))/α), list size O(1/α), and near input-sparsity running time tildeO(nnz(X)+d3/α) 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.