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

Machine learning models with inputs in a Euclidean space Rd, when implemented on digital computers, generalize, and their generalization gap converges to 0 at a rate ofc/N1/2concerning the sample sizeN. However, the constantc> 0 obtained through classical methods can be large in terms of the ambient dimensiondand machine precision, posing a challenge whenNis small to realistically large. In this paper, we derive a family of generalization bounds {cm/N1/(2∨m)}∞m=1tailored for learning models on digital computers, which adapt to both the sample sizeNand the so-called geometric representation dimensionmof the discrete learning problem. Adjusting the parametermaccording toNresults in significantly tighter generalization bounds for practical sample sizesN, while settingmsmall maintains the optimal dimension-free worst-case rate ofO(1/N1/2). Notably,cm∈O(m1/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.