mlsanityData to 7 Oct 2026

Instance-Dependent Generalization Bounds via Optimal Transport

arXiv 2211.01258 ↗First posted 2 Nov 2022stat.ML cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. Since such bounds often hold uniformly over all parameters, they suffer from over-parametrization and fail to account for the strong inductive bias of initialization and stochastic gradient descent. As an alternative, we propose a novel optimal transport interpretation of the generalization problem. This allows us to derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. Therefore, our bounds are agnostic to the parametrization of the model and work well when the number of training samples is much smaller than the number of parameters. With small modifications, our approach yields accelerated rates for data on low-dimensional manifolds and guarantees under distribution shifts. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 51 of its 98 references that are in the map. First posted on arXiv 2 Nov 2022.

Builds on

51 of 98 references.

References · 51

  1. 2018Neural Ordinary Differential Equationscited by 3,733
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  5. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  6. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  7. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  8. 2017Exploring Generalization in Deep Learningcited by 595
  9. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  10. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  11. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  12. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
38 more
  1. 2018Regularisation of Neural Networks by Enforcing Lipschitz Continuitycited by 311
  2. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  3. 2021The Intrinsic Dimension of Images and Its Impact on Learningcited by 307
  4. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  5. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  6. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  7. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 290
  8. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  9. 2017Parseval Networks: Improving Robustness to Adversarial Examplescited by 288
  10. 2015Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulationscited by 285
  11. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  12. 2018Sorting out Lipschitz function approximationcited by 211
  13. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  14. 2019Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learningcited by 169
  15. 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 158
  16. 2020Neural Rough Differential Equations for Long Time Seriescited by 140
  17. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  18. 2015On the properties of variational approximations of Gibbs posteriorscited by 121
  19. 2015Path-SGD: Path-Normalized Optimization in Deep Neural Networkscited by 117
  20. 2016Robust Large Margin Deep Neural Networkscited by 117
  21. 2018Predicting the Generalization Gap in Deep Networks with Margin Distributionscited by 111
  22. 2020Exactly Computing the Local Lipschitz Constant of ReLU Networkscited by 102
  23. 2019The phase diagram of approximation rates for deep neural networkscited by 86
  24. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  25. 2021On the approximation of functions by tanh neural networkscited by 81
  26. 2019Distributionally Robust Optimization and Generalization in Kernel Methodscited by 73
  27. 2020Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionalitycited by 49
  28. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 45
  29. 2019An Alternative Probabilistic Interpretation of the Huber Losscited by 43
  30. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
  31. 2020A generative adversarial network approach to calibration of local stochastic volatility modelscited by 28
  32. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  33. 2019Wasserstein Smoothing: Certified Robustness against Wasserstein Adversarial Attackscited by 25
  34. 2020On the Generalization Properties of Adversarial Trainingcited by 23
  35. 2020Generalised Lipschitz Regularisation Equals Distributional Robustnesscited by 14
  36. 2022Adversarial robustness of sparse local Lipschitz predictorscited by 11
  37. 2021Robustness to Pruning Predicts Generalization in Deep Neural Networkscited by 10
  38. 2022Change of measure through the Legendre transformcited by 10

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 3; 2025: 6; 2026: 1.

13 papers.

Sort:

  1. 2023Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equationcited by 32
  2. 2023A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regressioncited by 8
  3. 2024Neural Spacetimes for DAG Representation Learningcited by 5
  4. 2024Gentle Local Robustness implies Generalizationcited by 4
  5. 2023Transformers Can Solve Non-Linear and Non-Markovian Filtering Problems in Continuous Time For Conditionally Gaussian Signalscited by 3
  6. 2025Learning from one graph: transductive learning guarantees via the geometry of small random worldscited by 3
  7. 2025Simultaneously Solving Infinitely Many LQ Mean Field Games In Hilbert Spaces: The Power of Neural Operatorscited by 3
  8. 2025Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained modelscited by 2
  9. 2025Beyond Real Data: Synthetic Data through the Lens of Regularizationcited by 2
  10. 2025Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Datacited by 1
  11. 2024Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spacescited by 0
  12. 2025The Hidden Power of Normalization Layers in Neural Networks: Exponential Capacity Controlcited by 0
1 more
  1. 2026Statistical Guarantees for Reasoning Probes on Looped Boolean Circuitscited by 0