Abstract
Neural Architecture Search (NAS) is a popular method for automatically designing optimized architectures for high-performance deep learning. In this approach, it is common to use bilevel optimization where one optimizes the model weights over the training data (inner problem) and various hyperparameters such as the configuration of the architecture over the validation data (outer problem). This paper explores the statistical aspects of such problems with train-validation splits. In practice, the inner problem is often overparameterized and can easily achieve zero loss. Thus, a-priori it seems impossible to distinguish the right hyperparameters based on training loss alone which motivates a better understanding of the role of train-validation split. This work establishes that refined properties of the validation loss such as risk and hyper-gradients are indicative of those of the true test loss, revealing that the outer problem helps select the most generalizable model and prevent overfitting with a near-minimal validation sample size.
The Challenge of Overparameterization in NAS
Modern deep learning architectures are frequently designed using Neural Architecture Search (NAS), which typically follows a bilevel optimization strategy. The lower-level objective optimizes model weights on a training set, while the upper-level objective optimizes the architecture itself on a validation set.
However, modern networks are often "overparameterized," meaning they possess enough capacity to achieve zero training error across a wide variety of architectural configurations. If the training loss is uniformly zero, it becomes impossible to distinguish between a high-performing architecture and one that simply memorizes the training data. While practitioners have long used train-validation splits to mitigate this, the theoretical justification for why this works in the overparameterized regime has been lacking.
Theoretical Framework and Methods
The authors provide a rigorous analysis using several key theoretical tools:
- Uniform Convergence and Effective Dimension: They prove that validation loss and its hyper-gradients closely track the true test loss. Crucially, they show that the required validation sample size ($n_V$) depends on the "effective dimension" of the hyperparameter space ($h$), rather than the total number of model parameters ($p$).
- Neural Tangent Kernel (NTK) Analysis: By applying the NTK framework, the search phase of NAS is modeled as finding an optimal kernel or feature map. This allows for a precise analysis of gradient descent dynamics in both shallow and deep architectures.
- Spectral Methods for Algorithmic Efficiency: The paper connects NAS to low-rank matrix learning, proposing a spectral estimator that can efficiently identify near-optimal hyperparameters even when the model is capable of overfitting every training configuration.
Key Insights: Why Validation Works
The central finding is that validation loss serves as a robust "safety net." While training loss collapses to zero in overparameterized regimes, the validation loss remains a reliable proxy for generalization. The paper establishes that a validation set size $n_V \gtrsim h$ is sufficient to prevent overfitting at the architectural level.
Furthermore, the authors demonstrate that NAS can be viewed as a form of Kernel Selection, bridging the gap between modern automated design and classical Multiple Kernel Learning (MKL). They also prove that "hyper-gradients"—the gradients used to update the architecture—concentrate around their expected values, justifying the success of gradient-based methods like DARTS.
Empirical Validation and Results
The theoretical results are supported by experiments on CIFAR-10 and MNIST:
- DARTS Search Phase: In experiments with the Differentiable Architecture Search (DARTS) supernet on CIFAR-10, the authors observed that training error drops to zero rapidly. However, the validation error remains non-zero and tracks the test error closely once the validation set size reaches a threshold comparable to the number of architectural parameters (~250).
- Activation Search: On MNIST, the authors verified the Lipschitz stability of trained networks under perturbations of activation functions, confirming a key assumption in their theoretical derivations.
Conclusion
This work provides the first end-to-end generalization guarantees for NAS with train-validation splits. It confirms that the bilevel procedure effectively returns architectures with near-minimal risk, even when the underlying models are expressive enough to fit any training data perfectly. While currently focused on the NTK regime, this framework lays the groundwork for understanding generalization in more complex meta-learning and hyperparameter optimization scenarios.
Summary updated