Neural Architecture Search (NAS) is often described as finding a needle in a haystack. However, the "haystack" of potential network configurations is not just large—it is exponentially explosive. Searching for a complex, high-performing cell from scratch requires evaluating thousands of candidates, most of which are poorly structured and provide little signal for optimization.
To solve this, researchers have converged on a strategy of progressive growth. Instead of tackling the full search space at once, these methods start with simple, shallow, or restricted architectures and incrementally increase complexity. This approach transforms a massive combinatorial problem into a sequence of manageable steps, ensuring that the search process remains computationally feasible while bridging the gap between small-scale proxies and large-scale deployments.
The Efficiency of Incremental Complexity
The foundational intuition behind progressive search is that complex architectures are often composed of simpler, high-performing motifs. Progressive Neural Architecture Search (PNAS), proposed by Chenxi Liu, Barret Zoph, and colleagues, formalizes this by searching for cells in order of increasing complexity.
In PNAS, the system starts by evaluating all possible 1-block cells. It then uses a "surrogate model" to predict which 2-block expansions of those cells will perform best, evaluating only the top candidates. By the time the search reaches 5-block cells, it has already pruned away the vast majority of the search space based on evidence from simpler structures. This sequential approach allows PNAS to achieve state-of-the-art results while being up to 8 times faster than reinforcement learning methods that attempt to sample full-sized cells immediately.
Bridging the Depth Gap
A recurring problem in NAS is the "depth gap": to save time, researchers often search for architectures using shallow networks (e.g., 8 layers) but deploy them using much deeper ones (e.g., 20 layers). Unfortunately, an operation that works well in a shallow network—where gradients flow easily—might be suboptimal in a deep network where signal attenuation is a greater concern.
Progressive Differentiable Architecture Search (P-DARTS), developed by Lingxi Xie, Xin Chen, and Jun Wu, addresses this by gradually increasing the depth of the search network during the optimization process. As the network grows deeper, the search space is simultaneously pruned, removing operations that fail to handle the changing gradient dynamics. This ensures that the final discovered architecture is "native" to the target depth, leading to better performance on large-scale tasks like ImageNet.
Curriculum Search and Space Explosion
Even when the structure is fixed, the variety of possible operations (convolutions, pooling, dilations) can overwhelm a search controller. Yaofo Chen and colleagues introduced Curriculum Neural Architecture Search (CNAS) to solve this "space explosion."
CNAS treats the search space itself as a curriculum. It begins by searching a tiny space with only one or two basic operations. Once the controller learns the optimal topology for those simple choices, the algorithm introduces more complex operations. This staged approach provides a smoother learning curve, allowing the searcher to refine its knowledge of connectivity patterns before being forced to choose between subtle variations of sophisticated operators.
Beyond Standard Classification
The progressive philosophy has proven versatile across diverse domains:
- Hardware-Aware Search: PPP-Net by Jin-Dong Dong and Min Sun uses progressive expansion to find Pareto-optimal architectures that balance accuracy with real-world hardware constraints like inference time.
- Graph Networks: ARGNP by Liang Li uses "network proliferation" to iteratively divide and differentiate nodes, breaking the memory bottlenecks that typically prevent the search for deep Graph Neural Networks.
- Generative Models: AutoGAN by Shiyu Chang and Zhangyang Wang employs a multi-level search strategy to stabilize the notoriously difficult task of searching for GAN architectures, building the generator from the bottom up.
- Symbolic Regression: Even in mathematical discovery, EQL-Z by Sannyuya Liu uses a small-to-large structure search to prevent the discovery of overly complex, redundant equations, ensuring that new mathematical terms are only added if they significantly improve the fit.
By starting small and growing with intent, progressive search methods avoid the pitfalls of "cold-starting" a search in a massive space, leading to architectures that are both more efficient to find and more robust in practice.