该研究解决了多类线性分类在k≥3时长期存在的计算瓶颈，做机器学习理论或分类算法开发的团队值得关注，其成对框架可直接用于改进实际多类分类器的鲁棒性。
该研究解决了高斯分布下多类线性分类的鲁棒学习问题。对于k≥3类的情况，此前算法在精度上存在指数级依赖。研究者发现标准多类感知器算法在k≥3时所需样本和更新次数超多项式，揭示了二元分类与多类分类的根本差异。他们提出了一种成对非恰当学习框架，实现了误差O(k^{3/2}√opt)+ε的多项式时间算法。对于k=3，进一步开发了基于定位的框架，达到误差O(opt)+ε。这些结果首次为多类线性分类提供了维度无关的误差保证和高效算法。
Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals
We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples $(x, y)$ from a distribution over $\mathbb{R}^d \times [k]$, with Gaussian $x$-marginal, the goal is to output a hypothesis whose error is comparable to that of the best $k$-class linear classifier. While the binary case $k=2$ has a well-developed algorithmic theory, much less is known for $k \ge 3$. Even for $k=3$, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error $\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε$ for general $k$. Additionally, we develop a sharper localization-based framework which leads to error $O(\mathrm{opt})+ε$ for $k=3$, and error $\mathrm{poly}(k)\mathrm{opt}+ε$ for geometrically regular $k$-class linear classifiers.