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

2024/02/08 by Kratsios, Anastasis, Neuman, A. Martina, Pammer, Gudmund
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2402.05576

Abstract

Machine learning models with inputs in a Euclidean space ℝ^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^∞ 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 O(1/N^1/2). Notably, c_m∈ 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.

Related

• Dimension Free Generalization Bounds for Non Linear Metric Learning
• Learning Low-Dimensional Metrics
• Adaptive Metric Dimensionality Reduction
• Compressive Mahalanobis Metric Learning Adapts to Intrinsic Dimension
• Strong Memory Lower Bounds for Learning Natural Models