arXiv ID:
2602.21191
arXiv 提交日期: 2026-02-24
平滑不可知学习的统计查询下界 / Statistical Query Lower Bounds for Smoothed Agnostic Learning
1️⃣ 一句话总结
这篇论文证明了,在数据受到轻微高斯扰动的情况下,学习最佳分类器(特别是半空间分类器)的计算复杂度非常高,几乎达到了已知最优算法的上限,表明现有方法已接近理论极限。