Research map / Learning theory and algorithms / Sample complexity

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning halfspaces under noise · 0 citations (OpenAlex)

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 the standard multiclass perceptron can need super-polynomially many samples under Gaussian marginals, and gives fully polynomial-time agnostic learners for multiclass linear classifiers via pairwise partial learning and localization, with error Õ(k^{3/2}√opt)+ε in general, O(opt)+ε for k=3, and poly(k)opt+ε for regular classifiers.

Problem

Agnostically learning k-class linear classifiers under Gaussian marginals in polynomial time with error close to opt; prior algorithms need exponential dependence on 1/epsilon and the multiclass perceptron is known to be inefficient in the noiseless Gaussian setting.

Approach

Replace the single weight-matrix representation with an improper pseudo-MLC built from one halfspace per label pair, learned via partial (conditional on labels in {i,j}) projected gradient updates; for k=3 and regular classifiers, localize by sampling from a Gaussian with reduced variance along the current normal to boost the O(sqrt(opt)) rate to O(opt).

Key results

• Multiclass perceptron lower bound: for l=Theta(log k), requires k^{Omega(log k)} samples/iterations to reach error 1/k^{O(1)} under Gaussian marginals with realizable labels.
• Pairwise framework yields agnostic learner with error Õ(k^{3/2} sqrt(opt)) + eps using d·poly(k/eps) samples and poly time.
• For k=3, localization gives error O(opt)+eps in poly time; for regular k-MLCs, error poly(k)·opt+eps.

Measured effects reported in the paper

Surprising findings

• The standard multiclass perceptron can fail super-polynomially even with clean labels and Gaussian marginals.

Limitations

• Results rely on the Gaussian marginal assumption.
• Dependence on k is polynomial but nontrivial (k^{3/2}), and O(opt) guarantee for general k requires geometric regularity.
• Learner is improper; proper learning left open.

Experimental setup

Metrics: 0-1 error relative to opt

Baselines: multiclass perceptron prior O(opt) algorithm with 2^poly(k/eps) sample complexity

Builds on: multiclass perceptron binary agnostic learning of halfspaces under Gaussian marginals Chow-parameter methods

Closest papers by meaning

• Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise (ICML 2025 · similarity 0.86)
• Robust learning of halfspaces under log-concave marginals (NeurIPS 2025 · similarity 0.86)
• Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.85)
• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.85)
• Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs (ICML 2025 · similarity 0.85)
• The optimality of kernel classifiers in Sobolev space (ICLR 2024 · similarity 0.85)