# Training BatchNorm Only in Neural Architecture Search and Beyond

Yichen Zhu1222Equal contribution., Jie Du1,2222Equal contribution. , Yuqin
Zhu1, Yi Wang1, Zhicai Ou1, Feifei Feng1 and Jian Tang1444Corresponding
author.
1Midea Group, AI Innovation Center
2Tongji University

###### Abstract

This work investigates the usage of batch normalization in neural architecture
search (NAS). Specifically, Frankle et al. [22] find that training BatchNorm
only can achieve non-trivial performance. Furthermore, Chen et al. [9] claim
that training BatchNorm only can speed up the training of the one-shot NAS
supernet over ten times. Critically, there is no effort to understand 1) why
training BatchNorm only can find the perform-well architectures with the
reduced supernet-training time, and 2) what is the difference between the
train-BN-only supernet and the standard-train supernet.

We begin by showing that the train-BN-only networks converge to the neural
tangent kernel regime, obtain the same training dynamics as train all
parameters theoretically. Our proof supports the claim to train BatchNorm only
on supernet with less training time. Then, we empirically disclose that train-
BN-only supernet provides an advantage on convolutions over other operators,
cause unfair competition between architectures. This is due to only the
convolution operator being attached with BatchNorm. Through experiments, we
show that such unfairness makes the search algorithm prone to select models
with convolutions. To solve this issue, we introduce fairness in the search
space by placing a BatchNorm layer on every operator. However, we observe that
the performance predictor in Chen et al. is inapplicable on the new search
space. To this end, we propose a novel composite performance indicator to
evaluate networks from three perspectives: expressivity, trainability, and
uncertainty, derived from the theoretical property of BatchNorm. We
demonstrate the effectiveness of our approach on multiple NAS-benchmarks (NAS-
Bench-101, NAS-Bench-201) and search spaces (DARTS search space and MobileNet
search space).

##  1 Introduction

The big leap of convolutional neural networks (CNNs) starts from ResNet [27]
and batch normalization [33]. It was initially considered as a technique to
reduce internal covariance shift; however, recent works prove that it could
smooth the loss landscape [56], stabilize the training process [6, 74],
preserve rank stability under certain assumption [16]. Though some studies
show that BatchNorm may be the cause of gradient explosion in CNNs [77], there
are irreplaceable advantages of utilizing BatchNorm in CNNs.

Nevertheless, BatchNorm111For notation simplicity, we use both BatchNorm and
BN interchangeably to represent the batch normalization layers. is problematic
in Neural Architecture Search (NAS) due to inaccurate batch statistics across
sub-networks [19], the small batch size on downstream tasks [11]. Existing
works solve these issues by finetuning [25, 13], fixing the learnable
parameters, replacing with ghost batch normalization [4, 29]/group
normalization [73, 66], or removing entirely from training [75].

Train-BN-only222In our context, train BatchNorm only means to fix all
parameters at their initialization states, and update the parameters of
BatchNorm during training. NAS. Frankle et al. [22] was the first study to
empirically show a CNN that is trained with BatchNorm only can achieve
apparently non-random performance on multiple image classification datasets,
including ImageNet. Later works explore the train-BN-only networks on feature
orthogonality at deep layers [15] and influence on transfer learning [36].
Recently, Chen et al. [9] proposed to speed up the supernet training over ten
times by training the BatchNorm only and achieve comparable results on a
modified MobileNet search space than state-of-the-art one-shot NAS algorithms.

This breakthrough shows the great potential of BatchNorm in NAS; meanwhile, it
highlights two central questions: 1) Can we reduce the training time if only
BatchNorm is trained? Intuitively, without updating the parameters in the
networks other than BatchNorm requires less training time. However, unlike the
conventional image classification task as in Frankle et al. [22], it is
crucial to preserve the rank consistency between various architectures in the
supernet if the train-BN-only strategy can be successfully applied to NAS.
Therefore, understanding the training dynamics [71], which reflects the
optimization process of training neural networks and articulates models’
generalization ability of train-BN-only networks, is essential. In this work,
we demonstrate that, under certain conditions, the train-BN-only networks
converge to the fixed neural tangent kernel regime [80, 35]. It reveals that
the train-BN-only networks obtain the same training dynamic as networks train
all parameters, which partially indicates BN-NAS’s success in the NAS domain
and supports the method to train BatchNorm only in NAS.

It comes up with the second question, 2) What is the difference between train-
BN-only supernet and standard-train supernet? Typically, only the convolutions
are attached with a BatchNorm. This is problematic since many predefined
search spaces in NAS contain multiple operators other than convolutions (i.e.,
pooling, identity, etc.). These operators do not have a BatchNorm layer
follow-up. In this paper, we disclose an unfair competition between
architectures that are triggered by train-BN-only strategy. Because the
BatchNorm has learnable parameters, an unfair advantage is established for the
convolution operator (Detailed experiments are in §3.2).

To remedy the unfairness, we place a BatchNorm layer after every operator,
such that all architectures get the same chance to compete on the stage.
Nevertheless, we empirically find that the previously effective performance
predictor, gamma value [9] in BatchNorm, is no longer available after we bring
BN fairness into the search space. Therefore, we need to design a new
performance predictor that can efficiently and effectively evaluate the
networks. As aforementioned, the BatchNorm brings many theoretically sound
properties into the CNNs; thus, we leverage these properties to present a
BatchNorm-based, theoretically-inspired composite performance predictor, which
decomposes the generalization of neural networks to three perspectives:
expressivity, trainability, and uncertainty. Notably, although the prior two
properties have been discussed in training-free NAS, this is the first time in
the literature to leverage BatchNorm to evaluate these two properties of
networks in NAS. Moreover, to the best of our knowledge, the relationship
between performance and model uncertainty has not been studied before. Our
composite performance predictor shows a statistically significant correlation
with model accuracy, verified on NAS-Bench-201. It helps our method find
better and faster architecture in the search space than BN-NAS, while the
training cost is further reduced. In Figure 1, we demonstrate the overview of
our approach and compare it to the previous one-shot NAS. We also show that
our method enables faster supernet training and searches for more efficient
and powerful models in various search spaces.

Figure 1: The comparison of FBN-NAS with BN-NAS and conventional one-shot NAS.
Our approach use a new search space, and leverage theoretically inspired
properties of BatchNorm as performance indicator. Best view in color.

In summary, our contributions are the following:

  * •

We theoretically prove that train-BN-only networks obtain the same training
dynamic as training regular networks from the perspective of the neural
tangent kernel. Our proof lay the foundation of applying the train BatchNorm
only strategy to NAS.

  * •

We empirically identify an unfair competition between architectures that is
the consequence of the train-BN-only strategy. Therefore, we propose to insert
BN after every operator to fix the issue.

  * •

Our work is the first to leverage BatchNorm’s theoretical property as the
performance indicator to NAS. To the best of our knowledge, it is also the
first time to link network performance with model uncertainty.

##  2 Related Works

Batch Normalization. Though many normalization methods [73, 2] have been
proposed in the last few years, batch normalization [33] still dominates the
CNNs. It was initially considered as a technique to reduce internal covariance
shift [33]; however, recent works prove that it could smooth the loss
landscape [56], stabilize the training process [6, 74], and preserve rank
stability under certain assumption [16]. BatchNorm can also be used to measure
the model uncertainty [62]. [22] have found out that training BatchNorm only
while fixing the convolutional layers at the initial state can also achieve
performance that is much better from random guess.

Neural Architecture Search. The over-parameterizated neural networks have
demonstrate strong generalization ability on various tasks yet hard to deploy
on embedding devices, thus, many techniques have been proposed to accelerate
the model inferences, including pruning [26, 21], knowledge distillation [24,
28, 82], quantization [49]. Neural architecture search (NAS), one of the most
popular model compression techniques, has been extensively studied in the last
few years. The initial techniques focused on reinforcement learning [83, 48]
and evolutionary search [44, 48], one-shot NAS algorithms [4] and predictor-
based NAS algorithms [57, 65, 68]. However, these NAS methods are not
practical due to their extremely long training and search times. Many
researchers have redirected their interest in designing efficient and reliable
NAS algorithms. Among them, weight-sharing is the most popular and promising
technique. Given a pre-defined search space, the weight-sharing approach
constructs a supernet that consists of all potential models. Conventional one-
shot weight-sharing approaches [18, 25, 13] first train a supernet and then
apply the search strategy to find the optimal architectures. Another approach
is differentiable weight-sharing [40, 8, 14], which places a differentiable
parameter for each node and updates alone with the architecture weights. The
differentiable weight-sharing NAS is typically faster than one-shot NAS, yet
hard to put hard constraints (i.e., FLOPs or latency) on the target model.

##  3 Analysis

###  3.1 Train-BN-only Networks are Neural Tangent Kernel

We first formally defined a fully-connected network with batch normalization
layer. Consider a L-layers network with width $n_{l}$, for $l=0,\cdots,L$. We
denote the weight and bias for the $l$-th fully-connected layer by
$\mathcal{W}^{l,fc}\in\mathcal{R}^{n_{l}\times n_{l-1}}$ and bias
$b^{l,fc}\in\mathcal{R}^{n_{l}}$. The weight, bias, mean statistics for batch,
variance statistics for batch for the $l$-th batch normalization layer
attached to the $l$-th fully-connected layer is defined by
$\mathcal{W}^{l,bn}\in\mathcal{R}^{n_{l}\times n_{l-1}}$, bias, mean and
variance $b^{l,bn},\mu^{l},{\sigma^{2}}^{l}\in\mathcal{R}^{n_{l}}$. And a
Lipschitz non-linearity function $\phi:\mathcal{R}\rightarrow\mathcal{R}$. For
each input $x\in\mathcal{R}^{n_{0}}$, we denote the pre-activations by
$h^{l}(x)\in\mathcal{R}^{n_{l}}$ and post-activations by
$x^{l}(x)\in\mathcal{R}^{n_{l}}$. The feed-forward propagation for $l$-th
layer in the network is

$x^{l}_{i}=\phi(\sum_{n_{l}}^{j=1}\mathcal{W}^{l,bn}_{ij}\frac{h_{i}^{l}-\mu^{l}_{i}}{\sqrt{{\sigma^{2}}^{l}_{i}+\epsilon}}+b^{l,bn}_{i})$
(1)

where

$h^{l}_{i}=\sum_{n_{l}}^{j=1}W^{l,fc}_{ij}x^{l-1}_{j}+b^{l,fc}_{i}$ (2)

The Neural Tangent Kernel (NTK) is proposed to characterize the behavior of
fully-connected/convolutional infinite width neural networks whose layers have
been trained by gradient descent. According to Jacot et al. [34], the NTK of a
fully-connected network with Gaussian initialization stays asymptotically
constant during gradient descent training in the infinite-width limit,
providing a guarantee for loss convergence. We find that the NTK of fixed
fully-connected networks attached with trainable batch normalization have the
same property in an asymptotic way.

Theorem 1. Consider a FCN-BN of the equation (1) and (2) at Gaussian
initialization $\mathcal{N}(0,1)$, with a Lipschitz non-linearity $\sigma$,
and the $\mathcal{W}^{l,fc}$ and $b^{l,fc}$ is fixed at initialization. In the
limit as the layers width $n_{1},\cdots,n_{L-1}\rightarrow\infty$, the NTK
$\Theta^{L}_{0}(x,x^{\prime})$, converges in probability to a deterministic
limiting kernel:

$\Theta^{L}_{0}(x,x^{\prime})\rightarrow\Theta^{L}_{\infty}(x,x^{\prime})\otimes\mathbf{I}_{n_{L}\times
n_{L}}$ (3)

The scalar kernel $\Theta^{L}_{\infty}(x,x^{\prime})$ is defined recursively
by

$\Theta^{l}_{\infty}(x,x^{\prime})=\sigma^{2}_{w}\Sigma^{l}(x,x^{\prime})\Theta^{l-1}_{\infty}(x,x^{\prime})+\Sigma^{l}(x,x^{\prime})$
(4)

where

$\Theta^{1}_{\infty}(x,x^{\prime})=\Sigma^{l}(x,x^{\prime})=\mathcal{E}_{f\sim\mathcal{N}(0,1)}[\phi(f(x))\phi(f(x^{\prime}))]$
(5)

We refer readers to the Appendix for the derivation of this formula. Our
theoretical result indicates train-BN-only networks (infinite-width networks
of fixed, Gaussian initialization fully-connected layer with trainable
Gaussian initialized BatchNorm layer) and standard trained networks (infinite-
width networks of Gaussian initialization fully-connected layer) should have
the same convergence rate during the gradient descent training. This means
that two different training strategies have similar training dynamics in the
NTK regime. Our analysis theoretically supports the practicability of the
train-BN-only supernet. Additionally, since the training parameters in the
train-BN-only setting is much less than standard-trained supernet, it is
practicable to reduce the supernet training time.

###  3.2 Train-BN-only Supernet is Unfair

In this section, we empirically study the behavior of train-BN-only supernet.
The conventional one-shot NAS approach needs to train a supernet constructed
by all operation candidates $OP$. A typical NAS search space has many types of
operations, for instance,
$OP(\cdot)\in\\{3x3\\_conv,avg\\_pool,\cdots,identity\\}$. Notably, all
parameters in the operation candidates, including the BatchNorm, are updated
during training. Then, it uses validation accuracy to rank the architectures.
Recently, Chen et al. [9] propose to update the BatchNorm only and fix the
parameters of $OP(\cdot)$. The search stage uses the average $\gamma$ value
over all cells to indicate model rank. It is noteworthy that they limit the
choice of $OP(\cdot)\in Conv(\cdot)$ such that the search space contains
convolutional operators only.

Method | 1x1 Conv | 3x3 Conv | Avg Pool | Identity | Zero | Avg Params | Avg FLOPs | Avg Acc
---|---|---|---|---|---|---|---|---
BN-NAS | 24 | 36 | 0 | 0 | 0 | 0.87 | 126 | 93.24
FBN-NAS | 16 | 26 | 4 | 11 | 3 | 0.69 | 103 | 93.28
Table 1: We count the number of various operations for the Top-10 architecture
with training stand alone architectures in NAS-Bench-201 on CIFAR-10. We
present the result of BN-NAS and FBN-NAS.

Figure 2 shows the scatter plot of trained model test accuracy versus the
value of gamma in BatchNorm. We randomly sample 1,000 models from NAS-
Bench-201 and train BatchNorm only with each model by one epoch on CIFAR10.
Each color represents a range of the number of parameters.

We can observe that there is indeed a positive correlation between test
accuracy and gamma value. However, the architectures with a high gamma value
(over 85) mostly have a more significant number of parameters (we show the
corresponding plot measured by FLOPs in Appendix). Meanwhile, the test
accuracy of these architectures is mostly comparable or even worse than many
smaller architectures with low gamma values. In Table 1 we count the number of
operations in the architectures with the top ten highest gamma values in the
BN-NAS. We find out that the BN-NAS favors convolutional layers: None of the
architecture with high gamma values have operations other than 1x1 and 3x3
convolutions.

Our empirical observation unveils the fact that the train-BN-only supernet is
biased towards convolution layers because the BatchNorm only attached to the
convolutions. In other words, since only the BatchNorm is trained, the
capacity of networks is primarily determined by the learning process on the
learnable parameters in BatchNorm. Even though we calculate the average value
of gamma overall operation nodes, placing BatchNorm after convolutional layers
only has a negative impact on searching good-performing architectures with
small sizes. In conclusion, the BNNAS is biased, causing unfairness on the
search in supernet.

Figure 2: Analysis of BN-NAS and test accuracy on CIFAR10. The size of the
models that are measured by number of parameters. Best view in colors.
Conclusion: the BNNAS are biased toward large models.

Figure 3: The gamma value of BatchNorm versus test accuracy train with 1
(left) and 200 (right) epoch. Conclusion: the $\gamma$-Indicator is
ineffective on the unbiased BNNAS.

###  3.3 Fair-BN Supernet

As aforementioned, fixing the unfairness issue in the search space for the
Train-BN-Only supernet is necessary. Thus we propose the Fair BatchNorm
supernet (FBN supernet). The method is simple: we attach a BatchNorm layer to
every operation, including the pooling layer, the identity layer, etc. As
such, a fair evaluation for each architecture can be done when the training is
finished. This is extremely important for weight sharing NAS [12, 39, 14, 13].
The top part in Figure 1 gives a comparison of the BN-NAS and the unbiased
FBN-NAS in the training stage. We also show the number of operations on the
top ten architectures search by the unbiased FBN-NAS in Table 1. Evidently,
our approach can find networks consisting of diverse operations. While
obtaining slightly better accuracy than the BNNAS, our approach consistently
finds smaller architecture (measure by both FLOPs and number of parameters.).

###  3.4 The Ineffectiveness of $\gamma$-indicator

The most straightforward way to search architectures is to reuse the
$\gamma$-indicator in BN-NAS [9]. However, our empirical study shows that the
correlation between test accuracy and gamma value no longer exists after the
training becomes fair for various network architectures. The Figure 3 shows
the results of stand-alone training networks on CIFAR10 with training BN only
for one epoch and two hundred epochs. There are 1,000 architectures randomly
sampled from NAS-Bench-201. We can observe that when the networks are trained
for only one epoch, the correlation between test accuracy and gamma value is
completely random. The architectures with high gamma value can have an
accuracy range from 30% to 93%. When we train the networks for 200 epochs, the
situation becomes worse. In the right Figure 3, the architecture that obtains
the highest gamma value over 200 achieves around 60% test accuracy. As we
attach BatchNorm after pooling layers or identity layers, the gamma value of
network architectures with those operations can also reach a very high value,
which makes the $\gamma$-indicator no longer be an effective performance
indicator for FBN supernet.

##  4 The BatchNorm Based, Theoretically Inspired Composite Performance
Indicator for NAS

In the previous section, we have shown the convergence rate of train-BN-only
supernet and the unfairness issue with the search process. We also validate
that the $\gamma$-indicator fails on the Fair-BN supernet. In this section, we
introduce a composite performance indicator (CPI) for the FBN supernet. Our
goal is to design an indicator that can be 1) effectively predict the rank of
the architectures at the early training stage of the unbiased BNNAS, and 2)
efficiently calculated during the search stage. We disentangle the model
generalization into model expressivity, trainability, and uncertainty. More
importantly, since FBN supernet only involves training on BatchNorm, we derive
all three sub-performance indicators from theoretically inspired properties
from BatchNorm.

Expressivity. The ability of deep networks that can compactly express highly
complex functions over input space is viewed as one of the most critical
factors to their success. The expressivity of deep networks has been widely
studied theoretically [50, 51] and has been used on NAS to score networks with
random features [45, 10]. However, both [10] and [45] count the number of
linear regions of randomly initialized networks, limiting their search space
on networks with ReLU activation [46]. Whereas current SOTA backbones highly
rely on non-linear activation other than ReLU, such as Swish [30, 61].

This paper discusses the expressivity of random features for various layer
choices, such as convolutional layers, pooling layers, identity, etc., with
trainable batch normalization. The batch normalization can be considered as a
reparameterization trick on the parameters space. Learning to scale and shift
the initialized parameters does not increase the expressivity of the random
feature itself. Therefore, we refer to the validation accuracy as the
expressivity of the deep networks. The original BNNAS fails to measure the
expressivity of random features due to unfair supernet training. In our
unbiased BNNAS, since the number of learnable BatchNorm parameters are the
same for each operation, we can adopt expressivity as a performance indicator.

Trainability. Besides the expressivity, whether a deep network can achieve
good performance is determined by how effectively the optimizer can optimize
it. Recent work [56] shows the effect of BatchNorm on the Lipschitzness of the
loss, which plays a crucial role in optimization by controlling the amount by
which the loss can change when taking a training step [7, 47]. Their empirical
and theoretical results indicate that the BatchNorm smooth the loss landscape,
and the re-parametrization in BatchNorm makes the gradient of the loss more
Lipschitz.

Specifically, let us denote the loss of a network with BatchNorm as
$\mathcal{L_{BN}}$ and the loss of the same network without BatchNorm as
$\mathcal{L_{noBN}}$. Given the activation $\hat{y}_{j}$, and gradient
$\nabla_{\hat{y}_{j}}\hat{L}$, we define the Lipschitzness of the loss as
$||\nabla_{y_{j}}\mathcal{L}||$, [56] prove that we can measure the effect of
BatchNorm on the Lipschitz by

$\begin{split}||\nabla_{y_{j}}\hat{\mathcal{L}}||^{2}\leq\frac{\gamma^{2}}{\sigma^{2}_{j}}(||\nabla_{y_{j}}\mathcal{L}||^{2}&-\frac{1}{m}\langle
1,\nabla_{y_{j}}\mathcal{L}\rangle^{2}\\\
&-\frac{1}{\sqrt{m}}\langle\nabla_{y_{j}}\mathcal{L},\hat{y}_{j}\rangle^{2})\end{split}$
(6)

As a result, the scale term $\frac{\gamma}{\sigma}$ in the inequality can be
used to measure the flatness of the loss landscape, which we define as the
trainability score in our context.

Method | Search | CIFAR-10 |  | CIFAR-100 |  | ImageNet-16-120
---|---|---|---|---|---|---
(s) | validation | test |  | validation | test |  | validation | test
Search Space: NAS-Bench-201
Non-Weight Sharing
REA [53] | 12000 | 91.19$\pm$0.31 | 93.92$\pm$0.30 |  | 71.81$\pm$1.12 | 71.84$\pm$0.99 |  | 45.15$\pm$0.89 | 45.54$\pm$1.03
RS [38] | 12000 | 90.93$\pm$0.36 | 93.70$\pm$0.36 |  | 70.93$\pm$1.09 | 71.04$\pm$1.07 |  | 44.45$\pm$1.10 | 44.57$\pm$1.25
REINFORCE [70] | 12000 | 91.09$\pm$0.37 | 93.85$\pm$0.37 |  | 71.61$\pm$1.12 | 71.71$\pm$1.09 |  | 45.05$\pm$1.02 | 45.25$\pm$1.18
BOHB [20] | 12000 | 90.82$\pm$0.53 | 93.61$\pm$0.52 |  | 70.74$\pm$1.29 | 70.85$\pm$1.28 |  | 44.26$\pm$1.36 | 44.42$\pm$1.49
Weight Sharing
WSRS [25] | 7587 | 84.16$\pm$1.69 | 87.66$\pm$1.69 |  | 59.00$\pm$4.60 | 58.33$\pm$4.34 |  | 31.56$\pm$3.28 | 31.14$\pm$3.88
DARTS [40] | 29902 | 39.77$\pm$0.00 | 54.30$\pm$0.00 |  | 15.03$\pm$0.00 | 15.61$\pm$0.00 |  | 16.43$\pm$0.00 | 16.32$\pm$0.00
GDAS [79] | 28926 | 90.00$\pm$0.21 | 93.51$\pm$0.13 |  | 71.14$\pm$0.27 | 70.61$\pm$0.26 |  | 41.70$\pm$1.26 | 41.84$\pm$0.90
FairNAS [13] | 9845 | 90.07$\pm$0.57 | 93.23$\pm$0.18 |  | 70.94$\pm$0.94 | 71.00$\pm$1.46 |  | 41.90$\pm$1.00 | 42.19$\pm$0.31
SETN [18] | 31010 | 82.25$\pm$5.17 | 86.19$\pm$4.63 |  | 56.89$\pm$7.59 | 56.87$\pm$7.77 |  | 32.54$\pm$3.63 | 31.90$\pm$4.07
ENAS [48] | 13315 | 39.77$\pm$0.00. | 54.30$\pm$0.00 |  | 15.03$\pm$0.00 | 15.61$\pm$0.00 |  | 16.43$\pm$0.00 | 16.32$\pm$0.00
Training-Free
NASWOT [45] | 306.19 | 89.69$\pm$0.73 | 92.96$\pm$0.81 |  | 69.86$\pm$1.21 | 69.98$\pm$1.22 |  | 43.95$\pm$2.05 | 44.44$\pm$2.10
TENAS [10] | 1558 | 89.92$\pm$0.43 | 93.35$\pm$0.25 |  | 69.25$\pm$0.71 | 69.59$\pm$0.67 |  | 43.55$\pm$2.54 | 44.06$\pm$2.19
Training-BN
BN-NAS [9] | 967 | 89.72$\pm$0.42 | 92.62$\pm$0.31 |  | 68.46$\pm$1.04 | 68.33$\pm$0.89 |  | 38.97$\pm$1.02 | 39.22$\pm$0.80
FBN-NAS | 686 | 90.32$\pm$0.24 | 93.79$\pm$0.18 |  | 70.87$\pm$0.53 | 70.91$\pm$0.89 |  | 44.17$\pm$0.14 | 44.35$\pm$1.18
Optimal | - | 91.61 | 94.37 |  | 74.49 | 73.51 |  | 46.77 | 47.31
Table 2: The mean$\pm$std. accuracies on NAS-Bench-201. Baselines are run over
500 times for most cases and 3 for weight-sharing methods and average accuracy
is reported.

Uncertainty. Uncertainty is a measurement of knowing what the model does not
know. Deep neural networks are known to be overconfident in their predictions.
Instead of point estimation, the model can offer confidence bounds for each
decision from the probabilistic view to avoid over-confidence. This is useful
to solve core issues of deep networks such as poor calibration and data
inefficiency [23, 37]. There are rarely studies that discuss the relationship
between uncertainty and model generalization. In this work, we obtain
practical uncertainty for each network architecture via trainable batch
normalization [63]. We discuss the correlation of uncertainty and performance,
and we use it as one of the performance indicators to find plausible
architectures.

Specifically, given a network architecture $X$, we are interested in
approximating inference in Bayesian modeling. A common approach is to learn a
parameterized approximating distribution $q_{\theta}(\omega)$ that minimizes
$KL(q_{\theta}(\omega)||p(\omega|D))$, where $D$ is the training set, $\omega$
is the model parameters, $p(\omega|D)$ is the probabilistic model, the
Kullback-Leibler divergence is of the true posterior with respect to its
approximation.

For models that are built upon batch normalization, we are able to obtain
approximate posterior by modeling $\mu_{B}$ and $\sigma_{B}$ over a mini-batch
$B$ as stochastic variables. Following [63], we use approximate posterior to
express an approximate predictive distribution $p(y|x,D)=\int
f_{\omega}(x,y)q_{\theta}(\omega)d\omega$, and we can obtain the covariance of
the predictive distribution empirically by

$\begin{split}Cov_{p*}[y]&\approx\tau^{-1}I+\frac{1}{\tau}\sum^{T}_{i=1}f_{(\hat{\mu_{i}},\hat{\sigma_{i}})}(x)^{T}f_{(\hat{\mu_{i}},\hat{\sigma_{i}})}(x)\\\
&-E_{p*}[y]^{T}E_{p*}[y]\end{split}$ (7)

The calculation of variance is generic in practice. We simply record the value
of variance for each iteration during evaluation and then average the total
variance to obtain the final uncertainty score.

###  4.1 Composite Performance Indicator

In the previous section, we present three theoretically inspired performance
indicator to evaluate the performance of networks in FBN supernet. The key to
build an effective NAS algorithm is how to combine these indicators.
Intuitively, the numerical value for each indicator varies, thus it is
impossible to simply adding them together. The naive approach would be to
normalize each indicator’s value, then add them into a single score. However,
such a way requires us to know the estimated range of the value prior to we
perform the search, which is impossible for most cases. Therefore, we rank the
architecture according to the value for each indicator instead. How to combine
the rank results on different indicators can be treated as an ensemble
learning problem. In practice, we give equivalent importance to each indicator
and use the average rank across three indicators as the final rank for
simplicity. We discuss the correlation between accuracy and the CPI in Section
5.3.

Method | Accuracy | Search Cost
---|---|---
Random [38] | 90.38$\pm$5.51 | N/A
REA [54] | 93.87$\pm$0.22 | 12000
AREA [45] | 93.91$\pm$0.29 | 12000
RLNAS [81] | 93.78$\pm$0.14 | 10372
BN-NAS [9] | 91.04$\pm$0.32 | 979
FBN-NAS | 94.16$\pm$0.10 | 701
Table 3: The mean$\pm$std. accuracy with search cost on NAS-Bench-101.

##  5 Experiments

In this section, we introduce the experiments on NAS-Bench-101, NAS-Bench-201,
DARTS search space, and MobileNet search space. All search cost are evaluated
on Nvidia GTX 1080-Ti.

###  5.1 NAS-Benchmark Experiments

NAS-Bench-101. [78] is the first reproductive benchmark for NAS, and we
compare our FBN-NAS with random search [78], REA [54], AREA [45], and RLNAS
[81]. As shown in Table 3, our FBN-NAS outperforms the BN-NAS counterpart by a
large margin, on an average accuracy of 94.16% versus 91.04%. Our approach
also achieves slightly higher accuracy than other methods with much less
search cost, for instance, 6.8% of RLNAS and 5.8% of non-weight sharing REA.

NAS-Bench-201. The NAS-Bench-201 is proposed by [17], which benchmarks a
number of NAS algorithms. It contains 15,625 candidate architectures and
provides the accuracy for each architecture. We compare our proposed methods
with non-weight sharing NAS (Random Search, REA [53], REINFORCE [70], BOHB
[20]), weight-sharing NAS (Random Search [38], DARTS [40], GDAS [79], SETN
[18], ENAS [48], FairNAS [13], BN-NAS [9]), and training-free NAS (NASWOT [45]
and TENAS [10]). We report the experimental results of FBN-NAS in Table 2. Our
results indicate the FBN-NAS is extremely fast: over 20 to 30 times faster
than the weight-sharing approach (FairNAS and ENAS), while we obtain
comparable or slightly better performance than these methods. Compared to the
BN-NAS, our approach further save 70% of search time and achieve better
performance on all three datasets. Though our method does not designed for
training-free approach, we compare our method with two state-of-the-art
training-free NAS. Due to the high query time [69], the TENAS spend longer
search time than FBN-NAS, while the performance is lower than ours. The NASWOT
is about 2 times faster in terms of search cost, but our results are much
better than NASWOT.

Method | Acc | FLOPs | Search Cost
---|---|---|---
(%) | (M) | (GPU days)
Search Space: MobileNet
ProxylessNAS [8] | 75.1 | 465 | 8.3
FBNet [72] | 74.9 | 375 | 9
AngleNAS [32] | 75.97 | 472 | 10
FairNAS [13] | 74.07 | 325 | 16
SPOS [25] | 75.73 | 470 | 12
BNNAS [9] (FairNAS) | 74.12 | 326 | 0.8
FBN-NAS (FairNAS) | 74.28 | 325 | 0.5
BNNAS [9] (SPOS) | 75.67 | 470 | 1.2
FBN-NAS (SPOS) | 75.81 | 465 | 0.8
BNNAS [9] (SPOS) + SE | 76.78 | 473 | 0.8
FBN-NAS (SPOS) + SE | 76.83 | 327 | 0.5
Search Space: DARTS
DARTS [40] | 73.3 | 574 | 4
GDAS [79] | 74.4 | 590 | 0.3
PC-DARTS [76] | 75.8 | 597 | 3.8
Fair-DARTS [14] | 75.1 | 541 | 0.4
RLNAS [81] | 75.9 | 597 | 8
BNNAS [9] (SPOS) | 74.7 | 598 | 0.5
FBN-NAS (SPOS) | 75.7 | 534 | 0.33
Table 4: The Top-1 accuracy on ImageNet with MobileNet search space and DARTS
search space.

###  5.2 ImageNet Experiments

MobileNet search space. MobileNet-like Search Space consists of 21 to-be-
searched layers, each layer leverages the MobileNetV2 inverted bottleneck [55]
and optional with SE module [31]. At each layer, the search method can choose
operation between convolutional layers with kernel size {3, 5, 7}, expansion
ratio {3, 6} and identity layers. Note that the original BN-NAS does not have
the identity layer option. We compare with several weight-sharing NAS that use
the same search space setting [25, 13, 8, 9, 32]. We developed our method
based on SPOS [25] and FairNAS [13], following the BN-NAS [9] for fair
comparison.As shown in Table 4, with the same search space, our searched
results achieve 74.28% with 325 MFLOPs and 75.81% with 465 MFLOPs, slightly
outperform SPOS and FairNAS counterpart, whereas the search time is only 24
times and 20 times less the of the original method, respectively. Furthermore,
there is a clear advantage of FBN-NAS over the BN-NAS, which outperforms the
BN-NAS by 0.16% and 0.14% on accuracy with 1.6 times and 1.5 times less search
cost. It indicates that even on the search space that is mainly composed of
convolutions, our method is still superior to the BN-NAS. By searching the SE
module, we obtain architecture with 1.05% higher accuracy than the BN-NAS with
only 69% of the FLOPs. Our unbiased training strategy and performance
indicator help us find small architectures with plausible accuracy.

DARTS search space. We compare our algorithms with various NAS algorithms [13,
79, 40, 81, 14] that performed on the same DARTS search space. The bottom of
Table 4 provides the experimental results on ImageNet. We can observe that the
BN-NAS does not achieve satisfactory results, as the test accuracy is
relatively lower than state-of-the-art methods, yet its FLOPs are similar or
higher. On the other hand, the FBN-NAS obtain 1.0% higher accuracy and 64
fewer FLOPs than the BN-NAS. It demonstrates that our approach is robust on
search space with various operations. This further backs up our initial
assumption that the biased BN-NAS hurts search performance.

Figure 4: The correlation analysis of performance indicator on NAS-Bench-201
CIFAR100.

###  5.3 Ablation Study

Correlation analysis for composite performance indicator. One straightforward
question for our approach is how strong is the correlation between the
performance of networks with our composite performance indicator. Thus, we
conduct a correlation analysis on NAS-Bench-201 [17] CIFAR100. We follow White
et al. [69], a through study on performance indicator in NAS. We compare our
approach with a number of performance predictors, including training-free NAS
(Jacobian Covariance in NASWOT [45], Fisher, SNIP, Grasp, SynFlow in
ZeroCostProxy [1]) and many state-of-the-art methods [68, 52, 58, 67, 3, 59,
64, 43, 57, 42, 58, 5, 60, 41].

As illustrated in Figure 4, our approach obtained the highest Kendall tau
correlation under the same initialization time. Compared to the training-free
NAS, our approach achieve a higher correlation with a short initial time
overhead. In terms of initialization time, our method is highly efficient
compared to the other performance predictor. Notably, the NAO [43] needs to
around eight more times for initialization in order to achieve a similar
Kendall tau correlation. Overall, our composite performance indicator shows to
be effective in ranking architectures.

Trainability-indicator versus $\gamma$-indicator. Notice that even though the
only difference between our trainability-indicator and $\gamma$-indicator is
the term $\frac{1}{\sigma}$, the outcome is distinct. In Figure 6, we give a
comparison between trainability-indicator and $\gamma$-indicator on a
Mobilenet supernet, that is trained with unbiased FBN-NAS by 5 epochs on
CIFAR-10. As expected, the value of $\gamma$-indicator is clustered together,
which behaves similar to what we observe in previous study on training stand-
alone networks. On the other hand, the trainability score scatter and shows a
Kendall tau correlation of 0.646 with the test accuracy.

Figure 5: Left: The $\gamma$-indicator versus test accuracy on MobileNet
supernet, Right: the trainability score versus test accuracy on MobileNet
supernet Figure 6: The number of linear regions does not changes as the
BatchNorm are trained for more epochs.

Expressivity versus more epochs of training We discuss the impact that
training longer on FBN supernet has on architecture rank measured by
expressivity. We randomly select 1,000 architectures from NAS-Bench-201. We
compare the scores change after train for ten more epochs. We observe that the
expressivity is consistent. Training more epochs on supernet does not result
in a change in the architecture’s rank. In conclusion, it is safe to measure
the expressivity [45] of FBN supernet in the very beginning, thus saving lots
of time on initialization.

##  6 Conclusion

In this work, we both theoretically and empirically study the train-BN-only
strategy in NAS. First, we prove that the train-BN-only networks obtain the
same training dynamics as the conventional optimization strategy does in
networks by proving that optimizing infinite-width networks with updating BN-
only is a neural tangent kernel. We then verify the unfairness in supernet
training caused by the Conv-BN combination and propose a solution to solve the
issue. Further, we leverage the theoretically-inspired BN properties from
three perspectives to evaluate the networks. Overall, our method is general on
diverse search space, fast on supernet training, and better at finding small
and high-performing networks than the conventional one-shot NAS approach.

## References

  * [1] Mohamed S Abdelfattah, Abhinav Mehrotra, Łukasz Dudziak, and Nicholas D Lane.  Zero-cost proxies for lightweight nas.  arXiv preprint arXiv:2101.08134, 2021.
  * [2] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  arXiv preprint arXiv:1607.06450, 2016.
  * [3] Matthias Bauer, Mark van der Wilk, and Carl Edward Rasmussen.  Understanding probabilistic sparse gaussian process approximations.  In Advances in neural information processing systems, pages 1533–1541, 2016.
  * [4] 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.
  * [5] Christopher M Bishop.  Pattern recognition.  Machine learning, 128(9), 2006.
  * [6] Johan Bjorck, Carla Gomes, Bart Selman, and Kilian Q Weinberger.  Understanding batch normalization.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 7705–7716, 2018.
  * [7] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [8] Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  arXiv preprint arXiv:1812.00332, 2018.
  * [9] Boyu Chen, Peixia Li, Baopu Li, Chen Lin, Chuming Li, Ming Sun, Junjie Yan, and Wanli Ouyang.  Bn-nas: Neural architecture search with batch normalization.  2021\.
  * [10] Wuyang Chen, Xinyu Gong, and Zhangyang Wang.  Neural architecture search on imagenet in four {gpu} hours: A theoretically inspired perspective.  In International Conference on Learning Representations, 2021.
  * [11] Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Xinyu Xiao, and Jian Sun.  Detnas: Backbone search for object detection.  Advances in Neural Information Processing Systems, 32:6642–6652, 2019.
  * [12] Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan.  Darts-: Robustly stepping out of performance collapse without indicators.  In International Conference on Learning Representations, 2020.
  * [13] Xiangxiang Chu, Bo Zhang, Ruijun Xu, and Jixiang Li.  Fairnas: Rethinking evaluation fairness of weight sharing neural architecture search.  2021\.
  * [14] Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li.  Fair darts: Eliminating unfair advantages in differentiable architecture search.  In European conference on computer vision, pages 465–480. Springer, 2020.
  * [15] Hadi Daneshmand, Amir Joudaki, and Francis Bach.  Batch normalization orthogonalizes representations in deep random networks.  arXiv preprint arXiv:2106.03970, 2021.
  * [16] Hadi Daneshmand, Jonas Moritz Kohler, Francis R Bach, Thomas Hofmann, and Aurélien Lucchi.  Batch normalization provably avoids ranks collapse for randomly initialised deep networks.  In NeurIPS, 2020.
  * [17] Xuanyi Dong and Yi Yang.  Nas-bench-201: Extending the scope of reproducible neural architecture search.  In International Conference on Learning Representations, 2019.
  * [18] Xuanyi Dong and Yi Yang.  One-shot neural architecture search via self-evaluated template network.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3681–3690, 2019.
  * [19] Thomas Elsken, Benedikt Staffler, Arber Zela, Jan Hendrik Metzen, and Frank Hutter.  Bag of tricks for neural architecture search.  arXiv preprint arXiv:2107.03719, 2021.
  * [20] Stefan Falkner, Aaron Klein, and Frank Hutter.  Bohb: Robust and efficient hyperparameter optimization at scale.  In International Conference on Machine Learning, pages 1437–1446. PMLR, 2018.
  * [21] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  arXiv preprint arXiv:1803.03635, 2018.
  * [22] Jonathan Frankle, David J. Schwab, and Ari S. Morcos.  Training batchnorm and only batchnorm: On the expressive power of random features in {cnn}s.  In International Conference on Learning Representations, 2021.
  * [23] Yarin Gal and Zoubin Ghahramani.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In international conference on machine learning, pages 1050–1059. PMLR, 2016.
  * [24] Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao.  Knowledge distillation: A survey.  International Journal of Computer Vision, 129(6):1789–1819, 2021\.
  * [25] 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.
  * [26] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  arXiv preprint arXiv:1510.00149, 2015.
  * [27] 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.
  * [28] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [29] Elad Hoffer, Itay Hubara, and Daniel Soudry.  Train longer, generalize better: closing the generalization gap in large batch training of neural networks.  arXiv preprint arXiv:1705.08741, 2017.
  * [30] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al.  Searching for mobilenetv3.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1314–1324, 2019.
  * [31] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7132–7141, 2018.
  * [32] Yiming Hu, Yuding Liang, Zichao Guo, Ruosi Wan, Xiangyu Zhang, Yichen Wei, Qingyi Gu, and Jian Sun.  Angle-based search space shrinking for neural architecture search.  In European Conference on Computer Vision, pages 119–134. Springer, 2020.
  * [33] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International conference on machine learning, pages 448–456. PMLR, 2015.
  * [34] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: convergence and generalization in neural networks.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 8580–8589, 2018.
  * [35] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Freeze and chaos for dnns: an ntk view of batch normalization, checkerboard and boundary effects.  2019\.
  * [36] Fahdi Kanavati and Masayuki Tsuneki.  Partial transfusion: on the expressive influence of trainable batch norm parameters for transfer learning.  arXiv preprint arXiv:2102.05543, 2021.
  * [37] Alex Kendall and Yarin Gal.  What uncertainties do we need in bayesian deep learning for computer vision?  arXiv preprint arXiv:1703.04977, 2017.
  * [38] Liam Li and Ameet Talwalkar.  Random search and reproducibility for neural architecture search.  In Uncertainty in artificial intelligence, pages 367–377. PMLR, 2020.
  * [39] Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li.  Darts+: Improved differentiable architecture search with early stopping.  arXiv preprint arXiv:1909.06035, 2019.
  * [40] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  In International Conference on Learning Representations, 2018.
  * [41] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu.  Accuracy prediction with non-neural model for neural architecture search.  arXiv preprint arXiv:2007.04785, 2020.
  * [42] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu.  Semi-supervised neural architecture search.  arXiv preprint arXiv:2002.10389, 2020.
  * [43] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Yan Liu.  Neural architecture optimization.  arXiv preprint arXiv:1808.07233, 2018.
  * [44] Krzysztof Maziarz, Mingxing Tan, Andrey Khorlin, Marin Georgiev, and Andrea Gesmundo.  Evolutionary-neural hybrid agents for architecture search.  arXiv preprint arXiv:1811.09828, 2018.
  * [45] Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley.  Neural architecture search without training.  In International Conference on Machine Learning, pages 7588–7598. PMLR, 2021.
  * [46] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  arXiv preprint arXiv:1402.1869, 2014.
  * [47] Yurii Nesterov.  Introductory lectures on convex optimization: A basic course, volume 87.  Springer Science & Business Media, 2003.
  * [48] 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.
  * [49] Antonio Polino, Razvan Pascanu, and Dan Alistarh.  Model compression via distillation and quantization.  arXiv preprint arXiv:1802.05668, 2018.
  * [50] Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  Advances in neural information processing systems, 29:3360–3368, 2016.
  * [51] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In international conference on machine learning, pages 2847–2854. PMLR, 2017.
  * [52] Carl Edward Rasmussen.  Gaussian processes in machine learning.  In Summer school on machine learning, pages 63–71. Springer, 2003\.
  * [53] 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.
  * [54] 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.
  * [55] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4510–4520, 2018.
  * [56] Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Mądry.  How does batch normalization help optimization?  In Proceedings of the 32nd international conference on neural information processing systems, pages 2488–2498, 2018.
  * [57] Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang.  Bridging the gap between sample-based and one-shot neural architecture search with bonas.  Advances in Neural Information Processing Systems, 33, 2020.
  * [58] 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.
  * [59] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams.  Scalable bayesian optimization using deep neural networks.  In International conference on machine learning, pages 2171–2180. PMLR, 2015.
  * [60] Jost Tobias Springenberg, Aaron Klein, Stefan Falkner, and Frank Hutter.  Bayesian optimization with robust bayesian neural networks.  Advances in neural information processing systems, 29:4134–4142, 2016.
  * [61] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In International Conference on Machine Learning, pages 6105–6114. PMLR, 2019.
  * [62] Mattias Teye, Hossein Azizpour, and Kevin Smith.  Bayesian uncertainty estimation for batch normalized deep networks.  In International Conference on Machine Learning, pages 4907–4916. PMLR, 2018.
  * [63] Mattias Teye, Hossein Azizpour, and Kevin Smith.  Bayesian uncertainty estimation for batch normalized deep networks.  In International Conference on Machine Learning, pages 4907–4916. PMLR, 2018.
  * [64] Michalis Titsias.  Variational learning of inducing variables in sparse gaussian processes.  In Artificial intelligence and statistics, pages 567–574. PMLR, 2009.
  * [65] Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca.  Alphax: exploring neural architectures with deep neural networks and monte carlo tree search.  arXiv preprint arXiv:1903.11059, 2019.
  * [66] Ning Wang, Yang Gao, Hao Chen, Peng Wang, Zhi Tian, Chunhua Shen, and Yanning Zhang.  Nas-fcos: Fast neural architecture search for object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11943–11951, 2020.
  * [67] Wei Wen, Hanxiao Liu, Yiran Chen, Hai Li, Gabriel Bender, and Pieter-Jan Kindermans.  Neural predictor for neural architecture search.  In European Conference on Computer Vision, pages 660–676. Springer, 2020.
  * [68] Colin White, Willie Neiswanger, and Yash Savani.  Bananas: Bayesian optimization with neural architectures for neural architecture search.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10293–10301, 2021.
  * [69] Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter.  How powerful are performance predictors in neural architecture search?  arXiv preprint arXiv:2104.01177, 2021.
  * [70] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3):229–256, 1992.
  * [71] Charles L Wilson, James L Blue, and Omid M Omidvar.  Training dynamics and neural network performance.  Neural Networks, 10(5):907–923, 1997.
  * [72] Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer.  Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10734–10742, 2019.
  * [73] Yuxin Wu and Kaiming He.  Group normalization.  In Proceedings of the European conference on computer vision (ECCV), pages 3–19, 2018.
  * [74] Yuxin Wu and Justin Johnson.  Rethinking" batch" in batchnorm.  arXiv preprint arXiv:2105.07576, 2021.
  * [75] Hang Xu, Lewei Yao, Wei Zhang, Xiaodan Liang, and Zhenguo Li.  Auto-fpn: Automatic network architecture adaptation for object detection beyond classification.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6649–6658, 2019.
  * [76] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong.  Pc-darts: Partial channel connections for memory-efficient architecture search.  In International Conference on Learning Representations, 2019.
  * [77] Greg Yang, Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel S Schoenholz.  A mean field theory of batch normalization.  In International Conference on Learning Representations, 2018.
  * [78] 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.
  * [79] 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.
  * [80] Dingli Yu, Ruosong Wang, Zhiyuan Li, Wei Hu, Ruslan Salakhutdinov, Sanjeev Arora, and Simon S Du.  Enhanced convolutional neural tangent kernels.  2019\.
  * [81] Xuanyang Zhang, Pengfei Hou, Xiangyu Zhang, and Jian Sun.  Neural architecture search with random labels.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10907–10916, 2021.
  * [82] Yichen Zhu and Yi Wang.  Student customized knowledge distillation: Bridging the gap between student and teacher.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5057–5066, 2021.
  * [83] 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.


# Towards Realistic Market Simulations: a Generative Adversarial Networks
Approach

Andrea Coletta  1234-5678-9012 ,  Matteo Prata  ,  Michele Conti  ,  Emanuele
Mercanti  ,  Novella Bartolini  Sapienza University of RomeRomeItaly ,
Aymeric Moulin  ,  Svitlana Vyetrenko  and  Tucker Balch  J.P. Morgan AI
ResearchNew YorkUSA

###### Abstract.

Simulated environments are increasingly used by trading firms and investment
banks to evaluate trading strategies before approaching real markets.
Backtesting, a widely used approach, consists of simulating experimental
strategies while replaying historical market scenarios. Unfortunately, this
approach does not capture the market response to the experimental agents’
actions. In contrast, multi-agent simulation presents a natural bottom-up
approach to emulating agent interaction in financial markets. It allows to set
up pools of traders with diverse strategies to mimic the financial market
trader population, and test the performance of new experimental strategies.
Since individual agent-level historical data is typically proprietary and not
available for public use, it is difficult to calibrate multiple market agents
to obtain the realism required for testing trading strategies. To addresses
this challenge we propose a synthetic market generator based on Conditional
Generative Adversarial Networks (CGANs) trained on real aggregate-level
historical data. A CGAN-based ”world” agent can generate meaningful orders in
response to an experimental agent. We integrate our synthetic market generator
into ABIDES, an open source simulator of financial markets. By means of
extensive simulations we show that our proposal outperforms previous work in
terms of stylized facts reflecting market responsiveness and realism.

##  1\. Introduction

The standard approach in the evaluation of trading strategies before their
adoption in real markets, is to simulate their performance under a wide range
of existing historical scenarios — a technique known as backtesting. Despite
its common use in trading applications due to its simplicity, the backtesting
approach does not allow to simulate market response to experimental agents’
actions, which makes it unreliable for simulating the execution of trading
strategies.

Interactive Agent-Based Simulators (IABS) address the limitations of the
backtesting approach by modeling the interplay of individual traders, the
agents, of a market system. They are a fundamental tool in financial research
for studying and testing trading strategies, while also providing market
behavior explainability (macal2010tutorial, ; paulin2018agent, ). An agent-
based simulation allows to study the market response to the experimental
agents and enables “what if” studies on how their strategy would perform
(balch2019evaluate, ). IABS are increasingly being used for training of
machine learning based trading strategies (spooner2018market, ;
karpe2020multi, ; buehler2019deep, ), and deepen the study of real market
phenomena (borrajo2020simulating, ; wang2020market, ; yagi2020analysis, ).
While most market simulators are used for internal purposes within trading
firms, robust simulators for high-fidelity market simulation environments are
becoming available also for the research community. One example in this
direction is ABIDES (Agent-Based Interactive Discrete Event Simulation)
(byrd2020abides, ).

Modeling a realistic market behavior is a major challenge, common to all the
described works. To obtain realistic simulations, these approaches rely on
pools of hand-crafted experimental agents to mimic the complexity of a real
market. Along this line of research, previous works (byrd2019explaining, ;
gode1993allocative, ; palit2012can, ) analyzed traders’ behaviors through
market data-sets and described a series of trading strategies. However, a real
stock market includes thousands of participants adopting diverse proprietary
trading strategies. Historical data typically lacks complete details of trader
population and of the adopted strategies. Therefore, it is often impossible to
exactly understand the traders’ behaviors, and to precisely mimic them through
simulated agents. This inevitably leads to poorly realistic simulations, and
as a result “what if” studies may give inaccurate results (vyetrenko2019get,
).

To the best of our knowledge, we are first to propose a GAN-based framework
that is able to learn an abstract representation of the market that can also
react to the observed market state. The proposed framework leverages a
Conditional Generative Adversarial Network (CGAN) (mirza2014conditional, ;
NIPS2014_gan, ) trained on real historical data, to capture the market’s
behavior as a whole arising from the activity of different participants. The
CGAN is trained to generate limit orders conditioned by the currently observed
market situation. A world agent impersonated by a pre-trained CGAN that is
placed in a simulation environment, produces orders to be processed by the
exchange. This agent represents the whole ensemble of trading agents of the
particular symbol on which it was trained. Such simulation test-bed allows to
evaluate any experimental agent, while guaranteeing realism of the produced
market trend and market responsiveness to the experimental agent’s activity.
We show that the market traces generated by the proposed CGAN-based agent
preserve the statistical properties of historical data, and at the same time
expose a reactive behavior against experimental agents.

Here we summarize the original contributions of this paper:

  * •

We propose a framework able to automatically learn and reproduce the market
behavior, allowing realistic and reactive simulations.

  * •

We propose a CGAN architecture able to generate synthetic market data, in
terms of limit orders, as a function of the features observed from the current
market situation, thus guaranteeing both market realism and reactivity to
experimental agents.

  * •

We analyze the realism of generated orders and study the reactivity of the
simulation framework to experimental agents by comparing simulations conducted
with and without them.

  * •

We compare our CGAN based simulations against a state of the art IABS
(vyetrenko2019get, ), showing that our architecture outperforms existing
approaches, exhibiting more realistic properties in terms of stylized facts of
a Limit Order Book (LOB) (cont2001empirical, ; chakraborti2011econophysics, ).

##  2\. RELATED WORK

IABSs are increasingly gaining attention by the research community, with
several works studying simulators and solutions to closely mimic real markets
(vyetrenko2019get, ; byrd2020abides, ; karpe2020multi, ; palit2012can, ;
farmer2005predictive, ).

Farmer et al. (farmer2005predictive, ) study market simulations showing how
zero intelligence (ZI) agents, which place random orders, are able to
reproduce market dynamics (i.e., spread and price) and react to the arrival of
new orders. Palit et al. (palit2012can, ) deepen the study of ZI agents in
market simulations, showing that they can also reproduce fat tails and long
range dependencies.
In a recent work (vyetrenko2019get, ), S. Vyetrenko et al. survey metrics to
assess robust and realistic market simulations. The authors study two
different agent configurations showing how IABS configurations that still rely
on common sense hand-crafted rules may produce unrealistic market scenarios.
In the experimental section, we compare our framework against their agent
configurations and evaluate the related realism metrics.

Other approaches to achieve realistic simulations focus on automatic learning
strategies. An action conditional stochastic forward model (otherwise known as
a world model) was previously used to learn market response to trading from
historical data (world_models, ; lidia_world, ). The model is implemented via
a Convolutional Neural Network (CNN) autoencoder followed by Mixture-Density
Recurrent Network (RNN-MDN), and is subsequently used for reinforcement
learning trading agent training, but is not tested for simulated realism.

Other works in the literature focus on producing synthetic financial time-
series, retaining statistical properties of historical data,
(assefa2020generating, ; li2020generating, ; takahashi2019modeling, ;
NEURIPS2019_c9efe5f2, ; efimov2020using, ). For example, Junyi Li et al.
(li2020generating, ) propose an approach to generate realistic and high-
fidelity stock market order streams, based on GANs. The proposed Stock-GAN
model employs a Conditional Wasserstein GAN to capture the history dependence
of orders. The goal of this study is to generate synthetic data that does not
include features that may link back to the originator of the order in the
training data-set, for anonymity reasons.
However, none of these works address the issue of responsiveness and
reactivity to experimental agents.

Figure 1. An example of order book.

Figure 2. CGAN-Based Simulation Framework.

Figure 3. IABS Simulation Framework.

##  3\. BACKGROUND

In this section we briefly review some important pillars that are useful for
the reader to approach this paper.

#### Orders and Limit Order Book

In financial markets, traders can participate in the auction mechanism by
placing orders to buy [bid] or sell [ask] shares of the financial assets of
choice. There are two major types of orders: (1) market orders, which are
executed immediately at the best available price, i.e. highest buy (lowest
sell) price in case of a sell (buy) market order; (2) limit orders, which,
unlike the market orders, include the specification of a desired target price.
A sell (buy) limit order will be executed only when is matched to a buy (sell)
order whose price is greater than (lower than) or equal to the target price.
The exchange matching engine is responsible for matching the incoming buy and
sell orders issued by the trading agents. Figure 1 shows the LOB of a
financial asset, which is an electronic record of the orders issued by the
traders. LOBs are maintained at financial exchanges, such as NASDAQ and NYSE,
and act as an indicator of the supply and demand of a particular asset in
time. They are organized by price levels and are continuously updated as new
orders are placed.

#### Stylized Facts of financial markets

From the analysis of the market and LOB evolution over time, several metrics
(e.g., spread, mid-price, relative return) and other statistical properties
(e.g., absence of autocorrelation or fat-tailed distribution of asset relative
returns) can be derived. These statistical properties capture the market
behavior over different time periods, and are often referred to as stylized
facts (cont2001empirical, ; chakraborti2011econophysics, ).

One can calculate stylized facts for the time-series produced by agent
interactions for real and simulated markets, and use them as metrics of
simulation realism (vyetrenko2019get, ). In our work, we consider a set of the
most commonly used stylized facts to evaluate how our CGAN-based ”world” agent
is able to reproduce characteristic features of a real market. We study the
following stylized facts:

  * •

Absence of Autocorrelation. The linear autocorrelation of the return
$C(\tau)=\text{corr}(r(t,\Delta t),r(t+\tau,\Delta t))$ rapidly decays to zero
in few minutes and becomes insignificant for periods longer than 20 minutes.

  * •

Volatility Clustering. High-volatility events tend to cluster in time, showing
a positive autocorrelation over several days of trading.

  * •

Volume/Volatility correlation. The trading volume is positively correlated
with volatility.

  * •

Heavy tails and aggregation normality. The asset returns follow a normal
distribution with fat tails. Notice that, fat tails disappear when the time
period $\Delta t$ use to compute the returns increases.

#### Generative Adversarial Networks (GANs)

GANs (NIPS2014_gan, ) are a powerful subclass of generative models and were
successfully applied to image generation and editing, semi-supervised
learning, and domain adaptation.

With GANs, we have a two-player game between the generator $G$, learning how
to generate samples resembling real data, and a discriminator (or critic) $D$,
learning to discriminate between real and generated data. Both players aim to
minimize their own cost, and the solution to the game is the Nash equilibrium
where neither player can improve its cost unilaterally (NEURIPS2018_e46de7e1,
). In this paper, we consider a generator $G$ to learn how to produce new
orders, matching real orders statistical properties. In the GAN framework the
model learns a deterministic transformation $G$ of a simple distribution
$p_{z}$, with the goal of matching the real data distribution $p_{d}$. On the
other hand, $p_{z}$ is the distribution of the generated data, that is
implicitly defined as $\tilde{x}=G(z)$, where $z\sim\mathcal{N}(0,\,1)$ is the
input noise to the generator, sampled from a normal distribution. Random noise
as input to $G$ ensures variance of the generated data. The transformation $D$
is trained to maximize the probability of assigning the correct label to both
training examples $x\sim p_{d}$ and $\tilde{x}\sim p_{z}$, while at the same
time $G$ is trained to minimize the probability of $D$ assigning the correct
label.

The novelty of our work is the design of a synthetic market order generator
whose behavior reacts to the activity of experimental agents, resembling
realistic markets. To this end, while in its most basic form a GAN generator
takes random noise as its input to transform noise into a meaningful output,
we consider a Conditional Generative Adversarial Network (CGAN)
(arjovsky2017wasserstein, ) which takes as input also several features that
characterize the emulated market behavior.

This translates into a joint two-player minimax game that can be described by
the following dynamic:

(1) $\min_{G}\max_{D}\,\underset{x\sim
p_{d}}{\mathbb{E}}[\log(D(x|y))]-\underset{z\sim\mathcal{N}(0,\,1)}{\mathbb{E}}[\log(D(G(z|y)))],$

where $y$ is some extra information that conditions the players’ behavior. The
minimax game derives from the cross-entropy between the real and generated
distributions. Thus $\log(D(x|y))$ and $\log(D(G(z|y)))$ reflect the
likelihood that the discriminator correctly classifies real data $x$ given
$y$, or generated data $G(z|y)$ respectively. The generator $G$ cannot
directly affect the $\log(D(x|y))$ term, thus for him minimizing the loss is
equivalent to maximizing $\log(D(G(z|y)))$ as it is a negative additive
quantity.

##  4\. CGAN-Based Simulation Framework

The proposed simulation framework, represented in Figure 3, includes four main
components:

  1. (1)

The electronic market exchange, which handles incoming orders.

  2. (2)

One or more experimental agents, which operate the trading strategy under
investigation.

  3. (3)

The CGAN-based ”world” agent, which is responsible for emulating the market
behavior, by generating new orders as a function of the current market state.

  4. (4)

The historical data, which is used to train the CGAN agent and to initialize
the simulation.

In contrast to IABS simulations where experimental agents interact with
multiple diverse market participants via an exchange to mimic a real market
(Figure 3), we consider a unique CGAN-based agent, acting as the whole trader
population (Figure 3). In fact, while market behavior is typically modeled
through multiple heterogeneous agents in IABS simulations, these approaches
fail in guaranteeing the necessary realism and responsiveness
(vyetrenko2019get, ).

The lack of knowledge about traders and their strategy in historical data,
motivates poorly realistic simulations.

In our simulation framework, a CGAN-based agent is trained on historical data
to emulate the behavior resulting from the whole set of traders. It analyzes
the order book entries and mimics the market behavior by producing new limit
orders depending on the current market state. Thus, the experimental agents
interact with the CGAN-based agent through the exchange, enabling the test and
the study of their strategy against a responsive and realistic market.

###  4.1. Electronic Market Exchange Simulator

The electronic market exchange handles the LOB of a set of securities,
applying a price-then-FIFO matching rule for the trading orders issued by the
agents. For our simulations we use ABIDES (byrd2020abides, ). It is an open-
source simulator that provides a selection of background agent types (such as
market markers, fundamental value investors, momentum traders, etc.), a
NASDAQ-like exchange agent which lists any number of securities for trade
using a LOB with price-then-FIFO matching rules, and a simulation kernel which
manages the advancement of time and handles all inter-agent communications.

###  4.2. Experimental Agents

An experimental agent is an entity of a financial IABS, representing a
financial trader adopting a specific trading strategy. It owns a portfolio,
pending orders and initial cash. Experimental agents are implemented to
evaluate the performance of their trading strategy, taking into account agent
actions’ impact in the estimated profitability, or to pursue “what if”
studies.
Any trading strategy can be implemented inside an experimental agent
introduced in the simulation, including machine learning based ones
(karpe2020multi, ).

For instance, in our experimental analysis in Section 5, we use an
experimental agent which injects orders so as to reach a given cumulative
volume within a predefined interval of time. We refer to this agent with the
name of Percentage of Volume (POV) experimental agent (vyetrenko2019get, ). We
use this agent in our simulations to evaluate the responsiveness of our CGAN-
based ”world” agent.

###  4.3. CGAN-based World Agent

The core component of our framework is the CGAN-based ”world” agent, which
mimics the market behavior. To this end, our CGAN architecture takes as input
a set of features, representing the current market condition, and generates
the next order to feed into the exchange. The new order is processed by the
exchange and the simulation advances, generating a new market state, and a
subsequent new order from the CGAN. Thus, while common GAN models output data
from input random noise, the proposed CGAN, in addition, is fed with some
meaningful features to condition the data generation. We consider a similar
architecture of Junyi et al. (li2020generating, ), based on the conditional
WGAN (mirza2014conditional, ; arjovsky2017wasserstein, ), adapted to cope with
our task and to react in a simulated environment.

#### Output data

The output of the proposed CGAN-based ”world” agent is what CGAN generator $G$
generates, that is a single order $\tilde{x}$. Formally the output is a
4-tuple $\tilde{x}=$ (price, volume, direction, time), where: direction
$\in\\{-1,1\\}$ represents sell and buy orders respectively; and time is the
interarrival time between two consecutive orders, more precisely it is the
offset w.r.t. the previous order. After this time, the order is placed into
the exchange, and the CGAN is triggered to generate another order.

#### Input data

The input of the proposed CGAN-based experimental agent is made of a vector
$y$ responsible for the conditional nature of the method and random noise
vector $z$ to provide diversity to generated traces.

In more details, a vector $y$ is used to condition the generator output. At
time $t$ the $i$-th element of the vector with $i\in[1,N]$, represents a
series of 10 features linked to a trading order issued at time $t-i$.
Specifically, $y\in\mathbb{R}^{10\cdot N}$. The features are the 4-tuple
mentioned in the previous paragraph representing the order details, that is
(price, volume, direction, time), concatenated to the 6-tuple made of the
following features (best-bid price, best-bid volume, best-ask price, best-ask
volume, mid-price, time-period). As shown in (li2020generating, ), most of the
sent orders are strongly driven by the current mid-price and order book state,
making these features particularly adequate to influence future orders. In
order to avoid instabilities in the training process of the CGAN, we normalize
$y$ with a min-max scaler, between -1 and 1. As for the size, time, best-bid
volume, and best-ask volume they are pre-processed with a box-cox
transformation (sakia1992box, ) in order to reduce anomalies and normally
distribute the data.

Figure 4. CGAN Architecture.

Finally, features vector $z$ constitutes part of the input. This vector is
made of $N_{f}$ noise features sampled from a normal distribution. Notice that
the concatenation between noise and historical information of the market is
necessary. The latter maintain fidelity of the generated data with respect to
the historical data: our agent has to issue seemingly real orders, and this
can be done only if it has up-to-date knowledge of the market state. Instead,
the noise guarantees significant variance in the generated new orders. Noise
samples vary at varying simulation seeds, allowing the generation of diverse
market behaviors. In the experiments, we considered $N=50$ and $N_{f}=50$.

#### CGAN Architecture

We want our model to generate realistic orders providing responsiveness
conditional on the current market state. To do so, we use a CGAN
(mirza2014conditional, ). Input noise from the prior and extra information $y$
(i.e., features about current market situation) are combined and fed into both
the generator and the discriminator. State of the art Wasserstein Generative
Adversarial Network with Gradient Penalty (WGAN-GP) is adopted. In order to
address training instabilities due to exploding and vanishing gradients, we
introduce additional terms and constraints in the loss function as suggested
in (gulrajani2017improved, ). In fact, loss function is constructed using the
Kantorovich-Rubinstein duality (villani2008optimal, ), and considering as
discriminator a 1-Lipschitz function (i.e. a function which norm of the
gradients is upper-bounded by 1). Thus the used loss is:

(2) $\underset{G}{\min}\,\underset{D}{\max}\,\underset{x\sim
p_{d}}{\mathbb{E}}[D(x|y)]-\underset{z\sim\mathcal{N}(0,\,1)}{\mathbb{E}}[D(G(z|y))]+\\\
\underset{z\sim\mathcal{N}(0,\,1)}{\lambda\mathbb{E}}[(\|\nabla
D(G(z|y))\|_{2}-1)^{2}]$

where the weight $\lambda$ is set to 10 as in (gulrajani2017improved, ).

Figure 4 shows the architecture of the CGAN. The generator $G$ is responsible
for producing a trading order $\tilde{x}_{n+1}\sim G(z|y)$ which at best
resembles characteristics of a real order. The input of the generator is, the
normally distributed noise $z\sim\mathcal{N}(0,\,1)$ and the historical data
vector $y$ introduced in the previous section. Before going through the
generator, historical data vector $y$ is fed into a Long Short-Term Memory
(LSTM) (hochreiter1997long, ) to capture the long-term dependencies among
historical traces features and producing a compact encoding. The output of the
LSTM is concatenated with the normally distributed noise and passed through a
series of convolutional layers. CNNs are highly popular due to their ability
to detect patterns that are invariant for some transformation, depending on
the used filter. We believe that these layers allow to extract relevant
information from the LSTM output, which has condensed the history and features
of the current market scenario. The discriminator $D$ takes as input data
coming either from the generator or from the data-set made of real orders. It
outputs a real number representing the distance between the input order and a
real order.

###  4.4. Historical Data

The role of historical data in our proposed simulation framework is twofold.
First, our CGAN model needs order book data and order messages for the
training. The training is carried out in an unsupervised fashion; the CGAN
extracts sequences of historical orders, trying to generate a plausible next
order. The training can be either performed on a single stock during a very
tight time window (e.g., one/two days), or on multiple stocks and periods
(e.g., one month). In the former way, the trained network can be leveraged to
reproduce very specific trends of a certain stock, while in the latter the
trained CGAN can be used to emulate more general market trends.

In case of a single stock testing, the historical data is also used to
initialize the simulation. If we want to simulate a particular symbol and day,
we want to condition the CGAN-based agent with real data at the beginning of
the trading day. The input data let the framework evaluate the market
features, and feed them in the CGAN to generate coherent orders for that day.
The historical data is only needed to start the simulation, as the CGAN-based
agent needs the input market condition (i.e., features $\mathbf{y}$) to
generate new orders. However, if we want to simulate a scenario that is not
linked to any symbol nor day, it suffices to launch a run with experimental
agents that have the most diverse logic, to produce preliminary data in the
exchange, which are then fed into the CGAN to start the generative process.

Notice that, considering the input features, an order book with at least
1-level is needed, along with all the orders submitted to the exchange.
However, as our goal is to mimic the collective traders’ behavior (not per
trader), no sensitive market data are required.

In our experiments we use data from LOBSTER (lobster, ), an online limit order
book data tool that provides high-quality limit order book data, which are
reconstructed from NASDAQ traded stocks. It is worth noting that LOBSTER data
has a specific format that doesn’t provide the full picture. We use a 20-level
data-set. It is constituted of: (1) the order book snapshot history (price and
quantity for each level) for the first 20 levels on each side (there is a new
snapshot every time a price of quantity changes in these levels); (2) the
stream of messages (add order, cancellation etc) related to the levels
displayed in the order book. Liquidity coming from orders placed beyond 20th
level is accounted for in the order book when that price level becomes one of
the 20 first, but the message that created it is not represented in the data-
set. It is a necessary approximation for us in order to make computations
tractable.

##  5\. Experiments

In this section we evaluate our framework under three main aspects. First, we
study our CGAN model performance in terms of training convergence and
statistical similarity of the generated orders to historical ones. Then, we
evaluate the main novelty of our framework which is the ability to react to an
experimental agent. In particular, we show how the CGAN-based ”world” agent
reacts to the burst of orders issued by a POV experimental agent. Finally, we
evaluate the realism of our CGAN-based simulations against a state of the art
approach. In particular we consider the work of S. Vyetrenko et al.
(vyetrenko2019get, ) which proposes pools of hand-crafted experimental agents
to mimic the complexity of a real market, and studies statistical properties
of the resulting synthetic traces.

Figure 5. Comparison of CGAN syntethic and real TSLA orders - Stylized Facts
during the training process, at beginning (top), half (middle) and when it
achieves reasonable convergence (bottom).

We implement our framework extending ABIDES (byrd2020abides, ), an open-source
multi-agent simulator. We trained the model on order book entries from AAPL
and TSLA on 2 trading days. Each training process lasts 4 days, running for
200 epochs on a NVIDIA V100 GPU (nvidiav100, ). The datasets are obtained from
the LOBSTER archive (lobster, ). Being a conditional model, for the first
minutes of simulation, the CGAN ”world” agent is fed with historical data
coming from the training set alone.

###  5.1. CGAN Model Performance

To evaluate the performance of our CGAN model we compare the generated
synthetic orders against the real training data, by looking at their
statistical properties. In particular, we consider the order distributions
over the price, volume, direction and inter-arrival time. In fact, in order to
assess the goodness of a generative model, it is usual to compare the
statistics of real and synthetic data, as the loss value alone is not a good
indicator of convergence (gulrajani2017improved, ).

Figure 6. Comparison of multiple CGAN synthetic traces (thin colored lines)
and real TSLA real trace (fat red line).

Figure 5 shows the distributions of several useful features for the synthetic
and real traces. Specifically, the columns from left to right, plot the volume
(i.e., number of shares), the price, the direction (i.e., buy or sell order),
and the interarrival time distribution of the orders. The real data refers to
TSLA stock on the 2nd and 3rd of May 2019. All the order features are
normalized as in Section 4.3. The x-axis shows both the normalized form
between $[-1,1]$ and the unnormalized value.

The first row shows the distributions at the beginning of the training process
(epoch number 3), in which the CGAN is clearly unable to generate realistic
orders, mostly producing random output. The second row shows an intermediate
advancement of the training process (epoch number 50). The CGAN learns to
mimic the distributions more accurately, especially for direction and inter-
arrival time. Finally, the third row shows a much more stable CGAN agent,
achieved after 120 training epochs. The agent generates orders resembling real
ones: direction, inter-arrival, price distributions show a pattern that is
close to real. Orders volumes are discretionary for the traders, thus it is
intrinsically hard to match the real distribution.

Figure 6 shows the CGAN ”world” agent ability to replicate trends observed
during training, by generating orders that lead to a price pattern that is
close to that of the training data. The CGAN was trained on a single stock
with a tight time window (i.e., two days). The generated trends allow pursuing
studies on the specific historical scenarios. The chart shows the training
data (solid red line) and 5 generated traces (colored lines), which are
conditioned, at the beginning of the generation process with the historical
data.

###  5.2. Market Impact Experiment

We demonstrated that our CGAN model is able to generate orders and time-series
with properties resembling those of real historical traces. An additional
novelty of our framework is the ability to represent all the market
participants as a whole and respond to the strategy of an experimental agent,
thus allowing interactive simulations. In particular, our CGAN-based ”world”
agent is trained to generate trading limit orders conditioned by the currently
observed market situation. Therefore, as the orders submitted by any
experimental agent alter the market and the order book, they also condition
the CGAN agent and the evolution of the simulation (as shown in Figure 3).

In order to evaluate the reactivity of our framework to the activity of an
experimental agent, we craft an experiment in which a POV agent submits a
burst of buy orders (vyetrenko2019get, ; balch2019evaluate, ). A $\lambda$-POV
strategy is defined by a percentage level $\lambda\in(0,1]$, a wake up period
$\Delta t$, a direction, and a target quantity of shares $\tau$. The agent
wakes up every $\Delta t$ time units, observes the transacted volume in the
market since its last wake up $V_{t}$, and issues buy or sell orders of a
number of shares equal to $\lambda V_{t}$, it does so until $\tau$ shares are
transacted. In our experiments we consider three different $\lambda$-POV agent
configurations, with $\lambda\in[$0.01, 0.1, 0.25$]$, and a wake up period
$\Delta t=1$ min. We allow the agent to place only buy orders between 10:30
and 11:00, and we set $\tau$ equal to the mean daily volume. Thus, the POV
agent will trade around 30 times, and it will stop after 11:00 or when it
reaches $\tau$ transacted shares.

Figure 7. Comparison of a generated time-series with (orange) and without
(blue) a $0.25$-POV execution agent, placing order from 10:30 AM to 11:00 AM.

Figure 8 shows the impact of POV orders on the stock price, in our CGAN-based
framework (right) and in a classic market replay (left) (balch2019evaluate, )
at varying $\lambda$. The plots show the normalized mid-price difference,
between the simulations with and without POV agent. The thick blue line
represents the median mid-price difference, while the blue shaded regions
indicate the 50% and 90% quantiles. Results are averaged over 50 runs. It is
interesting to notice the substantial deviation of the mid-price during and
subsequent to the POV agent activity (from 10:30) with the CGAN-based approach
w.r.t. the market replay. In the market replay scenario, the small deviations
are due to new orders in the historical order book being replayed, and rapidly
vanish. We conclude that our framework can adapt and react to new orders,
showing new unobserved behavior. We believe that this is the first step
towards reactive IABS (balch2019evaluate, ), without the explicit need of
hand-crafted pools of experimental agents.

Figure 7 shows the mid-price traces resulting from a single market impact
experiment. The orange and blue lines are the synthetic data generated by our
framework with and without a $0.25$-POV agent, respectively. It is interesting
to notice that in the scenario with the POV agent, the mid-price exhibits a
substantial deviation w.r.t. the mid-price in the scenario without the POV
agent, also showing a common mean reversion trend to its average levels.

Figure 8. Market replay (left) and CGAN-Based simulation (right) with and
without a $\lambda$-POV execution agent. POV agent places orders between 10:30
AM and 11:00 AM with $\lambda\in[0.01,0.1,0.25]$, respectively on top, middle
and bottom row. POV wake us frequency = 1 minute. The x-axes are truncated and
y-axes expanded for clarity.

###  5.3. Realism through Stylized Facts

Finally, to assess the realism of generated simulations, we train and compare
our framework against TSLA historical data, and two state of the art IABS
configurations proposed in the work (vyetrenko2019get, ). The first IABS
configuration includes 5000 noise and 100 value agents; whereas the second
configuration comprises 5000 noise, 100 value, 1 market maker, and 25 momentum
agents. Both the configurations use historical data to compute the fundamental
value of the traded stock. 111We refer to the work in (vyetrenko2019get, ) for
further details on the configurations and description of the agent strategies.

Figure 9 shows the comparison between the three simulation approaches and
historical data, in terms of stylized facts (see section 3). The upper left
chart shows the one-minute log-returns distributions. Almost all the
simulations show the aggregation normality property, but CGAN-based framework
(green) is the most similar to historical data. The upper right chart shows
the volatility clustering, as a function of time lag. Also here the CGAN-based
framework (green) is the most similar to historical data, showing a slight
decay in the correlation as time lag increases. The Volume/volatility
correlation is instead shown in the bottom left chart, in which both the
simulations fall short to capture the historical trend. However, the CGAN
framework shows the most promising performance, with a similar trend to the
historical data, but shifted to the left. Finally, the bottom right chart
shows the absence of auto-correlation in which almost all the simulations
capture the historical trend, but our framework is still the closest to the
real data.

In summary, our CGAN-based framework outperforms the state-of-art
configurations, with more realistic stylized facts, close to historical data.

Figure 9. Market Stylized facts (TSLA) - historical data against simulations.

##  6\. Conclusion

In this paper, we provided a novel framework for synthetic market order
generation in agent-based simulations. The purpose of our framework is to
provide realistic market scenarios to be used for testing trading strategies,
while still ensuring a reactive behavior to the activity of the experimental
agents. Our framework learns the market behavior from historical data-sets,
and models all the market participants as a whole, that is a single agent
reproducing the entire market behavior and allowing realistic and reactive
simulations. In particular, we propose a CGAN to generate synthetic market
orders as a function of the current market state. Integrated in a simulator,
our CGAN-based ”world” agent can generate meaningful orders in response to an
experimental agent. By means of extensive simulations we show that our
framework outperforms previous IABS approaches based on hand-crafted market
configurations, showing better market realism. We also show that our approach
ensures a responsive behavior of the simulated market to the activity of
experimental agents.

## Disclaimer

This paper was prepared for informational purposes by the Artificial
Intelligence Research group of JPMorgan Chase & Co. and its affiliates (“JP
Morgan”), and is not a product of the Research Department of JP Morgan. JP
Morgan makes no representation and warranty whatsoever and disclaims all
liability, for the completeness, accuracy or reliability of the information
contained herein. This document is not intended as investment research or
investment advice, or a recommendation, offer or solicitation for the purchase
or sale of any security, financial instrument, financial product or service,
or to be used in any way for evaluating the merits of participating in any
transaction, and shall not constitute a solicitation under any jurisdiction or
to any person, if such solicitation under such jurisdiction or to such person
would be unlawful.

###### Acknowledgements.

This research was funded in part by JPMorgan Chase Co.

## References

  * [1] M. Arjovsky, S. Chintala, and L. Bottou.  Wasserstein gan, 2017.
  * [2] S. Assefa.  Generating synthetic data in finance: opportunities, challenges and pitfalls.  Challenges and Pitfalls (June 23, 2020), 2020.
  * [3] T. H. Balch, M. Mahfouz, J. Lockhart, M. Hybinette, and D. Byrd.  How to evaluate trading strategies: Single agent market replay or multiple agent interactive simulation?  arXiv preprint arXiv:1906.12010, 2019.
  * [4] D. Borrajo, M. Veloso, and S. Shah.  Simulating and classifying behavior in adversarial environments based on action-state traces: An application to money laundering.  In ACM International Conference on AI in Finance (ICAIF-2020), 2020\.
  * [5] H. Buehler, L. Gonon, J. Teichmann, and B. Wood.  Deep hedging.  Quantitative Finance, 19(8):1271–1291, 2019.
  * [6] D. Byrd.  Explaining agent-based financial market simulation.  arXiv preprint arXiv:1909.11650, 2019.
  * [7] D. Byrd, M. Hybinette, and T. H. Balch.  Abides: Towards high-fidelity multi-agent market simulation.  In Proceedings of the 2020 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, pages 11–22, 2020.
  * [8] A. Chakraborti, I. M. Toke, M. Patriarca, and F. Abergel.  Econophysics review: I. empirical facts.  Quantitative Finance, 11(7):991–1012, 2011.
  * [9] R. Cont.  Empirical properties of asset returns: stylized facts and statistical issues.  Quantitative finance, 1(2):223, 2001.
  * [10] D. Efimov, D. Xu, L. Kong, A. Nefedov, and A. Anandakrishnan.  Using generative adversarial networks to synthesize artificial financial datasets.  arXiv preprint arXiv:2002.02271, 2020.
  * [11] J. D. Farmer, P. Patelli, and I. I. Zovko.  The predictive power of zero intelligence in financial markets.  Proceedings of the National Academy of Sciences, 102(6):2254–2259, 2005.
  * [12] D. K. Gode and S. Sunder.  Allocative efficiency of markets with zero-intelligence traders: Market as a partial substitute for individual rationality.  Journal of political economy, 101(1):119–137, 1993.
  * [13] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  In Advances in Neural Information Processing Systems, volume 27, 2014.
  * [14] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville.  Improved training of wasserstein gans.  arXiv preprint arXiv:1704.00028, 2017.
  * [15] D. Ha and J. Schmidhuber.  World models, 2018.
  * [16] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [17] M. Karpe, J. Fang, Z. Ma, and C. Wang.  Multi-agent reinforcement learning in a realistic limit order book market simulation.  arXiv preprint arXiv:2006.05574.
  * [18] J. Li, X. Wang, Y. Lin, A. Sinha, and M. Wellman.  Generating realistic stock market order streams.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 727–734, 2020.
  * [19] M. Lucic, K. Kurach, M. Michalski, S. Gelly, and O. Bousquet.  Are gans created equal? a large-scale study.  In Advances in Neural Information Processing Systems, volume 31, 2018.
  * [20] C. Macal and M. North.  Tutorial on agent-based modelling and simulation.  Journal of Simulation, 4(3):151–162, 2010.
  * [21] M. Mirza and S. Osindero.  Conditional generative adversarial nets, 2014.
  * [22] NVIDIA.  Gpu nvidia tesla v100.
  * [23] I. Palit, S. Phelps, and W. L. Ng.  Can a zero-intelligence plus model explain the stylized facts of financial time series data?  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pages 653–660, 2012.
  * [24] J. Paulin, A. Calinescu, and M. Wooldridge.  Agent-based modeling for complex financial systems.  IEEE Intelligent Systems, 33(2):74–82, 2018.
  * [25] R. M. Sakia.  The box-cox transformation technique: a review.  Journal of the Royal Statistical Society: Series D (The Statistician), 41(2):169–178, 1992.
  * [26] T. Spooner, J. Fearnley, R. Savani, and A. Koukorinis.  Market making via reinforcement learning.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 434–442, 2018.
  * [27] S. Takahashi, Y. Chen, and K. Tanaka-Ishii.  Modeling financial time-series with generative adversarial networks.  Physica A: Statistical Mechanics and its Applications, 527:121261, 2019.
  * [28] G. The Efficient Reconstructor at Humboldt Universität zu Berlin.  Lobster: Limit order book system.
  * [29] C. Villani.  Optimal transport, old and new. notes for the 2005 saint-flour summer school.  Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, 2008.
  * [30] S. Vyetrenko, D. Byrd, N. Petosa, M. Mahfouz, D. Dervovic, M. Veloso, and T. H. Balch.  Get real: Realism metrics for robust limit order book market simulations.  In ACM International Conference on AI in Finance (ICAIF-2020), 2020\.
  * [31] X. Wang and M. P. Wellman.  Market manipulation: An adversarial learning framework for detection and evasion.  In 29th International Joint Conference on Artificial Intelligence, 2020.
  * [32] H. Wei, Y. Wang, L. Mangu, and K. Decker.  Model-based reinforcement learning for predictions and control for limit order books, 2019.
  * [33] I. Yagi, M. Hoshino, and T. Mizuta.  Analysis of the impact of maker-taker fees on the stock market using agent-based simulation.  In ACM International Conference on AI in Finance (ICAIF-2020), 2020\.
  * [34] J. Yoon, D. Jarrett, and M. van der Schaar.  Time-series generative adversarial networks.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.


Figure S9:  As in Fig. S2 but for kNN estimator ($k=3$), the nonlinear model,
and $n=1000$.

Figure S10:  As in Fig. S2 but for MLP estimator and $n=1000$.

Figure S11:  As in Fig. S2 but for MLP estimator, the nonlinear model, and
$n=1000$.

Figure S12:  As in Fig. S2 but for RF estimator and $n=1000$.

Figure S13:  As in Fig. S2 but for RF estimator, the nonlinear model, and
$n=1000$.

Figure S14:  As in Fig. S2 but for DML estimator and $n=1000$.

Figure S15: As in Fig. S7 but including non-parametric estimators for
$n=1000$.

Figure S16:  As in Fig. S15 but for nonlinear experiments.