arXiv cs.LG@Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma精选37该研究解决了高斯分布下多类线性分类的鲁棒学习问题。对于k≥3类的情况，此前算法在精度上存在指数级依赖。研究者发现标准多类感知器算法在k≥3时所需样本和更新次数超多项式，揭示了二元分类与多类分类的根本差异。他们提出了一种成对非恰当学习框架，实现了误差O(k^{3/2}√opt)+ε的多项式时间算法。对于k=3，进一步开发了基于定位的框架，达到误差O(opt)+ε。这些结果首次为多类线性分类提供了维度无关的误差保证和高效算法。论文多类分类鲁棒学习高斯分布多项式时间算法线性分类器推荐理由：该研究解决了多类线性分类在k≥3时长期存在的计算瓶颈，做机器学习理论或分类算法开发的团队值得关注，其成对框架可直接用于改进实际多类分类器的鲁棒性。