summaries: The authors present a distributed implementation of signSGD with majority vote as aggregation. The result is a  communication efficient and byzantine robust distributed training method. This is an interesting and relevant problem. There are two parts in this paper: first the authors prove a convergence guarantee for signSGD, and then they prove that under a weak adversary attack signSGD will be robust to a constant fraction of adversarial nodes. The authors conclude with some limited experiments.

summaries: This paper continues the study of the signSGD algorithm due to (Balles & Hennig, Bernstein et al), where only the sign of a stochastic gradient is used for updating. There are two main results: (1) a slightly refined analysis of two results in Bernstein et al. The authors proved that signSGD continues to converge at the 1/sqrt(T) rate even with minibatch size 1 (instead of T as in Bernstein et al), if the gradient noise is symmetric and unimodal; (2) a similar convergence rate is obtained even when half of the worker machines flip the sign of their stochastic gradients. These results appear to be relatively straightforward extensions of those in Bernstein et al.

abstractText: Training neural networks on large datasets can be accelerated by distributing the workload over a network of machines. As datasets grow ever larger, networks of hundreds or thousands of machines become economically viable. The time cost of communicating gradients limits the effectiveness of using such large machine counts, as may the increased chance of network faults. We explore a particularly simple algorithm for robust, communication-efficient learning—SIGNSGD. Workers transmit only the sign of their gradient vector to a server, and the overall update is decided by a majority vote. This algorithm uses 32× less communication per iteration than full-precision, distributed SGD. Under natural conditions verified by experiment, we prove that SIGNSGD converges in the large and mini-batch settings, establishing convergence for a parameter regime of ADAM as a byproduct. Aggregating sign gradients by majority vote means that no individual worker has too much power. We prove that unlike SGD, majority vote is robust when up to 50% of workers behave adversarially. The class of adversaries we consider includes as special cases those that invert or randomise their gradient estimate. On the practical side, we built our distributed training system in Pytorch. Benchmarking against the state of the art collective communications library (NCCL), our framework—with the parameter server housed entirely on one machine—led to a 25% reduction in time for training resnet50 on Imagenet when using 15 AWS p3.2xlarge machines.

authors:
Dan Alistarh
Demjan Grubic
Jerry Li
Ryota Tomioka
Milan Vojnovic

title: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

authors:
Dan Alistarh
Zeyuan Allen-Zhu
Jerry Li

title: Byzantine Stochastic Gradient Descent

authors:
Lukas Balles
Philipp Hennig

title: Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients

venue: In International Conference on Machine Learning

authors:
Jeremy Bernstein
Yu-Xiang Wang
Kamyar Azizzadenesheli
Animashree Anandkumar

title: signSGD: Compressed Optimisation for Non-Convex Problems

authors:
Peva Blanchard
El Mahdi El Mhamdi
Rachid Guerraoui
Julien Stainer

title: Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent

authors:
James Bradbury
Stephen Merity
Caiming Xiong
Richard Socher

title: Quasi-Recurrent Neural Networks

title: Sui confini della probabilit

venue: Atti del Congresso Internazionale dei Matematici,

authors:
David Carlson
Ya-Ping Hsieh
Edo Collins
Lawrence Carin
Volkan Cevher

title: Stochastic spectral descent for discrete graphical models

venue: IEEE Journal of Selected Topics in Signal Processing,

authors:
El Mahdi El Mhamdi
Rachid Guerraoui
Sébastien Rouault

title: The Hidden Vulnerability of Distributed Learning in Byzantium

title: Neural networks and physical systems with emergent collective computational abilities

venue: Proceedings of the National Academy of Sciences,

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A Method for Stochastic Optimization

venue: In International Conference on Learning Representations (ICLR-15),

authors:
Yujun Lin
Song Han
Huizi Mao
Yu Wang
Bill Dally

title: Deep gradient compression: Reducing the communication bandwidth for distributed training

authors:
Yurii Nesterov
B.T. Polyak

title: Cubic Regularization of Newton Method and its Global Performance

venue: Mathematical Programming,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic Differentiation in PyTorch

venue: In Advances in Neural Information Processing Systems, Autodiff Workshop

title: The Three Sigma Rule

venue: The American Statistician,

authors:
Sashank J. Reddi
Satyen Kale
Sanjiv Kumar

title: On the Convergence of Adam and Beyond

authors:
M. Riedmiller
H. Braun

title: A Direct Adaptive Method for Faster Backpropagation Learning: the RPROP Algorithm

venue: In International Conference on Neural Networks

authors:
Herbert Robbins
Sutton Monro

title: A Stochastic Approximation Method

venue: The Annals of Mathematical Statistics,

authors:
Frank Seide
Hao Fu
Jasha Droppo
Gang Li
Dong Yu

title: 1-Bit Stochastic Gradient Descent and Application to Data-Parallel Distributed Training of Speech DNNs

venue: In Conference of the International Speech Communication Association (INTERSPEECH-14),

authors:
Tijmen Tieleman
Geoffrey Hinton

title: RMSprop. Coursera: Neural Networks for Machine

venue: Learning, Lecture

authors:
Hongyi Wang
Scott Sievert
Shengchao Liu
Zachary B. Charles
Dimitris S. Papailiopoulos
Stephen Wright

title: ATOMO: Communication-efficient Learning via Atomic Sparsification

authors:
Wei Wen
Cong Xu
Feng Yan
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning

authors:
Dong Yin
Yudong Chen
Ramchandran Kannan
Peter Bartlett

title: Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates

heading: 1 INTRODUCTION

text:
The most powerful supercomputer in the world is currently a cluster of over 27,000 GPUs at Oak Ridge National Labs (TOP500, 2018). Distributed algorithms designed for such large-scale systems typically involve both computation and communication: worker nodes compute intermediate results locally, before sharing them with their peers. When devising new machine learning algorithms for distribution over networks of thousands of workers, we posit the following desiderata:
D1 fast algorithmic convergence; D2 good generalisation performance;
D3 communication efficiency; D4 robustness to network faults.
When seeking an algorithm that satisfies all four desiderata D1–4, inevitably some tradeoff must be made. Stochastic gradient descent (SGD) naturally satisfies D1–2, and this has buoyed recent advances in deep learning. Yet when it comes to large neural network models with hundreds of millions of parameters, distributed SGD can suffer large communication overheads. To make matters worse, any faulty SGD worker can corrupt the entire model at any time by sending an infinite gradient, meaning that SGD without modification is not robust.
A simple algorithm with aspirations towards all desiderata D1–4 is as follows: workers send the sign of their gradient up to the parameter server, which aggregates the signs and sends back only the majority decision. We refer to this algorithm as SIGNSGD with majority vote. All communication
∗JB was primary contributor for theory. JZ was primary contributor for large-scale experiments.
to and from the parameter server is compressed to one bit, so the algorithm certainly gives us D3. What’s more, in deep learning folklore sign based methods are known to perform well, indeed inspiring the popular RMSPROP and ADAM optimisers (Balles & Hennig, 2018), giving hope for D1. As far as robustness goes, aggregating gradients by a majority vote denies any individual worker too much power, suggesting it may be a natural way to achieve D4.
In this work, we make the above aspirations rigorous. Whilst D3 is immmediate, we provide the first convergence guarantees for SIGNSGD in the mini-batch setting, providing theoretical grounds for D1. We show how theoretically the behaviour of SIGNSGD changes as gradients move from high to low signal-to-noise ratio. We also extend the theory of majority vote to show that it achieves a notion of Byzantine fault tolerance. A distributed algorithm is Byzantine fault tolerant (Blanchard et al., 2017) if its convergence is robust when up to 50% of workers behave adversarially. The class of adversaries we consider contains interesting special cases, such as robustness to a corrupted worker sending random bits, or a worker that inverts their gradient estimate. Though our adversarial model is not the most general, it is interesting as a model of network faults, and so gives us D4.
Next, we embark on a large-scale empirical validation of our theory. We implement majority vote in the Pytorch deep learning framework, using CUDA kernels to bit pack sign tensors down to one bit. Our results provide experimental evidence for D1–D4. Comparing our framework to NCCL (the state of the art communications library), we were able to speed up Imagenet training by 25% when distributing over 7 to 15 AWS p3.2xlarge machines, albeit at a slight loss in generalisation.
Finally, in an interesting twist, the theoretical tools we develop may be brought to bear on a seemingly unrelated problem in the machine learning literature. Reddi et al. (2018) proved that the extremely popular ADAM optimiser in general does not converge in the mini-batch setting. This result belies the success of the algorithm in a wide variety of practical applications. SIGNSGD is equivalent to a special case of ADAM, and we establish the convergence rate of mini-batch SIGNSGD for a large class of practically realistic objectives. Therefore, we expect that these tools should carry over to help understand the success modes of ADAM. Our insight is that gradient noise distributions in practical problems are often unimodal and symmetric because of the Central Limit Theorem, yet Reddi et al. (2018)’s construction relies on bimodal noise distributions.

heading: 2 RELATED WORK

text:
For decades, neural network researchers have adapted biologically inspired algorithms for efficient hardware implementation. Hopfield (1982), for example, considered taking the sign of the synaptic weights of his memory network for readier adaptation into integrated circuits. This past decade, neural network research has focused on training feedforward networks by gradient descent (LeCun et al., 2015). It is natural to ask what practical efficiency may accompany simply taking the sign of the backpropagated gradient. In this section, we explore related work pertaining to this question.
Deep learning: whilst stochastic gradient descent (SGD) is the workhorse of machine learning (Robbins & Monro, 1951), algorithms like RMSPROP (Tieleman & Hinton, 2012) and ADAM (Kingma & Ba, 2015) are also extremely popular neural net optimisers. These algorithms have their
Algorithm 1 SIGNUM with majority vote, the proposed algorithm for distributed optimisation. Good default settings for the tested machine learning problems are η = 0.0001 and β = 0.9, though tuning is recommended. All operations on vectors are element-wise. Setting β = 0 yields SIGNSGD. Require: learning rate η > 0, momentum constant β ∈ [0, 1), weight decay λ ≥ 0, mini-batch size n, initial point x held by each of M workers, initial momentum vm ← 0 on mth worker
repeat on mth worker g̃m ← 1n ∑n i=1 stochasticGradient(x) . mini-batch gradient
vm ← (1− β)g̃m + βvm . update momentum push sign(vm) to server . send sign momentum
on server V ← ∑M m=1 sign(vm) . aggregate sign momenta
push sign(V ) to each worker . broadcast majority vote on every worker
x← x− η(sign(V ) + λx) . update parameters until convergence
roots in the RPROP optimiser (Riedmiller & Braun, 1993), which is a sign-based method similar to SIGNSGD except for a component-wise adaptive learning rate.
Non-convex optimisation: parallel to (and oftentimes in isolation from) advances in deep learning practice, a sophisticated optimisation literature has developed. Nesterov & Polyak (2006) proposed cubic regularisation as an algorithm that can escape saddle points and provide guaranteed convergence to local minima of non-convex functions. This has been followed up by more recent works such as NATASHA (Allen-Zhu, 2017) that use other theoretical tricks to escape saddle points. It is still unclear how relevant these works are to deep learning, since it is not clear to what extent saddle points are an obstacle in practical problems. We avoid this issue altogether and satisfy ourselves with establishing convergence to critical points.
Gradient compression: prior work on gradient compression generally falls into two camps. In the first camp, algorithms like QSGD (Alistarh et al., 2017), TERNGRAD (Wen et al., 2017) and ATOMO (Wang et al., 2018) use stochastic quantisation schemes to ensure that the compressed stochastic gradient remains an unbiased approximation to the true gradient. These works are therefore able to bootstrap existing SGD convergence theory. In the second camp, more heuristic algorithms like 1BITSGD (Seide et al., 2014) and deep gradient compression (Lin et al., 2018) pay less attention to theoretical guarantees and focus more on practical performance. These algorithms track quantisation errors and feed them back into subsequent updates. The commonality between the two camps is an effort to, one way or another, correct for bias in the compression.
SIGNSGD with majority vote takes a different approach to these two existing camps. In directly employing the sign of the stochastic gradient, the algorithm unabashedly uses a biased approximation of the stochastic gradient. Carlson et al. (2016) and Bernstein et al. (2018) provide theoretical and empirical evidence that signed gradient schemes can converge well in spite of their biased nature. Their theory only applies in the large batch setting, meaning the theoretical results are less relevant to deep learning practice. Still Bernstein et al. (2018) showed promising experimental results in the mini-batch setting. An appealing feature of majority vote is that it naturally leads to compression in both directions of communication between workers and parameter server. As far as we are aware, all existing gradient compression schemes lose compression before scattering results back to workers.
Byzantine fault tolerant optimisation: the problem of modifying SGD to make it Byzantine fault tolerant has recently attracted interest in the literature (Yin et al., 2018). For example, Blanchard et al. (2017) proposed KRUM, which operates by detecting and excluding outliers in the gradient aggregation. Alistarh et al. (2018) propose BYZANTINESGD which instead focuses on detecting and eliminating adversaries. Clearly both these strategies incur overheads, and eliminating adversaries precludes the possibility that they might reform. El Mhamdi et al. (2018) point out that powerful adversaries may steer convergence to bad local minimisers. We see majority vote as a natural way to protect against less malign faults such as network errors, and thus satisfy ourselves with convergence guarantees to critical points without placing guarantees on their quality.

heading: 3 THEORY

heading: 3.1 ASSUMPTIONS

text:
We aim to develop an optimisation theory that is relevant for real problems in deep learning. For this reason, we are careful about the assumptions we make. For example, we do not assume convexity because neural network loss functions are typically not convex. Though we allow our objective function to be non-convex, we insist on a lower bound to enable meaningful convergence results. Assumption 1 (Lower bound). For all x and some constant f∗, we have objective value f(x) ≥ f∗.
Our next two assumptions of Lipschitz smoothness and bounded variance are standard in the stochastic optimisation literature (Allen-Zhu, 2017). That said, we give them in a component-wise form. This allows our convergence results to encode information not just about the total noise level and overall smoothness, but also about how these quantities are distributed across dimension. Assumption 2 (Smooth). Let g(x) denote the gradient of the objective f(.) evaluated at point x. Then ∀x, y we require that for some non-negative constant ~L := [L1, ..., Ld]∣∣∣f(y)− [f(x) + g(x)T (y − x)]∣∣∣ ≤ 1
2 ∑ i Li(yi − xi)2.
Assumption 3 (Variance bound). Upon receiving query x ∈ Rd, the stochastic gradient oracle gives us an independent, unbiased estimate g̃ that has coordinate bounded variance:
E[g̃(x)] = g(x), E [ (g̃(x)i − g(x)i)2 ] ≤ σ2i
for a vector of non-negative constants ~σ := [σ1, .., σd].
Our final assumption is non-standard. We assume that the gradient noise is unimodal and symmetric. Clearly, Gaussian noise is a special case. Note that even for a moderate mini-batch size, we expect the central limit theorem to kick in rendering typical gradient noise distributions close to Gaussian. See Figure 2 for noise distributions measured whilst training resnet18 on Cifar-10. Assumption 4 (Unimodal, symmetric gradient noise). At any given point x, each component of the stochastic gradient vector g̃(x) has a unimodal distribution that is also symmetric about the mean.
Showing how to work with this assumption is a key theoretical contribution of this work. Combining Assumption 4 with an old tail bound of Gauss (1823) yields Lemma 1, which will be crucial for guaranteeing mini-batch convergence of SIGNSGD. As will be explained in Section 3.3, this result also constitutes a convergence proof for a parameter regime of ADAM. This suggests that Assumption 4 may more generally be a theoretical fix for Reddi et al. (2018)’s non-convergence proof of mini-batch ADAM, a fix which does not involve modifying the ADAM algorithm itself.

heading: 3.2 MINI-BATCH CONVERGENCE OF SIGNSGD

text:
With our assumptions in place, we move on to presenting our theoretical results, which are all proved in Appendix C. Our first result establishes the mini-batch convergence behaviour of SIGNSGD. We will first state the result and make some remarks. We provide intuition for the proof in Section 3.3.
Theorem 1 (Non-convex convergence rate of mini-batch SIGNSGD). Run the following algorithm for K iterations under Assumptions 1 to 4: xk+1 = xk − η sign(g̃k). Set the learning rate, η, and mini-batch size, n, as
η = √ f0 − f∗ ‖~L‖1K , n = 1.
LetHk be the set of gradient components at step k with large signal-to-noise ratio Si := |gk,i| σi , i.e. Hk := { i ∣∣∣Si > 2√3}. We refer to 2√3 as the ‘critical SNR’. Then we have
1
K K−1∑ k=0 E ∑ i∈Hk |gk,i|+ ∑ i 6∈Hk g2k,i σi  ≤ 3 √ ‖~L‖1(f0 − f∗) N .
where N = K is the total number of stochastic gradient calls up to step K.
Theorem 1 provides a bound on the average gradient norm. The right hand side of the bound decays like O ( 1√ N ) , establishing convergence to points of the objective where the gradient vanishes.
Remark 1: mini-batch SIGNSGD attains the same O (
1√ N
) non-convex convergence rate as SGD.
Remark 2: the gradient appears as a mixed norm: an `1 norm for high SNR components, and a weighted `2 norm for low SNR compoenents.
Remark 3: we wish to understand the dimension dependence of our bound. We may simplify matters by assuming that, during the entire course of optimisation, every gradient component lies in the low SNR regime. Figure 3 shows that this is almost true when training a resnet18 model. In this limit, the bound becomes:
1
K K−1∑ k=0 E [ d∑ i=1 g2k,i σi ] ≤ 3 √ ‖~L‖1(f0 − f∗) N .
Further assume that we are in a well-conditioned setting, meaning that the variance is distributed uniformly across dimension (σ2i = σ2
d ), and every weight has the same smoothness constant (Li = L). σ2 is the total variance bound, and L is the conventional Lipschitz smoothness. These are the
quantities which appear in the standard analysis of SGD. Then we get
1
K K−1∑ k=0 E‖gk‖22 ≤ 3σ √ L(f0 − f∗) N .
The factors of dimension d have conveniently cancelled. This illustrates that there are problem geometries where mini-batch SIGNSGD does not pick up an unfavourable dimension dependence.

heading: 3.3 THE SUBTLETIES OF MINI-BATCH CONVERGENCE

text:
Intuitively, the convergence analysis of SIGNSGD depends on the probability that a given bit of the sign stochastic gradient vector is incorrect, or P[sign(g̃i) 6= sign(gi)]. Lemma 1 provides a bound on this quantity under Assumption 4 (unimodal symmetric gradient noise).
Lemma 1 (Bernstein et al. (2018)). Let g̃i be an unbiased stochastic approximation to gradient component gi, with variance bounded by σ2i . Further assume that the noise distribution is unimodal and symmetric. Define signal-to-noise ratio Si :=
|gi| σi . Then we have that
P[sign(g̃i) 6= sign(gi)] ≤
{ 2 9 1 S2i
if Si > 2√3 , 1 2 − Si 2 √ 3 otherwise
which is in all cases less than or equal to 12 .
The bound characterises how the failure probability of a sign bit depends on the signal-to-noise ratio (SNR) of that gradient component. Intuitively as the SNR decreases, the quality of the sign estimate should degrade. The bound is important since it tells us that, under conditions of unimodal symmetric gradient noise, even at extremely low SNR we still have that P[sign(g̃i) 6= sign(gi)] ≤ 12 . This means that even when the gradient is very small compared to the noise, the sign stochastic gradient still tells us, on average, useful information about the true gradient direction, allowing us to guarantee convergence as in Theorem 1.
Without Assumption 4, the mini-batch algorithm may not converge. This is best appreciated with a simple example. Consider a stochastic gradient component g̃ with bimodal noise:
g̃ = { 50 with probability 0.1; −1 with probability 0.9.
The true gradient g = E[g̃] = 4.1 is positive. But the sign gradient sign(g̃) is negative with probability 0.9. Therefore SIGNSGD will tend to move in the wrong direction for this noise distribution.
Note that SIGNSGD is a special case of the ADAM algorithm (Balles & Hennig, 2018). To see this, set β1 = β2 = = 0 in ADAM, and the ADAM update becomes:
− g̃√ g̃2 = − g̃ |g̃| = −sign(g̃)
This correspondence suggests that Assumption 4 should be useful for obtaining mini-batch convergence guarantees for ADAM. Note that when Reddi et al. (2018) construct toy divergence examples for ADAM, they rely on bimodal noise distributions which violate Assumption 4.
We conclude this section by noting that without Assumption 4, SIGNSGD can still be guaranteed to converge. The trick is to use a “large” batch size that grows with the number of iterations. This will ensure that the algorithm stays in the high SNR regime where the failure probability of the sign bit is low. This is the approach taken by both Carlson et al. (2016) and Bernstein et al. (2018).

heading: 3.4 ROBUSTNESS OF CONVERGENCE

text:
We will now study SIGNSGD’s robustness when distributed by majority vote. We model adversaries as machines that may manipulate their stochastic gradient as follows.
Definition 1 (Blind multiplicative adversary). A blind multiplicative adversary may manipulate their stochastic gradient estimate g̃t at iteration t by element-wise multiplying g̃t with any vector vt of their choice. The vector vt must be chosen before observing g̃t, so the adversary is ‘blind’. Some interesting members of this class are:
(i) adversaries that arbitrarily rescale their stochastic gradient estimate;
(ii) adversaries that randomise the sign of each coordinate of the stochastic gradient;
(iii) adversaries that invert their stochastic gradient estimate.
SGD is certainly not robust to rescaling since an adversary could set the gradient to infinity and corrupt the entire model. Our algorithm, on the other hand, is robust to all adversaries in this class. For ease of analysis, here we derive large batch results. We make sure to give results in terms of sample complexityN (and not iteration numberK) to enable fair comparison with other algorithms.
Theorem 2 (Non-convex convergence rate of majority vote with adversarial workers). Run algorithm 1 for K iterations under Assumptions 1 to 4. Switch off momentum and weight decay (β = λ = 0). Set the learning rate, η, and mini-batch size, n, for each worker as
η = √ f0 − f∗ ‖L‖1K , n = K.
Assume that a fraction α < 12 of the M workers behave adversarially according to Definition 1. Then majority vote converges at rate:[
1
K K−1∑ k=0 E ‖gk‖1
]2 ≤ 4√
N
[ 1
1− 2α ‖~σ‖1√ M
+ √ ‖L‖1(f0 − f∗) ]2 where N = K2 is the total number of stochastic gradient calls per worker up to step K.
The result is intuitive: provided there are more machines sending honest gradients than adversarial gradients, we expect that the majority vote should come out correct on average.
Remark 1: if we switch off adversaries by setting the proportion of adversaries α = 0, this result reduces to Theorem 2 in (Bernstein et al., 2018). In this case, we note the 1√
M variance reduction
that majority vote obtains by distributing over M machines, similar to distributed SGD.
Remark 2: the convergence rate degrades as we ramp up α from 0 to 12 . Remark 3: from an optimisation theory perspective, the large batch size is an advantage. This is because when using a large batch size, fewer iterations and rounds of communication are theoretically needed to reach a desired accuracy, since only √ N iterations are needed to reach N samples. But from a practical perspective, workers may be unable to handle such a large batch size in a timely manner. It should be possible to extend the result to the mini-batch setting by combining the techniques of Theorems 1 and 2, but we leave this for future work.

heading: 4 EXPERIMENTS

text:
For our experiments, we distributed SIGNUM (Algorithm 1) by majority vote. SIGNUM is the momentum counterpart of SIGNSGD, where each worker maintains a momentum and transmits the sign momentum to the parameter server at each step. The addition of momentum to SIGNSGD is proposed and studied in (Balles & Hennig, 2018; Bernstein et al., 2018).
We built SIGNUM with majority vote in the Pytorch deep learning framework (Paszke et al., 2017) using the Gloo (2018) communication library. Unfortunately Pytorch and Gloo do not natively support 1-bit tensors, therefore we wrote our own compression code to bit-pack a sign tensor down to an efficient 1-bit representation. We obtained a performance boost by fusing together smaller tensors, which saved on compression and communication costs.
We test against SGD distributed using the state of the art NCCL (2018) communication library. NCCL provides an efficient implementation of allreduce. Our framework is often 4× faster in communication (including the cost of compression) than NCCL, as can be seen in Figure 4. Further code optimisation should bring the speedup closer to the ideal 32×.

heading: 4.1 COMMUNICATION EFFICIENCY

text:
We first benchmark majority vote on the Imagenet dataset. We train a resnet50 model and disitribute learning over 7 to 15 AWS p3.2xlarge machines. These machines each contain one Nvidia Tesla V100 GPU, and AWS lists the connection speed between machines as “up to 10 Gbps”. Results are plotted in Figure 5. Per epoch, distributing by majority vote is able to attain a similar speedup to distributed SGD. But per hour majority vote is able to process more epochs than NCCL, meaning it can complete the 80 epoch training job roughly 25% faster. In terms of overall generalisation, majority vote reaches a slightly degraded test set accuracy. We hypothesise that this may be fixed by inventing a better regularisation scheme or tuning momentum, which we did not do.
In Figure 6 we compare majority vote to ADAM (distributed by NCCL) for training QRNN (Bradbury et al., 2017) on WikiText-103. Majority vote completes an epoch roughly 3 times faster than ADAM, but it reaches a degraded accuracy so that the overall test perplexity after 2 hours ends up being similar. In Figure 7 we show that majority vote has superior convergence to the ‘theory’ version of QSGD that Alistarh et al. (2017) develop. Convergence is similar for the ‘max’ version that Alistarh et al. (2017) use in their experiments. Additional results are given in Appendix A.

heading: 4.2 ROBUSTNESS

text:
In this section we test the robustness of SIGNUM with majority vote to Byzantine faults. Again we run tests on the Imagenet dataset, training resnet50 across 7 AWS p3.2xlarge machines. Our adversarial workers take the sign of their stochastic gradient calculation, but send the negation to the parameter server. Our results are plotted in Figure 8. In the left hand plot, all experiments were carried out using hyperparameters tuned for the 0% adversarial case. Weight decay was not used in these experiments to simplify matters. We see that learning is tolerant of up to 43% (3 out of 7) machines behaving adversarially. The 43% adversarial case was slightly unstable (Figure 8, left), but re-tuning the learning rate for this specific case stabilised learning (Figure 8, right).
In Figure 9 we compare majority vote to MULTI-KRUM (Blanchard et al., 2017) with a security level of f = 2. When the number of adversaries exceeds f , MULTI-KRUM fails catastrophically in our experiments, whereas SIGNSGD fails more gracefully. Note that MULTI-KRUM requires 2f + 2 < M , therefore f = 2 is the maximum possible security level for these experiments with M = 7 workers.

heading: 5 DISCUSSION AND CONCLUSION

text:
We have analysed the theoretical and empirical properties of a very simple algorithm for distributed, stochastic optimisation. We have shown that SIGNSGD with majority vote aggregation is robust and communication efficient, whilst its per-iteration convergence rate is competitive with SGD for training large-scale convolutional neural nets on image datasets. We believe that it is important to understand this simple algorithm before going on to devise more complex learning algorithms.
An important takeaway from our theory is that mini-batch SIGNSGD should converge if the gradient noise is Gaussian. This means that the performance of SIGNSGD may be improved by increasing the per-worker mini-batch size, since this should make the noise ‘more Gaussian’ according to the Central Limit Theorem.
We will now give some possible directions for future work. Our implementation of majority vote may be further optimised by breaking up the parameter server and distributing it across machines. This would prevent a single machine from becoming a communication bottleneck as in our experiments. Though our framework speeds up Imagenet training, we still have a test set gap. Future work could attempt to devise new regularisation schemes for signed updates to close this gap. Promising future work could also explore the link between SIGNSGD and model compression. Signed updates force the weights to live on a lattice, facilitating compression of the resulting model.

heading: ACKNOWLEDGMENTS

text:
We would like to thank Yu-Xiang Wang, Alexander Sergeev, Soumith Chintala, Pieter Noordhuis, Hongyi Wang, Scott Sievert and El Mahdi El Mhamdi for useful discussions.
KA is supported in part by NSF Career Award CCF-1254106. AA is supported in part by a Microsoft Faculty Fellowship, Google Faculty Award, Adobe Grant, NSF Career Award CCF-1254106, and AFOSR YIP FA9550-15-1-0221.

heading: A ADDITIONAL EXPERIMENTS

heading: B BITS SENT PER ITERATION: SIGNSGD VS. QSGD

text:
In this section, we perform theoretical calculations of the number of bits sent per iteration in distributed training. We compare SIGNSGD using majority vote aggregation to two forms of QSGD (Alistarh et al., 2017). These calculations give the numbers in the table in Figure 7.
The communication cost of SIGNSGD with majority vote is trivially 2Md bits per iterations, since at each iteration M machines send d-dimensional sign vectors up to the server, and the server sends back one d-dimensional sign vector to all M machines.
There are two variants of QSGD given in (Alistarh et al., 2017). The first we refer to as L2 QSGD which is the version developed in the theory section of (Alistarh et al., 2017). The second we refer to as max QSGD which is the version actually used in their experiments. For each version we compute the number of bits sent for the highest compression version of the algorithm, which is a ternary quantisation (snapping gradient components into {0,±1}). We refer to this as 1-bit QSGD. The higher precision versions of QSGD will send more bits per iteration.
1-bit L2 QSGD takes a gradient vector g and snaps ith coordinate gi to sign(gi) with probability |gi| ‖g‖2 and sets it to zero otherwise. Therefore the expected number of bits set to ±1 is bounded by
E[#bits] = ∑ i=1 |gi| ‖g‖2 = ‖g‖1 ‖g‖2 ≤ √ d.
To send a vector compressed in this way, for each non-zero component 1 bit is needed to send the sign and log d bits are needed to send the index. Therefore sending a vector compressed by 1-bit L2 QSGD requires at most √ d(1 + log d) bits.
In the experiments in Figure 7 we see that the ‘2-way’ version of 1-bit L2 QSGD (which recompresses the aggregated compressed gradients) converges very poorly. Therefore it makes sense to use the 1-way version where the aggregated compressed gradient is not recompressed. A sensible way to enact this is to have each of the M workers broadcast their compressed gradient vector to all other workers. This has a cost of (M − 1) √ d(1 + log d) bits for each of the M workers, and from this we get the total cost of O(M2 √ d log d) for 1-bit L2 QSGD.
The final algorithm to characterise is 1-bit max QSGD. 1-bit max QSGD takes a gradient vector g and snaps ith coordinate gi to sign(gi) with probability
|gi| ‖g‖∞ and sets it to zero otherwise. As
noted in (Alistarh et al., 2017), there are no sparsity guarantees for this algorithm, so compression will generally be much lower than for 1-bit L2 QSGD.
It is easy to see that 1-bit max QSGD requires no more than O(d) bits to compress a d-dimensional vector, since 2d bits can always store d numbers in {0,±1}. To see that we can’t generally do better than O(d) bits, notice that 1-bit max QSGD leaves sign vectors invariant, and thus the compressed form of a sign vector requires exactly d bits. The natural way to enact 1-bit max QSGD is with a two-way compression where the M workers each send an O(d)-bit compressed gradient up to the server, and the server sends back an O(d)-bit compressed aggregated result back to the M workers. This gives a number of bits sent per iteration of O(Md).
For very sparse vectors 1-bit max QSGD will compress much better than indicated above. For a vector g with a single non-zero entry, 1-bit max QSGD will set this entry to 1 and keep the rest zero, thus requiring only log d bits to send the index of the non-zero entry. But it is not clear whether these extremely sparse vectors appear in deep learning problems. In the experiments in Figure 7, 1-bit max QSGD led to compressed vectors that were 5×more compressed than SIGNSGD—in our experimental setting this additional improvement turned out to be small relative to the time cost of backpropagation.

heading: C PROOFS

text:
C.1 ACCURACY OF THE SIGN STOCHASTIC GRADIENT
Lemma 1 (Bernstein et al. (2018)). Let g̃i be an unbiased stochastic approximation to gradient component gi, with variance bounded by σ2i . Further assume that the noise distribution is unimodal and symmetric. Define signal-to-noise ratio Si :=
|gi| σi . Then we have that
P[sign(g̃i) 6= sign(gi)] ≤
{ 2 9 1 S2i
if Si > 2√3 , 1 2 − Si 2 √ 3 otherwise
which is in all cases less than or equal to 12 .
Proof. Recall Gauss’ inequality for unimodal random variable X with mode ν and expected squared deviation from the mode τ2 (Gauss, 1823; Pukelsheim, 1994):
P[|X − ν| > k] ≤
{ 4 9 τ2 k2 if k τ > 2√ 3 ,
1− k√ 3τ
otherwise
By the symmetry assumption, the mode is equal to the mean, so we replace mean µ = ν and variance σ2 = τ2.
P[|X − µ| > k] ≤
{ 4 9 σ2 k2 if k σ > 2√ 3 ,
1− k√ 3σ
otherwise
Without loss of generality assume that gi is negative. Then applying symmetry followed by Gauss, the failure probability for the sign bit satisfies:
P[sign(g̃i) 6= sign(gi)] = P[g̃i − gi ≥ |gi|]
= 1
2 P[|g̃i − gi| ≥ |gi|]
≤
{ 2 9 σ2i g2i
if |gi|σ > 2√ 3 ,
1 2 − |gi| 2 √ 3σi
otherwise
=
{ 2 9 1 S2i
if Si > 2√3 , 1 2 − Si 2 √ 3 otherwise
C.2 MINI-BATCH CONVERGENCE GUARANTEES
Theorem 1 (Non-convex convergence rate of mini-batch SIGNSGD). Run the following algorithm for K iterations under Assumptions 1 to 4: xk+1 = xk − η sign(g̃k). Set the learning rate, η, and mini-batch size, n, as
η = √ f0 − f∗ ‖~L‖1K , n = 1.
LetHk be the set of gradient components at step k with large signal-to-noise ratio Si := |gk,i| σi , i.e. Hk := { i ∣∣∣Si > 2√3}. We refer to 2√3 as the ‘critical SNR’. Then we have
1
K K−1∑ k=0 E ∑ i∈Hk |gk,i|+ ∑ i 6∈Hk g2k,i σi  ≤ 3 √ ‖~L‖1(f0 − f∗) N .
where N = K is the total number of stochastic gradient calls up to step K.
Proof. First let’s bound the improvement of the objective during a single step of the algorithm for one instantiation of the noise. I[.] is the indicator function, gk,i denotes the ith component of the true gradient g(xk) and g̃k is a stochastic sample obeying Assumption 3.
First take Assumption 2, plug in the algorithmic step, and decompose the improvement to expose the stochasticity-induced error:
fk+1 − fk ≤ gTk (xk+1 − xk) + d∑ i=1 Li 2 (xk+1 − xk)2i
= −ηgTk sign(g̃k) + η2 d∑ i=1 Li 2
= −η‖gk‖1 + η2
2 ‖~L‖1 + 2η d∑ i=1 |gk,i| I[sign(g̃k,i) 6= sign(gk,i)]
Next we find the expected improvement at time k + 1 conditioned on the previous iterate.
E[fk+1 − fk|xk] ≤ −η‖gk‖1 + η2
2 ‖~L‖1 + 2η d∑ i=1 |gk,i|P[sign(g̃k,i) 6= sign(gk,i)]
By Assumption 4 and Lemma 1 we have the following bound on the failure probability of the sign:
P[sign(g̃i) 6= sign(gi)] ≤
{ 2 9 1 S2i
if Si > 2√3 , 1 2 − Si 2 √ 3 otherwise
≤
{ 1 6 if Si > 2√ 3 ,
1 2 − Si 2 √ 3
otherwise
Substituting this in, we get that
E[fk+1 − fk|xk] ≤ −η‖gk‖1 + η2
2 ‖~L‖1 + 2η ∑ i∈Hk |gk,i| 6 + 2η ∑ i 6∈Hk |gk,i| [ 1 2 − |gk,i| 2 √ 3σi ]
= −η d∑ i=1 |gk,i|+ η2 2 ‖~L‖1 + η ∑ i∈Hk |gk,i| 3 + η ∑ i 6∈Hk |gk,i| − η ∑ i 6∈Hk g2k,i√ 3σi
= −2η 3 ∑ i∈Hk |gk,i| − η ∑ i 6∈Hk g2k,i√ 3σi + η2 2 ‖~L‖1
Interestingly a mixture between an `1 and a variance weighted `2 norm has appeared. Now substitute in the learning rate schedule, and we get:
E[fk+1 − fk|xk] ≤ − √ f0 − f∗ ‖~L‖1K 2 3 ∑ i∈Hk |gk,i|+ 1√ 3 ∑ i 6∈Hk g2k,i σi + f0 − f∗ 2K
≤ − √
f0 − f∗ 3‖~L‖1K ∑ i∈Hk |gk,i|+ ∑ i 6∈Hk g2k,i σi + f0 − f∗ 2K
Now extend the expectation over the randomness in the trajectory and telescope over the iterations:
f0 − f∗ ≥ f0 − E[fK ]
= E [ K−1∑ k=0 fk − fk+1 ]
≥ √
f0 − f∗ 3‖~L‖1K K−1∑ k=0 E ∑ i∈Hk |gk,i|+ ∑ i 6∈Hk g2k,i σi − f0 − f∗ 2
Finally, rearrange and substitute in N = K to yield the bound
1
K K−1∑ k=0 E ∑ i∈Hk |gk,i|+ ∑ i 6∈Hk g2k,i σi  ≤ 3√3 2 √ ‖~L‖1(f0 − f∗) N ≤ 3 √ ‖~L‖1(f0 − f∗) N .
C.3 ROBUSTNESS OF MAJORITY VOTE
Theorem 2 (Non-convex convergence rate of majority vote with adversarial workers). Run algorithm 1 for K iterations under Assumptions 1 to 4. Switch off momentum and weight decay (β = λ = 0). Set the learning rate, η, and mini-batch size, n, for each worker as
η = √ f0 − f∗ ‖L‖1K , n = K.
Assume that a fraction α < 12 of the M workers behave adversarially according to Definition 1. Then majority vote converges at rate:[
1
K K−1∑ k=0 E ‖gk‖1
]2 ≤ 4√
N
[ 1
1− 2α ‖~σ‖1√ M
+ √ ‖L‖1(f0 − f∗) ]2 where N = K2 is the total number of stochastic gradient calls per worker up to step K.
Proof. We need to bound the failure probability of the vote. We can then use this bound to derive a convergence rate. We will begin by showing this bound is worst when the adversary inverts the signs of the sign stochastic gradient.
Given an adversary from the class of blind multiplicative adversaries (Definition 1), the adversary may manipulate their stochastic gradient estimate g̃t into the form vt ⊗ g̃t. Here vt is a vector of the adversary’s choosing, and ⊗ denotes element-wise multiplication. The sign of this quantity obeys:
sign(vt ⊗ g̃t) = sign(vt)⊗ sign(g̃t).
Therefore, the only thing that matters is the sign of vt, and rescaling attacks are immediately nullified. For each component of the stochastic gradient, the adversary must decide (without observing gt, since the adversary is blind) whether or not they would like to invert the sign of that component. We will now show that the failure probability of the vote is always larger when the adversary decides to invert (by setting every component of sign(vt) to −1). Our analysis will then proceed under this worst case.
For a gradient component with true value g, let random variable Z ∈ [0,M ] denote the number of correct sign bits received by the parameter server. For a given adversary, we may decompose Z into the contribution from that adversary and a residual termX from the remaining workers (both regular and adversarial):
Z(sign(v)) = X + I[sign(v)sign(g̃) = sign(g)],
where g̃ is the adversary’s stochastic gradient estimate for that component, v is the adversary’s chosen scalar for that component, and I is the 0-1 indicator function. We are considering Z to be a function of sign(v).
But by Assumption 4 and Lemma 1, we see that I[+1 × sign(g̃) = sign(g)] is a Bernoulli random variable with success probability p ≥ 12 . On the other hand, I[−1×sign(g̃) = sign(g)] is a Bernoulli random variable with success probability q = 1− p ≤ 12 .
The essential quantity in our analysis is the probability that more than half the workers provide the correct sign bit. But from the preceding discussion, this clearly obeys:
P [ Z(+1) ≤ M
2
] = P [ X + I[+1× sign(g̃) = sign(g)] ≤ M
2 ] ≤ P [ X + I[−1× sign(g̃) = sign(g)] ≤ M
2 ] = P [ Z(−1) ≤ M
2
] .
As we will see below, the implication of this is that our bounds always worse under the setting v = −1, and so we will adopt v = −1 hereon. It is worth remarking that blindness in the definition of blind multiplicative adversaries is important to ensure that I[sign(v)sign(g̃) = sign(g)] is indeed a random variable as described above. Were the adversary not blind, then the adversary could in effect deterministically set sign(v)sign(g̃). Cooperative adversaries, for example, could use this power to control the vote.
Now we restrict to our worst case blind multiplicative adversaries, that always choose to invert their sign stochastic gradient estimate. So, we have (1− α)M good machines and αM adversaries. The good workers each compute a stochastic gradient estimate, take its sign and transmit this to the server. The bad workers follow an identical procedure except they negate their sign bits prior to transmission to the server. It is intuitive that because the proportion of adversaries α < 12 , the good workers will win the vote on average. To make this rigorous, we will need Lemma 1 and Cantelli’s inequality. Cantelli (1928) tells us that for a random variable X with mean µ and variance σ2:
P[µ−X ≥ |λ|] ≤ 1 1 + λ 2
σ2
(1)
For a given gradient component, again let random variable Z ∈ [0,M ] denote the number of correct sign bits received by the parameter server. Let random variablesG andB denote the number of good and bad workers (respectively) who (possibly inadvertently) sent the correct sign bit. Then, letting p be the probability that a good worker computed the correct sign bit, q := 1− p and := p− 12 we can decompose Z as follows:
Z = G+B
G ∼ binomial[(1− α)M,p] B ∼ binomial[αM, q]
E[Z] = (1− α)Mp+ αMq = M 2 + (1− 2α)M
Var[Z] = (1− α)Mpq + αMpq =M ( 1
4 − 2
) .
The vote only fails if Z < M2 which happens with probability P [ Z ≤ M
2
] = P [ E[Z]− Z ≥ E[Z]− M
2 ] ≤ 1
1 + (E[Z]−M2 )2
Var[Z]
by Cantelli’s inequality
≤ 1 2
√ Var[Z]
(E[Z]− M2 )2 since 1 + x2 ≥ 2x
= 1
2
√ M ( 1 4 − 2 ) (1− 2α)2M2 2
= 1
2
√ 1
4 2 − 1
(1− 2α) √ M
We now need to substitute in a bound on . Assumption 4 and Lemma 1 tell us that
= 1
2 − q ≥
{ 1 2 − 2 9 1 S2 if S > 2√ 3 ,
S 2 √ 3
otherwise.
From this we can derive that 14 2 − 1 < 4 S2 as follows. First take the case S ≤ 2√ 3
. Then 2 ≥ S 2
12
and 14 2 − 1 ≤ 3 S2 − 1 < 4 S2 . Now take the case S > 2√ 3 . Then ≥ 12 − 2 9 1 S2 and we have
1 4 2 − 1 ≤ 1 S2
8 9− 16 81 1 S2
1− 89 1 S2 + 1681 1 S4
< 1S2 8 9
1− 89 1 S2 < 4S2 by the condition on S.
We have now completed the first part of the proof by showing the key statement that for the ith gradient component with signal to noise ratio Si := |gi| σi
, the failure probability of the majority vote is bounded by
P[vote fails for ith coordinate] = P [ Zi ≤ M
2
] ≤ 1
(1− 2α) √ MSi
(?)
The second stage of the proof will proceed by straightforwardly substituting this bound into the convergence analysis of SIGNSGD from Bernstein et al. (2018).
First let’s bound the improvement of the objective during a single step of the algorithm for one instantiation of the noise. I[.] is the indicator function, gk,i denotes the ith component of the true gradient g(xk) and sign(Vk) is the outcome of the vote at the kth iteration.
First take Assumption 2, plug in the step from Algorithm 1, and decompose the improvement to expose the error induced by stochasticity and adversarial workers:
fk+1 − fk ≤ gTk (xk+1 − xk) + d∑ i=1 Li 2 (xk+1 − xk)2i
= −ηgTk sign(Vk) + η2 d∑ i=1 Li 2
= −η‖gk‖1 + η2
2 ‖~L‖1 + 2η d∑ i=1 |gk,i| I[sign(Vk,i) 6= sign(gk,i)]
Next we find the expected improvement at time k + 1 conditioned on the previous iterate.
E[fk+1 − fk|xk] ≤ −η‖gk‖1 + η2
2 ‖~L‖1 + 2η d∑ i=1 |gk,i|P[sign(Vk,i) 6= sign(gk,i)]
From (?), we have that the probability of the vote failing for the ith coordinate is bounded by
P[sign(Vk,i) 6= sign(gk,i)] ≤ σk,i
(1− 2α) √ M |gk,i|
where σk,i refers to the variance of the kth stochastic gradient estimate, computed over a mini-batch of size n. Therefore, by Assumption 3, we have that σk,i ≤ σi/ √ n.
We now substitute these results and our learning rate and mini-batch settings into the expected improvement:
E[fk+1 − fk|xk] ≤ −η‖gk‖1 + 2η√ n ‖~σ‖1 (1− 2α) √ M + η2 2 ‖~L‖1
= − √ f0 − f∗ ‖L‖1K ‖gk‖1 + 2 √ f0 − f∗ ‖L‖1K2 ‖~σ‖1 (1− 2α) √ M + f0 − f∗ 2K
Now extend the expectation over randomness in the trajectory, and perform a telescoping sum over the iterations:
f0 − f∗ ≥ f0 − E[fK ]
= K−1∑ k=0 E[fk − fk+1]
≥ K−1∑ k=0 E [√ f0 − f∗ ‖L‖1K ‖gk‖1 − 2 √ f0 − f∗ ‖L‖1K2 ‖~σ‖1 (1− 2α) √ M − f0 − f∗ 2K ]
= √ K(f0 − f∗) ‖L‖1 E [ 1 K K−1∑ k=0 ‖gk‖1 ] − 2 √ f0 − f∗ ‖L‖1 ‖~σ‖1 (1− 2α) √ M − f0 − f∗ 2
We can rearrange this inequality to yield the rate:
1
K K−1∑ k=0 E ‖gk‖1 ≤ 1√ K [ 2 ‖~σ‖1 (1− 2α) √ M + 3 2 √ ‖L‖1(f0 − f∗) ]
E
[ 1
K K−1∑ k=0 ‖gk‖1
] ≤ 1√
K
[ 3
2
√ ‖L‖1(f0 − f∗) + 2‖~σ‖1
]
Since we are growing our mini-batch size, it will take N = O(K2) gradient calls to reach step K. Substitute this in on the right hand side, square the result, use that 32 < 2, and we are done:
[ 1
K K−1∑ k=0 E ‖gk‖1
]2 ≤ 4√
N
[ ‖~σ‖1
(1− 2α) √ M
+ √ ‖L‖1(f0 − f∗)
]2


summaries: This paper proposes a Generative Adversarial Network (GAN) methodology to learn the distribution of limit orders that arrive on an equity market. The proposed approach captures the (mostly discrete) structure in the generated orders; modeling is carried out with a conditional Wasserstein-GAN with a recurrent neural networks in both the generator and critic used to capture the time dependency, and convolutional layers to capture other conditioning information. Experiments are provided on both synthetic and real data.

summaries: The objective of this paper is to use GAN for generating the order stream of stock market data.   The novelty of the paper is the formulation of the order stream and the use of GAN for generating the stock data.   This is a paper for the application of GAN and there are limited contribution to the technical aspect of machine learning.    The paper is clearly written.   There are two main assumptions used in the paper; one is the Markov chain and the second one is the stationary distribution.   In real case, both assumptions are unlikely  to be satisfied.  The orders are mostly affected by many external factors and financial data are known to be non-stationary.  The authors may have to justify these assumptions.

abstractText: We propose an approach to generate realistic and high-fidelity stock market data based on generative adversarial networks. We model the order stream as a stochastic process with finite history dependence, and employ a conditional Wasserstein GAN to capture history dependence of orders in a stock market. We test our approach with actual market and synthetic data on a number of different statistics, and find the generated data to be close to real data.

authors:
Masaya Abe
Hideki Nakayama

title: Deep learning for forecasting stock returns in the cross-section

venue: In Pacific-Asia Conference on Knowledge Discovery and Data Mining,

authors:
Frédéric Abergel
Anana Marouane
Anirban Chakraborti
Aymen Jedidi
Ioane Muni Toke

title: Limit Order Books

authors:
Martin Arjovsky
Soumith Chintala
Léon Bottou

title: Wasserstein generative adversarial networks

venue: In 34th International Conference on Machine Learning,

authors:
Wei Bao
Jun Yue
Yulei Rao

title: A deep learning framework for financial time series using stacked autoencoders and long-short term memory

venue: PLOS One,

authors:
Junyoung Chung
Kyle Kastner
Laurent Dinh
Kratarth Goel
Aaron C Courville
Yoshua Bengio

title: A recurrent latent variable model for sequential data

venue: In Advances in neural information processing systems,

authors:
J. Doyne Farmer
Paolo Patelli
Ilija I. Zovko

title: The predictive power of zero intelligence in financial markets

title: The double auction market institution: A survey. The Double Auction Market Institutions, Theories and Evidence

venue: Addison Wesley,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Ishaan Gulrajani
Faruk Ahmed
Martin Arjovsky
Vincent Dumoulin
Aaron C Courville

title: Improved training of Wasserstein GANs

venue: In Advances in Neural Information Processing Systems,

authors:
M. Hiransha
E.A. Gopalakrishnan
Vijay Krishna Menon
K.P. Soman

title: NSE stock market prediction using deep-learning models

venue: Procedia Computer Science,

title: Agent-based computational finance

venue: Handbook of Computational Economics. Elsevier,

authors:
Mehdi Mirza
Simon Osindero

title: Conditional generative adversarial nets

venue: arXiv preprint arXiv:1411.1784,

authors:
Ofir Press
Amir Bar
Ben Bogin
Jonathan Berant
Lior Wolf

title: Language generation with recurrent generative adversarial networks without pre-training

venue: arXiv preprint arXiv:1706.01399,

title: Financial series prediction: Comparison between precision of time series models and machine learning methods

venue: arXiv preprint arXiv:1706.00948,

authors:
Michael P. Wellman
Elaine Wah

title: Strategic agent-based modeling of financial markets

venue: Russell Sage Foundation Journal of the Social Sciences,

authors:
Shuai Xiao
Mehrdad Farajtabar
Xiaojing Ye
Junchi Yan
Le Song
Hongyuan Zha

title: Wasserstein learning of deep generative point process models

authors:
Shuai Xiao
Hongteng Xu
Junchi Yan
Mehrdad Farajtabar
Xiaokang Yang
Le Song
Hongyuan Zha

title: Learning conditional generative models for temporal point processes

venue: In 32nd AAAI Conference on Artificial Intelligence,

authors:
Yizhe Zhang
Zhe Gan
Kai Fan
Zhi Chen
Ricardo Henao
Dinghan Shen
Lawrence Carin

title: Adversarial feature matching for text generation

venue: arXiv preprint arXiv:1706.03850,

heading: 1 INTRODUCTION

text:
Financial markets are among the most well-studied and closely watched complex multiagent systems in existence. Well-functioning financial markets are critical to the operation of a complex global economy, and small changes in the efficiency or stability of such markets can have enormous ramifications. Accurate modeling of financial markets can support improved design and regulation of these critical institutions. There is a vast literature on financial market modeling, though still a large gap between the state-of-art and the ideal. Analytic approaches provide insight through highly stylized model forms. Agent-based models accommodate greater dynamic complexity, and are often able to reproduce “stylized facts” of real-world markets (LeBaron, 2006). Currently lacking, however, is a simulation capable of producing market data at high fidelity and high realism. Our aim is to develop such a model, to support a range of market design and analysis problems. This work provides a first step, learning a high-fidelity generator from real stock market data streams.
Our main contribution is an approach to produce stock market data that is close to real market data, using a Wasserstein generative adversarial network (WGAN) (Arjovsky et al., 2017). There are many challenges that we overcome as part of this contribution. The first is how to represent a stream of stock market orders as data that can be used in a WGAN. Towards this end, we assume the stock market data stream to arise from a stochastic process with finite (but long) memory dependence. The stochastic process view also makes precise the conditional distribution that the generator is learning as well the joint distribution that the critic of the WGAN distinguishes by estimating the earth-mover distance.
The second main challenge is the design of the network architecture. We choose a conditional WGAN to capture the history dependence of the stochastic process, with both the generator and critic conditional on history of orders and the time of day. A single LSTM layer is used to summarize the history succinctly. The internal architecture of both the generator and critic uses a standard convolutional structure. The generator outputs the next stock market order as well as how this order changes the active orders in the market. Part of the generator output, which updates the active market orders, is produced using a pre-trained network to approximate the deterministic buy and sell order matching in the stock market.
Finally, we experiment with synthetic and real market data. The synthetic data is produced using a stock market simulator that has been used in several agent-based financial studies. The real data was obtained from OneMarketData, a financial data provider and publisher of the OneTick database product. We evaluate the generated data using various statistics such as the distribution of price and quantity of orders, inter-arrival times of orders, and the best bid and best ask evolution over time. We find the generated data matches the corresponding statistics in real data (simulated or actual stock market) closely.

heading: 2 RELATED WORK AND BACKGROUND

text:
WGAN is a popular and well-known variant of GANs (Goodfellow et al., 2014). Most prior work on generation of sequences using GANs has been in the domain of text generation (Press et al., 2017; Zhang et al., 2017). However, since the space of word representations is not continuous, the semantics change with nearby word representation, and given a lack of agreement on the metrics for measuring goodness of sentences, producing good quality text using GANs is still an active area of research. Stock market data does not suffer from this representation problem but the history dependence for stock markets can be much longer than for text generation. In a sequence of recent papers, Xiao et al. (2017; 2018) have introduced GAN-based methods for generating point processes. The proposed methods generate the time for when the next event will occur. The authors have also explored the use of these techniques to generate the time for transaction events in stock markets. Our problem is richer as we aim to generate the actual limit orders including time, order type, price, and quantity information.
Deep neural networks and machine learning techniques have been used on financial data mostly for prediction of transaction price (Hiransha et al., 2018; Bao et al., 2017; Qian, 2017) and for prediction of actual returns (Abe & Nakayama, 2018). As stated, our goal is not market prediction per se, but rather market modeling. Whereas the problems of learning to predict and generate may overlap (e.g., both aim to capture regularity in the domain), the evaluation criteria and end product are quite distinct.
The stock market is a venue where equities or stocks of publicly held companies are traded. Nearly all stock markets follow the continuous double auction (CDA) mechanism (Friedman, 1993). Traders submit bids, or limit orders, specifying the maximum price at which they would be willing to buy a specified quantity of a security, or the minimum price at which they would be willing to sell a quantity.1 The order book is a store that maintains the set of active orders: those submitted but not yet transacted or canceled. CDAs are continuous in the sense that when a new order matches an existing (incumbent) order in the order book, the market clears immediately and the trade is executed at the price of the incumbent order—which is then removed from the order book. Orders may be submitted at any time, and a buy order matches and transacts with a sell order when the limits of both parties can be mutually satisfied. For example, as shown in Figure 1 if a limit buy order with price $10.01 and quantity 100 arrives and the order book has the best offered sell price at $10.01 with quantity 100 then the arriving order matches an incumbent exactly. However, the next buy order does not match any sell, and the following sell order partially matches what is then the best buy in the order book.
The limit order book maintains the current active orders in the market (or the state of the market), which can be described in terms of the quantity offered to buy or sell across the range of price levels. Each order arrival changes the market state, recorded as an update to the order book. After processing any arrived order every buy price level is higher than all sell price levels, and the best bid
1Hence, the CDA is often referred to as a limit-order market in the finance literature (Abergel et al., 2016).
refers to the lowest buy price level and the best ask refers to the highest sell price level. See Figure 1 for an illustration. The order book is often approximated by few (e.g., ten) price levels above the best bid and ten price levels below the best ask; as these prices are typically the ones that dictate the transactions in the market. There are various kinds of traders in a stock market, ranging from individual investors to large investing firms. Thus, there is a wide variation in the nature of orders submitted for a security. We aim to generate orders for a security in aggregate (not per agent) that is close to the aggregate orders generated in a real market. We focus on generating orders and do not attempt to generate transactions in the stock market. This is justified as the CDA mechanism is deterministic and transactions can be determined exactly given a stream of orders.

heading: 3 STOCK-GAN

heading: 3.1 STOCK MARKET ORDERS AS A STOCHASTIC PROCESS

text:
We model stock market orders as a stochastic process. Recall that a stochastic process is a collection of random variables indexed by a set of numbers. We view the stock market orders for a given chunk of time of day ∆t as a collection of vector valued random variable {xi}i∈N indexed by the limit order sequence number in N = {1, . . . , n}. The components of the random vector xi include the time interval di, type of order ti, limit order price pi, limit order quantity qi, and the best bid ai and best ask bi. The time interval di specifies the difference in time between the current order i and previous order i− 1 (in precision of milliseconds); the range of di is finite. The type of order can be buy, sell, cancel buy, or cancel sell (represented in two bits). The price and quantity are restricted to lie within finite bounds. The price range is discretized in units of US cents and the quantity range is discretized in units of the equity (non-negative integers). The best bid and best ask are limit orders themselves and are specified by price and quantity. Observe that we assume the stochastic process depends on the discrete time of day ∆t, which we will make explicit in the next paragraph. We divide the time in a day into 25 equal intervals and ∆t refers to the index of the interval. A visual representation of xi is shown in Figure 2(a).
Following the terminology prevalent for stochastic processes, the above process is discrete time and discrete space (note that discrete time in this terminology here refers to the discreteness of the index set N ). We assume a finite history dependence of the current output xi, that is, P (xi | xi−1, . . . ,∆t) = P (xi | xi−1, . . . ,xi−m,∆t). Such dependence is justified by the observation that recent orders mostly determine the transactions and transaction price in the market as orders that have been in the market for long either get transacted or canceled. Further, the best bid and best ask serves as an (approximate) sufficient statistic for events beyond the history length m. While this process is not a Markov chain, it forms what is known as a higher order Markov chain, which implies that the process given by yi = (xi, . . . ,xi−m+1) is a Markov chain for any given time interval ∆t. We assume that this chain formed by yi has a stationary distribution (i.e., it is irreducible and positive recurrent). A Markov chain is a stationary stochastic process if it starts with its stationary distribution. After some initial mixing time, the Markov chain does reach its stationary distribution, thus, we assume that the process is stationary by throwing away some initial data for the day. Also, for the jumps across two time intervals ∆t, we assume the change in stationary distribution is small and hence the mixing happens very quickly. A stationary process means that P (xi, . . . ,xi−m+1 | ∆t) has the same distribution for any i. In practice we do not know m. However, we can assume a larger history length k + 1 > m, and then it is straightforward to check that yt = (xi, . . . ,xi−k) is a Markov chain and the claims above hold with m− 1 replaced by k. We choose k = 20.

heading: 3.2 WGAN ARCHITECTURE AND WORKING

text:
Given the above stochastic process view of the problem, we design a conditional WGAN with a recurrent architecture to learn the real conditional distribution Pr(xi | xi−1, . . . ,xi−k,∆t). We use the subscript r to refer to real distributions and the subscript g to refer to generated distributions. The real data x1,x2, . . . is a realization of the stochastic process. It is worth noting that even though P (xi, . . . ,xi−k | ∆t) has the same distribution for any i, the realized real data sequence xi, . . .xi−k is correlated with any overlapping sequnce xi+k′ , . . .xi−k+k′ for k ≥ k′ ≥ −k. Our data points for training (stated in detail in the next paragraph) are sequences xi, . . .xi−k, and to ensure independence in a batch we make sure that the sequences chosen in a batch are sufficiently far apart.
Architecture: The architecture is shown in Figure 2. Our proposed WGAN is conditional (Mirza & Osindero, 2014) with both the generator and critic conditioned on a k length history and the time interval ∆t. The history is condensed to one vector using a single LSTM layer. This vector and some uniform noise is fed to a fully connected layer layer followed by a convolutional structure. The generator outputs the next xi (realization of xi) and the critic outputs one real number. Note that when training both generator and critic are fed history from real data, but when the generator executes after training it is fed its own generated data as history. As stated earlier, the generator output includes the best bid and ask. As the best bid and ask can be inferred deterministically from the current order and the previous best bid and ask (for most orders), we use another neural network (with frozen weights during GAN training) to output the best bid and ask. We call this the CDA network. The CDA network is trained separately using a standard MSE loss (see Appendix C).
Critic details: When fed real data, the critic can be seen as a function cw of si = (xi, . . . ,xi−k,∆t), where w are the weights of the critic network. As argued earlier, samples in a batch that are chosen from real data that are spaced at least k apart are i.i.d. samples of Pr. Then for m samples fed to the critic, 1m ∑m i=1 cw(si) estimates Es∼Pr (cw(s)). When fed generated data (with the ten price levels determined from the output order and previous ten levels), by similar reasoning 1m ∑m i=1 cw(si) estimates Es∼Pg (cw(s)) when the samples are sufficiently apart (recall that the history is always real data). Thus, the critic computes the Wasserstein distance between the joint distributions Pr(xi, . . . ,xi−k,∆t) and Pg(xi, . . . ,xi−k,∆t). Further, we use a gradient penalty term in the loss function for the critic instead of clipping weights as proposed in the original WGAN paper (Arjovsky et al., 2017) because of the better performance as revealed in prior work (Gulrajani et al., 2017).
Generator details: The generator learns the conditional distribution Pg(xi | xi−1, . . . ,xi−k,∆t). Along with the real history, the generator represents the distribution Pg(xi, . . . ,xi−k,∆t) = Pg(xi | xi−1, . . . ,xi−k,∆t)Pr(xi−1, . . . ,xi−k,∆t).
The loss functions used is the standard WGAN loss function with a gradient penalty term (Gulrajani et al., 2017). The critic is trained 100 times in each iteration and as already stated, the notable part in constructing the training data is that for each mini-batch the sequence of orders chosen (including history) is far away from any other sequence in that mini-batch (see Appendix C for code snippets).

heading: 4 EXPERIMENTAL RESULTS

text: We apply and evaluate Stock-GAN on two types of data sets composed of orders from an agentbased market simulator and from a real stock market, respectively. We describe each data set in detail and then compare key metrics and distributions of our generated orders with ground truth orders from the agent-based simulator and real stock markets.

heading: 4.1 SYNTHETIC AND REAL DATA

text:
Synthetic data: We first evaluate Stock-GAN on synthetic orders generated from an agent-based market simulator. Previously adopted to study a variety of issues in financial markets (e.g., market making and manipulation), the simulator captures stylized facts of the complex financial market with specified stochastic processes and distributions (Wellman & Wah, 2017). We briefly describe the market simulator below.
In the simulation, the market operates over a finite time horizon. Agents enter and reenter the market according to a Poisson process with an arrival rate of 0.005. On each arrival these traders submit a limit order to the market (replacing their previous order, if any), indicating the price at which they are willing to buy or sell a single unit of the security. The market environment is populated by 32 traders, representing investors. Each investor has an individual valuation for the security made up of private and common components. The common component is represented by a fundamental value, which can be viewed as the intrinsic value of the security. This fundamental value varies over time according to a mean-reverting stochastic process. The private component of value captures the preference contribution of the individual agent’s reason for trading this security at the current time (e.g., investment, liquidity, diversification). The private valuations are drawn from a specified distribution at the start of a simulation. The common and private components are effectively added together to determine each agents valuation of the security. Agents accrue private value on each transaction, and at the end of the trading horizon evaluate their accumulated inventory on the basis of a prediction of the end-time fundamental. Given the market mechanism and valuation model for the simulation, investors pursue their trading objectives by executing a trading strategy in that environment. A popular trading strategy we adopt in the simulator is the zero-intelligence (ZI) strategy (Farmer et al., 2005). The ZI trader shades its bid from its current valuation of the stock by a random offset. We use about 300,000 orders generated by the simulator as our synthetic data. The price output by the simulator is normalized to lie in the interval [−1, 1]. Real data: We obtained real limit-order streams from OneMarketData, who provided access for our research to their OneTick database for selected time periods and securities. The provided data streams comprise order submissions and cancellations across multiple exchanges at millisecond granularity. In experiments, we evaluate in the performance of Stock-GAN on two securities: a small capitalization stock, Patriot National (PN), and a large capitalization stock, Alphabet Inc (GOOG). The two stocks differ in several key aspects, including investment sector, market activity intensity, price range, liquidity etc., and thus their order patterns represent distinct dynamic processes. By training Stock-GAN with historical data for individual stocks, we can generate limit-order streams that capture key characteristics of each.
Relative to our simulated agent-based market, the real market limit orders tend be very noisy including many orders at extreme prices far from the range where transactions occur. Since our interest is primarily on behavior that can affect market outcomes, we focus on limit orders in the relevant range near the best bid and ask. Specifically, in a preprocessing step, we eliminate limit orders that never appear within ten levels of the best bid and ask prices. In the experiment reported here, we use historical real market data of PN during one trading day in August 2016, and GOOG during one trading day in August 2017. After preprocessing, the PN daily order stream has about 20,000 orders and GOOG has about 230,000.

heading: 4.2 EVALUATION STATISTICS

text:
We generate a number of orders equal to the number of real orders used to train the WGAN. We evaluate our generated order stream in comparison to real data using the following statistics:
1. Price. Distribution over price for the day’s limit orders, by order type.
2. Quantity. Distribution over quantity for the day’s limit orders, by order type.
3. Inter-arrival time. Distribution over inter-arrival durations for the day’s limit orders, by order type.
4. Intensity evolution. Number of orders for consecutive 1000-second chunks of time.
5. Best bid/ask evolution. Changes in the best bid and ask over time as new orders arrive.
A note on cancellation: In our generation process, cancellation type orders are not contingent on the order book. We use a heuristic which is to match the generated cancellation order to the closest priced order in the book. Cancellations that are too far from any existing order to be a plausible match are ignored.

heading: 4.3 RESULTS

text:
In describing our results, “real” refers to simulated or actual stock market data and “fake” refers to generated data. Figure 3 presents statistics on buy orders for the three cases when the real data is simulated, PN, or GOOG. For simulated data, the price and inter-arrival distribution matches the real distribution quite closely. The quantity for the simulated data is always one, which is also trivially captured in the generated data. For PN and GOOG, the quantity distribution misses out on some peaks but gets most of the peaks in the real distribution. The inter-arrival time distribution matches quite closely (note that the axis has been scaled for inter-arrival time to highlight the peaks and show the full range of time). The price distribution matches closely for GOOG, but is slightly off for PN, which could be due to the low amount of data for PN.
Figure 4 presents statistics on sell orders for the three cases when the real data is simulated, PN, or GOOG. The results for sell orders are quite similar to buy orders. Results for cancellations are included in the appendix.
Figure 5 presents order intensity as a function of time (number of orders in every chunk of 1000 secs normalized by max number) for the simulated, PN, and GOOG markets. As in the graphs for other statistics, generated WGAN results are compared with the measured intensities in the real data. The intensities show similar trends, though for the real markets there is significant variation. The
differences are particularly large for PN, likely due to the relatively smaller magnitude of trading volume for that stock.
In Figure 6, we show the change in best buy/ask as a function of time for the simulated, PN, and GOOG markets. The generated results looks similar to real data in range and variation over time for simulated data. The similarity to real best bid/ask is better for GOOG than PN, which could possibly be due to more data available for GOOG.
Quantitative measures: The figures till now show that the price distribution appears like a normal distribution and the inter-arrival time appears like a geometric distribution (geometric is discrete version of exponential). We fit these standard distributions to the real price and inter-arrival distribution and compare the total variation (TV) distance between the real and fitted vs real and generated
distributions. The quantity distribution does not appear like any standard distribution, hence we do not evaluate it by fitting. The results in Table 1 show that the generated price distribution is almost as close to the real one as the fitted price distribution. The generated inter-arrival distribution is much closer to the real one than the fitted price distribution. A point to note is that the actual price and quantity is a stochastic process with dependence on history, thus, the fitted distributions will not be helpful in generating the correct intensities or best bid and best ask evolution.
A note on architectural choices: Various parts of our architecture were developed iteratively to improve the results that we obtained in a previous iteration. The input of ∆t to the generator and critic is critical to get the time trend in the intensity for the GOOG stock. The CDA network and the best bid and ask in history was added to improve the results for best bid/ask variation over time.
Comparision with baseline: We also implemented a variational recurrent generative network but found its performance to be worse than our approach (shown in Appendix B).

heading: 5 CONCLUSION

text: Our results reveal that GANs can be used to simulate a stock market. While our results are promising, there are open issues that provide for further research material. One experimental aspect is to try different size of the network in the WGAN, possibly dependent on the data size of the given stock and testing with many different variety of stocks. Another open research issue is to output cancellations in a more intelligent manner than the heuristic approach we use now. Overall, our work provides fertile ground for future research at the intersection of deep learning and finance.

heading: A ADDITIONAL RESULTS

text:
Below we show results for buy order cancellation and sell order cancellation using the exact same measures as for the buy and sell orders in the main paper. The results also are similar to buy or sell results earlier.
(a) Simulated cancel buy order price.(b) Simulated cancel buy order quantity. (c) Simulated cancel buy order interarrival.
(a) Simulated cancel sell order price.(b) Simulated cancel sell order quantity. (c) Simulated cancel sell order interarrival.
B VARIATIONAL RECURRENT NEURAL NETWORK
We use the variational recurrent network as another baseline generative model. The architecture is exactly same as the work Chung et al. (2015). We used the code available at https: //github.com/phreeza/tensorflow-vrnn, but modified it. Our modification was to enable not forcing the output to be Gaussian as done in Chung et al. (2015), as those produced much worse results. Instead, we use a MSE loss. We also modified the input size, etc. to make the neural network structure compatible with our problem. The exact change to the code changing the loss function is shown below:
kl loss = tf kl gaussgauss(enc mu , enc sigma , prior mu , prior sigma) # we replace the maximium likelihood loss with the mse loss below mse loss = tf.losses.mean squared error(y,dec rho) return tf.reduce mean(kl loss + mse loss)
The results in Figure 9 for GOOG buy order only and in Figure 10 for all types of GOOG orders shows that the entropy of the output is high (when comparing price and inter-arrival distributions) and the performance is worse than our GAN. In particular, the generated (fake) price distribution is wider than the real one (or the one generated by the GAN). The generated inter-arrival distribution is almost uniform over the discrete time points and not concentrated at 0. The quantity distribution matches the real one, somewhat similarly like our GAN approach, but it generates some negative values unlike our GAN approach (which could be discarded). The intensity distribution is also somewhat close to the real intensity. The results are similar for other types of orders.

heading: C CODE SNIPPETS

text:
Here we present codes snippets that show the architecture of the GAN. First, we start with the CDA network that is trained independently with MSE loss:
input his = Input(shape=(8,))
G = Sequential(name=’discriminator’) G.add(Dense(256∗3,input dim=8)) G.add(BatchNormalization()) G.add(Activation(’relu’)) G.add(Reshape((16, 16, 3))) G.add(Conv2D(128,(3,3),padding=’same’)) G.add(BatchNormalization()) G.add(Activation(’relu’)) G.add(Conv2D(64, (3,3),padding=’same’)) G.add(BatchNormalization()) G.add(Activation(’relu’)) G.add(Conv2D(32,(3,3),padding=’same’)) G.add(BatchNormalization()) G.add(Activation(’relu’)) G.add(Flatten()) G.add(Dense(4)) output vec = G(input his)
self.net = Model(inputs=input his , outputs=output vec) optimizer = Adam(0.0001) self.net.compile(optimizer=optimizer , loss=’mean squared error’) self.net.summary()
Input LSTM structure for both Generator and Critic are shown below
########### Input for both Generator and Critic ####################### # history orders of shape (self.historyLength , self.orderLength) history = Input(shape=(self.historyLength , self.orderLength), \
name=’history full’) # current time slot: Integer, from 0 to 23 history input = Input(shape=(1,), name=’history time’) # noise input of shape (self.noiseLength) noise input 1 = Input(shape=(self.noiseLength ,), name=’noise input 1’)
# Real order of shape((self.mini batch size ,self.orderLength) truth input = Input(shape=(self.mini batch size ,\
self.orderLength ,1),name=’truth input’)
# lstm at Generator to extract history orders features lstm output = LSTM(self.lstm out length)(history)
# lstm at Critic to extract history orders features lstm output h = LSTM(self.lstm out length ,name=’lstm critic’)(history)
# concatenate history features with noise gen input = Concatenate(axis=−1)([history input ,lstm output ,noise input 1])
The Generator structure is shown below, which includes the trained CDA network
############# Generator ######################## # Input: gen input , shape(self.noiseLength+self.lstm out length + 1)
# Output: gen output 1 , shape(self.mini batch size ,self.orderLength − 4) dropout = 0.5 G 1 = Sequential(name=’generator 1’) G 1.add(Dense((self.orderLength−4)∗self.mini batch size∗100, \
input dim=self.noiseLength+self.lstm out length + 1)) G 1.add(BatchNormalization()) G 1.add(Activation(’relu’)) G 1.add(Reshape((int(self.mini batch size), int(self.orderLength − 4), 100))) G 1.add(UpSampling2D()) G 1.add(Dropout(dropout)) G 1.add(UpSampling2D()) G 1.add(Conv2DTranspose(32, 32, padding=’same’)) G 1.add(BatchNormalization()) G 1.add(Activation(’relu’)) G 1.add(Conv2DTranspose(16,32 , padding=’same’)) G 1.add(BatchNormalization()) G 1.add(Activation(’relu’)) G 1.add(Conv2DTranspose(8, 32, padding=’same’)) G 1.add(BatchNormalization()) G 1.add(Activation(’relu’)) G 1.add(MaxPooling2D((2,2))) G 1.add(Conv2DTranspose(1, 32, padding=’same’)) G 1.add(Activation(’tanh’)) G 1.add(MaxPooling2D((2,2)))
gen output 1 = G 1(gen input)
#CDA network(train offline) #Input: cda input , shape(self.mini batch size , 8) #Output: gen output 2 , shape(self.mini batch size , 4) G 2 = Sequential(name=’orderbook gen’) G 2.add(Dense(256∗3,input dim=8)) G 2.add(BatchNormalization()) G 2.add(Activation(’relu’)) G 2.add(Reshape((16, 16, 3))) G 2.add(Conv2D(128,(3,3),padding=’same’)) G 2.add(BatchNormalization()) G 2.add(Activation(’relu’)) G 2.add(Conv2D(64, (3,3),padding=’same’)) G 2.add(BatchNormalization()) G 2.add(Activation(’relu’)) G 2.add(Conv2D(32,(3,3),padding=’same’)) G 2.add(BatchNormalization()) G 2.add(Activation(’relu’)) G 2.add(Flatten()) G 2.add(Dense(4))
# extract the last best bid/ask from history as the history of CDA orderbook history = Lambda(lambda x: x[:,−1,5:], output shape=(4,))(history) # gen output 1 is output of generator gen output reshaped = Reshape((self.orderLength−4,))(gen output 1) # remove time as it is not needed for CDA network gen output without time = \
Lambda(lambda x: x[:,1:], output shape=(4,))(gen output reshaped) cda input = Concatenate(axis=1)([gen output without time ,orderbook history]) gen output 2 = G 2(cda input)
#Output of Generator , shape(self.mini batch size , self.orderLength) concatentated # with output of the CDA network to get final output
gen output = Concatenate(axis=2)([gen output 1 ,\ Reshape((self.mini batch size , 4, 1))(generator output 2)])
The structure of the critic is shown below
############# Critic ################## # Input of Critic, merge history input , lstm output h and gen output/truth input discriminator input fake = (Concatenate(axis=2)\
([Reshape((1, 1,1))(history input), \ Reshape((1, self.lstm out length ,1))(lstm output h), gen output]))
discriminator input truth = Concatenate(axis=2)\ ([Reshape((1, 1,1))(history input), \ Reshape((1, self.lstm out length ,1))(lstm output h), truth input]) #random−weighted average of real and generated samples − following # Improved WGAN work averaged samples = RandomWeightedAverage()\
([discriminator input fake , discriminator input truth])
#Critic #Input: discriminator input fake/discriminator input truth #Ouput: score D = Sequential(name=’discriminator’) D.add(Conv2D(512,(3,3),padding=’same’, input shape=(self.mini batch size , \
self.orderLength+self.lstm out length+1,1))) D.add(Activation(’relu’)) D.add(Conv2D(256, (3,3),padding=’same’)) D.add(Activation(’relu’)) D.add(Conv2D(128,(3,3),padding=’same’)) D.add(Activation(’relu’)) D.add(Flatten()) D.add(Dense(1)) #self.D = D
discriminator output fake = D(discriminator input fake) discriminator output truth = D(discriminator input truth) averaged samples output = D(averaged samples)
#Def gradient penalty loss partial gp loss = partial(self.gradient penalty loss ,
averaged samples=averaged samples , gradient penalty weight=1)
partial gp loss. name = ’gradient penalty’
The full model
############### Model Definition ################ # Generator model # Input: [history input ,history,noise input 1] # Output: gen output self.gen = Model(inputs=[history input ,history,noise input 1], outputs= gen output) #Model Truth: self.model truth = Model(inputs=[history input ,history,noise input 1 ,truth input],\
outputs=[discriminator output fake ,discriminator output truth ,\ averaged samples output])
#Model Fake: self.model fake = Model(inputs=[history input ,history,noise input 1],\
outputs= discriminator output fake) #Optimizer optimizer = Adam(0.0001, beta 1=0.5, beta 2=0.9)
#Compile Models #Generator self.gen.compile(optimizer=optimizer , loss=’binary crossentropy’) self.gen.summary() #Model Truth − Generator is not trainable here for layer in self.model truth.layers:
layer.trainable = False self.model truth.get layer(name=’discriminator’).trainable = True self.model truth.get layer(name=’lstm critic’).trainable = True self.model truth.compile(optimizer=optimizer , \
loss=[self.w loss ,self.w loss ,partial gp loss]) #Model Fake − critic is not trainable here for layer in self.model fake.layers:
layer.trainable = True self.model fake.get layer(name=’discriminator’).trainable = False self.model fake.get layer(name=’lstm critic’).trainable = False self.model fake.compile(optimizer=optimizer , loss=self.w loss) #print summary self.model fake.summary() self.model truth.summary()

title: GENERATING REALISTIC STOCK MARKET ORDER STREAMS