Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2511.22524 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912734473355264 |
|---|---|
| author | Pourali, Herbod Hashemian, Sajjad Ardeshir-Larijani, Ebrahim |
| author_facet | Pourali, Herbod Hashemian, Sajjad Ardeshir-Larijani, Ebrahim |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22524 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | List-Decodable Regression via Expander Sketching Pourali, Herbod Hashemian, Sajjad Ardeshir-Larijani, Ebrahim Machine Learning Discrete Mathematics G.3; G.2 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. |
| title | List-Decodable Regression via Expander Sketching |
| topic | Machine Learning Discrete Mathematics G.3; G.2 |
| url | https://arxiv.org/abs/2511.22524 |