Deep learning generalizes because the parameter-function map is biased towards simple functions

Abstract

Deep neural networks (DNNs) generalize remarkably well without explicit regularization even in the strongly over-parametrized regime where classical learning theory would instead predict that they would severely overfit. While many proposals for some kind of implicit regularization have been made to rationalise this success, there is no consensus for the fundamental reason why DNNs do not strongly overfit. In this paper, we provide a new explanation. By applying a very general probability-complexity bound recently derived from algorithmic information theory (AIT), we argue that the parameter-function map of many DNNs should be exponentially biased towards simple functions. We then provide clear evidence for this strong simplicity bias in a model DNN for Boolean functions, as well as in much larger fully connected and convolutional networks applied to CIFAR10 and MNIST. As the target functions in many real problems are expected to be highly structured, this intrinsic simplicity bias helps explain why deep networks generalize well on real world problems. This picture also facilitates a novel PAC-Bayes approach where the prior is taken over the DNN input-output function space, rather than the more conventional prior over parameter space. If we assume that the training algorithm samples parameters close to uniformly within the zero-error region then the PAC-Bayes theorem can be used to guarantee good expected generalization for target functions producing high-likelihood training sets. By exploiting recently discovered connections between DNNs and Gaussian processes to estimate the marginal likelihood, we produce relatively tight generalization PAC-Bayes error bounds which correlate well with the true error on realistic datasets such as MNIST and CIFAR10 and for architectures including convolutional and fully connected networks.

arXiv commentPublished as a conference paper at ICLR 2019

References in corpus (29)

• Deep Learning in Neural Networks: An Overview
• Improving neural networks by preventing co-adaptation of feature detectors
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Do Deep Nets Really Need to be Deep?
• On the Number of Linear Regions of Deep Neural Networks
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Deep Neural Networks as Gaussian Processes
• Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
• A Closer Look at Memorization in Deep Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Exponential expressivity in deep neural networks through transient chaos
• On the importance of single directions for generalization
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Essentially No Barriers in Neural Network Energy Landscape
• Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
• Simple random search provides a competitive approach to reinforcement learning
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Sharp Minima Can Generalize For Deep Nets
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• The arrival of the frequent: how bias in genotype-phenotype maps can steer populations to local optima
• Stochastic Gradient Descent as Approximate Bayesian Inference
• Deep Convolutional Networks as shallow Gaussian Processes
• Genetic correlations greatly increase mutational robustness and can both reduce and enhance evolvability
• Norm-Based Capacity Control in Neural Networks
• Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning
• Theory II: Landscape of the Empirical Risk in Deep Learning
• On the non-randomness of maximum Lempel Ziv complexity sequences of finite size
• A Correspondence Between Random Neural Networks and Statistical Field Theory

Cited by in corpus (39)

• Shortcut Learning in Deep Neural Networks
• Machine Learning and Deep Learning -- A review for Ecologists
• Unsupervised phase discovery with deep anomaly detection
• The Pitfalls of Simplicity Bias in Neural Networks
• What shapes feature representations? Exploring datasets, architectures, and training
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes
• A Fine-Grained Spectral Perspective on Neural Networks
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• Risks from Learned Optimization in Advanced Machine Learning Systems
• Boundary thickness and robustness in learning models
• Frequency Principle in Deep Learning with General Loss Functions and Its Potential Application
• Generalization bounds for deep learning
• A Note on A Priori Forecasting and Simplicity Bias in Time Series
• The Low-Rank Simplicity Bias in Deep Networks
• Neural networks are a priori biased towards Boolean functions with low entropy
• Which Shortcut Cues Will DNNs Choose? A Study from the Parameter-Space Perspective
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• A Bayesian Perspective on Training Speed and Model Selection
• Is SGD a Bayesian sampler? Well, almost
• The shape and simplicity biases of adversarially robust ImageNet-trained CNNs
• Multiclass classification utilising an estimated algorithmic probability prior
• Learning by Turning: Neural Architecture Aware Optimisation
• Deep frequency principle towards understanding why deeper learning is faster
• Layer Folding: Neural Network Depth Reduction using Activation Linearization
• Improved generalization by noise enhancement
• Why flatness does and does not correlate with generalization for deep neural networks
• How Does Adversarial Fine-Tuning Benefit BERT?
• On the Power of Deep but Naive Partial Label Learning
• Initializing ReLU networks in an expressive subspace of weights
• Deep Networks as Logical Circuits: Generalization and Interpretation
• Unified Regularity Measures for Sample-wise Learning and Generalization
• SGD Through the Lens of Kolmogorov Complexity
• Understanding Layer-wise Contributions in Deep Neural Networks through Spectral Analysis
• Depth Without the Magic: Inductive Bias of Natural Gradient Descent
• On Data-centric Myths
• Combating Unknown Bias with Effective Bias-Conflicting Scoring and Gradient Alignment
• Avoiding Kernel Fixed Points: Computing with ELU and GELU Infinite Networks
• An information-theoretic upper bound on prime gaps