PaperlayerView exact revision on arXiv

Source-linked AI summary

XNAS: Neural Architecture Search with Expert Advice

Niv Nayman, Asaf Noy, Tal Ridnik, Itamar Friedman, Rong Jin, Lihi Zelnik-Manor

arXiv:1906.08031v1cs.LGcs.CVmath.OCstat.ML

TL;DR

Neural architecture search methods face concerns including hard pruning, difficult hyperparameter tuning, and limited theoretical understanding. XNAS treats architecture search as online selection with expert advice and uses exponentiated-gradient updates with dynamic expert wipeout. Across seven public datasets, it reports state-of-the-art performance on three and top-NAS performance on the rest, including 1.60% error on CIFAR-10.

  • Problem

    Current neural architecture search methods face concerns about hard pruning, difficult hyperparameter tuning, and weak theoretical understanding.

    Source: §1 · p. 1

  • Method

    XNAS frames architecture search as online selection under Prediction with Experts Advice and updates architecture weights with an exponentiated-gradient rule and dynamic expert wipeout.

    Source: §1 · p. 1, §2.2 · p. 3

  • Results

    Across seven public datasets, XNAS achieves state-of-the-art performance on three and top-NAS performance on the rest, with 1.60% error on CIFAR-10.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The regret analysis suggests using multiple learning rates based on information carried by backward gradients, while the wipeout mechanism permits recovery of experts that may be selected at the end.

    Source: §1 · p. 2

    Relaxing the wipeout threshold can speed convergence to a single architecture but violates the theoretical regret bound; the paper leaves optimizing this trade-off for future work.

    Source: §3.2.1 · p. 6

Abstract

from arXiv · show

This paper introduces a novel optimization method for differential neural architecture search, based on the theory of prediction with expert advice. Its optimization criterion is well fitted for an architecture-selection, i.e., it minimizes the regret incurred by a sub-optimal selection of operations. Unlike previous search relaxations, that require hard pruning of architectures, our method is designed to dynamically wipe out inferior architectures and enhance superior ones. It achieves an optimal worst-case regret bound and suggests the use of multiple learning-rates, based on the amount of information carried by the backward gradients. Experiments show that our algorithm achieves a strong performance over several image classification datasets. Specifically, it obtains an error rate of 1.6% for CIFAR-10, 24% for ImageNet under mobile settings, and achieves state-of-the-art results on three additional datasets.

1 Introduction

The paper presents XNAS as a PEA-based optimizer for differential neural architecture search, addressing concerns about hard pruning, tuning burden, and limited theoretical understanding. It reports strong results across seven public datasets, including state-of-the-art performance on three.

1 Introduction

  • Earlier NAS approaches could require years of GPU compute, while weight-sharing and continuous-relaxation methods made search more affordable.The introduction also notes concerns about hyperparameter tuning and weak theoretical understanding in current methods.Source: §1 · p. 1
  • XNAS views architecture search as online selection under Prediction with Experts Advice (PEA), with neural operations and connections treated as experts weighted by architecture weights.This frames the optimizer around selecting among operations in the differentiable search space.Source: §1 · p. 1
  • The method uses Exponentiated-Gradient updates and dynamically wipes out inferior experts, aiming to mitigate hard pruning performed only at the end of search.The paper also states that XNAS requires fewer hyperparameters to tune and that its theory guides learning-rate choices.Source: §1 · p. 2
  • XNAS is reported to achieve an optimal worst-case regret bound, with multiple learning rates guided by information in backward gradients.The paper also describes robustness to architecture-weight initialization and recovery of late-blooming experts.Source: §1 · p. 2
  • Across seven public datasets, XNAS achieves state-of-the-art performance on three and top-NAS performance on the rest; it reports 1.60% error on CIFAR-10.The paper also reports more than 20% improvement over existing NAS methods on CIFAR-10.Source: §1 · p. 2

2 Proposed Approach

The approach reformulates differentiable architecture search as separable expert-selection subspaces, then optimizes architecture weights with XNAS. The search alternates network and architecture-weight updates before discretizing the learned architecture.

2.1 Neural Architecture Space

  • The search space is represented as separable PEA subspaces: graph edges combine expert predictions into feature maps, and intermediate nodes aggregate predecessor outputs.Experts correspond to neural operations such as convolution or max pooling, with their own network weights.Source: §2.1 · p. 2
  • After architecture weights are optimized, discretization retains each intermediate node's two strongest predecessor edges and replaces each forecaster with its strongest expert.The search first alternates updates to network and architecture weights, then produces a discrete child architecture.Source: §2.1 · p. 3

2.2 XNAS: eXperts Neural Architecture Search

  • XNAS alternates network-weight training with validation-based Exponentiated-Gradient updates to architecture weights, using gradient-projected expert rewards and a dynamic wipeout step.The method is designed for architecture selection, where a forecaster's experts compete through a convex combination.Source: §2.2 · p. 3
  • Wipeout removes weak experts during search, smoothing the transition to final selection while reducing network weights and graph computations.The paper states this can simplify optimization, help avoid over-fitting, and speed architecture search.Source: §2.2 · pp. 3–4

3 Analysis and Discussion

XNAS analyzes architecture search through expert-selection regret, proving a worst-case guarantee and examining when dynamic wipeout, learning-rate choices, and optimizer design help. The discussion also explains how XNAS handles late-blooming operations and reduces tuning requirements.

3.1 Theoretical Analysis

  • The optimal expert in hindsight cannot be wiped out, while experts with no chance of leading by the search’s end are removed during the process.The wipeout mechanism transfers attention to leading experts.Source: §3.1 · p. 4
  • XNAS’s regret bound is tight against a lower bound of Ω(L T ln N), and wipeout can further reduce regret for certain reward sequences.The wipeout-related reduction depends on the data sequence through γT; the paper also reports a worst-case regret bound for XNAS.Source: §3.1 · pp. 4–5

3.2.2 Fewer Hyper Parameters

  • XNAS’s regret-bound learning rates account for different feedback counts in normal and reduction cells, with cell-specific effective horizons determined by validation size, epochs, and replications.The proposed rates minimize the upper bound in the no-wipeout worst case, so they upper-bound optimal rates and can be fine-tuned.Source: §3.1 · p. 5, §3.2.2 · p. 6

3.1 Theoretical Analysis

  • XNAS uses the same effective reward as policy-gradient NAS while avoiding its sampling inefficiency.This equivalence is stated for sampling a single expert at each step with probability specified by the architecture weights.Source: §3.1 · p. 5

3.2.1 The Recovery of Late Bloomers and Robustness to Initialization

  • GD with softmax attenuates rewards for weakly weighted experts, whereas XNAS’s indirect dependence on architecture weights supports late-bloomer recovery and greater robustness to initialization.Wipeout also prevents inferior operations that begin blooming too late from interfering by removing experts with no chance of leading at the end.Source: §3.2.1 · pp. 5–6

3.2.2 Fewer Hyper Parameters

  • Weight decay increases mean normalized entropy and encourages dense architecture solutions, whereas sparse solutions are preferred because discretization can degrade performance.Figure 2 plots mean normalized entropy against weight decay and marks DARTS’ settings.Source: §3.2.2 · p. 6, Figure 2 · p. 6
  • XNAS omits momentum and Adam’s exponential decay rates, yielding a simpler optimizer with lower computation and memory requirements than commonly used NAS optimizers.The paper notes that momentum requires additional state variables and computations.Source: §3.2.2 · p. 6

4 Experiments and Results

The experiments evaluate XNAS on CIFAR-10 and test transferability of the CIFAR-10-found cell across six other classification benchmarks. XNAS reports strong comparisons against prior NAS methods across these evaluations.

4.1 Architecture Search on CIFAR-10

  • The CIFAR-10 search found convolutional cells in a small parent network, which were stacked into a larger evaluation network and compared with other NAS methods.The search ran for 50 epochs, split the training set equally between operation-weight and architecture-weight training, and took about seven hours on one GPU.Source: §4.1 · p. 7

4.2 CIFAR-10 Evaluation Results

  • XNAS-Small outperforms previous NAS methods on CIFAR-10 by a large margin, while XNAS-Large is the second-highest reported score without extra pre-training data and uses one-quarter the parameters of the top model.XNAS is also reported among the fastest NAS methods.Source: §4.2 · p. 7, Table 1 · p. 7

4 Experiments and Results

  • The CIFAR-10-found cell was transferred to ImageNet, CIFAR-100, Fashion-MNIST, SVHN, Freiburg, and CINIC10.The experiments used CIFAR-10 for the main search and evaluation, then tested transferability on the six named benchmarks.Source: §4 · p. 7, §4.3 · p. 8

4.3 Transferability Evaluation

  • On ImageNet, XNAS transfer results outperform all previous NAS cells; on CIFAR-100, the cell surpasses the next top cell by 1%, and it reports new state-of-the-art accuracy on Fashion-MNIST, Freiburg, and CINIC10.The CIFAR-100 result is second-highest without additional pre-training data; the table captions identify the reported measures as top-1 test error and search cost.Source: §4.3 · p. 8, Table 2 · p. 8, Table 3 · p. 8

5 Related Work

Related work covers expert-based models and online optimization. XNAS draws on prediction-with-expert-advice theory to frame architecture search as selection under regret.

Experts

  • Earlier deep-learning expert models combined separable expert sub-models, while later mixture-of-experts approaches used gating for per-example routing and sometimes sparsity regularization.XNAS draws on prediction-with-expert-advice methods to design inner network components.Source: §5 · p. 8

Regret and optimization

  • Prediction-with-expert-advice strategies seek small regret, which the paper uses as an objective for selecting architecture weights.The related-work passage notes that Adam's worst-case scenario has nonzero average regret, unlike the optimal regret bound claimed for XNAS.Source: §5 · p. 9
  • Prior work showed stochastic gradient descent and prediction-with-expert-advice approaches such as follow-the-regularized-leader can be equivalent, while NAS commonly used Adam or momentum SGD.The paper motivates a selection-oriented optimizer rather than relying on those general optimizers for architecture weights.Source: §5 · p. 9

6 Conclusion

XNAS applies prediction-with-expert-advice optimization to differential NAS, selecting architecture weights by minimizing regret. The conclusion reports strong results across image-classification datasets and identifies dynamic pruning and learning-rate choices as features of the method.

Conclusion

  • XNAS uses exponentiated-gradient back-propagation to learn architecture weights governing network operations and connections.These weights represent experts in the architecture-selection formulation.Source: §6 · p. 9
  • Its regret criterion favors sparse operation selection while allowing late-blooming experts to warm up and take over during search.Regret analysis also motivates multiple learning rates based on information carried by backward gradients.Source: §6 · p. 9
  • Dynamic wiping out of weak experts reduces the computational graph during search, reducing search time and increasing final accuracy.The conclusion reports strong performance across several image-classification datasets and says XNAS is among the fastest existing NAS methods.Source: §6 · p. 9

7 Proofs

The proofs establish that XNAS cannot wipe out the expert that is optimal in hindsight and develop the stated regret bound. They use bounded-loss weight comparisons and a Hoeffding-based argument with convexity.

7.1 Proof of Lemma 1

  • The hindsight-optimal expert cannot be wiped out: the proof assumes a wipeout and contradicts the expert’s final weight advantage.It compares the leading expert’s weight at the wipeout time with the two experts’ bounded-loss weight changes through time T.Source: §7.1 · p. 12

7.2 Proof of Lemma 2

  • The Lemma 2 proof uses nonnegative expert weights and the threshold defining the remaining-expert set to bound the wipeout contribution.The proof separates the left- and right-hand sides before combining the bounds through a telescopic product.Source: §7.2 · p. 12

7.3 Proof of XNAS Regret Bound

  • The regret-bound proof invokes Hoeffding’s lemma for losses bounded by [-L, L], then uses telescoping sums and loss convexity.The supplied proof passages identify these ingredients but do not provide the final bound’s expression.Source: §7.3 · pp. 13–14

8 Supporting Materials for the Key Properties Discussion

These supporting experiments and derivations examine XNAS’s recovery behavior, softmax GD’s gradient attenuation, and regret in a noisy expert-selection setup. They also give derivative calculations for the toy problems.

8.1 A Deterministic 3D Axes Toy Problem

  • After the loss shifts, XNAS’s 3D trajectory moves toward the newly rewarding z-axis, while softmax GD’s update is attenuated and z struggles to recover.The toy problem changes from ℓ1(x, y, z) = 2z for 30 steps to ℓ2(x, y, z) = −y − 2z for 90 steps.Source: §8.1 · p. 15, Figure 3 · p. 15

8.2.1 Balanced Initialization

  • With balanced initialization and constant loss gradients, softmax GD’s gradient magnitude decreases away from initialization, while XNAS reaches the minimum faster.The comparison uses ℓ(x, y) = −x.Source: §8.2.1 · p. 15, Figure 4 · p. 16

8.2.2 Imbalanced Initialization

  • With imbalanced initialization αx = 0 < 5 = αy, softmax GD makes no progress while XNAS reaches the minimum.The reported comparison uses the linear loss ℓ(x, y) = −x.Source: §8.2.2 · p. 15, Figure 5 · p. 16

8.2.3 The Preference of Dense Solutions

  • The softmax GD attenuation factor x·y is smaller farther from a dense solution, making it harder to strengthen one expert over another.The passage notes that this favors dense over sparse solutions, although the discretization stage incurs greater performance degradation for denser solutions.Source: §8.2.3 · p. 16, Figure 6 · p. 16

8.2.4 Loss Functions of a Higher Curvature

  • For the quadratic loss ℓ(x, y) = 0.5(x − 1)^2 + 0.5y^2, softmax GD’s further gradient attenuation makes reaching the local minimum harder.Unlike the linear-loss cases, gradients decrease toward the local minimum.Source: §8.2.4 · p. 17, Figure 7 · p. 17

8.3 Regret and Correct Selection in Statistical Setting

  • The statistical setup compares XNAS and softmax GD on noisy i.i.d. rewards, selecting each run’s highest-weight expert and measuring regret and correct classification.Correct classification means that the selected expert has the highest bias.Source: §8.3 · p. 17
  • XNAS regret is significantly smaller in the statistical comparison and scales as ln N, as implied by its regret upper bound.The comparison averages 1,000 Monte Carlo runs of 1,000 time steps; correct-selection fraction decreases monotonically as regret increases.Source: §8.3 · pp. 17–18, Figure 8 · p. 17

8.4 Gradients Derivations

  • For comparison to previous work [25], decision variables αt,i = ln vt,i; derivatives are derived along x, y, and z for a 3D toy problem and x and y for a 2D toy problem.Each 2D axis represents an expert of a constant prediction.Source: §8.4 · p. 18, §8.4.2 · p. 19, §8.4.3 · p. 19

8.5 The Mean Normalized Entropy

The appendix describes how it calculates mean normalized entropy for forecasters in a normal cell.

8.5 The Mean Normalized Entropy

  • The mean normalized entropy is calculated by averaging the end-of-search normalized entropy across forecasters in a normal cell.The passage specifies that I and J are the index sets used in the mean.Source: §8.5 · p. 20

9 Detailed Experiments Setting

The detailed experiments section specifies the additional classification datasets, CIFAR-10 search choices and preprocessing, and training protocols. The ImageNet and additional-dataset protocols differ from the CIFAR-10 training setup.

9.1 Classification Datasets Details

  • The paper identifies CINIC-10, CIFAR-100, FREIBURG, SVHN, and FMNIST as additional datasets used for transferability tests in Section 4.3.CINIC-10 extends CIFAR-10 with down-sampled ImageNet images and contains 270,000 images of 10 classes [8].Source: §9.1 · p. 20

9.2 CIFAR-10 XNAS Search details

  • CIFAR-10 search uses selected operations in normal and reduction cells, with ReLU-Conv-BN ordering and depthwise separable convolutions applied twice.Training images are padded to 40×40, randomly cropped to 32×32, horizontally flipped, AutoAugmented, and standardized; the search takes up to 0.3 days on an NVIDIA GTX 1080Ti.Source: §9.2 · p. 20

9.3 Train Details

  • CIFAR-10 training stacks 20 cells for 1,500 epochs, while ImageNet training stacks 14 cells for 250 epochs; additional datasets largely follow the CIFAR-10 scheme with adjustments.The appendix specifies separate architectures and augmentation or resizing adjustments for ImageNet, CINIC-10, FREIBURG, and Fashion-MNIST.Source: §9.3 · p. 21

10 Cells Learned by XNAS

XNAS learns normal and reduction cells on CIFAR-10. Its normal cell is described as deeper than typical NAS cells, using average inner-connection depth as the metric.

Cell depth

  • Visually, the XNAS cell appears deeper in some sense than other reported NAS cells [29] [25].Source: §10 · pp. 21–22
  • Cell depth is measured as the average depth of its inner connections, where each connection’s depth is the index of its source node or previous cell.The indexing covers the two previous cells and the cell’s four nodes.Source: §10 · p. 22
  • XNAS’s normal cell is much deeper than a typical NAS cell, a pattern the authors suggest could hint at superior performance.Table 4 presents normal-cell depth for XNAS and other NAS methods; the authors attribute XNAS’s deeper, more complex architecture to better use of the cell design’s degrees of freedom.Source: §10 · p. 22, Table 4 · p. 22
Loading 1906.08031v1…