# Balanced Mixture of SuperNets
for Learning the CNN Pooling Architecture

Mehraveh Javan
LIVIA, ÉTS
Montréal, Canada
<EMAIL_ADDRESS>
&Matthew Toews
LIVIA, ÉTS
Montréal, Canada
<EMAIL_ADDRESS>
&Marco Pedersoli
LIVIA, ÉTS
Montréal, Canada
<EMAIL_ADDRESS>
Corresponding author

###### Abstract

Downsampling layers, including pooling and strided convolutions, are crucial
components of the convolutional neural network architecture that determine
both the granularity/scale of image feature analysis as well as the receptive
field size of a given layer.

To fully understand this problem, we analyse the performance of models
independently trained with each pooling configurations on CIFAR10, using a
ResNet20 network, and show that the position of the downsampling layers can
highly influence the performance of a network and predefined downsampling
configurations are not optimal.
Network Architecture Search (NAS) might be used to optimize downsampling
configurations as an hyperparameter. However, we find that common one-shot NAS
based on a single SuperNet does not work for this problem. We argue that this
is because a SuperNet trained for finding the optimal pooling configuration
fully shares its parameters among all pooling configurations. This makes its
training hard, because learning some configurations can harm the performance
of others.
Therefore, we propose a balanced mixture of SuperNets that automatically
associates pooling configurations to different weight models and helps to
reduce the weight-sharing and inter-influence of pooling configurations on the
SuperNet parameters. We evaluate our proposed approach on CIFAR10, CIFAR100,
as well as Food101 and show that in all cases, our model outperforms other
approaches and improves over the default pooling configurations.

##  1 Introduction

Downsampling layers in convolutional neural networks (CNN) are crucial, as
they provide robustness to shift and scale variations [1], reduce the
computational cost of models [2, 3], and control the access of subsequent
convolution kernels to spatial information, determining their receptive field
[4, 5]. In CNNs, spatial resolution is related to the receptive field, which
determines the aggregation of local features and affects the performance of
the CNN [6, 7]. The receptive field in turn is controlled indirectly by the
hyperparametrs of the network such as depth, filter sizes and
downsampling/pooling layers. The spatial density of the content in a dataset
highly affects the optimal receptive field and therefore, the spatial pooling
configuration. For instance, for a good recognition on textures, smaller and
more detailed local patterns are more important [6], while for shapes,
considering larger regions of the image should provide a better representation
[5]. Thus, being able to select how to downsample the image representation in
CNNs can help to better adapt the representation to the specific
characteristics of a given dataset and help to better understand the way that
convolutional neural network find meaningful patterns in images, and therefore
determine what are the relevant features for a given task [3].

In CNN design, feature map downsampling is commonly performed by applying a
strided convolution [8], a convolution followed by a pooling operation [9, 10]
or a combination of the two [11]. For a downstream task such as
classification, the position of the downsampling in a network architecture is
pre-defined and based on the assumption that the receptive field should
increase over layers until covering most of the image [7]. While this
assumption can be removed by the use of self-attention [12], its usage seems
still utterly important for a good trade-off of computation and accuracy [13].
In this work we show that the commonly used pooling configurations may not be
optimal. A possible solution is to learn the best pooling configuration for
the dataset at hand. However, pooling configurations are discrete parameters
and the number of candidate architectures grows exponentially with depth,
making bruteforcefully searching for the best pooling configuration
computationally infeasible for modern CNNs.

Previous works that attempt to find optimal feature map sizes in a predefined
architecture avoid the discrete nature of sub-sampling layers by relaxing the
problem by learning resizing modules [14, 3, 6], or indirectly do so by
learning continuous filter sizes [15, 16, 15] at the same time as training the
CNN. Some works such as DiffStride [3] casts learning fractional strides as
learning cropping size in frequency domain, the pooling is performed in
spectral domain resulting in higher cost and involving complex values
operations.

Differently than previous work, we cast the problem of finding the optimal
scales of analyzing the CNN features as a Neural Architecture Search (NAS)
problem. A popular research direction for solving NAS problem is to first
relax the optimization problem into an equivalent, but differentiable one and
then find the optimal hyper-parameters through bi-level optimization [17]. The
search is then reduced to the training of a single over-parameterized network
that contains all the searchable configurations, commonly called a SuperNet.
However, differentiable models are computationally and memory-wise demanding
because they evaluate all model configurations at each training iteration.
Additionally, they do not always provide optimal solutions as the bi-level
optimization is heavily approximated [18] and it is difficult to impose
constraints in configurations (as some configurations might not be feasible).

An alternative is to train a SuperNet by sampling at each iteration a
different sub-net [19, 20, 21], while selecting the most likely sub-net
(Single Path Single-Shot). This solves the problems of computation and memory
and it is not limited to differentiable models. However, finding the optimal
subnet during training is quite risky because the estimation of the gradients
for sampling based algorithms is very noisy [20] and the learning can easily
be misled by this noise. These NAS approaches are sometimes referred to as
coupled or one-stage approaches, since the training of the SuperNet and
searching for the optimal configuration are performed together. In general,
coupled optimization of architecture and weights suffer from bias towards
rapidly converging networks and multi-model forgetting [22]. A promising
alternative is a two-stage search method where a SuperNet is used to sample
configurations uniformly with shared parameters for training, but no specific
configuration is selected or preferred [19]. Instead, after training, at
search stage, the best configurations are evaluated on a validation set and
selected. Even though in this case, training might be slightly longer, because
it does not favor any sub-net, the simplicity and the robustness of the
provided results make it a promising candidate for NAS, especially for those
problems that are difficult to be relaxed in a differentiable way [23]. For a
more detailed analysis of related work see Appendix A.

In this work we tested both differentiable and sample based approaches, but
both failed to provide good results for finding the optimal pooling
configuration of a network. We hypothesize that the underlying reason is two
fold: inappropriate search space design, and strong weight sharing in
SuperNet. We show that defining the search space naively, by treating each
resolution similar to independent operations, does not necessarily return
better results than fully sharing weights among all resolutions, despite lower
degree of weight sharing among the former. This search space design result in
greedily reducing the weight sharing, i.e. all configurations with the same
resolution at a layer share weights, regardless of the path as a whole.
Therefore, even though complete weight sharing poses a problem, its reduction
should be performed in a more appropriate way.

To investigate this problem, we perform extensive experiments on on CIFAR10
dataset to find the optimal pooling configuration on ResNet20. As the
resolution of CIFAR10 images is low, ResNet20 applies only 2 pooling layers,
which amounts (after reasonable constraints discussed in section 2.1) to 36
configurations. Thus, we have independently trained all configurations and
consider the obtained accuracy as our ground truth performance. A revealing
result is that, even with only 36 possible configurations and the extreme use
of CIFAR10 for image classification, the standard pooling strategy is not the
optimal and there is a gap of more than one point.

In order to find the optimal pooling configuration, we propose a new model
based on SuperNet sampling that reduces the problem of parameter sharing by
using multiple balanced SuperNets. The sampling of the pooling configuration
is kept uniform as in [19], to avoid to introduce a bias in the selection of
the best SuperNet. However, to avoid interference among the different pooling
configurations, we train multiple models at the same time. Each configuration
favors sampling the model that leads to higher accuracy with it, while making
sure that all models on average receive equal amounts of training, so that
they are balanced. This training strategy allows each model to specialize to
different pooling configurations.

Our main contributions are summarized as follows:

  * •

We present the task of finding the optimal CNN downsampling or pooling layers
as a NAS problem, and perform extensive experiments to evaluate search space
design and NAS methods on the CIFAR10 classification task with the ResNet20
architecture. We show that designing the search space for this problem
requires more insight and naive design can lead to poor pooling
configurations.

  * •

We show that, while optimal pooling configurations can improve upon the
performance of standard configurations on the widely used CIFAR10 dataset,
they are not identified by common NAS methods. We argue that this is due to
weight sharing in the SuperNet and more specifically to the full weight
sharing of the problem.

  * •

We propose a balanced mixture of SuperNets that reduces the weight sharing
problem by learning the correct association between each pooling configuration
and one of the weight models.

  * •

We validate our approach on several datasets and CNN configurations and show
that by only learning the optimal scales with our method, we can improve the
classification performance of ResNet architectures without altering any other
hyperparameters.

##  2 Our Approach: Balanced Mixture of SuperNets

In this section we present the search space that we use in order to find the
optimal pooling configurations. Then we present the corresponding SuperNet
model and finally the balanced mixture of SuperNets we propose to tackle the
full weight sharing problem.

###  2.1 Search Space

In this work we focus on finding the optimal spatial resolution of the feature
maps in a CNN, that are controlled by downsampling operations.

First, we consider the general search space that contain $r$ resolutions per
layer. The downsampling is performed by applying the most commonly used
downsampling operations such as max or average pooling reducing feature map
size by a factor of two. Similarly to typical layer-wise operations, we can
assign unique convolutional operations to each resolution at each layer.
Considering $L$ layers, this will result in search space of size $r^{L}$. We
note that for classification it is well known that the resolution of feature
map is reduced across layers. Therefore, paths in the search space that
contain upsampling operations are not appropriate for this task.

As downsampling operations reduce the feature map size, the boundary of this
search space is determined by input size and the minimum feature map size
expected before the classification layer. We consider the same number of
downsampling operations as a default network (i.e. the predefined network
configuration) and exclude from the search space the first pooling layer as
the it corresponds to a manipulation of the input data. With these
restrictions, the search space size is combination ${L-1\choose p}$,
exponentially growing with the depth of the network. With $p+1$ resolutions
present at the search space, each architecture in this search space can be
uniquely identified by the number of blocks in each resolution as
$\alpha=[n_{0},n_{1},..n_{p+1}]$, where $n_{i}$ is the number of blocks in
resolution $i$ and $\sum_{i}n_{i}=L$. The search space design for each
experiment is detailed in Appendix B.2 in tab. 5.

For simplicity we use a pre-defined number of channels for all architectures,
ensuring the same number of parameters in all architectures. We choose ResNet
[11] as the building block of our search space as it is one of the most widely
used and well studied architectures and ensured the incorporation of skip
connections in our search space. As in ResNet the basic block is not a single
convolutional layer but a block (with two convolutional layers and the skip
connection), we use this block instead of a layer as basic unit to move the
pooling location.

###  2.2 SuperNet

Figure 1: Interference of representations for ResNet20 on CIFAR10. _Early
pooling_ and _late pooling_ produce different feature representations on their
layers, which lead to different performance (on top). When training a model by
sampling either one or the other pooling configurations (_combination_), the
two representations interfere which leads to lower performance of both models.
This motivated us to propose a mixture of models.

In order to find the optimal pooling configuration we follow a two-stage
strategy in which we first sample all configurations during training and then
evaluate the best ones at evaluation time. We follow single-path uniform
sampling strategy [19], by sampling a pooling configuration $c\in\mathcal{C}$
(from the search space described above) with uniform probability at each
iteration. For a mini-batch of training samples and the corresponding
annotations $(x,y)\in\mathcal{X}_{tr}$, we update the network weights $w$ by
minimizing the following loss:

$\sum_{(x,y)\sim\mathcal{X}_{tr},c\sim\mathcal{{C}}}\mathcal{L}(f_{c}(x,w),y),$
(1)

where $f_{c}$ is the output of the network for a given pooling configuration
$c$ and $\mathcal{L}$ is a classification loss such as cross-entropy. The
choice of uniform sampling [24, 19] is hyperparameter free and ensures
fairness in training among architectures and single path selection helps
alleviate the weight sharing problems. As the configurations are chosen
uniformly, this training does not favor any specific configuration provides a
meaningful estimation of the performance of each configuration.

At the end of training, the network $f$ is evaluated on a validation set
$\mathcal{X}_{val}$ for all configurations $\mathcal{C}$, and top-k
configurations with higher accuracy are selected as best configurations.
Previous work has shown that this approach works when used to select network
parts that do not share weights, however, in our setting, as all
configurations share the same parameters, they produce interference, and the
SuperNet is no longer a good proxy to find the best performing configurations,
which is the aim of this approach. This is illustrated in Fig. 1, where
jointly training two pooling configurations produces worse results than
training either one or the other independently. In fact, the features and
structures seen by the convolutional filters when working with different
pooling configuration are drastically different and learning them together
hinder performance. For this reason, to reduce the weight sharing and to avoid
the interference of different configurations on the same model we propose to
use a mixture of models.

Figure 2: Balanced Mixture of SuperNets. At each training iteration we
uniformly sample a pooling configuration $c$, then a model with a probability
proportional to $p(m|c)$. The model weights $w_{m}$ are updated on a mini-
batch of training data from model accuracy $Acc$ on validation data. A moving
average of the accuracy is used to update $p(c,m)$ such that $p(m)$ remains a
uniform, balanced mixture of models, ensuring that each model is trained for
the same number of iterations.

###  2.3 Balanced Mixture of SuperNets

Instead of using a single set of weights or SuperNet, we propose to use $M$
independent SuperNet models or weight sets $w_{m}$ associated with a network
$f_{c}$. In this way, each set of weights may specialize to represent unique
subsets of specific pooling configurations, leading to improved performance.
After each mini-batch training iteration, we compute the moving average of the
accuracy $a_{c,m}$ on a validation minibatch $\mathcal{X}_{val}$ for a given
network $f_{c}(\cdot,w_{m})$ with pooling configuration $c$ and weight set
$w_{m}$ as follows:

$a_{c,m}=\beta\leavevmode\nobreak\ a_{c,m}+(1-\beta)\leavevmode\nobreak\
{Acc}(f_{c}(x,w_{m}),y),\ \leavevmode\nobreak\ \leavevmode\nobreak\
(x,y)\sim\mathcal{X}_{val},\leavevmode\nobreak\ \leavevmode\nobreak\
c\sim\mathcal{C},\leavevmode\nobreak\ \leavevmode\nobreak\ m\sim p(m|c)$ (2)

where $\beta$ is a hyper-parameter controlling the smoothness of the moving
average. At each iteration, the pooling configuration $c$ is sampled
uniformly, while the model $m$ is sampled based on the conditional
probabilities $p(m|c)=\frac{p(c,m)}{\sum_{c}p(c,m)}$. The probability $p(c,m)$
is computed by normalizing the accuracies $a_{c,m}$ with a $\tau$-softmax
function:

$p(c,m)=\frac{\exp(a_{c,m}/\tau)}{\sum_{j,k}\exp({a_{j,k}}/\tau)},$ (3)

where in Equation (3) $\tau$ is a temperature hyperparameter of the
probability distribution where $\tau\to 0$ implies a maximally concentrated
distribution. These probabilities are thus proportional to the accuracy of the
chosen joint configuration of pooling $c$ and model $m$. We could use directly
these probabilities to sample with a multinomial distribution a joint
configuration $(c,m)$ to train a mini-batch. However, this would make the
model focus on some specific joint configuration/model during training and
will lead to coupling of pooling configurations and models due to unbalanced
sampling. Instead we want the training to give equal importance to each
pooling configuration $c$ while selecting the most promising model. The best
pooling strategy is then selected at the end of the training, making sure that
each configuration and each model have received the equal amounts of training.

We thus achieve balance supernet mixtures by imposing the constraint that the
joint probability distribution $p(c,m)$ have uniform marginals, i.e.
$\sum_{i}p(c_{i})=1/C$ and $\sum_{j}p(m_{j})=1/M$. We use the iterative
proportional fitting (IPF) algorithm to do this, where $p(c,m)$ is
alternatingly normalized along $c$ and $m$ dimensions until uniformity is
achieved. The KL-distance is used to estimate the deviation of $p(m)$ from
uniformity, and IPF terminates when the KL-distance falls below the threshold
of $\delta=0.0001$. At this point the pooling configuration $c$ is sampled
uniformly while the model $m$ is sampled from the conditional distribution
$p(m|c)$.

Balancing allows each model to focus on different configurations, while
ensuring equal importance of all models during training iterations. $\tau$ is
a concentration parameter and is decreased linearly over the course of
training. After training, the mixture of SuperNets is used to select the top-k
performing configurations, by evaluating the model $m$ with highest $p(m|c)$
for each configuration $c$ on the validation data. In this way, the number of
evaluations required depends only on the number of configurations even if many
models are considered. The number of configurations to evaluate may still
become prohibitive when using very deep models (such as ResNet50). In this
case, instead of evaluating all configurations, we can use $p(c,m)$ as a proxy
to select the correct model and $a_{c,m}$ to rank configurations and evaluate
only the top ranking on the entire validation set, and therefore reducing the
computation required to select the best model after training.

##  3 Experiments

In this section we perform several experiments and ablations in order to
evaluate the performance of our proposed approach. We first individually train
and evaluate the performance of a small ResNet with 36 different pooling
configurations on CIFAR10 and show that the optimal pooling can improve the
performance of the model. We also compare the correlation between different
configurations of a Mixture of SuperNets for various number of mixtures (M)
with the individually trained configurations and demonstrate that more models
help in obtaining a better correlation. Next, we present an ablation,
considering different variants of weight sharing for DARTS and Single Path
One-Shot (SPOS) approaches. Additionally, we compare our model with other NAS
and non-NAS approaches. Finally, we evaluate our model on a higher resolution
dataset (Food101), with a larger model (ResNet50). In all experiments, we
separate the training set of each dataset in $50\%$ for training and $50\%$
for validation, used for estimating the quality of the configurations.

###  3.1 Performance of individually trained Models

As shown in [3] the pooling configuration of a CNN has a large impact on the
performance of the model. To establish a benchmark we consider all possible
pooling configurations that satisfy conditions set in section 2.1 to avoid
useless configurations. With 2 pooling operations and 9 available pooling
locations, the search space size is combination ${9\choose 2}=36$. This
limited search space facilitates the exhaustive search of entire space and
allows us to find the true ranking by training independently all baseline
models. In other words, unlike [25, 26] benchmarks, we fully train all
architectures.

For this evaluation, we choose a lightweight ResNet configuration [11] and
exhaustively train each architecture 3 times with different seeds and report
the average result. The complete results on the entire space are included in
tab. 6 in appendix. The standard pooling configuration is configuration
[4,3,3], which has the first pooling layer after 4 ResNet block and the second
after other 3 blocks and its classification accuracy is $90.52\%\pm 0.6$. In
contrast, the best configuration is [6,1,2], with an accuracy of $92.01\%\pm
0.12$. This shows that even for one of the most common datasets, the pooling
structure is not optimal, and therefore it makes sense to propose models that
can optimize the CNN pooling configuration. We hope that this benchmark will
motivate researcher in the field to not overlook the importance of an optimal
pooling configuration. While this benchmark is relatively small, with only 36
feasible pooling configurations, we show in the next experiments that it is
quite challenging and most of the commonly used NAS methods fail to find a
good pooling configuration.

###  3.2 Balanced Mixture of SuperNets

We evaluate our proposed balanced mixture of SuperNets on our benchmark with
different numbers of models M=[1,2,4,8]. The case of M=1 is equivalent to SPOS
method with uniform sampling as in [19] with complete weight sharing among
architectures. In Fig.3, we show the correlation of the performance obtained
by our SuperNet trained with different number of mixture models, with true
accuracies of given pooling configuration models trained independently on test
set, and we calculate Kendall tau-rank correlation coefficient. As expected,
using multiple mixtures shows overall stronger correlation compared to SPOS
uniform sampling ($M=1$). This model has poor correlation with ground-truth
and is unable to find optimal configurations even in a limited search space.
The improvement is more prominent with higher ranking models, resulting in
finding better final configurations. For this experiment, for more than M=4
mixture models the gain in performance seems to saturate.

Figure 3: Evaluation accuracy vs. ground truth accuracy for CIFAR10 test
dataset for different number of mixtures (M). Each point represents the
performance of a given configuration of a model trained independently (Ground
truth - x axis) and the same configuration evaluated with the SuperNet
(Evaluation Accuracy - y axis) with different numbers of mixtures M (colors).
Rank correlation measured by Kendall’s tau increases with number of models.

###  3.3 Relaxing the full weight sharing

We argued that one reason that makes the learning of optimal pooling difficult
is the fact that the model weights are fully shared, i.e. the same weights are
used for all feature scales/resolutions. In this subsection we consider the
case of relaxing the weight sharing and using a different weights for each
resolution. For this experiment we evaluate SPOS and DARTS, in case of using
the same parameters for each feature map resolution (_Fully shared_) or
different (_Not shared_). For SPOS, we consider two different variants. The
first uses the 36 paths that are meaningful. However, we note that by using
only those 36 paths and different filters per resolutions would induce some
filters to be trained much more than others, which would bias the selection of
the optimal filters. To avoid that we also considered a case in which all
19,683 possible configurations are used. In this case the training takes
longer and has more noise. For DARTS, in the case in which each resolution has
different parameters (_Not shared_) we consider two variants, the case of
initializing filters with the same initialization for all resolutions (_same
init._) or different (_rnd init._). As tab. 1 shows, only our adaptive
association of pooling configurations and model parameters (_Balanced
Mixtures_) manage to obtain better results than the _Default_ pooling
configuration.

NAS Method | Mixtures(M) | Paths | Architecture | Accuracy
---|---|---|---|---
 _Default_ | 1 | 1 | [4,3,3] | $90.52\pm 0.1$
DARTS |  |  |  |
 _Fully shared_ | 1 | 19,638 | Fig. 4(a) | $89.23\pm 0.13$
 _Not shared - same init._ | 4 | 19,638 | Fig. 4(b) | $89.85\pm 0.18$
 _Not shared - rnd. init._ | 4 | 19,638 | Fig. 4(b) | $90.03\pm 0.21$
SPOS |  |  |  |
 _Fully shared_ | 1 | 36 | [3,3,4] | $90.61\pm 0.17$
 _Not shared_ | 4 | 36 | [4,2,4] | $90.34\pm 0.12$
 _Not shared_ | 4 | 19,683 | [4,2,4] | $90.34\pm 0.12$
 _Balanced Mixtures (Ours)_ | 4 | 36 | [5,3,2] | $\bf{91.55}\pm 0.08$
Table 1: CIFAR10 results for different search methods, number of model weights
and paths. For DARTS we consider a model with shared weights for different
feature map resolutions _Fully Shared_ and not shared with different weights
per resolution and different initialization. In all cases accuracy is lower
than the _Default_. For SPOS, we test _Fully Shared_ weights and not shared
with different weights per resolution and different number of paths. Results
are comparable to the default setting. Only our _Balanded Mixtures_ of
SuperNets clearly outperforms default.

###  3.4 Comparison with NAS-based methods

NAS Method | Architecture | Accuracy | Training (GPU hours)
---|---|---|---
DARTS + GAEA | Fig. 4(a) | $89.12\pm 0.1$ | 12
DARTS | Fig. 4(a) | $89.23\pm 0.08$ | 12
SBE + Unif. Smp. | [1,6,3] | $90.13\pm 0.06$ | 2.5
SPOS | [4,2,4] | $90.34\pm 0.12$ | 1.5
MCTS UCB | [4,2,4] | $90.34\pm 0.12$ | 2.5
SBE | [2,3,5] | $90.42\pm 0.08$ | 2
Default | [4,3,3] | $90.52\pm 0.10$ | -
MCTS UCB + Unif. Smp. | [4,4,2] | $90.85\pm 0.09$ | 2.5
Balanced Mixtures (Ours) | [5,3,2] | $\bf{91.55}\pm 0.08$ | 6
Best conf. (Bruteforce) | [7,1,2] | $92.01\pm 0.12$ | 98
Table 2: CIFAR10 found architectures, accuracies and training time for
different search methods. Results on DARTS are relaxed selections of
resolutions and therefore outside the search space we defined in our work.

We compare our method with several variants of commonly used NAS methods:
Differentiable architecure search (DARTS) [17], Monte-Carlo Tree Search (MCTS)
[25] and Boltzmann Softmax Exploration (BSE) [27, 28]. A detailed explanation
of these approaches is presented in Appendix C.

In tab.2, we present results in terms of found architecture and accuracy of
the selected configuration. Even if the number of possible configurations is
limited, none of the method manages to obtain the best pooling configuration,
which is 1.5 points above the default baseline. DARTS-based methods as they do
not have constraints on the pooling configurations, yield strange
configurations in which down-sampling if followed by up-sampling (see
Fig.4(a)) which brings a loss of information and therefore poor results. Other
methods based on SPOS, BSE and MCTS with different variants, obtain results
that are comparable close to default setting. Our method with M=4 models is
the only one that approaches the optimal performance, with an accuracy of
$91.55\%$.

(a) Fully shared

(b) Not shared

Figure 4: Final configurations found by DARTS [17]. The first layer in grey is
fixed at the maximum input resolution. 4(a) shared weights per layers. 4(b)
different weights per feature map resolution for each layer, weight are
initialized randomly or with same values.

###  3.5 Comparison with other methods

We compare our Balanced Mixture of SuperNets with other approaches that aim to
improve performance by learning the scale of the feature representation
through different algorithms not based on NAS search. In contrast to the other
experiments, here we present results provided directly by other papers. In
this case, we noticed that the final performance is highly affected by the
performance of the baseline model, which can vary depending on small and
difficult to control details. Thus, in order to make the comparison fairer,
results of the method (_Improved_) are presented with respect to the
corresponding _Baseline_ , so that we can consider not only the absolute
performance but also the relative _Gap_ with respect to the baseline. In tab.
3 we compare our results with DiffStride [3] on CIFAR10 with ResNet18 and
CIFAR100 with ResNet50. We also compare with DynOPool [6] and Shape Adaptor
[14] on CIFAR100 with ResNet50. In all experiment our approach performs
comparable to other methods that explicitly change and improve the pooling
layers.

Method | Dataset | Backbone | Baseline | Improved | Gap
---|---|---|---|---|---
DiffStride [3] | CIFAR10 | ResNet18 | $91.4\pm 0.2$ | $92.4\pm 0.1$ | 1.0
Balanced Mixtures (Ours) | CIFAR10 | ResNet18 | $90.45\pm 0.21$ | $91.51\pm 0.09$ | 1.06
DynOPool[6] | CIFAR100 | ResNet50 | 78.50 | 80.60 | 2.1
ShapeAdaptor[14] | CIFAR100 | ResNet50 | 78.50 | 80.29 | 1.8
Balanced Mixtures (Ours) | CIFAR100 | ResNet50 | $77.57\pm 0.18$ | $79.61\pm 0.21$ | 2.04
Table 3: Accuracy comparison between default, different methods that find
optimal feature map scale and our method on CIFAR10 and CIFAR100 for ResNet18
and ResNet50.

###  3.6 Larger Dataset and Model

Models | Best Arch. | Accuracy
---|---|---
Default | [3,4,6,3] | $84.00\pm 0.10$
M = 1 | [6,4,5,1] | $84.24\pm 0.09$
M = 2 | [4,5,6,1] | $84.34\pm 0.18$
M = 4 | [8,3,3,2] | $84.35\pm 0.14$
M = 8 | [9,4,2,1] | $84.73\pm 0.09$
Table 4: Resnet50 on Food101. We report best architectures, their accuracy
after retraining for different number of Mixtures (M) of our SuperNets.
Increasing M leads to an architecture with better accuracy.

To evaluate our method on new domains, we use fine-grained food classification
on Food101, which contains more images than CIFAR and at higher resolution. We
adapt a deeper ResNet network, ResNet50 and fix first layer and initial
downsampling in the architecture. By using a deeper network, the search space
size is increased to comb(3,15) = 455 architectures. We conduct our
experiments on input image resolution of 256. Food101 is a challenging fine-
grained object classification dataset that consists of 101 food categories
with 75,750/25250 training/test split. We show the results in tab. 4 The
results clearly show increased improvement in the optimal model. Food101 has
high intra-class variance, that does not show distinguishing spatial layout
and the classification would need to rely on colors, textures and local
information to distinguish them [29]. Architectures identified show a tendency
to adopt high resolution feature maps in early layers.

##  4 Conclusion

In this paper we presented the problem of learning the optimal scale for CNN
feature maps by learning pooling/stride configurations. We showed that current
NAS methods (single-path uniform sampling, differentiable methods and tree
search) are insufficient for this problem. We have established empirically the
importance of appropriate search space design by an extensive evaluation on
CIFAR10 and introduced a balanced mixture of SuperNets to alleviate the
weight-sharing poor ranking correlations for this problem. Finally we compared
our method with several non NAS-based approaches and evaluated it on a more
challenging dataset and larger models.

##  5 Broader Impact

Our approach requires a higher number of iterations needed to converge, due to
joint use of multiple models. However, the computational cost and memory
requirements of one iteration are not affected as for each minibatch we select
only one pooling configuration and one model. Also, we should consider that
even if the balanced mixtures approach can work for any NAS problem, we
evaluated it only for finding the optimal pooling configuration, because it is
the focus of this research. We leave a more general evaluation of the approach
to future work. One could argue that NAS in general are a waste of
computation, however, they help to avoid an even more expensive validation
search for the optimal hyper-parameters of the model.

##  6 Acknowledgement

This research was supported in part by Digital Research Alliance of Canada
(alliancecan.ca).

## References

  * [1] Gangming Zhao, Jingdong Wang, Zhaoxiang Zhang, et al.  Random shifting for cnn: a solution to reduce information loss in down-sampling layers.  In IJCAI, pages 3476–3482, 2017.
  * [2] Chen Jin, Ryutaro Tanno, Thomy Mertzanidou, Eleftheria Panagiotaki, and Daniel C Alexander.  Learning to downsample for segmentation of ultra-high resolution images.  arXiv preprint arXiv:2109.11071, 2021.
  * [3] Rachid Riad, Olivier Teboul, David Grangier, and Neil Zeghidour.  Learning strides in convolutional neural networks.  arXiv preprint arXiv:2202.01653, 2022.
  * [4] Hung Le and Ali Borji.  What are the receptive, effective receptive, and projective fields of neurons in convolutional neural networks?  arXiv preprint arXiv:1705.07049, 2017.
  * [5] Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel.  Understanding the effective receptive field in deep convolutional neural networks.  Advances in neural information processing systems, 29, 2016.
  * [6] Dong-Hwan Jang, Sanghyeok Chu, Joonhyuk Kim, and Bohyung Han.  Pooling revisited: Your receptive field is suboptimal.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 549–558, 2022.
  * [7] Mats L Richter and Christopher Pal.  Receptive field refinement for convolutional neural networks reliably improves predictive performance.  arXiv preprint arXiv:2211.14487, 2022.
  * [8] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  arXiv preprint arXiv:1704.04861, 2017.
  * [9] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [10] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1–9, 2015.
  * [11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [12] Zhengsu Chen, Lingxi Xie, Jianwei Niu, Xuefeng Liu, Longhui Wei, and Qi Tian.  Visformer: The vision-friendly transformer.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 589–598, 2021.
  * [13] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10012–10022, 2021.
  * [14] Shikun Liu, Zhe Lin, Yilin Wang, Jianming Zhang, Federico Perazzi, and Edward Johns.  Shape adaptor: A learnable resizing module.  In European Conference on Computer Vision, pages 661–677. Springer, 2020.
  * [15] David W Romero, Robert-Jan Bruintjes, Jakub M Tomczak, Erik J Bekkers, Mark Hoogendoorn, and Jan C van Gemert.  Flexconv: Continuous kernel convolutions with differentiable kernel sizes.  arXiv preprint arXiv:2110.08059, 2021.
  * [16] Silvia L Pintea, Nergis Tömen, Stanley F Goes, Marco Loog, and Jan C van Gemert.  Resolution learning in deep convolutional networks using scale-space theory.  IEEE Transactions on Image Processing, 30:8342–8353, 2021.
  * [17] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  arXiv preprint arXiv:1806.09055, 2018.
  * [18] Chao Xue, Xiaoxing Wang, Junchi Yan, Yonggang Hu, Xiaokang Yang, and Kewei Sun.  Rethinking bi-level optimization in neural architecture search: a gibbs sampling perspective.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10551–10559, 2021.
  * [19] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun.  Single path one-shot neural architecture search with uniform sampling.  In European conference on computer vision, pages 544–560. Springer, 2020.
  * [20] Liam Li and Ameet Talwalkar.  Random search and reproducibility for neural architecture search.  In Uncertainty in artificial intelligence, pages 367–377. PMLR, 2020.
  * [21] Dimitrios Stamoulis, Ruizhou Ding, Di Wang, Dimitrios Lymberopoulos, Bodhi Priyantha, Jie Liu, and Diana Marculescu.  Single-path nas: Designing hardware-efficient convnets in less than 4 hours.  In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part II, pages 481–497. Springer, 2020.
  * [22] Xin He, Kaiyong Zhao, and Xiaowen Chu.  Automl: A survey of the state-of-the-art.  Knowledge-Based Systems, 212:106622, 2021.
  * [23] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang.  A comprehensive survey of neural architecture search: Challenges and solutions.  ACM Computing Surveys (CSUR), 54(4):1–34, 2021.
  * [24] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin.  Snas: stochastic neural architecture search.  arXiv preprint arXiv:1812.09926, 2018.
  * [25] Xiu Su, Tao Huang, Yanxi Li, Shan You, Fei Wang, Chen Qian, Changshui Zhang, and Chang Xu.  Prioritized architecture sampling with monto-carlo tree search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10968–10977, 2021.
  * [26] Thomas Chun Pong Chau, Łukasz Dudziak, Hongkai Wen, Nicholas Donald Lane, and Mohamed S Abdelfattah.  Blox: Macro neural architecture search benchmark and algorithms.  arXiv preprint arXiv:2210.07271, 2022.
  * [27] Kavosh Asadi and Michael L Littman.  An alternative softmax operator for reinforcement learning.  In International Conference on Machine Learning, pages 243–252. PMLR, 2017.
  * [28] Nicolò Cesa-Bianchi, Claudio Gentile, Gábor Lugosi, and Gergely Neu.  Boltzmann exploration done right.  Advances in neural information processing systems, 30, 2017.
  * [29] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool.  Food-101–mining discriminative components with random forests.  In Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part VI 13, pages 446–461. Springer, 2014.
  * [30] Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  arXiv preprint arXiv:1611.01578, 2016.
  * [31] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697–8710, 2018.
  * [32] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy.  Progressive neural architecture search.  In Proceedings of the European conference on computer vision (ECCV), pages 19–34, 2018.
  * [33] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In Proceedings of the aaai conference on artificial intelligence, volume 33, pages 4780–4789, 2019.
  * [34] Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu.  Practical block-wise neural network architecture generation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2423–2432, 2018.
  * [35] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter.  Nas-bench-101: Towards reproducible neural architecture search.  In International Conference on Machine Learning, pages 7105–7114. PMLR, 2019.
  * [36] Xuanyi Dong and Yi Yang.  Nas-bench-201: Extending the scope of reproducible neural architecture search.  arXiv preprint arXiv:2001.00326, 2020.
  * [37] Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter.  Nas-bench-301 and the case for surrogate benchmarks for neural architecture search.  arXiv preprint arXiv:2008.09777, 2020.
  * [38] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean.  Efficient neural architecture search via parameters sharing.  In International conference on machine learning, pages 4095–4104. PMLR, 2018.
  * [39] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar.  Designing neural network architectures using reinforcement learning.  arXiv preprint arXiv:1611.02167, 2016.
  * [40] Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang.  Efficient architecture search by network transformation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * [41] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter.  Efficient multi-objective neural architecture search via lamarckian evolution.  arXiv preprint arXiv:1804.09081, 2018.
  * [42] Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf.  Nsga-net: neural architecture search using multi-objective genetic algorithm.  In Proceedings of the genetic and evolutionary computation conference, pages 419–427, 2019.
  * [43] Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc V Le, and Alexey Kurakin.  Large-scale evolution of image classifiers.  In International Conference on Machine Learning, pages 2902–2911. PMLR, 2017.
  * [44] Vasco Lopes and Luís A Alexandre.  Towards less constrained macro-neural architecture search.  arXiv preprint arXiv:2203.05508, 2022.
  * [45] Lingxi Xie and Alan Yuille.  Genetic cnn.  In Proceedings of the IEEE international conference on computer vision, pages 1379–1388, 2017.
  * [46] Hanzhang Hu, John Langford, Rich Caruana, Saurajit Mukherjee, Eric J Horvitz, and Debadeepta Dey.  Efficient forward architecture search.  Advances in Neural Information Processing Systems, 32, 2019.
  * [47] Hanzhang Hu, John Langford, Rich Caruana, Eric Horvitz, and Debadeepta Dey.  Macro neural architecture search revisited.  In 2nd Workshop on Meta-Learning at NeurIPS, 2018.
  * [48] Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian.  Progressive differentiable architecture search: Bridging the depth gap between search and evaluation.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 1294–1303, 2019.
  * [49] Shan You, Tao Huang, Mingmin Yang, Fei Wang, Chen Qian, and Changshui Zhang.  Greedynas: Towards fast one-shot nas with greedy supernet.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1999–2008, 2020.
  * [50] Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem.  Sgas: Sequential greedy architecture search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1620–1630, 2020.
  * [51] Xin Xia, Xuefeng Xiao, Xing Wang, and Min Zheng.  Progressive automatic design of search space for one-shot neural architecture search.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 2455–2464, 2022.
  * [52] 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/CVF conference on computer vision and pattern recognition, pages 10628–10637, 2020.
  * [53] Guocheng Qian, Xuanyang Zhang, Guohao Li, Chen Zhao, Yukang Chen, Xiangyu Zhang, Bernard Ghanem, and Jian Sun.  When nas meets trees: An efficient algorithm for neural architecture search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2782–2787, 2022.
  * [54] Stephen Cha, Taehyeon Kim, Hayeon Lee, and Se-Young Yun.  Supernet in neural architecture search: A taxonomic survey.  arXiv preprint arXiv:2204.03916, 2022.
  * [55] Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsieh.  Rethinking architecture selection in differentiable nas.  arXiv preprint arXiv:2108.04392, 2021.
  * [56] Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann.  Evaluating the search phase of neural architecture search.  arXiv preprint arXiv:1902.08142, 2019.
  * [57] Yuan Zhou, Xukai Xie, and Sun-Yuan Kung.  Exploiting operation importance for differentiable neural architecture search.  IEEE Transactions on Neural Networks and Learning Systems, 2021\.
  * [58] Xiangning Chen and Cho-Jui Hsieh.  Stabilizing differentiable architecture search via perturbation-based regularization.  In International conference on machine learning, pages 1554–1565. PMLR, 2020.
  * [59] Thomas Elsken Arber Zela, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter.  Understanding and robustifying differentiable architecture search.  In International Conference on Learning Representations, volume 2, 2020.
  * [60] Miao Zhang, Steven W Su, Shirui Pan, Xiaojun Chang, Ehsan M Abbasnejad, and Reza Haffari.  idarts: Differentiable architecture search with stochastic implicit gradients.  In International Conference on Machine Learning, pages 12557–12566. PMLR, 2021.
  * [61] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le.  Understanding and simplifying one-shot architecture search.  In International conference on machine learning, pages 550–559. PMLR, 2018.
  * [62] Yiyang Zhao, Linnan Wang, Yuandong Tian, Rodrigo Fonseca, and Tian Guo.  Few-shot neural architecture search.  In International Conference on Machine Learning, pages 12707–12718. PMLR, 2021.
  * [63] Xiu Su, Shan You, Mingkai Zheng, Fei Wang, Chen Qian, Changshui Zhang, and Chang Xu.  K-shot nas: Learnable weight-sharing for nas with k-shot supernets.  In International Conference on Machine Learning, pages 9880–9890. PMLR, 2021.
  * [64] Shoukang Hu, Ruochen Wang, Lanqing Hong, Zhenguo Li, Cho-Jui Hsieh, and Jiashi Feng.  Generalizing few-shot nas with gradient matching.  arXiv preprint arXiv:2203.15207, 2022.
  * [65] Jiawei Liu, Kaiyu Zhang, Weitai Hu, and Qing Yang.  Improve ranking correlation of super-net through training scheme from one-shot nas to few-shot nas.  arXiv preprint arXiv:2206.05896, 2022.
  * [66] Guillaume Leclerc, Andrew Ilyas, Logan Engstrom, Sung Min Park, Hadi Salman, and Aleksander Madry.  FFCV: Accelerating training by removing data bottlenecks.  https://github.com/libffcv/ffcv/, 2022.  commit xxxxxxx.
  * [67] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [68] Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar.  Geometry-aware gradient algorithms for neural architecture search.  arXiv preprint arXiv:2004.07802, 2020.
  * [69] Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca.  Neural architecture search using deep neural networks and monte carlo tree search.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 9983–9991, 2020.
  * [70] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.

##  Appendix A Related Work

Optimal Scale for CNN Feature Maps Some recent work have addressed the
optimization of feature map scales in CNN design by adapting dynamic kernel
shapes [15, 16], learning resizing modules [14, 3, 6] or receptive field
analysis [7]. Feature map sizes as well as receptive field are controlled by
kernel sizes, and number and position of down-sampling layers in a CNN.

Among the works that indirectly learn feature map scales by learning kernel
sizes, N-Jet [16] uses Gaussian derivative filters to dynamically adapt kernel
size during training, using scale space theory and employs a safe-sub-sampling
alternative. Flexconv [15] learns long range dependencies without using
pooling and replaces them with multiplication of continuous kernels and a
Gaussian mask and learns the parameters of the mask. However, these methods
often struggle with large kernel sizes[16] or use uses several techniques such
as Fourier transformation and training on down-sampled images to reduce the
cost [15].

Another work introduces a resizing module, ShapeAdaptor [14] that learns the
scale and mixing weight of linear combination of two feature map sizes in
differentiable manner. However, the number of shape adaptor modules is a fixed
hyperparameter that limits the placement of down-sampling layers, and the
framework only works with max-pooling operations. DiffStride [3] proposes a
down-sampling layer with learnable fractional strides by casting down-sampling
in spatial domain as cropping in frequency domain and show that on CIFAR10 and
CIFAR100 dataset with ResNet18, lower layers tend to preserve more details
while the pooling is performed more aggressively at later layers. However, the
placement of down-sampling layers remains fixed and the pooling is performed
in spectral domain resulting in higher cost and involving complex valued
operations that are not optimized on GPU. DynOPool [6] relaxes the problem by
using bi-linear interpolation to allow for non integer feature map sizes and
learns the resizing scale in differentiable manner. In these models, learning
the resizing factor and network weights are performed simultaneously on
training set, which can render the optimization hard and introduce bias
towards non-optimal solutions [22]. Furthermore, these approaches are outside
the NAS framework often cannot easily find a single architecture and might
introduce additional costs at run-time.

Macro Search in NAS While early NAS works focused on a global search space
[30], containing both micro and macro search space, the complexity of the
search space contributed to their great computational cost. NASNet [31]
proposed a cell-based search space, reducing the search space size from the
entire network to only a set of operations in cells with many recent works
[17, 32, 33, 34, 35, 36, 37] using cell-based search spaces due to its
efficiency.

In terms of search strategy [30, 38, 39, 40] use reinforcement learning, while
[41, 42, 43, 44, 45] use evolutionary algorithms (EA) and [46, 47] use random
search to perform macro search. Several of the early works [39, 30, 43]
however, required hundreds of GPUdays to perform the search. To navigate the
huge search space, progressive NAS methods [32, 48] were proposed that
progressively add layers to the a shallow network, while [49, 50] drop
unpromising architectures progressively. Among works that perform NAS on the
entire network, MCTS [25] uses Monte-Carlo tree search algorithm to establish
a benchmark in MobileNetV2 search space. While, this model is not cell-base,
the feature map sizes and downasmpling locations are still fixed. Some of
these works [25, 51] search on all layers of a CNN, however they still use a
fixed template for the CNN’s outer-skeleton.

DenseNAS [52] proposes a densely connected search space by designing routing
blocks. The routing blocks contain shape alignment layers that perform
convolutions on different shaped inputs (channels and spatial dimension) and
are the sum of the results. Both, basic blocks (containing operations) and
routing blocks are relaxed and perform a gradient based optimization of mixing
weights. Several blocks at the same resolution are searched as well as number
of channels per layer. The position to downsampling is determined along with
the block count search.

TNAS [53] factorizes the space in a hierarchical manner by designing an
operation space (by a binary operation tree), and architecture layers (by a
architecture tree) and performs a bilevel search on both trees. LCMNAS [44]
autonomously generates search spaces by creating weighted directed graphs with
hidden properties from existing architectures and performs search using EA and
evaluation using a performance predictor. Compared to these approaches, ours
is more general, the models are specialized automatitically and does not
require prior knowledge about search space.

Weight Sharing in NAS The problem of how to efficiently evaluating candidate
architectures has been a bottleneck of NAS research [23, 54]. Training each
candidate architecture from scratch to convergence provides the true
performance of the architecture, however that was one of the reasons for
significant cost of early NAS methods [39, 30, 43, 45]. A great improvement in
this regard was using weight sharing [38] among architectures in one-shot
methods, where the search space is defined as an oveparametrized SuperNet,
from which every possible architecture can be derived. After training the
SuperNet, the candidate architectures are evaluated without any additional
training by inheriting the weights from the SuperNet. One of the most
influential works that is based on SuperNet training is DARTS [17], which
relaxed the discrete search space of NAS, and enabled using backpropagation to
jointly learn SuperNet weights and architecture parameters. However, several
works show that the architecture parameters fail to reflect the importance of
them [55, 56, 57] as well as facing challenges in generalizing [48, 50, 24,
56] and stability [58, 55, 59, 60] and high memory requirements to perform
backward pass through all configurations. Poor rank correlation is the result
of coupling between the architecture and network weights as well as coupling
of weights among architectures. Training architecture weights simultaneously
results in introducing bias by favoring certain architectures during training.
These weights can be decoupled by uniform sampling and single path methods
[19], which has been shown to outperform training a SuperNet as a whole as in
DARTS. One direction to reduce one-shot methods suffer from poor rank
correlation [56] and performance degradation due to the co-adaptation of
weights among architectures [61], is reducing the amount of weight shared
among architectures.

Among works that directly reduce weight sharing, few-shot NAS [62, 63] was
proposed to partition SuperNet to multiple sub-SuperNets. The split is
performed by random selection of an edge in SuperNet and dividing all
operation on that edged into sub-SuperNets. While this setup reduces weight
sharing and improves the performance over one-shot methods, the partitioning
criteria is inefficient as it fails to identify similar and dissimilar models
and whether the partitioning of specific regions results in any meaningful
gain. To address this issue, [64] address these issues by proposing a gradient
matching score that decides which candidate network should share weights,
while [65] propose a gradual training from one-shot to few-shot NAS. However,
these works focus on finding operations in a micro-search space, the SuperNet
partitioning is not automatic [62], and focus on NAS benchmarks that are not
applicable to the specific application addressed in this work.

##  Appendix B Experimental Setup and Details

###  B.1 Datasets and Hyperparameters

All datasets in our experiments were split 50/50 for NAS training and
validation. Unless otherwise specified, all experiments were run 3 times with
random seeds and average and standard deviations are reported. For ResNet18
and Resnet50 tests we use mixed-precision operations and FFCV [66] library to
increase training efficiency.

We tuned the hyperparameters either by grid search for our experiments or when
compared with other work, used similar hyperparameters. We used SGD with
learning rate scheduling and weight decay for all our experiments. For
ResNet20 we used learing rate of 0.1 with cosine annealing and weight decay
1e-3 and batch size 256. For DARTS experiments, we used Adam for architecture
parameters with learning rate 1e-2. For our Balance Mixture of SuperNets, the
number of training epochs is set proportional to number of models to ensure
sufficient training. Furthermore, we initialize $\tau=1$ and decrease it
linearly during the training with minimum value of $1/(100M)$ with $M$ the
number of models. For experiments on CIFAR10 and CIFAR100 with ResNet18, we
train for 400 epochs, with learning rate of 0.1 and reduced it by factor of
0.1 on epochs [200,300] and weight decay of 5e-3. For ResNet50 experiments on
CIFAR100 we trained for 250 epochs and changed the scheduling to reducing by
factor 0.2 at epochs [60,120,160]. For Food101 we used learning rate of 0.1,
cosine annealing and batch size 256.

###  B.2 Search Space Details

Summary of search space design for the experimetns is provided in tab. 5.
ResNet20 [11] architecture consists of one convolutional layer followed by 9
ResNet layers. The original structure consists of [32, 16, 8] feature map
sizes and [16, 32, 64] number of filters respectively, with [3,3,3] blocks per
resolution. In our implementation, fully connected layer is removed and
strided convolutions are replaced by maxpooling.

Backbone | Dataset | Searched feature map sizes | no. searched layers | no. pooling | Search Space Size
---|---|---|---|---|---
ResNet20 | CIFAR10 | [32,16,8] | 10 | 2 | 36
ResNet18 | CIFAR10 | [32,16,8,4] | 9 | 3 | 56
ResNet50 | CIFAR100 | [32,16,8,4] | 17 | 3 | 560
ResNet50 | Food101 | [56,28,14,7] | 16 | 3 | 455
ResNet18 | ImageNet | [56,28,14,7] | 8 | 3 | 35
Table 5: Search space design for experiments conducted in paper. We consider
the same number of downsampling operations as a default network (no. pooling)
and exclude from the search space the first pooling layer as the it
corresponds to a manipulation of the input image. For larger input images
(ImageNet and Food101), we keep the first layer (conv and maxpooling)
predefined for computational efficiency and only search the pooling locations
among layers after the predefined maxpooling layers. The search space size is
then the combination ${Layers-1\choose pooling}$

##  Appendix C Comparison With Other NAS Methods (Details)

DARTS: Differentiable approaches first proposed by DARTS [17] has been
commonly used in recent years for NAS problems. As one of the most efficient
and reliable NAS methods, we utilize DARTS for our problem. In terms of
optimization, we use the same differentiable principle for architecture search
as DARTS [17]. Instead of learning weights for different networks branches, we
learn weights for different feature map resolutions by learning associated
architecture parameter $\alpha$. Since changing the position of the pooling
layer in the network changes the size of a feature map and therefore it
invalidates all the subsequent blocks, we need to find a way to achieve this
without without changing the feature map resolution. Therefore, we introduce a
multi-resolution block $M$ defined as the weighted combination of convolutions
$V$ at different resolutions $r$ of the same filters $f_{l}$ at a given layer
$l$:

$\begin{split}h_{l+1}(x,y)&=\mathbf{M}(h_{l}(x,y))\\\
&=\sum_{r=1}^{R}\alpha_{l,r}\mathbf{U}_{2^{r}}(\mathbf{V}(\mathbf{S}_{2^{r}}(h_{l}(x,y)),f_{l}(h,w))).\end{split}$
(4)

The resulting feature map is the sum of the feature map at each resolution
multiplied by a coefficient $\alpha_{l,r}$ and rescaled to the initial feature
map resolution $(x,y)$ resolution with an upsampling operation $\mathbf{U}$.

The normalized coefficient $\alpha_{l,r}$ learns the relative strength of a
certain resolution with respect to the others for a given layer $l$ and is
computed as a softmax over feature map resolutions:

$\alpha_{l,r}=\frac{\exp(\alpha_{l,r})}{\sum_{s}\exp(\alpha_{l,s})}.$ (5)

This approach allows us to train a model that can learn the convolutional
filters, but at the same time, with a marginal increase in computation and
memory can also learn the best feature resolution to use at each layer.

To make the search space as similar to out method as possible we manually
select highest resolution for first layer of the network, however imposing
further restrictions on the search space is more difficult. At the end of
training we select maximum ${\alpha}_{l,r}$ for each layer as final
architecture to retrain. We used ADAM [67] optimizer to train $\alpha$ and SGD
with cosine learning rate for CNN weights. Furthermore, We used another
standard optimizer and GAEA[68] which both fail on this task as it finds sub-
optimal architectures. As seen in section 3.5, the architectures found by this
approach are atypical for classification task as they utilize upsampling in
several later layers, resulting in lower accuracy of final architecture.

Monte-Carlo Tree Search: Several recent works [25, 69] have used MCTS for NAS
problem both in training and search stage of NAS. As MCT captures dependencies
amongst layers [25], it is viable candidate for our task. We designed the same
search space as 2.1 as a binary tree. Each layer $l$ of CNN correspond to
generations of tree, at each layer maximum of two nodes exist, 1) same
resolution and 2) downampling . By fixing the leaf nodes at minimum resolution
and first layer at highest resolution, we design an asymmetric tree with 36
leaves.

To balance exploration and exploitation we use Upper Confidence Bound (UCB) to
calculate sampling probabilities as:

$UCB(r_{i}^{l})=\frac{a(r_{i}^{l})}{n_{i}^{l}}+c\sqrt{\frac{log(n_{p}^{l-1})}{n_{i}^{l}}}$
(6)

Where $p$ corresponds to the parent node and $a$ is the reward and $c$ is a
hyperparameter constant controlling the trade-off. In our experiments we use
validation accuracy on minibatches as reward.

We considered two settings: sampling with UCB from the beginning and sampling
with a uniform warm-up. By using UCB it is expected that training will focus
more on better performing architectures compared to uniform sampling,
therefore improving the ranking of top architectures. At the end of the
training phase we evaluate the found architecture by on validation set.
Results in tab. 2 shows MCT finds sub-optimal architecture in both cases.

Boltzmann Softmax Exploration (BSE): BSE is one of the simplest reinforcement
learning exploration strategies. For sampling an architecture $c$ we use:

$p(c)=Softmax(\tau\leavevmode\nobreak\ a_{c})$ (7)

Where $p(c)$ is the probability of selecting architecture $c$, and $a_{c}$ is
the reward (here the validation accuracy) and $\tau$ is the inverse
temperature, controlling exploration and exploitation. We increase $\tau$ from
1 linearly during the experiment.

With the defined search space of 36 architectures, we choose a linear schedule
for the inverse temperature that balances exploration and exploitation.
Furthermore we considered another option with a uniform warm-up. However, the
appropriate scheduling is difficult as the model can either continue to
explore sup-optimal solutions or commit to one solution too early [28].

##  Appendix D Comparison With Other Methods (Details)

###  D.1 Comparison With DiffStride, DynOPool and ShapeAdaptor

To compare with DiffStride [3] we ResNet18 architecture where original
structure consists of 8 blocks With 4 resolutions as [2,2,2,2], resulting in
the search space of 56 configurations.

To compare with DynOPool [6] and Shape Adaptor [14] we used ResNet50. Since
ResNet50 for CIFAR does not include initial downsampling layers, the search
space consist of 560 configurations with default configuration of [4,4,6,3].
It should be noted that the search space of these methods are not identical
with ours.

no. | Architecture | Accuracy | no. | Architecture | Accuracy
---|---|---|---|---|---
1 | [ 1 , 1 , 8 ] | $87.45\pm 0.06$ | 19 | [ 3 , 4 , 3 ] | $90.92\pm 0.1$
2 | [ 1 , 2 , 7 ] | $87.69\pm 0.08$ | 20 | [ 3 , 5 , 2 ] | $90.88\pm 0.08$
3 | [ 1 , 3 , 6 ] | $87.89\pm 0.17$ | 21 | [ 3 , 6 , 1 ] | $90.14\pm 0.16$
4 | [ 1 , 4 , 5 ] | $88.6\pm 0.15$ | 22 | [ 4 , 1 , 5 ] | $89.68\pm 0.14$
5 | [ 1 , 5 , 4 ] | $89.38\pm 0.07$ | 23 | [ 4 , 2 , 4 ] | $90.34\pm 0.13$
6 | [ 1 , 6 , 3 ] | $90.13\pm 0.14$ | 24 | [ 4 , 3 , 3 ] | $90.52\pm 0.15$
7 | [ 1 , 7 , 2 ] | $90.16\pm 0.1$ | 25 | [ 4 , 4 , 2 ] | $90.85\pm 0.12$
8 | [ 1 , 8 , 1 ] | $89.41\pm 0.15$ | 26 | [ 4 , 5 , 1 ] | $89.71\pm 0.16$
9 | [ 2 , 1 , 7 ] | $88.78\pm 0.1$ | 27 | [ 5 , 1 , 4 ] | $91.05\pm 0.15$
10 | [ 2 , 2 , 6 ] | $89.03\pm 0.12$ | 28 | [ 5 , 2 , 3 ] | $90.96\pm 0.15$
11 | [ 2 , 3 , 5 ] | $90.42\pm 0.1$ | 29 | [ 5 , 3 , 2 ] | $91.55\pm 0.09$
12 | [ 2 , 4 , 4 ] | $90.57\pm 0.11$ | 30 | [ 5 , 4 , 1 ] | $89.84\pm 0.08$
13 | [ 2 , 5 , 3 ] | $90.89\pm 0.07$ | 31 | [ 6 , 1 , 3 ] | $91.78\pm 0.11$
14 | [ 2 , 6 , 2 ] | $91.01\pm 0.13$ | 32 | [ 6 , 2 , 2 ] | $91.83\pm 0.13$
15 | [ 2 , 7 , 1 ] | $90.22\pm 0.18$ | 33 | [ 6 , 3 , 1 ] | $90.96\pm 0.12$
16 | [ 3 , 1 , 6 ] | $89.1\pm 0.06$ | 34 | [ 7 , 1 , 2 ] | $92.01\pm 0.18$
17 | [ 3 , 2 , 5 ] | $89.7\pm 0.1$ | 35 | [ 7 , 2 , 1 ] | $90.47\pm 0.11$
18 | [ 3 , 3 , 4 ] | $90.61\pm 0.17$ | 36 | [ 8 , 1 , 1 ] | $89.99\pm 0.12$
Table 6: CIFAR10 accuracies for all configurations with ResNet20 Backbone.
Architectures are displayed in terms of number of blocks associates with
feature map sizes of [32, 16, 8]. Architecture 24 is the original ResNet20
architecture pooling configuration.

##  Appendix E Extended Results

In tab. 6 we present ground truth accuracy of all configurations in our
searrch space for ResNet20, as described in 3.1. In figure 5 we show the
progress of $p(m|c)$ for our method described in 2.3.

Figure 5: Progress of $p(c|m)$ during training for a mixture of M=4 SuperNets
and 36 pooling configurations. As temperature $\tau$ in equation 3 is linearly
decreased, the distribution transitions from uniform (left) to concentrated
(right).

###  E.1 Experiment on ImageNet [70]

We used ResNet18 architecture as backbone for ImageNet dataset. We trained the
top-1 and top-3 best architectures found by our method with (N=1,2,4,8) for
100 epochs and report mean and std on 3 runs in tab. 7. We note that the
baseline is the superior architecture among the trained architecture and

Nevertheless, using our method with M=2, we were able to recover the default
architecture. We hypothesise that the reason for default architecture having
the best performance is that current ResNet architecture is highly optimized
for ImageNet dataset.

Models | top-1 Arch. | top-1 | top-3 Best | top-3 average
---|---|---|---|---
Default | [2,2,2,2] | $68.32\pm 0.24$ | NA | NA
M = 1 | [1,3,1,3] | $62.21\pm 0.26$ | $65.91\pm 0.21$ | $63.51\pm 1.56$
M = 2 | [3,1,1,3] | $62.56\pm 0.18$ | ${68.32\pm 0.24}$ | $64.70\pm 2.57$
M = 4 | [5,1,1,1] | $65.88\pm 0.24$ | $66.12\pm 0.18$ | $64.73\pm 1.78$
M = 8 | [2,3,2,1] | $64.81\pm 0.11$ | $66.12\pm 0.23$ | $64.15\pm 2.98$
Table 7: Resnet18 on ImageNet. We report best architectures, their accuracy
after retraining for different number of Mixtures (M) of our SuperNets. As the
ranking is noisy, we retrained the best 3 architectures based on our ranking
and report top-1 and top-3 accuracies.