mlsanityData to 7 Oct 2026

Benefits of Additive Noise in Composing Classes with Bounded Capacity

arXiv 2206.07199 ↗First posted 14 Jun 2022stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We observe that given two (compatible) classes of functions F and H with small capacity as measured by their uniform covering numbers, the capacity of the composition class H circ F can become prohibitively large or even unbounded. We then show that adding a small amount of Gaussian noise to the output of F before composing it with H can effectively control the capacity of H circ F, offering a general recipe for modular design. To prove our results, we define new notions of uniform covering number of random functions with respect to the total variation and Wasserstein distances. We instantiate our results for the case of multi-layer sigmoid neural networks. Preliminary empirical results on MNIST dataset indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible (i.e., element-wise i.i.d. Gaussian noise with standard deviation 10-240). The source codes are available at https://github.com/fathollahpour/compositionnoise.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 28 of its 60 references that are in the map. First posted on arXiv 14 Jun 2022.

Builds on

28 of 60 references.

References · 28

  1. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  4. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  5. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  6. 2017Implicit Regularization in Matrix Factorizationcited by 318
  7. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  8. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  9. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  10. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  11. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  12. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
16 more
  1. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  2. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  3. 2021Deep learning: a statistical viewpointcited by 239
  4. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  5. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  6. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  7. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  8. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  9. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  10. 2018Does data interpolation contradict statistical optimality?cited by 95
  11. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  12. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  13. 2020Gradient descent follows the regularization path for general lossescited by 57
  14. 2019Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resiliencecited by 51
  15. 2021Noisy Recurrent Neural Networkscited by 42
  16. 2014Dropout Rademacher Complexity of Deep Neural Networkscited by 14

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 2.

4 papers.

  1. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  2. 2025Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Datacited by 1
  3. 2023On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequencescited by 0
  4. 2025Tight Generalization Error Bounds for Stochastic Gradient Descent in Non-convex Learningcited by 0