# Dynamic Sparse Training via Balancing the Exploration-Exploitation Trade-off

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 30 Nov 2022.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Carbon Emissions and Large Neural Network Training](https://mlsanity.com/paper/2104.10350/) (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)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [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)
- [Qualitatively characterizing neural network optimization problems](https://mlsanity.com/paper/1412.6544/) (2014)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [Deep Rewiring: Training very sparse deep networks](https://mlsanity.com/paper/1711.05136/) (2017)
- [A Systematic DNN Weight Pruning Framework using Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1804.03294/) (2018)
- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [Sparse Training via Boosting Pruning Plasticity with Neuroregeneration](https://mlsanity.com/paper/2106.10404/) (2021)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [MEST: Accurate and Fast Memory-Economic Sparse Training Framework on the Edge](https://mlsanity.com/paper/2110.14032/) (2021)
- [Prune Once for All: Sparse Pre-Trained Language Models](https://mlsanity.com/paper/2111.05754/) (2021)
- [Progressive Skeletonization: Trimming more fat from a network at initialization](https://mlsanity.com/paper/2006.09081/) (2020)
- [Diverse Neural Network Learns True Target Functions](https://mlsanity.com/paper/1611.03131/) (2016)
- [Accelerating Framework of Transformer by Hardware Design and Model Compression Co-Optimization](https://mlsanity.com/paper/2110.10030/) (2021)
- [Effective Model Sparsification by Scheduled Grow-and-Prune Methods](https://mlsanity.com/paper/2106.09857/) (2021)
- [Sparse Double Descent: Where Network Pruning Aggravates Overfitting](https://mlsanity.com/paper/2206.08684/) (2022)
- [A Length Adaptive Algorithm-Hardware Co-design of Transformer on FPGA Through Sparse Attention and Dynamic Pipelining](https://mlsanity.com/paper/2208.03646/) (2022)
- [Sparse Progressive Distillation: Resolving Overfitting under Pretrain-and-Finetune Paradigm](https://mlsanity.com/paper/2110.08190/) (2021)
- [The Externalities of Exploration and How Data Diversity Helps Exploitation](https://mlsanity.com/paper/1806.00543/) (2018)
- [Towards Sparsification of Graph Neural Networks](https://mlsanity.com/paper/2209.04766/) (2022)
- [An Automatic and Efficient BERT Pruning for Edge AI Systems](https://mlsanity.com/paper/2206.10461/) (2022)

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

- [AutoReP: Automatic ReLU Replacement for Fast Private Network Inference](https://mlsanity.com/paper/2308.10134/) (2023)
- [LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference](https://mlsanity.com/paper/2309.14331/) (2023)
- [Visual Prompting Upgrades Neural Network Sparsification: A Data-Model Perspective](https://mlsanity.com/paper/2312.01397/) (2023)
- [Accel-GCN: High-Performance GPU Accelerator Design for Graph Convolution Networks](https://mlsanity.com/paper/2308.11825/) (2023)
- [RRNet: Towards ReLU-Reduced Neural Network for Two-party Computation Based Private Inference](https://mlsanity.com/paper/2302.02292/) (2023)
- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [Sparse-IFT: Sparse Iso-FLOP Transformations for Maximizing Training Efficiency](https://mlsanity.com/paper/2303.11525/) (2023)
- [Training Large Language Models Efficiently with Sparsity and Dataflow](https://mlsanity.com/paper/2304.05511/) (2023)
- [DynST: Dynamic Sparse Training for Resource-Constrained Spatio-Temporal Forecasting](https://mlsanity.com/paper/2403.02914/) (2024)
- [QuMoS: A Framework for Preserving Security of Quantum Machine Learning Model](https://mlsanity.com/paper/2304.11511/) (2023)
- [Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correction](https://mlsanity.com/paper/2301.03573/) (2023)
- [Calibrating the Rigged Lottery: Making All Tickets Reliable](https://mlsanity.com/paper/2302.09369/) (2023)
- [Edge-InversionNet: Enabling Efficient Inference of InversionNet on Edge Devices](https://mlsanity.com/paper/2310.09667/) (2023)
- [Embracing Unknown Step by Step: Towards Reliable Sparse Training in Real World](https://mlsanity.com/paper/2403.20047/) (2024)
- [On-Demand Multi-Task Sparsity for Efficient Large-Model Deployment on Edge Devices](https://mlsanity.com/paper/2511.19986/) (2025)

## Abstract (arXiv)

Over-parameterization of deep neural networks (DNNs) has shown high prediction accuracy for many applications. Although effective, the large number of parameters hinders its popularity on resource-limited devices and has an outsize environmental impact. Sparse training (using a fixed number of nonzero weights in each iteration) could significantly mitigate the training costs by reducing the model size. However, existing sparse training methods mainly use either random-based or greedy-based drop-and-grow strategies, resulting in local minimal and low accuracy. In this work, we consider the dynamic sparse training as a sparse connectivity search problem and design an exploitation and exploration acquisition function to escape from local optima and saddle points. We further design an acquisition function and provide the theoretical guarantees for the proposed method and clarify its convergence property. Experimental results show that sparse models (up to 98% sparsity) obtained by our proposed method outperform the SOTA sparse training methods on a wide variety of deep learning tasks. On VGG-19 / CIFAR-100, ResNet-50 / CIFAR-10, ResNet-50 / CIFAR-100, our method has even higher accuracy than dense models. On ResNet-50 / ImageNet, the proposed method has up to 8.2% accuracy improvement compared to SOTA sparse training methods.