# One, two, three, $\ldots$ infinity: topological properties of thin films of
Co-based shandite

Kazuki Nakazawa, Yasuyuki Kato, and Yukitoshi Motome  Department of Applied
Physics, The University of Tokyo, Tokyo 113-8656, Japan

###### Abstract

The kagome ferromagnet, Co-based shandite Co3Sn2S2, shows a large anomalous
Hall effect (AHE) associated with the Weyl nodes. A thin film with a Co kagome
monolayer was predicted to exhibit the quantum AHE, which awaits the
experimental realization. However, since the Weyl nodes are the topological
singularities unique to bulk, it is unclear how they reside while the film
thickness is reduced. Moreover, it is challenging to precisely predict the
band topology of thin films where the lattice and electronic structures are in
general different from the bulk. Here we report the ab initio results for thin
films of Co3Sn2S2 with one, two and three Co layers with Sn or S surface
terminations, with special attention to the optimization of lattice structure
and magnetism. We find that all the Sn-end films stabilize a ferromagnetic
state similar to the bulk, and retain the large AHE down to the monolayer
limit where the AHE is quantized. In contrast, in the S-end films, the
magnetic state varies with the number of Co layers, which drastically changes
the topological properties, including an interlayer antiferromagnetic state
with zero AHE in the bilayer case. Our results would stimulate further
experimental exploration of thin Weyl materials.

After the prediction of the Berezinskii-Kosterlitz-Thouless transition and the
Haldane’s seminal work for a spontaneous quantum AHE in two spatial
dimensions, it has been widely recognized that condensed matters can be
characterized using the concept of topology Nobel . The Weyl semimetals are a
representative in three dimensions that has attracted much attention because
of the variety of interesting physical properties arising from their unique
topology AMV . The energy spectrum of the Weyl semimetals possesses Weyl
nodes, which can be regarded as “monopoles” with chirality $+1$ or $-1$ in
momentum space. The Weyl nodes always appear in pairs with positive and
negative chirality NN , and this feature generates the Fermi arc on the
surface through the bulk-edge correspondence Murakami , as indeed observed by
the angle-resolved photoemission spectroscopy Xu ; Souma . The peculiar
topology of the Weyl semimetals is also detected in quantum transport
phenomena, such as the large AHE Murakami ; Burkov ; Suzuki , the anomalous
Nernst effect (ANE) Sakai , and the negative magnetoresistance associated with
the chiral anomaly due to the monopoles Burkov ; XHuang ; Zhang .

A prescription for the Weyl semimetals is to lift the degeneracy in the Dirac
nodes by breaking symmetry. The Weyl semimetals with broken spatial inversion
symmetry has been confirmed in several materials, e.g., transition metal
pnictides Xu ; Souma ; WFFBD  and dichalcogenides Soluyanov ; Feng , whereas
those with broken time-reversal symmetry have been rather scarce, with only a
few theoretical proposals WTVS ; XWWDF ; KF  and experiments under the
magnetic field Suzuki ; Sakai . Recently, however, a kagome ferromagnet
Co3Sn2S2 has been discovered to possess the Weyl nodes by spontaneous breaking
of time-reversal symmetry, in the vicinity of $60$ meV from the Fermi level
Wang ; Liu . Indeed, theoretical and experimental studies revealed that the
giant AHE and ANE observed in this compound are of the intrinsic contribution
from the Weyl nodes Wang ; Liu ; Guin ; Yang ; Yanagi .

Figure 1:  Lattice structures of the bulk and thin films of Co3Sn2S2. a, Bulk structure. The black box represents the conventional unit cell which contains three unit cells. b, Top view of a kagome plane composed of Co ions. c-e, Side views of the monolayer, bilayer and trilayer systems with Sn terminations. f-h, Corresponding figures with S terminations. The lattice structures are visualized by VESTA MI .  System | Lattice constant $({\mathrm{\mathring{A}}})$ | Co layer distance $({\mathrm{\mathring{A}}})$ | Magnetic state | Co moment ($\mu_{\rm B}$)
---|---|---|---|---
Sn-end | monolayer | 5.325 | - | FM $\parallel c$ | 0.415
bilayer | 5.355 | 4.434 | FM $\parallel c$ | 0.372
trilayer | 5.370 | 4.436 | FM $\parallel c$ | 0.365 (top, bottom)
0.362 (middle)
S-end | monolayer | 5.194 | - | FM $\parallel c$ | 1.01
bilayer | 5.276 | 4.410 | interlayer AFM $\parallel b^{\prime}$ | 0.339
trilayer | 5.310 | 4.412 | interlayer ferri $\parallel c$ | 0.207 (top, bottom)
0.080 (middle)
bulk | 5.358 $(a,b)$ | 4.403 | FM $\parallel c$ | 0.350
13.123 $(c)$
Table 1:  Optimized lattice structures and stable magnetic states. The lattice
structure for the bulk is taken from the experimental data Li , whose in-plane
lattice constants and the Co layer distance are used for the initial guess for
the optimization of the thin films. $a$, $b$ and $c$ denote the
crystallographic axes defined in Fig. 1. The structural optimizations are
performed for a FM state, except for the S-end bilayer and trilayer where we
assume interlayer AFM and ferrimagnetic states, respectively, by
nonrelativistic ab initio calculations. For all the cases, the $p3m1$ symmetry
is almost preserved, while the lattice constant is considerably shortened in
the S-end cases. All the Sn-end systems exhibit out-of-plane FM, whose Co
magnetic moments approach the bulk value while increasing the layer number. In
contrast, the S-end systems show different magnetic states depending on the
layer number: out-of-plane FM for monolayer, interlayer AFM with in-plane FM
moment directed to ${\bm{b}}^{\prime}={\bm{b}}-{\bm{a}}/2$ in each layer for
bilayer, and interlayer ferrimagnetic state with out-of-plane FM moment in
each layer for trilayer, where $\bm{a}$ and $\bm{b}$ are the in-plane lattice
vectors. See also the top left panel of each figure in Figs. 2 and 3.

Co3Sn2S2 has a quasi-two-dimensional lattice structure with Co kagome layers,
as shown in Figs. 1a and b. Recently, two types of Co kagome monolayers with
different surface terminations, Co3Sn3S2 and Co3SnS2, were investigated
theoretically Muechler . As a remnant of the Weyl nodes in the bulk, both
monolayers are predicted to show a large AHE; especially in Co3Sn3S2 with Sn-
end surfaces, the Weyl gap opens at the Fermi level, which leads to the
quantum AHE. Stimulated by this theoretical prediction, experimental attempts
to fabricate monolayer systems have been carried out, and the magnetism,
transport phenomena and surface states have been discussed for atomically thin
films of Co3Sn2S2 Fujiwara ; Shiogai ; Ikeda1 ; Ikeda2 . In the theoretical
study, however, the lattice parameters were fixed at the bulk values for both
monolayers, despite the fact that the lattice structures are expected to be
relaxed in a different manner depending on the surface termination,
sensitively affecting the magnetism and band topology of the atomically thin
films GG ; BHuang . More importantly, since the Weyl points are the
topological singularities predicted for the three-dimensional bulk systems, it
remains elusive how they appear while changing the film thickness.

In this study, we perform comprehensive ab initio calculations of the band
topology and transport properties for thin films of Co3Sn2S2, with special
attention to the optimal lattice structures and stable magnetic states. We
study monolayers, bilayers and trilayers of Co kagome planes with two
different surface terminations by Sn and S atoms (Figs. 1c–h). From the
obtained magnetic and electronic states, we compute the anomalous Hall
conductivity and the anomalous Nernst conductivity. Through the systematic
study in comparison with the bulk, we discuss the evolution of the topological
properties with the number of kagome layers from one, two, three to infinity.

First, we optimize the lattice structures of each system (see Methods). The
optimized structures are summarized in Table. 1 (see also Supplementary
Information). All the thin films maintain nearly the $p3m1$ symmetry. Compared
to the bulk, the in-plane lattice constants change by less than $\sim 0.6$ %
for the Sn-end systems, while substantial decreases are observed for the S-end
systems, maximally about $3$ % for the monolayer case. Such lattice
deformation was not taken into account in the previous study for the
monolayers Muechler . We note that the distance between the Co layers for
bilayers and trilayers does not change so much from the bulk value, while it
is slightly larger for the Sn-end systems than the S-end ones.

Next, for the optimized structures, we compare the ab initio energy for
various magnetic states (see Supplementary Information). The lowest-energy
states and the magnitudes of Co moments are summarized in Table 1 (see
Methods); see also the top left panel of each figure in Figs. 2 and 3. For the
bulk, a ferromagnetic state is obtained with Co moment of $0.350$ $\mu_{\rm
B}$ along the out-of-plane direction, where $\mu_{\rm B}$ is the Bohr
magneton; the total magnetic moment per unit cell is $1.00$ $\mu_{\rm B}$
because of small but nonzero antiparallel magnetic moments at Sn and S atoms.
The result agrees well with the previous studies Liu ; Wang ; Yanagi . For the
Sn-end thin films, similar out-of-plane ferromagnetic states are obtained for
all the monolayer, bilayer and trilayer systems. The Co moment changes with
the number of Co layers: $0.415$ $\mu_{\rm B}$ for monolayer, $0.372$
$\mu_{\rm B}$ for bilayer, and $0.365$ $\mu_{\rm B}$ (top and bottom layers)
and $0.362$ $\mu_{\rm B}$ (middle layer) for trilayer; the value is
monotonically reduced to the bulk one as the number of Co layers increases. We
note that the net moments per primitive unit cell is $1.00$, $2.01$ and $3.00$
$\mu_{\rm B}$ for monolayer, bilayer and trilayer, respectively, indicating
that the value per Co layer is the same as in the bulk. In contrast, for the
S-end thin films, we obtain different magnetic states depending on the layer
number: an out-of-plane ferromagnetic state for monolayer, an intralayer in-
plane ferromagnetic and interlayer antiferromagnetic state for bilayer, and an
intralayer out-of-plane ferromagentic and interlayer ferrimagnetic state for
trilayer, as shown in Fig. 3, whose net magnetic moments per unit cell are
$3.01$, $0.00$ and $1.00$ $\mu_{\rm B}$, respectively. The Co moment is also
largely different from the Sn-end cases: $1.01$ $\mu_{\rm B}$ for monolayer,
$0.339$ $\mu_{\rm B}$ for bilayer, and $0.207$ $\mu_{\rm B}$ (top and bottom
layers) and $0.080$ $\mu_{\rm B}$ (middle layer) for trilayer. The contrasting
behaviors between the Sn- and S-end series are summarized in Fig. 4a.

Our results indicate that the ferromagnetic order within each Co kagome layer
is stable, regardless of the number of Co layers and the surface termination.
In addition, the magnetic order has out-of-plane anisotropy, except for the
S-end bilayer system. These suggest that the out-of-plane ferromagnetic state
of the Co layer, which is a building block for the bulk system, is robust in
most cases of thin films. Meanwhile, our results reveal that the surface
termination matters to the interlayer magnetism as well as the magnetic
anisotropy. Analyzing the maximally-localized Wannier functions, we indeed
find that the spatial extensions of the Co $d$ orbitals are substantially
different for different surface terminations, which would be relevant to the
interlayer magnetic interactions (see Supplementary Information).

Figure 2:  Magnetic states, Fermi surfaces, band structures with the Berry
curvature $\Omega_{n{{\bm{k}}}}$, the anomalous Hall conductivity $\sigma_{\rm
H}$, and the anomalous Nernst conductivity $\alpha_{\rm N}$ for the Sn-end
films: a, monolayer, b, bilayer and c, trilayer. For comparison, we present
the data for bulk in d. The orange arrows in each top left panel represent the
magnetic moments on the Co ions. The black and gray hexagons in the bottom
left and middle panels, respectively, are the first Brillouin zone in a-c,
while those in d depict the $k_{z}=0$ cut of the Brillouin zone of the bulk.
a1, a2, $\cdots$ d3 denote the bands near the Fermi level set at $0$ eV. An
out-of-plane ferromagnetic state is obtained throughout this Sn-end series,
The monolayer is a Chern insulator with the Weyl gap between the bands a1 and
a2, resulting to the quantized $\sigma_{\rm H}=3e^{2}/h$. The bilayer is
metallic, while having a similar Weyl gap between the bands b1 and b2 above
the Fermi level, leading to the plateau (unquantized) $\sigma_{\rm H}\simeq
6e^{2}/h$. The trilayer hosts electron and hole pockets and Weyl gaps, similar
to the bulk. $\sigma_{\rm H}$ is always positive at Fermi level and shows
similar energy dependence in this series.  Figure 3:  Magnetic states, Fermi
surfaces, band structures with the Berry curvature $\Omega_{n{{\bm{k}}}}$, the
anomalous Hall conductivity $\sigma_{\rm H}$, and the anomalous Nernst
conductivity $\alpha_{\rm N}$ for the S-end films: a, monolayer, b, bilayer
and c, trilayer. In this series, the stable magnetic states change with the
number of layers: out-of-plane ferromagnetic, in-plane interlayer
antiferromagnatic, and out-of-plane interlayer ferrimagnetic states for the
monolayer, bilayer and trilayer, respectively. While all the cases are
metallic, the Berry curvature and the transport properties do not behave
systematically with respect to the layer number. In particular, both
$\sigma_{\rm H}$ and $\alpha_{\rm N}$ vanish in the bilayer case because of
the band degeneracy.  Figure 4:  Layer number dependence of the magnetic and
transport properties of the thin films. a, The averaged magnetic moment per Co
ion. In the Sn-end films where the out-of-plane ferromagnetic state is stable,
the magnetic moment changes smoothly to the bulk value. In contrast, in the
S-end cases, it shows nonmonotonic behavior, reflecting the different magnetic
states depending on the layer number. b, The anomalous Hall conductivity
$\sigma_{\rm H}$ at zero temperature and the anomalous Nersnt conductivity
$\alpha_{\rm N}$ at $k_{\rm B}T=5$ meV. $\sigma_{\rm H}$, which reflects the
band topology through the Berry phase, has large positive values in the Sn-end
series, whereas small negative values for monolayer and trilayer, and zero in
bilayer in the S-end series. $\alpha_{\rm N}$ also shows contrasting behaviors
between the two cases.

The differences in the lattice structures and the stable magnetic states
result in qualitatively different electronic states between the Sn- and S-end
series. We show the Fermi surfaces and the band structures near the Fermi
level in the bottom left and middle panels of each figure, respectively, in
Figs. 2 and 3. In the band structures, we also plot the Berry curvature for
each band by color, which is computed for the tight-binding models constructed
by the Wannier functions obtained from the ab initio calculations (see
Methods).

Let us first discuss the Sn-end films in Figs. 2a-c. In the case of the
monolayer, the band structure has a gap of $\sim 50$ meV at the Fermi level
between the bands a1 and a2, and there is no Fermi surface. The gap is opened
by the spin-orbit coupling at the Weyl nodes on the $\Gamma$-$\rm K$ line in
momentum space, resulting in the large values of the Berry curvatures near the
band top and bottom. Thus, the system is an insulator with the Weyl gap, as
pointed out in the previous study without structural optimization Muechler .
This is reasonable, given little changes in the lattice structure as well as
the magnetism after the optimization in our calculations. In the bilayer,
however, the system becomes metallic with the electron Fermi surfaces around
the $\rm K$ point in the band b1 and the pairs of the hole pockets on both
sides of each $\Gamma$-$\rm M$ line in the band b2. By closely looking at the
band structure, we can identify the Weyl gap of $\sim 30$ meV between b1 and
b2 slightly above the Fermi level, which appears to correspond to that in the
monolayer case but split into two, leading to the hole pocket pair; see also
the band structure in the right panel of Fig. 2b. In the trilayer system, the
band structure becomes more complicated, but still retains the characteristic
features in the monolayer and bilayer: One of the Weyl gap opens between the
bands c2 and c3 on the $\Gamma$-K line above the Fermi level, while the other
two are along the $\Gamma$-M line, as shown in the band structure in the right
panel of Fig. 2c. These overall systematic changes of the electronic states
appear to smoothly connect to the bulk. In fact, as shown in Fig. 2d, the
$k_{z}=0$ cut of the bulk band structure shows similar distribution of the
Weyl gap and the Berry curvature to the above Sn-end films. Thus, in the Sn-
end series, where the out-of-plane ferromagnetic state persists, the
electronic structure and the topological properties change systematically as
the number of Co layers increases.

Next, we discuss the S-end cases. In the monolayer, the system is metallic
with two electron pockets around the $\Gamma$ point as shown in Fig. 3a, in
contrast to the Sn-end case. The result is also different from the previous
study without structural optimization Muechler . The difference is ascribed to
the substantial shrinkage of the lattice constants shown in Table 1. We find
considerable values of the Berry curvature in the bands close to the Fermi
level, which affect the transport properties as discussed later. In the case
of the bilayer, the system is also metallic with one electron pocket around
the $\Gamma$ point; notably, all the bands are doubly degenerate due to the
interlayer antiferromagnetic ordering, cancelling out the Berry curvature. In
the trilayer, there are three bands forming two electron pockets around the
$\Gamma$ point, one electron pocket around the K point, and one hole pocket
around the M point. In each band, the Berry curvature takes nonzero values,
similar to the monolayer case. In addition, we find two small Weyl gaps
between the bands g1 and g2 along the $\rm M$-$\Gamma$ line and another one
between g2 and g3 along $\Gamma$-$\rm K$ line close to the Fermi level.
Although this apparently resembles the case of Sn-end trilayer and bulk
systems, these bands show qualitatively different Berry curvatures due to the
different magnetic state. Thus, in stark contrast to the Sn-end cases, the
S-end series shows no systematic change not only in the magnetic orders but
also in the electronic structure and the band topology.

Now we turn to the transport properties. First of all, in the bulk case, our
results on the anomalous Hall conductivity $\sigma_{\rm H}$ and the anomalous
Nernst conductivity $\alpha_{\rm N}$ well reproduce the previous ones Liu ;
Wang ; Yanagi , as shown in Fig. 2d. Then, in the Sn-end series, the monolayer
shows a quantized AHE with $\sigma_{\rm H}=3e^{2}/h$, where $e$ and $h$ are
the elementary charge and the Planck constant, respectively, corresponding to
the Weyl gap in the blue-shaded energy window in Fig. 2a including the Fermi
level. The result coincides with the previous one without structural
optimization Muechler . In the bilayer, we find that $\sigma_{\rm H}$ exhibits
a plateau at $\simeq 6e^{2}/h$ slightly above the Fermi level in the blue-
shaded region, which corresponds to the Weyl gap between the bands b1 and b2,
as shown in Fig. 2b. The plateau with an almost twice $\sigma_{\rm H}$ of the
monolayer case is due to the systematic change of the band structure from
monolayer to bilayer mentioned above. Note that the contribution from the band
b1 crossing the Fermi level is negligible. Such a plateau is absent in the
trilayer case, but a large value of $\sigma_{\rm H}$ is still observed in the
energy window corresponding to the gap between the bands c2 and c3, as shown
in Fig. 2c. Thus, in the Sn-end series, we obtain systematic evolution of the
AHE, from the quantum AHE in the monolayer to the large AHE in the bulk limit,
reflecting the band structure with the Weyl gap. We note that $\sigma_{\rm H}$
is always positive in the Sn-end series. The results are summarized in Fig.
4b.

In contrast, $\sigma_{\rm H}$ does not show systematic changes in the S-end
cases, as shown in Figs. 3a-c: $\sigma_{\rm H}/(e^{2}/h)\simeq-0.34$, $0.00$
and $-2.71$ for the monolayer, bilayer and trilayer, respectively. The absence
of the AHE in the bilayer case is due to the cancellation of the Berry
curvature by the band degeneracy discussed above, and the negative values of
$\sigma_{\rm H}$ for the monolayer and trilayer originate from the different
band topology from the Sn-end series. Note that in the monolayer case,
$\sigma_{\rm H}$ is largely different from that of the previous study Muechler
because of the structural optimization.

We also compute the anomalous Nernst conductivity $\alpha_{\rm N}$ for both
series of the films. According to the generalized Mott formula XYFN ; Yanagi ,
$\alpha_{\rm N}$ is related with the energy derivative of $\sigma_{\rm H}$.
This holds for our results, as plotted in the rightmost panels in Figs. 2a-c
and 3a-c. In the Sn-end series, $\alpha_{\rm N}$ is almost zero at the Fermi
level for the monolayer because of the quantization of $\sigma_{\rm H}$, while
it takes a negative value for the bilayer and trilayer cases corresponding to
the positive derivative of $\sigma_{\rm H}$. Interestingly, $\alpha_{\rm N}$
takes a large negative value for the bilayer since the Fermi level is on the
verge of the plateau like feature of $\sigma_{\rm H}$ where $\sigma_{\rm H}$
increases rapidly. Since $\alpha_{\rm N}$ is positive in the bulk, our results
suggest a sign change while increasing the number of Co layers, in contrast to
$\sigma_{\rm H}$. Meanwhile, in the S-end cases, $\alpha_{\rm N}$ vanishes for
the bilayer, while it takes small negative values for the monolayer and
trilayer. The layer number dependences for both cases are summarized in Fig.
4b.

Our systematic ab initio study for the thin films of Co-based shandite
revealed that the number of Co kagome layers and the surface termination are
both relevant to the lattice structure, the magnetic state, the electronic
band structure and its topology, and transport properties. We found that the
Sn-end series shows similar behaviors to the bulk, and retains the large AHE
down to the monolayer limit where the quantum AHE is realized, reflecting the
systematic change of the gapped Weyl nodes in the band structure. In contrast,
the S-end series exhibits nonmonotonic behaviors with respect to the layer
number, owing to the dominantly antiferromagnetic interlayer coupling. Our
results would stimulate further experimental studies of the thin films of Co-
based shandite to realize the quantum AHE in the monolayer form. The important
implication of our results is that the measurements of the AHE and ANE as well
as the magnetism will distinguish the film thickness and the surface
termination, both of which are usually hard to directly identify in
experiments. In particular, the sign of $\sigma_{\rm H}$, which is positive in
the Sn-end films while negative in the S-end films, can be relevant
measurement. Furthermore, the different sign of $\alpha_{\rm N}$ from the bulk
will also be useful to measure the film thickness. Furthermore, our prediction
of the systematic evolution of the topological band structure would stimulate
optical measurements, which have been useful to detect the chirality and gap
structure of the Weyl nodes away from the Fermi level CLRL ; Ma ; Okamura .

## Methods

DFT calculation

The OpenMX code OpenMX ; Ozaki  was used for structural optimization and
electronic structure calculations based on the density functional theory
(DFT). The exchange-correlation functional was considered within the
generalized gradient approximation (GGA) proposed by Perdew-Burke-Ernzerhof
(PBE) PBE . For the calculations of thin films, we prepared the slabs with the
bulk in-plane lattice parameter ($a=5.358~{}{\mathrm{\mathring{A}}}$ Li ) and
inserted the vacuum space along the $c$ axis which is larger than
$15~{}{\mathrm{\mathring{A}}}$. The quasi-Newton method was used for the
relaxation of the atomic positions and the lattice vectors until the residual
force becomes lesser than $0.01~{}{\rm eV}/{\mathrm{\mathring{A}}}$ per atom.
The structural optimization was performed by nonrelativistic calculations for
the ferromagnetic state, except for the S-end bilayer and trilayer systems,
where we took interlayer antiferromagnetic and ferrimagnetic states,
respectively. Then, the electronic structure calculations were performed by
relativistic calculations for various magnetic states (ferromagnetic,
collinear antiferromagnetic and 120-degree noncollinear antiferromagnetic for
the intraplane, and ferromagnetic and antiferromagnetic for the interplane),
and employ the lowest-energy solution. We set the cutoff energy for the FFT
grid to 1800 Ry, and sampled the Brillouin zone with $16\times 16\times 1$ and
$16\times 16\times 16$ $\bm{k}$ points for the thin films and the bulk,
respectively. The local magnetic moments are calculated from the Mulliken
population analysis.

Band topology and transport properties

The Bloch functions obtained by the DFT calculations were projected to the
Wannier functions within the maximal localization procedure MV ; SMV  using
the OpenMX code WOT . We employed Co $d$, Sn $s$ and $p$, and S $p$ orbitals.
The target Bloch states was chosen by setting the outer energy window properly
for each system; we confirmed that the tight-binding models constructed from
the Wannier functions well reproduced the original DFT band structure within
the inner energy window which was also properly chosen for each case. Using
the obtained tight-binding models, the anomalous Hall conductivity
$\sigma_{\rm H}$ and the anomalous Nernst conductivity $\alpha_{\rm N}$ were
calculated based on the Kubo formula:

$\displaystyle\sigma_{\rm H}$ $\displaystyle=-\frac{e^{2}}{\hbar
V_{d}}\sum_{{\bm{k}}\in{\rm BZ}}\sum_{n}f(E_{n{\bm{k}}})\Omega_{n{\bm{k}}},$
(1) $\displaystyle\alpha_{\rm N}$ $\displaystyle=\frac{ek_{\rm B}}{\hbar
V_{d}}\sum_{{\bm{k}}\in{\rm BZ}}\sum_{n}s(E_{n{\bm{k}}})\Omega_{n{\bm{k}}},$
(2)

respectively, where $k_{\rm B}$ is the Boltzmann constant, $\hbar$ is Dirac’s
constant, $V_{d}$ is a $d$-dimensional volume of the system,
$f({\varepsilon})=({{\rm e}}^{({\varepsilon}-\mu)/k_{\rm B}T}+1)^{-1}$ and
$s({\varepsilon})=-f({\varepsilon})\ln
f({\varepsilon})-(1-f({\varepsilon}))\ln(1-f({\varepsilon}))$ are the Fermi
distribution function and the entropy density, respectively; the summations
are taken for the wave number ${{\bm{k}}}$ within the first Brillouin zone and
for the band index $n$. In Eqs. (1) and (2), $\Omega_{n{{\bm{k}}}}$ is the
Berry curvature calculated by

$\displaystyle\Omega_{n{{\bm{k}}}}=-\sum_{m\neq n}\frac{2{\rm
Im}\left[J_{x,nm}J_{y,mn}\right]}{(E_{n{{\bm{k}}}}-E_{m{{\bm{k}}}})^{2}},$ (3)

with the current operator

$\displaystyle J_{\xi,nm}=\left\langle n{{\bm{k}}}\left|\frac{\partial
H_{{\bm{k}}}}{\partial k_{\xi}}\right|m{{\bm{k}}}\right\rangle,$ (4)

where $m$ and $n$ are the band indices, $\xi=x,y$, $H_{{\bm{k}}}$ is the
tight-binding Hamiltonian obtained from the maximally-localized Wannier
functions, and $E_{n{{\bm{k}}}}$ and $\left.|n{{\bm{k}}}\right\rangle$ are the
eigenvalue and the eigenvector of $H_{{\bm{k}}}$, respectively. The number of
the $\bm{k}$-mesh in the first Brillouin zone was taken as $2000\times 2000$
for monolayers and bilayers, $2800\times 2800$ for the S-end trilayer,
$6000\times 6000$ for the Sn-end trilayer, and $360\times 360\times 360$ for
the bulk.

## Acknowledgements

The authors thank K. Fujiwara, K. Nomura, S. Okumura, A. Ozawa and A.
Tsukazaki for fruitful discussions. This work is supported by JST CREST (Grant
No. JPMJCR18T2) and JSPS KAKENHI (Grant No. JP21K13875).

## References

  * (1) Gibney, E. & Castelvecchi, D. Physics of 2D exotic matter wins Nobel, Nature 538, 18 (2016).
  * (2) Armitage, N. P., Mele, E. J. & Vishwanath, A. Weyl and Dirac semimetals in three-dimensional solids, Rev. Mod. Phys. 90, 015001 (2018).
  * (3) Nielsen, H. B. & Ninomiya, M. The Adler-Bell-Jackiw anomaly and Weyl fermions in a crystal, Phys. Lett. B 130, 389 (1983).
  * (4) Murakami, S. Phase transition between the quantum spin Hall and insulator phases in 3D: emergence of a topological gapless phase, New J. Phys. 9, 356 (2007).
  * (5) Xu, S.-Y. et al. Discovery of a Weyl Fermion Semimetal and Topological Fermi Arcs, Science 349, 613 (2015).
  * (6) Souma, S. et al. Direct observation of nonequivalent Fermi-arc states of opposite surfaces in the noncentrosymmetric Weyl semimetal NbP, Phys. Rev. B 93, 161112(R) (2016).
  * (7) Burkov, A. A. Chiral anomaly and transport in Weyl metals, J. Phys.: Condens. Matter 27, 113201 (2015).
  * (8) Suzuki, T. et al. Large anomalous Hall effect in a half-Heusler antiferromagnet, Nat. Phys. 12, 1119 (2016).
  * (9) Sakai, A. et al. Giant anomalous Nernst effect and quantum-critical scaling in a ferromagnetic semimetal, Nat. Phys. 14, 1119 (2018).
  * (10) Huang, X. et al. Phys. Rev. X 5, 031023 (2015).
  * (11) Zhang, C.-L. et al. Signatures of the Adler–Bell–Jackiw chiral anomaly in a Weyl fermion semimetal, Nat. Commun. 7, 10735 (2016).
  * (12) Weng, H., Fang, C., Fang, Z., Bernevig, B. A. & Dai, X. Weyl Semimetal Phase in Noncentrosymmetric Transition-Metal Monophosphides, Phys. Rev. X 5, 011029 (2015).
  * (13) Soluyanov, A. A. et al. Type-II Weyl semimetals, Nature 527, 495 (2015).
  * (14) Feng, B. et al. Spin texture in type-II Weyl semimetals WTe2, Phys. Rev. B 96, 195134 (2016).
  * (15) Wan, X. G., Turner, A. M., Vishwanath, A. & Savrasov, S. Y. Topological semimetal and Fermi-arc surface states in the electronic structure of pyrochlore iridates, Phys. Rev. B 83, 205101 (2011).
  * (16) Xu, G., Weng, H. M., Wang, Z. J., Dai, X. & Fang, Z. Chern semimetal and the quantized anomalous Hall effect in HgCr2Se4. Phys. Rev. Lett. 107, 186806 (2011).
  * (17) Kübler, J. & Felser, C. Weyl points in the ferromagnetic Heusler compound Co2MnAl, Europhys. Lett. 114, 47005 (2016).
  * (18) Wang, Q. et al. Large intrinsic anomalous Hall effect in half-metallic ferromagnet Co3Sn2S2 with magnetic Weyl fermions, Nat. Commun. 9, 3681 (2018).
  * (19) Liu, E. et al. Giant anomalous Hall effect in a ferromagnetic kagome-lattice semimetal, Nat. Phys. 14, 1125 (2018).
  * (20) Guin, S. N. et al. Zero-Field Nernst Effect in a Ferromagnetic Kagome-Lattice Weyl-Semimetal Co3Sn2S2, Adv. Mater. 31, 1806622 (2019).
  * (21) Yang, H. et al. Giant anomalous Nernst effect in the magnetic Weyl semimetal Co3Sn2S2, Phys. Rev. Mater. 4, 024202 (2020).
  * (22) Yanagi, Y. et al. First-principles investigation of magnetic and transport properties in hole-doped shandite compounds Co3InxSn2-xS2, Phys. Rev. B 103, 205112 (2021).
  * (23) Muechler, L. et al. Emerging chiral edge states from the confinement of a magnetic Weyl semimetal in Co3Sn2S2, Phys. Rev. B 101, 115106 (2020).
  * (24) Fujiwara, K. et al. Ferromagnetic Co3Sn2S2 thin films fabricated by co-sputtering, Jpn. J. Appl. Phys. 58, 050912 (2019).
  * (25) Shiogai, J. et al. Robust perpendicular magnetic anisotropy of Co3Sn2S2 phase in sulfur deficient sputtered thin film, Phys. Rev. Mater. 5, 024403 (2021).
  * (26) Ikeda, J. et al. Critical thickness for the emergence of Weyl features in Co3Sn2S2 thin films, Commun. Mater. 2, 18 (2021).
  * (27) Ikeda, J. et al. Two-dimensionality of metallic surface conduction in Co3Sn2S2 thin films, Commun. Phys. 4, 117 (2021).
  * (28) Geim, A. K. & Grigorieva, I. V. Van der Waals heterostructures, Nature 499, 419 (2013).
  * (29) Huang, B. et al. Layer-dependent ferromagnetism in a van der Waals crystal down to the monolayer limit, Nature 546, 270 (2017).
  * (30) Momma, K. & Izumi, F. VESTA 3 for three-dimensional visualization of crystal, J. Appl. Cryst. 44, 1272 (2011).
  * (31) Li, G. et al. Surface states in bulk single crystal of topological semimetal Co3Sn2S2 toward water oxidation, Sci. Adv. 5, eaaw9867 (2019).
  * (32) Xiao, D., Yao, Y., Fang, Z. & Niu, Q. Berry-Phase Effect in Anomalous Thermoelectric Transport, Phys. Rev. Lett. 97, 026603 (2006).
  * (33) Chan, C.-K., Lindner, N. H., Refael, G. & Lee, P. A. Photocurrents in Weyl semimetals, Phys. Rev. B 95, 041104(R) (2017).
  * (34) Ma, Q. et al. Direct optical detection of Weyl fermion chirality in a topological semimetal, Nat. Phys. 13, 842 (2017).
  * (35) Okamura, Y. et al. Giant magneto-optical responses in magnetic Weyl semimetal Co3Sn2S2, Nat. Commun. 11, 4619 (2020).
  * (36) http://www.openmx-square.org.
  * (37) Ozaki, T. Variationally optimized atomic orbitals for large-scale electronic structures Phys. Rev. B.67, 155108, (2003).
  * (38) Perdew, J. P., Burke, K. & Ernzerhof, M. Generalized Gradient Approximation Made Simple, Phys. Rev. Lett. 77, 3865 (1996).
  * (39) Marzari, N. & Vanderbilt, D. Maximally localized generalized Wannier functions for composite energy bands, Phys. Rev. B 56, 12847 (1997).
  * (40) Souza, I., Marzari, N. & Vanderbilt, D. Maximally localized Wannier functions for entangled energy bands, Phys. Rev. B 65, 035109 (2001).
  * (41) Weng, H., Ozaki, T. & Terakura, K. Revisiting magnetic coupling in transition-metal-benzene complexes with maximally localized Wannier functions, Phys. Rev. B 79, 235118 (2009).

Supplementary information for “One, two, three, $\ldots$ infinity: topological
properties of thin films of Co-based shandite”

## Details of the optimized lattice structures

We present additional information of the optimized lattice structures in Table
S1: the averaged angles for neighboring Co-Sn-Co and Co-S-Co bonds,
$\theta_{\rm Co{{\mathchar 45\relax}}Sn{{\mathchar 45\relax}}Co}$ and
$\theta_{\rm Co{{\mathchar 45\relax}}S{{\mathchar 45\relax}}Co}$,
respectively, and the averaged bond lengths of the nearest-neighbor Co ions in
different layers, $d_{\rm inter{{\mathchar 45\relax}}Co}$. In most cases, the
bond angles and lengths do not change so much from the bulk values, except for
$\theta_{\rm Co{{\mathchar 45\relax}}S{{\mathchar 45\relax}}Co}$ at the
surfaces.

System |  $\theta_{\rm Co{{\mathchar 45\relax}}Sn{{\mathchar 45\relax}}Co}$ (degree) |  $\theta_{\rm Co{{\mathchar 45\relax}}S{{\mathchar 45\relax}}Co}$ (degree) |  $d_{\rm inter{{\mathchar 45\relax}}Co}$ $({\mathrm{\mathring{A}}})$
---|---|---|---
Sn-end | monolayer | 58.8 (A-I, A-II) | 73.6 (A-1, A-2) | -
bilayer | 60.4 (A-I, B-IV) | 73.1 (A-1, B-4) | 4.69
58.9 (A-II, B-II) | 77.5 (A-2, B-3)
trilayer | 60.6 (A-II, C-IV) | 73.3 (A-1, C-6) | 4.67
59.0 (A-II, C-III) | 77.6 (A-2, C-5)
59.6 (B-II, B-III) | 76.4 (B-3, B-4)
S-end | monolayer | - | 72.0 (A-1, A-2) | -
bilayer | 58.1 (A-II, B-II) | 71.9 (A-1, B-4) | 4.65
trilayer | 76.9 (A-2, B-3) | 4.66
58.5 (A-II, C-III) | 71.3 (A-1, C-6)
| 78.7 (A-2, C-5)
|  | 58.5 (B-II, B-III) |  |
|  |  | 75.4 (B-3, B-4) |
bulk | 60.0 | 76.1 | 4.64
Table S1:  Additional information of the optimized lattice structures to Table
1 in the main text. $\theta_{\rm Co{{\mathchar 45\relax}}Sn{{\mathchar
45\relax}}Co}$ and $\theta_{\rm Co{{\mathchar 45\relax}}S{{\mathchar
45\relax}}Co}$ denote the averaged angles for neighboring Co-Sn-Co and Co-S-Co
bonds, respectively, and $d_{\rm inter{{\mathchar 45\relax}}Co}$ is the
averaged bond length for the nearest-neighbor Co ions in different layers.
Alphabets, Roman numbers and Arabic numbers in the parentheses specify the Co,
Sn and S ions, respectively, depicted in Fig. S1b. The bonds in the same
parenthesis are equivalent under the $C_{2}$ rotation around the $\bm{a}$ or
$\bm{b}$ axis.  Figure S1:  Definitions of the bond angles and the ions used
in Table S1: a, $\theta_{\rm Co{{\mathchar 45\relax}}Sn{{\mathchar
45\relax}}Co}$ and $\theta_{\rm Co{{\mathchar 45\relax}}S{{\mathchar
45\relax}}Co}$, and b, the labels of the ions to specify the bonds for the
monolayer, bilayer and trilayer cases.

## Energy comparison for various magnetic states

We show in Table S2 the energy for different magnetic states obtained by the
full relativistic ab initio calculations for the optimized lattice structures.
As listed in Fig. S2, we took the initial states as ferromagnetic (FM) states,
120 degree noncollinear antiferromagnetic (120AFM) states, and intralayer FM
and interlayer collinear antiferromagnetic (IAFM) states [interlayer collinear
ferrimagnetic (IFRM) state for trilayer]. For the FM states, we considered
three types whose magnetic moments are along the out-of-plane ($c$) and two
in-plane ($a$ and $b^{\prime}$) directions; for the 120AFM states, we
considered three types with different chirality and helicity; for the IAFM
states, we considered three types similar to the FM cases. For the Sn-end
systems, the FM states with the out-of-plane magnetic moments are most stable,
similar to the bulk, with the energy differences from the in-plane FM states
being about 1$\sim$2 meV. In contrast, for the S-end systems, the stable
magnetic states and the directions of the magnetic moments depend on the layer
number as described in the main text. The energy differences between the most
stable states and the other competing states are less than $1$ meV, which are
smaller than the Sn-end cases. This implies that the magnetic anisotropy is
smaller for the S-end films than the Sn-end ones.

System | PM | FM | 120AFM | IAFM/IFRM
---|---|---|---|---
$a$ | $b^{\prime}$ | $c$ | $a$ | $b^{\prime}$ | $c$
Sn-end | monolayer | 122 | 0.993 | 1.01 | 0 | 85.7 | - | - | -
bilayer | 162 | 1.57 | 1.60 | 0 | 128 | 30.1 | 30.1 | 29.3
trilayer | 219 | 2.28 | 2.28 | 0 | 195 | 71.4 | 71.4 | 70.4
S-end | monolayer | 393 | 0.033 | 0.034 | 0 | 162 | - | - | -
bilayer | 79.7 | 28.6 | 28.5 | 29.5 | - | 0.009 | 0 | 0.532
trilayer | 34.7 | 22.9 | 23.1 | 22.8 | - | 0.030 | 0.046 | 0
bulk | 58.1 | 0.619 | 0.623 | 0 | - | - | - | -
Table S2:  Energy per unit cell for various magnetic states in the unit of
meV. The schematic pictures of the magnetic states are shown in Fig. S2. The
values are measured from the lowest one: FM $c$ for all the Sn-end films, and
FM $c$, IAFM $b^{\prime}$ and IFRM $c$ for the S-end monolayer, bilayer and
trilayer, respectively. $a$, $b^{\prime}$ and $c$ specify the direction of the
magnetic moments. For the 120AFM states, the energy was obtained by averaging
the values for three different 120 degree structures chosen such that one of
the Co spin directs in the $a$, $b$ and $b^{\prime}$ directions. “-”
represents the magnetic states not stabe or not considered.  Figure S2:
Schematic pictures of the magnetic states considered in the ab initio
calculations. The black arrows represent the directions of each Co magnetic
moment on the kagome lattice.  Figure S3: Isosurfaces of the maximally-
localized Wannier functions with Co $d_{z^{2}}$\- and $d_{x^{2}-y^{2}}$-like
orbital characters. The green and yellow surfaces represent the isosurfaces of
the real part of the Wannier functions being $0.007$ and $-0.007$,
respectively.

## Maximally-localized Wannier functions for $\rm Co$ $d$ orbitals

We display the maximally-localized Wannier functions with Co $d_{z^{2}}$ and
$d_{x^{2}-y^{2}}$ orbital characters in Fig. S3, which are mostly different
between the Sn- and S-end films among the $d$ orbitals. The results are
obtained for the paramagnetic state by the relativistic calculations. In all
cases, the Wannier functions in the S-end systems, especially of the Co ions
near the surfaces, have wider spatial extensions to the interlayer directions.
This difference leads to different overlaps of the wave functions between the
Sn- and S-end systems, possibly being relevant to the difference in the
interlayer magnetic interactions.


# Neural Architecture Search on ImageNet in Four GPU Hours:
A Theoretically Inspired Perspective

Wuyang Chen, Xinyu Gong, Zhangyang Wang
Department of Electrical and Computer Engineering
The University of Texas at Austin, Austin, TX, USA
<EMAIL_ADDRESS>

###### Abstract

Neural Architecture Search (NAS) has been explosively studied to automate the
discovery of top-performer neural networks. Current works require heavy
training of supernet or intensive architecture evaluations, thus suffering
from heavy resource consumption and often incurring search bias due to
truncated training or approximations. Can we select the best neural
architectures without involving any training and eliminate a drastic portion
of the search cost? We provide an affirmative answer, by proposing a novel
framework called training-free neural architecture search (TE-NAS). TE-NAS
ranks architectures by analyzing the spectrum of the neural tangent kernel
(NTK) and the number of linear regions in the input space. Both are motivated
by recent theory advances in deep networks and can be computed without any
training and any label. We show that: (1) these two measurements imply the
trainability and expressivity of a neural network; (2) they strongly correlate
with the network’s test accuracy. Further on, we design a pruning-based NAS
mechanism to achieve a more flexible and superior trade-off between the
trainability and expressivity during the search. In NAS-Bench-201 and DARTS
search spaces, TE-NAS completes high-quality search but only costs 0.5 and 4
GPU hours with one 1080Ti on CIFAR-10 and ImageNet, respectively. We hope our
work inspires more attempts in bridging the theoretical findings of deep
networks and practical impacts in real NAS applications. Code is available at:
https://github.com/VITA-Group/TENAS.

##  1 Introduction

The recent development of deep networks significantly contributes to the
success of computer vision. Thanks to many efforts by human designers, the
performance of deep networks have been significantly boosted (Krizhevsky et
al., 2012; Simonyan & Zisserman, 2014; Szegedy et al., 2015; He et al., 2016;
Xie et al., 2017). However, the manual creation of new network architectures
not only costs enormous time and resources due to trial-and-error, but also
depends on the design experience that does not always scale up. To reduce the
human efforts and costs, neural architecture search (NAS) has recently amassed
explosive interests, leading to principled and automated discovery for good
architectures in a given search space of candidates (Zoph & Le, 2016; Brock et
al., 2017; Pham et al., 2018; Liu et al., 2018a; Chen et al., 2018; Bender et
al., 2018; Gong et al., 2019; Chen et al., 2020a; Fu et al., 2020).

As an optimization problem, NAS faces two core questions: 1) “how to
evaluate”, i.e. the objective function that defines what are good
architectures we want; 2) “how to optimize”, i.e. by what means we could
effectively optimize the objective function. These two questions are entangled
and highly non-trivial, since the search spaces are of extremely high
dimension, and the generalization ability of architectures cannot be easily
inferred (Dong & Yang, 2020; Dong et al., 2020). Existing NAS methods mainly
leverage the validation set and conduct accuracy-driven architecture
optimization. They either formulate the search space as a super-network
(“supernet”) and make the training loss differentiable through the
architecture parameters (Liu et al., 2018b), or treat the architecture
selection as a sequential decision making process (Zoph & Le, 2016) or
evolution of genetics (Real et al., 2019). However, these NAS algorithms
suffer from heavy consumption of both time and GPU resources. Training a
supernet till convergence is extremely slow, even with many effective
heuristics for sampling or channel approximations (Dong & Yang, 2019; Xu et
al., 2019). Approximated proxy inference such as truncated training/early
stopping can accelerate the search, but is well known to introduce search bias
to the inaccurate results obtained (Pham et al., 2018; Liang et al., 2019; Tan
et al., 2020). The heavy search cost not only slows down the discovery of
novel architectures, but also blocks us from more meaningfully understanding
the NAS behaviors.

On the other hand, the analysis of neural network’s trainability (how
effective a network can be optimized via gradient descent) and expressivity
(how complex the function a network can represent) has witnessed exciting
development recently in the deep learning theory fields. By formulating neural
networks as a Gaussian Process (no training involved), the gradient descent
training dynamics can be characterized by the Neural Tangent Kernel (NTK) of
infinite (Lee et al., 2019) or finite (Yang, 2019) width networks, from which
several useful measures can be derived to depict the network trainability at
the initialization. Hanin & Rolnick (2019a; b); Xiong et al. (2020) describe
another measure of network expressivity, also without any training, by
counting the number of unique linear regions that a neural network can divide
in its input space. We are therefore inspired to ask:

  * •

_How to optimize NAS at network’s initialization without involving any
training, thus significantly eliminating a heavy portion of the search cost?_

  * •

_Can we define how to evaluate in NAS by analyzing the trainability and
expressivity of architectures, and further benefit our understanding of the
search process?_

Our answers are yes to both questions. In this work, we propose TE-NAS, a
framework for training-free neural architecture search. We leverage two
indicators, the condition number of NTK and the number of linear regions, that
can decouple and effectively characterize the trainability and expressivity of
architectures respectively in complex NAS search spaces. Most importantly,
these two indicators can be measured in a training-free and label-free manner,
thus largely accelerates the NAS search process and benefits the understanding
of discovered architectures. To our best knowledge, TE-NAS makes the first
attempt to bridge the theoretical findings of deep neural networks and real-
world NAS applications. While we intend not to claim that the two indicators
we use are the only nor the best options, we hope our work opens a door to
theoretically-inspired NAS and inspires the discovery of more deep network
indicators. Our contributions are summarized as below:

  * •

We identify and investigate two training-free and label-free indicators to
rank the quality of deep architectures: the spectrum of their NTKs, and the
number of linear regions in their input space. Our study finds that they
reliably indicate the trainability and expressivity of a deep network
respectively, and are strongly correlated with the network’s test accuracy.

  * •

We leverage the above two theoretically-inspired indicators to establish a
training-free NAS framework, TE-NAS, therefore eliminating a drastic portion
of the search cost. We further introduce a pruning-based mechanism, to boost
search efficiency and to more flexibly trade-off between trainability and
expressivity.

  * •

In NAS-Bench-201/DARTS search spaces, TE-NAS discovers architectures with a
strong performance at remarkably lower search costs, compared to previous
efforts. With just one 1080Ti, it only costs 0.5 GPU hours to search on
CIFAR10, and 4 GPU hours on ImageNet, respectively, setting the new record for
ultra-efficient yet high-quality NAS.

##  2 Related Works

Neural architecture search (NAS) is recently proposed to accelerate the
principled and automated discovery of high-performance networks. However, most
works suffer from heavy search cost, for both weight-sharing based methods
(Liu et al., 2018b; Dong & Yang, 2019; Liu et al., 2019; Yu et al., 2020a; Li
et al., 2020a; Yang et al., 2020a) and single-path sampling-based methods
(Pham et al., 2018; Guo et al., 2019; Real et al., 2019; Tan et al., 2020; Li
et al., 2020c; Yang et al., 2020b). A one-shot super network can share its
parameters to sampled sub-networks and accelerate the architecture
evaluations, but it is very heavy and hard to optimize and suffers from a poor
correlation between its accuracy and those of the sub-networks (Yu et al.,
2020c). Sampling-based methods achieve more accurate architecture evaluations,
but their truncated training still imposes bias to the performance ranking
since this is based on the results of early training stages.

Instead of estimating architecture performance by direct training, people also
try to predict network’s accuracy (or ranking), called predictor based NAS
methods (Liu et al., 2018a; Luo et al., 2018; Dai et al., 2019; Luo et al.,
2020). Graph neural network (GNN) is a popular choice as the predictor model
(Wen et al., 2019; Chen et al., 2020b). Siems et al. (2020) even propose the
first large-scale surrogate benchmark, where most of the architectures’
accuracies are predicted by a pretrained GNN predictor. The learned predictor
can achieve highly accurate performance evaluation. However, the data
collection step - sampling representative architectures and train them till
converge - still requires extremely high cost. People have to sample and train
2,000 to 50,000 architectures to serve as the training data for the predictor.
Moreover, none of these works can demonstrate the cross-space transferability
of their predictors. This means one has to repeat the data collection and
predictor training whenever facing an unseen search space, which is highly
nonscalable.

The heavy cost of architecture evaluation hinders the understanding of the NAS
search process. Recent pioneer works like Shu et al. (2019) observed that
DARTS and ENAS tend to favor architectures with wide and shallow cell
structures due to their smooth loss landscape. Siems et al. (2020) studied the
distribution of test error for different cell depths and numbers of parameter-
free operators. Chen & Hsieh (2020) for the first time regularizes the Hessian
norm of the validation loss and visualizes the smoother loss landscape of the
supernet. Li et al. (2020b) proposed to approximate the validation loss
landscape by learning a mapping from neural architectures to their
corresponding validate losses. Still, these analyses cannot be directly
leveraged to guide the design of network architectures.

Mellor et al. (2020) recently proposed a NAS framework that does not involve
training, which shares the same motivation with us towards training-free
architecture search at initialization. They empirically find that the
correlation between sample-wise input-output Jacobian can indicate the
architecture’s test performance. However, why does the Jacobian work is not
well explained and demonstrated. Their search performance on NAS-Bench-201 is
still left behind by the state-of-the-art NAS works, and they did not extend
to DARTs space.

Meanwhile, we see the evolving development of deep learning theory on neural
networks. NTK (neural tangent kernel) is proposed to characterize the gradient
descent training dynamics of infinite wide (Jacot et al., 2018) or finite wide
deep networks (Hanin & Nica, 2019). Wide networks are also proved to evolve as
linear models under gradient descent (Lee et al., 2019). This is further
leveraged to decouple the trainability and generalization of networks (Xiao et
al., 2019). Besides, a natural measure of ReLU network’s expressivity is the
number of linear regions it can separate in its input space (Raghu et al.,
2017; Montúfar, 2017; Serra et al., 2018; Hanin & Rolnick, 2019a; b; Xiong et
al., 2020). In our work, we for the first time discover two important
indicators that can effectively rank architectures, thus bridging the
theoretic findings and real-world NAS applications. Instead of claiming the
two indicators we discover are the best, we believe there are more meaningful
properties of deep networks that can benefit the architecture search process.
We leave them as open questions and encourage the community to study.

##  3 Methods

The core motivation of our TE-NAS framework is to achieve architecture
evaluation without involving any training, to significantly accelerate the NAS
search process and reduce the search cost. In section 3.1 we present our study
on two important indicators that reflect the trainability and expressivity of
a neural network, and in section 3.2 we design a novel pruning-based method
that can achieve a superior trade-off between the two indicators.

###  3.1 Analyzing Trainability and Expressivity of Deep Networks

Trainability and expressivity are distinct notions regarding a neural network
(Xiao et al., 2019). A network can achieve high performance only if the
function it can represent is complex enough and at the same time, it can be
effectively trained by gradient descent.

####  3.1.1 Trainability by Condition Number of NTK

The trainability of a neural network indicates how effective it can be
optimized using gradient descent (Burkholz & Dubatovka, 2019; Hayou et al.,
2019; Shin & Karniadakis, 2020). Although some heavy networks can
theoretically represent complex functions, they not necessarily can be
effectively trained by gradient descent. One typical example is that, even
with a much more number of parameters, Vgg networks (Simonyan & Zisserman,
2014) usually perform worse and require more special engineering tricks
compared with ResNet family (He et al., 2016), whose superior trainability
property is studied by Yang & Schoenholz (2017).

Recent work (Jacot et al., 2018; Lee et al., 2019; Chizat et al., 2019)
studied the gradient descent training of neural networks using a quantity
called the neural tangent kernel (NTK). The finite width NTK is defined by
$\hat{\Theta}(\bm{x},\bm{x}^{\prime})=J(\bm{x})J(\bm{x}^{\prime})^{T}$, where
$J_{i\alpha}(\bm{x})=\partial_{\theta_{\alpha}}z_{i}^{L}(\bm{x})$ is the
Jacobian evaluated at a point $\bm{x}$ for parameter $\theta_{\alpha}$, and
$z_{i}^{L}$ is the output of the $i$-th neuron in the last output layer $L$.

Lee et al. (2019) further proves that wide neural networks evolve as linear
models using gradient descent, and their training dynamics is controlled by
ODEs that can be solved as

$\mu_{t}(\bm{X}_{\text{train}})=(\textbf{I}-e^{-\eta\hat{\Theta}_{\text{train}}t})\bm{Y}_{\text{train}}$
(1)

for training data. Here $\mu_{t}(\bm{x})=\mathbb{E}[z^{L}_{i}(\bm{x})]$ is the
expected outputs of an infinitely wide network. $\hat{\Theta}_{\text{train}}$
denotes the NTK between the training inputs, and $\bm{X}_{\text{train}}$ and
$\bm{Y}_{\text{train}}$ are drawn from the training set
$\mathcal{D}_{\text{train}}$. As the training step $t$ tends to infinity we
can see that Eq. 1 reduce to
$\mu(\bm{X}_{\text{train}})=\bm{Y}_{\text{train}}$.

The relationship between the conditioning of $\hat{\Theta}$ and the
trainability of networks is studied by Xiao et al. (2019), and we brief the
conclusion as below. We can write Eq. 1 in terms of the spectrum of $\Theta$:

$\mu_{t}(\bm{X}_{\text{train}})_{i}=(\textbf{I}-e^{-\eta\lambda_{i}t})\bm{Y}_{{\text{train}},i},$
(2)

Figure 1: Condition number of NTK $\kappa_{\mathcal{N}}$ exhibits negative
correlation with the test accuracy of architectures in NAS-Bench201 (Dong &
Yang, 2020).

where $\lambda_{i}$ are the eigenvalues of $\hat{\Theta}_{\text{train}}$ and
we order the eigenvalues $\lambda_{0}\geq\cdots\geq\lambda_{m}$. As it has
been hypothesized by Lee et al. (2019) that the maximum feasible learning rate
scales as $\eta\sim 2/\lambda_{0}$, plugging this scaling for $\eta$ into Eq.
2 we see that the $\lambda_{m}$ will converge exponentially at a rate given by
$1/\kappa$, where $\kappa=\lambda_{0}/\lambda_{m}$ is the condition number.
Then we can conclude that if the $\kappa$ of the NTK associated with a neural
network diverges then it will become untrainable, so we use $\kappa$ as a
metric for trainability:

$\kappa_{\mathcal{N}}=\frac{\lambda_{0}}{\lambda_{m}}.$ (3)

$\kappa_{\mathcal{N}}$ is calculated without any gradient descent or label.
Figure 1 demonstrates that the $\kappa_{\mathcal{N}}$ is negatively correlated
with the architecture’s test accuracy, with the Kendall-tau correlation as
$-0.42$. Therefore, minimizing the $\kappa_{\mathcal{N}}$ during the search
will encourage the discovery of architectures with high performance.

####  3.1.2 Expressivity by Number of Linear Regions

Figure 2: Example of linear regions divided by a ReLU network111.
11footnotetext: Plot is generated by us with the same method described by
Hanin & Rolnick (2019a).

The expressivity of a neural network indicates how complex the function it can
represent (Hornik et al., 1989; Giryes et al., 2016). For ReLU networks, each
ReLU function defines a linear boundary and divides its input space into two
regions. Since the composition of piecewise linear functions is still
piecewise linear, every ReLU network can be seen as a piecewise linear
function. The input space of a ReLU network can be partitioned into distinct
pieces (i.e. linear regions) (Figure 2), each of which is associated with a
set of affine parameters, and the function represented by the network is
affine when restricted to each piece. Therefore, it is natural to measure the
expressivity of a ReLU network with the number of linear regions it can
separate.

Following Raghu et al. (2017); Serra et al. (2018); Hanin & Rolnick (2019a;
b); Xiong et al. (2020), we introduce the definition of activation patterns
and linear regions for ReLU networks.

Definition 1. Activation Patterns and Linear Regions (Xiong et al. (2020))
Let $\mathcal{N}$ be a ReLU CNN. An activation pattern of $\mathcal{N}$ is a
function ${\bm{P}}$ from the set of neurons to $\\{1,-1\\}$, i.e., for each
neuron $z$ in $\mathcal{N}$, we have ${\bm{P}}(z)\in\\{1,-1\\}$. Let $\theta$
be a fixed set of parameters (weights and biases) in $\mathcal{N}$, and
${\bm{P}}$ be an activation pattern. The region corresponding to ${\bm{P}}$
and $\theta$ is

${\bm{R}}({\bm{P}};\theta):=\\{\bm{x}^{0}\in\mathbb{R}^{C\times H\times
W}:z(\bm{x}^{0};\theta)\cdot{{\bm{P}}(z)}>0,\quad\forall z\in\mathcal{N}\\},$
(4)

where $z(\bm{x}^{0};\theta)$ is the pre-activation of a neuron $z$. Let
$R_{\mathcal{N},\theta}$ denote the number of linear regions of $\mathcal{N}$
at $\theta$, i.e.,
$R_{\mathcal{N},\theta}:=\\#\\{{\bm{R}}({\bm{P}};\theta):{\bm{R}}({\bm{P}};\theta)\neq\emptyset~{}\text{
for some activation pattern }{\bm{P}}\\}.$

Figure 3: Number of linear regions $\hat{R}_{\mathcal{N}}$ of architectures in
NAS-Bench201 exhibits positive correlation with test accuracies.

Eq. 4 tells us that a linear region in the input space is a set of input data
$\bm{x}^{0}$ that satisfies a certain fixed activation pattern ${\bm{P}}(z)$,
and therefore the number of linear regions $R_{\mathcal{N},\theta}$ measures
how many unique activation patterns that can be divided by the network.

In our work, we repeat the measurement of the number of linear regions by
sampling network parameters from the Kaiming Norm Initialization (He et al.,
2015), and calculate the average as the approximation to its expectation:

$\hat{R}_{\mathcal{N}}\simeq\mathbb{E}_{\theta}R_{\mathcal{N},\theta}$ (5)
Figure 4: $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$ prefer different
operators in NAS-Bench201.

We iterate through all architectures in NAS-Bench-201 (Dong & Yang, 2020), and
calculate their numbers of linear regions (without any gradient descent or
label). Figure 3 demonstrates that the number of linear regions is positively
correlated with the architecture’s test accuracy, with the Kendall-tau
correlation as $0.5$. Therefore, maximizing the number of linear regions
during the search will also encourage the discovery of architectures with high
performance.

Finally, in Figure 4 we analyze the operator composition of top 10%
architecture by maximizing $\hat{R}_{\mathcal{N}}$ and minimizing
$\kappa_{\mathcal{N}}$, respectively. We can clearly see that
$\hat{R}_{\mathcal{N}}$ and $\kappa_{\mathcal{N}}$ have different preferences
for choosing operators. They both choose a large ratio of conv$3\times 3$ for
high generalization performance. But meanwhile, $\hat{R}_{\mathcal{N}}$
heavily selects conv$1\times 1$, and $\kappa_{\mathcal{N}}$ leads to skip-
connect, favoring the gradient flow.

###  3.2 Pruning-by-importance Architecture Search

Given the strong correlation between the architecture’s test accuracy and its
$\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$, how to build an efficient
NAS framework on top of them? We motivate this section by addressing two
questions:

1\. How to combine $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$
together, with a good explicit trade-off?

We first need to turn the two measurements $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$ into one combined function, based on which we can rank
architectures. As seen in Figure 1 and 3, the magnitudes of
$\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$ differ much. To avoid one
overwhelming the other numerically, one possible remedy is normalization; but
we cannot pre-know the ranges nor the value distributions of
$\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$, before computing them over
a search space. In order to make our combined function well defined before
search and agnostic to the search space, instead of using the numerical values
of $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$, we could refer to their
relative rankings. Specifically, each time by comparing the sampled set of
architectures peer-to-peer, we can directly sum up the two relative rankings
of $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$ as the selection
criterion. The equal-weight summation treats trainability and expressivity
with the same importance conceptually111We tried some weighted summations of
the two, and find their equal-weight summation to perform the best. and
delivers the best empirical result: we thus choose it as our default combined
function. We also tried some other means to combine the two, and the ablation
studies can be found in Appendix D.2.

2\. How to search more efficiently?

Sampling-based methods like reinforcement learning or evolution can use
rankings as the reward or filtering metric. However, they are inefficient,
especially for complex cell-based search space. Consider a network stacked by
repeated cells (directed acyclic graphs) (Zoph et al., 2018; Liu et al.,
2018b). Each cell has $E$ edges, and on each edge we only select one operator
out of $|\mathcal{O}|$ ($\mathcal{O}$ is the set of operator candidates).
There are $|\mathcal{O}|^{E}$ unique cells, and for sampling-based methods,
$\gamma\cdot|\mathcal{O}|^{E}$ networks have to be sampled during the search.
The ratio $\gamma$ can be interpreted as the sampling efficiency: a method
with small $\gamma$ can find good architectures faster. However, the search
time cost of sampling-based methods still scales up with the size of the
search space, i.e., $|\mathcal{O}|^{E}$.

Inspired by recent works on pruning-from-scratch (Lee et al., 2018; Wang et
al., 2020), we propose a pruning-by-importance NAS mechanism to quickly shrink
the search possibilities and boost the efficiency further, reducing the cost
from $|\mathcal{O}|^{E}$ to $|\mathcal{O}|\cdot E$. Specifically, we start the
search with a super-network $\mathcal{N}_{0}$ composed of all possible
operators and edges. In the outer loop, for every round we prune one operator
on each edge. The outer-loop stops when the current supernet $\mathcal{N}_{t}$
is a single-path network222Different search spaces may have different criteria
for the single-path network. In NAS-Bench201 (Dong & Yang, 2020) each edge
only keeps one operator at the end of the search, while in DARTS space (Liu et
al., 2018b) there are two operators on each edge in the searched network.,
i.e., the algorithm will return us the final searched architecture. For the
inner-loop, we measure the change of $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$ before and after pruning each individual operator, and
assess its importance using the sum of two ranks. We order all currently
available operators in terms of their importance, and prune the lowest-
importance operator on each edge.

The whole pruning process is extremely fast. As we will demonstrate later, our
approach is principled and can be applied to different spaces without making
any modifications. This pruning-by-importance mechanism may also be extended
to indicators beyond $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$. We
summarize our training-free and pruning-based NAS framework, TE-NAS, in
Algorithm 1.

1 Input: supernet $\mathcal{N}_{0}$ stacked by cells, each cell has $E$ edges,
each edge has $|\mathcal{O}|$ operators, step $t=0$.

2 while  _$\mathcal{N}_{t}$ is not a single-path network_ do

3 for  _each operator $o_{j}$ in $\mathcal{N}_{t}$_ do

4
$\Delta\kappa_{t,o_{j}}=\kappa_{\mathcal{N}_{t}}-\kappa_{\mathcal{N}_{t}\backslash
o_{j}}$ $\triangleright$ the higher $\Delta\kappa_{t,o_{j}}$ the more likely
we will prune $o_{j}$

5 $\Delta R_{t,o_{j}}=R_{\mathcal{N}_{t}}-R_{\mathcal{N}_{t}\backslash o_{j}}$
$\triangleright$ the lower $\Delta R_{t,o_{j}}$ the more likely we will prune
$o_{j}$

6

7 Get importance by $\kappa_{\mathcal{N}}$: $s_{\kappa}(o_{j})=$ index of
$o_{j}$ in descendingly sorted list
$[\Delta\kappa_{t,o_{1}},...,\Delta\kappa_{t,o_{|\mathcal{N}_{t}|}}]$

8 Get importance by $R_{\mathcal{N}}$: $s_{R}(o_{j})=$ index of $o_{j}$ in
ascendingly sorted list $[\Delta R_{t,o_{1}},...,\Delta
R_{t,o_{|\mathcal{N}_{t}|}}]$

9 Get importance $s(o_{j})=s_{\kappa}(o_{j})+s_{R}(o_{j})$

10 $\mathcal{N}_{t+1}=\mathcal{N}_{t}$

11 for  _each edge $e_{i}$, $i=1,...,E$_ do

12 $j^{*}=\operatorname*{arg\,min}_{j}\\{s(o_{j}):o_{j}\in e_{i}\\}$
$\triangleright$ find the operator with greatest importance on each edge.

13 $\mathcal{N}_{t+1}=\mathcal{N}_{t+1}\backslash o_{j^{*}}$

14 $t=t+1$

return _Pruned single-path network $\mathcal{N}_{t}$._

Algorithm 1 TE-NAS: Training-free Pruning-based NAS via Ranking of
$\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$.

####  3.2.1 Visualization of Search Process

Figure 5: Pruning trajectory on NAS-Bench-201 (top) and DARTs search space
(bottom). Number “0” indicates the supernet $\mathcal{N}_{0}$ before any
pruning, which is of high expressivity but poor trainability.

TE-NAS benefits us towards a better understanding of the search process. We
can analyze the trajectory of $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$ during the search. It is worth noting that our
starting point $\mathcal{N}_{0}$, the un-pruned supernet, is assumed to be of
the highest expressivity (as it is composed of all operators in the search
space and has the largest number of parameters and ReLU functions). However,
it has poor trainability, as people find many engineering techniques are
required to effectively training the supernet (Yu et al., 2020a; b).
Therefore, during pruning we are expecting to strengthen the trainability of
the supernet, while retaining its expressivity as much as possible.

As we observe in Figure 5, the supernet $\mathcal{N}$ is first pruned by
quickly reducing $\kappa_{\mathcal{N}}$, i.e., increasing the network’s
trainability. After that, as the improvement of $\kappa_{\mathcal{N}}$ is
almost plateaued, the method carefully fine-tunes the architecture without
sacrificing too much expressivity $\hat{R}_{\mathcal{N}}$.

##  4 Experiments

In this section, we evaluate our TE-NAS on two search spaces: NAS-Bench-201
(Dong & Yang, 2020) and DARTS (Liu et al., 2018b). Search and training
protocols are summarized in Appendix A. Our code is available at:
https://github.com/VITA-Group/TENAS.

###  4.1 Results on NAS-Bench-201

NAS-Bench-201 (Dong & Yang, 2020) provides a standard cell-based search space
(containing 15,625 architectures) and a database of architecture’s performance
evaluated under a unified protocol. The network’s test accuracy can be
directly obtained by querying the database, which facilitates people to focus
on studying NAS algorithms without network evaluation. NAS-Bench-201 supports
three datasets (CIFAR-10, CIFAR-100, ImageNet-16-120 (Chrabaszcz et al.,
2017)). The operation space contains none (zero), skip connection,
conv$1\times 1$, conv$3\times 3$ convolution, and average pooling $3\times 3$.
We refer to their paper for details of the space. Our search is dataset-
specific, i.e. the search and evaluation are conducted on the same dataset.

Table 1: Comparison with state-of-the-art NAS methods on NAS-Bench-201. Test
accuracy with mean and deviation are reported. “optimal” indicates the best
test accuracy achievable in NAS-Bench-201 search space.

Architecture | CIFAR-10 | CIFAR-100 | ImageNet-16-120 |  | Search Cost
---
(GPU sec.)
| Search
---
Method
ResNet (He et al., 2016) | 93.97 | 70.86 | 43.63 | - | -
RSPS (Li & Talwalkar, 2020) | $87.66(1.69)$ | $58.33(4.34)$ | $31.14(3.88)$ | 8007.13 | random
ENAS (Pham et al., 2018) | $54.30(0.00)$ | $15.61(0.00)$ | $16.32(0.00)$ | 13314.51 | RL
DARTS (1st) (Liu et al., 2018b) | $54.30(0.00)$ | $15.61(0.00)$ | $16.32(0.00)$ | 10889.87 | gradient
DARTS (2nd) (Liu et al., 2018b) | $54.30(0.00)$ | $15.61(0.00)$ | $16.32(0.00)$ | 29901.67 | gradient
GDAS (Dong & Yang, 2019) | $93.61(0.09)$ | $70.70(0.30)$ | $41.84(0.90)$ | 28925.91 | gradient
NAS w.o. Training (Mellor et al., 2020) | $91.78(1.45)$ | $67.05(2.89)$ | $37.07(6.39)$ | 4.8 | training-free
TE-NAS (ours) | $\bf{93.9(0.47)}$ | $\bf{71.24(0.56)}$ | $\bf{42.38(0.46)}$ | 1558 | training-free
Optimal | 94.37 | 73.51 | 47.31 | - | -

We run TE-NAS for four independent times with different random seeds, and
report the mean and standard deviation in Table 1. We can see that TE-NAS
achieves the best accuracy on all three datasets, and largely reduces the
search cost ($5\times\sim 19\times$ reduction). Although Mellor et al. (2020)
requires even less search time (by only sampling 25 architectures), they
suffer from much inferior accuracy performance, with notably larger deviations
across different search rounds.

###  4.2 Results on CIFAR-10 with DARTs Search Space

Table 2: Comparison with state-of-the-art NAS methods on CIFAR-10.

Architecture |  | Test Error
---
(%)
| Params
---
(M)
| Search Cost
---
(GPU days)
| Search
---
Method
AmoebaNet-A (Real et al., 2019) | $3.34(0.06)$ | 3.2 | 3150 | evolution
PNAS (Liu et al., 2018a)$\star$ | $3.41(0.09)$ | 3.2 | 225 | SMBO
ENAS (Pham et al., 2018) | 2.89 | 4.6 | 0.5 | RL
NASNet-A (Zoph et al., 2018) | 2.65 | 3.3 | 2000 | RL
DARTS (1st) (Liu et al., 2018b) | $3.00(0.14)$ | 3.3 | 0.4 | gradient
DARTS (2nd) (Liu et al., 2018b) | $2.76(0.09)$ | 3.3 | 1.0 | gradient
SNAS (Xie et al., 2018) | $2.85(0.02)$ | 2.8 | 1.5 | gradient
GDAS (Dong & Yang, 2019) | 2.82 | 2.5 | 0.17 | gradient
BayesNAS (Zhou et al., 2019) | $2.81(0.04)$ | 3.4 | 0.2 | gradient
ProxylessNAS (Cai et al., 2018)$\dagger$ | 2.08 | 5.7 | 4.0 | gradient
P-DARTS (Chen et al., 2019) | 2.50 | 3.4 | 0.3 | gradient
PC-DARTS (Xu et al., 2019) | $2.57(0.07)$ | 3.6 | 0.1 | gradient
SDARTS-ADV (Chen & Hsieh, 2020) | $2.61(0.02)$ | 3.3 | 1.3 | gradient
TE-NAS (ours) | $2.63(0.064)$ | 3.8 | 0.05$\ddagger$ | training-free

  * $\star$

No cutout augmentation.

  * $\dagger$

Different space: PyramidNet (Han et al., 2017) as the backbone.

  * $\ddagger$

Recorded on a single GTX 1080Ti GPU.

##### Architecture Space

The DARTs operation space $\mathcal{O}$ contains eight choices: none (zero),
skip connection, separable convolution $3\times 3$ and $5\times 5$, dilated
separable convolution $3\times 3$ and $5\times 5$, max pooling $3\times 3$,
average pooling $3\times 3$. Following previous works (Liu et al., 2018b; Chen
et al., 2019; Xu et al., 2019), for evaluation phases, we stack 20 cells to
compose the network and set the initial channel number as 36. We place the
reduction cells at the 1/3 and 2/3 of the network and each cell consists of
six nodes.

##### Results

We run TE-NAS for four independent times with different random seeds, and
report the mean and standard deviation. Table 2 summarizes the performance of
TE-NAS compared with other popular NAS methods. TE-NAS achieves a test error
of 2.63%, ranking among the top of recent NAS results, but meanwhile largely
reduces the search cost to only 0.05 GPU-day. ProxylessNAS achieves the lowest
test error, but it searches on a different space with a much longer search
time and has a larger model size. Besides, Mellor et al. (2020) did not extend
to their Jacobian-based framework to DARTs search space for CIFAR-10 or
ImageNet classification.

###  4.3 Results on ImageNet with DARTs Search Space

##### Architecture Space

Following previous works (Xu et al., 2019; Chen et al., 2019), the
architecture for ImageNet is slightly different from that for CIFAR-10. During
retraining evaluation, the network is stacked with 14 cells with the initial
channel number set to 48, and we follow the mobile setting to control the
FLOPs not exceed 600 MB by adjusting the channel number. The spatial
resolution is downscaled from $224\times 224$ to $28\times 28$ with the first
three convolution layers of stride 2.

##### Results

As shown in Table 3, we achieve a top-1/5 test error of 24.5%/7.5%, achieving
competitive performance with recent state-of-the-art works in the ImageNet
mobile setting. However, TE-NAS only cost four GPU hours with only one 1080Ti.
Searching on ImageNet takes a longer time than on CIFAR-10 due to the larger
input size and more network parameters.

Table 3: Comparison with state-of-the-art NAS methods on ImageNet under the
mobile setting.

Architecture | Test Error(%) |  Params (M) |  Search Cost (GPU days) |  Search Method
---|---|---|---|---
top-1 | top-5
NASNet-A (Zoph et al., 2018) | 26.0 | 8.4 | 5.3 | 2000 | RL
AmoebaNet-C (Real et al., 2019) | 24.3 | 7.6 | 6.4 | 3150 | evolution
PNAS (Liu et al., 2018a) | 25.8 | 8.1 | 5.1 | 225 | SMBO
MnasNet-92 (Tan et al., 2019) | 25.2 | 8.0 | 4.4 | - | RL
DARTS (2nd) (Liu et al., 2018b) | 26.7 | 8.7 | 4.7 | 4.0 | gradient
SNAS (mild) (Xie et al., 2018) | 27.3 | 9.2 | 4.3 | 1.5 | gradient
GDAS (Dong & Yang, 2019) | 26.0 | 8.5 | 5.3 | 0.21 | gradient
BayesNAS (Zhou et al., 2019) | 26.5 | 8.9 | 3.9 | 0.2 | gradient
P-DARTS (CIFAR-10) (Chen et al., 2019) | 24.4 | 7.4 | 4.9 | 0.3 | gradient
P-DARTS (CIFAR-100) (Chen et al., 2019) | 24.7 | 7.5 | 5.1 | 0.3 | gradient
PC-DARTS (CIFAR-10) (Xu et al., 2019) | 25.1 | 7.8 | 5.3 | 0.1 | gradient
TE-NAS (ours) | 26.2 | 8.3 | 6.3 | 0.05 | training-free
PC-DARTS (ImageNet) (Xu et al., 2019)$\dagger$ | 24.2 | 7.3 | 5.3 | 3.8 | gradient
ProxylessNAS (GPU) (Cai et al., 2018)$\dagger$ | 24.9 | 7.5 | 7.1 | 8.3 | gradient
TE-NAS (ours)$\dagger$ | 24.5 | 7.5 | 5.4 | 0.17 | training-free

  * $\dagger$

The architecture is searched on ImageNet, otherwise it is searched on CIFAR-10
or CIFAR-100.

##  5 Conclusion

The key questions in Neural Architecture Search (NAS) are “what are good
architectures” and “how to find them”. Validation loss or accuracy are
possible answers but not enough, due to their search bias and heavy evaluation
cost. Our work demonstrates that two theoretically inspired indicators, the
spectrum of NTK and the number of linear regions, not only strongly correlate
with the network’s performance, but also benefit the reduced search cost and
decoupled analysis of the network’s trainability and expressivity. Without
involving any training, our TE-NAS achieve competitive NAS performance with
minimum search time. We for the first time bridge the gap between the
theoretic findings of deep neural networks and real-world NAS applications,
and we encourage the community to further explore more meaningful network
properties so that we will have a better understanding of good architectures
and how to search them.

## Acknowledgement

This work is supported in part by the NSF Real-Time Machine Learning program
(Award Number: 2053279), and the US Army Research Office Young Investigator
Award (W911NF2010240).

## References

  * Bender et al. (2018) Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le.  Understanding and simplifying one-shot architecture search.  In _International Conference on Machine Learning_ , pp. 549–558, 2018.
  * Brock et al. (2017) Andrew Brock, Theodore Lim, James M Ritchie, and Nick Weston.  Smash: one-shot model architecture search through hypernetworks.  _arXiv preprint arXiv:1708.05344_ , 2017.
  * Burkholz & Dubatovka (2019) Rebekka Burkholz and Alina Dubatovka.  Initialization of relus for dynamical isometry.  In _Advances in Neural Information Processing Systems_ , pp. 2385–2395, 2019.
  * Cai et al. (2018) Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  _arXiv preprint arXiv:1812.00332_ , 2018.
  * Chen et al. (2018) Liang-Chieh Chen, Maxwell Collins, Yukun Zhu, George Papandreou, Barret Zoph, Florian Schroff, Hartwig Adam, and Jon Shlens.  Searching for efficient multi-scale architectures for dense image prediction.  In _Advances in Neural Information Processing Systems_ , pp. 8699–8710, 2018.
  * Chen et al. (2020a) Wuyang Chen, Xinyu Gong, Xianming Liu, Qian Zhang, Yuan Li, and Zhangyang Wang.  Fasterseg: Searching for faster real-time semantic segmentation.  In _International Conference on Learning Representations_ , 2020a.
  * Chen & Hsieh (2020) Xiangning Chen and Cho-Jui Hsieh.  Stabilizing differentiable architecture search via perturbation-based regularization.  _arXiv preprint arXiv:2002.05283_ , 2020.
  * Chen et al. (2019) Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian.  Progressive differentiable architecture search: Bridging the depth gap between search and evaluation.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1294–1303, 2019.
  * Chen et al. (2020b) Xin Chen, Lingxi Xie, Jun Wu, Longhui Wei, Yuhui Xu, and Qi Tian.  Fitting the search space of weight-sharing nas with graph convolutional networks.  _arXiv preprint arXiv:2004.08423_ , 2020b.
  * Chizat et al. (2019) Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  2019\.
  * Chrabaszcz et al. (2017) Patryk Chrabaszcz, Ilya Loshchilov, and Frank Hutter.  A downsampled variant of imagenet as an alternative to the cifar datasets, 2017.
  * Dai et al. (2019) Xiaoliang Dai, Peizhao Zhang, Bichen Wu, Hongxu Yin, Fei Sun, Yanghan Wang, Marat Dukhan, Yunqing Hu, Yiming Wu, Yangqing Jia, et al.  Chamnet: Towards efficient network design through platform-aware model adaptation.  In _Proceedings of the IEEE Conference on computer vision and pattern recognition_ , pp. 11398–11407, 2019.
  * Dong & Yang (2019) Xuanyi Dong and Yi Yang.  Searching for a robust neural architecture in four gpu hours.  In _Proceedings of the IEEE Conference on computer vision and pattern recognition_ , pp. 1761–1770, 2019.
  * Dong & Yang (2020) Xuanyi Dong and Yi Yang.  Nas-bench-102: Extending the scope of reproducible neural architecture search.  _arXiv preprint arXiv:2001.00326_ , 2020.
  * Dong et al. (2020) Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys.  Nats-bench: Benchmarking nas algorithms for architecture topology and size.  _arXiv preprint arXiv:2009.00437_ , 2020.
  * Fu et al. (2020) Yonggan Fu, Wuyang Chen, Haotao Wang, Haoran Li, Yingyan Lin, and Zhangyang Wang.  Autogan-distiller: Searching to compress generative adversarial networks.  In _International Conference on Machine Learning_ , pp. 3292–3303. PMLR, 2020.
  * Giryes et al. (2016) Raja Giryes, Guillermo Sapiro, and Alex M Bronstein.  Deep neural networks with random gaussian weights: A universal classification strategy?  _IEEE Transactions on Signal Processing_ , 64(13):3444–3457, 2016.
  * Gong et al. (2019) Xinyu Gong, Shiyu Chang, Yifan Jiang, and Zhangyang Wang.  Autogan: Neural architecture search for generative adversarial networks.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 3224–3234, 2019.
  * Guo et al. (2019) Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun.  Single path one-shot neural architecture search with uniform sampling.  _arXiv preprint arXiv:1904.00420_ , 2019.
  * Han et al. (2017) Dongyoon Han, Jiwhan Kim, and Junmo Kim.  Deep pyramidal residual networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 5927–5935, 2017.
  * Hanin & Nica (2019) Boris Hanin and Mihai Nica.  Finite depth and width corrections to the neural tangent kernel.  _arXiv preprint arXiv:1909.05989_ , 2019.
  * Hanin & Rolnick (2019a) Boris Hanin and David Rolnick.  Complexity of linear regions in deep networks.  _arXiv preprint arXiv:1901.09021_ , 2019a.
  * Hanin & Rolnick (2019b) Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns.  In _Advances in Neural Information Processing Systems_ , pp. 361–370, 2019b.
  * Hayou et al. (2019) Soufiane Hayou, Arnaud Doucet, and Judith Rousseau.  On the impact of the activation function on deep neural networks training.  _arXiv preprint arXiv:1902.06853_ , 2019.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 1026–1034, 2015.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hornik et al. (1989) Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In _Advances in neural information processing systems_ , pp. 8571–8580, 2018.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pp. 1097–1105, 2012.
  * Lee et al. (2019) Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  In _Advances in neural information processing systems_ , pp. 8572–8583, 2019.
  * Lee et al. (2018) Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr.  Snip: Single-shot network pruning based on connection sensitivity.  _arXiv preprint arXiv:1810.02340_ , 2018.
  * Li et al. (2020a) Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem.  Sgas: Sequential greedy architecture search.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 1620–1630, 2020a.
  * Li & Talwalkar (2020) Liam Li and Ameet Talwalkar.  Random search and reproducibility for neural architecture search.  In _Uncertainty in Artificial Intelligence_ , pp. 367–377. PMLR, 2020.
  * Li et al. (2020b) Yanxi Li, Minjing Dong, Yunhe Wang, and Chang Xu.  Neural architecture search in a proxy validation loss landscape.  In _International Conference on Machine Learning_ , pp. 5853–5862. PMLR, 2020b.
  * Li et al. (2020c) Zhihang Li, Teng Xi, Jiankang Deng, Gang Zhang, Shengzhao Wen, and Ran He.  Gp-nas: Gaussian process based neural architecture search.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11933–11942, 2020c.
  * Liang et al. (2019) Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li.  Darts+: Improved differentiable architecture search with early stopping.  _arXiv preprint arXiv:1909.06035_ , 2019.
  * Liu et al. (2018a) Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy.  Progressive neural architecture search.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pp. 19–34, 2018a.
  * Liu et al. (2019) Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei.  Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 82–92, 2019.
  * Liu et al. (2018b) Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ , 2018b.
  * Luo et al. (2018) Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Yan Liu.  Neural architecture optimization.  In _Advances in neural information processing systems_ , pp. 7816–7827, 2018.
  * Luo et al. (2020) Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu.  Semi-supervised neural architecture search.  _arXiv preprint arXiv:2002.10389_ , 2020.
  * Mellor et al. (2020) Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley.  Neural architecture search without training.  _arXiv preprint arXiv:2006.04647_ , 2020.
  * Montúfar (2017) Guido Montúfar.  Notes on the number of linear regions of deep neural networks.  _Sampling Theory Appl., Tallinn, Estonia, Tech. Rep_ , 2017.
  * Pham et al. (2018) Hieu Pham, Melody Y Guan, Barret Zoph, Quoc V Le, and Jeff Dean.  Efficient neural architecture search via parameter sharing.  _arXiv preprint arXiv:1802.03268_ , 2018.
  * Raghu et al. (2017) Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In _international conference on machine learning_ , pp. 2847–2854. PMLR, 2017.
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In _Proceedings of the aaai conference on artificial intelligence_ , volume 33, pp. 4780–4789, 2019.
  * Serra et al. (2018) Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam.  Bounding and counting linear regions of deep neural networks.  In _International Conference on Machine Learning_ , pp. 4558–4566. PMLR, 2018.
  * Shin & Karniadakis (2020) Yeonjong Shin and George Em Karniadakis.  Trainability of relu networks and data-dependent initialization.  _Journal of Machine Learning for Modeling and Computing_ , 1(1), 2020.
  * Shu et al. (2019) Yao Shu, Wei Wang, and Shaofeng Cai.  Understanding architectures learnt by cell-based neural architecture search.  In _International Conference on Learning Representations_ , 2019.
  * Siems et al. (2020) Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter.  Nas-bench-301 and the case for surrogate benchmarks for neural architecture search.  _arXiv preprint arXiv:2008.09777_ , 2020.
  * Simonyan & Zisserman (2014) Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Szegedy et al. (2015) Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1–9, 2015.
  * Tan et al. (2019) Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le.  Mnasnet: Platform-aware neural architecture search for mobile.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 2820–2828, 2019.
  * Tan et al. (2020) Mingxing Tan, Ruoming Pang, and Quoc V Le.  Efficientdet: Scalable and efficient object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10781–10790, 2020.
  * Wang et al. (2020) Chaoqi Wang, Guodong Zhang, and Roger Grosse.  Picking winning tickets before training by preserving gradient flow.  _arXiv preprint arXiv:2002.07376_ , 2020.
  * Wen et al. (2019) Wei Wen, Hanxiao Liu, Hai Li, Yiran Chen, Gabriel Bender, and Pieter-Jan Kindermans.  Neural predictor for neural architecture search.  _arXiv preprint arXiv:1912.00848_ , 2019.
  * Xiao et al. (2019) Lechao Xiao, Jeffrey Pennington, and Samuel S Schoenholz.  Disentangling trainability and generalization in deep learning.  _arXiv preprint arXiv:1912.13053_ , 2019.
  * Xie et al. (2017) Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1492–1500, 2017.
  * Xie et al. (2018) Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin.  Snas: stochastic neural architecture search.  _arXiv preprint arXiv:1812.09926_ , 2018.
  * Xiong et al. (2020) Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao.  On the number of linear regions of convolutional neural networks.  _arXiv preprint arXiv:2006.00978_ , 2020.
  * Xu et al. (2019) Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong.  Pc-darts: Partial channel connections for memory-efficient architecture search.  In _International Conference on Learning Representations_ , 2019.
  * Yang & Schoenholz (2017) Ge Yang and Samuel Schoenholz.  Mean field residual networks: On the edge of chaos.  In _Advances in neural information processing systems_ , pp. 7103–7114, 2017.
  * Yang (2019) Greg Yang.  Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation.  _arXiv preprint arXiv:1902.04760_ , 2019.
  * Yang et al. (2020a) Zhaohui Yang, Yunhe Wang, Xinghao Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu.  Cars: Continuous evolution for efficient neural architecture search.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020a.
  * Yang et al. (2020b) Zhaohui Yang, Yunhe Wang, Dacheng Tao, Xinghao Chen, Jianyuan Guo, Chunjing Xu, Chao Xu, and Chang Xu.  Hournas: Extremely fast neural architecture search through an hourglass lens.  _arXiv preprint arXiv:2005.14446_ , 2020b.
  * Yu et al. (2020a) Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le.  Bignas: Scaling up neural architecture search with big single-stage models.  _arXiv preprint arXiv:2003.11142_ , 2020a.
  * Yu et al. (2020b) Kaicheng Yu, Rene Ranftl, and Mathieu Salzmann.  How to train your super-net: An analysis of training heuristics in weight-sharing nas.  _arXiv preprint arXiv:2003.04276_ , 2020b.
  * Yu et al. (2020c) Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann.  Evaluating the search phase of neural architecture search.  In _ICLR_ , 2020c.
  * Zhou et al. (2019) Hongpeng Zhou, Minghao Yang, Jun Wang, and Wei Pan.  Bayesnas: A bayesian approach for neural architecture search.  _arXiv preprint arXiv:1905.04919_ , 2019.
  * Zoph & Le (2016) Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  _arXiv preprint arXiv:1611.01578_ , 2016.
  * Zoph et al. (2018) Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 8697–8710, 2018.

##  Appendix A Implementation Details

For $\kappa_{\mathcal{N}}$ we sample one mini-batch of size 32 from the
training set, and calculate
$\hat{\Theta}(\bm{x},\bm{x}^{\prime})=J(\bm{x})J(\bm{x}^{\prime})^{T}$. For
$\hat{R}_{\mathcal{N}}$ we sample 5000 images, forward them through the
network, and collect the activation patterns from all ReLU layers. The
calculation of both $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$ are
repeated three times in all experiments, where each time the network weights
are randomly drawn from Kaiming Norm Initialization (He et al., 2015) without
involving any training (network weights are fixed).

Our retraining settings (after search) follow previous works (Xu et al., 2019;
Chen et al., 2019; Chen & Hsieh, 2020). On CIFAR-10, we train the searched
network with cutout regularization of length 16, drop-path (Zoph et al., 2018)
with probability as 0.3, and an auxiliary tower of weight 0.4. On ImageNet, we
also use label smoothing during training. On both CIFAR-10 and ImageNet, the
network is optimized by an SGD optimizer with cosine annealing, with learning
rate initialized as 0.025 and 0.5, respectively.

##  Appendix B Searched Architecture

We visualize the searched normal and reduction cells in figure 6 and 7, which
is directly searched on CIFAR-10 and ImageNet respectively.

(a) Normal Cell (b) Reduction Cell

Figure 6: Normal and Reduction cells discovered by TE-NAS on CIFAR-10.

(a) Normal Cell (b) Reduction Cell

Figure 7: Normal and Reduction cells discovered by TE-NAS on imageNet.

##  Appendix C Depth and Width Preference of $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$ in DARTs Space

To analyze the impact of different architectures on trainability and
expressivity in DARTs search space, we visualize $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$ with different depths and width. Following Shu et al.
(2019), the depth of a cell is defined as the number of connections on the
longest path from input nodes to the output node, and the width of a cell is
the summation of the edges of the intermediate nodes that are connected to the
input nodes. We randomly sample 20,000 architectures in DARTs space, and plot
the visualizations in Figure 8. Good architectures should exhibit low
$\kappa_{\mathcal{N}}$ (good trainability, blue dots in Figure 8(a)) and high
$\hat{R}_{\mathcal{N}}$ (powerful expressivity, red dots in Figure 8(b)).
Therefore, $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$ tell us that in
DARTs space shallow but wide cells are preferred to favor both trainability
and expressivity. This conclusion matches the findings by Shu et al. (2019):
existing NAS algorithms tend to favor architectures with wide and shallow cell
structures, which enjoy fast convergence with smooth loss landscape and
accurate gradient information.

(a) $\kappa_{\mathcal{N}}$

(b) $\hat{R}_{\mathcal{N}}$

Figure 8: Depth and width preference of (a) $\kappa_{\mathcal{N}}$ and (b)
$\hat{R}_{\mathcal{N}}$ on DARTs Search Space.

##  Appendix D More Ablation Studies

###  D.1 Search with only $\kappa_{\mathcal{N}}$ or $\hat{R}_{\mathcal{N}}$

As we observed in Table 4, searching with only $\kappa_{\mathcal{N}}$ or
$\hat{R}_{\mathcal{N}}$ leads to inferior performance, which indicates the
importance of maintaining both trainability and expressivity during the
search.

Table 4: Search with only $\kappa_{\mathcal{N}}$ or $\hat{R}_{\mathcal{N}}$ on CIFAR-100 in NAS-Bench-201 space. Methods | CIFAR-100 Test Accuracy
---|---
Prune with only $\kappa_{\mathcal{N}}$ | 69.25 (1.29)
Prune with only $\hat{R}_{\mathcal{N}}$ | 70.48 (0.29)
TE-NAS |  71.24 (0.56)

###  D.2 Different combination options for $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$

Pruning by $s(o_{j})=s_{\kappa}(o_{j})+s_{R}(o_{j})$ is not the only option
(see Algorithm 1). Here in this study we consider more:

  1. 1)

pruning by $s(o_{j})=\mathrm{min}(s_{\kappa}(o_{j}),s_{R}(o_{j}))$, i.e.,
pruning by the worst case.

  2. 2)

Pruninng by $s(o_{j})=\mathrm{max}(s_{\kappa}(o_{j}),s_{R}(o_{j}))$, i.e.,
pruning by the best case.

  3. 3)

pruning by summation of changes $\Delta\kappa_{t,o_{j}}+\Delta R_{t,o_{j}}$,
i.e., directly use the numerical values of the changes.

As we observed in Table 5, our TE-NAS stands out of all options. This means a
good trade-off between $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$ are
important, and also the ranking strategy is better than directly using
numerical values.

Table 5: Search with only $\kappa_{\mathcal{N}}$ or $\hat{R}_{\mathcal{N}}$ on CIFAR-100 in NAS-Bench-201 space. Methods | CIFAR-100 Test Accuracy
---|---
Prune by $s(o_{j})=\mathrm{min}(s_{\kappa}(o_{j}),s_{R}(o_{j}))$ | 70.75 (0.73)
Prune by $s(o_{j})=\mathrm{max}(s_{\kappa}(o_{j}),s_{R}(o_{j}))$ | 70.33 (1.09)
Prune by $\Delta\kappa_{t,o_{j}}+\Delta R_{t,o_{j}}$ | 70.47 (0.68)
Prune by $s(o_{j})=s_{\kappa}(o_{j})+s_{R}(o_{j})$ (TE-NAS) |  71.24 (0.56)

###  D.3 Correlation between Test Accuracy and Combination of
$\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$

Figure 9: Summation of ranking of $\kappa_{\mathcal{N}}$ and
$\hat{R}_{\mathcal{N}}$ exhibits stronger (negative) correlation with the test
accuracy of architectures in NAS-Bench201 (Dong & Yang, 2020).

Figure 9 indicates that by using the summation of the ranking of
both$\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$, the combined metric
achieves a much higher correlation with the test accuracy. The reason can be
explained by Figure 4, as $\kappa_{\mathcal{N}}$ and $\hat{R}_{\mathcal{N}}$
prefers different operators in terms of trainability and Expressivity. Their
combination can filter out bad architectures in both aspects and strongly
correlate with networks’ final performance.

##  Appendix E Generalization v.s. Test Accuracy

Figure 10: The correlation between test accuracy and the training accuracy in
NAS-Bench201 (Dong & Yang, 2020).

Conceptually, the generalization gap is the difference between a model’s
performance on training data and its performance on unseen data drawn from the
same distribution (e.g., testing set). In comparison, the two indicators
$\kappa_{\mathcal{N}}$ (trainability) and $R_{\mathcal{N}}$ (expressiveness)
of a network determine how well the training set could be fit (i.e., training
set accuracy), and do not directly indicate its generalization gap (or test
set accuracy). Indeed, probing generalization of an untrained network at its
initialization is a daunting, open challenge that seems to go beyond the
current theory scope.

In NAS, we are searching for the architecture with the best test accuracy. As
shown in Figure 10, in NAS-Bench201 the training accuracy strongly correlates
with test accuracy. This also seems to be a result of the current standard
search space design that could have implicitly excluded severe overfitting.
This explains why $\kappa_{\mathcal{N}}$ and $R_{\mathcal{N}}$, which only
focuses on trainability and expressiveness during training, can still achieve
good search results of test accuracy.