Papers › Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces
Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces
Anastasis Kratsios, A. Martina Neuman, Gudmund Pammer
Machine learning models with inputs in a Euclidean space ℝᵈ, 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ₘ/N^(1/(2∨m))}ₘ₌₁^∞ 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 𝒪(1/N^(1/2)). Notably, cₘ∈𝒪(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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections