# A Combinatorial Theory of Dropout: Subnetworks, Graph Geometry, and Generalization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 20 Apr 2025.

## Builds on (most cited first, 13 of 13)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Variational Dropout and the Local Reparameterization Trick](https://mlsanity.com/paper/1506.02557/) (2015)
- [Deep Ensembles: A Loss Landscape Perspective](https://mlsanity.com/paper/1912.02757/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Essentially No Barriers in Neural Network Energy Landscape](https://mlsanity.com/paper/1803.00885/) (2018)
- [The Lottery Ticket Hypothesis for Pre-trained BERT Networks](https://mlsanity.com/paper/2007.12223/) (2020)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [Dropout Training as Adaptive Regularization](https://mlsanity.com/paper/1307.1493/) (2013)

## Built on by (most cited first, 3 of 3)

- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2509.10034/) (2025)
- [Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphs](https://mlsanity.com/paper/2509.03056/) (2025)

## Abstract (arXiv)

We propose a combinatorial and graph-theoretic theory of dropout by modeling training as a random walk over a high-dimensional graph of binary subnetworks. Each node represents a masked version of the network, and dropout induces stochastic traversal across this space. We define a subnetwork contribution score that quantifies generalization and show that it varies smoothly over the graph. Using tools from spectral graph theory, PAC-Bayes analysis, and combinatorics, we prove that generalizing subnetworks form large, connected, low-resistance clusters, and that their number grows exponentially with network width. This reveals dropout as a mechanism for sampling from a robust, structured ensemble of well-generalizing subnetworks with built-in redundancy. Extensive experiments validate every theoretical claim across diverse architectures. Together, our results offer a unified foundation for understanding dropout and suggest new directions for mask-guided regularization and subnetwork optimization.