# On the Convergence of Shallow Neural Network Training with Randomly Masked Neurons

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 70 of its 83 references that are in the map.
- First posted on arXiv 5 Dec 2021.

## Builds on (most cited first, 30 of 70)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [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)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Slimmable Neural Networks](https://mlsanity.com/paper/1812.08928/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)

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

- [Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable?](https://mlsanity.com/paper/2502.20914/) (2025)
- [FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity](https://mlsanity.com/paper/2404.09816/) (2024)
- [Efficient and Light-Weight Federated Learning via Asynchronous Distributed Dropout](https://mlsanity.com/paper/2210.16105/) (2022)
- [On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks](https://mlsanity.com/paper/2203.14328/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Federated Learning Over Images: Vertical Decompositions and Pre-Trained Backbones Are Difficult to Beat](https://mlsanity.com/paper/2309.03237/) (2023)
- [LOFT: Finding Lottery Tickets through Filter-wise Training](https://mlsanity.com/paper/2210.16169/) (2022)
- [Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK](https://mlsanity.com/paper/2301.00327/) (2023)
- [Xtreme Margin: A Tunable Loss Function for Binary Classification Problems](https://mlsanity.com/paper/2211.00176/) (2022)
- [Demystifying the Global Convergence Puzzle of Learning Over-parameterized ReLU Nets in Very High Dimensions](https://mlsanity.com/paper/2206.03254/) (2022)
- [MIRACLE: Multi-task Learning based Interpretable Regulation of Autoimmune Diseases through Common Latent Epigenetics](https://mlsanity.com/paper/2306.13866/) (2023)

## Abstract (arXiv)

With the motive of training all the parameters of a neural network, we study why and when one can achieve this by iteratively creating, training, and combining randomly selected subnetworks. Such scenarios have either implicitly or explicitly emerged in the recent literature: see e.g., the Dropout family of regularization techniques, or some distributed ML training protocols that reduce communication/computation complexities, such as the Independent Subnet Training protocol. While these methods are studied empirically and utilized in practice, they often enjoy partial or no theoretical support, especially when applied on neural network-based objectives. In this manuscript, our focus is on overparameterized single hidden layer neural networks with ReLU activations in the lazy training regime. By carefully analyzing i) the subnetworks' neural tangent kernel, ii) the surrogate functions' gradient, and iii) how we sample and combine the surrogate functions, we prove linear convergence rate of the training error -- up to a neighborhood around the optimal point -- for an overparameterized single-hidden layer perceptron with a regression loss. Our analysis reveals a dependency of the size of the neighborhood around the optimal point on the number of surrogate models and the number of local training steps for each selected subnetwork. Moreover, the considered framework generalizes and provides new insights on dropout training, multi-sample dropout training, as well as Independent Subnet Training; for each case, we provide convergence results as corollaries of our main theorem.