{"ID":2836025,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.22524","arxiv_id":"2511.22524","title":"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/δ))/α)$, 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.","short_abstract":"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 syn...","url_abs":"https://arxiv.org/abs/2511.22524","url_pdf":"https://arxiv.org/pdf/2511.22524v1","authors":"[\"Herbod Pourali\",\"Sajjad Hashemian\",\"Ebrahim Ardeshir-Larijani\"]","published":"2025-11-27T15:04:37Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.DM\"]","methods":"[]","has_code":false}