PaperlayerView exact revision on arXiv

Source-linked AI summary

Weight-Sharing Neural Architecture Search: A Battle to Shrink the Optimization Gap

Lingxi Xie, Xin Chen, Kaifeng Bi, Longhui Wei, Yuhui Xu, Zhengsu Chen, Lanfei Wang, An Xiao, Jianlong Chang, Xiaopeng Zhang, Qi Tian

arXiv:2008.01475v2cs.CVcs.LG

TL;DR

Weight-sharing makes NAS much faster by evaluating architectures through a shared super-network, but the review identifies instability tied to a gap between that network and its sub-architectures. It synthesizes approaches to shrink the gap and highlights its persistence in local architecture properties.

  • Problem

    Weight-sharing NAS can be unstable because a well-optimized super-network does not necessarily yield high-quality sub-architectures.

    Source: §1 · p. 2

  • Method

    The paper reviews weight-sharing NAS and organizes existing approaches around efforts to shrink the optimization gap.

    Source: §1 · p. 2, §3.3 · p. 9

  • Results

    The review identifies the optimization gap as weight-sharing NAS’s core challenge; in CIFAR10, a super-network near 90% training accuracy can yield a pruned sub-architecture below 20% without weight retraining.

    Source: §3.3 · p. 9, §3.2 · p. 9

  • Takeaways & Limitations

    The authors conclude that NAS has contributed to state-of-the-art computer vision algorithms but still has drawbacks that hinder broader applications.

    Source: §5 · p. 13

    Learning-based approaches approximate the accuracy distribution from few samples and may miss local properties, so the optimization gap can remain.

    Source: §3.3.5 · p. 11

Abstract

from arXiv · show

Neural architecture search (NAS) has attracted increasing attentions in both academia and industry. In the early age, researchers mostly applied individual search methods which sample and evaluate the candidate architectures separately and thus incur heavy computational overheads. To alleviate the burden, weight-sharing methods were proposed in which exponentially many architectures share weights in the same super-network, and the costly training procedure is performed only once. These methods, though being much faster, often suffer the issue of instability. This paper provides a literature review on NAS, in particular the weight-sharing methods, and points out that the major challenge comes from the optimization gap between the super-network and the sub-architectures. From this perspective, we summarize existing approaches into several categories according to their efforts in bridging the gap, and analyze both advantages and disadvantages of these methodologies. Finally, we share our opinions on the future directions of NAS and AutoML. Due to the expertise of the authors, this paper mainly focuses on the application of NAS to computer vision problems and may bias towards the work in our group.

1 INTRODUCTION

As network design grows more complex across tasks and hardware constraints, NAS offers automated architecture search. This review focuses on weight-sharing NAS, framing its instability as an optimization gap between super-networks and sub-architectures and organizing prior efforts around shrinking that gap.

1 INTRODUCTION

  • Manual network design struggles to generalize across scenarios and to explore architectures under hardware constraints, motivating automated search.NAS searches a defined space of architectures and has shown performance gains in constrained settings such as mobile ImageNet classification.Source: §1 · p. 1
  • Weight-sharing NAS reduces search costs by orders of magnitude, but individual search runs can yield very different performance because the super-network may not produce high-quality sub-architectures.The review describes this mismatch as the optimization gap and frames it as the central challenge.Source: §1 · pp. 1–2
  • The review adopts prior survey categories but combines search strategy with evaluation, then examines weight-sharing NAS through the lens of shrinking its optimization gap.It covers modern deep-learning NAS and excludes early work on finding efficient neural networks.Source: §1 · p. 2
  • The paper formalizes NAS and reviews search approaches before analyzing the optimization gap, related NAS directions, and open problems for NAS and AutoML.The authors note that their coverage mainly reflects computer vision and may be biased toward work from their group, as stated in the supplied paper context.Source: §1 · p. 2

2 NEURAL ARCHITECTURE SEARCH

The section establishes a general NAS formulation and notation, then introduces the search space and search strategy, including evaluation, as the framework’s basic elements.

2 NEURAL ARCHITECTURE SEARCH

  • The section builds a generalized NAS formulation and notation system around fundamental concepts, search spaces, and search strategies.The search strategy includes the evaluation method.Source: §2 · p. 2
  • NAS follows regular machine-learning tasks: given dataset D with N input-output pairs (x_n, y_n), it seeks a model that works best on D and transfers well to testing; subsets are Dtrain, Dval and Dtest.Source: §2.1 · p. 2

2.1 Overall Framework

  • Algorithm 1 takes a search space, training and validation data, and an evaluation method as inputs, and returns an optimal model after initializing a probability distribution over architectures.The algorithm’s stated output is the optimal model with its architecture and weights.Source: §2.1 · p. 2

2 repeat

The section describes NAS as searching a space of architectures and using a strategy to evaluate candidates and guide further sampling. Its generalized pipeline returns the best-seen model.

2 NEURAL ARCHITECTURE SEARCH

  • The generalized pipeline samples architectures, evaluates them, updates the sampling distribution, and returns the best-seen model at convergence or the time limit.The algorithm checks whether accuracy surpasses the best seen value before updating the distribution.Source: §2 · p. 2
  • NAS defines a search space of network architectures, each with weights, and seeks an architecture that performs well on the testing set.In practice, the search uses training and validation data because the test set is hidden.Source: §2 · p. 2
  • Because exhaustive search is often too costly, practical NAS uses a heuristic strategy that adjusts an architecture-sampling distribution according to sampled candidates’ rewards.Each strategy includes an evaluation method for judging candidate quality.Source: §2 · p. 2

2.2 Search Space

Search spaces define which architectures NAS can explore, balancing breadth against search difficulty. The section surveys open and fixed spaces, including widely used NAS-RL, NASNet, DARTS, and MobileNet variants.

2.2 Search Space

  • A larger search space can include more potentially powerful architectures, but makes optimization harder and generally requires more samples to characterize.Most current methods fix the macro architecture and search micro architectures, constraining flexibility.Source: §2.2 · p. 3

2.2.1 The EvoNet Search Space

  • EvoNet uses an open search space in which architectures grow through reversible actions, while hardware limits constrain network shape.The paper notes that robust strategies are still needed to explore challenging open spaces efficiently.Source: §2.2.1 · p. 3

2.2.2 The NAS-RL Search Space

  • NAS-RL combines a densely connected macro architecture with layer-level hyperparameter choices, yielding a space whose size depends on the layer options and connectivity.The search space is constructed in a macro-then-micro manner.Source: §2.2.2 · pp. 3–4

2.2.3 The NASNet Search Space

  • NASNet searches repeatable cells in a relatively shallow network, allowing the final architecture to be deeper, with two incoming connections per hidden node.Follow-up methods reduced the candidate operators or cell topology, including DARTS.Source: §2.2.3 · p. 4

2.2.4 The DARTS Search Space

  • DARTS uses a weight-sharing super-network with candidate operators on edges, allowing arbitrary prior-layer inputs during search but retaining only two per layer.Its search space has been extended by changing operator choices, edge contents, and connectivity constraints.Source: §2.2.4 · p. 4

2.2.5 The MobileNet Search Space

  • The MobileNet space searches chain-structured networks built from MobileNet cells, varying layer operators and cell options; later variants reduced the cell depth and choices.The space also permits extensions such as mixed convolutions, dense connections, and attention blocks.Source: §2.2.5 · pp. 4–5

2.2.6 Other Search Spaces

  • Other search spaces adapt NAS to tasks such as detection, segmentation, image generation, and language modeling, while arbitrarily enlarging a space may yield weak results on par with random search.The review notes that task-specific spaces can target, for example, feature fusion in detection or down- and up-sampling paths in segmentation.Source: §2.2.6 · p. 5

2.3 Search Strategy and Evaluation Method

Search strategy and evaluation are closely coupled, so the section reviews individual and weight-sharing approaches together. It covers heuristic, differentiable, and predictor-based methods, with weight-sharing identified as a mainstream direction.

2.3.1 Individual Heuristic Search Strategies

  • Individual heuristic search uses evolutionary operations or reinforcement-learning policies, but retraining each sampled architecture from scratch can make search computationally expensive.Random search is the uniform-probability baseline; it can find high-quality architectures given sufficient computation, but is less efficient than heuristic or weight-sharing search.Source: §2.3.1 · p. 6

2.3.2 Weight-Sharing Heuristic Search Strategies

  • Weight-sharing super-networks share modules across sub-architectures, accelerating search, but copied weights may not accurately predict a sub-architecture’s validation performance.The resulting optimization gap motivates fine-tuning, fairer super-network training, and graph-based search-space modeling.Source: §2.3.2 · p. 6

2.3.3 Weight-Sharing Differentiable Search Strategies

  • Differentiable search jointly optimizes network weights and architectural parameters, then discretizes the strongest operators to produce a sub-architecture.It still has an optimization gap and can fail because of gradient-approximation error; early termination and progressive optimization are among proposed remedies.Source: §2.3.3 · p. 7

2.3.4 Predictor-Based Search Methods

  • Predictor-based methods train architecture-accuracy predictors using benchmarks such as NAS-Bench-101 and NAS-Bench-201, and the review identifies weight-sharing search as a mainstream direction.The cited benchmarks contain about 423K architectures on CIFAR10 and 15,526 architectures across CIFAR10, CIFAR100, and ImageNet-16-120, respectively.Source: §2.3.4 · p. 7

2.4 Summary

The section links search-space properties to the suitability and cost of search strategies, and argues that larger, more flexible spaces make efficient and stable weight-sharing important. It also offers an end-to-end search direction and notes evaluation and reproducibility considerations.

2.4 Summary

  • Larger, more flexible search spaces make individual search computationally burdensome, motivating efficient and stabilized weight-sharing strategies.Individual heuristic methods can work well in small, tidy spaces where similar architectures have correlated performance.Source: §2.4 · p. 8
  • The authors argue that multi-stage NAS algorithms reflect instability and immaturity, and advocate end-to-end exploration of very large search spaces.They also note related work on designing search spaces and progressively removing candidate connections or operators.Source: §2.4 · p. 8
  • NAS evaluation depends on suitable benchmarks and hyperparameters, while applications beyond supervised learning and AutoML toolkits are noted as promising for transferability and reproducibility.The review also observes that evaluating NAS methods is often hard.Source: §2.4 · p. 8

3 TOWARDS STABILIZED WEIGHT-SHARING NAS

This section examines why weight-sharing NAS is unstable, formalizes the optimization gap, and reviews proposed remedies and unresolved issues.

3 TOWARDS STABILIZED WEIGHT-SHARING NAS

  • The section defines instability as differing searched architectures or test accuracies across runs of the same algorithm, then formalizes the optimization gap and reviews remedies and open issues.Its structure proceeds from formulation to the gap, proposed alleviations, and remaining unsolved issues.Source: §3 · p. 8

3.1 An Alternative Formulation of Weight-Sharing NAS

The formulation represents a candidate architecture with architectural parameters and finds its weights on training data before selecting parameters using validation loss. Weight-sharing amortizes this optimization across architectures, with heuristic and differentiable search handling the parameters differently.

3.1 An Alternative Formulation of Weight-Sharing NAS

  • The formulation represents the selected architecture as the discretization of optimal architectural parameters, chosen to minimize validation loss using weights optimized on training data.The loss is expected cross-entropy; training and validation subsets need not differ, and discretization is unnecessary when parameters are not continuous.Source: §3.1 · p. 8
  • Weight-sharing methods optimize network weights and architectural parameters across sub-architectures to obtain an amortized optimum, rather than assigning separate weights to each architecture.The formulation contrasts this with non-weight-sharing methods, where different architectural parameters have individual weights.Source: §3.1 · p. 8
  • Heuristic search keeps architectural parameters identical during super-network training and uses a separate sampler, whereas differentiable search updates them with the weights and greedily selects a sub-architecture.In differentiable search, the weights are often discarded after the sub-architecture is selected.Source: §3.1 · p. 8

3.2 The Devil Lies in the Optimization Gap

Weight-sharing NAS can be unstable because optimizing a super-network does not ensure high-quality sub-architectures. The resulting optimization gap makes architecture evaluation unreliable and can leave search results sensitive to initialization or hyper-parameters.

3.2 The Devil Lies in the Optimization Gap

  • For heuristic search, Kendall’s τ between true and estimated accuracy rankings is close to zero when candidates have similar complexity.Sub-architecture performance depends partly on how often it appears, especially in the final training iterations, which is mostly random and uncontrollable.Source: §3.2 · p. 9
  • For differentiable search, a super-network at around 90% CIFAR10 training accuracy can yield a pruned sub-architecture below 20% without weight retraining.This gap reflects that super-network training does not account for the later discretization stage.Source: §3.2 · p. 9
  • Optimization-gap noise can exceed the true accuracy difference between two candidates, making judgments unreliable and results sensitive to initialization or hyper-parameters.The paper describes this noise as potentially downgrading search results.Source: §3.2 · pp. 8–9

3.3 Shrinking the Optimization Gap

Weight-sharing NAS gains search speed at the cost of lower evaluation accuracy, producing an optimization gap that cannot be eliminated while weights are shared across many sub-architectures. The section organizes ways to shrink that gap around its sources and discusses the limits of each approach.

3.3 Shrinking the Optimization Gap

  • Four gap sources frame the remedies: gradient-estimation error, super-network local optima, discretization loss, and search–evaluation differences in network shape or hyper-parameters.Most weight-sharing methods may involve more than one source.Source: §3.3 · p. 9

3.3.1 Fixing the Mathematical Error

  • Bi-level optimization addresses α/ω imbalance but depends on near-optimal ω and accurate, costly gradients; rough Hessian approximation can lead to skip-connect mode collapse.One-level alternatives avoid the mathematical burden, but without a validation set they risk overfitting the training set.Source: §3.3.1 · pp. 9–10

3.3.2 Avoiding the Sub-Optima of Super-Network

  • Warm-up delays α updates so operator weights can initialize, while operator partitioning, dropout, and candidate-set changes can reduce unfair competition and local optima.Regularization can slow convergence, though the added overhead is often acceptable for weight-sharing search.Source: §3.3.2 · p. 10

3.3.3 Reducing the Discretization Loss

  • Discretization loss can be reduced by searching discrete architectures, pushing α toward decisive values, or pruning gradually; individual retraining is safest but sacrifices efficiency.Short fine-tuning of top-ranked sub-architectures offers a tunable tradeoff between weight-sharing and individual search.Source: §3.3.3 · pp. 10–11

3.3.4 Bridging the Deployment Gap

  • Search and retraining can differ in network shape and hyper-parameters, so adjusting depth, width, resolution, and training settings helps bridge the deployment gap.The depth gap may be addressed by searching at target shape; transferring architectures across tasks remains difficult, as EfficientDet did not show dominant detection accuracy despite borrowing EfficientNet’s architecture and weights.Source: §3.3.4 · p. 11

3.3.5 Learning-based Approaches

  • Learning-based methods encode sub-architectures and predict quality using auxiliary information, potentially filtering weak candidates earlier, but may miss local properties of the search space.Their predictions depend substantially on how architectures are represented.Source: §3.3.5 · p. 11

3.4 Unsolved Problems

The paper identifies three unresolved challenges for weight-sharing NAS: unclear search-space structure, uncertain fairness in operator comparisons, and difficulty expanding a small super-network into larger architectures.

3.4 Unsolved Problems

  • The smoothness and quality distribution of large search spaces remain unclear, since accurately evaluating all sub-architectures is computationally expensive.The paper asks whether good architectures are numerous and whether a strong architecture may be surrounded by poor ones.Source: §3.4 · p. 11
  • Operator comparisons may be unfair because heavier operators converge more slowly, making outcomes sensitive to when competing operators are compared.The uncertainty is especially consequential in very large search spaces.Source: §3.4 · p. 12
  • Weight-sharing methods can prune large super-networks into smaller architectures but have difficulty deriving larger or deeper architectures from small super-networks.Existing extensions are mostly rule-based, and the paper calls for methods that can expand the search space when needed.Source: §3.4 · p. 12

4 RELATED RESEARCH DIRECTIONS

This section relates NAS to model compression, dynamic routing, meta-learning, hyper-parameter optimization, and automated data augmentation as connected research directions.

4.1 Model Compression

  • Pruning and quantization improve accuracy–complexity tradeoffs, and NAS transfers to compression, though optimization gaps and operator unfairness persist.Non-weight-sharing methods can reach the goal but require retraining the enlarged network each time, adding heavy overhead.Source: §4.1 · p. 12

4.2 Dynamic Routing Networks

  • Dynamic routing assigns computation according to test data, and its relationship to static networks suggests a path toward weight-sharing NAS in larger search spaces.Dynamic networks switch off larger units such as layers or blocks; heavy computation can be assigned to easy samples and light computation to hard samples.Source: §4.2 · p. 12

4.3 Meta Learning

  • Meta-learning treats NAS as learning to design computational models and can support few-shot NAS, transfer across tasks, and optimization-gap reduction.Source: §4.3 · pp. 12–13

4.4 Hyper-Parameter Optimization

  • NAS can be viewed as HPO over architectures, but HPO's complete-training steps make it slower and constrain its search-space flexibility.HPO commonly tunes learning rate, mini-batch size, weight decay, and momentum.Source: §4.4 · p. 13

4.5 Automated Data Augmentation

  • Automated data augmentation formulates image transformations as HPO, but AutoAugment's search cost can reach hundreds of GPU-days on CIFAR10.Uncontrolled aggressive augmentation can contaminate training; the area is viewed as having high potential for future research.Source: §4.5 · p. 13

5 CONCLUSIONS AND FUTURE PROSPECTS

The paper argues that NAS's future depends on more flexible search spaces and reliable algorithms. It identifies coupled limitations in current spaces and search stability, and outlines design criteria for both.

5 CONCLUSIONS AND FUTURE PROSPECTS

  • Limited search spaces and unstable algorithms are coupled constraints; popular DARTS and MobileNet spaces show no significant advantage over reasonable random search.Source: §5 · p. 13
  • NAS's prospects depend on a framework for more flexible search spaces and reliable algorithms, with search-space design more urgent as of July 31st, 2020.Source: §5 · p. 13
  • A good search space should be broad, adjustable, transferable across vision tasks, and yield better accuracy–complexity tradeoffs than reasonable random search or manual design.Source: §5 · pp. 13–14
  • Search algorithms should explore without getting lost, embed constraints such as latency, and may leverage distillation, augmentation, dynamic routing, and transfer learning.Source: §5 · p. 14
Loading 2008.01475v2…