Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Not on the map. Why?
Abstract (arXiv)
We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of labeled examples (x, y), where x is drawn from an unknown distribution on Rd and the labels are generated by a multiclass linear classifier corrupted with RCN. That is, the label y is flipped from i to j with probability Hij according to a known noise matrix H with non-negative separation σ: = mini neq j Hii-Hij. The goal is to compute a hypothesis with small 0-1 error. For the special case of two labels, prior work has given polynomial-time algorithms achieving the optimal error. Surprisingly, little is known about the complexity of this task even for three labels. As our main contribution, we show that the complexity of MLC with RCN becomes drastically different in the presence of three or more labels. Specifically, we prove super-polynomial Statistical Query (SQ) lower bounds for this problem. In more detail, even for three labels and constant separation, we give a super-polynomial lower bound on the complexity of any SQ algorithm achieving optimal error. For a larger number of labels and smaller separation, we show a super-polynomial SQ lower bound even for the weaker goal of achieving any constant factor approximation to the optimal loss or even beating the trivial hypothesis.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 21 of its 46 references that are in the map. First posted on arXiv 17 Feb 2025.
Builds on
21 of 46 references.
References · 21
- 2016Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approachcited by 663
- 2017Robust Loss Functions under Label Noise for Deep Neural Networkscited by 441
- 2018Detecting and Correcting for Label Shift with Black Box Predictorscited by 364
- 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
- 2018Adversarial examples from computational constraintscited by 79
- 2017The power of sum-of-squares for detecting hidden structurescited by 54
- 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
- 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
- 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
- 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
- 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
- 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
9 more
- 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
- 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
- 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
- 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
- 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
- 2019Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Casecited by 11
- 2022A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learningcited by 11
- 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 8
- 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
Built on by
Citing papers per year: 2026: 2.
2 papers.