Many of the foundations of machine learning rely on the idealized premise
that all input and output spaces are infinite, e.g.~$\mathbb{R}^d$. This core
assumption is systematically violated in practice due to digital computing
limitations from finite machine precision, rounding, and limited RAM. In short,
digital computers operate on finite grids in $\mathbb{R}^d$. By exploiting
these discrete structures, we show the curse of dimensionality in statistical
learning is systematically broken when models are implemented on real
computers. Consequentially, we obtain new generalization bounds with
dimension-free rates for kernel and deep ReLU MLP regressors, which are
implemented on real-world machines.
Our results are derived using a new non-asymptotic concentration of measure
result between a probability measure over any finite metric space and its
empirical version associated with $N$ i.i.d. samples when measured in the
$1$-Wasserstein distance. Unlike standard concentration of measure results, the
concentration rates in our bounds do not hold uniformly for all sample sizes
$N$; instead, our rates can adapt to any given $N$. This yields significantly
tighter bounds for realistic sample sizes while achieving the optimal
worst-case rate of $\mathcal{O}(1/N^{1/2})$ for massive. Our results are built
on new techniques combining metric embedding theory with optimal transport

通过利用离散结构，研究表明在实际计算机上实现的模型中统计学习中的维度灾难被系统性地打破。我们得到了基于内核和深度 ReLU MLP 回归器的新的无维度率的广义界限，并使用新的非渐近测度集中结果导出，该结果在任意有限度量空间上的概率测度与其经验版本之间的 $1$-Wasserstein 距离测量时成立。