13:12arXiv cs.LG@August Y. Chen, Ahmed El Alaoui精选该论文研究了在高维过参数化场景下,能够完美插值训练数据的线性分类器的泛化性能分布。在两种数据生成模型(高斯混合模型和逻辑回归模型)下,作者证明了当样本数与维度之比足够小时,几乎所有插值分类器的泛化误差都集中在某个最优值附近,只有指数级小部分的分类器性能显著不同。通过数值比较,发现梯度下降和经验风险最小化等高效算法找到的插值器性能优于绝大多数随机插值器,揭示了这些算法在过参数化设置下具有非平凡的良性过拟合特性。这项工作为理解深度学习中的“良性过拟合”现象提供了理论支撑。论文过参数化泛化理论线性分类器大偏差原理良性过拟合推荐理由:这篇论文从理论层面解释了为什么过参数化模型能泛化——做高维统计学习或深度学习理论的研究者,看完会对“良性过拟合”有更精确的数学理解,值得深入阅读。原文
12:29arXiv cs.LG@Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma精选该研究解决了高斯分布下多类线性分类的鲁棒学习问题。对于k≥3类的情况,此前算法在精度上存在指数级依赖。研究者发现标准多类感知器算法在k≥3时所需样本和更新次数超多项式,揭示了二元分类与多类分类的根本差异。他们提出了一种成对非恰当学习框架,实现了误差O(k^{3/2}√opt)+ε的多项式时间算法。对于k=3,进一步开发了基于定位的框架,达到误差O(opt)+ε。这些结果首次为多类线性分类提供了维度无关的误差保证和高效算法。论文多类分类鲁棒学习高斯分布多项式时间算法线性分类器推荐理由:该研究解决了多类线性分类在k≥3时长期存在的计算瓶颈,做机器学习理论或分类算法开发的团队值得关注,其成对框架可直接用于改进实际多类分类器的鲁棒性。原文