ZiCo: Zero-shot NAS via Inverse Coefficient of Variation on Gradients

1 INTRODUCTION

• Existing zero-shot proxies do not consistently outperform the naive #Params proxy, motivating a more reliable measure of candidate architectures.One-shot NAS reduces search time but still requires training; multi-shot NAS trains multiple networks.Source: §1 · pp. 1–2
• The paper analyzes how gradient mean and standard deviation relate to convergence, then proposes ZiCo as a theoretically grounded zero-shot proxy.Its contributions also include theoretical links between gradients, convergence, and generalization, and a zero-shot NAS framework.Source: §1 · p. 2
• ZiCo has higher or at least on-par correlation with test accuracy than existing proxies, including #Params, on NASBench101 and NATS-Bench-SSS/TSS across multiple datasets.The introduction also reports better proxy performance across TransNASBench-101 and applications including image classification/reconstruction and pixel-level prediction.Source: §1 · p. 2
• ZiCo-based zero-shot NAS finds architectures with competitive test accuracy to representative one-shot and multi-shot methods at much lower search costs.The introduction identifies the search-time advantage without specifying a numeric cost in these passages.Source: §1 · p. 2

2.1 ZERO-SHOT NAS

• The number of parameters generally works better than previously proposed zero-shot proxies, motivating a proxy that consistently exceeds this baseline.Existing proxies include linear-region measures, gradient-based scores, feature-map gradients, and Jacobian covariance.Source: §2.1 · pp. 2–3

2.2 KERNEL METHODS IN NEURAL NETWORKS

• Kernel-based analyses relate neural-network training convergence and generalization capacity to corresponding kernels, and this work extends that analysis to gradient properties.The cited context includes results on wide networks and networks subject to width constraints.Source: §2.2 · p. 3

3.1 LINEAR REGRESSION

• For linear regression, the analysis considers normalized inputs and bounded labels, and derives training-loss bounds using gradient statistics and a learning-rate condition.The dataset has ||x_i|| = 1 and |y_i| ≤ R; the theorem states a bound for 0 < η < 2, with a further bound when η = 1/M.Source: §3.1 · p. 3

3.2.1 CONVERGENCE RATE

• For ReLU networks, the analysis studies gradient standard deviation in Gaussian-kernel space and relates it to weight movement and convergence under stated initialization and learning-rate assumptions.The convergence results assume i.i.d. Gaussian initial weights and gradients, and report that smaller gradient standard deviation corresponds to lower training loss after training steps.Source: §3.2 · p. 4, §3.2.1 · pp. 4–5

3.2.2 GENERALIZATION CAPACITY

• The generalization analysis links a lower largest Gram-matrix eigenvalue to greater generalization capacity, and reports that smaller gradient standard deviation yields a flatter loss landscape.The latter relationship is presented under the assumptions of Theorem 3.2.Source: §3.2.2 · p. 5

3.3 SUMMARY OF OUR THEORETICAL ANALYSIS

• Higher absolute gradient means and lower gradient standard deviations are associated with faster convergence and greater generalization capacity in the paper’s theoretical summary.The linear-regression analysis says larger absolute means lower the converged training loss, while smaller standard deviations do so when ηM < 1.Source: §3.1 · p. 3, §3.3 · p. 5

3 CONVERGENCE AND GENERALIZATION VIA GRADIENT ANALYSIS

• The paper extends kernel-based analysis by relating gradient properties to neural-network convergence and generalization capacity.Its theoretical summary identifies high absolute gradient means and low standard deviations as the favorable properties.Source: §3.3 · p. 5

3.4 NEW ZERO-SHOT PROXY

• ZiCo jointly considers absolute gradient means and standard deviations to score candidate CNNs, with higher scores associated with better convergence and generalization.The proxy is defined for general CNN architectures without restrictions on architecture; the paper says it uses initial parameters and two input batches for efficient computation.Source: §3.4 · pp. 5–6
• On linear networks trained on MNIST, larger mean gradients and smaller sums of gradient variances correspond to lower training loss after one epoch.For two-layer ReLU MLPs on MNIST, smaller gradient standard deviation tends to accompany lower training and test loss after one epoch.Source: Figure 1 · p. 6, Figure 2 · p. 6

4.1 EXPERIMENTAL SETUP

• The experiments cover theorem validation on MNIST, proxy comparisons on NATSBench and NASBench101, and zero-shot search on ImageNet.The benchmark comparisons also include TransNASBench-101-Mirco, with 4,096 networks across downstream applications.Source: §4.1 · pp. 6–7

4.2 VALIDATION OF THEOREMS 3.1&3.3&3.5

• Lower gradient standard deviation is associated with lower training and test loss, while higher squared mean gradients and lower squared variance coincide with lower training loss.The MNIST experiments use normalized samples for the mean-gradient and variance comparison, and a two-layer ReLU MLP with batch size 256 and learning rate 10^-8 for the standard-deviation comparison.Source: §4.2 · p. 7

4.3 ZICO VS. OTHER PROXIES ON NAS BENCHMARKS

• ZiCo achieves the highest correlation with real test accuracy on NATSBench-TSS and is the only proxy consistently better than #Params there.Table 1 reports correlation coefficients against test accuracy; KT and SPR denote Kendall’s τ and Spearman’s ρ.Source: §4.3 · p. 7, Table 1 · p. 7
• On NASBench101, ZiCo’s Kendall’s τ is 0.46 versus 0.31 for #Params, and it exceeds other proxies except Zen-score.Across NATSBench and NASBench101 search spaces and datasets, the authors report ZiCo as consistently better than #Params.Source: §4.3 · p. 8, Figure 3 · p. 8

4.4 ZICO ON IMAGENET

• 78.1% Top-1 accuracy at around 450M FLOPs; ZiCo-based NAS is competitive with DONNA using fewer FLOPs and 648× faster search.At 600M FLOPs, ZiCo achieves 2.6% higher Top-1 Accuracy than MAGIC-AT with a 3× reduction in search time.Source: §4.4 · pp. 8–9, Table 2 · p. 8
• The search evaluates MobileNetV2-based candidates under 450M, 600M, and 1000M FLOPs budgets; using #Params instead yields 63.5% versus ZiCo’s 78.1% accuracy at 450M.Candidates stack inverted bottleneck blocks with SE modules, with depth-wise kernel sizes 3, 5, or 7 and expansion ratios 1, 2, 4, or 6.Source: §4.4 · pp. 8–9
• Evaluating an architecture requires two backward propagations and takes 0.3 seconds on an NVIDIA 3090 GPU, according to the authors.The paper connects this lightweight computation and avoidance of training with reduced NAS search time.Source: §4.4 · p. 9

4.5 ABLATION STUDY

• Two batches produce the highest correlation in the tested range, and batch size 64 is enough to stabilize the coefficient; the authors use batch size 128.The ablation samples 2,000 NATSBench-TSS networks on CIFAR100 and varies the number of batches from 2 to 10 and batch size from 1 to 128.Source: §4.5 · p. 9, Figure 4 · p. 9

• ZiCo-based NAS finds ImageNet architectures with 78.1%, 79.4%, and 80.4% test accuracy at 450M, 600M, and 1000M FLOPs budgets, respectively, within 0.4 GPU days.The conclusion reports that the architectures are competitive with representative one-shot and multi-shot NAS methods, with much lower search costs.Source: §5 · p. 9

• For learning rate 0 < η < 2, the proof bounds total training loss after updating the weights with accumulated gradients; it interprets larger absolute mean gradients across samples as a lower loss bound and faster convergence.The proof also gives a bound for η = 1/M.Source: A PROOF OF THEOREM 3.1 · pp. 17–18

B PROOF OF THEOREM 3.2

• Under Theorem 3.2’s assumptions, weight displacement is bounded with probability at least (1 − δ)(1 − ϵ), with C determined by η, t, σ, and Φ(1 − ϵ).The proof derives the displacement bound from Gaussian weight and gradient assumptions and a chi-squared distribution.Source: B PROOF OF THEOREM 3.2 · pp. 18–19
• The proof uses bounded weight displacement to control changes in the Gram matrix during training.It invokes a perturbation bound for the Gram matrix after establishing a bound on each weight vector’s movement.Source: B PROOF OF THEOREM 3.2 · pp. 19–20
• Under the stated learning-rate condition, the proof concludes that the minimum eigenvalue of H(t) remains positive.The argument substitutes the learning-rate upper bound into the eigenvalue estimate.Source: B PROOF OF THEOREM 3.2 · p. 20

C PROOF OF THEOREM 3.5

• Theorem 3.5’s Gram-matrix bound is stated under a learning-rate condition and the Gaussian assumptions on initial weights and gradients.The proof refers to the similar argument for Theorem 3.2.Source: C PROOF OF THEOREM 3.5 · p. 20
• With probability at least (1 − δ)(1 − ϵ), weight displacement is bounded by C = ηtσΦ(1 − ϵ) under Theorem 3.5’s assumptions.The proof derives this bound from Gaussian initial weights and gradients.Source: C PROOF OF THEOREM 3.5 · p. 20
• The proof uses normalized training samples, each with unit L2 norm, to bound entry-wise deviations in the Gram matrix.It applies the Cauchy–Schwarz inequality after establishing the weight-displacement bound.Source: C PROOF OF THEOREM 3.5 · pp. 20–21

D.1 SEARCH SPACE

• The search space stacks MobileNetV2-style inverted bottleneck blocks with SE modules, varying kernel size, expansion ratio, and channel count.SE ratio is 0.25; depth-wise kernels are 3, 5, or 7, and expansion ratios are 1, 2, 4, or 6.Source: §D.1 · p. 22

D.2 SEARCH ALGORITHM

• The evolutionary search mutates candidate architectures, scores budget-feasible networks with ZiCo, and retains the population’s highest-scoring candidates.The final architecture is the highest-ZiCo candidate after T search steps.Source: §D.2 · p. 22
• The ImageNet search uses 105 steps, population size 512, two training-set batches of size 128, and takes 10 hours on one NVIDIA 3090 GPU.The authors note that other search methods can also be used.Source: §D.2 · pp. 22–23

D.3 TRAINING DETAILS

• The obtained network is trained for 480 epochs with SGD, cosine annealing, and knowledge distillation from EfficientNet-B3.Training uses mix-up, label smoothing, random erasing, random crop/resize/flip/lighting, and AutoAugment.Source: §D.3 · p. 23

E.1 COMPARISON WITH MORE PROXIES

• ZiCo-selected architectures have the highest test accuracy on all three datasets in the reported optimal-architecture comparison.Table 4 reports test accuracy averaged over five runs on the NATSBench-TSS search space.Source: §E.1 · p. 23, Table 4 · p. 24
• ZiCo is the only proxy reported to work consistently better than #Params and is generally the best among the compared proxies on NATSBench-SSS and NATSBench-TSS.NASWOT and GradSign have similar correlation to ZiCo on TSS, while ZiCo’s correlation is significantly higher on SSS.Source: §E.1 · p. 23, Table 3 · p. 24

E.2 COMPARISON ON TRANSNAS-BENCH-101-MICRO

• ZiCo stays close to the best correlation scores on Scene Classification, Jigsaw, and Surface Normal, but ranks second to Fisher on Autoencoding.The gap on the first three tasks is 0.01 or 0.02; Fisher’s advantage on Autoencoding is attributed as a possibility to its use of gradients with respect to feature maps.Source: Table 5 · p. 25, §E.2 · p. 25
• ZiCo’s selected architectures significantly outperform other proxies on all TransNAS-Bench-101-Micro tasks except Autoencoding, where ZiCo is second best, trailing Fisher by 0.01 SSIM.Other proxies do not achieve high accuracy consistently across the tasks.Source: §E.2 · pp. 25–26, Table 6 · p. 26

E.3 ILLUSTRATION OF VARIOUS PROXIES VS. REAL TEST ACCURACY

• The illustrations compare real test accuracy with various proxies on NATSBench-SSS and NASBench101 search spaces.They cover CIFAR10 and ImageNet16-120 for NATSBench-SSS, and CIFAR10 for NASBench101.Source: §E.3 · p. 26

F.1 IMPACT OF MEAN AND STD

• On three NATSBench-SSS datasets, ZiCo’s combination of gradient mean and standard deviation correlates better with test accuracy than either alone.The comparison uses 2,000 randomly selected networks per dataset.Source: §F.1 · p. 26, Table 7 · p. 26

F.2 SEARCH ALGORITHMS: ZERO-COST PT

• With Zero-PT on NASBench-201, ZiCo finds the highest-test-accuracy architectures except on ImageNet16-120, where it ranks second.Zero-PT integrates candidate networks into a supernet and updates candidate-operation weights using a zero-cost proxy.Source: §F.2 · pp. 26–27, Table 8 · p. 27

F.3 TRAINING RECIPE: WITHOUT DISTILLATION

• The ImageNet training recipe uses 150 epochs, batch size 512, and 224×224 inputs, without knowledge distillation or advanced augmentation.Training uses an initial learning rate of 0.4 with cosine annealing; EfficientNets and Zen-score are trained under the same setup.Source: §F.3 · pp. 27–28
• 77.1% Top-1 accuracy at around 600M FLOPs is 1.0% above Zen-score and 1.6% above TE-NAS; ZiCo also reports comparable or higher accuracy than one-shot or multi-shot NAS with 5-9500× less search time.The reported ZiCo model has similar accuracy to EfficientNet-B1 with 100M fewer FLOPs and much less search cost.Source: §F.3 · p. 28

F.4 SEARCH SPACE: DARTS

• The DARTS search selects the highest-ZiCo networks without FLOPs budgets, using a 100,000-step search that takes 0.7 hours on one NVIDIA 3090 GPU.The selected networks are trained for 600 epochs with standard augmentation and cutout, without knowledge distillation or advanced augmentation.Source: §F.4 · p. 28
• On DARTS, ZiCo outperforms prior zero-shot NAS approaches and achieves comparable or higher accuracy than one-shot or multi-shot NAS with at least 10× less search time.The cited comparison concerns standalone-trained CIFAR10 architectures; Table 10 averages results over three runs.Source: §F.4 · p. 28, Table 10 · p. 28
• Figures 6–8 plot real test accuracy against proxies on NATSBench-SSS for CIFAR10 and ImageNet16-120, and on NASBench101 for CIFAR10.The figures identify Kendall’s τ and Spearman’s ρ as correlation measures.Source: Figure 6 · p. 29, Figure 7 · p. 30, Figure 8 · p. 31