Neural Architecture Search (NAS) promises to automate the design of deep learning models, replacing human intuition with optimization algorithms. Among the various flavors of NAS, one-shot and differentiable methods (such as DARTS) are highly popular due to their efficiency. Instead of training thousands of candidate networks from scratch, these methods train a single, over-parameterized supernet (or super-graph) containing all possible operations (e.g., various convolutions, pooling, identity mappings) as parallel paths. Once the supernet is trained, the algorithm selects the best-performing paths to form the final discrete architecture.
However, this weight-sharing paradigm introduces a fundamental flaw: weight coupling and interference. Because the same weights are shared across millions of competing architectural paths, they suffer from a "tragedy of the commons." A weight configuration that benefits one path might degrade another, preventing any single architecture from reaching its true potential.
To solve this, a powerful paradigm has emerged: Progressive Search Space Pruning. Instead of keeping the entire search space active until the end of training, these methods dynamically eliminate underperforming operations during the supernet training phase.
The Core Intuition: Specialization Through Elimination
To understand why progressive pruning works, imagine trying to train an elite decathlete. If you force them to practice all ten sports equally every day, they may never achieve world-class performance in any single event due to fatigue and conflicting physical demands. However, if you notice early on that they are fundamentally unsuited for the pole vault and high jump, permanently dropping those events allows them to focus their energy and specialize in the remaining disciplines.
In a weight-sharing supernet, keeping unpromising operations active introduces massive optimization noise. As Xin Xia et al. observe, iteratively reducing the complexity of the search space minimizes the interference between competing operations sharing weights within the supernet.
When you permanently discard a poor operation mid-stream:
- Shared weights can specialize: The remaining network weights no longer have to compromise their values to accommodate suboptimal paths. As noted by Xiang Li et al., narrowing the active paths forces the shared weights to specialize in high-potential candidates rather than attempting to represent the entire initial search space.
- An efficiency feedback loop is created: Dropping operations reduces the computational overhead of the search phase itself. Asaf Noy demonstrates in ASAP: Architecture Search, Anneal and Prune that progressively removing underperforming operations accelerates the discovery of optimal structures, allowing high-performance models to be found in a fraction of the time.
How to Spot a Dead End: Pruning Metrics
The central challenge of progressive pruning is determining when and which operations to eliminate without accidentally discarding a path that would perform well later. Researchers have developed several distinct proxies to measure candidate importance during training.
1. Probability and Selection Likelihood
The most straightforward approach treats the search space as a probability distribution. Operations that consistently receive low selection probabilities or architectural weights are pruned.
- Chenyi Yang et al. treat the search space as a probability distribution and dynamically prune low-performing operations based on distribution updates.
- Hanlin Chen et al. iteratively remove operations based on their selection likelihood, concentrating computational resources on the most promising candidates.
- Lunchen Xie et al. utilize a "sparsemax" function combined with an annealing strategy to assign absolute zero probabilities to poor operations, effectively dropping them from the optimization landscape.
2. Weight Dynamics and Information Theory
Relying solely on architectural parameters can be deceptive, as trivial operations (like skip connections) often learn faster than complex convolutions, leading to a premature "performance collapse." To circumvent this, some methods look directly at weight geometry or information content.
- Yiming Hu et al. propose using the angular change of weights as a proxy for model quality. If an operator's weight vectors stabilize or change minimally, it indicates low contribution, allowing the algorithm to prune it based on this stability metric.
- Hongyi He et al. leverage Fisher Information to precisely measure candidate importance. By progressively removing operations with low Fisher Information, they prevent the sudden performance drops typically seen when jumping directly from a dense supernet to a sparse architecture.
3. Interaction and Synergy Scores
Operations do not exist in isolation; their performance depends heavily on the layers surrounding them.
- B Zhang et al. introduce a dependency-aware approach that models inter-edge relationships using a learnable correlation matrix. Pruning is guided by an interaction score, removing operations that exhibit poor synergy with other components and ensuring the remaining sub-networks are highly cohesive.
Closing the Generalization Gap
A notorious issue in standard differentiable NAS is the relaxation bias (or generalization gap). During the search phase, the supernet evaluates operations in a continuous, blended mixture. But during evaluation, the architecture is abruptly discretized into standalone paths. An operation that thrived when supported by parallel paths might fail completely on its own.
Progressive pruning bridges this gap by turning a harsh, single-step discretization into a gradual transition.
Standard NAS: [ Dense Supernet Training ] -------------------------> [ Sudden Discretization ]
Progressive NAS: [ Dense Supernet ] -> [ Prune Bad ] -> [ Prune More ] -> [ Smooth Final Selection ]
Niv Nayman et al. show that early elimination reduces the discrepancy between the continuous search space and the final discrete architecture. By progressively shrinking the super-graph during training, the network weights gradually adapt to the structural changes.
Taking this to its logical conclusion, Guohao Li et al. introduce a sequential greedy strategy (SGAS). As soon as the choice for a specific edge or layer is determined to be optimal, all other competing candidate operations for that edge are immediately pruned. This sequential alignment ensures that the validation performance observed during the search phase accurately reflects the true generalization capability of the final standalone model.
Key Foundational Work
XNAS: Neural Architecture Search with Expert Advice (2019) — contributed 2 concept elements to this direction.
Dynamic Distribution Pruning for Efficient Network Architecture Search (2019) — contributed 1 concept elements to this direction.
Reducing The Search Space For Hyperparameter Optimization Using Group Sparsity (2019) — contributed 1 concept elements to this direction.