论文标题
具有平均平滑度的功能：结构，算法和学习
Functions with average smoothness: structure, algorithms, and learning
论文作者
论文摘要
我们启动了平均平滑度分析程序，以有效地学习公制空间上的实数功能。我们不是将Lipschitz常数用作正规器，而是在每个点定义一个局部斜率，并将功能复杂性作为这些值的平均值。由于平均值可能大于最大值，因此这种复杂性度量可以产生明显的概括范围 - 假设这些量子允许在Lipschitz常数被我们的局部斜率平均值所取代的改进中。 我们的第一个主要贡献是仅获得这种分布敏感的界限。这需要克服许多技术挑战，也许最强大的是{\ em经验}涵盖数字的界限，这可能比周围的数字更糟糕。我们的组合结果伴随着有效的算法，用于平滑随机样品的标签，并确保从样本到整个空间的延伸将继续保持平均水平。在途中，我们在定义的功能类别中发现了一个非常丰富的组合和分析结构。
We initiate a program of average smoothness analysis for efficiently learning real-valued functions on metric spaces. Rather than using the Lipschitz constant as the regularizer, we define a local slope at each point and gauge the function complexity as the average of these values. Since the mean can be dramatically smaller than the maximum, this complexity measure can yield considerably sharper generalization bounds -- assuming that these admit a refinement where the Lipschitz constant is replaced by our average of local slopes. Our first major contribution is to obtain just such distribution-sensitive bounds. This required overcoming a number of technical challenges, perhaps the most formidable of which was bounding the {\em empirical} covering numbers, which can be much worse-behaved than the ambient ones. Our combinatorial results are accompanied by efficient algorithms for smoothing the labels of the random sample, as well as guarantees that the extension from the sample to the whole space will continue to be, with high probability, smooth on average. Along the way we discover a surprisingly rich combinatorial and analytic structure in the function class we define.
