Neural Architecture Search Part 4: Efficient Estimation Strategies

One of the biggest challenges in Neural Architecture Search is cost: evaluating thousands of candidate architectures by training them all from scratch takes months on supercomputers. In Part 3, we learned about the real-world impact of NAS, but we glossed over a critical question: how do we actually afford to run NAS?

In this part, we’ll explore the efficiency problem and discover clever techniques that dramatically reduce the computational cost of architecture search—techniques that make NAS accessible rather than a luxury only major tech companies can afford.

The Cost Problem

Let’s start with concrete numbers. The original NAS paper by Zoph et al. (2017) trained 12,800 model architectures on CIFAR-10. This took 22,400 GPU hours—roughly 5 years on a single GPU.

For ImageNet, the computational cost explodes. Early DARTS-style approaches required up to 100GB of GPU memory, which only the most powerful accelerators could handle.

This created a fundamental barrier: only well-funded organizations could run NAS effectively.

The Core Problem: Training Cost

Every architecture search method has the same bottleneck:

1. Sample or construct a candidate architecture
2. Train it (or partially train it) on the target task
3. Evaluate its accuracy
4. Use results to guide the search
5. Repeat steps 1-4 thousands of times

Step 2—training—dominates the cost. Training a neural network from scratch requires hundreds or thousands of gradient updates.

Why Full Training?

In principle, we need to train architectures completely to get accurate accuracy estimates. A partially trained model might perform differently than a fully trained one:

• Early training performance correlates with final accuracy, but imperfectly
• Some architectures train slower initially but reach higher accuracy eventually
• The relationship between early and final accuracy varies across architectures

So the naive question becomes: can we estimate accuracy without full training?

Accuracy Estimation Strategy 1: Train from Scratch

Let’s start with the baseline: the straightforward approach that doesn’t try to save cost.

Process:

1. Train the given model from scratch on the training set
2. Evaluate on validation set to get accuracy
3. Use this accuracy to guide the search

Cost: Prohibitively expensive (22,400 GPU hours for small CIFAR-10)

Accuracy: Perfect—we know the true validation accuracy

The trade-off is clear: maximum accuracy information at maximum cost.

Accuracy Estimation Strategy 2: Weight Inheritance

Rather than training from scratch, can we reuse weights from previously trained models?

The insight: if we’ve already trained one architecture, maybe a similar architecture can inherit its weights rather than starting random.

Net2Net: Network Transformation

Net2Net introduced the concept of network transformation: start with a trained network and carefully expand it.

Two key transformations:

Net2Wider: Add more channels to existing layers

• The new channels are initialized with the same weights as existing channels
• This preserves the learned representations while increasing capacity
• Reuses computation from the parent network

Net2Deeper: Add new layers

• New layers are initialized as identity mappings
• Ensures the expanded network can at least match the parent’s performance
• Allows the search to explore deeper architectures efficiently

The Inheritance Advantage

By inheriting weights, we dramatically reduce training time:

• Parent model already learned useful representations
• Child network starts at parent’s accuracy level
• Fine-tuning needs far fewer epochs than training from scratch
• Some architectures may never need adjustment if they’re very similar to the parent

Cost: Minutes to hours instead of days per architecture

Tradeoff: Slight bias toward architectures similar to the parent model

Accuracy Estimation Strategy 3: One-Shot Models and Hypernetworks

What if, instead of training thousands of separate models, we trained one large super-network that contains all possible architectures?

SMASH: Super-Network with Hypernetworks

SMASH (Stochastic Micro Architectures Search via HyperNetworks) introduced an elegant idea:

The Approach:

1. Build an over-parameterized network containing all possible operations
2. Use a hypernetwork that generates weights for the architecture
3. At each training step, sample a random architecture from the search space
4. The hypernetwork generates the specific weights for that architecture
5. Train the hypernetwork using gradient descent
6. The hypernetwork learns to generate good weights for any architecture

Key Innovation: Rather than training architectures sequentially, we train a single super-network that learns to weight-share across all architectures.

Training Efficiency

Cost: Single training pass through the super-network (hours instead of thousands of GPU-days)

How it works:

• During training, different random architectures are sampled
• The hypernetwork generates weights adapted to each architecture
• All architectures share weights through the hypernetwork
• The hypernetwork learns correlations between architectures

Tradeoff: Accuracy ranking might differ from full training, but correlations are typically strong

Accuracy Estimation Strategy 4: Weight Sharing Super-Networks

Building on hypernetwork ideas, researchers developed weight-sharing super-networks: one massive network where all possible architectures are sub-networks.

The Super-Network Concept

Imagine a network so large that it contains every architecture in the search space as a sub-network:

┌─────────────────────────────────────────┐
│   Super-Network (Over-Parameterized)    │
├─────────────────────────────────────────┤
│                                         │
│  Path 1:  Conv3x3 → Conv1x1 → MaxPool  │
│  Path 2:  Conv5x5 → Conv3x3 → AvgPool  │
│  Path 3:  DwConv → Conv1x1 → SepConv   │
│  ...                                    │
│  Path N:  [Any combination of ops]      │
│                                         │
└─────────────────────────────────────────┘

Key idea: Instead of operations being binary choices (use or don’t use), we train all operations in parallel and let weights determine importance.

Training and Evaluation

Training:

1. Build the super-network with all possible operations
2. For each mini-batch, sample one or more random architectures
3. Run forward/backward pass for sampled architectures
4. Update only the weights used by sampled architectures
5. Repeat until convergence

Evaluation:

1. For a candidate architecture, run inference through the super-network
2. Use only the weights corresponding to that architecture
3. Get accuracy without any training—just reuse super-network weights

Cost: One training pass (typically 1-5 GPU days for ImageNet) then instant evaluation

Speedup: 1000-10000× compared to training from scratch

Accuracy Estimation Strategy 5: From Proxy Tasks to Direct Search

Early NAS methods couldn’t run on target tasks like ImageNet directly, so they used proxy tasks as substitutes:

• Search on CIFAR-10 instead of ImageNet
• Use smaller architecture spaces
• Train for fewer epochs
• Estimate latency from MACs instead of actual measurements

The problem: architectures optimal for CIFAR-10 might be suboptimal for ImageNet. Proxy tasks introduce systematic bias.

ProxylessNAS: Direct Search on Target Task and Hardware

ProxylessNAS (Cai et al., ICLR 2019) solved this by running search directly on target tasks and hardware without proxies.

The Innovation:

1. Build an over-parameterized network containing all possible operations
2. Memory efficiency: Rather than keeping all paths active, binarize architecture parameters—each operation is either used or not
3. Memory footprint: Reduces from O(N) to O(1), where N is the number of paths

This clever trick enables direct search on large datasets like ImageNet with memory constraints.

ProxylessNAS Results

By eliminating proxy tasks, ProxylessNAS discovers architectures truly optimized for target conditions:

• CIFAR-10: Achieves 97.3% accuracy with efficient architecture
• ImageNet: Discovers FairDARTS architecture with better latency-accuracy tradeoff
• Mobile inference: Specialized architectures for specific hardware constraints

From Theory to Hardware Reality

Here’s a critical insight: MACs (multiply-accumulate operations) don’t perfectly predict real hardware efficiency.

Two networks with identical MACs can have vastly different latencies:

• Memory access patterns affect bandwidth utilization
• Cache efficiency varies by architecture
• Kernel implementations have different performance
• Parallelization potential differs

This is why hardware-aware NAS—actually measuring latency on target devices—became critical.

The Practical Workflow

Putting together all these efficiency techniques, a modern NAS system looks like:

1. Build super-network with weight sharing containing all possible architectures
2. Train once on target task (using direct search, not proxy tasks)
3. Measure actual latency on target hardware (not estimated from MACs)
4. Architecture parameters guide search through gradient descent or evolutionary methods
5. Instant evaluation reuses super-network weights—no additional training
6. Fine-tune top candidates from scratch for final validation (optional, but recommended)

Total cost: Days to weeks on a single GPU, compared to months on thousands of GPUs for naive approaches.

Key Takeaways

The journey from training-from-scratch to efficient estimation shows how research removes barriers:

1. Weight inheritance (Net2Net): Reuse trained models → 10-100× speedup
2. Weight sharing (SMASH, one-shot): Train once, evaluate instantly → 100-1000× speedup
3. Direct search (ProxylessNAS): Search on real tasks and hardware → better results
4. Binarization: Reduce memory from O(N) to O(1) → enable large-scale search

These techniques stack, enabling NAS to move from research luxury to practical tool accessible to smaller organizations and research labs.

In Part 5, we’ll explore the latest frontier: hardware-aware NAS and co-design, where architecture and hardware co-evolve.

---

Series Navigation:

• Part 1: Foundations and Building Blocks
• Part 2: Search Spaces and Strategies
• Part 3: Applications and Real-World Impact
• Part 4: Efficient Estimation Strategies (this post)
• Part 5: Hardware-Aware NAS and Co-Design

---

References:

• MIT 6.5940: TinyML and Efficient Deep Learning - Lecture 8: Neural Architecture Search Part II (Fall 2024)
• Neural Architecture Search with Reinforcement Learning (Zoph & Le, ICLR 2017) - Original NAS, demonstrates cost challenge
• Net2Net: Accelerating Learning via Knowledge Transfer (Chen et al., ICLR 2016) - Network transformation for weight inheritance
• SMASH: One-Shot Model Architecture Search through HyperNetworks (Brock et al., ICLR 2018) - Hypernetwork weight generation
• ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware (Cai et al., ICLR 2019) - Direct search without proxies
• Efficient Neural Architecture Search via Parameter Sharing (Pham et al., ICML 2018) - Weight sharing super-networks