Jul, 2024
学习具有低内在维度的概念的平滑分析
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos
TL;DR传统的监督学习模型中，学习器的目标是基于一些类别中最适应的概念，通过学习任意分布的示例，输出一个与之相差不超过 epsilon 的假设。本研究引入了平滑分析框架，要求学习器只需与对小的随机高斯扰动具有鲁棒性的最佳分类器竞争，从而提供了广泛的学习结果。此类别包括依赖于低维子空间（即多索引模型）和具有有界高斯曲面积的概念。有趣的是，我们的分析还为传统的非平滑框架（如学习边际）提供了新的结果。特别地，在时间复杂度为 k ^poly（log（k）/（epsilon * gamma））的算法中，我们首次获得了关于 k 半空间求交的无偏学习算法，这里 gamma 是边际参数。在之前的工作中，最优的运行时间复杂度是指数级的（Arriaga 和 Vempala，1999 年）。