# Gradual Capacity Growth for Sparse Network Discovery

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 24 references that are in the map.
- First posted on arXiv 30 Sep 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Rethinking Spatial Dimensions of Vision Transformers](https://mlsanity.com/paper/2103.16302/) (2021)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization](https://mlsanity.com/paper/1902.05967/) (2019)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [The Break-Even Point on Optimization Trajectories of Deep Neural Networks](https://mlsanity.com/paper/2002.09572/) (2020)
- [Vision Transformer for Small-Size Datasets](https://mlsanity.com/paper/2112.13492/) (2021)
- [GradMax: Growing Neural Networks using Gradient Information](https://mlsanity.com/paper/2201.05125/) (2022)
- [Firefly Neural Architecture Descent: a General Approach for Growing Neural Networks](https://mlsanity.com/paper/2102.08574/) (2021)
- [PHEW: Constructing Sparse Networks that Learn Fast and Generalize Well without Training Data](https://mlsanity.com/paper/2010.11354/) (2020)
- [A Unified Paths Perspective for Pruning at Initialization](https://mlsanity.com/paper/2101.10552/) (2021)
- [Always-Sparse Training by Growing Connections with Guided Stochastic Exploration](https://mlsanity.com/paper/2401.06898/) (2024)

## Abstract (arXiv)

Sparse neural network methods typically assume that the target sparsity (or density) is fixed in advance, even though the relationship between network capacity and performance is generally unknown and task-dependent. Existing approaches (including iterative pruning, dynamic sparse training, and pruning at initialization) either rely on dense pretraining, incur substantial retraining cost, or require a preset sparsity budget. We propose Gradual Capacity Growth (GCG), a constructive sparse-to-dense training framework that allocates network capacity progressively during training. Starting from a sparse seed network, GCG grows new connections in stages using PathGrow, a probabilistic path-based growth rule that biases additions toward high-signal input-output pathways while preserving structural diversity. Growth is interleaved with limited training, and a lightweight performance-density extrapolation rule is used to estimate the smallest density beyond which further capacity increases yield diminishing accuracy gains. Experiments on CIFAR, TinyImageNet, and ImageNet show that GCG efficiently identifies sparse networks that achieve near-dense performance at moderate densities, without requiring dense pretraining or exhaustive retraining at each sparsity level. While growth-only methods do not reach the extreme sparsity achievable by pruning or dynamic reallocation techniques, GCG substantially reduces total training cost compared to iterative magnitude pruning and provides a practical mechanism for exploring the accuracy-density tradeoff under limited optimization budgets.