Pruning with Regrowth

Unlike static pruning, pruning with regrowth treats the network's connectivity as a mutable structure. The algorithm performs an ongoing search for an optimal sparse sub-network by:

• Pruning: Removing connections with the smallest magnitudes or lowest scores.
• Regrowing: Adding new connections in locations suggested by high gradient signals or other heuristics.
• Iteration: Repeating this cycle allows the network to escape suboptimal sparse configurations discovered early in training. This is a form of architecture search within a fixed parameter budget.

A core constraint in these algorithms is maintaining a target sparsity level (e.g., 90% zeros). After each pruning-and-regrowth cycle, the total number of non-zero parameters is restored to this predefined budget. This ensures the computational and memory benefits of sparsity are preserved throughout training. The budget can be applied globally or per layer. Managing this budget is what differentiates it from purely pruning-aware training, which only removes parameters.

The intelligence of the algorithm lies in how it selects connections to regrow. Common heuristics include:

• Gradient-based Regrowth: Connections are regrown where the gradient of the loss with respect to a zeroed weight is large, indicating high potential to reduce loss.
• Random Regrowth: A fraction of new connections are assigned randomly, providing exploration.
• Momentum-based: Historical gradient information guides regrowth to persistent promising areas. The choice of heuristic directly impacts the speed of convergence and final accuracy, balancing exploration vs. exploitation of the parameter space.

Pruning with regrowth is a practical implementation of searching for a 'winning ticket'—a sparse, trainable subnetwork—as proposed by the Lottery Ticket Hypothesis. However, instead of finding a static ticket at initialization, it dynamically evolves the ticket during training. If a pruned connection proves important later (evidenced by a large gradient), the regrowth mechanism can restore it. This makes the algorithm more robust and less dependent on finding the perfect initial sparse mask.

Two seminal algorithms exemplify this paradigm:

• Sparse Evolutionary Training (SET): Initializes a network with a sparse Erdős–Rényi random connectivity. Periodically, it removes the smallest-magnitude weights and regrows new random connections. It relies on the random exploration of new pathways.
• Dynamic Network Surgery: A more guided approach. It prunes low-magnitude weights but only regrows connections where the gradient exceeds a high threshold. It also uses momentum to track the importance of connections over time, reducing noisy regrowth decisions. Both maintain a fixed parameter count.

This approach addresses key limitations of iterative magnitude pruning:

• Mitigates Irreversible Damage: In pure pruning, if an important weight is mistakenly removed early, it's lost forever. Regrowth provides a recovery mechanism.
• Explores Better Topologies: It can discover high-performance sparse structures that are not reachable by only removing weights from a dense network.
• Improved Final Accuracy: For a given target sparsity, pruning with regrowth often achieves higher accuracy than one-shot or iterative pruning, as it refines the connectivity. The trade-off is increased algorithmic complexity and training time overhead.

Dynamic Network Surgery is an early and influential algorithm that introduced the core prune-and-regrow loop. It operates by:

• Iteratively pruning connections with weights below a threshold.
• Regrowing connections based on high gradient magnitude, indicating untapped potential.
• Maintaining a fixed parameter budget throughout training, forcing the network to explore the sparse parameter space efficiently. This method demonstrated that networks could achieve high sparsity with minimal accuracy loss by not treating pruning as a one-way operation.

Sparse Evolutionary Training (SET) is a foundational algorithm that starts with a randomly initialized, sparse Erdős–Rényi network. During training, it periodically:

• Removes a fraction of the smallest-weight connections.
• Regrows new random connections to maintain the fixed sparsity level.
• This evolutionary process allows the network topology to adapt, often outperforming static sparse masks. SET proved that training a network from scratch with dynamic sparsity is feasible and effective.

Building on the Lottery Ticket Hypothesis, Rigging the Lottery Ticket (RLT) is an algorithm that finds high-performing sparse subnetworks through regrowth. The process is:

1. Prune a large percentage of weights from a pre-trained network.
2. Regrow connections based on gradient information, not just magnitude.
3. Re-train the new subnetwork. This method actively 'rigs' the lottery by guiding the regrowth process with gradient signals, leading to discovered subnetworks that can match or exceed the performance of those found by iterative magnitude pruning alone.

Deep Rewiring (DeepR) frames pruning and regrowth as a sampling process from a probability distribution over connections, regulated by a log-barrier term in the loss function. This approach:

• Encourages exploration of the parameter space by preventing any connection from being permanently removed.
• Uses a stochastic update rule where connections can be regrown based on their potential contribution.
• Provides a theoretical foundation connecting the algorithm to Bayesian sampling, offering insights into why dynamic sparsity aids learning.

While not always bundled as high-level APIs, the core mechanics of pruning with regrowth are implemented using standard deep learning frameworks:

• Mask Management: Sparse connectivity is enforced using binary masks applied to weight tensors.
• Gradient Tracking: The register_full_backward_hook in PyTorch or custom gradient tapes in TensorFlow are used to track gradients for regrowth decisions.
• Custom Optimizers: Algorithms often require modifying the optimizer step to include the mask update (prune/regrow) logic. Libraries like TorchPruner or TensorFlow Model Optimization Toolkit provide foundational pruning APIs that can be extended for regrowth.

For real-world deployment, naive regrowth can create irregular sparsity patterns that are inefficient on hardware. Advanced implementations incorporate hardware-aware constraints:

• Structured Regrowth: Regrowing entire filters, channels, or blocks (2:4 sparsity) to align with hardware accelerators like NVIDIA's Ampere architecture.
• Pattern-Locked Gradients: Only allowing regrowth in hardware-supported sparse patterns.
• Search-Based Methods: Using Hardware-Aware Neural Architecture Search (HW-NAS) to explore the space of sparse, regrowable architectures under direct latency or energy constraints.

An iterative compression technique that performs pruning and connection regrowth in real-time during training. Unlike static pruning, it allows the network topology to evolve dynamically.

• Key Mechanism: Uses gradient-based heuristics to identify and prune unimportant weights while simultaneously regrowing connections in regions with high gradient magnitude.
• Objective: To continuously explore the sparse parameter space, avoiding irreversible removal of potentially useful connections.
• Contrast with Pruning with Regrowth: Often used synonymously, but 'surgery' emphasizes the continuous, fine-grained cutting and splicing of connections.

An algorithm that initializes and maintains a sparse network throughout training by periodically removing the smallest weights and regrowing random new connections.

• Fixed Sparsity: Maintains a user-defined, constant level of sparsity (e.g., 80% zeros) from start to finish.
• Evolutionary Phase: After each training epoch, a fraction of the smallest-magnitude weights are pruned, and an equal number of new connections are randomly initialized elsewhere in the network.
• Use Case: Efficiently trains large networks from scratch with a fraction of the parameters, reducing memory and compute costs during training itself.

A foundational theory that motivates pruning with regrowth. It posits that within a dense, randomly-initialized network, there exists a sparse subnetwork that, if trained in isolation, can match the original network's performance.

• Winning Ticket: The optimal sparse subnetwork found through iterative magnitude pruning.
• Implication for Regrowth: Suggests the existence of high-performance sparse architectures, but the initial pruning may destroy them. Regrowth algorithms actively search for these 'winning tickets' by exploring new connections.
• Experimental Basis: Demonstrated that these subnetworks exist at initialization, before training.

A framework that uses reinforcement learning to automatically determine the optimal compression policy (pruning ratio, quantization bit-width) for each layer.

• Agent-Based Search: An RL agent takes layer-specific states (e.g., filter shape, accuracy sensitivity) and outputs a compression action.
• Reward Function: Typically balances model accuracy, size, and latency.
• Relation to Regrowth: AMC can be used to schedule when and how aggressively to apply pruning with regrowth, making the exploration process data-driven and automated.

A scheduling paradigm where the rate or type of compression is dynamically adjusted during training based on real-time performance feedback.

• Feedback Signals: Uses metrics like validation loss, gradient norms, or layer-wise sensitivity to decide the next compression step.
• Application in Regrowth: An adaptive scheduler might increase the regrowth rate if accuracy plateaus or steer regrowth towards layers where gradients are most volatile.
• Goal: To create a responsive compression lifecycle that minimizes disruptive accuracy drops.

The use of search algorithms to discover novel, efficient network architectures that are inherently small and fast, often viewed as a form of compression-at-design-time.

• Search Space: Includes operations, connections, channel widths, and kernel sizes.
• Differentiable NAS (DNAS): A gradient-based method that formulates the search for a sub-network as a continuous optimization problem, highly relevant for finding efficient sparse structures.
• Hardware-Aware NAS (HW-NAS): Incorporates target hardware metrics (latency, energy) directly into the search, ensuring discovered architectures are optimal for specific deployment chips.