TL;DR
NASI (Neural Architecture Search at Initialization) is a novel algorithm that selects high-performing neural architectures without training a single model. By leveraging the properties of the Neural Tangent Kernel (NTK), NASI provides a theoretically grounded proxy for performance that is both label- and data-agnostic, reducing search costs from days to minutes.
The Problem: Search Inefficiency in NAS
Neural Architecture Search (NAS) aims to automate the design of deep neural networks, moving away from manual, trial-and-error engineering. However, traditional NAS is notoriously expensive because it typically requires training and evaluating thousands of candidate architectures to see which performs best.
Even "one-shot" NAS methods, which share weights across architectures, still require a significant training phase for a "super-net." This paper addresses the fundamental search inefficiency of NAS by asking a provocative question: Can we identify the best architecture at the very moment of initialization, before any training happens?
Methods: Searching via the Neural Tangent Kernel
The core of NASI is the Neural Tangent Kernel (NTK). In the limit of infinite width, the training dynamics of a neural network are governed by this kernel, which remains constant during training.
- Performance Proxy: The authors prove mathematically that the training loss of an architecture can be upper-bounded by a function of the trace norm of its NTK at initialization. Essentially, a larger trace norm correlates with better training potential and representation power.
- Efficient Approximation: Calculating the full NTK is computationally prohibitive. To solve this, the authors propose an efficient approximation using the Frobenius norm of the Jacobian matrix. This can be computed quickly via automatic differentiation on just a single mini-batch of data.
- Differentiable Search: To navigate the massive space of possible architectures, NASI utilizes a Gumbel-Softmax relaxation. This turns the discrete choice of operations (like choosing between a $3\times3$ convolution or a max pool) into a continuous optimization problem that can be solved efficiently using gradient descent.
- Complexity Trade-off: The authors introduce a penalty term and a constraint to balance model complexity with trainability. This prevents the search algorithm from simply picking the largest, most complex model, which might be difficult to optimize in practice.
Key Insights and Ideas
Training is Optional
The most profound insight of NASI is that the "DNA" of a good architecture is visible at initialization. You do not need to see a model learn to know if it can learn well.
Label- and Data-Agnosticism
Because the NTK trace norm depends on the architecture's structure rather than specific data patterns, NASI works even with random labels or random Gaussian noise as input. This means you can find a great architecture for CIFAR-10 without actually using CIFAR-10 data during the search phase.
As shown in the figures above, the performance proxy exhibits near-perfect correlation ($\rho=1.00$) when comparing true labels to random labels, and exceptionally high correlation ($\rho \approx 0.94-0.95$) when comparing true data to random data across different search spaces.
The Complexity/Trainability Balance
The paper highlights that NAS is essentially a search for a "sweet spot." Models need enough complexity to represent the data accurately but must remain structured enough to be optimized efficiently by gradient descent.
Key Results
- Massive Speedup: NASI completes its search in approximately 0.24 GPU hours (about 15 minutes) on a single Nvidia 1080Ti. For comparison, traditional RL-based NAS can take up to 48,000 hours, and even the popular DARTS method takes roughly 24 hours.
- Competitive Accuracy: Despite the extreme speedup, NASI achieves a 2.79% error rate on CIFAR-10, which is comparable to or better than many training-heavy, state-of-the-art methods.
- Strong Transferability: Architectures found by NASI on CIFAR-10 transferred successfully to ImageNet, achieving a 24.3% Top-1 error, outperforming several human-designed and automatically searched models.
Limitations and Future Work
- Infinite Width Assumption: The theoretical foundation relies on the "infinite width" regime of neural networks. While it works well in practice for finite networks, bridging the gap between this theory and practical application is an ongoing area of study.
- Loss Function Focus: The theoretical proofs are primarily derived for Mean Squared Error (MSE) loss. While the authors show it works for Cross-Entropy in practice, a more direct theoretical treatment of classification losses could be beneficial.
- Search Space Constraints: Like most NAS methods, NASI is still constrained by the predefined search space (e.g., the DARTS cell). Expanding this to more diverse or "macro" architectures remains a challenge for future research.
Summary updated