Searching for Convolutions and a More Ambitious NAS
Authors: Nicholas Carl Roberts
Mikhail Khodak
Tri Dao
Liam Li
Nina Balcan
Christopher Re
Ameet Talwalkar
Venue:  (2021)
Keywords: neural architecture search
automated machine learning
convolutional neural networks

Abstract: An important goal of neural architecture search (NAS) is to automate-away the design of neural networks on new tasks in under-explored domains, thus helping to democratize machine learning. However, current NAS research largely focuses on search spaces consisting of existing operations---such as different types of convolution---that are already known to work well on well-studied problems---often in computer vision. Our work is motivated by the following question: can we enable users to build their own search spaces and discover the right neural operations given data from their specific domain? We make progress towards this broader vision for NAS by introducing a space of operations generalizing the convolution that enables search over a large family of parameterizable linear-time matrix-vector functions. Our flexible construction allows users to design their own search spaces adapted to the nature and shape of their data, to warm-start search methods using convolutions when they are known to perform well, or to discover new operations from scratch when they do not. We evaluate our approach on several novel search spaces over vision and text data, on all of which simple NAS search algorithms can find operations that perform better than baseline layers.

Under review as a conference paper at ICLR 2021
SEARCHING FOR CONVOLUTIONS AND A MORE AMBITIOUS NAS
Anonymous authors Paper under double-blind review
ABSTRACT
An important goal of neural architecture search (NAS) is to automate-away the design of neural networks on new tasks in under-explored domains, thus help- ing democratize machine learning. However, current NAS research largely fo- cuses on search spaces consisting of existing operations-succ as different types of convolution that are already known to work well on well-studied problems- often in computer vision. Our work is motivated by the following question: can we enable users to build their own search spaces and discover the right neural operations given data from their specific domain? We make progress towards this broader vision for NAS by introducing a space of operations generalizing the convolution that enables search over a large family of parameterizable linear-time matrix- vector functions. Our flexible construction allows users to design their own search spaces adapted to the nature and shape of their data, warm-start search methods using convolutions when they are known to perform well, or to discover new operations from scratch when they do not. We evaluate our approach on sev- eral novel search spaces over vision and text data, on all of which simple NAS search algorithms can find operations that perform better than baseline layers.
INTRODUCTION
Neural architecture search is often motivated by the AutoML vision of democratizing ML. by reduc- ing the need for expert deep net design, both on existing problems and in new domains. However, while NAS research has seen rapid growth with developments such as weight-sharing (Pham et al.)
2018) and TEAS-bbnchee" (Ying et al. 2019 Zela et al. 2020), most efforts focus on search spaces
that glue together established primitives for well-studied tasks like vision and text (Liu et al. 2019
Li & Talwalkar 2019; Xu et al.) 2020; Li et al. 2020) or on deployment-
issues such as latency
(Cai et al. (020). Application studies have followed suit (Nekrasov et al. 2019: Wang et al.
2020
In this work, we revisit a broader vision for NAS, proposing to move towards much more general search spaces while still exploiting successful components of leading network topologies and effi- cient NAS methods. We introduce search spaces built using the Chrysalis a rich family of param- eterizable operations that we develop using characterization of efficient matrix transforms by Dao eet al. (220)) and which contain convolutions and many other simple linear operations. When com- bined with backbone architecture, the Chrysalis induces general NAS search spaces for discovering the right operation for given type of data, For example, when inducing novel search space from the LeNet architecture (LeCun et al. 1999), we show that randomly initialized gradient-basse NAS methods applied to CIFAR-10 10 discover operations in the Chrysalis that outperform convolutions the "right" operation for vision- by 1% on both CIFAR-10 10 and CIFAR- 100. Our contributions, summarized below, take critical steps towards a broader NAS that enables the discovery of good design patterns with limited human specification from data in under-explored domains:
We define the broad NAS problem and discuss how it interacts with modern techniques such as continuous relaxation, weight-sharing, and bilevel optimization. This discussion sets up our new approach for search space design and our associated evaluations of whether leading NAS methods, applied to our proposed search spaces, can find good parameterizable operations.
We introduce Kaleidoscope-operalie the Chrysalis that generalize the convolution while preserving key desirable properties: short
(K-operationss) parameterizable operations comprising
FFllooing Dao et al. 2020), butterffy- naming will be used throughout

---

Under review as a conference paper at ICLR 2021
description length, linearity, and fast computation. Notably, K-operations can be combined with fixed architectures to induce rich search spaces in which architectural parameters are decoupled from model weights, the former to be searched via NAS methods.
We evaluate the Chrysalis on text and image settings where convolutions are known to work well. For images, we construct the Butterfl .eNet search space by combining K-operations with the well- known LeNet (LeCun et al.. 1999). For text classification, we generalize the simple multi-width model of Kim 2014)) On both we evaluate several applicable NAS methods and find that single- level supemnet SGD able find operations that come close to or match the performance of convolutions when searched from-scratch, while also improving upon them when warm-started
We conclude by examining the generality of our approach on domains where convolutions are the "wrong" operation. We first consider permuted image data, where the "right" operation is permutation followed by convolution, and observe that NAS methods applied to the ButterfLeNet search space yield an architecture that outperforms all fixed operation baselines by 8%. Next we consider spherical MNIST data Cohnn et al. (2018), where the "right" operation is the spherical convolution from the same paper. We consider the K-operation search space that generalizes their network and again find that it outperforms convolutions by more than 20%. Our results highlight the capacity of K-operation- based search spaces, coupled with standard NAS methods, to broaden the scope of NAS to discovering neural primitives in new data domains.
1.1 RELATED WORK
AutoML is a well-studied area, with most work focusing on the fairly small search spaces of hyper- parameter optimization (Bergstra & Bengio 2012 Li al. 2018) or on NAS (Elsken al., 2019). In the latter case, it has been observed that the search spaces are still "easy" in the sense that random architectures can do reasonably well (Elsken al., 2019 Li & Talwalkar 2019). More recently, Real et al. (020) demonstrated the possibility of evolving ving all aspects of ML just the model but also the training algorithm from scratch. We seek establish a middle ground in which search spaces are large and domain-agnostic but still allow the encoding of desirable constraints and the application of well-tested learning algorithms such as stochastic gradient descent (SGD).
Our main contribution is a family of search spaces that build upon K-operations, which generalize parameterized convolutions (LeCun et al. 1999). Most NAS search spaces only allow a categorical choice between few kinds of convolutions (Liu et al. 2019; Zela et al. [020 Dong & Yang )020); even when drastically expanded to include many types of filter sizes and other hyperparameters (Mei et al.) 2020). the operation itself is not generalized and so these search spaces may not be useful outside of domains where convolutions are applicable. Beyond NAS, recent work by ZZhu al. 2020) uses a meta-learning framing (Thrun & Pratt 1998) to study how learn more general types of symmetries--eeonn allows clear formalization of learning such equivariances, though unlike NAS, is not applicable to single-task settings. In addition, their technical approach does not generalize two-dimensional convolutions due computational intractabality, while our K-operations are indeed able to do so.
simply cansslatioal-fron multi-task data. This transfer-based setup
The above works search over spaces of parameterizable operations by delineating a set of architec- tural or meta parameters to define the space over operations that are separate from model weights, which parameterize the operations found. In contrast, other efforts seek to simply outperform con- volutions by directly training more expressive models. This includes several that use linear maps based on butterfly factors as drop-in replacements for linear or convolutional layers (Dao et al.) 2019)] 2020 Alizadeh vahid et al. 2020 Ailon et al. 2020). Very recently, Neyshabur (2020) showed that sparsity-inducing optimization routine can train fully connected nets that match the performance of convolutional networks and in the process the weights learn local connectivity patterns. However, none of these papers return parameterizable operations from formally defined search space.
2 STATISTICAL AND OPTIMIZATION OBJECTIVES OF NAS
In this section we set up the statistical and algorithmic objectives of neural architecture search. This is critical since we seek a definition of NAS that encompasses not only categorical decisions but also learning primitives such as convolutions. We ignore latency and transfer considerations and instead focus on the statistical problem of learning to parameterize function fw.a Z + R so as to minimize its expected value Egf (2) w.r.t some unknown distribution over the data-domain Z. Here E A are architectures in some search space A and w E W are model-weights of sufficient
2

---

Under review as a conference paper at ICLR 2021
dimensionality to parameterize any architecture in A. Classically, is chosen by a human expert to aid the data-driven selection of w E W, i... to have favorable statistical and optimization properties to ensure that, given finite data set S Z, some learning algorithm Alg 2 A + W will return wa = ( a) s.t. Eu is small. Alg is usually some iterative gradient-based approximation like SGD to the empirical risk over S.
NAS Algorithms and Optimization Objectives: In contrast to the standard learning setting, NAS aims to select both a E A and w E W on the basis of training data, reducing the need for human intervention to constructing a search space and implementing a search algorithm, both of which should be as amenable as possible to general-purposse domain-agnostin designs. Assuming a given training method Alg, this leads to search objectives of the form
arg min aEAA
Swall()) REV
s.t.
wa ATg
where T. V.V. S are disjoint training and validation sets. The main challenge with this search objective is intractability: (1) A usually contains combinatorially many architectures and (2) eval- uating even one requires one run of Alg. Modern NAS avoids these problems using two tech- niques: continuous relaxation and weight-sharing (Pham et al., 2018 Liu et al. 2019) First, the often-discrete architecture search space A is relaxed into convex space of architecture parameters @ - A such that any A e ② is associated with some architecture a E A via some discretization mapping Map : θ - A. For example, O could consist of linear combinations of operations in A and Map could select the one with the largest coefficient. After continuous relaxation, we can run search by updating using gradients w.r.t fes.e, replacing the approximation error incurred by with the one incurred by running the discretization Map
truncating the discrete optimization of (I) on the output of
arg min 6
Σ (m).o(=) REV
S.t.
Wy = (T)
(2)
This addresses the first intractability issue, but computing the architecture gradient w.r.t. Suo, is still prohibitively expensive due to the need to differentiate through Alg. Weight-sharing resolves this via another approximation that simply maintains a fixed set of shared weights w throughout search and updates & using the gradient of fw.0. which does not depend on Alg. This exploits the
fact that changing & directly affects the objective fw.00 and so having different weights for different architectures, i.e. not sharing them, is not necessary to distinguish their performance (Li et al. 2020). The weight-sharing approximation to (2) leads to alternating update methods (Pham al. 2018] Liu (et al. 2019) in which gradient updates to w using data from I are alternated with gradient updates to 8 using data from V; one can also define a single-leve,, empirical risk minimization (ERM) objective
arg min min 12
fm.a(2)) EES
WeW
which can also be solved by alternating gradient updates, just using the same data, or by joint gradi- ent updates. Despite eschewing the usual data-splitting of most AutoML algorithms, this objective has been found to do well in certain NAS settings (Li al. 2020).
The Goals of NAS: The use of weight-sharing, continuous relaxation, and ERM blurs the line between NAS and regular model training, since architecture parameters are optimized in much the same way as model weights during search. The remaining differences are due to post-search dis- cretization, in which an architecture or (3). and dost-discretization re- -e-training, in which new weights w = Alg(S, a) are obtained with the discrete architecture. We will blur the line even further by considering search spaces that do not require post-search discretization and thus may not need post-discretization re-training either.
Map(f) A is recovered from the output E θ of (
thus useful to formally state our main objective, in alignment with standard NAS (Liu et al., 2019 Ying al.) 2019), which is to use the given data I to find 'good' architecture a E A, i.c., one such that with suitable model weights w., we obtain a function fw.,e with low test error. In practice, suitable model weights can be obtained either via: (a) offline evaluation in which weights directly after discovering a, i.e., w. = ATg(T, a); or (b) supernet evaluation in which we leverage the model weights learned jointly with architectural parameters, in or 33)
train model
For most instances of NAS with shariin offline evaluation achieves better test performance than supernet evaluation; this likely results from combination of (1) overfitting while training w
3

---

Under review as a conference paper at ICLR 2021
in-conjunction with relaxed architecture parameters 8, and (2) lossiness when discretizing to obtain a valid architecture a = Map(f) post-search (Liu et al. 2019 Dong & Yang 2020). However, our proposed search spaces do not require discretization, and will see that supernet evaluation sometimes outperforms offline evaluation, which we view as a benefit since it removes the need for re-training. Notably, while single-task supernet evaluation can be viewed as similar in spirit to regular model training, as we use I' to jointly train weight-architecture pair with low test error, we can isolate the quality of an architecture alone by performing supernet evaluation in a transfer learning setting, which we explore in Section
GENERALIZING CONVOLUTIONS WITH PARAMETERIZABLE OPERATIONS
The use of parameterized convolution operations to extract features from images is major archi- tectural breakthrough that has spearheaded most recent progress in computer vision (LeCun et al. 1999). Convolutions have also found numerous application in other domains such as text (Kim,
2014 Zhang et al., 2015), but they may not be the appropriate parameterized operation for all do- mains, or the right kind of convolution may not always be evident or easy construct (Cohen al.) 2018). Our main question is whether NAS can find a good parameterized neural primitive for a given data domain. To investigate, we start with a minimal requirement: that NAS can find operation that matches the performance of convolutions given computer vision data. This leads to our main contribution: Chrysalis of parameterizable K-operations that generalizes the convolution while preserving many of its desirable properties: small description length, linearity, and efficiency. Sub- stituting Kooperations for operations such as convolutions in backbone architectures yields search spaces in which the goal is to search the Chrysalis for a good K-operation to use on the input data.
Desirable Properties of Parameterizable Neural Operations: We first define what a parame- terizable operation is; this is crucial for distinguishing our process of searching for such operations compared to directly training model parameters for them.
Definition 3.1. A parameterizable operation Op(:.-) is a function with two inputs, i.e., data and model parameters w, and ouipuls parameterized function Op(;, w).
For example, a linear layer is parameterizable operation that takes as input a matrix and outputs the corresponding linear map: Neyshabur (2020) trains such layers in an attempt to recover convo- lutional performance. Another example is the Kaleidoscope layer (K-layer) of Dao et al. (2020), which is similar except the matrix is constrained to be stack of one more structured maps. No- tably, these and other works (Dao et al. 2019; Alizadeh vahid et al. 2020 Ailon et al. 2020) fix the parameterizable operation Op and learn its parameterization ux; contrast, we search for good Op. In particular, we formulate our search for a good Op via a search over architecture encodings we give evidence that the NAS approach of separating the search for from the learning of w yields good operations Op..
a. As discussed in Section 2
Our aim is to construct search space that generalizes the convolution Conv(:.) while preserving its favorable, domain-independen properties; the goal will then be to use NAS to find operations within this search space that have good domain-dependent properties. We identify three domain- independent properties possessed by functions Conv(:, w) returned by the parameterizable convo- lution for any fixed input dimension n. >> and any model weights w E R²());
1. Short description length: parameterized function Conv(,, w) can be represented with O(z) bits.
2. Linearity: 3 Aw,, s.t. Conv(z, w) = Aw. x for all inputs x E IR" and A o w0l2-
3. Fast computation: given arbitrary xc E R we can compute Conv(a, w) in time ((n).
These properties have many tearning-theoretic
theoretic and computational advantages. In particular. models with short description length have better generalization guarantees (Shalev-Shwarrs & Ben-David]
2014 Theorem 7.7); linearity is also advantageous statistically due to its simplicity and may interact better with optimization techniques such as batch-norm and weight-decay (loffe & Szegedy [2015] Zhang et al. 2019). The last property has clear importance in practice and is intimately connected with the first, since any linear transform with description length ((n) must take time W(n).
The Chrysalis of Kaleidoscope Operations: To maintain these properties we turn to Kaleido- scope matrices (K-matrices) (Dao et al., 2020). which are products of butterfly matrices (Parkrr 1995). Each butterfly matrix of dimension a special fixed sparsity pattern, which encodes the recursive divide-and-conquee algorithms such as the FFT. Each butterfly matrix has total of O(n n) parameters and O(n log n) runtime to
is itself product of log sparse matrices with
4

---

Under review as a conference paper at ICLR 2021
0.76
Validation accurac)
0.78
W
M
0.72
0.73
0.6
x K₂
K₁
123 0
Depth
Illustration of a K-operation parameterized by weights w and K-matrices (K1, K2, 2 M). with elementwise product in orange (left). is found via search, while weights retrained for the discovered Plot of supernet evaluation K-operations found when searching ButterfL.eNet as function depth (right).
Figure 1:
multiply a vector æ E IR". The depth of a K-matrix refers to the number of butterfly matrices in the product that form that K-matrix. Remarkably, all matrices whose matrix- products can be expressed as a constant-depth arithmetic circuit with (nn) gates can be represented as a constant-depth K-matrix with memory and time complexity ((n) (Do et al. 2020 Theorem 1); for many specific matrices, including convolutions, the logarithmic factors also disappear. These matri- ces thus provide a simple way to define a search space containing operations sharing the desirable properties of convolutions.
Several works have proposed a parameterizable operations based on butterfly factors; for example Dao et al. (2020) propose replace convolutional layers by K-matrices. As discussed above, such approaches fur parameterizable operation and train model weights for it rather than finding one in larger search space. In contrast we propose to search over a space of kaleidoscope operations, im- posing the constraint that our selected K-operations have same architecture parameterizations across all instantiations in the resulting network, but can be parameterized by different model weights in each instantiation. This is analogous to the parameterization of the same convolution operation by different models weights (or filters) at each instantiation in a network. These K-operations com- prise the Chrysalis, which can be combined with backbone architectures to create new search spaces containing potential operations for new domains.
For simplicity, we motivate and formalize design of K-operations for the of 1d input data; for higher dimensions, see Appendix[A A To motivate our construction, note that a convolution of an input x R" with filters I can be expressed using the Fourier transform matrix F Caxn,
Conv w) F (Fiag(Fw)..
Thus we can obtain a space of parameterizable operations that contains convolutions by varying the matrices in the expression above. Since F and its inverse both K-matrices (Dao et al. 2020 this can be done efficiently as follows:
Definition 3.2. A Kaleidoscope operation K-Op, of depth k S 1 defined by three K-matrices (K1, K2, MM) of depth k is operation that, when parameterized by model weights R." takes as imput an arbitrary vector æ E R. and outputs Real( K diag(M Ww) K2
is easy to show that K-operations satisfy the three desirable lata-independent properties of convo- lutions. Furthermore, in the single-channel case the extended function class K- K-Op, (.. w) of depth can trivially express any depth-2k: K-matrix transform by setting w 1, and M I,; this includes well-known functions such as Fourier, cosine, and wavelet transforms. Note that depth increases the expressivity of the space K-operations and can be critical for performance (c.f. Fig- ure T.. In the multi-channa case layer of K-operations is less expressive than the K-layer of Dao et al. 2020) but can still express average- wootggee-pooinggggooo (a type of convolution) and skip-com conn-cconetsoos,, thus comprising most of operations in NAS search spaces such DARTS (Liu et al. 2019).
The caveat here is that the Chrysalis itself does not contain these operations since it does not in- clude any nonzero operations that ignore the filter weights w, which is required for parameter-fiet free operations such as average pooling and skip-connections. This can be easily rectified by adding per-channel bias terms inside the diag that allow its output to be the identity, setting up a channel- connection problem related to that of Wortsman et al. (2019). However, we did not find simple algorithms for doing so empirically beneficial and so leave further exploration to future work.
5

---

Under review as a conference paper at ICLR 2021
Comparison of architectures found by searching Butterfl.eNet CIFAR-10. Results averages over random seeds affecting both search and offline evaluation. When warm starting with convolutions, offline ovaluation of Supernet SGD outperforms fixed convolutions by 1% on both CIFAR-IN 10 and on transfer to CIFAR-I00 Furthermore, when search is initialized to random operation, offline evaluation of Supernet SGDR matches the performance of fixed convolutions. Finally, we find that when
Table 1:
starting with convolu- tions, supernet evaluation of ButterfLeNee using Supernet SGDR attains best performance.
CIFAR
fixed operation baselines
DARTS
Supernet SGD
Supernet SGDR
classes (eval.)
random
1st
2nd
from
warm
from
warm
linear
K-layer
K-op
order
order
scratch
scratch
start
10 (supernet)
51.25
70.25
75.27
76.43
76.84
77.15
10 (offfine)
59.17 75.76
68.64 68.64
56.76
57.92
71.88
73.75
76.46
75.43
75.98
100 (offline")
28.02
43.88
39.26
29.47
29.50
41.70
42.86
44.86
44.33
44.20
For DARTS, Supernet SGD, and Supernet SGDR, K-Op found on CTFAR- is transferred to CIFAR-100.
Convolution
K-Op.: warm start
K-Op,: from scratch
ButterLeNet layer
ButtertLeNee leeeee Layer?
Figure 2: Comparison of the filters, and filter analogues, produced by three parameterized operations trained on CIFAR-10- 10: convolutions, K-operations warm-stad warm-started with convolutions, and K K-operations searched from scratch. The latter two are discovered using Supernet SGD. the case of convolutions, these are randomly selected filters at random positions on the input feature map. In the cases of the learned K- K-operations, these are randomly selected neighhorhoods of the operation over the input feature map. The first layer of the warm started K-operation remains mostly convolutional, while the second layer pools features more globally. The first layer the from scratch K-operation some locality structure, while the second layer does not.
USING THE CHRYSALIS TO COMPETE WITH CONVOLUTIONS
We now examine the viability of the Chrysalis to find good K-operations tasks where convolu- tions are known to perform well. We first consider standard computer vision tasks, i.e., the canonical application of convolutions, and next study another well-known application of parameterized volutions: extracting features from temporal data such as text (Kim 2014 Zhang et al.) 2015).
SutterfLeeNet-SSachiing for Good Operations on Image Data. To construct a search space from (2d) K-operations, we use the classic LeNet architecture (LeCun et al. 1999), which consists two convolutional layers followed by two fully connected layers. We replace each convolutional layer by layer which the same depth-9 K-Op is shared across input-output channels; our task on the resulting search space, Butterfl.NNe is thus to learn two operations in total, one for each layer. Offline evaluation of the discovered operation is conducted by fixing the architecture parameters and retraining the model weights using SGD with the same hyperparameters used for LeNet.
Because K-operations comprise a continuous search space, ButterfLeNet amenable to standard gradient based optimization without the need for continuous relaxation. At the same time, it is not straightforward to define sampling-bers based approaches beyond random search, which itself works poorly due to the difficulty of the search space. We thus evaluate the following gradient-bare methods, each with the same fixed budget in terms of number of training epochs:
DARTS (Liu et al. 2019% approximates the bilevel objective (2) using Adam (Kingma Ba 2015) to update the architecture parameters and SGD update the shared weights.

---

Under review as a conference paper at ICLR 2021
Table 2: Comparison of fixed operations and K-operations found via Supernet SGD over Nutterfl.eNet-Tee Tasks comprise a standard set of text classification benchmarks. Either supernet or offline evaluation of warm
started K-operations found using Supernet SGD outperform the fixed operation baselines on all 7 datascts.
method
evaluation
CR
MPQA
MR
SST1
SST2
SUBJ
TREC
baseline linear
offline
73.89
88.37
71.22
38.93
77.66
88.08
86.76
operations
convolution
offline
81.47
90.53
87.75
45.03
85.35
91.66
92.48
from scratch
supernet
78.74
90.51
77.43
43.71
82.06
90.78
89,44
Supernet
from scratch
offline
78.58
91.24
76.09
43.74
82.56
90.40
90.44
SGD
warm start
supernet
83.11
90.84
80.00
44.91
85.84
91.88
93.20
warm start
offline
83.74
90.90
79.72
45.24
85.3
92.18
92.24
Supernet SGD: direct optimization of the single-level objective
3 using SGD.
Supernet SGDR: runs Supernet SGD but periodically resets the step-size schedule and reinitializes model weights un; inspired by the warm-restart method of Loshchilo & Hutter (2017). it attempts to boost from-scratch performance by "warm wwarm-starting" from discovered K-operation.
We further compare our discovered K-operations to four natural parameterizable operations: linear (fully-connected) layers, convolutions, K-layers, and random K-operations.
In Tables [ we show that Supernet SGD is able search Butterfl.NNet from random initialization to find K-operations that match the performance of convolutions, i.c. regular LeNet. Despite being less expressive, our approach also outperforms the fixed K-layer approach in which all convolu- tions are replaced with pallmy-prrmeeee K-matrices. Interestingly, supernet evaluation is worse for established NAS methods like DARTS but better for direct optimization, with Supemet SGD-R outperforming convolutions by around 1.1% % from scratch and 1.4% when warm-started. Because of the K-operation construction, we can also investigate the quality of Kooperations found when we "warm-start" K-OP,, to be convolution by setting the K-matrices comprising a to the appropri- ate Fourier transforms; doing so we find K-operations that outperform convolutions. Table also shows transfer learning experiment that further demonstrates the usefulness of the K-operations discovered on CIFAR-10: when the architecture parameters are fixed and the weights retrained on CIFAR-100, operations outperform convolutions at test-time. Finally, we note the difficulty of our search space, as demonstrated by the poor performance of random K-operations, which do worse than even linear layers; this is in contrast most NAS search spaces, which are often easy-enough to be solved by random search (Li & Talwalkar 2019 Yang et al. (220)). We find that a larger ButterfLeNet model, Wide ButteriLeNet, can still outperform convolutions in terms of supernet evaluation. This is shown in Appendix
We also explore what operations are being learned, comparing convolutions, K-operations discov- ered by warm-starting with convolutions, and K-operations found from-scratch in Figure Our visualizations suggest that learned K-operations use more global information to extract features, especially in the second ButterfLeNet layer discovered from-scratch.
ButterfLeNet-TTes Searching for Good One- tne-Dimensional Operations. We next consider ap- plications of temporal data such as text. We again use the Chrysalis to replace convolutions in all onput-output channels in an existing model, namely the network of Kim (2014) which has three par- allel convolutional layers with different kernel widths followed by a fully-connected layer; our task will be find a separate K-operation for each of layer.
Our evaluation focuses on a standard suite of sentence classification tasks, with results presented in Table 2] As before, we compare the performance of Supernet SGD with the baseline performance of fixed linear operations. In out of 7 of the datasets considered, offline evaluation of Supernet SGD where the K-operations are warm started yields higher performance than all fixed operation baselines. On the remaining two datasets, supernet evaluation outperforms convolutions and offline evaluation matches the performance of convolutions. We find that when the K-operations are ini- tialized from scratch, offline evaluation substantially outperforms the fully connected baseline and, among the architectures considered, achieves the highest test aceuracy on the MPQA dataset.

---

Under review as a conference paper at ICLR 2021
Table 3: Comparison of fixed operation baselines to Butterfl.e trained using Supernet SGD on permuted CIFAR-10 and CIFAR-100. K- K-operations trained from scratch outperform all other methods on supernet eval- uation, offline evaluation, and transfer to CIFAR-100.
fixed operation baselines
Supernet SGD
dataset
lincar
conv
K-layer
from scratch
warm start
CIFAR-10 10 (supernet)
74,69
70.22
CIFAR-I0 (offline)
59.61
58.90
66.16
72.99
69.56
CIFAR- 100 (oflinee)
27.89
31.41
37.36
42.73
40.42
For Supernet SGD, K-Op found on CIFAR-10 10 transferred CIFAR- 100.
Table 4: Comparison of spherical convolutions, convolutions, and NAS on the ButterfLeNet- -Nee-Spheeiaaal scarch space, built atop the convolutional baseline of Cohen et al. (2018). We test on the stereographically projected spherical MNIST well rotated variant (Cohen et al. 2018).
Spherical MNIST
fixed operations
Supernet SGD
subset (evaluation)
conv spherical
from scratch
warm start
warm start, from scratch
non-rotated (supernet)
98.44
97.26
98.56
non-rotated (offline)
97.59
96.49
98.55
98.23
98.87
rotated (supernet)
33.92
96.32
35.77
28.26
56.
rotated (offline)
33.92
96.32
33.38
30.29
54.49
5 BEYOND CONVOLUTIONS AND TOWARDS A MORE AMBITIOUS NAS
Convolutions are well-suited to many applications, but they are not always the best operation to use. Since our broader goal is to enable users apply the Chrysalis to find neural primitives for whatever type of data they use, we now ask whether our novel search spaces can be leveraged to find operations that outperform convolutions in domains where they not optimal. We establish this in two simple settings using the same approach as before: borrowing existing network structures and replacing convolutions by K-operations.
ButterfLeNet: Unpermuting Image Data. Here we consider a setting similar to that of Section ?? except fixed permutation of all rows and columns is applied to CIFAR images before being passed as imput. Since K-matrices can express both convolutions and permutations, there exist K K-operations that do well on this data; this experiment thus tests whether we can leverage our search space to identify these good operations. Note that Dao et al. (2019) report related experiment, in which they directly attempt to recover permutation; our setting is more difficult because we are simultaneously attempting to do well on a classification task. Table shows that both supernet and offline evaluation of Supernet SGD can attain nearly the same performance as in the unpermuted case when searching from-scratch. Perhaps unsurprisingly, warm-starting from convolutions performs worse. We also outperform all fixed linear operations, including the K-layer approach that is more expressive than approach but experiences slightly larger drop in performance from Table [
ButterfLeNet SperSeiraaal Finally, we consider the spherical MNIST dataset of Cohen et al. (2018), applying the Chrysalis their baseline model consisting of two convolutional and fully- connected layer. The spherical MNIST dataset consists of stereographic projection of the MNIST dataset onto the sphere and projection back the plane, resulting in a nonlinear distortion. The rotated variant additionally applies random rotations before projecting back to the plane. We com- pare convolutions to search spaces induced by the Chrysalis. Since the spherical CNN of Cohen et al. (2018) uses two types of spherical convolution layers, we add an additional evaluation that only warm starts the first layer to break the symmetry of initializing both operations to be the same.
Table 4 shows that supernet and offline evaluation of Supernet SGD both find operations that sig- nificantly outperform convolutions but are also significantly behind spherical convolutions on the rotated spherical MNIST dataset. While convolutions, spherical convolutions, and K-operations all achieve high performance on the stereographically projected data, spherical convolutions are specifically designed to be invariant to rotation as well. It is unclear to what degree K-matrices are expressive enough to capture rotational invariance of stereographic projections. On the other-hand, our ceneral-purpont approach significantly exceeds simple convolutions. This demonstrates that while it is difficult to match sophisticated operation designs, K-operations can still lead to strong improvements over convolutions in new domains.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Nir Ailon, Omer Leibovich. and Vineet Nair. Sparse linear networks with a fixed butterfly structure: Theory and practice. arXiv, 2020.
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 Computer Vision and Pattern Recognition, 2020.
James Bergstra and Yoshua Bengio. Random search hyper-parameter optimization. Journal of Machine Learning Research, 13:281-305, 2012.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In Proceedings of the 8th International Con- ference on Learning Representations, 2020.
Taco S. Cohen, Mario Geiger, Jonas Koehler, and Max Welling. Spherical CNNs. In Proceedings of the 6th International Conference Learning Representations, 2018.
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 Con- ference on Machine Learning, 2019.
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.
Xuanyi Dong and Yi Yang. NAS-Bench-201: Extending the scope of reproducible neural archi- tecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Thomas Elsken, Benedikt Staffler, Jan Hendrik Metzen, and Frank Hutter. Meta-learming of neural architectures for few-shot learning. arXiv, 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Pruceedings of the 32nd International Conference on Machine Learning, 2015.
Yoon Kim. Convolutional neural networks for sentence classification. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, 2014.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
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.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Proceedings of the Conference on Uncertainty Artificial Intelligence, 2019.
Liam Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(18)):1-52. 2018.
Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradient algorithms for neural architecture search. arXiv, 2020.
Sungbin Lim, Ildoo Kim, Taesup Kim, Chiheon Kim, and Sungwoong Kim. 2019.
Fast autoaugment,
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proceedings of the 7th International Conference Learning Representations, 2019.

---

Under review as a conference paper at ICLR 2021
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In Pro- ceedings of the Sth International Conference on Learning Representations, 2017.
Jieru Mei, Yingwei Li, Xiaochen Lian, Xiaojie Jin, Linjie Yang, Alan Yuille, and Jianchao Yang. AtomNAS: Fine- grann-g end-to-end neural architecture search. Proceedings of the 8th Inter- national Conference Learning Representations, 2020.
Vladimir Nekrasov, Hao Chen, Chunhua Shen, and lan Reid. Fast neural architecture search of com- pact semantic segmentation models via auxiliary cells. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Behnam Neyshabur. Towards learning convolutions from scratch. arXiv, 2020.
D. Stott Parker. Random butterfly transformations with applications in computational linear algebra. Technical report, UCLA, 1995.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proceedings of the 35th International Conference Machine Learning. 2018.
Esteban Real, Chen Liang, David R. So. and Quoc V. Le. AutoML-Zero: Evolving machine learn- ing algorithms from scratch. In Proceedings of the 37th International Conference on Machine Learning. 2020.
Shai Shalev-Shwarte and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithns. Cambridge University Press, 2014.
Sebastian Thrun and Lorien Pratt. Learning to Learn. Springer Science Business Media, 1998.
Yujing Wang, Yaming Yang, Yiren Chen, Jing Bai, Ce Zhang, Guinan Su, Xiaoyu Kou, Yunhai Tong, Mao Yang, and Lidong Zhou, Textnas: neural architecture search space tailored for text representation. In Proceedings the 34th AAAI Conference Artificial Intelligence, 2020.
Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. Discovering neural wirings. Ad-
vances in Neural Information Processing Systems, 2019.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC- DARTS: Partial channel connections for memory-efficient architecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
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.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS- Bench- 101: Towards reproducible neural architecture search. Proceedings of the 36th Interna- tional Conference on Machine Learning, 2019.
Matthew D. Zeiler. Adadelta: adaptive learning rate method, 2012.
Arber Zela, Julien Siems, and Frank Hutter. NAS Bench-1Shotl. Benchmarking and dissecting one- shot neural architecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Guodong Zhang, Chaoqi Wang, Bowen Xu, and Roger Grosse. Three mechanisms of weight decay regularization. In Proceedingy of the 7th International Conference on Learning Representations, 2019.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. In Advances Neural Information Processing Systems, 2015.
Allan Zhou, Tom Knowles, and Chelsea Finn. Meta-learning symmetries by reparameterization. arXiv, 2020.
10

---

Under review as a conference paper at ICLR 2021
Table 5: Performance CIFAR-I0 of larger variant of LeNet ("Wide LeNet") with greater number of channels. Here, supernet evaluation of warm started Supernet SGD achieves the highest performance on CIFAR-10.
Supernet SGD
dataset
conv
from scratch
warm start
CIFAR- 10 (supernet)
78.42
87.27
CIFAR-10 (offline)
86.72
76.51
86.72
A
KALEIDOSCOPE OPERATIONS
To generalized Kaleidoscope operations to higher dimension, we simply perform the Kaleidoscope operations on each dimension of the input. This is similar to how 2d-FFT is done by performing two Id-FFTs on each dimension of the input.
More precisely, we take the Kronecker product (denoted by @) of the 1d Kaleidoscope matrices in the 1d Kaleidoscope operation. For simplicity of notation, we assume that the two dimensions have the same size
Definition A.1. A 2d Kaleidoscope operation K-Opa of depth k 3 defined by six K- matrices (K1,,, K1, K2,1, 2,1,K222 Kg M1, M2) of depth an operation that, when param- elerized by model weights w E R=, takes as inpul an arbitrary vector a E Rnd and outputs Real(K, diag( Mw) K2r)) where K; K1,1 K1,, K₂ K2, @ K2 and M -M M2.
It is also straightforward to generalize to N-d: Definition A.2. An N-d Kaleidoscope operation K-Op, a of depth defined by 3N K-matrices (K1,,..... K1,N, K2,1,..., K2,N, M1, ..., Mn) of depth lo is operation that, when param- eterized by model weights w RT". takes as input an arbitrary vector x E Ip=" and outputs Real( K2 diag( Mw) w)) K2z) where K; ON K1, K2 = NN K2,5 and M 2 M M,.
B WIDE BUTTERFLENET
We show that started supernet training of larger LeNet architecture can outperform its fixed convolutional counterpart. These results are presented in Table
C EXPERIMENTAL DETAILS
C.I BUTTERFLENET-VISION
C.I.1 ARCHITECTURE DETAILS
For all LeNet experiments, we use the LeNet architecture except padding is added to the convolu- tional layers to preserve feature map dimension, and ReLUU activations used. Namely, this is convolution (3, 6), average pooling (2, 2), convolution (6, 16), average pooling (2, 2), linear (120), linear (84), linear (10 or 100). 5 kernels are used throughout. The linear baseline consists of 4 linear layers with ReLU activations. In particular, that is linear (6 16 16), linear (16 8 8), linear (120), linear (84), linear (10 or 100). The K-layer baseline replaces all convolutions in LeNet with K-layers of the same shape. A K-layer consists of two K-matrices per ontut- channel pair. For ButterfLeNet experiments, we replace each convolutional layer in LeNet with K-operation of the same shape, and parameterized by the same number of model parameters as the analogous convolutional layer. In particular for our warm start experiments, we initialize Ki and K2 to be inverse Fourier transform and Fourier transform matrices scaled to be unitary, while M is initialized be a unscaled Fourier transform matrix. Each of these are depth K-matrices. When initializing K-operations from seratch, we depth 9 K-matrices with unitary initialization. That is, unitary matrices.
K1, K2, M are each a product of K-matrices, where K1, K2, M are each initialized to be random
Wide LeNet comprises convolutional layers with more channels than LeNet, and two linear layers. In particular, convolution (3, 32), batch norm, convolution (32, 64), batch norm, convolution (64,

---

Under review as a conference paper at ICLR 2021
128), linear (128), batch norm, linear (10 100). Here, convolutions use 3 3 filters. As before, ReLU activations are used. Wide ButterfLeNet replaces all convolutional layers with K-operations of corresponding dimension. In both the warm start and from scratch settings, tie the operations between the second and third K-operation layers.
C.1.2 HYPERPARAMETERS FOR OFFLINE EVALUATION AND FIXED BASELINES
For offline evaluation (except DARTS) and models with fixed operations. we train for 200 epochs using SGD with a learning rate of 0.01, decreased to 0.005 at epoch 100, to 0.001 at epoch 150 and a minibatch size of 128. We use weight decay of 0.0001. For all methods except from scratch ButterflLeNer we employ data augmentation with random cropping and random horizontal flipping. For from scratch ButterfLeNet, we instead employ the Fast AutoAugment policy found on CIFAR- 10 (Lim et al. 2019). For offline evaluation of DARTS, we train using the Adam optimizer KKiggma & Ba 2013) to stay faithful to the original DARTS formulation.
C.1.3
ARCHITECTURE SEARCH
For Supernet SGD methods, train the supernet for 800 epochs using SGDD and initial learning rate of 0.01, decreased to 0.005 at epoch 400, to 0.001 at epoch 600. We use the same augmenta- tion scheme used for baselines and offline evaluation, where from scratch ButterfLeNet uses Fast AutoAugment. We use a weight decay of 0.0001. First and second order DARTS use Adam (with a learning rate of 0.001) for optimizing architecture parameters as well as bilevel training routine. First order DARTS alternates between updating architecture parameters and model parameters us- ing a validation set and the training set. practice, we partition the training set into equally sized subsets. Second order DARTS uses a second order gradient with a 'lookahead' step, which is ap- proximated using a finite difference approximation. We find that the second order update is more stable in our search spaces.
For Supernet SGDR methods, we train the supernet times for 200 epochs each, using SGD with learning rate of 0.01, decreased to 0.005 at epoch 100, 0.001 at epoch 150. All other hyperpa- rameters are the same as above.
C.2 BUTTERFLENET-TEXY
C.2.1 ARCHITECTURE DETAILS
Our convolutional baseline is the convolutional architecture proposed by Kim (2014) with static word2vec embeddings. This architecture involves three 1d convolutional layers in parallel with different filter sizes (3, 4, and 5), and 100 output channels each, which are concatenated. This followed by 1d max pooling, and 300 x & linear layer where k is the number of classes in the classification task. The linear baseline replaces the three parallel convolutional layers with a single linear layer. For both of these, the ReLU activation function is used throughout. ButterfLeNet-text, which generalizes the convolutional baseline, replaces all 1d convolutions with Id K-operations of the same dimensionality. For from scratch, use depth 9 K-operations.
C.2.2 HYPERPARAMETERS FOR BUTTERFLENETTTEEX
We use the same training procedure for supernet training, offline evaluation, and fixed operations. In particular, use the Adadelta optimizer (Zeiler) 2012) and train using early stopping with patience parameter of based on held out validation set. We use batch size of 50 and employ dropout with probability of 0.5 on the final linear layer.
C.3 BUTTERFLENEET-PPERRE
C.3.1 ARCHITECTURE DETAILS
The baseline convolutional architecture that we consider comprises two convolutional layers and fully connected layer. Both convolutional layers have 5 x 5 kernels with a stride of 3, the first has 20 output channels and the second has 40 output channels, and use ReLU throughout, This is followed
12

---

Under review as a conference paper at ICLR 2021
by linear layer. ButterfLeNNe-sshheiie replaces these convolutions with K-operations. We warm start the first K-operation as convolutions and initialize the second one from scratch.
C.3.2 HYPERPARAMETERS FOR BUTTERFLENET-SPPEEE
We use the same training procedure for supernet training, offline evaluation, and fixed operations. Namely, we train for 20 epochs using Adam with a learning rate of 0.0005 and minibatch size of 32.
13


Reviews:
[{"review_id": "beNlUvJHBej", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:** \nThe authors propose a new NAS method that comes with a space of operations generalizing the convolution. The proposed method makes it possible for users to design their own search spaces according to the training data. However, the experiments and writing should be further improved.\n\n**Strengths:**\n1. The proposed method enables users to build their own search spaces.\n2. The authors incorporate Kaleidoscope-operations to develop a new search space.\n\n**Weaknesses:**\n1. The authors only conduct experiments on small datasets, e.g., CIFAR. It would be stronger to report the comparison results on ImageNet.\n2. The authors seek to allow users to design their own search spaces adapted to their data, which, however, is very labor-intensive. Moreover, it is also not clear how different search spaces would affect the search performance?\n3. The proposed method fixes the backbone architecture and only searches for the optimal operation. However, this method ignores the topology of architectures. In my opinion, architecture topology should be an important factor to search in NAS.\n4. The authors argue that the proposed method “enables the discovery of good design patterns with limited human specification from data in under-explored domains”. What does “under-explored domain” mean? How to define it?\n5. What is FFT in Page 4? There is no definition before it appears, which makes the paper hard to follow.\n6. From Definition 3.2, the search process w.r.t. k-operations seems to learn the parameters of the matrix K1 and K2. Thus, it seems not a typical NAS process. It would be better to illustrate the relationship between the proposed method and the standard NAS.\n7. It is not clear what the proposed search space is. How large is it?\n8. Several state-of-the-art NAS methods should be compared in the experiments, such as PDARTS, PCDARTS, etc.\n9. The writing of this paper should be improved. The paper is hard to follow and there are many grammatical errors:\n(1) In Page 3, “the main challenge … is intractability” should be “The main challenge … is intractable”.\n(2) In Page 5, “Dao et al. (2020) propose replace convolutional layers” should be “Dao et al. (2020) propose to replace convolutional layers”\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YMGeABT7Fqi", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper introduces Kaleidoscope-operations to reprameterize convolutions. The reparameterization results in a more general search space of convolutions. Moreover, it enables one-level optimization on the convolution search as well as a supernet optimization, which avoids post-search discretization and post-discretization re-training.  \n\n\nPros:\n\nThe paper seems a good reading material to teach readers about a big picture of convolution search problem or even neural architecture search problem.\n\nThe paper also shows a huge ambitious motivation to touch the boundary of the current main-stream NAS methodologies. \n\nThe idea of introducing repratermeterized convolutions (i.e., K-operations that was originally proposed by Dao et al., 2020) to convolution search seems novel and promising to me. \n\nThe evaluation is comprehensively conducted on several novel search spaces over vision and text data, and the results show the effectiveness of the proposed method. When being evaluated on permuted CIFAR and spherical MNIST, the new method shows some superiorities.\n\n\nCons:\n\nIt seems that the proposed model is designed to merely search for convolutions with a reprameterization approach (i.e, K-operation). Compared to regular NAS algorithms like DARTS that search for a much larger architecture space including convolutions, poolings, skip connections, this paper’s search space is merely on reprameterized convolutions. This makes me disappointed as both the title and the beginning parts somehow mislead readers that the paper aims at making a good innovation in the big scope of NAS. However, I finally realize that it actually searches for better convolutions rather than an entire neural architecture, after I went to the last paragraph of Page 5. Moreover, the search merely on convolutions is very likely to result in a much easier neural architecture optimization task, and make the so-called supernet (without post-search discretization & post-discretization retraining) work. This also reminds me that there exists one work [Stamoulis et al., 2019] which shares a similar motivation with this submission. In particular, [Stamoulis et al., 2019] proposes one single-path over-parameterized ConvNet to encode all architectural decisions with  convolutional kernel parameters. The overall network loss is directly a function of the “superkernel” weights, where the learnable kernel- and expansion ratio-related parameters can be directly derived as a function of the kernel weights. This strategy also enables one-level optimization and has a potential for supernet optimization as suggested by the submission. \n\n\n[Stamoulis et al., 2019] Single-path NAS: Designing hardware-efficient convnets in less than 4 hours. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2019.\n\n\nIn Table 1, I find the best performances on CIFAR-10 and the transferring to CIFAR-100 are still far away from the state of the art. For example, DARTS (Liu et al., 2019) can obtain about 97% and 74% accuracies on CIFAR-10 and CIFAR-100 respectively. Please explain which causes this gap. For a fair comparison, I see the results of the proposed K-op with supernet SGD/SGDR are worse than Conv (fixed operation baselines, offline), while they are better when warm starting with convolution. What if warm-start is also applied to Conv (fixed operation baselines, offline)? \n\nAs presented in the paper, Fig.2 shows that learned K-operations use more global information to extract features. But what is the benefit for deep learning?\n\n\nTable 2 is not self-contained. It should clarify the meaning of CR, MPQA, …, TREC in the caption. I guess they are the 7 used datasets according to the presentation in the main text. Again, I find the proposed method can obtain better results only when using the warm-start strategy, while it generally performs worse than the competitor (i.e., convolution) when training from scratch. \n\nThe last column of Table 4 seems confusing to me whether it corresponds to the case that uses warm start or from scratch. \n\nIn the paragraph of “utterfLeNet: Unpermuting Image Data”, the index of the referred section is missing.\n\nOverall I think the paper oversells the new idea and the corresponding technology. Thus I tend to suggest a major revision by tuning down its current tone throughout the paper, while I like the idea and really expect the paper can be baked better for publication. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EauVzx4Nz65", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper claims to perform neural operator search on a search space defined by a family of Kaleidoscope operations. The paper address the computation challenges in the search using  a supernet, and performs variable ablation studies to show that the searched K-Op can slightly outperforms existing convolution operators.\n\nHere I appreciate if the authors can clarify the following points:\n\na) \"Each butterfly matrix of dimension n x n is itself a product of log n sparse matrices with a special fixed sparsity pattern, which encodes the recursive divide-and-conquer algorithms such as the FFT.\"\n\nHere the author deliberately selects a family of operations that contains FFT and convolution. It is unclear how you constrain the search space of K-matrices; I get you searched K operations, but I did not find it's structure and how does that different from FFT. I'm also confused about the point of fig.2, what's the point you want to say about these feature map?\n\nb) Ablation studies.\n\nThere are a lot of ablation studies show that the searched K-operations are better than convolution. However, none of them show they actually pushed SoTA results. Considering the fact that there are so many tricks (https://github.com/facebookresearch/LaMCTS/tree/master/LaNAS/LaNet) in boosting the performance of a CNN, it is more convincing to see the searched K operators can actually push the boundary. The ablation studies in the current experiments are not enough to convince me, especially they are focusing on relatively simple tasks, e.g. CIFAR-10, MNIST.\n\nc) Another thought, Tensorized Neural Network has also tried to replace of current operators, and their hyper-parameters can also formulate a search space; My main concern about this line of work is \"are we really making progress here\"?\n\nHere we're building something based one prior knowledge; if we will end up someting similar to convolution, so what's the point of doing it? However, the paper lacks a strong evidence that they invented a new operators that actually work. This is my main concern of this paper.\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2Uvl1rz_txE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper proposes to search neural network operations that outperform some human-designed ones, e.g. convolution. Specifically, it proposes to extend the Kaleidoscope paper to formulate a new searchable operation. Combining with differently architecture search method, \n\n# Strength\n\nThe proposed Kaleidoscope Op is new to the field and seems to be an interesting aspect, searching for an operation similar to convolution but on different tasks. \n\n# Major weakness\n\n## 1. The presentation of this work hinders my understanding. \n\n- The paper introduces a simple operation set but with many unnecessary descriptions and definitions. For example, what is the purpose to introduce definition 3.1? Does a parameterized operation return a parameterized function? This is confusing. \n\n- Is Section 2 necessary? It occupies a significant space in the main text but is not related to the methodology section 3. I did not see any definition introduced in this section later. Instead, the definition of the core method of Kaleidoscope operations is not well introduced. The paper keeps mentioning the Dao 2020 and K-matrices, yet it only briefly defines it. \n\n- What's the purpose to emphasize the three `key properties'? Will the author show some ablation study what happened if these properties are violated for some other operations? Why they are good properties in the NAS domain? \n\n- How do you combine the NAS with K-Op (defined in 3.2)?\nIt is strange to see the authors spend a large space to describe the common NAS algorithms in section 2 but do not clearly state how this K-Op is combined with the search algorithms. On page 6, there is one sentence saying `K-op comprise a continuous search space...', but what exactly is that? What are the settings of your experiments? Please correct me if I miss something. For now, it should be clearly defined instead of a brief sentence to forester the reproducibility of this method. \n\n- What's offline in Table 1? Does it mean you generate the architecture after search and train from scratch on CIFAR-10? But it seems on many methods the offline surpass the super-net, which is again weird. \n\n\n\n## Weak baselines\nThis paper essentially extends the original paper to make it searchable. Does it seem to be reasonable to compare against it at least over one task in the Kaleidoscope paper? The baselines, e.g. LeNet, in this work are too weak compared to the recent NAS approach. I understand this paper does not claim to be state-of-the-art but showing the potential, yet with this baseline on CIFAR-10, it is hard to compare with the literature.\n\n\n# Minor issues\n\n- a random search on NAS on Page 7, did you mean Yu et al 2020 (evaluating the search phase of NAS) instead of Yang et al. 2020 (NAS Evaluation is frustratingly hard)? The latter describes the stand-alone training pipeline can significantly impact the reproducibility where Yu et al. describes that many NAS algorithms do not even outperform the random search.\n\n- `FFT' on page 4 not defined when first used.\nBroken reference on page 8.\n\n- Repeating descriptions: Page 2 Top `desirable properties: short description length ...` with page 4 first paragraph of section 3.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Motivated by the possibility of Neural Architecture Search on domains beyond computer vision, this paper introduces a new search space and search method to improve neural operators. It applies the technique to problems in vision and text.

Reviewer 1 found the paper interesting and liked the motivation of considering different tasks in NAS. However, they found some aspects of the paper confusing and, like other reviewers, thought that the baselines were weak. The authors clarified some points, and R1 said that some, but not all, concerns were resolved. The reviewer improved their score by a point but still was not in favour of acceptance.

Reviewer 2 thought the paper was interesting but questioned its main claim: that it was proposing a search space over novel operators. They argued that what was discovered was similar to convolution and therefore not much had been gained. They questioned the significance of the ablation studies: there were a lot of them, but they focused on relatively simple tasks like MNIST and CIFAR-10. They also asked some clarifying questions which were answered by the authors. Pushing back on the point about the smaller scale of the experiments (in a general reply to all reviews), the authors said that the goal of their work was not advancing computer vision, but to push NAS beyond computer vision and simple search spaces to new application domains.

Reviewer 3 liked that the paper gave a good overview of the NAS problem and thought that it was ambitious. They also thought the approach was novel and promising. Like R2’s comment, R3 seemed disappointed that the search was over “reparameterized convolutions”. In fact, they thought that the paper was overselling its contribution. They pointed out that performance was still far from state-of-the art on the various benchmarks. The authors argued against this view of “reparameterizing convolutions” and claimed that the search space was, in fact, much larger than that of DARTS. R3 read and responded to the rebuttal, appreciating the response but ultimately thought that the search space wasn’t clear and comparisons fell short.
Reviewer 4 shared similar pros & cons as have been pointed out by the other reviewers. They thought that operator search was limiting and that the paper should also consider topology. The authors responded to this, saying that they intentionally fixed the topology. Searching beyond operators was out of scope. R4 responded to the rebuttal though still had some remaining concerns both in terms of motivation and execution.

Multiple reviewers said that they would have considered the paper more favourably had an updated paper been submitted, addressing some of the original concerns. As it stands, all of the reviewers think that the paper has some merits but none believe after considering the author response, that the paper is ready for acceptance. I see no reason to overrule the consensus.
Decision: Reject