提出新方法，高效解决带噪声的线性回归问题。
List-Decodable Regression via Expander Sketching
- 用保真展开图生成少量污染数据批次，实现鲁棒聚合。
- 样本复杂度仅需 $\tilde{O}((d+\log(1/δ))/α)$，列表大小为 $O(1/α)$。
- 运行时间接近输入稀疏性，适合大规模高维数据处理。
我们提出一种基于展开图的可列表解线性回归框架，在标准亚高斯假设下，实现了样本复杂度 $\tilde{O}((d+\log(1/δ))/α)$、列表大小 $O(1/α)$，以及近输入稀疏性的运行时间 $\tilde{O}(\mathrm{nnz}(X)+d^{3}/α)$。该方法利用无损展开图合成轻度污染的数据批次，支持鲁棒聚合，并通过简短的谱滤波阶段达成当前最优的高效性能，避免了使用 SOS 机制和显式批次结构。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。