Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces
IEEE Transactions on Information Theory · 2026-08 · 72 (8) · 5954-5969
DOI: 10.1109/tit.2026.3693950 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-08. Verfasst von Anastasis Kratsios und 2 weiteren Autor:innen. Die Arbeit nennt 80 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery, Austrian Science Fund, ETH Zürich Foundation.
Abstract (Originalsprache)
Machine learning models with inputs in a Euclidean space $\mathbb {R}^{d}$ , when implemented on digital computers, generalize, and their generalization gap converges to 0 at a rate of $c/N^{1/2}$ concerning the sample size $N$ . However, the constant $c\gt 0$ obtained through classical methods can be large in terms of the ambient dimension $d$ and 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 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}(m^{1/2})$ 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 finite metric spaces, established via leveraging metric embedding arguments.
Förderung
- Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery
- Austrian Science Fund
- ETH Zürich Foundation
Zitieren
APA
Kratsios, A., Neuman, A. M., & Pammer, G. (2026). Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces. IEEE Transactions on Information Theory, 72(8), 5954-5969. https://doi.org/10.1109/tit.2026.3693950
Vancouver
Kratsios A, Neuman AM, Pammer G. Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces. IEEE Transactions on Information Theory. 2026;72(8):5954-5969. doi:10.1109/tit.2026.3693950
BibTeX
@article{Kratsios2026,
author = {Kratsios, Anastasis and Neuman, A. Martina and Pammer, Gudmund},
title = {Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {8},
pages = {5954--5969},
doi = {10.1109/tit.2026.3693950}
}
EUVIMED