We study distribution-free nonparametric regression following a notion of average smoothness initiated by Ashlagi et al. (2021), which measures the "effective" smoothness of a function with respect to an arbitrary unknown underlying distribution. While the recent work of Hanneke et al. (2023) established tight uniform convergence bounds for average-smooth functions in the realizable case and provided a computationally efficient realizable learning algorithm, both of these results currently lack analogs in the general agnostic (i.e. noisy) case. In this work, we fully close these gaps. First, we provide a distribution-free uniform convergence bound for average-smoothness classes in the agnostic setting. Second, we match the derived sample complexity with a computationally efficient agnostic learning algorithm. Our results, which are stated in terms of the intrinsic geometry of the data and hold over any totally bounded metric space, show that the guarantees recently obtained for realizable learning of average-smooth functions transfer to the agnostic setting. At the heart of our proof, we establish the uniform convergence rate of a function class in terms of its bracketing entropy, which may be of independent interest.

我们研究了分布自由的非参数回归，根据Ashlagi等人（2021）提出的一种平均平滑性概念，该概念度量了函数相对于任意未知基础分布的“有效”平滑程度。我们提供了分布自由的均匀收敛界限，以及与计算高效的无知学习算法相匹配的采样复杂度。我们的结果表明，最近对于可实现的平滑函数学习所获得的保证可以转移到无知设置中。在我们的证明的核心，我们根据函数类的夹逼熵建立了函数类的均匀收敛速率，这可能具有独立的研究意义。

高效无知学习与平均光滑度