Tighter Generalization Bounds on Digital Computers via Discrete Optimal Transport
<|reference_start|>Tighter Generalization Bounds on Digital Computers via Discrete Optimal Transport: Machine learning models with inputs in a Euclidean space $\mathbb{R}^d$, when implemented on digital computers, generalize, and their {\it generalization gap} converges to $0$ at a rate of $c/N^{1/2}$ concerning the sample size $N$. However, the constant $c>0$ obtained through classical methods can be large in terms of the ambient dimension $d$ and the machine precision, posing a challenge when $N$ is small to realistically large. In this paper, we derive a family of generalization bounds $\{c_m/N^{1/(2\vee m)}\}_{m=1}^{\infty}$ tailored for learning models on digital computers, which adapt to both the sample size $N$ and the so-called geometric {\it representation dimension} $m$ of the discrete learning problem. Adjusting the parameter $m$ according to $N$ results in significantly tighter generalization bounds for practical sample sizes $N$, while setting $m$ small maintains the optimal dimension-free worst-case rate of $\mathcal{O}(1/N^{1/2})$. Notably, $c_{m}\in \mathcal{O}(\sqrt{m})$ for learning models on discretized Euclidean domains.   Furthermore, our adaptive generalization bounds are formulated based on our new non-asymptotic result for concentration of measure in discrete optimal transport, established via leveraging metric embedding arguments.<|reference_end|>
@article{kratsios2024tighter,
    title={Tighter Generalization Bounds on Digital Computers via Discrete Optimal
  Transport},
    author={Anastasis Kratsios, A. Martina Neuman, Gudmund Pammer},
    journal={arXiv preprint arXiv:2402.05576},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.05576},
    primaryClass={cs.LG}
}