mlsanityData to 7 Oct 2026

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

arXiv 2402.05576 ↗First posted 8 Feb 2024cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

37 of 81 references.

References · 37

  1. 2018Neural Ordinary Differential Equationscited by 3,733
  2. 2018Link Prediction Based on Graph Neural Networkscited by 829
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  4. 2016Error bounds for approximations with deep ReLU networkscited by 567
  5. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  6. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  7. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  8. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  9. 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 176
  10. 2020Benign overfitting in ridge regressioncited by 152
  11. 2020Neural Rough Differential Equations for Long Time Seriescited by 140
  12. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 95
25 more
  1. 2020COT-GAN: Generating Sequential Data via Causal Optimal Transportcited by 70
  2. 2016Deep vs. shallow networks : An approximation theory perspectivecited by 63
  3. 2020Approximation Bounds for Random Neural Networks and Reservoir Systemscited by 52
  4. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  5. 2020Neural Jump Ordinary Differential Equations: Consistent Continuous-Time Prediction and Filteringcited by 33
  6. 2019Multi-marginal Wasserstein GANcited by 32
  7. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  8. 2023Generalization in Kernel Regression Under Realistic Assumptionscited by 26
  9. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  10. 2022Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformercited by 22
  11. 2022Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysiscited by 22
  12. 2016Inference for Empirical Wasserstein Distances on Finite Spacescited by 21
  13. 2013Adaptive Metric Dimensionality Reductioncited by 14
  14. 2022Instance-Dependent Generalization Bounds via Optimal Transportcited by 13
  15. 2024Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrumcited by 13
  16. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
  17. 2022Small Transformers Compute Universal Metric Embeddingscited by 12
  18. 2022Limitations of Deep Learning for Inverse Problems on Digital Hardwarecited by 9
  19. 2016Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC) Machine Learning Modelcited by 8
  20. 2023A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regressioncited by 8
  21. 2020Phase Transitions in Rate Distortion Theory and Deep Learningcited by 5
  22. 2022On generalization bounds for deep networks based on loss surface implicit regularizationcited by 5
  23. 2022Inverse Problems Are Solvable on Real Number Signal Processing Hardwarecited by 5
  24. 2024Expressive Power of ReLU and Step Networks under Floating-Point Operationscited by 5
  25. 2023Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problemcited by 4

Built on by

Not cited yet.