Sparse Evolutionary Training (SET)

SET begins by initializing the network with a sparse Erdős–Rényi topology, where each neuron is connected to a random, fixed number of other neurons. This creates a starting point with a pre-defined, uniform sparsity level (e.g., 90% of weights are zero), avoiding the computational cost of a dense matrix from the outset.

• Key Benefit: Immediate memory and compute savings at the start of training.
• Contrasts with traditional methods that start dense and prune later.

The core mechanism of SET is a cyclical process of removing the smallest-magnitude weights and adding new connections. After each training phase, a fraction of the lowest-magnitude weights are pruned (set to zero). An equal number of new connections are then randomly regrown, initialized to zero, to maintain a constant sparsity level.

• Evolutionary Exploration: This allows the network to explore new, potentially better pathways throughout training.
• Fixed Sparsity Enforcement: The total number of non-zero parameters remains constant, providing predictable memory footprint.

Unlike static pruning which removes connections permanently, SET allows the network's connectivity pattern to evolve. The algorithm does not assume the initial sparse random graph is optimal. Through iterative regrowth, it can discover more efficient, task-specific architectures.

• Adaptive Structure: The network can rewire itself, moving connectivity to where it is most needed for the learning objective.
• Mitigates Dead Neurons: Regrowth can reconnect neurons that became inactive due to aggressive pruning.

By enforcing sparsity throughout training and inference, SET directly reduces the model's memory footprint and FLOPs (floating-point operations). Sparse matrix operations can leverage specialized hardware and libraries for accelerated computation.

• Inference Advantage: The final trained model is inherently sparse and efficient for deployment.
• Training Efficiency: While the regrowth process adds overhead, the per-iteration cost is lower due to sparse forward/backward passes.

SET's process of iterative pruning and training aligns with the principles of the Lottery Ticket Hypothesis. It continuously searches for a high-performing sparse subnetwork (a 'winning ticket') within the larger architectural space. The regrowth phase acts as a form of exploration, testing new candidate subnetworks.

• Key Difference: SET maintains a fixed parameter count and allows topology changes, whereas classic Lottery Ticket research often finds a static subnetwork.

SET differs fundamentally from post-training pruning or one-shot pruning. Those are destructive, offline operations applied after training is complete. SET is an online, non-destructive process integrated into the training loop.

• Advantage: The network can recover from overly aggressive pruning during the same training run via regrowth.
• Disadvantage: Introduces algorithmic complexity and requires careful tuning of the pruning/regrowth rate and schedule.

SET initializes a neural network with a sparse, Erdős–Rényi random graph topology. During training, it periodically executes a drop-and-grow cycle:

• Pruning Phase: The smallest magnitude weights (e.g., bottom 20%) are removed (set to zero).
• Regrowth Phase: An equal number of new connections are randomly initialized in previously unconnected parts of the network. This cycle maintains a fixed level of sparsity (e.g., 80% of weights are zero) while allowing the network topology to evolve, searching for an optimal sparse architecture.

SET provides significant efficiency gains over traditional dense training:

• Memory & Compute Efficiency: By maintaining high sparsity, it drastically reduces the number of floating-point operations (FLOPs) and memory footprint during both forward and backward passes.
• Evolutionary Search: The regrowth mechanism performs a continuous, lightweight architecture search, allowing the network to discover critical connections that dense training might overlook.
• Scalability: Enables the training of very large models (e.g., with trillions of potential connections) on hardware that could only handle much smaller dense networks, as only active weights are stored and computed.

Implementing SET requires modifying the training loop to handle dynamic sparsity:

• Sparse Data Structures: Use Compressed Sparse Row (CSR) or similar formats to store only non-zero weights and their indices.
• Custom Optimizers: Standard optimizers like SGD or Adam must be adapted to skip updates for zeroed weights and correctly handle the newly added connections.
• Sparsity Schedule: The frequency of the drop-and-grow cycle (e.g., every 100 steps) and the fraction of weights updated are critical hyperparameters. A common implementation is available in libraries like TensorFlow Model Optimization Toolkit.

SET is empirically aligned with the Lottery Ticket Hypothesis. The hypothesis suggests dense networks contain sparse, trainable subnetworks ('winning tickets'). SET's dynamic process can be seen as a continuous search for these high-performing subnetworks. Unlike Iterative Magnitude Pruning which finds a static ticket, SET allows the 'winning ticket' to evolve throughout training, potentially discovering more robust or efficient sparse structures.

SET differs fundamentally from static pruning techniques:

• Static Pruning (e.g., Iterative Magnitude Pruning): Removes weights once, based on a final trained model. The topology is fixed after pruning.
• Dynamic SET: The network topology is fluid. Connections deemed unimportant early in training can be regrown later if they become relevant, offering more exploration and potentially better final performance for a given sparsity level. However, it introduces runtime overhead for managing sparsity changes.

The benefits of SET are fully realized only with hardware and software that accelerate sparse computations:

• Sparse Tensor Cores: Modern GPUs and NPUs (e.g., NVIDIA Ampere architecture) include hardware for accelerated sparse matrix multiplication.
• Kernel Support: Inference runtimes like TensorRT and ONNX Runtime provide optimized kernels for executing sparse models. Without this support, the sparse matrix format overhead can negate the theoretical FLOPs savings.
• The final trained SET model is a static sparse network, making it directly deployable for efficient inference on supporting hardware.