SiGeo: Sub-One-Shot NAS via Information Theory and Geometry of Loss Landscape

Hua Zheng, Kuang-Hung Liu, Igor Fedorov, Xin Zhang, Wen-Yen Chen, Wei WenSubmission to ICLR 2024 · Rejected

TL;DR

One-shot Neural Architecture Search (NAS) requires expensive supernet training, while zero-shot proxies struggle to capitalize on partial training and falter on complex, heterogeneous domains like recommendation systems (RecSys). This paper introduces sub-one-shot NAS, a middle ground that lightly warms up a supernet on a tiny fraction of data (1–10%), paired with SiGeo, a proxy derived from information theory and loss landscape geometry. SiGeo matches the accuracy of full one-shot methods on RecSys and vision benchmarks while cutting computational costs by roughly 60%.

What Problem Does This Paper Address?

Designing optimal neural architectures manually is tedious, making automated Neural Architecture Search (NAS) attractive. However, existing paradigms suffer from an efficiency-accuracy trade-off:

  • One-shot NAS trains an enormous weight-sharing "supernet," which is computationally demanding and prone to optimization interference among sub-architectures.
  • Zero-shot NAS ranks architectures without training using heuristic proxies (e.g., gradient variance, linear regions). Yet, these proxies cannot exploit the information gained if a network is partially trained, and they degrade significantly on heterogeneous architectures like RecSys (which mix multi-modal inputs, attention, gating, and dot products).

The authors bridge this divide by investigating how minimal training ("warm-up") alters the loss landscape, proposing a principled proxy capable of operating across zero-shot and warm-up regimes.

Methods

  • Sub-One-Shot Paradigm: Instead of training a supernet to completion (one-shot) or not at all (zero-shot), the supernet is warmed up on a fraction of data (e.g., 1–10%) to push weights out of saddle points and into a local basin of attraction.
  • Theoretical Formulation of Test Loss: Expected test loss is decomposed into excess risk, generalization error, and achievable empirical training loss:
  • Generalization Error: Measured via loss landscape flatness, approximated by gradient variance across mini-batches ($\sigma_k$).
  • Achievable Training Loss: Lower-bounded via Taylor expansion around the local minimum, revealing a dependency on the Fisher-Rao (FR) norm ($\theta^\top F \theta$), the mean gradient magnitude ($\mu_k$), and the current training loss ($\ell$).
  • The SiGeo Proxy: Combining these components yields the multi-term scoring function: $$\text{SiGeo} = \sum_{m=1}^{M} \lambda_1 \log \left( \left\| \mu_k^{(m)} \oslash \sigma_k^{(m)} \right\|_1 \right) + \lambda_2 \log \left( \theta_k^\top \hat{F}(\theta_k) \theta_k \right) - \lambda_3 \ell(\theta_k; \mathcal{D}_k)$$ Where the first term captures layer-wise signal-to-noise ratio of gradients (generalizing ZiCo), the second captures the Fisher-Rao norm (using the empirical Fisher information matrix), and the third accounts for current batch loss.

  • Compute Efficiency: SiGeo requires only $k = 4$ mini-batches to estimate gradients and the empirical Fisher matrix product.

Datasets

  • Recommendation Systems (CTR Prediction): Criteo, Avazu, and KDD Cup 2012 evaluated on the NASRec search spaces (NASRec-Small and NASRec-Full).
  • Computer Vision NAS Benchmarks: NAS-Bench-101, NAS-Bench-201 (evaluated on CIFAR-10, CIFAR-100, ImageNet16-120), and NAS-Bench-301 (DARTS space).
  • Vision Model Search: CIFAR-10 and CIFAR-100 in a 1M parameter budget search space.
  • Synthetic/Empirical Validation: MNIST trained on two-layer MLPs with varying hidden widths to validate theoretical bounds.

Key Insights and Ideas

  • Why Pure Zero-Shot Proxies Plateau: Existing gradient-dispersion proxies (like ZiCo) rely strictly on gradient variance. As networks warm up, the correlation between gradient variance and final accuracy plateaus; in contrast, the Fisher-Rao norm and training loss become dramatically better predictors of final performance.
  • Warm-Up Validates Curvature Approximations: Lightly warming up the supernet allows parameters to escape non-convex saddle points into local convex basins, satisfying theoretical regularity assumptions where quadratic Hessian/Fisher approximations hold.
  • Unification of Proxy Paradigms: Setting $\lambda_2 = \lambda_3 = 0$ reduces SiGeo to the zero-shot proxy ZiCo; fully training and evaluating subnets on validation loss makes it equivalent to standard one-shot NAS.

Key Results

  • RecSys Benchmarks: With just a 1% warm-up, SiGeo achieves CTR log loss matching or beating full one-shot methods (e.g., Criteo log loss of 0.4396 vs. NASRecNet's 0.4395; KDD 2012 log loss of 0.1484 vs. 0.1487), while reducing search time from ~0.3–0.75 GPU days down to ~0.1–0.12 GPU days (~60% reduction).
  • Ranking Correlation Under Warm-Up: On NAS-Bench-201 (CIFAR-100), increasing warm-up from 0% to 40% improves SiGeo’s Spearman rank correlation from 0.82 to 0.88, whereas ZiCo remains flat (0.78 to 0.80).
  • Zero-Shot Vision Performance: Even with 0% warm-up, SiGeo matches or slightly outperforms prior zero-cost proxies, reaching 97.01% top-1 accuracy on CIFAR-10 and 81.19% on CIFAR-100 under a 1M parameter budget.

Limitations and Future Work

  • Hyperparameter Sensitivity: The weighting factors ($\lambda_2, \lambda_3$) differ across domains. For instance, $\lambda_2$ must be set to 50 for computer vision models due to differing gradient scale dynamics compared to RecSys ($\lambda_2 = 1$).
  • Warm-Up Thresholds: Performance gains from the Fisher-Rao norm saturate beyond 20–40% warm-up, meaning practitioners must calibrate how much warm-up is necessary without wasting compute.
  • Theoretical Assumptions: The analysis assumes local convexity and realizability (the true data distribution falls within the model class), which deep neural networks only approximate locally.

Summary updated

Abstract

Neural Architecture Search (NAS) has become a widely used tool for automating neural network design. While one-shot NAS methods have successfully reduced computational requirements, they often require extensive training. On the other hand, zero-shot NAS utilizes training-free proxies to evaluate a candidate architecture's test performance but has two limitations: (1) difficulty in taking advantage of strictly increasing information and (2) unreliable performance, particularly in complex domains like recommendation systems, due to the multi-modal data inputs and complex architecture configurations. To synthesize the benefits of both methods, we introduce a "sub-one-shot" paradigm that serves as a bridge between zero-shot and one-shot NAS. In sub-one-shot NAS, the supernet is trained using only a small subset of the training data, a phase we refer to as "warm-up." Within this framework, we present SiGeo, a proxy for NAS, founded on a novel theoretical framework that connects the supernet warm-up with the efficacy of the proxy. Extensive experiments have demonstrated that SiGeo, even without the benefit of supernet warm-up, consistently outperforms state-of-the-art zero-shot NAS competitors on various established NAS benchmarks. When warmed up, it can achieve comparable performance to one-shot NAS methods, but with a significant reduction ($\sim 60$\%) in computational costs.
BibTeX
@misc{zheng2023sigeo,
  author = {Hua Zheng and Kuang-Hung Liu and Igor Fedorov and Xin Zhang and Wen-Yen Chen and Wei Wen},
  title = {{SiGeo: Sub-One-Shot NAS via Information Theory and Geometry of Loss Landscape}},
  year = {2023},
  eprint = {2311.13169},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.13169},
}
Figure