Abstract: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>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.
| Subjects: | Machine Learning (cs.LG) |
| MSC classes: | 68T05, 49Q22, 60B10, 46B85, 68Q32 |
| Cite as: | arXiv:2402.05576 [cs.LG] |
| (or arXiv:2402.05576v4 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2402.05576 arXiv-issued DOI via DataCite |
Submission history
From: A. Martina Neuman [view email]
[v1]
Thu, 8 Feb 2024 11:23:11 UTC (854 KB)
[v2]
Sun, 14 Apr 2024 23:17:15 UTC (621 KB)
[v3]
Fri, 27 Dec 2024 23:45:57 UTC (1,239 KB)
[v4]
Wed, 13 May 2026 08:37:33 UTC (132 KB)