2023/07/13 by Ilias Diakonikolas, Jelena Diakonikolas, Diakonikolas, Ilias +7 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2307.08438
openalex publication_date 2023/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces with Random Classification Noise under the Gaussian distribution. We establish nearly-matching algorithmic and Statistical Query (SQ) lower bound results revealing a surprising information-computation gap for this basic problem. Specifically, the sample complexity of this learning problem is \widetildeΘ(d/ε), where d is the dimension and ε is the excess error. Our positive result is a computationally efficient learning algorithm with sample complexity O(d/ε+ d/(max\p, ε\)2), where p quantifies the bias of the target halfspace. On the lower bound side, we show that any efficient SQ algorithm (or low-degree test) for the problem requires sample complexity at least Ω(d1/2/(max\p, ε\)2). Our lower bound suggests that this quadratic dependence on 1/ε is inherent for efficient algorithms.