Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise

Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, Christos Tzamos

International Conference on Machine Learning 2025 · Oral

This talk delves into the computational complexity of **multiclass linear classification (MLC)**, a fundamental problem in machine learning, particularly when faced with **random classification noise (RCN)**. Multiclass linear classification extends the familiar binary classification problem of learning halfspaces, where a classifier assigns a label based on which of *k* vectors yields the highest inner product score with an input example. While straightforward in the ideal "realizable" setting, practical scenarios inevitably involve noisy labels. The speakers, Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, and Christos Tzamos, present compelling evidence that learning general MLC under RCN becomes surprisingly intractable for even a small number of classes, specifically when *k* is 3 or more.

AI review

A rigorous and technically clean hardness result establishing that multiclass linear classification under random classification noise undergoes a sharp phase transition at k=3: polynomial-time solvable for binary classification, SQ-hard for three or more classes. The construction is well-motivated, the result is non-trivial, and the information-computation gap it reveals addresses a genuine open problem. This is a solid theoretical contribution from a group with a strong track record in computational learning theory. The primary limitation is scope — the SQ framework, while broad, is not…