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

arXiv: https://arxiv.org/abs/2402.05576 · HTML: https://mlsanity.com/paper/2402.05576/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 81 references that are in the map.
- First posted on arXiv 8 Feb 2024.

## Builds on (most cited first, 30 of 37)

- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Neural Rough Differential Equations for Long Time Series](https://mlsanity.com/paper/2009.08295/) (2020)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [COT-GAN: Generating Sequential Data via Causal Optimal Transport](https://mlsanity.com/paper/2006.08571/) (2020)
- [Deep vs. shallow networks : An approximation theory perspective](https://mlsanity.com/paper/1608.03287/) (2016)
- [Approximation Bounds for Random Neural Networks and Reservoir Systems](https://mlsanity.com/paper/2002.05933/) (2020)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Neural Jump Ordinary Differential Equations: Consistent Continuous-Time Prediction and Filtering](https://mlsanity.com/paper/2006.04727/) (2020)
- [Multi-marginal Wasserstein GAN](https://mlsanity.com/paper/1911.00888/) (2019)
- [Individually Conditional Individual Mutual Information Bound on Generalization Error](https://mlsanity.com/paper/2012.09922/) (2020)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformer](https://mlsanity.com/paper/2201.13094/) (2022)
- [Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysis](https://mlsanity.com/paper/2210.13300/) (2022)
- [Inference for Empirical Wasserstein Distances on Finite Spaces](https://mlsanity.com/paper/1610.03287/) (2016)
- [Adaptive Metric Dimensionality Reduction](https://mlsanity.com/paper/1302.2752/) (2013)
- [Instance-Dependent Generalization Bounds via Optimal Transport](https://mlsanity.com/paper/2211.01258/) (2022)
- [Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum](https://mlsanity.com/paper/2402.01297/) (2024)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Limitations of Deep Learning for Inverse Problems on Digital Hardware](https://mlsanity.com/paper/2202.13490/) (2022)

## Abstract (arXiv)

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/N1/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 cm/N1/(2vee 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/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.