Memorization Capacity of Neural Networks with Conditional Computation
Not on the map. Why?
Abstract (arXiv)
Many empirical studies have demonstrated the performance benefits of conditional computation in neural networks, including reduced inference time and power consumption. We study the fundamental limits of neural conditional computation from the perspective of memorization capacity. For Rectified Linear Unit (ReLU) networks without conditional computation, it is known that memorizing a collection of n input-output relationships can be accomplished via a neural network with O(√n) neurons. Calculating the output of this neural network can be accomplished using O(√n) elementary arithmetic operations of additions, multiplications and comparisons for each input. Using a conditional ReLU network, we show that the same task can be accomplished using only O(log n) operations per input. This represents an almost exponential improvement as compared to networks without conditional computation. We also show that the Theta(log n) rate is the best possible. Our achievability result utilizes a general methodology to synthesize a conditional network out of an unconditional network in a computationally-efficient manner, bridging the gap between unconditional and conditional architectures.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 24 of its 41 references that are in the map. First posted on arXiv 20 Mar 2023.
Builds on
24 of 41 references.
References · 24
- 2017Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layercited by 3,413
- 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,014
- 2013Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computationcited by 2,031
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
- 2017BranchyNet: Fast Inference via Early Exiting from Deep Neural Networkscited by 591
- 2017Learning Sparse Neural Networks through L0 Regularizationcited by 571
- 2016Adaptive Computation Time for Recurrent Neural Networkscited by 479
- 2021Dynamic Neural Networks: A Surveycited by 405
- 2013Learning Factored Representations in a Deep Mixture of Expertscited by 275
- 2015Conditional Computation in Neural Networks for faster modelscited by 166
- 2018Dynamic Channel Pruning: Feature Boosting and Suppressioncited by 129
12 more
- 2016Identity Matters in Deep Learningcited by 107
- 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
- 2018Deep Neural Decision Treescited by 72
- 2018Adaptive Neural Treescited by 64
- 2013Low-Rank Approximations for Conditional Feedforward Computation in Deep Neural Networkscited by 44
- 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
- 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
- 2016Convolutional Rectifier Networks as Generalized Tensor Decompositionscited by 32
- 2014Exponentially Increasing the Capacity-to-Computation Ratio for Conditional Computation in Deep Learningcited by 24
- 2016Decision Forests, Convolutional Networks and the Models in-Betweencited by 15
- 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14
- 2022Class Based Thresholding in Early Exit Semantic Segmentation Networkscited by 5
Built on by
Citing papers per year: 2023: 2; 2024: 0; 2025: 0; 2026: 1.
3 papers.