2025/11/27 by Herbod Pourali, Pourali, Herbod, Sajjad Hashemian +3
Computer Science · #Adversarial Robustness in Machine Learning #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2 #G.3 #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2511.22524
openalex publication_date 2025/11/27 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity O((d+log(1/δ))/α), list size O(1/α), and near input-sparsity running time O(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.