Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature
Authors: Rohan Asthana
Joschua Conrad
Maurits Ortmanns
Vasileios Belagiannis
Venue: Accepted by TMLR ()

Abstract: Zero-shot Neural Architecture Search (NAS) typically optimises the architecture search process by exploiting the network or gradient properties at initialisation through zero-cost proxies. The existing proxies often rely on labelled data, which is usually unavailable in real-world settings. Furthermore, the majority of the current methods focus either on optimising the convergence and generalisation attributes or solely on the expressivity of the network architectures. To address both limitations, we first demonstrate how channel collinearity affects the convergence and generalisation properties of a neural network. Then, by incorporating the convergence, generalisation and expressivity in one approach, we propose a zero-cost proxy that omits the requirement of labelled data for its computation. In particular, we leverage the Singular Value Decomposition (SVD) of the neural network layer features and the extrinsic curvature of the network output to design our proxy. As a result, the proposed proxy is formulated as the simplified harmonic mean of the logarithms of two key components: the sum of the inverse of the feature condition number and the extrinsic curvature of the network output. Our approach enables accurate prediction of network performance on test data using only a single label-free data sample. Our extensive evaluation includes a total of six experiments, including the Convolutional Neural Network (CNN) search space, i.e. DARTS and the Transformer search space, i.e. AutoFormer. The proposed proxy demonstrates a superior performance on multiple correlation benchmarks, including NAS-Bench-101, NAS-Bench-201, and TransNAS-Bench-101-micro; as well as on the NAS task within the DARTS and the AutoFormer search space, all while being notably efficient. The code is available at https://github.com/rohanasthana/Dextr.

Published in Transactions on Machine Learning Research (08/2025)
Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature
Rohan Asthana
rohon.asthono@fou.de
Priedrich- Alennddee Universität Erlangen- Brlangen-Nümmbery Brlangen, Germany
Joschua Conrad
joschua. com.
Universität Ulm Ulm, Germany
Maurits Ortmanns
Universität Ulm Ulm, Germany
Vasileios Belagiannis
Universität Brlangen- Nirnberr
Brlangen, Germany
Reviewed on OpenReview: /ttp::///pprrevteeee net/ forum? XOuPof5DVV
Abstract
Zero-shot Neural Architecture Search (NAS) typically optimises the architecture search process by exploiting the network gradient properties at initialisation through zero-cost proxies. The existing proxies often rely on labelled data, which is usually unavailable in real- world settings. Furthermore, the majority of the current methods focus cither on optimising the convergence and generalisation attributes or solely on the expressivity of the netw architectures. To address both limitations, we first demonstrate how channel collinearity affects the convergence and generalisation properties of neural network. Then, by incor- porating the convergence, generalisation and expressivity in approach, propose vero-cost proxy that omils the requirement. of labelled data. for its computation. In par- ticular, we leverage the Singular Value Decomposition (SVD) of the neural network layer features and the extrinsic curvature of the network output to design our proxy. Our ap- proach enables accurate prediction network performance on test data using only a sin- gle label-free data sample. Our extensive evaluation includes a total of six experiments, including the Convolutional Neural Network (CNN) search space, i.e. DARTS and the Transformer search space, i.e. AutoFormer. The proposed proxy demonstrates superior performance multiple correlation benchmarks, including NAS-Bench- 101, NAS-Bench- 201, and TransNAS MaansNAA--enc-10---... 101-micro; well as on the NAS task within the DARTS and the AutoFormer search space, all while being notably elficient. The code is available al httpss/ggggtabbboo/////aaattttat
1 Introduction
Following the success of standard deep neural network architectures (He al.) 2016 Szogody al. 2015 LeCun al. 1998 Vaswani al.] (017)). the search for optimal network topologies, referred to as Neural Architecture Search (NAS), has gained significant attention in the past years. Search-based [Li & Talwalkar

---

Published in Transactions on Machine Learning Research (08/2025)
Validation Accuracy
80
60
25
40
20
22
28
Epoch
(a) (left) Scatter plot between the network performance and linear independence of feature maps (FMT). (right) Training loss curve for six networks sampled from NAS-Bench-201 CIFAR-10.
Accuracy-63.35
Accuracy=55 8%
Accuracy=32.89%
Low- Low- perforrfooiggg
Accuracy-90.2%% Accuracy-91.1%
Accuracy-90.499
High-performing
(b) Outputs six randomly initialised networks induced by a circular input pro- jected the first three principal components. The accuracies reported with respect to training on CIFAR-10.
Figure 1: Comparison of convergence, generalisation, and expressivity of low-performing and high-performing networks sampled from NAS-Bench-201 (Dong & Yang. 2020). (a-left): Generalisation: The linear inde- pendence of feature maps (FMI) is positively correlated to the validation accuracy and hence, generalisation of the network. (a-right): Convergence: The networks with high FMI (FMT>25) demonstrate faster con- vergence during training CIFAR-10. (b) Expressivity: The outputs of the nigh-performing networks projected on the first three principal components induced by an arbitrary cireular input are more curved than those of the low- oow-eerfrrmng networks. Hence, the low-performing networks are less expressive than the high-performing networks.
2020
White et al. 2021 reinforcement learning methods (Zoph & Le 2017 Tian et al. 2020). as well as evolutionary algorithms RRall al. 2019 Chu et al. 2020aa have originally been used to tackle this task. However, they suffer from heavy computational requirements due to the enormous search space. Generative methods (Lukasik et al. 20222 Asthana et. al.) 2024 An et al. (0224) alleviate this issue by deploying gradient- based learning of the search space through first-order methods. However, the requirement for architectural training data, including the performance of each architecture, poses serious challenge to the applicability of these methods in practice. Alternatively, zero-shot NAS eliminates the need for such an architecture dataset. This technique leverages the network structure and gradient properties close to initialisation (termed as zero- cost proxies) to predict the performance on a test set prior to its full training (Abdelfattah et al. 2021).
Normally, zero-cost proxies are either task/data agnostic, e.g. FLOPS or parameters, or fata-based Data- agnostic proxies evaluate architecture's potential without using any input data. They rely solely the
2

---

Published in Transactions on Machine Learning Research (08/2025)
network's structure to estimate the network performance. In contrast, data-based proxies estimate network performance by passing small batch of data through the network. While most of the data agnostic proxies (Tanaka et al. 2020 Lin et al. 2021 Li et al.) 2021b) fail to be consistent, most data-dependent proxies (Mellor et al. 2021 Abdelfattah et al. 2021) require labels for gradient computation, which are usually not
available in real-world scenarios. Thus, these drawbacks motivate the design of a zero-cost proxy independent of labelled data.
Another limitation of most current proxies is their focus performance attributes that they aim to optimise. Formally, network performance is analysed through three attributes, namely convergence, generalisation, and expressivity (Chen et al.) 2023). Convergence refers to how fast a network can converge to a minimum through gradient descent. Generalisation refers to how well a network trained on training data can generalise to unseen test data. Finally, expressivity indicates the complexity of functions that a network can estimate. In addition, the No Free Lunch theorem states that the most optimal network balances these attributes as it is practically impossible to minimise all three simultancously (Chen et al. 2023 Most zcro-cost proxies
focus either on convergence and generalisation aspects (Jiang al. 2023 Li el al. 2023 Yang al. 2023)
solely the expressivity characteristic (Lin et al. (2021). However, designing proxy by balancing all three attributes is an open challenge that is hardly addressed in the literature (Loe & HHm 2024). This is
important because while convergence and generalisation alone are sufficient to somewhat predict the network performance, the architectures searched through NAS methods utilising solely convergence and generalisation are inherently less expressive, either through their limited depth or their choice of operations (as observed in Appendix Section A.8). Hence, the No Free Lunch Theorem states that the best networks are the ones that have balanced convergence, generalisation and expressivity Chen et al. (2023). Therefore, to generate optimal architectures, zero-cost proxy balancing all three attributes is required.
To address the above shortcomings, we present zero-cost proxy that (i) operates without the need for labelled data, and (ii) balances convergence, generalisation, and expressivity of networks in one approach. To this end, we first demonstrate using Singular Value Decomposition (SVD) (Klema & Laub 1980) that the collinearity of feature maps negalively affects the training convergence rale and ceneralisation capabilities of Convolutional Neural Network (CNN). In other words, the convergence and generalisation of a CNN are positively correlated to the lincar independence of feature maps (FMI), as illustrated in Figure 1a. This makes intuitive sense CNN with limited width or repeated identical blocks is structurally constrained in its ability to decorrelate inputs, and hence its feature maps would exhibit high colinearity. Therefore, the given CNN would have poor convergence and generalisation. Next, we employ Riemannian geometry (Lee) 2006) to consider the relationship between the extrinsic curvature of the output and the expressivity of a network (Poole et al. 2016). Specifically, we utilize the fact that the expressivity of a network is related to how curved the output is when an input is fed into the network. This is visually illustrated in Figure 1b Based on the relationships related to convergence, generalisation, and expressivity, we propose cost-effective proxy, namely Dextr, which leverages the collinearity of layer feature maps and the extrinsic curvature of the output. As a result, Dextr accurately predicts the network performance on test data using just a single label-free data sample. Our evaluation shows the capabilities of our proxy by outperforming all existing zero-shot NAS methods on three standard tabular benchmarks, specifically NASS-Bechh 2019), MAS--Bnch-200 (Dong & Yang. 2020). and TransNASS BaeiA--Becc--ae Bench-micro (Duan et al.) 2021) benchmarks, and showing competitive performance in the NAS-Bench-300 (Zela et al., (022) benchmark. Additionally, we perform experiments within two search spaces: the DARTS search space (Liu et al. 2019) containing CNNs, and the AutoFormer search space (Chen al.) 2021b) containing Vision Transformers (VTTs) (Dosovitskiy let al. 2021). The architecture discovered through our proxy in these search spaces is then evaluated by training it on ImageNet (Deng et al., 2009) and its test performance is compared with bascline approaches. We demonstrate that the architecture found through our proxy outperforms the previous multi-shot and zero-shot NAS methods on ImageNet classification, all while maintaining minimal search time. We conduct a total of three ablation studies, where we analyse the stability of our approach, compare Dextr with a simple combination of existing proxies, and analyse contribution of individual layers. We additionally perform two experiments NATS-Bench-SS: (Dong al.) 2021 and MobileNet-v2 (Sandler et al. 2018 provided in the Appendix Section A.4 In summary, our contributions are follows:
(Ying el al.,
3

---

Published in Transactions on Machine Learning Research (08/2025)
We present the relationship between the collinearity of feature maps across a convolutional layer in network and the convergence and generalisation capabilities of the network.
By incorporating the convergence, generalisation, and expressivity in our proxy, we propose zero- cost proxy requiring one label-free data sample for its computation.
Our proposed proxy outperforms the existing methods three correlation benchmarks, i.e. NAS- (Dong & Yang 2020), and TransSAS-Bencch-O00 20021) as well as on the ImageNet (Deng et al. 2009) NAS task within the
Bench-101 (Ying et al.) 2019),
micro (Duan et al.)
DARTS (Liu et al. 2019 search space and the AutoFormer search space (Chen et al. 2021b).
2 Related Work
Multi-shot and Zero-Shot NAS
Traditional attempts to automate the design process of neural network
architectures, such as random search (Li & Talwalkar 2020), evolutionary approaches (Real et al.) 2019 Chu
et al. 2020a), reinforcement learning approaches (Zoph & Le 2017 Tian et al. 2020), and graddient-base Yang et al.)
approaches (Brock et al.
2018
2020a] Chen et al. 2021d], are considered rather slow due
to the requirement of training iterations at each search stop (Liu et al. 2019). More recent generative
methods (Lukasik et al. learning-baset techniques the architecture search space. For instance, [ukasik et al. (2022) employed a generator and surrogate predictor to accurately learn and sample from the architectural data distribution. Recently, similar to this direction, An et al. (2024) and Asthana et al. (2024) employed conditioned diffusion models to generate well-performing neural network architectures. However, the expensive training process of the generative models and the requirement of architectural training data limits the applicability of these approaches.
2022 Asthana et al.) 2024 An et al. 2024) addressed this limitation by employing
Alternatively, zero-shot NAS accelerates the rather costly architecture search process Li & Talwalkar, 2020;
White ct al. 2021 Zoph & Le 2017 Tian ct al., 2020: Real et al. 2019 Chu et al., 2020a by using network metrics at initialisation, known as zero-cost proxies. The concept. of zero-shot NAS was established by Mellor et al. 2021), who introduced the activation overlap between data points a proxy. Since then, various
zero-cost proxics (Loe ct al.] 2019 Lin ct al.] 2021 Chen et al. 2021c) have advanced the field, including Snip (Lee et al. 2019), Grasp /Wang et al. 2020), Synllow ('Tanaka et al. 2020), Fisher (Turner el al. 2020
and Jacob (Mellor et al. 2021). ), all proposed by Abdelfattah et al. (2021). Additionally, Li et al. 2023 have introduced ZiCo, which predicts network performance using the mean and standard deviation parameter gradients at initialisation. Unlike our approach, all these proxies rely on data labels for their computation.
In contrast, some previous works do not require data labels for performance estimation. For instance, NASWOT (Melor et al. 2021) analyses activation overlaps for network performance estimation. However, it only considers the expressivity of network and neglects the convergence and generalisation attributes.
Similarly, Zen (Lin et al.] 2021) considers the expressivity exclusively by utilising the network's Gaussian complexity. Conversely, McCo (Jiang et al.) 2023) omits the need for labels by calculating the minimum eigenvalue of the Pearson Correlation matrix. However, it solely focuses on the convergence and generalisation lisation aspects of the network, while neglecting the expressivity. To consider all three attributes, Chen et al. (2021c) utilised Neural Tangent Kernels (NTK) and the Number of Linear Regions (NLR) for efficient architecture scarch. More recently, AZ-NAS (Lee & Ham 2024 considers multiple network attributes like trainability, expressivily, progressivily, and complexity. However, they both require labels and backpropagation for their calculation. Following a more efficient direction, we propose a zero-cost proxy that further improves the performance without requiring labels while considering all three performance attributes, i.c. convergence, generalisation, and expressivity.
Performance Attributes Several works have studied the theory concerning convergence, generalisation and expressivity of the neural networks (Neal 1996 Williams 1996 Du et al. 2019a| Poole et al.) 2016). For instance, Du et al. (2019a b) provided insights into the convergence and generalisation of overparameterized networks through gram matrix analysis. Building upon this idca, we establish a connection between the collinearity of feature maps and the convergence and generalisation capabilities of CNNs. Additionally, Pooole
4

---

Published in Transactions on Machine Learning Research (08/2025)
al. 2016 investigated the expressivity of neural networks using concepts from Riemannian geometry Lee 2006 and Mean Field Theory (Weiss, Pierre 1907]. We leverage these concepts to incorporate expressivity into our proxy. Finally, Chen et al. (2023) demonstrated the 'No Free Lunch' behaviour, indicating that with a fixed number of paramcters, no single architecture can simultanconsly optimise all performance attributes. This is because convergence and generalisation properties favour wide and shallow works while expressivity favours deep and narrow network topologies. Hence, our proxy aims to balance these attributes rather than optimising all three simultaneously.
3 Dextr
3.1
Problem Formulation
Consider the convergence, generalisation, and expressivity of an overparameterised neural network. In this context, convergence refers to the rate at which the loss of this network reaches minimum, generalisation refers to the performance of the network on unseen test data post-training, and expressivity refers to the ability of the network to model complex functions.
We aim design zero-cost proxy that considers all three attributes convergence, generalisation, and expressivity of a network without the roquirement for labelled data. To this end, based the background concepts detailed in Section 3.2
establish the relationship between the collinearity of feature maps of a specific convolutional layer in the CNN with the convergence and generalisation properties of this network, by employing Singular Value Decomposition. To address expressivity, we build upon the findings of Poole et al. (2016) (Section 3.2.2) for designing our proxy. Next, we apply our proposed proxy to Vision Transformers (ViTs) (Section 3.3.4). Finally, we utilise the proposed proxy to search for optimal neural architectures in a training- free setting.
3.2 Background Theory
We consider, for simplicity, the two-layer fully-connected neural network f(W, a, x,) with ReLU activation function, as Du et al. (2019b), such that
S(W a.x:) vm Σ a.o x:),
(1)
where x; is the input to f taken from the training set = {xx; yi) M)) y: the ground-truth for x,, w E Rd and W E Rdxm are the weight vector and matrix for the first layer respectively, m the number of hidden nodes, is the ReLU activation function, a, E R. is the output weight, and E Rmx1 is the output weight vector. We consider the simple case where the training objective of this network is to minimise the following Mean Squared Error (MSE) loss
(Du et al. 2019b):
L(W, a) = Σ (f(,,
(2)
First, we present the background theory regarding convergence, generalisation, and expressivity of f. Then, we demonstrate the transferability of these foundational concepts CNNs.
3.2.1 Convergence and generalisation: Minimum eigenvalue of gram matrix
We start by examining the convergence and generalisation of f. Following Du et al. (019b)) consider a continuous training scenario where I is trained through gradient descent with infinitely small step-size t, and the output layer of f is fixed. The prediction of this network on given input x, at training time step is denoted as (t) = (t) a, x.). Then, the gram matrices generated by the ReLU activation function the training set D at given time and at initialisation, i.c. t = 0, respectively defined as
1 >
H()
xxxII (1)x 2 0, w, (1)x; 2 0},
5

---

Published in Transactions on Machine Learning Research (08/2025)
H = www XII [["" x; 2 0, w=xx 2 0}},
where r E [m],W[ .V.}} represents the Gaussian distribution, Il represents the indicator function and H(t) e R H E R are the respective gram matrices. Next, we consider the following theorem for network convergence [Du et al. 2019b).
Theorem Let the input E [n], Clow < ||x,||2 < Chigh and llvsll < C, where Chigh, Qow, and C are no constonts. If the number of nodes m is set to 92( ElammitHs (H= where 8 is the probability of fasture, Q denotes the lower bound, and Amin (H*) ) denotes the scaled minimum eigenvalue of H and we i.idd. initialise wr ~ (O,,,)) I) and a, -[[[1,111,] 1]}, where u(-} represents the uniform distribution, then with at least probability, the following relationship holds:
[|u,(t) - y:llă I exp(-Amiin (0) -vllle
Theorem 1 establishes that the loss incurred by f at time-step 6, defined as ||u(t) yll has upper bound controlled by Xmin (H. If we take the training loss at initialisation out of consideration, then higher the term Amin (H would be, lower the term exp(->min (H))) would be, and lower the upper bound of the training loss at time t, i.e. (t) y, l2 would be, which shows better convergence. In conclusion, the term Amin ) at a given time controls the upper bound the training loss at t and hence, governs the convergence rate of f- The proof of this theorem provided in the work by Du al. (2019h). Theorem [ can be extended the case of deep neural networks, as described in the Appendix Section A.2 Next, we
explore network generalisation based on the following thcorem from Cao & Gu (2019) and Zhu et al. 2022
Theorem Let the loss function of f with m + evaluated on the test set be denoted L(W). Let the ground truth y "ux.)"" yx) where N is the total number of samples and represents the step size of stochastic gradient descent (SGD), determined by 7 kC1 (H
where k is a sufficiently small absolute constant (Zhu et al. 2022). If Theorem | holds, then for any 8 E e0,e-'], there erists a value mn which depends on 8, N, and Amin (mo) such that of m 2 m', with probubilily of at least - 8, the following inequality holds:
B(L(W)] 50 (CAV
y"y Amin (HoO)N)
(V N
+0
(4)
where C1 and C2 are constants.
We observe that the upper bound of the expected test loss, E[L(W)), is governed by two key terms. In particular, the smaller the term O C2y Amm (H*)N is, the tighter the upper bound on the test loss. Conse- quently, larger value of Amin (Ho² leads to a smaller test loss, indicating better generalisation. Therefore, Amin (H2) positively correlates with the generalisation capabilities of f. The proof of this theorem is detailed in the work by Jiang et al. 2023)
y"y
Remark 1 Based on Theorems and 2 and findings from Du et al. (20196), while H(t) changes through the progression of L from 0 to co, it still stays close if + co. Moreover, for any two non-parallel inpuls X and xj (i.e. X4 * xz), the minimum eigenvalue of the gram matriz H at initialisation, i.e. Amin (H²) is strictly positive, i.e. Amin(H% > 0, and is positively correlated to the convergence rate and generulisation capobilities of f.
The relationship between Ht) and H in Remark [ also implics that the inputs xt(t) and xt(t) at any training time step can be used to estimate the convergence rate and generalisation of f. This motivates us to design our proxy close to the start of the training, i.e. when i is close to 0.
3.2.2 Expressivity: Extrinsic curvature of the output
Next, we consider the expressivity characteristies of f using the characterisation through extrinsic curvature of the output, given by Poolle et. al. (2016). We utilise this characterisation because the extrinsic curvature

---

Published in Transactions on Machine Learning Research (08/2025)
of the output captures how sensitive the network's output is to small changes in its imput. This property is directly connected to the expressivity as expressive model can adapt finely to differences between input samples, which is reflected in high local curvature. To examine the expressivity of f, we leverage principles from Riemannian geometry (Lee. 2006). In this geometry, a manifold represents a topological space that resembles Euclidean space locally near each point but may have an intricate global structure. Following Poole et al. (2016), we define g(f) as a 1-dimensional manifold within the input space, where 0 serves as an intrinsic scalar coordinate on this manifold. We consider g(0) to be an arbitrary circular input i.e. g(0) Vo (os()) + o sin(f)], where 0 [0, 2T), and o", o' form orthonormal basis for 2-dimensional subspace of R.M. The layer propagation of f transforms this input manifold into new manifold h0) h' (g((),, where corresponds to the layers of f. Each point 0 in the manifold h'(0) induces a velocity vector (equal to its langent), represented by v'(0) = 8ah'(0), and an acceleration vector a' (0) = (0). Formally, the extrinsic curvature of the output, induced by the arbitrary circular input g(0) parameterisod by B is defined in Poole et al. (2016):
x(0) (v- 3/2 (v (a a) - (v. a)).
(5)
Remark 2
The extrinsic curvature of the output, i.e. k(0) measures the complezity of the output curve, which indicates the functional complerity of f. Thus, k(O) is positively correlated to the expressivity characterislic of the nelwork f.
Intuitively, a more expressive network induces a more tangled output manifold after propagation through the network, observed in Figure 1b Thus it has higher x(0). The extrinsic curvature k(0) remains invariant irrospective of the particular parametorisation 0 and does not require any data for its computation. Moreover, this characterisation of expressivity is applicable to networks with random weights (Poole et al. 2016), ie. at time-step = O. The data- inta-independent property of k(0), as well as its ability to express the functional complexity of f at network initialisation makes suitable to incorporate x(0) in our proxy.
3.2.3 Approximation to convolutional layer
Consider the multi-channel convolutional layer Jonn of the CNN fenn. The number of channels in layer Jenn is denoted as C. The vector-representted output feature maps at time step t are denoted as x(),,, where CE (1,2, ,.....C.. We define (t) as a matrix containing all the vector-represented feature maps, such that (t) E (t).. The network foon is trained on the training set D = [(x,, y)] The output of fenn at time step is denoted as u, (1) and the loss incurred by Senn at time step / is defined as [lu - y:
Remark 3 Through the approzimation of the multi-sample fully-connectedd layer of to consolutional layer Jenn of the network Seen under some construints presented by Jiang el al. (2023), we know that each data sample x, can be regarded as a vector-represented channel x of the convolutional layer genn, where c E [1,C}. Thas, the concepls regarding I presented in Section 3.2. and 3.2.2 hold for senn by replacing the input data sample x, with the feature maps x..
ciaitiichannet
Hence, the gram matrix H(1) for multiple input samples in the fully-connected layer of can be approximated as (t) for multiple channels in the convolutional layer joun, where Ht) is the gram matrix associated to the feature maps at time stop t. A detailed explanation on approximation to convolutional layer is provided in the Appendix Section A.3
3.3 Designing Dextr
We now design our zero-cost proxy, focused on CNNs (Sec. 3.2.3 by utilising the remarks on the convergence and generalisation (Sec. 3.2.1], as well as expressivity (Scc. 3.2.2 In particular, we exploit the collincarity (Sec. 3.3.1 among all channels of the layers in the CNN using SVD (Sec. 3.3.2) to formulate our proxy, namely Dextr.

---

Published in Transactions on Machine Learning Research (08/2025)
3.3.1 Multi-collinerrty in feature maps
According to Remark we observe that firstly Amin ( correlates positively with the training convergence rate and the generalisation capabilities of f. Furthermore, for any two non-parallel inputs x, and xj, H(t) remains close to H at each training time step Therefore, when t close to 0, Amin (H())) can similarly measure the convergence and generalisation of f. In Remark we recall the approximation of fully- connected layer to the convolutional layer (Jiang et al. 2023) by replacing the imput sample x,(t) with the vector-represented channel x (t) and H(t) with (t). Therefore, we infer that Amin (H*(t) of any convolutional layer is positively correlated with the convergence and generalisation of a CNN.
Additionally, the eigenvalues of (1) represent the variance along the orthogonal eigenvectors. These eigenvectors capture the orthogonal directions of the variability of the data (Shawe- Consoquently, Amin (t) shows the uniqueness of information in the most linearly dependent channel or Jealure map in (1). Lower values of Amin (H+()) indicate that al least one channel in (+( is highly redundant and could be represented as linear combination of other channels.
et al,, 2005
Instead of focusing solely on the linear dependence or collincarity of the most linearly dependent channel in (1), we focus on the collinearity among all channels jointly. Thus, we assume that the convergence and generalisation of fenn are negatively correlated to the multi-collinearity of channels in (t). This assumption is proved later in Theorems and
3.3.2 Singular Value Decomposition for multi-collinearity
To estimate the multi-collinearity in (t), we deploy SVD due its effectiveness and numerical stability, especially when considering large ill-conditioned matrices (Klema & Laub 1980). We know that the singular values 0% of (t) equal to the square root of the eigenvalues 2 of the gram matrix Ht) at any time-step t, i.c. dx
where k indexes the orthogonal cigenvectors.
Remark 4 The condition number of (t), defined as the ratio of the marimum singular value to the minimum singular value, i.e. ctX maax
(x* (t) E IR, colculated through SVD, depicts the ill-conditioning or collinearily of vectors in (1) Demmel 1987).
Thus, we utilise the condition number (t) to establish the relationship between the collincarity of channels in (t) and the convergence and generalisation properties of the CNN femn- Hence, we present the following lemma and theorems concerning convergence and generalisation through adaptation of the theorems presented Section 3.2.1
Lemma 1 Consider multi-channel convolutional layer with the rumber of channels as C, then the max- The proof and the experimental validation is provided in the Appendix Sections A.1.3 and A.1.4 respectively.
imum singulor value of (+()) is greater thon or equal to 1, i.c. Omax (X* (1)) 2 1.
Theorem Consider multii-hannel convolutional neural network senn that is approrimated by the nelwork f. Let the input to f be i E [n] and Clow < ||x:|12 < Chigh, lyal C. for some constant Clow: Chigh, and C. Nert, consider the Lemma 7 to be satisfied, and that the number of nodes for f is selected according n
21 Amau(H (1gg)) where represents the lower bound. Then, if we perform an i.i.d. inátialisation of wr (O, and let a, ~ U[[-1,1]} for r E [m], where u denotes uniform distribution, then with probability of at least 1 - 8, the following inequality holds for Senn:
(tu y.ll3 (xp((eptp(((((( = 01) -.
(6)
where (t = is the scaled feature matrix at instialisation, i.c. =0 0.
We observe from Theorem that ct = 0))² negatively correlates with the convergence rate. Thus, through Remark g and Theorem 3 we deduce that the convergence rate worsens with the increase in multi-
collinearity of X (t = 0). The proof for Theorem is available the Appendix Section A.l
8

---

Published in Transactions on Machine Learning Research (08/2025)
Theorem For the test loss function L (W) of the network fenn, let the SGD step-size "y be determined by AC (H*))1yy(m/)>) where N is the number of samples. If Theorem 3 holds, then for any E (0,e-)), there evists a value m which depends on 8, N, and c(X = 0)) such that if m 2 m then with a probability of at least - 6, the following inequality holds:
where k is small absolule constant. Let the ground truth (y1,.., ...,, UN)"
ELL (L)(W)) 5o (C2c(X((t=)) ())
y"y N +0
log log 1/
(7)
N
where Ci and C2 are conslants.
The proof for this theorem is presented the Appendix Section the upper bound the test loss of fown is directly proportional to cf (t = 0)). Hence, ct =0) is inversely proportional to the generalisation capabilities of fenn.
A.1 We observe from Theorem g that
We now see from Theorem 8 and 4 that the convergence and generalisation of ferm negatively correlated to the multi-collimaarity of feature maps of given layer at imitialisation, which is also observed in Figure
la Next, we formulate Dextr through the proposed theorems.
3.3.3 Formulating Dextr
Through the Theorem and we note that et 0)) correlates negatively with the convergence and generalisation of Sean- Through Remark [ know that (() stays close to H (when / 0) if - oo. Hence, infer that Amin ( (t) approximates the value of Amin (H = 0)). Thus, through the relation (H* (t)), we know that the condition number c(X)(tt) also approximates the value (t ( 0)). Hence, the inverse of (t) correlates positively with the convergence and generalisation. Subsequently, through Remark g we observe that the extrinsic curvature of the output, i.e. x(0) corvelates positively with the expressivity characteristics of feen. To balance convergence, generalisation, and expressivity character- isations, we propose the following zero-cost proxy using the simplified harmonic mean of the logarithms of the extrinsic curvature k(0) and the sum of the inverse of the feature condition number ((X(()))
log (1 (1+E/ (xx)
log (1+ x(())
Dextr
(8)
log 1+ 1+ E/ 21=1 cx(x²))
+ log (1 k(O))
where L the number of layers, a (X*) ) is the condition number corresponding to the feature maps of layer and x(0) is the extrinsic curvature of the output given an arbitrary circular input 0. As observed from Eq. the proposed proxy is defined the half of the harmonic mean between two terms: log (1 EL dx(k)) and log (1 x())) The logarithmic transformations in Eq. g are applied to reduce the effect of the scale of these two terms and to avoid numerical instabilities, while the addition of I ensures that both terms remain positive. Note that we omit the training time step / in our proposed proxy as Dextr is invariant to I, meaning theoretically, feature maps X and curvature x(0) at any point in training can be used to calculate Dextr
3.3.4 Application to Vision Transformers
To demonstrate the application of Dextr to Vision Transformers (ViTs) (Dosovilskiy et al. 2021 ; rely the relation of CNNs with ViTs given by Li et all (2021a). Notably, Li et al. (2021a) prove that multi- head self-attention (MSA) layer in ViTs with relative positional encoding can exactly mimic a convolution operation the number of heads is carefully set with a sufficient number, mainly due to the similarities between the attention mechanism and convolutions. This supports the applicability of our convolutional layer analysis (Section 3.2.3) to VÝTs, Next, we consider the Gaussian Error Linear Units (GeLU) activation function (Hendrycks & Gimpel 2016 used in ViTs. Since GeLU is regarded
smooth approximation
We provide the procedure to calculate Dextr and the experimental settings in the Appendix Sections A.6
respec-
tively.
9

---

Published in Transactions on Machine Learning Research (08/2025)
of ReLU (Hendryeks & Gimpel 2016); the behaviour of these functions is comparable. Thus, the concepts discussed earlier in relation to ReI.Us can be directly applied to GeLUUs as well.
Lastly, we acknowledge that in some cases, strict equivalence of ViTs and CNNs is not met, specifically, in the cases where relative positional encodings are not always used, or where the number of attention heads may not be large enough to achieve the convolutional limit. However, we argue that the reason why Dextr is generalisable on ViT's is because a strict equivalence is not necessary for Dextr to be effective. As long as the output of the transformer layers exhibit somewhat sufficient structure similar to CNNs, the SVD analysis is meaningful. Importantly, our theoretical derivation interprets inputs features collections of vectors, on which SVD analysis is performed. Notably, the central assumption of our theory is not convolution, but rather the existence of a meaningful Gram matrix formed from activations. Since ViT block outputs can be reshaped or projected into such vector sets, our analysis of convergence and generalisation via Gram eigenvalues, and hence SVD, extends naturally.
4 Experiments
Our evaluation is performed through two standard protocols (Li et al. 2023 Jiang et al. 2023 Sun et al, 2023), namely the correlation experiments and NAS experiments. The experiments include a total of six benchmarks involving CNN and VIT architectures. We evaluate method on a variety of supervised and
sclf-supervised tasks, including image classification (Ying et al. 2019 Dong & Yang 2020 Zela ct al. 2022
object classification (Duan et al. 2021), scene classification Duan el al. 2021 and jigsaw classification Duan et al. 2021).
4.1 Correlation experiments
Experimental Protocol We first consider the correlation experiments. To this end, we evaluate our
proposed zero-cost proxy on four standard benchmarks: NAS-Bench-101 (Ying et al. 2019). NAS-Bench- 201
Dong & Yang 2020). NAS-Bench-301 (Zela et al. 2022), and TransNAS-Bench-1000 1ee--Bnnc-11111mi
Duan et al.
2021 through the NAS- NAS-Bench-See Beench-Suite-P Zero framework Krishnakumar et al. 2022) for an unbiased comparison
[Pegg et al. 2024). Additionaly, we provide correlation experiments on NATS-Bench-SS5 (Dong et al., 2021
in the Appendix Section A.5 To evaluate our approach, we utilise the standard evaluation protocol (Peng
et al. 2024 Jiang el. al., 2023 Li et al. 2023 , calculating the Spearman rank correlation coefficient. (Zar
2005 between the proxy value and the architecture test accuracy, We consider 1000 randomly sampled architectures from NAS- Sus-Benh-SSuite-eero for our analysis. We perform 3 runs of cach correlation experiment and compare the mean proxy-accuracy correlation of Dextr with several zero-cost, proxies, following the same evaluation protocol, namely Fisher (Turner et al.) 2020). Snip Lee et al. 2019), Grasp (Wang et al., 2020). Synflow (Tanaka et al. 2020). Grad Norm (Abdelfattah et al. 2021), MeCo (Jiang et al., 2023). SWAP-NAS (Peng et al. 2024), and the number of parameters #params.
Discussion of Results Table I presents the comparison of Spearman rank correlation cocfficient p across different zero-cost proxies. Our method consistently surpasses previous baselines across the NAS-Bench- 101 and NAS-Bench-201, and in two out of three tasks of TransNAS TransSAAS-Bench-1000 the results in TransNAS-Bende Bee-Beenh-0l-mierr benchmark show that Dextr is robust to task variations using the same search space. Moreover, we can observe that our method performs better in scene classification task compared to object classification and jigsaw classification tasks. This is because the scene classification task is an casier task that benefits more from global image cucs and spatial hicrarchies (Duan et al.) (021), which are more aligned with the characteristics that zero-cost proxies like our method can capture. In particular, our method outperforms other proxies in Scene Classification because it captures the expressive capacity of network to model global spatial patterns and hierarchical features, both of which are critical for scene understanding,
benchmark. Specifically,
Remarkably, in the case of best approach. In the NAS-Bench-301 benchmark, our method performs competitively with a correlation of 44%. However, compared to other benchmarks, our method performs relatively worse in this benchmark since NAS Benchhen is known to be particularly challenging benchmark due to high architectural diversity
our approach shows an improvement of 8% over the previous
10

---

Published in Transactions on Machine Learning Research (08/2025)
Table 1: Comparison of Spearman rank correlation coefficient for various zero-cost proxies on four tasks of TransNASBenchOO--mo (TNB), along with NAS-Bench-100 (NB101), NAS-Bench-201 (NB201), and NAS-Bench-300 Bench-301 (NB301). We report the mean and standard deviation of our results across runs. The best approach is indicated bold and the second-best approach is indicated underlined. All numbers except
ours and MeCo (Jiang et al. 2023 are taken from (Png et al.
2024
Approach
TNB-Object
TNB-Seene
TNB-Jigaa
NB101
NB201-cf10
NB201-cf100
NB201-ImNet120
NI3301
Grasp
-0.22
-0.43
-0.12
0.27
0.39
0.46
0.45
0.34
Fisher
-0.28
Grad Norm
0.39
-0.33
0.36
-0.21
0.42
0.49
0.47
-0.04
Snip
0.45
-0.14
0.41
-0.19
0.43
0.49
0.48
-0.05
Synflow
0.48
0.27
0.47
0.31
0.74
0.76
0.75
0.18
#pparas
0.45
0.32
0.44
0.38
0.72
0.73
0.69
0.46
ZiCo
0.50
0.70
0.52
0.411
0.76
0.79
0.77
0.49'
MeCo
0.58
0.62
0.45
0.571
0.89
0.85
0.43*
Swap__Te regg
Dextr (ours)
0.53=0.007
0.75+0.003
0.53=0.003
0.65=0.010
0.90:#0.006
0.91=0.004
0.87=00006
0.44+0.007
Table 2: Quantitative comparison of networks chosen by the NAS methods on ImageNet (eng et al.
2009
within the DARTS (Liu et al.) 2019) search space in terms of the top-1 and top-5 error rate, along with the number of parameters (Params), Method Type (One Shot, Zero-Shot, or Predictor) and search cost GPU days. The best approach is indicated as bold and the second-best approach is indicated as underlined.
Method
Top-1/Topp 4
Params
GPU
Type
Error
(M)
Days +
DARTS (2nd) Liu et al.
2019
26.7 / 8.7
4.7
4.0
OS
SNAS (ie et
2018
27.3/9.2
4.3
1.5
OS
BarDARTS Chhu et al. PC-DARTS
2020b)
24.4/7.4
5.3
3.8
OS
et 2019
25.1/ 7.8
5.3
0.1
OS
P-DARTS CCen et al 2019
24.4 / 7.4
4.9
0.3
OS
LA-NAS Mills al. 2021
24.6/7.5
5.4
OS
3-DARTS Ye et al. 2022
23.9 / 7.0
5.5
0.4
OS
PRE-NAS
Peng al.
2022
24.0/7.8
6.2
PR
TE-NAS Chen et
2021c)
26.2 /
ZS
7iCo
[Ta et al. 2023
24.9/7.6
7.7
0.02
7S
MeCo
Jaagg et al.
2023)
25.1/7.7
7.8
0.04
ZS
Dextr (ours)
24.6/7.4
6.6
0.07
ZS
(Zela et al. 2022). Notably, our approach demonstrates superior performance in both supervised tasks (scene classification) and self-supervised tasks (jigsaw classification), highlighting its versatility and effectivencss across a range of computer vision tasks. Lastly, as evident from the low standard deviation values, we observe that the results of approach stable across different runs.
4.2 NAS experiments
Experimental Protocol Our NAS experiments involve searching architectures for the ImageNet (Deng
et al. 2009) classification task and comprise two search spaces- AutoFormer (Chen et al. 2021b search
space containing Vision Transformer (ViT) architectures and DARTS search space containing CNNs [Liu]
ct al., 2019). We conduct an additional experiment on MobilcNet-v2 space (Sandler al.
2018 available
in the Appendix Section A.5.2
Our DARTS evaluation follows the standard protocol (Liu et al. 2019
Chen et al. 2021c Peng et al. 2022
of scarching for the optimal architecture on CIFAR-10 and training the found architecture on ImageNet (Degg et al. 2009). Furthermore, the search for the best architecture for all zero-cosi. proxies is based on the operation scoring strategy through the Zero-Cost-PPT algorithm (Xiang et al. 2023). We perform the search and training procedures and report the top-1 and top-5 error of the architecture found by Dextr, along with the number of parameters and search cost in GPU days, and compare with various bascline one-shot and
zero-shot NAS approaches, including DARTS [Liu et al. 2019) SNAS Xie et. al.] 2018), FairDARTS (Chu

---

Published in Transactions on Machine Learning Research (08/2025)
Table 3: Quantitative comparison for the AutoFormer (Chen et al. 2021b search space the Tiny and Small sctting with parameter constraints 6M and 24M respectively. We report the top-1 error, the number of parameters (Params) and floating point operations (FLOPs) of selected networks on ImageNet (Deng al, 2009), along with the search cost in GPU days. The best approach is indicated bold and the sccond-best approach is indicated as underlined.
Method
Top-1 Error
Params (M)
FLOPs
GPU
Days +
Tiny (6M)
AutoFormer (Chen et al.
b021
25.3
5.7
1.30G
21
AZ-NAS [ee & Ham
2024
23.9
5.9
1.38G
0.03
Dextr (ours)
23.7
5.8
1.36G
0.03
Small (24M)
AutoFormer (Chen et b021b
18.3
22.9
5.10G
TF-TAS
Zhou et al. 2022
18.1
23.9
5.16G
0.5
AZ-NAS
Lee & Ham
2024
17.8
23.8
5.13G
0.07
Dextr (ours)
18.0
23.0
4.93G
0.07
et al. 2020b, PC-DARTS Xu et PRE-NAS Peng
2019), P-DARTS (Chen al. 2019),
LA-NAS
Mills et al. 2021
3-DARTS Yee ct al., 2022).
2022). TE-NAS (Chen al.
2021c). McCo (Jiang al.
2023), and ZiCo (Li et al. 2023
Next, consider our evaluation in the AutoFormer search space (Chen et al. 2021b). The AutoFormer (Chen et al.] 2021b) search space is segregated into three subspaces- tiny, small and base with varying architecture sizes. In our experiments, we consider the tiny and small subspaces of AutoFormer to leverage
faster training times. We follow the standard protocol (Chen et al. 2021b Zhou et al. 2022: Lee & Ham 2024) which involves searching for the parameter-constraineee architecture with the best Dextr score among 1000 candidate architectures. The selected ViT then trained on ImageNet with an identical experimental
setup as (Zhou al., 2022; Lee Ham 2024). Our approach is compared with several baselines, namely
AutoFormer (Chen et al. 2), TF-TAS (Zhou et al. 2022), and AZ-NAS (Lee & Ham 2024 We compare the top-1 1 error, number of parameters (Params), number of floating point operations (FLOPs) and search cost of the architecture in GPU days found through our method with the baselines.
Discussion of Results Our NAS experiments on DARTS and AutoFormer search spaces are summarisod in Table and resppectively Table 2 shows that our proposed approach efficiently searches for architectures with low test errors ImageNet, completing the search in only 0.07 GPU days. Specifically, Dextr achieves lower error rates and is faster compared to previous one-shot methods, such as DARTS (Liu et al. 2019 SNAS (Xic et al. 2018), and PC-DARTS (Xu et al. 2019). while relying on only a single label-froe data sample. Furthermore, Dextr demonstrates superior performance over all prior stale-of-the-arl zero-shot methods with a comparable search cost. Although some one-shot approaches like FairDARTS (Chu et al. 2020b), P-DARTS (Chen et al. (2019), B-DARTS (Ye et al. 2022). and PRE-NAS (Peng et al. 2022) achieve better test error, our approach marginal difference in test error. This speedup makes our proxy particularly useful in practical scenarios with limited compute.
least approximately 2.3x faster than any of these approaches with
Moreover, we observe from Table 3 that our approach outperforms the previous best methods in the AutoFormer-tiny search space and demonstrates competitive performance the AutoFormer- small search space in terms Top-1 error while being at least as fast as the previous fastest approach.
4.3
Ablation Studies
4.3.1
Stability of Dextr
"Experiments marked by rerun through their official implementation using the NAS- NAS-Bench-San Bench-Suite Zero Krishnakuuma
2022 framework.
12

---

Published in Transactions on Machine Learning Research (08/2025)
Table 4: Comparison Spearman Rank Correlation Coefficient (p) using individual characteristics with Zen and ZiCo on NAS-Bench-2011 along with the comparison of Dextr with the harmonic mean of Zen and ZiCo. Here, C/G refers to convergence/ getaraaisttnnnnniniiionnnoo and refers to expressivity.
Component
Property Type
CIFAR-10
CIFAR- 100
GrageNee116-10
log(1 +
X)
C/G C/G
0.88
0.89
0.85
ZiCo
Li et al.
2023
0.76
0.79
0.77
log(1
E
0.51
0.49
0.51
Zen Lin et al.
(0021)
E
0.33
0.34
0.38
HM ZiCo)
C/G + E
0.44
0.44
0.47
Dextr
C/G +
E
0.90
0.91
0.87
In this study, we assess the stability of our approach. To this end, we sample 10 architectures from NAS-Bench-201 (Dong) & Yang 2020) search space, ranging from 50% to 90% accu- racy. Next, for each network, we calculate 10 Dextr values cor- responding to 10 random inputs taken from 10, along with randomly generated circular inputs g()) for our curvature calculation. Finally, we calculate the mean and standard devi- ation the different Dextr values of cach network and report them in Figure 2 along with the test accuracy of that network.
Dextr Stability across Networks (NAS Bench 201)
24
900
acccurac (%)
88
Dextr Score
88
22
1.8
70
Test &
65
Dextr Mean Std
Test Accuraty 1%)
Network Index
As shown in Figure 2 approach exhibits strong stability across random CIFAR-10 inputs and randomly sampled circu- lar inputs. The standard deviation of Dextr across multiple in- put samples remains consistently low for all 10 networks (rang- ing between 0.01 and 0.05), indicating that the proxy is robust to variations in input data and curvature sampling. Further- more, the mean Dextr scores correlate well with test accuracy, i.c. networks with higher Dextr values achieve higher accuracy, while those with lower Dextr values perform worse. Notably, the best-performing network (Network with 89.90% accuracy) has the highest mean Dextr score (2.34). whereas the lowest-performing network (Network with 56.19% accuracy) has the lowest Dextr value (1.32). The mid-range networks show that Dextr able to separate similarly performing architectures, which sug- gests that Dextr is sensitive enough capture subtle performance differences between architectures.
Figure Mean and Standard Deviation of Dextr for 10 networks (sorted by accu- racy) sampled from NAS-Bench-201 (Dong & Yang 2020), corresponding to 10 random inputs taken from CIFAR-10 and 10 ran- domly generated circular inputs g(0).
4.3.2 Performance of individual components of Dextr
We now compare the Spearman rank correlation coefficient, of individual components of Dextr, i.e. the con- dition number term log(1 +11+++cl c()) (focused on convergence/ pwverggoco/genncraiisttooo and the curvature term log(1 + x) (focused on expressivity) with previous proxies considering these individual characteristics on NAS-Bench- 201. We consider Zen (Lin al. (021)) as the expressivity proxy and ZiCo (Li al.) (0223) as the con- vergence/
segence/generalisation generalisation proxy. Additionally, also compare Dextr with simple harmonic mean of these
proxies. The results can be observed in Table 4
and expressivity compo- nents, consistently achioves the highost Spearman rank correlation across all three datasets in NAS-Bench- 201. Notably, the condition number term log(1 + c(X)) outperforms ZiCo across all tasks, indicating that Dextr's convergence/ / /ennraliisatoonn measure a more reliable proxy for performance than ZiCo. Moreover, the curvature term log(1 + k) also consistently outperforms Zen, indicating its effectiveness. Lastly, the har- monic mean of Zen and ZiCo performs worse than either of Dextr's individual components and significantly worse than Dextr itself, suggesting that naively combining external proxies is not as elfective as Dextr.
The results demonstrate that Dextr, which combines convergence//eneraaiee
4.3.3 Analysis for individual layers
13

---

Published in Transactions on Machine Learning Research (08/2025)
We study the variation in linear independence of feature maps (FMT) across different hid- den layers of networks sampled from NAS- Bench-201 (Dong & Yang. 2020). The FMI is calculated using the inverse of the condition number, i.c. 1/e(X*). We compare the FMT between layers of high-performing network, with validation aceuracy of 89.43% and low-performing network, with validation ac- curacy of 63%. The results, shown in Figure reveal that the FMI of the networks fluctu- ates due to considering outputs from all layers, including activations, convolutions, and fully connected layers. Peaks in FMI increase, then slightly decrease, and finally drop to zero, with the highest peaks occurring during network di- mensionality expansion. This is because di- mensionality expansion increases the rank ca- pacity of the feature matrix, allowing it to span a larger subspace with more orthogonal directions. As a result, the collinearity between feature channels is reduced, and feature linear independence (FMI) peaks. Later, when the network compresses feature dimensionality, the rank of the feature matrix decreases, which squeezes the singular value spectrum and FMI drops. Finally, we observe that the low-performing network's layer outputs are generally less linearly independent, supporting the theoretical findings in Theorems 3 and 4
Low-Performing Network
High-Pertorming Network
0.35
Linear Independence
0.30
0.25
0.40
0.33
0.00
Layer Index
Figure 3: Graph depicting the linear independence of out- puts, calculated using 1/c(X**, for each hidden layer of CNNs. We observe that the hidden layer outputs of the high- high-performing network are more linearly independent than the low-performing network.
5 Conclusion
We presented a zero-cost proxy, Dextr. this end, we first. demonstrated the relationship between the collinearity of the features and the convergence and generalisation of a network through SVD. Next, we exploited concepts from Riemannian geometry to include expressivity in our proxy. Our experiments demon- strated that our proxy exhibits strong correlation with network performance without requiring labelled data. As result, it outperforms all previous proxies in JAS-Bench-101, NAS-Bench-201, and TransNAS. Bench-micro benchmarks, along with established multi-shot and zero-shot NAS baselines in the ImageNet experiment in the DARTS and AutoFormer search space, all while inducing a low search cost.
Acknowledgement
We are thankful to the German National Science Foundation (DFG), which supported and funded this work under the project Always-on Deep Neural Networks (grant number BE 7212/7-1 OR245/19-11 Addi- tionally, we acknowledge the computational resources provided by the Erlangen National High Performance Computing Center (NHR@FAU) of the Friedrich- Uniiesssnnnne--iiissstaaaa Universität Erlangen-Nürnberg (FAU).
References
Mohamed Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero-cost proxies for lightweight {nas}. In International Conference on Learning Representations, 2021. URL https
Sohyun An, Hayeon Lee, Jachyeong Jo, Scanie Lee, and Sung Ju Hwang. DiffusionNAG: Predictor-guided
neural architecture generation with diffusion models. In The Twelfth International Conference on Learning Representations, 2024. URL htttps://openreviiee wwwp::wwwennnnnnte///e// iddyy22LLyyyy
Rohan Asthana, Joschua Conrad, Youssef Dawoud, Maurits Ortmanns, and Vasileios Belagiannis. Multi- conditioned graph diffusion for neural architecture search. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL http:://gpaaeeeeee..eee///r//s/p
14

---

Published in Transactions on Machine Learning Research (08/2025)
Andrew Brock, Theo Lim, J.M. Ritchie, and Nick Weston. SMASH: One-shot model architecture search
through hypernetworks. In International Conference on Learning Represenlations, 2018. URL https:
//openreview http://wwweetttooooiiirreeeeee
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In International Conference on Learning Representations.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neurol information processing systems, 32, 2019.
Boyu Chen, Peixia Li, Baopu Li, Chen Lin, Chuming Li, Ming Sun, Junjie Yan, and Wanli Ouyang. Bn- nas: Neural architecture search with batch normalization. In Proceedings of the IEEE/CVE international conference on computer vision, pp. 307 316, 2021a.
Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. Autoformer: Searching transformers for visual recognition. In Proceedings of the IEEE/CVE international conference on computer vision, pp. 12270- 12280, 2021b.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four {gpu} hours: A thcoretically inspired perspective. In International Conference on Learning Representations, 2021c. URL https://openreviiee
Wuyang Chen, Wei Huang, and Zhangyang Wang. "no free lunch" in neural architectures? joint analysis of expressivity, convergence, and generalization. In AutoML Conference 2023, 2023. URL https:// http:/iiiwwneet/ftuundiiiidddd
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. Dr(nas}: Dirichlet neural architecture search. In International Conference on Learning Representations, 2021d. URL https:
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 TEEE/CVF international conference computer vision, pp. 1294 1303, 2019.
Xiangxiang Chu, Bo Zhang, and Ruijum Xu. Multi-objective reinforced evolution in mobile neural architecture scarch. In european conference on computer vision, pp. 99-113. Springer, 2020a.
Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li. Fair darts: Eliminating unfair advantages in differentiable architecture search. In European conference on computer vision, pp. 465 480. Springer, 2020b.
James Weldon Demmel. On condition numbers and the distance to the nearest ill-posed problem. Numerische Mathematik, 51(3):251 289, May 1987. ISSN 0945-3245. doi: 10.1007/BF004400155 URL httpp::/doii org/10. 10///001007//F81400011
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hicrarchical image database. In 2009 IEEE conference on compuler vision and pallern recognition, pp. 248 255. Ieee, 2009.
Xuanyi Dong and Yi Yang. NAS-Bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations (ICLR), 2020. URL /ttppp::/openrreviee.. net/ Dorum?id=HxxyZkBBe
Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. NATS-Bench. Benchmarking nas algorithms for architecture topology and size. IEFF Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021. doi: 10.1109/TTB TPA.T.........0.........
doi 10. 1109/TPAMI
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Golly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Represendations, 2021. URL httpe://gggaaeeeraaaaeeee/rorrra
15

---

Published in Transactions on Machine Learning Research (08/2025)
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-167866 PMLR, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Represenlations, 2019b. URL
Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang, Tong Zhang, and Zhenguo Li. Transnas- bench-101: Improving transfcrability and generalizability of cross-task neural architecture scarch. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 5251-5260, 2021.
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- 1700-78, 2016.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv prepriml arXiv:1606.0 160.008461 2016.
Ya Sh y'yso and AB Muravnik. Min-max principles with nonlinear generalized rayleigh quotients for nonlinear equations. Journal of Mathematical Sciences, 260(6), 2022.
Tangyu Jiang, Haodi Wang, and Rongfang Bie. Meco: Zero-shot NAS with one data and single forward pass via minimum eigenvalue of correlation. In Thirly-sewentth Conference on Neural Information Processing Systems, 2023. URL https:// net//forum2id-//22121111
V. Klema and A. Laub. The singular value decomposition: Its computation and some applications. 1EEE Transactions on Automatic Control, 25(2):164-176, 1980. doi: 10.1109/TAC. 1AC.1980.... 1102314.
Arjun Krishnakumar, Colin White, Arber Zela, Renbo Tu, Mahmoud Safari, and Frank Hutter. Nas-bench- suite-zero: Accelerating research on zero cost proxies. Advances in Newral Information Processing Systems, 35:28037-28051, 2022.
Yann LeCun, Léon Botton, Yoshua Bengio, and Patrick Haffner. Gradient-based lcarning applied to docu- ment recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
John M Lec. Riemannian manifolds: introduction to curvature, volume 176. Springer Science & Business Media, 2006.
Junghyup Lee and Bumsub Ham. Az-nas: Assembling zero-cost proxies for network architecture search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 5893-5903, 2024.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. In ICLR, 2019.
Guihong Li, Yuedong Yang, Kartikeya Bhardwaj, and Radu Marculescu. Zico: Zero-shot NAS via inverse co- efficient of variation on gradients. In The Fleventh International Conference on Learning Representations, 2023. URL
wwtp://wwweeeeoouuidddrre-e--eee 1s5Gq(
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificcial intelligence, pp. 367-377. PMLR, 2020.
Shanda Li, Xiangning Chen, Di He, and Cho-Jui Hsieh. Can vision transformers perform convolution? anXiv
preprint ar xrX:::2111.0033 2021a.
Yuhong Li, Cong Hao, Pan Li, Jinjun Xiong, and Deming Chen. Generic neural architecture search via regression. Advances in Newral Information Processing Systems, 34:20476 20490, 2021b.
Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-nas: A zero-shot nas for high- perfoorrfeeeeee image recognition. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 347-30 -56, 2021.
16

---

Published in Transactions on Machine Learning Research (08/2025)
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In In- lernational Conference on Learning Represenlations, 2019. URL htctss//ppparrevieevnetfoooooo S1eYHoC5FX
Jovita Lukasik, Steffen Jung, and Margret Keuper. Learning where to look generative nas is surprisingly efficient. In European Conference on Computer Vision, pp. 257-273. Springer, 2022.
Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. In International conference on machine learning, pp.
PMTR, 2021.
Keith G Mills, Fred X Han, Mohammad Salameh, Seyed Saeed Changiz Rezaei, Linglong Kong, Wei Lu, Shuo Lian, Shangling Jui, and Di Niu. L2nas: Learning to optimize neural architectures via continuous- action reinforcement learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Monagement, pp. 1294,, 2021.
Bert Moons, Parham Noorzad, Andrii Skliar, Giovanni Mariani, Dushyant Mehta, Chris Lott, and Tijmen Blankevoort. Distilling optimal neural networks: Rapid search in diverse spaces. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 12229 12238, 2021.
Radford M. Ncal.
Priors for Infinite Networks, pp. 29-53. Springer New York, New York, NY, 1996. ISBN 978- 078-1-4612-0745-00 978- 978-1-4612-0745-77
doi: 10.1077/988-1-461227//44 2. URL fttps:///01..rg/10..oo
Yameng Peng, Andy Song, Vic Ciesiclski, Haytham M Fayek, and Xiaojun Chang. Pre-nas: predictor-assistel evolutionary neural architecture search. In Proceedings of the Genetic and Evolutionary Compulation Conference, pp. 1066-1074, 2022.
Yameng Peng, Andy Song, Haytham M. Fayek, Vic Ciesielski, and Xiaojun Chang, SWAP-NAS: Sample-wise activation patterns for ultra-fast NAS. In The Twelfth International Conference Learning Representa- tions, 2024. URL https://openreviies
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential ex- pressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture scarch. In Proceedings of the aaat conference artificial intelligence, volume 33, pp. 4780- 4789, 2019.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginox, and Liang-Chieh Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510-4520, 2018.
J. Shawo-Taylor C. K.I. Williams, N. Cristianini, and J. Kandola. On the cigenspectrum of the gram matrix and the generalization error of kernel-pca. IEEE Trans. Inf. Theor., (7):)221 2522, jul 2005. ISSN 0018-9448. doi: 10.1109/TII 2005.2000.850052 URL https:://ot:: org/10. 11000.199/100 TITT 2005. 8800552
Zihao Sun, Yu Sun, Longxing Yang, Shun Lu, Jilin Mei, Wenxiao Zhao, and Yu Hu. Unleashing the power of gradient signal-to-noise ratio for zero-shot nas. In Proceedings of the IEFE/CC /CVF International Conference on Computer Vision (ICCV), pp. 5763 5773, October 2023.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitra 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.
Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in neural information processing systems, 33: -387-6389, 2020.
17

---

Published in Transactions on Machine Learning Research (08/2025)
Yuan Tian; Qin Wang, Zhiwu Huang, Wen Li, Dengxin Dai, Minghao Yang, Jun Wang, Olga Fink, E Zürich, and N Europe. Off-policy reinforcement learning for elficient and effective gan architecture search (supple- mentary material). In Proceedings of the 16th European Conference on Computer Vision (ECCV 2020), Glasgow, UK, pp. 23-28, 2020.
Jack Turner, Elliot J. Crowley, Michael O'Boyle, Amos Storkey, and Gavin Gray, Blockswap: Fisher- guided block substitution for network compression budget. In International Conference on Learning Representations, 2020. URL http:://paeueeeeee....eoooooaaaa
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020. URL https:://penrrevie.. fest/forumiid-Skgeee
Weiss, Pierre. L'hypothèse du champ moléculaire et la propriété ferromagnétique. J. Phys. Theor. Appl., 6 (1):661-600, 1907. doi: 11..5///ppystap011000000 019070060066100
URL http://....orrr0011011//////tttp
Colin White, Sam Nolen, and Yash Savani. Exploring the loss landscape in neural architecture search. Tn Uncertainty in Artificial Intelligence, pp. 654 664. PMLR, 2021.
Christopher K. I. Williams. Computing with infinite networks. NIPS pp. 295 301, Cambridge, MA, USA, 1996. MIT Press.
Lichuan Xiang, Lukasz Dudziak, Mohamed S Abdelfattah, Thomas Chau, Nicholas Lane, and Hongkai Wen. Zero-cost operation scoring in differentiable architecture search. In Proceedings of the AAAT Con- ference on Artificial Intelligence, volume 37, pp. 10453 10463, 2023.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arXiv:1812 09926, 2018
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. arXiv preprint 2019.
Longxing Yang, Yanxin Fu, Shun Lu, Zihao Sun, Jilin Mei, Wenxiao Zhao, and Yu Hu. Sweet gradient matters: Designing consistent and elficient estimator for zero-shot architecture search. Newral Networks, 168:237 255, 2023. ISSN 0893-6080. doi: http:////doo.oog10011116.. neene nww.:e...tteetneeeee..e 2023.09.012. URL https:
Yibo Yang, Hongyang Li, Shan You, Fei Wang, Chen Qian, and Zhouchen Lin. Ista-nas: Efficient and consistent neural architecture search by sparse coding, Advances in Newral Information Processing Systems, 33, 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/CVP conference on compuler vision and paltern recognition, pp. 1829 1838, 2020b.
Peng Ye, Baopu Li, Yikang Li, Tao Chen, Jiayuan Fan, and Wanli Ouyang, b-darts: Beta-decay regulariza- tion for differentiable architecture search. In proceedings of the IEEE/CVE conference on computer vision and pattern recognition, 10874 10883, 2022.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench- 101: Towards reproducible neural architecture search. In International conference on machine learning. pp. 7105-7111 PMIRR, 2019.
18

---

Published in Transactions on Machine Learning Research (08/2025)
Jerrold H Zar. Spearman rank correlation. Encyclopedia of Biostatistics, 2005.
Arber Zela, Julien Niklas Siems, Lucas Zimmer, Jovita Lukasik, Margret Keuper, and Frank Hutter. Sur- rogate NAS benchmarks: Going beyond the limited search spaces of tabular NAS benchmarks. In In- ternational Conference Learning Representations, 2022. URL https://oppnreerie. http:/ppaarrrreeeeeeeeee//rrr/aa net/forummid- OmpFa95RVqs
Xuanyang Zhang, Pengfei Hou, Xiangyu Zhang, and Jian Sun. Neural architecture search with random labels. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10907-10916, 2021.
Qinqin Zhou, Kekai Sheng, Xiawu Zheng, Ke Li, Xing Sun, Yonghong Tian, Jie Chen, and Rongrong Ji. Training-free free transformer architecture search. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 10894-10903, 2022.
Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. Generalization properties of nas under activation and skip connection search. Advonces in Neural Information Processing Systems, 35:23551 23565, 2022.
Barrel Zoph and Quoc Le. Neural architecture search with reinforcement learning, In International Confer- ence on Learning Representations, 2017. URL
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc Le. Learning transferable architectures for scal- able image recognition. In Proceedings of the IEFE conference computer vision and pattern recognition, pp. 8697 8710, 2018.
19

---

Published in Transactions on Machine Learning Research (08/2025)
A Appendix
A.1 Proofs and Derviations
A.1.1 Proof for Theorem 3
We start from Theorem which states:
Theorem 1 Let the input be [n], Clow < | Chigh and l| < C, where C' is constant. If the number of nodes m is set to S X(x.... (Hr where å is the probability of failure, denotes the lower bound, and Amin (H²) denotes the scaled minimum eigenvalue of H and we i.i.d. initialise W, ~ (O, and ar ~ u[]-1,1},, where U{-} represents the uniform distribution, then with at least 1 - ô probability, the sollowing relationship holds,
[l,,(1) yill2 S expl 1 A j yv
99)
By relying on Lemma 1, we know that Omaa X (t = 0)) 2 1 and thus, Amax (H 2 1. Hence, we divide the term Amin (H with Amax and obtain the following incquality
[1:(() yill2 S exp (- Amin (H Amaxx (H>)))
|lu;(0) -y:1/-
(10)
This inequality holds because Amax (H*) 2 implies that function with negative exponent is monotonically decreasing.
Amin (H
AminnHH) and the exponential
Amaax HH
Next, we use Remark 3 to approximate the gram matrix concerning the fully connected layer of f. i.e. H with the gram matrix of the convolutional layer of the CNN feon (t 0). This allows to re-parameterize the eigenvalues A of H into singular values o& (x(X(11 0)) using the equation (X V>x Then, by replacing the network output f, i.e. (t( with the network output ferns ie. u (t), we obtain
min X (0)(
[1f(() -vil3 < exp
t)
|| (0) y:ll2
maxx (X)(O))
t
$ exp
[u -y.1
(11)
c c (X)(0)))
which completes the proof.
A.1.2 Proof for Theorem 4
We start from from Theorem 2, which states
Theorem Let the loss function of f with m + oo evaluated on the test set be denoted as L(W). Let the ground truth y = (y1, yN) and represent the step size of stochastic gradient descent (SGD), determined where Io a sufficiently small absolute constand. Tf Theorem 1 holds,
by 7 kC (H (yymmm) then for any 8 (0, e I, there ewists a vatue m which depends on ö, N, Amin (H such that if m 2 m², with probability of at least 1 8, the following inequality holds:
E[L(W)] [[L(W)]= so =o(o))
yTy
+0 (v log(1/8) N
(12)
Amiin
NN
where C₁ and C2 are constants.
Using Lemma 1, we know that Iamaz (X*(t =0)) 2 and thus, Amax H 00) 2 following inequality:
Thus, we can derive the
20

---

Published in Transactions on Machine Learning Research (08/2025)
B[L(W) 00 (Cov Amax H Amin (H
y"y y
(13)
N
(lo((1/0) N
+0
(14)
Next, we use Remark 3 to approximate the gram matrix a fully connected layer H with a convolution layer H (t 0). This allows to re-parameterize the eigenvalues Au (HH²) into singular values σx (x = 0))
using the equation ox (x 0)) / (t 0). By replacing the loss term E[L(W)) with the CNN loss term [[L+(W)), we obtain
[[T) 5 505
C2 min
T mmax
y" y N
(x(())
log( (/5) (1/()
0
N
yTy
5
(0))
N
10g(1/0)
(15)
N
which completes the proof.
A.1.3 Proof for Lemma
Let 333 denote the ij-th entry of (t). We know from the Courant Fischer Weyl MineMex- [I y'yssov
& Muravnik 2022 that mea (X (X) max
(X)ul) or any unit vector u. Then, we oblain
||||=1
man X (1)
(16)
(17)
|2gg v
(18)
which shows that the maximum singular value of (t) is larger than the maximum value in the matrix (t). Next, we assume that at least one absolute entry in the output induced by the ReLU activation function greater than 1, i.e. Lxpal > 1. Thus, the lemma omar X (1)) 2 holds true general, which is further validated in Section A.I.4
A.1.4 Experimental validation for Lemma 1
To provide experimental validation for Lemina 1, we conduct an analysis examining the number of cases where our Lemma holds true, i.e. where maa (t) 2 1. To this end, we sample 1000 networks from NAS-Bench-101 (Ying et al., 2019), NAS-Bench-200 (Dong Yang 2020), and NAS-Bench-301 (Zela et al., 2022) through the NAS-Bench-Suiie Beench-Suito-eerr (Krishnakumar al. (022) franework. Next, we input random data sample from CIFAR-10 to each of these networks and calculate the mean of the percentage of layers
21

---

Published in Transactions on Machine Learning Research (08/2025)
Table 5: The mean percentage of layers corresponding to 1000 networks in three different benchmarks where Lemma 1 holds true, i.c. men (X (t) 1. 1.
Benchmark
mmar (1)) 2
NAS--ennde Bee-BBenchhii 101
99.18 %
AAS-Bench-201
90.01
JAS-Bench-301
99.51
where maaz (X* 2 From Table 5 we observe that for all the benchmarks for at least 90% of the cases, Lemma 1 holds true for almost all
maz (t) 2 Remarkably, in NAS-Bench- 101 and
the layer outputs.
A.2 Transferability to deep neural networks
We elaborate how extend the convergence theorems (Theorems 1 and 3 to deep neural networks, relying the proof by Du et al. (019b). Consider deep neural network of the form:
frr a. = a² (W(()) ....(((())))
(19)
where x E Rd is the input and E I is the output layer. If = 2,........ H and W E [Rmx are the middle layers, then the associated gram matrix (t) E Raxx will have values G (1) 0u,(t) 0n,(t) where u, and Uj the i-th and j-th predictions respectively.
G = awen))) (w()
Du et al. (2019)) show that Σ (t)(t)) has a lower bounded least eigenvalue because i and j are not parallel. Moreover, Σ ()) is close to the fixed matrix Σ h= (1) and Σ h=1 (() is close to
Σ (0). Therefore, the proof for the convergence theorem by Du et al. 2019bb is transferable to deep neural networks with H hidden layers. Moreover this case, the rate of convergence a multi-layer case is governed by Aman (E G(h))
Now, using Weyl's inequality for Hermitian matrices, we know that
H
H
Amin ((A) S Amiin
G
(
(20)
h=1
Through this inequality, we can observe that the sum individual minimum eigenvalues of each layer's Gram matrix provides a lower bound on the total minimum eigenvalue governing convergence. Adding negative and exponential on both sides, we know that.
exp min (h)) 2 expeexpiiiiiee (Amin )
(21)
Hence, ΣH Amin G can be replacod with Amin Ei= (h)) in the convergence theorem for multi-layer networks. Hence, DH network. Therefore, Theorems and are transferable to deep neural networks with H hidden layers.
(h)
hh Amin G utilised by Dextr, also governs the convergence rate of deep neural
(h)
A.3 Detailed approximation to convolutional layer
We now provide a detailed approximation of single-layer multi-sampled fully connected layer to convolu- tional layer. Jiang et. al. (2023) show that the convolutional layer operation with an input Vin E Tgexaxxx and a filter w E RR XXXX with a stride of one and zero padding, can formally be expressed as
Cin Σ
[Fout] jij
[w0 (10))a 1attt1 (mn
c=1
22

---

Published in Transactions on Machine Learning Research (08/2025)
Table 6: Comparison of the Spearman rank correlation coefficient on NATS-Bench-SSS across different datasets for various zero-cost proxies.
Dong et al.
2021
Methods
CIFAR-10
CIFAR-100
ImageNet
#params
0.72
0.73
0.84
Fisher
Turner et al.
2020
0.44
0.55
0.47
Snip
Lee et al. 2019
0.59
0.62
0.76
Grasp
Wang al.
2020
-0.13
0.01
0.42
Synflow
Tanaka et al. 2020
0.81
0.80
0.57
Grad
Norm
A Abdellattah et a1
2021
0.51
0.49
0.67
NTK
Chen et al.
2021c
0.34
0.29
0.28
Zen
Lin et al.
2021
0.69
0.71
0.87
ZiCo
et al.
2023
0.73
0.75
0.88
MeCo
Jiang al. 2023)
-0.79
-0.87
-0.86
Dextr (ours)
-0.63 + 0.006
-0.60 + 0.005
-0.67
0.006
where in and w represent the e-th channel of Iin and w respectively, (k - 1)/2, and i E [w), E [h] Next, Tout and each input channel zin can be flattened into one-dimensional vectors, Bout E Rdx and oi E Rdx1 respectively, where w x This transformation leads to the following approximation, viewing the convolutional layer as multi-sample fully-connected network:
Tout Σ
A
subject to the following constraints:
Ag E dxdx [Aclij =[( = (c- 1)d i).
Be E ddd [Ba]k] [[(c - 1)d < ed),
Be Wsatisfying weight sharing constraints.
Here, dn = Cm x dl and W E Rdxds is the weight matrix. We can further simplify this by relaxing the second constraint to B. = 1d, and ignore the last constraint. As a result, we view each flattened input channel zi as an independent data sample, forming a multi-sample fully-connected network.
A.4
Additional Experiments
A.5
NATS-Bench-SS5
We now conduct correlation experiments on the NATS-Bench-SSS (Dong et al. 2021 benchmark. The XATS-Bench-SSS benchmark is fundamentally different from other correlation benchmarks (Dong & Yang, 2020 Ying al. 2019 Zela al. 2022), as contains architectures of varying numbers channels. We follow the same evaluation protocol as the other correlation experiments, detailed in Scction 4.1 of the main paper. We report. the mean Spearman Rank Correlation Coefficient p and standard deviation, averaged over 3 rums of Dextr in Table 6 and compare it with various baselines.
We observe from the results that in unlike other benchmarks, our approach exhibits nogative correlation weaker than some of the previous methods in the NATS-Bench-SSS benchmark. Upon investigating, we found out that this discrepancy arises due to the sensitivity of the condition number c(X) to the number of channels, similarly exhibited by McCo (Jiang al. 2023 This behaviour specific the NATS-Bench- SSS benchmark as it contains architectures of varying number of channels. We rectify this behaviour for this benchmark through the imissatio procedure detailed in the Section A.5.T
23

---

Published in Transactions on Machine Learning Research (08/2025)
Table 7: Comparison of the Spearman rank correlation coefficient between Dextr and the optimised version of Dextr oDe on
Dong al. 2021
Methods
CIFAR-10 10
CIFAR- 100
ImageNet166120
Dextr
-0.63
-0.60
-0.67
Dox
0.56
0.66
0.65
A.5.1 Dextr optimisation
As observed in the SEITS-Benc--SSS (Dong al. 2021 correlation experiment detailed in Table 6 Dextr achieves a negative correlation with the accuracy of the architecture. We utilise the optimisation procedure detailed by [Jiang et al. 2023) to fix this discrepancy. Specifically, instead of considering all the channels of the network layer, we randomly sample a fixed number of channels and calculate the Dextr value using the formula
log
1
Σ 1=1
-log(1 x()))
Rey (Xx')
DextTopt
(22)
log
1+
log(1 x(0))
Boi
where ay is the total number of channels of the layer, / is the number of sampled channels, and X is the concatenated feature map matrix using the sampled channels. This formulation restricts the dimension of the feature map matrix X and eliminates the effect caused by the varying mumber of channels. We present the results of this optimisation procedure on the SAIS-Bench-SSS. benchmark in the Table 7 As observed, while Dextropt fixes the discrepancy for the NATS-Bench. fails to outperform the original formulation of Dextr in two out of three datasets.
(Dong al., 2021) benchmark, it
A.5.2 MobileNet-v2
Our experiment on the MobilcNet-v2 (Sandler et al.- 2018 search space follows the standard evaluation protocol (Li et al. 2023 Lin et al., 2021 Lee & Ham 2024h of searching for an architecture through evolutionary algorithm with FLOPs constraint 450M. We use the same experimental settings as (Lee & Ham 2024) with a population size of 1024 and a number of iterations as 1e5. Next, we train the selected architecture on ImageNet and report the floating point operations (FLOPs), Top-1 accuracy, and search cost in GPU Days in Table We observe from the results that method marginally improves the previous best method AZ-NAS with smaller scarched model.
A.6 Implementation Details
We now elaborate upon the procedure for the calculation of the Dextr value. First, we input a label-free data sample, ie. an image from the CIFAR-10 10 dataset to a network from the respective benchmark and perform one forward pass with the image. In the forward pass, we calculate the sum of the inverse of the condition
number of the layer output for each layer, i.e. ( 1Xx()x)). Next, we obtain the extrinsic curvature x(0)
by generating random circular input and then calculating the velocity and accelcration vectors (Eq. 5). Finally, calculate the Dextr value through Eq. 8.
A.7 Experimental settings
We run all the search procedures on a single NVIDIA RIX A6000 GPU with 48GB memory. For our correlation experiments on NAS-Bench-101 (Ying et al. 2019), NAS-Bench-301 (Zela et al. 2022), and TransNASBench-100 (Duan et al. 2021), we utilise the same experimental configuration as NAS-Bench-
Suite-Zero Krrihhakkmmrr et al. 2022 SWAPNAS (Peng et al. 2024 For correlation experiments
24

---

Published in Transactions on Machine Learning Research (08/2025)
Table 8: Quantitative comparison for the MobileNet-v2 (Sander et al. 2018 search space with FLOPs constraint of 450M. We report the top-1 accuracy, floating point operations (FLOPs) of selected networks on ImageNet (Deng al,, 2009), the type of search method- multi-shot (MS), one-shot (OS) zero-shot (ZS), along with the search cost in GPU days. The best approach is indicated bold and the second-best approach is indicated as underlined.
Method
FLOPs
Top-1 Acc.
Type
Search Cost.
(M)
(%) t
(GPU Days)
NAS-Net-B Zoph et al.
2018
488
72.8
MS
1800
CARS-D
Yang et al. 2020b
496
73.3
MS
0.4
BN-NAS
CCen et al.
2021a
470
75.7
MS
0.8
OFA
(Cal ct al.
406
77.7
OS
50
RLNAS
Zhang el al.
2021
473
75.6
OS
DONNA
Moons et al.
2021
501
78.0
OS
405
paraams
451
63.5
ZS
0.02
ZiCo
Li et al.
2023
448
78.1
ZS
0.4
AZ-NAS
Lee & Ham
2024
462
78.6
7S
0.4
Dextr (ours)
457
78.8
ZS
0.6
sep cooy
cony 3x3
1k-2
sep. coiyy
c.
sep. opp.ony
NE.00 35
conw 3x5
sep. Sx5
ep 20.0 33
sep. cony 3x3
(a) MeCo Jiang et al. mal cell)
2023 (Nor-
(b) ZiCo cell)
Li al. 2023 (Normal
(c) Dextr (Normal cell) (ours)
uR per
14
(d) MeCo Jiang et al. 2023 (Re-
(e) ZiCo Li et al. 2023 tion cell)
(Reduc-
duction cell)
(f) Dextr (Reduction cell) (ours)
Figure 4: Found architectures from three zero cost proxies in the DARTS Liu al. 2019 search space for
the ImageNet experiment using Zero-Cost-PT [iiang 2023).
201hhhnc we utilize the experimental setup as McCo (Jiang et al. 2023 Morcover, the experimental
configuration of the search on DARTS search space [Liu et al.
2019) using Zero-Cost- (Xiang el al.) 2023)
algorithm is detailed Table 9 The training on Image Net for DARIS search space follows the same settings
and protocol as (Lukasik et al.
2022 Asthana al.) 2024 Chen al. 2021c). Lastly, for our AutoFormer
and MobileNet-v2 experiments,
we utilize the same experimental framework TF-TAS (Zhou al. 2022)
and AZ-NAS (Lee & Ham
2024
25

---

Published in Transactions on Machine Learning Research (08/2025)
Table 9: Experimental settings for search in DARTS search space through algorithm.
Settings
Search settings
Batch Size
Cutout
False
Cutout Length
Learning Rate
0.025
Learning Rate Min
0.001
Momentum
0.9
Weight Decay
3e-4
Grad Clip
5
Init Channols
16
Layers
Drop Path Prob
A.8 Visual Comparison
Figure presents visual comparison of the architectures generated by our proposed proxy, Dextr, alongside those produced by prior works, specifically MeCo 4Jiang et al. 2023) and ZiCo (Li et al. 2023). The normal cell (used for feature extraction) generated by Dextr demonstrates a broad range of operations, including skip connections, separable convolutions, and dilated convolutions, while maintaining a densely connected structure. In contrast, the normal cell produced by McCo exhibits simpler connoctions, which limits the network's expressivity. Similarly, although the normal cell generated by ZiCo features dense connections, it employs less diverse set of operations compared to Dextr.
Furthermore, the reduction cell (used for downsampling) generated by Dextr incorporates a more diverse set of operations. It effectively balances feature reuse through skip connections and flexible transformations utilizing dilated and separable convolutions. Thus, this design is particularly well-suited for complex tasks that require robust hierarchical representations. Lastly, we observe that the network selected by Dextr is shallower than other approaches mentioned, which might seem counterintuitive, as it suggests the network does not have enough expressivity. However, since do not characterise expressivity by explicitly maximis- ing depth (or minimising width), arguc that in this case, the found network from Dextr still maintains adequate expressivily through its choice of operations. To prove this claim, we measure the expressivity by comparing the curvature of the networks presented in Figure ! We empirically find that the architecture found through our approach has more curvature (1.2 x 108) than the architectures found through ZiCo (cur- vature = 7.7 x 107) and MeCo (curvature= 5.8 107). This implics that even if the chosen network by Dextr does not exhibit the deepest structure, it still more expressive than the networks found through ZiCo and MeCo, due to its chosen operations, which proves the effectiveness of Dextr in capturing expressivity. This indicates that while deeper networks often exhibit greater expressive capacity, depth alone is not sufficient indicator., i.e. there can be networks which are shallow, yet expressive, That is also the reason why, instead of utilising depth directly, we utilise a more reliable metric used in the literature (Poole et al. 2016: Chen et al. 2023), i.e. curvature of the output.
the one depicted in Figure 4
A.9 Visualisation of correlation
We provide scatter plots between the Dextr score and the validation accuracy of the network across multiple correlation benchmarks, including NAS-Bench-101, NAS-Bench-201, MAS--ennh--301, and TransNAS-Bont 101-micro in Figure 5) All the plots reveal strong posilive correlation between the Dextr score and the performance of the network.
A.10 Limitations and Future Work
We now discuss some limitations of our work. Firstly, although our proxy does not require labelled data for computation, it still needs to perform slightly expensive calculations of the derivative of the output
26

---

Published in Transactions on Machine Learning Research (08/2025)
NB101-CF10
NB201-CF10
Correlation-0.65 0.65
Correlation-0.90
Validation Accuracy
Validation Accuracy
60
20.
1.0
1.5
2.0
2.5
3.0
20
40
80
Dextr
Dextr
N8201-CF100
NB201-ImNet120
Correlation 0.91
Correlation=0.87
Validation Accuracy
70
Validation Accuracy
60
30-
20
4004
1.55
1.50
1.75
2.35
2.75
12
1.4
1.6
2.0
2.2
2/4
2.6
Dextr
Dextr
NB301-CF10 Correlation=0.44
TNB-Object Correlation 0.53
Valiciation Accuracy
Valiciation Accuracy
82-
00-
Dextr
Dextr
TNB-Scene
TNB-Jigsaw
C0rrelation=0.75
Correlation:0.55
Validation Accuracy
50-
Validation Accuracy
R:
40
@lalthoe the
80
1.6
1.8
2.0
2.2
2.4
2.6
2.8
Dextr
Dextr
Figure 5: Scatter plots between Dextr value and validation accuracy for NAS-Bench-100 Ying et al. 2019
TAS--Benhh 201 (Dong & Yang 2020), NAS- MAS-Bench-301. (Zela et al. 2022) and TransN AS Bench- -icro 101-micro
(Dunn et al. 2021
to compute the velocity v00) and acceleration a00) vectors, essential to calculate the expressivity of the network. Future works can focus on this issue by utilising different characterisation of expressivity in the approach. Lastly,
theoretical analysis only applics to ReLU and GeLU networks. Extending the be important future
theoretical framework to other activation functions such Sigmoid and Tanh work direction. Lastly, Lemma 1 requires at least one absolute entry in X to be greater than 1. Although this is generally the case, some uncommon data normalisation tecnhniques can falsify this assumption.
27


Reviews:
[{"review_id": "9o4Hg8r8YL", "reviewer": "Reviewer_abwc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- Lower collinearity being correlated with higher expressivity and better performance makes a lot of intuitive sense, and the authors do a great job of motivating this particular approach in the introduction. \n- Dextr has a clean theoretical motivation that is mostly easy to follow. \n- Dextr appears to substantially outperform most existing methods on many of the tasks on which the authors evaluate. Furthermore, the experimental results cover both simplified NAS settings where the entire search space can be evaluated and ranked explicitly (e.g. NAS-Bench-201), as well as more realistic settings with much larger search spaces (e.g. DARTS). \n\n**Weaknesses**\n- It's not immediately clear to me why collinearity would arise as a property of the architecture. Rather, I would think that this would instead be a property of poor initialization. Can the authors elaborate on their intuition for this, or perhaps provide a motivating example of an architecture that is prone to collinearity? \n- While not crucial to the evaluation, it would be useful to see how Dextr performs across different tasks using the same search space but with wildly different final rankings. For example, Figure 3 in NAS-Bench-360 [1] shows that while NAS-Bench-201 rankings are mostly correlated across vision tasks, they become completely uncorrelated when comparing CIFAR-100 to prosthetics control and PDE solving tasks. Naturally, zero-cost proxies that are data agnostic would completely fail in such settings, which is discussed in [2]. It makes intuitive sense that unlabeled data usage should overcome this limitation of data agnostic proxies, but making this more explicit either with an additional discussion or experiment would make the choice to use unlabeled data more compelling. With that said, this isn't a central claim of the paper, so I don't view this as crucial to the evaluation. \n- Table 5 shows a comparison between Dextr and the harmonic mean between the Zen (which focuses on expressivity) and ZiCo methods (which focuses on convergence and generalization). The reason for the comparison is that Dextr, on the other hand, balances expressivity, convergence, and generalization roughly by taking the harmonic mean of a curvature term and an inverse condition number term. What seems missing from this table are the individual performance values for Zen and ZiCo on their own---does the harmonic mean somehow make performance worse in the case of these proxies? For that matter, it would also be useful to understand how Zen compares to just using the curvature term in Dextr (both expressivity focused), and how ZiCo compares to just using the inverse condition number term (with both focusing on convergence/generalization). \n\n[1] https://arxiv.org/abs/2110.05668\n[2] https://iclr-blog-track.github.io/2022/03/25/zero-cost-proxies/", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Dextr, a 'zero-cost proxy' NAS technique that uses unlabeled data to score architectures---this is often used to either generate a ranking over a small search space or to guide a local search in a large search space where architectures cannot easily be enumerated. Most zero-cost proxy techniques either use labeled data, which might not be realistically available, or they do not use data at all, which make such techniques brittle to changes in the target task. The actual technique is motivated by two observations: 1. feature collinearity negatively impacts performance, and 2. network outputs at random initialization that are more curved implicate higher expressivity, perhaps as a result of lower collinearity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dERgQkrJSG", "reviewer": "Reviewer_o4YZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strenghts**\n- Important and interesting research on zero-shot proxies for NAS, which helps to decrease the cost of NAS methods\n- It is fully reasonable to construct a zero-shot proxy that incorporates measures of expressivity, generalizability, and convergence of a neural network\n- The experimental setup is reasonable and shows that the proposed score improves upon existing zero-shot and one-shot NAS baselines\n- Generally well-structured paper\n- Proofs of Theorems given in the Appendix\n\n**Weaknesses**\n- It seems that the theoretical motivation of the proposed score only provably holds for small ReLU neural networks with one hidden layer\n- It would help to provide an intuition on Eq. 3, 4 & 5, giving the reader an idea why these scores measure convergence, generalizability, and expressivity reliably (can also be given in the Appendix)\n- Similarly, Remark 3 should be discussed in more detail. The authors claim that the results from Sec. 3.2.1 and Sec. 3.2.2 can be transferred to CNNs (at least approximately) without giving a rigorous theoretical grounding. Since in CNNs, weight sharing is an integral part of the architecture, which is not reflected in the theory in Sec. 3.2.1 and Sec. 3.2.2. This must be clarified\n- In Eq. 8, the authors define their Dextr score, which assumes that one can sum over the inverse of feature condition numbers (which are related to the Gram matrix as shown). However, the theory only deals with MLPs with one hidden layer, making a simple summation questionable in this setting: Since the feature condition number of layer $l$ depends on the feature condition number of layer $l-1$, and since summing over these values assumes independence, I'm not sure if this summation can be reliably done.\n- Akin to the generalization of their score/theory to CNNs, the authors argue that - since under some conditions Transformers behave like CNNs - one can also transfer their score and theory to Transformer architectures. While in general I agree that this is possible under some conditions, I think the authors should discuss this in more detail: As they correctly say, Transformers only behave like CNNs if, e.g., the number of attention heads is set carefully, this might not hold in Transformer search spaces used in practice.\n- In Sec. 4, an additional ablation would be nice to show that Dextr indeed captures convergence, generalizability and expressivity properties of neural networks.\n\n**Minor Weaknesses/Questions**\n- Assumption 1 is not really an assumption, but a Lemma.\n- Tab. 1 should be moved into Sec. 4\n- in Tab. 4, no standard deviation is shown for the baseline scores. Also, the std is only computed using 3 runs, this should be increased (also given that computing these scores should be cheap). \n- Why did the authors decide not to compare their zero-shot method to the baselines on the benchmarks they have used for the correlation experiments?\nTab. 4 should be reported as a plot to increase readability\n- Tab. 5 can be merged with Tab. 1\n- Sec. 4.3.3: How do the authors explain that the Dextr peaks at layers expanding the dimensionality?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce a novel score for zero-shot neural architecture search (NAS) that aims to balance generalizability, convergence, and expressivity of neural networks. To construct their score, they exploit that the minimum eigenvalue of the gram matrix of a neural network w.r.t. its input data correlates with convergence and generalizability of a neural network. Additionally, they make use of measuring the output curvature of a neural network using first-order and second-order gradient information with respect to the network input.\nIn the experiments, it is shown that the proposed score (Dextr) exhibits better Spearman correlation with architecture performances than existing scores, which leads to better results in NAS on two tasks they consider.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should provide more intuition on Eqs. 3, 4, and 5 (see above) and consider adding a more detailed discussion on the generalization of their theory to CNNs and Transformers. This seems to be important since their experimental evaluation is fully based on CNN and ViT architectures, while their theory only considers simple MLPs, introducing a significant gap between theoretical insights and experimental findings.\n\nTo increase readability, the authors should consider incorporating my suggestions in **Minor Weaknesses/Questions** above.", "broader_impact_concerns": "n/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UWXAXklDB6", "reviewer": "Reviewer_qJ1j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Most of the motivation for the paper is well-grounded. In particular, the reviewer appreciates the writing in the third paragraph of the introduction (where No Free Lunch theorem is brought up). Overall, the writing of this manuscript is smooth.\n- The method provides a fast and accurate zero-cost proxy.\n- The authors provide rigorous mathematical proofs and explanations to back their method.\n- The method is evaluated on a plethora of different NAS environments ranging from cell-based benchmarks [3] to Vision Transformers [1] and others. \n- Figure 1(a) is very effective.\n- Reviewer appreciates additional results in the appendix they are informative. \n\nWeaknesses:\n- The motivation for having a ZCP that covers the \"expressivitiy\" of a network is not very well established. Convergence and generalisation are straightforward, but expressivity not so much. From the reviewer's point of view, the utility of expressivitity is as a means to improve convergence and generalisation; by modeling more complex functions, the network can better achieve its end-to-end objectives.\n- Table 1, there is some concern: Also, there is some concern about the results in this table, e.g., for NB301, no method is able to achieve over 0.5 SRCC. With that in mind, what is the motivation for using a ZCP at all on this benchmark when one could just use a performance predictor [4]? Also, the reviewer is puzzled by some of the TNB results, e.g., on Object, only one ZCP achieves negative SRCC, but most ZCP performance (including Dextr) is quite mediocre, while on Scene, several ZCPs obtain negative SRCC but others achieve above 0.6 and Dextr achieves an impressive 0.75. Can the authors provide any commentary on why this happens? \n- Table 2 results are more of a mixed bag. Dextr is finding a larger network in terms of #params that performs worse than that found by Oneshot and Predictor methods. While the cost of Dextr is smaller than these methods, Dextr and some Oneshot/Predictor methods all find a network in less than 1 GPU day. Further, given that the cost of training a neural network on ImageNet is several GPU days, the search cost savings do not justify the downstream performance inefficiencies. \n- While ablation studies are provided, the reviewer does not feel that they are well-explained. E.g., it is hard to see a clear pattern in Table 4, while Figure 2 is more readily understood as higher independence -> better performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Dextr, a Zero-Cost Proxy (ZCP) for Neural Architecture Search (NAS) that aims to balance convergence (neural network ability to reach a loss objective), generalisation (performance on a test set) and expressivitity (ability to model complex function). Dextr has a rigorious theoretical grounding in Singular Value Decomposition (SVD) and Riemannian geometry. Further, Dextr is evaluated on multiple benchmarks including NAS-Benchmarks, AutoFormer [1] and MobileNets [2] to demonstrate its veracity. Finally, the authors provide some ablation studies of their approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The reviewer would ask for a greater elaboration on task/data agnostic and data-based proxies in the 2nd paragraph of the introduction, to help future readers to better understand the demarcation betweeen each of them. \n- Figure 1(b). Since this is the first figure mentioned chronologically following the text, it should be the first to appear. Also, revise formatting to make the figures bigger and have larger axis/legend font size.\n- Table 1 should be moved to the top of the next page (pg. 9) so as to be closer to where it is actually discussed. \n- Table 2: Missing comparison with a transferable RL NAS [5] which has similar search cost/results.\n- Sections 4.1 and 4.2 should be revised and interwoven. E.g., first have the paragraph explaining the setup leading to Table 1, then the paragraph that introduces Table 1 and discusses results. Then follow with setup and results discussion for Table 2, then 3, etc. This helps a reader understand the context of how you got the results in a Table.\n- Table 4 should either be a wraptable environment or at the top of a page.", "broader_impact_concerns": "N/A\nOverall, this is a well-written manuscript with mostly solid results though missing some comparisons and in need of some writing tune-up in places, specifically Section 4. \n\nReferences:\n\n[1] \"Autoformer: Searching transformers for visual recognition\" - CVPR'21.\n\n[2] \"Mobilenetv2: Inverted Residuals and Linear Bottlenecks\" - CVPR'18.\n\n[3] \"NAS-Bench-101: Towards reproducible neural architecture search\" - ICML'19.\n\n[4] \"How powerful are performance predictors in neural architecture search?\" - NeurIPS'21.\n\n[5] \"L2NAS: Learning to optimize neural architectures via continuous-action reinforcement learning\" - CIKM'21.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)