Rethinking Neural Operations for Diverse Tasks
Authors: Nicholas Carl Roberts
Mikhail Khodak
Tri Dao
Liam Li
Christopher Re
Ameet Talwalkar
Venue: NeurIPS 2021 Poster (2021)
Keywords: automated machine learning
neural architecture search
partial differential equations

Abstract: An important goal of AutoML is to automate-away the design of neural networks on new tasks in under-explored domains. Motivated by this goal, we study the problem of enabling users to discover the right neural operations given data from their specific domain. We introduce a search space of operations called XD-Operations that mimic the inductive bias of standard multi-channel convolutions while being much more expressive: we prove that it includes many named operations across multiple application areas. Starting with any standard backbone such as ResNet, we show how to transform it into a search space over XD-operations and how to traverse the space using a simple weight sharing scheme. On a diverse set of tasks—solving PDEs, distance prediction for protein folding, and music modeling—our approach consistently yields models with lower error than baseline networks and often even lower error than expert-designed domain-specific approaches.

Rethinking Neural Operations for Diverse Tasks
Nicholas Roberts' University of Wisconsin-Madiin Madison ni mickttrobssssecs wwic.. wisc.edi edu
Mikhail Khodak Carnegie Mellon University thodak@cmu.eddi
Tri Dao
Stanford University
trid@stanf edu
Liam Li
Christopher Ré
Hewlett Packard Enterprise me@1 iamcli.cooo com
Stanford University
chri Chrismrecss. stanford.edu
Ameet Talwalkar
Carnegie Mellon University & Hewlett Packard Enterprise talwalkar@cmu. edu
Abstract
An important goal of AutoML is automate-awan the design of neural networks new tasks in under-cxplored domains. Motivated by this goal, we study the problem of enabling users discover the right neural operations given data from their specific domain. We introduce search space of operations called XD-Operations that mimic the inductive bias of standard multi-channel convolutions while being much more expressive: we prove that it includes many named operations across multiple application areas. Starting with any standard backbone such ResNet, we show how to transform it into a search space over XD-operations and how to traverse the space using simple weight-sharing scheme. On diverse of tasks- solving PDEs, distance prediction for protein folding, and music modeling- approach consistently yields models with lower error than bascline networks and often even lower error than expert-designed domain-specinf approaches.
1 Introduction
Automated machine learning (AutoML) and neural architecture search (NAS) are often motivated by a vision of democratizing ML by reducing the need for expert design on a variety of tasks. While NAS has grown rapidly with developments such weight-sharing [36] and "NAS-benches" [47, 49], most efforts focus on search spaces that glue together established primitives for well-studied tasks like vision and text [32, 26, 45, 25] or issues such as latency [8, 13). In this work, we revisit the broader vision NAS and propose to move towards much more general search spaces while still exploiting successful network topologies. To do
focus expanding the set of operations, which is usually fairly small; for example, that of the well-studied DARTS space has eight elements: a few types of convolution and pooling layers [32]. The baseline approach for expanding this set att-adingg operations une-by-one-eee poorly and will not result in new operations when faced with new types of data.
Our core contribution is re-imagining of NAS operation spaces that drastically expands this set in principled fashion to include both standard operations as well as wide range of new ones. To do so we exploit the fact that most standard operations used in modern NAS return linear transforms diagonalized by the discrete Fourier transform (DFT). Replacing the DFT matrices in the diagonal decomposition by more expressive family of efficient linear transforms known as Kaleidoscope or
denotes equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

backbone
standard discrete NAS search space
search space XD-operations
network
Conv(w)
Maxhoool
A AxgPool Pool
per
model weights
AvgPool(x)
DilatedConr diaciee--
L-0 Roct
M DPP
DiilteedCon
Fouria Noural:
irpul edge
K
X
M x
Conr a Pecuutaatio
GrapliCouv
Tunning MAS gurithimm
expressive
Transoondoouv
picking oporation edge 12.4)
diagonalization
relaxation
Figure I: Diagram of our search space depicting a NAS method picking an operation for an edge in backbone network (left). Instead of choosing from a discrete search space, we use a relaxation based on the convolution's 's diagonalization by the discrete Fourier transform in which the DFTs are replaced by K-matrices [10] K, L, and M (middle); these the main architecture parameters of our new search space over Expressive Diagonalization (XD) operations. This space contains most operations considered in standard NAS and many other important operations in variety of domains (right).
K-matrices [10] yields the set of Expressive Diagonalization (XD) Operations, which comprise large search space containing various types of grid-based convolutions and pooling, permutations, transposed convolutions, certain kinds of graph convolutions, the Fourier Neural Operator (FNO) [30], and infinitely many more. This broad expressivity reflects the key insight of our work: that many of the most important neural operations in ML consist of multiple channels that apply weights to inputs x by computing
K (La)
(1)
where the matrices K, L, and M efficient (to represent and apply) and shared across channels.
We leverage XD-operations take critical steps towards broader NAS that enables the discovery of good design patterns with limited human specification from data in under-explored domains. To do so we develop a simple procedure which transforms any backbone convolutional neural network (CNN) into architecture search space by replacing its operations with XD- XD-operations. This space is then searched using a simple weight-sharing algorithm that needs only a small amount of tuning to find effective operations. As simple first demonstration, that are 15% more accurate than standard discrete search spaces on permuted CIFAR- 10, highlighting the fragility of standard NAS operation spaces new datasets, and thus the need for -Dooperations.
show that XD-operations yield models
As our main evaluation, we demonstrate the effectiveness of XD-operations a series of applications showing that, starting from vanilla CNNs, they consistently outperform custom-designed operations.
Learning to solve partial differential equations (PDEs): when substituted into simple CNN backbone, XD-operations outperform convolutions and the dense prediction NAS method Auto- Deeplab [31], and even achieve lower error than custom-designed state-of-the-aar operations (FNOs [30]) across three problems with different dimensionalities (Burgers' equation, Darcy Flow, and Navier-Stokes). Our method also maintains consistent performance across different resolutions, a major stated advantage of FNOs over previous methods.
Protein folding: on the task of predicting residue distances a polypeptide chain-a key compo- nent of the protein folding problem- we substitute XD-operations into vanilla ResNets and achieve lower error than cyclically-dilated ResNets adapted specifically for this setting [1]. Furthermore, our ResNet-34 XD outperforms the reported error of the much deeper Dilated ResNet-258.
Music modeling: on two next-note prediction tasks, we show that substituting XD-operations into an undilated CNN outperforms temporal convolutional networks ("CNs)-exponentallly-iii 1d CNNs that themselves outperform standard convolutional and recurrent networks [5].
Code to reproduce these results available here: /ttps://githaen wtt.//iikkk11rrrbbrrtts/ Software to apply XD-operations can be found here: https / //gttttt....//./ httpuu..ccommkhhok///eeeeea.

---

Related Work AutoML is a well-studied area, with most work focusing on fairly small hyperparam- eter spaces [7, 24] or on NAS [12]. Most NAS operation spaces only contain a few operations such as convolutions [32, 33, 49, 111, which may not be useful for domains where CNNs are ineffective. Applications of NAS outside vision largely follow the same pattern of combining numan-designes operations [35, 43]. On the other extreme, Autr [37] demonstrates the possibility of evolving all aspects of ML from scratch. We seek to establish a middle ground with large and domain-agnosti search spaces that still allow the use of well-tested methods, e.g. stochastic gradient descent (SGD).
Several papers have generalized the DFT to replace layers in deep nets [9, 2, 10] in order to speed up or add structure to models while reducing expressivity. In contrast, we can replace convolutions and other layers while increasing expressivity by extending their diagonalization via K-matrices. As discussed in Section 2. using K K-matrices for this directly is inefficient for input dimension >> 1.
2 The Expressive Diagonalization Relaxation
In this section we overview our main contribution: a large, general search space of neural operations. Formally, we view an architecture as parameterizable object-a mapping from model weights to functions described by a labeled directed acyclic graph (DAG) G(V. E). Each edge in E has the form (u, v, Op), where u. v E V nodes and Op is an operation that can be parameterized to define some transformation of the representation at node u; node V aggregates the outputs of its incoming edges into new representation. For example, the popular ResNet architecture [15] has many nodes with two incoming edges, one labeled by the convolution operation Conv and one by the identity (skip-connect) Id, whose outputs it sums and passes to outgoing edges with the same labels. Each architecture has a source node taking in input data and an output node returning a prediction.
Neural architecture search is the problem of automatically selecting operation for each edge of G to optimize an objective.' For each edge e E E' NAS algorithm must pick one element a search space S= (Op, la E AA} of operations specified by architecture parameters a E A to assign to e; in past work, A usually indexes a small set of operations. As an example, we will refer to a variant Sdiscrete of the DARTS search space with parameters Adiscrete {1, ..... 8} where each operation is one of Zero, Id, MaxPoolyx3, AvgPoolyx3. ConV or 5x5, or DilatedConv 3x3,2 or xx,2 [32].
Our main contribution is a novel family of operations that comprise search space containing almost all these operations, in addition to many others that have been found useful on different types of data. The starting point of our construction of these XD-operations is the simple observation that all the operations Op E Sdiscrete listed above except MaxPoolax3 are linear, i.c. for any model weights w there exists matrix Aw such that for all inputs x we have Op(w)(x) = Awx. More specifically. all seven of them return convolutions: to see this note that Zero, Id, and AvgPool each apply convolution with filter 01x1, 11x1, and 13x3/9, respectively. This means that most of the operations in the DARTS search space which is representative of NAS operation spaces in computer vision share the convolution's 's diagonalization by the discrete Fourier transform (DFT). Formally, if Aw E R²² xn² the matrix representing a 2d convolution with filter w e RR of kernel size k E [n]], then for any 2d input x E R= we have
Conv(w)(x) = Awx = F-1 diag (Fw) Fx
Here [n] = (1,.... n), diag(z) denotes the diagonal matrix with entries z, w E R"" is an appropriate zero-padding of RRk, and F E C xn? is the 2d DFT (a Kronecker product of two 1d DFTs).
This diagonalization explicates both the computational and representational efficiency of the DARTS operations, as the DFT and its inverse can be applied in time O(n log n) and stored with On log bits. It also suggests a natural way to dramatically cxpand the operation space while preserving these efficiencies: just replace matrices F and F-1 in (2) by any one of a general family of efficient matrices. Doing so yields the single-channel version of our expressive diagonalization (XD) operations:
XD (w)(x) = Real (K diag (Lw) Mx)
(3)
Here architecture parameter a (K, L, M) sets the matrices replacing F and F-1 in Equation 2.
It is often defined as selecting both operations and graph topology [50], but if the set of operations contains the zero-operation Zero then the former subsumes the latter. For memory- all convolutions in the original DARTS search space are separable [32].
3

---

The main remaining question is the family of efficient matrices to use, i.e. the domain of the archi- tecture parameters K, L, and M. For this we turn the Kaleidoscope matrices, or K-matrices [10], which generalize F and F-1 to include all computationally efficient linear transforms with short description length, including important examples such as sparse matrices and permutations. To obtain this general family, K-matrices allow the DFT's butterfly matricess whose products take on different values. While a detailed construction of
yield its efficient implementation K-matrices can be found in the original paper, we need only the following useful properties: they are as (asymptotically) efficient to apply as DFTs, are differentiable and can thus be updated using gradient- methods, and can be composed (made "deeper") to make more expressive K-matrices.
Specifying that K, L, and M in Equation are K-matrices largely completes our core contribution: a new search space SXD of XD-operations with K-matrix architecture parameters. We give full multi-channel formalization in N dimensions, as well as an overview of its expressivity, in Section 3. First, we note some key aspects of this new search space:
Complexity: XD (w) requires three K-matrices and ((1) filter weights to represent, i.e. de- scription length On log nt); this is larger than regular convolution (which has no architecture parameters) but is not quadratic in the input size like a linear layer. Applying XD requires multi- plication by three K-matrices, yielding a theoretical per-channel time complexity of On log n). matching the efficiency of convolutions. However, as -peorrraio strictly generalize convolu- tions they are more expensive to apply in-practice; we detail these costs both in the application sections and as appendix table, and we view improving upon them as an important future direction. Initialization: a crucial advantage of XDoopraaiioss is that we can initialize warm-star start search using operations with known constructions. In particular, since we can recover convolutions (2) by setting architecture parameters K F L F, and M F in Equation 3, can always start search with any CNN backbone. We use this extensively in experiments.
K-matrices: as they contain all efficient linear transforms, K-matrices can represent all functions returned by XD-operations, including convolutions. However, for input dimension and filter size > 1 the only known way is to apply K-matrices directly to flattened inputs x E RR" N yielding much worse description length O(n" log n). In contrast, detailed in Section 3, our diagonalization approach uses Kronecker products to apply DFTs to each dimension separately, yielding description length On log n). It is thus the first (and in some sense, "right") method to such matrices to replace convolutions. Furthermore, diagonalization allows us to separate model weights w from architecture parameters a, letting the former vary across channels while fixing the latter.
Finally, we address the fact that the architecture parameters of SXD continuous, not discrete, contrasting with much of the NAS literature. This can be viewed as a natural extension of the weight-sharing paradigm [36], in which continuous relaxation enables updating architecture pa- rameters with gradient methods. For example, many algorithms traverse the relaxed DARTS
search space Sdiscrete = { - Op, (Yg 2 0, Ei =11) defined via DARTS operations
Op, Sdiscrete and architecture parameters A in the 8-simplex; most search spaces then require discretizing after search via a rounding procedure that maps from the simplex to Adiscrete- Note that the fully continuous nature of XD-operations means that we will only evaluate the final network re- tumned by search. In particular, while some weight-sharing papers also report the correlation between true architecture performance and that indicated by the shared weights [46], there is no obvious way to define a ranking or sampling distribution over XD-operations in order to do so. This also means that our final architecture will not be more efficient than the supernet, unlike other weight-sharing methods that do discretize.
3 XD-OPerations and Their Expressivity
Here we formalize XD-operations and show what operations they include. We first define operations:
Definition 3.1. A parameterizable operation is mapping Op W + F from parameter space W to a space F = (Op(w): : X + >/w E W) of parameterized functions from input space X to output space y. A search space set of operations with the same W, X, and y.
For example, if X = = RD and W = Raxn then each W E W defines a parameterized linear layer that for each x E returns Lin(W)( = Wx. Here Lin the parameterizable operation and for each W the linear map Lin(W) is the parameterized function.

---

From Definition 3.1, we say search space can express specific operation if it contains it, Crucially, the ability of parameterizable operation Op, express a parameterized function Opy(w) output from another operation Op2 given the right set of weights w does not imply that a search space containing Op, can express Opz. For example, Lin(I,) = (d) W E R but Lin Lin of (d) A W * I, so search space containing the linear operation Lin cannot express the skip-connection Id, despite the fact that Lin can be parameterized to compute the identity.
Formalizing Multi-Channel XD-Operations Recall the single-channel XD-operation XD in Equation 3 specified by three-matrix architecture parameter a = (K, L, M). For input dimension N 2 1, every matrix B E a is Kronecker product of N K-matrices of depth d E 2i. i.e. B = ==1 B, for K-matrices B; E Ca of depth dnj d'2). or dis for B = K. L, or M, respectively. 3 Roughly speaking, XD return any linear operation that is diagonalized by K- matrices and is thus efficient to compute and represent, e.g. any convolution (recall we recover the diagonalization of Conv(w) in Equation 2 by setting K, L, and M appropriately in Equation 3). However, XD cannot represent efficient parameter-free operations such 8kip-connections and average-pooling, both common in NAS. In particular, the only way to always ignore the model weights is to set one of the K-matrices zero, producing the zero-operation. We avoid this by adding bias C"" as an architecture parameter, yielding the biased single-channel XD-operation."
XD (,b( Roal (K diag(Lw (Lw + b)Mx)
This lets us define skip-connections (set K M- I N, L = 0n XnN, and b = vw) and average-pooling (set = F- ON N,,, F, and b to F multiplied by a pooling filter).
Lastly, we use XD! a.b construct multi-channel "layers" that pass multiple input features through multiple channels and re-combine them as multiple output features. This follows the primary way of using convolutions deep nets. The key insight here that we will share the same parameterizable operation (specified by a and b) across all channels, just as in convolutional layers.
Let (a, C) be architecture parameter containing a triple (K, M, of Kronecker products of N K-matrices with depths d E Z4, a bias C" aand channel gates C E gexe.5 Using "A" to denote concatenation, the XD-operation XD, of depth specified by a is a parumeterizable operation on parameter space W Rxxex consisting of c² filters of size funttion on X = Rxxm N for m S n mapping every x E X to
Definition 3.2.
ke E [n]N that outpus parameterized functions
XDa(w)(x) = CRJ C XD o, D.DDD..(Wr.l (WI1)))(11))
(5)
The last architecture parameter C allows interpolation between all-to-all layers (C e. e.g. multi-channel convolutions, and layers where each channel is connected to one other channel (C = I.), e.g. skip-connections and peragg-pooolng. We note that we use SXD to describe the set of operations covered by Definition 3.2 and conclude our construction by discussing two properties:
Kernel size: the weight-space available to an XD-operation is Rxxxxx" however, since we will initialize search with existing CNNs, we will zero-pad to have the same weight- space Rexex k the convolutions with filter size à < n that they replace. This preserves the weight count but also means that if the backbone has 3 x 3 filters our search space will not contain 5 x 5 convolutions. Experimentally, we find that relaxing the constraint to allow this does not significantly affect results image tasks,
as
do not do so in subsequent applications to avoid increasing the weight count. Depth: XD-operation's 's depth is triple describing the depths of its K-matrices K, L, and M. Increasing it trades off efficiency for expressivity; for example, in the next section we describe operations that can show are contained in SXD if L M have depth > By default we will set the depth to be the minimum needed to initialize search with the backbone operation.
2 A depth-d d K- K-matrix is a product of d depth-1 1 K-matrices. "Zero- parro--aaiin&&a x as well lets the input to be smaller than the output if needed, e.g. for transposed convolutions. For simplicity we formalize the case where all N dimensions have the same input size and there is an identical number of input and output channels; both are straightforward to extend.
5

---

Expressivity of XD-Operations For many papers that replace deep net layers with efficient linear transforms [34, 10). the question of expressivity comes down to the transform capacity. For example, layers with a K-matrix in every channel can represent a different transform in each, thus allowing the output to be any combination of efficient linear operations. Our case is less straightforward since we care about expressivity of the search space, not of parameterized functions, and our approach is less-expressive by design as all channels share K-matrices K, L, and M. The latter can be thought of as useful inductive bias on NAS: the set of XD-operations is still much broader than the set of convolutions, but the way in which model weights are applied is the same across all channels.
Expressivity results are way to see if this bias is useful or constraining, Here we summarize some important operations that are 1d XD-operations; proofs can be found the appendix and are straightforward to extend to multi-dimensional inputs. Formally, there exists d E 2 such that the set of XD-operations of depth d over weights W _exexx and inputs X E for S n contains 1, and arbitrary channel groups. parameter-free operations Id, Zero, and AvgPool, for any kernel size s f n.
1. convolutions with filter size S k, dilation I - stride
3. composing I or 2 with multiplication of all input or output channels by bounded-depth K-matrix.
Note this does not account for all important XD-operations, e.g. we show in the appendix that they also express Fourier Neural Operators [30] with [k/2] modes and any transposed convolutions whose stride equals the dilated kernel size. 6 Still, the first two items account for non-separable variants of most operations considered in past NAS work in computer vision, excluding the nonlinear MaxPool [47, 11]. Note depthwise-separabe convolutions are contained in the set of compositions of xDooprrations. The third item implies that XD-operations can express the basic and diffusion graph convolutions over fixed graphs [21, 27]: both are point-wise convolutions composed with sparse multiplication by a modified adjacency matrix, which K-matrices can represent efficiently.
As a concrete example, consider dilated convolutions, which for k: > 1 and dilation factor d 2 1 apply filters of effective size (k 1)d + with nonzero entries separated by d d- 1 zeros. One could to an input x E R" in the single-channel setting
hope to express the application of as F diag(F diag(Pk..)) )..,))) Fx, where Pk.d E {0, 1)ah zeroes out appropriate entries of w, but this requires filter size (k- 1)d + 1 > k. increasing the number of weights. Instead, we can use permutation Pi.d E {0. 1 jmxn before the DFT to place the k entries of w into dilated positions:
DilatedCony a, (x) = F diag (F k Fx
Fx
(6)
As permutations are depth-2 K-matrices [10], we can express DilatedConv with an XD- operation of depth (1,3, 1), with K F FP..d and M
F.
4 Finding and Evaluating XD-Operations
This section outlines a simple procedure that we use evaluate XDoopeatioos.. Recall that NAS methods specify architectures by assigning operations to each edge (u, u, Op) of a computational graph. We aim to simultaneously find good operations and model weights, a goal distinct from the classic two-stage NAS formulation, which finds assignments in an initial search phase before training the resulting architecture from scratch [47]. However, the use of weight-sharing (36) extends NAS to one-shot objectives where weights and architectures are jointly optimized. Under weight-sharing. architecture parameters become weights in a larger "supernet," extending the hypothesis class [25].
To assess XD-operations directly we assume the user provides a starter network with existing edge labels Opu, backbone. We transform this into a weight-sharing supernet by reparameterizing each operation Opa.. as an XD-operation XD az.. with architecture parameter Gu,e- Then we simultaneously train both au,v and the model weights Wa,v associated with each edge as follows:
Architecture parameters au,e are initialized using the original operation used by the CNN backbone by setting OP..- XD au is then updated via SGD or Adam [20]. We tune step-size, momentum, and the number of "warmup" epochs: initial epochs during which only model weights Wa, are updated. This can be viewed as a specialized step-size schedule.
Model weights w..v are initialized and updated using the routine provided with the backbone.
'This restriction still includes transposed convolutions used in well-known architectures such as U-Net [38].

---

Distance from initial operation to final architecture parameter
Table I: Search space comparison CIFAR-10. Valida-
tion accuracies are averages of three trials. While we use small CNNs for exploration, XD-operations can also be used with bigh-performance backbones to obtain > 95% accuracy (c.f. the appendix).
reatove Eustidean distance
Permuled
6.4-
Backbone
Permuted CIFAR-10*
Cost (hours!)
search space
CIFAR-10
LeNet
75.5 0.1
43.7 = 0.5
0.3
Sdiscrete
75.6
47.7 + 1.0
1.0
Conv-Sa5 (LeNet)
Pool-2x2 (LeNeo
Conw333 (ResNet)
Skp-Con (ResNet)
SXD
77.7 0.7
63.0 + 1.0
0.9
ResNet-20
91.7
58.6 0.7
0.6
Figure On permuted images, where convolutions are not the "right" opera- tion, we find XD-operations that are far- ther away from the operations of the ini- tial CNN backbone.
Sdiscrete
92.7 0.2
58.0 1.0
5.3
SXD
92.4 + 0.2
73.5 + 1.6
5.6
No data augmentation used in the permuted case.
This approach allows us to use established topologies and optimizers while searching for new operations, thus aligning with the goal for Sections 5, 6, and 7: improve upon the CNN backbones that practitioners often use as a first attempt. As a simple example, we start by applying the procedure image classification. Since this is the main objective of our work, we treat it as a warmup and consider two datasets: CIFAR- 10 and a variant where the images' rows and columns are permuted. On CIFAR-10 we do not expect to see much improvement from XD-operations over the CNN backbone used to initialize search, as convolutions are already the "right" operation for images. On the other hand, the "right" operation on permuted data, at least layer one, is an inverse permutation followed by convolution; as this is an XD-operation", here we do hope to see improvement.
Using LeNet [23] and ResNet-20 [15] as backbones, we compare applying our algorithm to XI>- operations with two baselines: (I) using just the backbone CNN and (2) applying similar method to the relaxed set Sdiscrete of DARTS operations from Section 2. To optimize over Saiscrete we take an approach similar DARTS: parameterize the simplex using softmax and apply Adam. We experiment with both uniform initialization and one biased towards the backbone's 's operation. While both SxD and Sdiscrete contain LeNet's Convsxs and ResNet's Conv3x3 and Id, for LeNet's MaxPoolax3 layer we initialize with the closest operation. For direct comparison, both search spaces employ weights with maximum filter size rather than retraining, which we find hurts Sdiscrete- We set the XD-operations' depth express the dilated convolutions in Sdiscrete and convolutions composed with permutations.
and for both we evaluate the shared weights
33 to
In Table 1, we that while both the relaxed discrete NAS operations and X XD-operations perform comparably on regular images, XD-operations achieve around 15% better accuracy with both back- bones when the images are permuted." Note that networks obtained by running state-of-the-an NAS procedures such as GAEA PC-DARTS [25] and DenseNAS [13] on permuted CIFAR-10 achieve only 66.3% and 61.6% accuracy, respectively, despite using millions more parameters than ResNet-20. While it is not straightforward to understand the recovered XD-operations that perform so well, we can use the relative Euclidean distance of their architecture parameters from initialization for novelty; in Figure 2 we see that on regular images our procedure finds operations that are quite similar convolutions, but on permuted data they are much further away. These results show that to enable NAS on diverse data, we will need search space that contains truly novel operations, not just combinations of existing ones. In the remainder of the paper, we study more diverse and realistic tasks that show further evidence that SXD is strong candidate for this.
proxy
Recall SxD includes compositions convolutions with multiplication by K-matrix, e.g. a permutation. Full accuracy can be recovered via auxiliary loss encouraging permutation-lik like K-matrices [10].
7

---

Burgers' equation
Darcy Flow
resstre unar
CNN- FNO-1d CNN--1 XD
12 relartee
Chil-2d
TNO-2d
Chili-d DAATS one
Lab
10-2
10a1
2566
912
2048
4056
6192
106
161
421
Reselutton
Resclition
Figure 3: Relative error on Burgers' equation (left) and Darcy Flow (right) across different resolutions.
5 Application: Learning to Solve Partial Differential Equations
As our first non-vision application, consider the task of solving PDEs, an important application area of ML in the natural sciences [28, 29, 41J. In our setup, data generated by classical PDE solvers is used learn functions from some initial condition setting the corresponding PDE solution, with the goal of replacing the solver by a deep net forward pass; the latter can be orders of magnitude faster. A recent state-of-the-an approach for this introduces Fourier Neural Operators [30], operations that significantly improve upon previous neural approaches across three different PDE settings. To evaluate the ability of XD-operations compete with such custom-designed operations starting from simple CNN backbones, we will investigate the same three PDEs that they study: Burgers' equation, Darcy Flow, and the 2d Navier-Stole equations, which involve 1d, 2d, and 3d data, respectively. The first two are studied across multiple resolutions, while the last one is studied at different viscosities.
As before, we start with a simple CNN backbone- type a scientist might use in first attempt at solution-and replace all convolutions by XD-operations. We initially hope to do better than this backbone, but ambitiously also hope compete with the custom-designed FNO. The specific CNN we use is simply the FNO architecture of the appropriate dimension N but with all N Nddimensional FNOs replaced by N N-dimensional convolutions; this performs similarly to their CNN baselines [30]. In all cases we compare mainly to the CNN backbone and our reproduction of the FNO results, as the latter exceeds all other neural methods; a complete results table is provided in the appendix. Our reproduction of FNO is slightly worse than their reported numbers for Burgers' equation and slightly better in the other two settings. Note that on the Stoier-Stokes equations we only compare the 3d FNO on the two settings in which we were able to reproduce their approach; moreover, we do nor compare to their use of a 2d FNO plus a recurrent net in time, but in-principle XD-operations can also be substituted there. In the 2d Darcy Flow case we also include comparisons to DARTS operations in the simple CNN backbone, as in Section 4, and to Auto-Deepl..ab (AutoDI.) [31], a well-known again follow the procedure in
NAS method for dense prediction. For evaluating XD-operations Section 4, in which we tune only the architecture optimizer; notably, we do this only at the lowest resolutions. At all dimensions we use XD-operations of depth d = 13; in addition, in dimensions N > 1 we fix the architecture biases b and channel gates C to 0 and 1, respectively, to conserve memory at higher resolutions. At lower ones we find that the performance difference negligible.
We report our results for the Burger's ' equation and Darcy Flow in Figure 3; for 2d Navier-Stokes the results are in Table 2. In all cases we dramatically outperform the CNN backhone used to initialize XD-operations; furthermore, we also achieve better error than FNO, despite it being custom-made for this problem. In particular, we find that XD-operations have higher training error but generalize better (c.f. the appendix). Figure also shows that XD-operations perform consistently well across resolutions, major ad advantage of FNOs over previous methods, whose performance was tightly coupled to the discretization [30]. Notably, CNN performance worsens with higher resolution, unlike that of XD and FNO. Finally, we also substantially outperform DARTS operations and AutoDL in 2d, although the latter is at least consistent across resolutions. These results provide strong evidence that a useful search space for discovering neural operations, even in domains where the convolutions used to initialize them perform much worse than of Note that these results do come at a cost of slower training and inference: XDD-operations are roughly order of magnitude slower than FNOs, despite having fewer parameters in 2d and 3d. This still yields solvers one-to-two orders of magnitude faster than classical solvers, maintaining usefulness for the problem.
XD-operations
8

---

Table 2: Relative test the 2d Wavier-Stoker equations different settings of the viscosity y and time steps T. Best results in each setting are bolded.
V 10 = 30
== 10-5, -,- T 20
CNN-3o (our baseline) FNO-3d (reproduced) CNN-3d XD (ours)
0.325
0.278
0.182
0.177
0.172
0.168
real-valued distance prediction
atad Na5
Autto-Oeepl.i
6.0-
RosNet
RusNet
5.5
ResNee DARTS
Reshict Depth
Figure 4: ResNet XD outperforms both baseline and dilated ResNets PSICOV. At the highest depth we test we also outperform the reported MAEg of the much deeper Dilated ResNet-258 [1].
Application: Real- Distance Prediction for Protein Folding
As second scientific application, we consider the task of inferring the 3d "folded" structure of polypeptide chain, which yields important insights into the function of the resulting protein [18]. This problem is high-priority challenge in biology and has recently seen significant MI-drrven advances from deep learning methods such as AlphaFold [40, 19] and PDNET [1]. These typically involve training network to predict pairwise physical distances between residues in the chain. We work with the PDNET benchmark, which consists a training set of 3,356 proteins, a validation set 100 of proteins, and the PSICOV [18] test set of 150 proteins. PDNET is designed to be more accessible than datasets used by large-scale methods such as AlphaFold, which are not always publicly available and/or require massive compute [40, 19]. We follow the PDNET training procedure [1] and evaluate test set performance using their MAEs metric for assessing long-range distances.
As before we start with simple CNN backbones-in in this case ResNets. We choose this to compare most directly to the designd architecture used by PDNET, consisting of a Dilated ResNet characterized by its use of cyclically increasing dilation rate across ResNet blocks [1]. At sufficient depth, the Dilated ResNet shown to outperform a standard pre-activation ResNet adapted to this task [1]. Our goal will be to see whether we can start with the vanilla ResNet and use XD to outperform both it and the specialized Dilated ResNet. We also aim to outperform the DARTS operations baseline from the previous two sections well as the AutoDL NAS approach for dense prediction. We use ooooperations of depth = 13 and fix the architecture biases and channel gates before to conserve memory. We evaluate architectures of different depths-4, 6, 10, 18, and by varying the number of ResNet blocks used in the backbone architecture and baseline.
We report the results as averages across three trials for each depth in Figure 4. Notably, while Dilated ResNet slightly outperforms ResNet, ResNet XD outperforms both dilated and standard ResNets at all depths. This provides further evidence that XD-operations can outperform specialized operations for diverse domains, even when initialized naively as standard convolutions. XD also outperforms LutoDL, which does poorly, and DARTS operations, except at the two smaller depths where performance is similar. Moreover, our ResNet-34 XD's MAEs of 4.0 also improves upon PDNET's reported MAEs of 4.1 attained by the much deeper Dilated ResNet-255 258 [1]: however, in our reproduction Dilated ResNet-258 achieved an MAE, of 3.5. Given the trend in Figure 4, where XD-operations consistently improve the backbone architecture of the same depth, we conjecture that ResNet-258 XD could further improve upon this result. We leave scaling XD-operations to such deeper networks to future work.

---

Table 3: XD-operations compared recent results in music modeling. We report average loss across three trials. The best result on each task is bolded.
Method (source)
JSB Chorales
Nottingham
Best recurrent [5]
8.43 8.10
3.29
TCN [5]
3.07
Transformer [44]
3.34
R- T-ransformer [44]
2.37
Undilated TCN (our baseline)
8. 3.16 = 0.04
3.23 + 0.02
TCN (reproduced)
8.17 = 0.01
2.97 + 0.01
Undilated TCN XD (ours)
8.07 = 0.01
2.84 + 0.02
7 Application: Music Modeling
Our final application is to music modeling, i.e. learning to predict the next note from sheet music [4]. The dominant approaches for such tasks are recurrent nets [16] and Transformers [42], but recent work has shown that specially-designed convolutional models can also be made competitive at similar model sizes [5, 6]. We will consider the temporal convolutional network (TCN) [5], which improves upon regular CNN by having the dilation factor grow exponentially across layers. The tasks we study are on the JSB Chorales and Nottingham corpora, used in the original evaluation of TCNs [5]. As the baselinn we take the TCN and set all dilation factors to one (undilated); goal will be to start with this undilated network and match or outperform the custom dilation design of the TCN.
The results presented in Table 3 show that we achieve this goal, we outperform both the undilated baseline and the TCN on both tasks. While the simple undilated backbone that we initialize with turns out to already match the TCN on JSB Chorales, on Nottingham our approach demonstrates that XD-operations can be used to outperform band-designed architectures starting from vanilla CNNs. Where possible we also compare to other known results; XD-operations outperforms all of these except the R-Transformer [44], a model combining recurrent nets and self-attention, on Nottingham.
Together with our results on PDEs and proteins, our study of music modeling provides further evidence that XD-operations can effectively find good operations using standard backbones on diverse tasks. One notable difficulty here is causality enforcement: making sure the input data does not contain the target when predicting the next entry. While TCNs can efficiently do so via temporal shifts, we do it in brute-force manner by treating sequences of length n as n 1 data-points with masked targets. This is expensive and thus limits our evaluation to small music tasks. A fruitful direction for future work is thus to examine whether it is possibly to directly enforce causality in XD- operations, e.g. by forcing architecture parameters and M to be lower triangular; since a product of lower triangular matrices is again lower triangular, the entire operation is then multiplication of the input sequence by a lower triangular matrix, which suffices to prevent causality violations.
8 Conclusion
This work aims to transition NAS from combining existing operations designed for vision and text to finding novel and effective operations in many domains. To do so we introduced a new search space of XD-operations and demonstrated its effectiveness on diverse tasks. Combining XD-operations with standard topology-search NAS, warm-starting search from non-standard operations such as graph convolutions and FNOs, 10 improving the computational limitations described earlier, and constructing spaces containing missing operations such as BatchNorm [17] and self-attention [42] are all promising future directions. Finally, note that our goal- lowering the barrier for applying ML-neccssarily comes with the possibility of misuse. Mitigating this involves developing tools for applicationsspeifee concerns, e.g. privacy and fairness, that go beyond the error metrics we target.
'In the appendix we report similar improvements on two other tasks on which TCNs were evaluated- permuted MNIST and Penn TreeBank that we do not discuss in detail as our focus is on under-explored tasks. In this direction, we found that initializing XD with FNO did worse than initializing with convolutions on Burgers' equation and Darcy Flow, a surprising result given how much better FNO is than the baseline CNN. Similarly, initializing XD with convolutions dilated as in the original TCN did not lead to significant improvement, except setting, over undilated initialization. See the appendix for more details and results.
10

---

Acknowledgmentt
We thank Maria-Floriina Balcan, Jeremy Cohen, and Tian Li for helpful advice on early versions of this paper and anonymous reviewers for suggested improvements. This work was supported in part by DARPA under cooperative agreements FA875017C0141 and HR001 NSF grants CCF- 1535967, CCF-1910321, I1S-1618714, IIS- 705121, IIS- NSS-183017, IIS- NSS-1904433, and IIS-2046613, a Microsoft Research Faculty Fellowship. a Bloomberg Data Science research grant, an Amazon Research Award, an AWS Machine Learning Research Award, a Facebook Faculty Research Award, funding from Booz Allen Hamilton Inc., a Block Center Grant, a Carnegie Bosch Institute Research Award, and a Two Sigma Fellowship Award. We also gratefully acknowledge the support of NIH under No. U54EB020405 (Mobilize), NSF under Nos. CCF1763315 (Beyond Sparsity), CCF1563078 (Volume to Velocity), and 1937301 (RTML); ONR under No. N000141712266 (Unifying Weak Supervision); the Moore Foundation, NXP, Xilinx, LETI-CEA, Intel, IBM, Microsoft, NEC, Toshiba, TSMC, ARM, Hitachi, BASF, Accenture, Ericsson, Qualcomm, Analog Devices, the Okawa Foun- dation, American Family Insurance, Google Cloud, Swiss Re, Total, the HAI-AWS Cloud Credits for Research program, the Stanford Data Science Initiative (SDSI), and members of the Stanford Facebook, Google, and VMWare. The Mobilize Center is Biomedical Technology Resource Center, funded by the NIH National Institute of Biomedical Imaging and Bioengineering through Grant P41EB027060. The U.S. Government authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings and conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of DARPA, NSF, NIH, ONR, or any other funding agency.
DAWN project:
References
[1] Badri Adhikari. A fully open-source framework for deep learning protein real-valued distances. Scientific Reports, 10(1):13374, 2020.
[2] Nir Ailon, Omer Leibovich, and Vineet Nair. Sparse linear networks with fixed butterfly structure: Theory and practice. arXiv, 2020.
[3] Keivan Alizadeh vahid, Anish Prabhu, Ali Farhadi, and Mohammad Rastegari. Butterfly transform: An efficient FFT based neural architecture design. In Proceedings of the IEEE Conference on Conference on Computer Vision and Pattern Recognition, 2020.
[4] Moray Allan and Christopher Williams. Harmonising chorales by probabilistic inference. In Advances in Neural Information Processing Systems, 2005.
[5] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolu- tional and recurrent networks for sequence modeling. arXiv, 2018
[6] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Trellis networks for sequence modeling. In Proceedings of the 7th International Conference on Learning Representations, 2019.
[7] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13:281-305, 2012.
[8] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all. Train one network and specialize for efficient deployment. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[9] Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning fast algorithms for linear transforms using butterfly factorizations. In Proceedings of the 36th International Conference on Machine Learning, 2019.
[10] Tri Dao, Nimit Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszezynski, Atri Rudra, and Christopher Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[11] Xuanyi Dong and Yi Yang. NAS-Bench-200 Extending the scope of reproducible neural archi- tecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
11

---

[12] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, Journal of Machine Learning Research, 20(55):1-21, 2019.
[13] Jiemin Fang, Yuzhu Sun, Qian Zhang. Yuan Li, Wenyu Liu, and Xinggang Wang. Densely connected search space for more flexible neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
[14] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HiPPO: Recurrent memory with optimal polynomial projections. In Advances in Neural Information Processing Systems, 2020.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2016.
[16] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9:1735-1780, 1997.
[17] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
[18] David T. Jones, Daniel W. A. Buchan, Domenico Cozzetto, and Massimiliano Pontil. PSICOV: precise structural contact prediction using sparse inverse covariance estimation on large multiple sequence alignments. Bioinformatics. 28(2):184-19) 11 2011.
[19] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowie, Bernardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler. Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure predic- tion with alphafold. Nature, 596(7873):583- 589, 2021.
[20] Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proceedings of the 3rd International Conference Learning Representations, 2015.
[21] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, 2017.
[22] Alex Krizhevksy. Learning multiple layers of features from tiny images. Technical report, 2009.
[23] Yann LeCun, Patrick Haffner, Léon Bottou, and Yoshua Bengio. Object recognition with gradient-based learning. In Shape, Contour and Grouping in Computer Vision. 1999.
[24] Liam Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(1 1-2,, 2018.
[25] Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradient algorithms for neural architecture search. In Proceedings of the 9th International Conference on Learning Representations, 2021. To Appear.
[26] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2019.
[27] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In Proceedings of the 6th International Conference on Learning Representations, 2018
[28] Yingzhou Li, Haizhao Yang, Fileen R. Martin, Kenneth I.. Ho, and Lexing Ying. Butterfly factorization. Multiscale Modeling & Simulation, 13(2):714-732, 2015.
12

---

[29] Yingzhou Li, Haizhao Yang, and Lexing Ying. Multidimensional butterfly factorization. Applied and Computational Harmonic Analysis, 44(3):33-775, 2018.
[30] Zongyi Li, Nikola Borislavov Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differential equations. In Proceedings of the 9th International Conference on Learning Representations, 2021. To Appear.
[31] Chenxi Liu, Liang-Chieh Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan Yuille, and Fei-Fei. Auto-DeeplLae Hierarchical neural architecture search for semantic image segmen- tation. In Proceedings of the IEEE Conference Conference Computer Vision and Pattern Recognition, 2019.
[32] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proceedings of the 7th International Conference on Learning Representations, 2019.
[33] Jieru Mei, Yingwei Li, Xiaochen Lian, Xiaojie Jin, Linjie Yang, Alan Yuille, and Jianchao Yang. AtomNAS: Fine-grained end-to-end neural architecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[34] Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. ACDC: A structured efficient linear layer. arXiv, 2015.
[35] Vladimir Nekrasov, Hao Chen, Chunhua Shen, and Ian Reid. Fast neural architecture search of compact semantic segmentation models via auxiliary cells. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
[36] Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proceedings of the 35th International Conference on Machine Learning, 2018
[37] Esteban Real, Chen Liang, David R. So, and Quoe V. Le. AutoML-ZZroo Evolving machine learning algorithms from scratch. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[38] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assisted Inter- vention, 2015.
[39] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet large scale visual recognition challenge. International Journal of Computer Vision,
115(3):211-252, 2015.
[40] Andrew W. Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifre, Tim Green, Chongli Qin, Augustin Zídek, Alexander W. R. Nelson, Alex Bridgland, Hugo Penedones, Stig Petersen, Karen Simonyan, Steve Crossan, Pushmeet Kohli, David T. Jones, David Silver, Koray Kavukcuoglu, and Demis Hassabis. Improved protein structure prediction using potentials from deep learning. Nature, 577(7792):06--716 2020.
[41] Justin Sirignano and Konstantinos Spiliopoulos. DGM: A deep learning algorithm for solving partial differential equations. Journal of Computational Physics, 375:1339-1364, 2018.
[42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- tion Processing Systems, 2017.
[43] Yujing Wang, Yaming Yang, Yiren Chen, Jing Bai, Ce Zhang. Guinan Su, Xiaoyu Kou, Yunhai Tong, Mao Yang, and Lidong Zhou. Textnas: A neural architecture search space tailored for text representation. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020.
[44] Zhiwei Wang, Yao Ma, Zitao Liu, and Jiliang Tang. R-Transformer: Recurrett neural net- work enhanced transformer. In Proceedings of the 8th International Conference on Learning Representations, 2020.
13

---

[45] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC-DARTS: Partial channel connections for memory-efficient architecture search. In Proceed- ings of the 8th International Conference Learning Representations, 2020.
[46] Antoine Yang, Pedro M. Esperança, and Fabio M. Carlucci. NAS evaluation is frustratingly hard. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[47] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. 10S- Towards reproducible neural architecture search. In Proceedings of the 36th International Conference on Machine Learning. 2019.
[48] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. Proceedings of the British Machine Vision Conference, 2016.
[49] Arber Zela, Julien Siems, and Frank Hutter. NAS Bee--Bnnhhh-eeeee Sench-1Shotll Shottl: Benchmarking and dissecting one-shot neural architecture search. Proceedings of the 8th International Conference on Learning Representationss 2020.
[50] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the first bullet-point of Section 2 and the last paragraphs of Sections 5, 6, and 7.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the end of Section 8.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of theoretical results? [Yes] See the appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] See the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Tables 1 and 3 and Figure 4.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Table and the appendix.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes]
See code in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
14

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "wpAOvu4SyEY", "reviewer": "Reviewer_misB", "summary": "This paper explores learning more general neural architectures by leveraging a novel, continuous parameterization of architecture (based on kaleidoscope marix) and one-shot style NAS algorithms. They present results on standard, and permuted cifar10, then 3 more exotic datasets including PDE solutions, problems from protein folding, and music modeling.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This seems like a solid paper. I would advocate for accepting though I am not an expert in this field (hence my low confidence). My rational for a 6 vs 7 is the limited baselines comparing to existing NAS methods.\n\nClarity: My main concern is about clarity of the presentation. I found the the abstract discussion based solely on equations of this method difficult to follow. I realize the paper is space constrained, but including examples of K-matrix / even showing how standard operations map into XD-operators would be greatly appreciated. The description of the method also takes around 5-6 pages as well which feels very long.\n\nResults: \nI found these experiments quite compelling. Having baselines that outperform existing work is always great!\n\nFor the PDE, protein and music, it would be interesting to see another NAS comparison -- in particular a discrete search space style NAS algorithm like what was done in the cifar10 experiments.\n\nOne question I have is about how useful the resulting architectures are. In Darts, one can discretize the discrete search space resulting in very efficient architectures for future tasks. In this work, this doesn't seem so straight forward (and it is even stated that this was not done on purpose). Do the K-matrix style formulation lead to an efficient formula? Naively it seems like without it it would be up to 10x more costly (judging by the resnet-20 cifar10 walltimes).\n\nRelated, but do you have any understanding of what kinds of \"architectures\" these things learn? Is anything interpretable?\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are discussed, but as noted above I would appreciate some discussion on inference costs / how to actually use these models / some notion of overhead at inference time.\n\nNo societal impact is discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "_LAGV3hC3wG", "reviewer": "Reviewer_9aTC", "summary": "The core contribution of this work is to re-image of NAS operation spaces to include both standard operations as well as new operations. This work replaces the Discrete Fourier Transform (DFT) in the diagonal decomposition by a more expressive family of efficient liner transforms known as Kaleidoscope or K-matrices (Expressive Diagonalization Operations), which comprises of a large search space of various types of grid-based convolutions and pooling, permutations, graph convolutions, the Fourier Neural Operator, and more. This work developed a simple procedure which transforms any backbone convolutional neural network into an architecture search space by replacing its operations with XD-operations. This space is then searched using a simple weight-sharing algorithm. This work yields models that are 15% more accurate than standard discrete search spaces on permuted CIFAR-10, highlighting the fragility of standard NAS operation spaces on new datasets, and thus the need for XD-operations.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This work brings up an interesting perspective that ,. This work also proposes to replace matrices F and F-1 in by any one of a general family of efficient matrices, which yields the single-channel version of expressive diagonalization operations. \n\nStrengths:\n1. This approach in general provides a much more expressive search space for NAS, by devising XD-opeartions with K-matrix architecture parameters.\n2. The formulation and complexity analysis on a single-channel XD-operations with K-matrix architecture parameters is pretty clear. \n\nWeakness:\n1. The paper is not clear about how to rank models or evaluate models generated from this enlarged search space. The reviewer is particularly confused by \"Note that the fully continuous nature of XD-operations means that we will only evaluate the final network returned by search\". \n\n2. Empirical results are weak. Only Cifar10 results are provided and only bad baselines (LeNet and ResNet-20) are compared against. Also, it is odd that \"On CIFAR-10 we do not expect to see much improvement from XD-operations over the CNN backbone used to initialize search, as convolutions are already the “right” operation for images\", why this work should evaluate on CIFAR10 then?\n\n5. Application section is interesting but not very formal.  There isn't any standard benchmarks used or any well-known baselines are compared upon. \n\nOverall, the reviewer thinks the general direction is interesting, however, evaluation is poor. The work is not thoroughly evaluated and no strong baselines are provided. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, both are addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6BGmjB5SzDN", "reviewer": "Reviewer_nncs", "summary": "The paper starts by introducing Kaleidoscope-matrices (K-matrices). The core idea here is: \n1. Most of the interesting operations in NAS spaces are linear and can be expressed as a matrix multiplication $A_W x$\n2. The operations can therefore be diagonalized by a DFT\n3. We can factorize the DFT matrices into “butterfly matrices” (such that, for a factorization of factor $N$, we can write $F =$ the product of the $N$ butterfly matrices and a permutation matrix). \n4. By allowing this factor $N$ to vary, the matrix multiplication $A_W x$ can be generalized to express a wider family of operations \n\nThe core contribution of this paper appears to be using K-matrices in a NAS setting (which involves a reasonable amount of work):\n- The architecture parameters are continuous \n- K-matrices can’t express parameter-free ops\n- Finding/evaluating new operations in a NAS setting\n\nTheir NAS process then looks like:\n1. Take in a backbone and generalize it to a supernet \n2. Simultaneously train the architecture parameters and the weights \n3. Extract a net + weights for inference\n\nThe paper then explores a few unusual tasks and shows that this generalization process is worthwhile. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Overall this paper was a joy to read, filled with insightful interpretations of things I previously thought boring (e.g. the definition of NAS spaces as a set of operations with the same W,X,Y and their expressibility). The paper would be strengthened by more thorough empirical results, but I understand why in this particular setting that could hard to provide.\n\nThe paper has a hard task: construct a general framework for neural architecture search that will let us do more exciting things than squeeze out performance on existing benchmarks, but that also doesn’t perform drastically worse than existing (extremely heavily engineered) techniques on said benchmarks. \n\nI think the authors do a good job of showing the expressivity of their method with regards to diverse tasks while also showing that it continues to work on the more boring tasks (e.g. CIFAR-10). Even so, I do think the lack of focus on the typical “NAS-bench” setups is a little disappointing. I would have liked to see what happened if the authors took a NAS-bench cell/skeleton as their starting point — since we have results for a wide range of NAS-techniques on those benchmarks, it would be easier to put their method in context.\n\nThe authors perform some analysis of the Euclidean distance between their architecture parameters (which I’m assuming is butterfly factors + bias?) and the traditional convolution operation show that they can tailor then operations to suit the complexity of the tasks, which is very nice. \n\nThe authors then dive into a few diverse tasks, none of which I have experience with so may have missed some evaluation points:\n\n**Solving PDEs**: this section is neat, and it shows that the XD-operations can be used to replace the hand-engineering effort that went into designing Fourier Neural Operators. I may have missed it but it would be good to have some detail on the dataset specifically (number of training/test samples per PDE/resolution/viscosity). My immediate concern is that learning over a space of operations like this probably requires a lot of data? \n\n**Protein folding distance prediction**: I don’t know much about this task but the results seem good (there are minor improvements over both ResNet and Dilated ResNet at each depth). \n\n**Music modeling**: again, I don’t know much about the task but the results seem good.\n\nI’m happy that the evidence provided is sufficient to show that this process can be used to take a backbone, generalize it to some family of ops, and then specialize the operations to suit the task. That alone is a very useful contribution. \n\nIn the abstract the authors state “Starting with any standard backbone such as ResNet, we show how to transform it into a search space over XD-operations and how to traverse the space using a simple weight-sharing scheme.” My assumption from this sentence was that they would use is a single backbone used for all three of the tasks. That they don’t suggests that though the method provides a good level of generalization, it still requires some hand engineering to get it to work well.\n\n## Overview\n\n**Originality**: In some ways this felt like the inevitable next step to [1]. However, it appears there is still a reasonable amount of novelty/originality to the paper in getting K-matrices to work for NAS. Related work is adequately cited.\n\n**Quality**: The submission is technically sound, and filled with satisfying definitions of the various aspects of the problem. The authors show the performance of their method on three unusual problems, plus the more classic task of CIFAR-10. The step from CIFAR $\\rightarrow$ permuted CIFAR $\\rightarrow$ other tasks is a nice logical narrative. The experimental evidence isn't overwhelmingly strong, but the paper does break NAS into relatively new territory so I don't think a huge amount of empirical evaluation is needed.\n\n**Clarity**: The submission is very clearly written, organized, and thoroughly cites background material which was useful for me as a reader with not a great deal of knowledge regarding butterfly matrices and the related work. It's an interesting topic because the paper is trying to generate new types of operation which by their nature probably won't be particularly intuitive, but I feel like the authors did a good job of showing why a few example operations are expressible in their search space.\n\n**Significance**: The paper addresses a major limitation with neural architecture search: that we typically only use a very restrictive set of operations that we know to work well on a limited range of tasks. I'm not convinced that after this paper, everybody in the NAS subfield will switch to using K-matrices, but it seems like a useful tool in the toolbox for people who are using NAS outside of CIFAR-10. \n\n## Questions\n\n1. I’m a little confused about exactly what the “architecture parameters” look like. Is it a collection of “butterfly factors” and biases for K, L, and M? Are all of the cells in the network the same or do you have different architecture parameters for each layer? \n2. In my interpretation, the authors are almost implicitly proposing a new “NAS-bench” which is composed of XD-operations (a much wider family of operations than what we currently use). To that end, it would be nice to see some statistics about what the space of XD-operations looks like: if you randomly sample from the space, how much variance is there in the performance of the operations? Is the space dense with very-convolution-like operations or is it quite uniformly distributed? What happens if you take the cell-structure/backbone from NATS-bench/ NAS-Bench-101/ NAS-Bench-201 and set all of the operations to be XD-operations? \n3. On page 6 the authors state “On CIFAR-10 we do not expect to see much improvement from XD-operations over the CNN backbone used to initialize search, as convolutions are already the “right” operation for images.” I guess this is true, but I was wondering whether the authors think there is any scope to improve on convolution using their method in future? Given the volume of work on convolutional-alternatives (LambdaNetworks, the Shift operation, OctaveConvolution etc.) for image domains, I was hoping that within a space of XD-Operations we might find more of these.\n4. One thing I can’t quite figure out is whether all of the operations expressible in the space of XD-Operations are reduced forms of convolution (e.g. adding dilation)?  Could you express something like transposed convolution? Is there anything expressible as an XD-Operation that isn’t expressible as unstructured pruning in the matrix A? \n5. An evaluation of the limitations of the expressivity of the search space would also be nice. For example, I assume you probably can’t express something like a self-attention layer due to the softmax? \n\n[1] Dao, Tri, et al. \"Kaleidoscope: An efficient, learnable representation for all structured linear maps.\" arXiv preprint arXiv:2012.14966 (2020).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the potential negative societal impact of their work.\n\nIn general, moving NAS away from vision and language tasks is a direction that we should probably encourage.", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work is a well-presented and motivated perspective on NAS, where a reparameterisation of the search space using K-matrices yields a method that is able to operate across a number of interesting domains. The only major concern raised by the reviewers is, naturally, the choice of domains. The reviewers all agreed the authors have selected a diverse range of tasks and demonstrated their method on each. Naturally, given this demonstration, there is some anticipation of demonstrating this method on a diverse set of larger-scale problems, perhaps this will be future work.
Decision: Accept (Poster)