2023/02/13 by Ilias Diakonikolas, Daniel M. Kane, Diakonikolas, Ilias +3 · 4 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2302.06512
openalex publication_date 2023/02/13 · openalex created_date 2023/02/16 · openalex updated_date 2026/07/28
We study the task of agnostically learning halfspaces under the Gaussian distribution. Specifically, given labeled examples (x,y) from an unknown distribution on ℝn × \ ± 1\, whose marginal distribution on x is the standard Gaussian and the labels y can be arbitrary, the goal is to output a hypothesis with 0-1 loss OPT+ε, where OPT is the 0-1 loss of the best-fitting halfspace. We prove a near-optimal computational hardness result for this task, under the widely believed sub-exponential time hardness of the Learning with Errors (LWE) problem. Prior hardness results are either qualitatively suboptimal or apply to restricted families of algorithms. Our techniques extend to yield near-optimal lower bounds for related problems, including ReLU regression.