EUVIMEDEUVIMED entdecken
Crossref

Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces

Anastasis Kratsios, A. Martina Neuman, Gudmund Pammer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →