Search Strategy (NAS)

In Reinforcement Learning NAS (RL-NAS), a controller network (typically an RNN or Transformer) is trained via policy gradient methods to generate candidate architecture descriptions. The controller's actions (e.g., selecting layer types, filter sizes) are rewarded based on the validation accuracy of the child network after training. This creates a feedback loop where the controller learns to propose better architectures over time.

• Key Mechanism: The search is framed as a sequential decision-making process.
• Classic Example: NASNet used an LSTM controller to generate convolutional cell structures for image classification.
• Pros: Can discover highly novel, high-performing architectures.
• Cons: Extremely computationally expensive, often requiring thousands of GPU days for the initial pioneering works.

Evolutionary NAS treats architecture discovery as a population-based optimization problem. A population of candidate architectures is maintained and iteratively improved through biologically inspired operations.

• Core Operations:
  • Mutation: Randomly alters an architecture (e.g., change an operation, add/remove a connection).
  • Crossover (Recombination): Combines parts of two parent architectures to create an offspring.
  • Selection: The least fit architectures (by accuracy, latency, etc.) are culled from the population.
• Fitness Evaluation: Each candidate is trained (often partially) and evaluated to assign a fitness score.
• Advantage: Naturally suited for multi-objective optimization, easily finding architectures on the Pareto frontier of accuracy vs. efficiency.
• Example: AmoebaNet achieved state-of-the-art results using regularized evolution.

Gradient-Based NAS, exemplified by Differentiable Architecture Search (DARTS), formulates the search as a continuous optimization problem. It constructs a supernet where every possible architectural choice is represented as a mixture of operations with continuous architecture parameters (alpha weights).

• Process: The supernet weights and the alpha parameters are optimized jointly via gradient descent on the training data. After search, a discrete architecture is derived by selecting the operation with the highest alpha weight at each choice point.
• Key Benefit: Dramatically faster search (order of days vs. thousands of GPU days) by leveraging efficient backpropagation.
• Major Drawback: High memory consumption due to the supernet, and potential performance discrepancy between the continuous relaxation and the final discretized network.
• Hardware-Aware Extension: ProxylessNAS extends this by incorporating hardware latency, measured directly on target devices, into the gradient-based loss.

One-Shot NAS is a family of methods that decouples architecture search from architecture evaluation using a central technique: weight sharing. A single, over-parameterized supernet is trained once. All candidate sub-architectures inherit their weights from this shared supernet, allowing their performance to be estimated without costly independent training.

• Search Phase: After supernet training, a search algorithm (e.g., evolutionary, random) samples sub-architectures and evaluates them using the shared weights, often in minutes.
• Final Training: The top-performing candidate is then retrained from scratch for final deployment.
• Efficiency: This approach reduces search cost by several orders of magnitude.
• Paradigm Example: Once-For-All (OFA) trains a single supernet that can dynamically shrink in depth, width, and kernel size to produce numerous hardware-tailored sub-networks without retraining.

Bayesian Optimization (BO) is a sample-efficient global optimization strategy well-suited for expensive black-box functions—like training a neural network. In NAS, BO builds a probabilistic surrogate model (e.g., a Gaussian Process) to predict the performance of unseen architectures based on previously evaluated ones.

• Acquisition Function: Guides the search by balancing exploration (trying architectures in uncertain regions) and exploitation (refining around current best candidates). Common functions include Expected Improvement (EI) and Upper Confidence Bound (UCB).
• Search Loop:
  1. Use the surrogate model to predict performance across the search space.
  2. Select the most promising candidate via the acquisition function.
  3. Evaluate it (train it) to get ground-truth performance.
  4. Update the surrogate model with the new data point.
• Use Case: Particularly effective when the search space can be encoded with meaningful, continuous descriptors and the total number of evaluations must be very low (e.g., <100).

This category encompasses the simplest and most efficient strategies, crucial for constrained environments like TinyML.

• Random Search: Serves as a surprisingly strong baseline. By uniformly sampling architectures from a well-designed search space, it often outperforms more complex, poorly tuned search algorithms. Its efficiency allows for extensive exploration within a fixed compute budget.
• Zero-Cost Proxies: A class of ultra-efficient metrics that predict a network's final trained performance using only its initial, untrained state. They require a single forward/backward pass (or less) and no training.
  • Examples: grad_norm (magnitude of gradients), snip (sensitivity of loss to parameter pruning), synflow (preservation of signal flow).
  • Application in NAS: Used to pre-filter thousands of candidates in seconds, ranking them to guide a subsequent search (e.g., evolutionary) or to select top architectures directly, enabling NAS in minutes on a single GPU.

A search strategy where a controller network, trained via reinforcement learning, sequentially generates candidate architectures. The controller receives a reward based on the trained candidate's performance (e.g., accuracy, latency), guiding it to produce better designs over time.

• Key Mechanism: Uses policy gradient methods (e.g., REINFORCE) to update the controller.
• Pioneering Example: Zoph & Le (2017) used an RNN controller to discover convolutional cells for image classification.
• Trade-off: Can discover high-performing architectures but is often computationally expensive due to the need to train each candidate to convergence for reward evaluation.

A search strategy inspired by biological evolution. It maintains a population of candidate architectures, which are iteratively improved through mutation (random alterations) and crossover (combining parts of two parents).

• Selection Pressure: Poor-performing architectures are culled from the population.
• Advantage: Highly parallelizable and effective at exploring complex, non-differentiable search spaces.
• Example: Real et al. (2019) used regularized evolution to discover AmoebaNet, which achieved state-of-the-art ImageNet accuracy.
• Hardware-Aware Use: Easily adapted for multi-objective search by incorporating hardware metrics (latency, energy) into the fitness function.

A strategy that relaxes the discrete architecture search space into a continuous, differentiable one. Architecture parameters (e.g., the weight of choosing between a 3x3 conv or a 5x5 conv) are optimized alongside network weights via gradient descent.

• Core Method: Differentiable Architecture Search (DARTS) uses a continuous relaxation of operations, enabling efficient search on a single GPU in a few days.
• Efficiency: Avoids training thousands of discrete models from scratch by leveraging weight sharing in a supernet.
• Limitation: The continuous relaxation can lead to a discrepancy between the searched continuous architecture and the final discrete one, sometimes resulting in performance degradation.

A family of methods that decouples architecture search from architecture evaluation by training a single, weight-shared supernet once. Candidate architectures are evaluated as sub-networks of this supernet without needing retraining.

• Weight Sharing: All candidate architectures inherit weights from the supernet, providing a cheap performance proxy.
• Search Phase: After supernet training, a separate search algorithm (e.g., evolutionary, random) samples and evaluates sub-networks using the shared weights.
• Paradigm Example: Once-For-All (OFA) trains a supernet supporting diverse depths, widths, and kernel sizes, enabling the extraction of many hardware-tailored sub-networks post-search.

A search strategy that optimizes for multiple, often competing, objectives simultaneously. For TinyML, key objectives are model accuracy, inference latency, memory footprint, and energy consumption.

• Pareto Optimality: The goal is to find architectures on the Pareto frontier, where improving one objective worsens another.
• Implementation: Can be integrated into RL (multi-term reward), evolutionary (multi-objective fitness), or gradient-based frameworks.
• Critical for Deployment: Essential for Hardware-Aware NAS, ensuring discovered models are not just accurate but also feasible for deployment on specific microcontrollers.

Ultra-low-cost metrics used to estimate the potential performance of a neural architecture without any training. They analyze properties of the network at initialization to predict final trained accuracy or hardware efficiency.

• Purpose: Dramatically accelerate the initial phase of NAS by pruning the search space of poor candidates.
• Common Proxies: Metrics like gradient norm, synaptic flow (SNIP), and Fisher information.
• Use Case: In a multi-stage search, zero-cost proxies can screen thousands of architectures in seconds. Promising candidates are then evaluated with more accurate (but costly) methods like one-shot evaluation or short training.