Research map / Learning theory and algorithms / Sample complexity
Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows super-polynomial statistical query lower bounds for multiclass linear classification under random classification noise, even with three labels and constant separation, via a hidden-direction moment-matching construction.
Problem
Computational complexity of learning multiclass linear classifiers in the distribution-free PAC model with random classification noise (RCN), where prior poly-time results only cover the binary case.
Approach
Reduces a correlation-testing problem to MLC-with-RCN learning by constructing hidden-direction distributions whose conditional label distributions are mixtures of moment-matching one-dimensional base distributions, with the noise matrix's last row a convex combination of the others, yielding SQ hardness for optimal, approximate, and beat-random-guess learning.
Key results
- For three labels with noise matrix H having separation at least 0.1, learning MLC with RCN to error opt+epsilon requires d^{Omega~(log^{1.98} d / eps^{1.98})} SQ queries or a tiny-tolerance query.
- For any C>1, with k=O(C) labels and separation Omega(1/C), approximating to error C*opt is SQ-hard even when opt=Omega(1/C).
- For any k>=3, learning MLC with RCN to error 1-1/k-o(1) is SQ-hard even when opt=O(1/k), i.e., no better than random guessing.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use at least three labels with RCN and constant separation | Multiclass linear classification · Distribution-free MLC with RCN, k=3 | SQ complexity for error opt+epsilon: d^{\Tilde{\Omega}(\log^{1.98}(d)/\epsilon^{1.98})} queries or tolerance at most 1/d^{\Tilde{\Omega}(\log^{1.98}(d)/\epsi | Hurt |
| Use larger k with separation min_{i,j} H_{i,i}-H_{i,j}=\Omega(1/C) | Multiclass linear classification · Distribution-free MLC with RCN, k=O(C) | SQ complexity for error C opt: d^{\Omega(\log^{0.99} d)} queries or tolerance at most 1/d^{\Omega(\log^{0.99} d)} | Hurt |
| Use k≥3 with separation min_{i,j} H_{i,i}-H_{i,j}=1/poly(d) | Multiclass linear classification · Distribution-free MLC with RCN, opt=O(1/k) | SQ complexity for error 1-1/k-1/poly(d): d^{\Omega(\log^{0.99} d)} queries or tolerance at most 1/d^{\Omega(\log^{0.99} d)} | Hurt |
| Use k≥3 and the constructed noise matrix H | Multiclass linear classification · Distribution-free MLC with RCN | SQ complexity for error 1-1/k-zeta-2 mu: min(q,1/μ^2)=d^{Ω(log^{0.99} d)} | Hurt |
Surprising findings
- Unlike the binary case, where RCN-robust learning reduces efficiently from the realizable setting, multiclass MLC with RCN is SQ-hard even with three labels and constant separation.
- Hardness holds even when the noise matrix is known to the learner and the noise level is small (e.g., 1% noise for k=100 makes beating 99% error hard).
Limitations
- Results are SQ lower bounds only and do not rule out non-SQ algorithms.
- Hardness is for distribution-free setting; structured marginals such as Gaussian are not covered (noted as a direction).
Experimental setup
Builds on: statistical query dimension framework hidden direction distribution construction for SQ lower bounds Veronese mapping reduction from polynomial to linear classification Massart halfspace SQ lower bound construction
Closest papers by meaning
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.86)
- Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals (NeurIPS 2026 · similarity 0.86)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.86)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.85)
- Representation Preserving Multiclass Agnostic to Realizable Reduction (ICML 2025 · similarity 0.85)
- Smoothed Online Classification can be Harder than Batch Classification (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.