summaries: Training with large batches provides a disproportionate improvement for GANs (e.g. FID drops from 18.65 to 12.39 by simply increasing the batch size by a factor of 8 for BigGAN). The authors point out that not everybody has access to the computing power which is required to run large batches. Therefore, this paper proposes a method to select the image of the batch and thereby obtaining the benefits of large batches while running only small batches. This paper applies core-set selection to the training of GANs. The motivation is to limit the minibatch size with suitably sampled sets of datapoints. The proposed technique is relatively reasonable: e.g. extract features from an image, reduce dimensionality by the taking random projections, then run Core-Set selection. The Core-Set selection part of the method is modular from the rest of the GAN training, and can be applied easily.  This paper addresses the challenging problem of how to speed up the training of GANs without using large mini-batch sizes and causing significant performance drop. To achieve this, the authors propose to use the method of core-sets, mainly inspired by recent use of core-set selection in active learning. The proposed method allows us to generate effectively large mini-batches though actually small during the training process, or more concretely, drawing a large batch of samples from the prior and then compress that batch using core-set selection. To address the curse of dimensionality issue for high-dimensional data like images, the authors suggest using a low-dimensional embedding based on Inception activations of each training image. Regarding the experimental evaluation, it is clearly shown that the proposed core-set selection greatly improves GAN training in terms of timing and memory usage, and allows significantly reducing mode collapse on a synthetic dataset. As a by-product, it is successfully applied to anomaly detection and achieves state-of-the-art results.
abstractText: Recent work by Brock et al. (2018) suggests that Generative Adversarial Networks (GANs) benefit disproportionately from large mini-batch sizes. Unfortunately, using large batches is slow and expensive on conventional hardware. Thus, it would be nice if we could generate batches that were effectively large though actually small. In this work, we propose a method to do this, inspired by the use of Coreset-selection in active learning. When training a GAN, we draw a large batch of samples from the prior and then compress that batch using Coreset-selection. To create effectively large batches of ‘real’ images, we create a cached dataset of Inception activations of each training image, randomly project them down to a smaller dimension, and then use Coreset-selection on those projected activations at training time. We conduct experiments showing that this technique substantially reduces training time and memory usage for modern GAN variants, that it reduces the fraction of dropped modes in a synthetic dataset, and that it allows GANs to reach a new state of the art in anomaly detection.
authors.name: SMALL-GAN: SPEEDING
authors.name: GAN TRAINING
references.authors: Pankaj K Agarwal Sariel Har-Peled Kasturi R Varadarajan
references.title: Geometric approximation via coresets
references.venue: Combinatorial and computational geometry,
references.authors: Sanjeev Arora Rong Ge Yingyu Liang Tengyu Ma Yi Zhang
references.title: Generalization and equilibrium in generative adversarial nets (gans)
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Sanjeev Arora Andrej Risteski Yi Zhang
references.title: Do gans learn the distribution? some theory and empirics
references.authors: Samaneh Azadi Catherine Olsson Trevor Darrell Ian Goodfellow Augustus Odena
references.title: Discriminator rejection sampling
references.venue: arXiv preprint arXiv:1810.06758,
references.authors: Mihai Bādoiu Sariel Har-Peled Piotr Indyk
references.title: Approximate clustering via core-sets
references.venue: In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing,
references.authors: Francisco Barahona FabiáN A Chudak
references.title: Near-optimal solutions to large-scale facility location problems
references.venue: Discrete Optimization,
references.authors: Marc G Bellemare Ivo Danihelka Will Dabney Shakir Mohamed Balaji Lakshminarayanan Stephan Hoyer Rémi Munos
references.title: The cramer distance as a solution to biased wasserstein gradients
references.venue: arXiv preprint arXiv:1705.10743,
references.authors: Andrew Brock Jeff Donahue Karen Simonyan
references.title: Large scale gan training for high fidelity natural image synthesis
references.venue: arXiv preprint arXiv:1809.11096,
references.authors: Varun Chandola Arindam Banerjee Vipin Kumar
references.title: Anomaly detection: A survey
references.venue: ACM computing surveys (CSUR),
references.authors: Tatjana Chavdarova François Fleuret
references.title: Sgan: An alternative training of generative adversarial networks
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Tatjana Chavdarova Gauthier Gidel François Fleuret Simon Lacoste-Julien
references.title: Reducing noise in gan training with variance reduced extragradient
references.authors: Kenneth L Clarkson
references.title: Coresets, sparse greedy approximation, and the frank-wolfe algorithm
references.venue: ACM Transactions on Algorithms (TALG),
references.authors: Sanjoy Dasgupta Anupam Gupta
references.title: An elementary proof of a theorem of johnson and lindenstrauss
references.venue: Random Structures & Algorithms,
references.authors: David L Donoho
references.title: High-dimensional data analysis: The curses and blessings of dimensionality
references.venue: AMS math challenges lecture,
references.authors: Ishan Durugkar Ian Gemp Sridhar Mahadevan
references.title: Generative multi-adversarial networks
references.venue: arXiv preprint arXiv:1611.01673,
references.authors: Ahmet M Eskicioglu Paul S Fisher
references.title: Image quality measures and their performance
references.venue: IEEE Transactions on communications,
references.authors: Reza Zanjirani Farahani Masoud Hekmatfar
references.title: Facility location: concepts, models, algorithms and case studies
references.authors: William Fedus Ian Goodfellow Andrew M Dai
references.title: Maskgan: better text generation via filling in the
references.venue: arXiv preprint arXiv:1801.07736,
references.authors: Dan Feldman Matthew Faulkner Andreas Krause
references.title: Scalable training of mixture models via coresets
references.venue: In Advances in neural information processing systems,
references.authors: Gauthier Gidel Hugo Berard Gaëtan Vignoud Pascal Vincent Simon Lacoste-Julien
references.title: A variational inequality perspective on generative adversarial networks
references.venue: arXiv preprint arXiv:1802.10551,
references.authors: Bernd Girod
references.title: What’s wrong with mean-squared error? Digital images and human vision, pp
references.authors: AJ Goldman
references.title: Optimal center location in simple networks
references.venue: Transportation science,
references.authors: Ian Goodfellow Jean Pouget-Abadie Mehdi Mirza Bing Xu David Warde-Farley Sherjil Ozair Aaron Courville Yoshua Bengio
references.title: Generative adversarial nets
references.venue: In Advances in neural information processing systems,
references.authors: Priya Goyal Piotr Dollár Ross Girshick Pieter Noordhuis Lukasz Wesolowski Aapo Kyrola Andrew Tulloch Yangqing Jia Kaiming He
references.title: Accurate, large minibatch sgd: Training imagenet in 1 hour
references.venue: arXiv preprint arXiv:1706.02677,
references.authors: Ishaan Gulrajani Faruk Ahmed Martin Arjovsky Vincent Dumoulin Aaron C Courville
references.title: Improved training of wasserstein gans
references.venue: In Advances in neural information processing systems,
references.authors: Jiaxian Guo Sidi Lu Han Cai Weinan Zhang Yong Yu Jun Wang
references.title: Long text generation via adversarial training with leaked information
references.venue: In Thirty-Second AAAI Conference on Artificial Intelligence,
references.authors: Sariel Har-Peled Akash Kushal
references.title: Smaller coresets for k-median and k-means clustering
references.venue: Discrete & Computational Geometry,
references.authors: Sariel Har-Peled Soham Mazumdar
references.title: On coresets for k-means and k-median clustering
references.venue: In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing,
references.authors: Martin Heusel Hubert Ramsauer Thomas Unterthiner Bernhard Nessler Sepp Hochreiter
references.title: Gans trained by a two time-scale update rule converge to a local nash equilibrium
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jonathan Huggins Trevor Campbell Tamara Broderick
references.title: Coresets for scalable bayesian logistic regression
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Phillip Isola Jun-Yan Zhu Tinghui Zhou Alexei A Efros
references.title: Image-to-image translation with conditional adversarial networks
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Nitish Shirish Keskar Dheevatsa Mudigere Jorge Nocedal Mikhail Smelyanskiy Ping Tak Peter Tang
references.title: On large-batch training for deep learning: Generalization gap and sharp minima
references.venue: arXiv preprint arXiv:1609.04836,
references.authors: Alex Krizhevsky Geoffrey Hinton
references.title: Learning multiple layers of features from tiny images
references.venue: Technical report, Citeseer,
references.authors: Rithesh Kumar Anirudh Goyal Aaron Courville Yoshua Bengio
references.title: Maximum entropy generators for energy-based models
references.venue: arXiv preprint arXiv:1901.08508,
references.authors: Donghwoon Kwon Hyunjoo Kim Jinoh Kim Sang C Suh Ikkyun Kim Kuinam J Kim
references.title: A survey of deep learning-based network anomaly detection
references.venue: Cluster Computing,
references.authors: Christian Ledig Lucas Theis Ferenc Huszár Jose Caballero Andrew Cunningham Alejandro Acosta Andrew Aitken Alykhan Tejani Johannes Totz Zehan Wang
references.title: Photo-realistic single image super-resolution using a generative adversarial network
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Victor Lempitsky Yuri Boykov
references.title: Global optimization for shape fitting
references.venue: IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Chun-Liang Li Wei-Cheng Chang Yu Cheng Yiming Yang Barnabás Póczos
references.title: Mmd gan: Towards deeper understanding of moment matching network
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jerry Li Aleksander Madry John Peebles Ludwig Schmidt
references.title: Towards understanding the dynamics of generative adversarial networks
references.venue: arXiv preprint arXiv:1706.09884,
references.authors: Xudong Mao Qing Li Haoran Xie Raymond YK Lau Zhen Wang Stephen Paul Smolley
references.title: Least squares generative adversarial networks
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Lars Mescheder
references.title: On the convergence properties of gan training
references.venue: arXiv preprint arXiv:1801.04406,
references.authors: Lars Mescheder Andreas Geiger Sebastian Nowozin
references.title: Which training methods for gans do actually converge
references.venue: arXiv preprint arXiv:1801.04406,
references.authors: Takeru Miyato Toshiki Kataoka Masanori Koyama Yuichi Yoshida
references.title: Spectral normalization for generative adversarial networks
references.venue: arXiv preprint arXiv:1802.05957,
references.authors: Ben Mussay Margarita Osadchy Vladimir Braverman Samson Zhou Dan Feldman
references.title: Dataindependent neural pruning via coresets, 2019
references.authors: Vaishnavh Nagarajan J Zico Kolter
references.title: Gradient descent gan optimization is locally stable
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Cuong V Nguyen Yingzhen Li Thang D Bui Richard E Turner
references.title: Variational continual learning
references.venue: arXiv preprint arXiv:1710.10628,
references.authors: Jeff M Phillips
references.title: Coresets and sketches
references.venue: arXiv preprint arXiv:1601.00617,
references.authors: Rameshwar Pratap Sandeep Sen
references.title: Faster coreset construction for projective clustering via lowrank approximation
references.venue: In International Workshop on Combinatorial Algorithms,
references.authors: Alec Radford Luke Metz Soumith Chintala
references.title: Unsupervised representation learning with deep convolutional generative adversarial networks
references.venue: arXiv preprint arXiv:1511.06434,
references.authors: Tim Salimans Han Zhang Alec Radford Dimitris Metaxas
references.title: Improving gans using optimal transport
references.venue: arXiv preprint arXiv:1803.05573,
references.authors: Ozan Sener Silvio Savarese
references.title: Active learning for convolutional neural networks: A core-set approach
references.venue: arXiv preprint arXiv:1708.00489,
references.authors: Christopher J Shallue Jaehoon Lee Joe Antognini Jascha Sohl-Dickstein Roy Frostig George E Dahl
references.title: Measuring the effects of data parallelism on neural network training
references.venue: arXiv preprint arXiv:1811.03600,
references.authors: Samarth Sinha Sayna Ebrahimi Trevor Darrell
references.title: Variational adversarial active learning
references.venue: arXiv preprint arXiv:1904.00370,
references.authors: Samuel L Smith Pieter-Jan Kindermans Chris Ying Quoc V Le
references.title: Don’t decay the learning rate, increase the batch size
references.venue: arXiv preprint arXiv:1711.00489,
references.authors: Christian Szegedy Sergey Ioffe Vincent Vanhoucke Alexander A Alemi
references.title: Inception-v4, inception-resnet and the impact of residual connections on learning
references.venue: In Thirty-First AAAI Conference on Artificial Intelligence,
references.authors: Ivor W Tsang James T Kwok Pak-Ming Cheung
references.title: Core vector machines: Fast svm training on very large data sets
references.venue: Journal of Machine Learning Research,
references.authors: Ivor W Tsang Andras Kocsor James T Kwok
references.title: Simpler core vector machines with enclosing balls
references.venue: In Proceedings of the 24th international conference on Machine learning,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In Advances in neural information processing systems,
references.authors: Kai Wei Yuzong Liu Katrin Kirchhoff Jeff Bilmes
references.title: Using document summarization techniques for speech data subset selection
references.venue: In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,
references.authors: Laurence A Wolsey George L Nemhauser
references.title: Integer and combinatorial optimization
references.authors: Yongqin Xian Tobias Lorenz Bernt Schiele Zeynep Akata
references.title: Feature generating networks for zero-shot learning
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Jason Yosinski Jeff Clune Yoshua Bengio Hod Lipson
references.title: How transferable are features in deep neural networks
references.venue: In Advances in neural information processing systems,
references.authors: Fisher Yu Ari Seff Yinda Zhang Shuran Song Thomas Funkhouser Jianxiong Xiao
references.title: Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop
references.venue: arXiv preprint arXiv:1506.03365,
references.authors: Houssam Zenati Chuan Sheng Foo Bruno Lecouat Gaurav Manek Vijay Ramaseshan Chandrasekhar
references.title: Efficient gan-based anomaly detection
references.venue: arXiv preprint arXiv:1802.06222,
references.authors: Han Zhang Tao Xu Hongsheng Li Shaoting Zhang Xiaogang Wang Xiaolei Huang Dimitris N Metaxas
references.title: Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Han Zhang Ian Goodfellow Dimitris Metaxas Augustus Odena
references.title: Self-attention generative adversarial networks
references.venue: arXiv preprint arXiv:1805.08318,
references.authors: Jia-Jie Zhu José Bento
references.title: Generative adversarial active learning
references.venue: arXiv preprint arXiv:1702.07956,
references.authors: Jun-Yan Zhu Taesung Park Phillip Isola Alexei A Efros
references.title: Unpaired image-to-image translation using cycle-consistent adversarial networks
references.venue: In Proceedings of the IEEE international conference on computer vision,
sections.heading: 1 INTRODUCTION
sections.text: Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) have become a popular research topic. Arguably the most impressive results have been in image synthesis (Brock et al., 2018; Salimans et al., 2018; Miyato et al., 2018; Zhang et al., 2018; 2017), but they have also been applied fruitfully to text generation (Fedus et al., 2018; Guo et al., 2018), domain transfer learning (Zhu et al., 2017; Zhang et al., 2017; Isola et al., 2017), and various other tasks (Xian et al., 2018; Ledig et al., 2017; Zhu & Bento, 2017).
  Recently, Brock et al. (2018) substantially improved the results of Zhang et al. (2018) by using very large mini-batches during training. The effect of large mini-batches in the context of deep learning is well-studied (Smith et al., 2017; Goyal et al., 2017; Keskar et al., 2016; Shallue et al., 2018) and general consensus is that they can be helpful in many circumstances, but the results of Brock et al. (2018) suggest that GANs benefit disproportionately from large batches. In fact, Table 1 of Brock et al. (2018) shows that for the Frechet Inception Distance (FID) metric (Heusel et al., 2017) on the ImageNet dataset, scores can be improved from 18.65 to 12.39 simply by making the batch eight times larger.
  Unfortunately, increasing the batch size in this manner is not always possible since it increases the computational resources required to train these models – often beyond the reach of conventional hardware. The experiments from the BigGAN paper require a full ‘TPU Pod’. The ‘unofficial’ open source release of BigGAN works around this by accumulating gradients across 8 different V100 GPUs and only taking an optimizer step every 8 gradient accumulation steps. Future research on GANs would be much easier if we could have the gains from large batches without these pain points. In this paper, we take steps toward accomplishing that goal by proposing a technique that allows for mimicking large batches without the computational costs of actually using large batches.
  In this work, we use Core-set selection (Agarwal et al., 2005) to sub-sample a large batch to produce a smaller batch. The large batches are then discarded, and the sub-sampled, smaller, batches are used to train the GAN. Informally, this procedure yields small batches with ‘coverage’ similar to that of the large batch – in particular the small batch tries to ‘cover’ all the same modes as are covered in the large batch. This technique yields many of the benefits of having large batches with much less computational overhead. Moreover, it is generic, and so can be applied to nearly all GAN variants.
  Our contributions can be summarized as follows:
  • We introduce a simple, computationally cheap method to increase the ‘effective batch size’ of GANs, which can be applied to any GAN variant.
  • We conduct experiments on the CIFAR and LSUN datasets showing that our method can substantially improve FID across different GAN architectures given a fixed batch size.
  • We use our method to improve the performance of the technique from Kumar et al. (2019), resulting in state-of-the-art performance at GAN-based anomaly detection.
sections.heading: 2 BACKGROUND AND NOTATION
sections.text: Generative Adversarial Networks A Generative Adversarial Network (or GAN) is a system of two neural networks trained ‘adversarially’. The generator, G, takes as input samples from a prior z ∼ p(z) and outputs the learned distribution, G(z). The discriminator, D, receives as input both the training examples, X , and the synthesized samples, G(z), and outputs a distribution D(.) over the possible sample source. The discriminator is then trained to maximize the following objective:
  LD = −Ex∼pdata [logD(x)]− Ez∼p(z)[log(1−D(G(z)))] (1) while the generator is trained to minimize1:
  LG = −Ez∼p(z)[logD(G(z))] (2) Informally, the generator is trained to trick the discriminator into believing that the generated samples G(z) actually come from the target distribution, p(x), while the discriminator is trained to be able to distinguish the samples from each other.
  Inception Score and Frechet Inception Distance: We will refer frequently to the Frechet Inception Distance (FID) (Heusel et al., 2017), to measure the effectiveness of an image synthesis model. To compute this distance, one assumes that we have a pre-trained Inception classifier. One further assumes that the activations in the penultimate layer of this classifier come from a multivariate Gaussian. If the activations on the real data are N(m,C) and the activations on the fake data are N(mw, Cw), the FID is defined as:
  ‖m−mw‖22 +Tr ( C + Cw − 2 ( CCw )1/2) (3)
  Core-set selection: In computational geometry, a Core-set, Q, of a set P is a subset Q ⊂ P that approximates the ‘shape’ of P (Agarwal et al., 2005). The problem of approximating the shape of a larger set using a smaller subset is formally called shape fitting Lempitsky & Boykov (2007). Core-sets perform sequential selection of points for shape-fitting (Agarwal et al., 2005). Core-sets are used to quickly generate approximate solutions to problems whose full solution on the original set would be burdensome to compute. Given such a problem2, one computes Q, then computes the solution to the problem for Q and converts that into an approximate solution for the original set P . The general Core-set selection problem can be formulated several ways, here we consider the the minimax facility location formulation (Farahani & Hekmatfar, 2009):
  min Q:|Q|=k max xi∈P min xj∈Q d(xi, xj) (4)
  where k is the desired size of Q, and d(., .) is a metric on P . Informally, the formula above encodes the following objective: find some set, Q, of points of size k such that the maximum distance between a point in P and its nearest point in Q is minimized. Since finding the exact solution to the minimax facility location problem is NP-Hard (Wolsey & Nemhauser, 2014), we will have to make do with a greedy approximation, detailed in Section 3.3. Using the minimax facility location formulation is an appropriate heuristic since Agarwal et al. (2005) demonstrated that minimizing the maximum distance between Q and P is an effective approximate solution for shape fitting.
  1 This is the commonly used “Non-Saturating Cost”. There are many others, but for brevity and since our technique we describe is agnostic to the loss function, we will omit them.
  2 As an example, consider computing the diameter of a point-set (Agarwal et al., 2005).
  Algorithm 1 GreedyCoreset Input: batch size (k), data points (x where |x| > k) Output: subset of x of size k s← {} . Initialize the sampled set while |s| < k do . Iteratively add points to sampled set
  p← argmaxxi /∈s minxj∈s d(xi, xj) s← s ∪ {p}
  end whilereturn s
sections.heading: 3 USING CORE-SET SAMPLING FOR GANS (OR SMALL-GAN)
sections.text: We aim to use Core-set sampling to increase the effective batch size during GAN training. This involves replacing the basic sampling operation that is done implicitly when minibatches are created. This implicit sampling operation happens in two places: First, when we create a minibatch of samples drawn from the prior distribution p(z). Second, when we create a minibatch of samples from the target distribution pdata(x) to update the parameters of the discriminator. The first of these replacements is relatively simple, while the second presents challenges. In both cases, we have to work around the fact that actually doing Core-set sampling is computationally hard.
sections.heading: 3.1 SAMPLING FROM THE PRIOR
sections.text: We need to sample from the prior when we update the discriminator and generator parameters. Our Core-set sampling algorithm doesn’t take into account the geometry of the space we sample from, so sampling from a complicated density may cause trouble. This problem is not intractable, but it’s nicer not to have to deal with it, so in the absence of any evidence that the choice of prior affects the training, we define the prior in our experiments to be a uniform distribution over a hypercube. To add Core-set sampling to the prior distribution, we randomly sample n points from the prior, where n is greater than the desired batch size, k. We then perform Core-set selection on the large batch of size n to create a batch of size k. By applying Core-set sampling on the randomly over-sampled prior, we obtain a small sparse batch that approximates the shape of the hypercube. The smaller batch is what’s actually used to perform an SGD step.
sections.heading: 3.2 SAMPLING FROM THE TARGET DISTRIBUTION
sections.text: Sampling from the target distribution is more challenging. The elements drawn from the distribution are high dimensional images, so taking pairwise distances between them will tend to work poorly due to concentration of distances (Donoho et al., 2000; Sinha et al., 2019), and the fact that Euclidean distances are semantically meaningless in image space (Girod, 1993; Eskicioglu & Fisher, 1995).
  To avoid these issues, we instead pre-process our data set by computing the ‘Inception Embeddings’ of each image using a pre-trained classifier (Szegedy et al., 2017). This is commonly done in the transfer-learning literature, where it is generally accepted that these embeddings have nontrivial semantics (Yosinski et al., 2014). Since this pre-processing happens only once at the beginning of training, it doesn’t affect the per-training-step performance.
  In order to further reduce the time taken by the Core-set selection procedure, and inspired by the Johnson-Lindenstrauss Lemma (Dasgupta & Gupta, 2003), we take random low dimensional projections of the Inception Embeddings. In practice, we multiply the Inception Embeddings by a fixed and random matrix, to find low-dimensional embeddings where the distances are nearly preserved (Dasgupta & Gupta, 2003). Combined with Core-set selection, this gives us low-dimensional representations of the training set images in which pairwise Euclidean distances have meaningful semantics. We can then use Core-set sampling on those representations to select images at training time, analogous to how we select images from the prior.
sections.heading: 3.3 GREEDY CORE-SET SELECTION
sections.text: In the above sections, we have invoked Core-set selection while glossing over the detail that exactly solving the k-center problem is NP-hard. This is important, because we propose to use Core-set
  selection at every training step3. Fortunately, we can make do with an approximate solution, which is faster to compute: we use the greedy k-center algorithm (similar to Sener & Savarese (2017)) summarized in Alg. 1.
sections.heading: 3.4 SMALL-GAN
sections.text: Our full proposed algorithm for GAN training is presented in Alg. 2. Our technique is agnostic to the underlying GAN framework and therefore can replace random sampling of mini-batches for all GAN variants. More implementation details and design choices are presented in Section 4.
  Algorithm 2 Small-GAN Input: target batch size (k), starting batch size (n > k), Inception embeddings (φI ) Output: a trained GAN
  Initialize networks G and D for step = 1 to ... do
  z ∼ p(z) . Sample n points from the prior x ∼ p(x) . Sample n points from the data distribution φ(x)← φI(x) . Get cached embeddings for x ẑ ← GreedyCoreset(z) . Get Core-set of z φ̂(x)← GreedyCoreset(φ(x)) . Get Core-set of embeddings x̂← φ−1I (φ̂(x)) . Get x corresponding to sampled embeddings Update GAN parameters as usual
  end for
sections.heading: 4 EXPERIMENTS
sections.text: In this section we look at the performance of our proposed sampling method on various tasks: In the first experiment, we train a GAN on a Gaussian mixture dataset with a large number of modes and confirm our method substantially mitigates ‘mode-dropping’. In the second, we apply our technique to GAN-based anomaly detection (Kumar et al., 2019) and significantly improve on prior results. Finally, we test our method on standard image synthesis benchmarks and confirm that our technique seriously reduces the need for large mini-batches in GAN training. The variety of settings in these experiments testifies to the generality of our proposed technique.
sections.heading: 4.1 IMPLEMENTATION DETAILS
sections.text: For our Core-set algorithm, the distance function, d(·, ·) s the `2-norm for both the prior and target distributions. Since we use the current state-of-the-art GAN architectures, each GAN model is trained with the same hyper-parameters and optimizers as was proposed in the corresponding paper, to ensure fair comparison. The only hyper-parameter altered is the batch-size, which is stated for all experiments. For over-sampling, we use a factor of 4 for the prior p(z) and a factor of 8 for the target, p(x), unless otherwise stated. We investigate the effects of different over-sampling factors in the ablation study in Section 4.6.
sections.heading: 4.2 MIXTURE OF GAUSSIANS
sections.text: We first investigate the problem of mode dropping (Arora et al., 2018) in GANs, where the GAN generator is unable to recover some modes from the target data set. We investigate the performance of training a GAN to recover a different number of modes of 2D isotropic Gaussian distributions, with a standard deviation of 0.05. We use a similar experimental setup as Azadi et al. (2018), where our generator and discriminator are parameterized using 4 ReLU-fully connected networks, and use the standard GAN loss in Eq. 1 and 2. To evaluate the performance of the models, we generate
  3 Though the Core-set sampling does happens on CPU and so could be done in parallel to the GPU operations used to train the model, as long as the Core-set sampling time doesn’t exceed the time of a forward and backward pass – which it doesn’t.
  10, 000 samples and assign them to their closest mode. As in Azadi et al. (2018), the metrics we use to evaluate performance are: i) ‘high quality samples’, which are samples within 4 standard deviations of the assigned mode and ii) ‘recovered modes’ which are mixture components with at least one assigned sample.
  Our results are present in table 1, where we experiment with an increasing number of modes. We see that as the number of modes increases, a normal GAN suffers from increased mode dropping and lower sample quality compared to Core-set selection. With 100 modes, Core-set selection recovers 97.33% of the modes compared to 90.67% for the vanilla GAN. Core-set selection also generates 49.87% ‘high quality’ samples compared to 23.31% for the vanilla GAN.
sections.heading: 4.3 ANOMALY DETECTION
sections.text: To see whether our method can be useful for more than just GANs, we also apply it to the Maximum Entropy Generator (MEG) from Kumar et al. (2019). MEG is an energy-based model whose training procedure requires maximizing the entropy of the samples generated from the model. Since MEG gives density estimates for arbitrary data points, it can be used for anomaly detection – a fundamental goal of machine learning research (Chandola et al., 2009; Kwon et al., 2017) – in which one aims to find samples that are ‘atypical’ given a source data set. Kumar et al. (2019) do use MEG successfully for this purpose, achieving results close to the state-of-the-art technique for GAN-based anomaly detection (Zenati et al., 2018). We hypothesized that – since energy estimates can in theory be improved by larger batch sizes – these results could be further improved by using Core-set selection, and we ran an experiment to confirm this hypothesis.
  We follow the experimental set-up from Kumar et al. (2019) by training the MEG with all samples from a chosen MNIST digit left-out during training. Those samples then serve as the ‘anomaly class’ during evaluation. We report the area under the precision-recall curve and average the score over the last 10 epochs. The results are reported in Table 2, which provides clear evidence in favor of our above hypothesis: for all digits tested, adding Core-set selection to MEG substantially improves the results. By performing these experiments, we aim to show the general applicability of Core-set selection, not to suggest that MEG is superior to BiGANs (Zenati et al., 2018) on the task. We think it’s likely that similar improvements could be achieved by using Core-set selection with BiGANs.
sections.heading: 4.4 IMAGE SYNTHESIS
sections.text: CIFAR and LSUN: We also conduct experiments on standard image synthesis benchmarks. To further show the generality of our method, we experiment with two different GAN architectures and two image datasets. We use Spectral Normalization-GAN (Miyato et al., 2018) and Self AttentionGAN (Zhang et al., 2018) on the CIFAR (Krizhevsky et al., 2009) and LSUN (Yu et al., 2015) datasets, respectively. For the LSUN dataset, which consists of 10 different categories, we train the model using the ‘outdoor church’ subset of the data.
  For evaluation, we measured the FID scores (Heusel et al., 2017) of 50, 000 generated samples from the trained models4. We compare the performance using SN-GANs with and without Core-set selection across progressively doubling batch sizes. We observe a similar effect to Brock et al. (2018): just by increasing the mini-batch size by a factor of 4, from 128 to 512, we are able to improve the FID scores from 18.75 to 15.68 for SN-GANs. This further demonstrates the importance of large mini-batches for GAN training. Adding Core-set selection significantly improves the performance of the underlying GAN for all batch-sizes. For a batch size of 128, our model using Core-set sampling significantly outperforms the normal SN-GAN trained with a batch size of 256, and is comparable to an SN-GAN trained with a batch size of 512. The results suggest that the models perform significantly better for any given batch size when Coreset-sampling is used.
  However, Core-set sampling does become less helpful as the underlying batch size increases: for SN-GAN, the performance improvement at a batch size of 128 is much larger than the improvement at a batch size of 512. This supports the hypothesis that Core-set selection works by approximating the coverage of a larger batch; a larger batch can already recover more modes of the data - so under this hypothesis, we would expect Core-set selection to help less.
  We see similar results when experimenting with Self Attention GANs (SAGAN) (Zhang et al., 2018) on the LSUN dataset (Yu et al., 2015). Compared to our results with SN-GAN, increasing the batch size results in a smaller difference in the performance for the SAGAN model, but we still see the FID improve from 14.82 to 12.63 as the batch-size is increased by a factor of 4. Using Core-set sampling with a batch size of 64, we are able to achieve a comparable score to when the model is trained with a batch size of 128. We believe that one reason for a comparably smaller advantage of using Core-set sampling on LSUN is the nature of the data itself: using the ‘outdoor church’ subset of LSUN reduces the total number of ‘modes’ possible in the target distribution, since images of churches have fewer differences than the images in CIFAR-10 data set. We see similar effects in the mixture of Gaussians experiment (See 4.2) where the relative difference between a GAN trained with and without Core-set sampling increases as the number of modes are increased.
  ImageNet: Finally, in order to test that our method would work ‘at scale, we ran an experiment on the ImageNet data set. Using the code at https://github.com/heykeetae/ Self-Attention-GAN, we trained two GANs: The first is trained exactly as described in the
  4Note that we measure the performance of all the models using the PyTorch version of FID scores, and not the official Tensorflow one. We ran all our experiments with the same code for accurate comparison.
  open-source code. The second is trained using Coreset selection, with all other hyper-parameters unchanged. Simply adding Coreset selection to the existing SAGAN code materially improved the FID (which we compute using 50000 samples): the baseline model had an FID of 19.40 and the Core-set model had an FID of 17.33.
sections.heading: 4.5 TIMING ANALYSIS
sections.text: Since random sampling can be done very quickly, it is important to investigate the amount of time it takes to train GANs with and without Core-set sampling. We measured the time for SN-GAN to do 50 gradient steps on the CIFAR dataset with various mini-batch sizes: the results are in Table 5. On average, for each gradient step, the time added by performing Core-Set sampling is only 0.024 seconds.
sections.heading: 4.6 ABLATION STUDY
sections.text: We conduct an ablation study to investigate the reasons for the effectiveness of Core-set selection. We also investigate the effect of different sampling factors and other hyper-parameters. We run all ablation experiments on the task of image synthesis using SN-GAN (Miyato et al., 2018) with the CIFAR-10 dataset (Krizhevsky et al., 2009). We use the same hyperparameters as in our main image synthesis experiments and a batch size of 128, unless otherwise stated.
sections.heading: 4.7 EXAMINATION OF MAIN HYPER-PARAMETERS
sections.text: We examine i) the importance of the chosen target distribution for Core-set selection and ii) the importance of performing Core-set on that target distribution. The FID scores are reported in Table 6. The importance of the target distribution is clear, since performing Core-set selection directly on the images (experiment B) performs similar to random-sampling. Experiment C supports our hypothesis that performing a random projection on the Inception embeddings can preserve semantic information while reducing the dimensionality of the features. This increases the effectiveness of Core-set sampling and reduces sampling time. Our ablation study also shows the importance of performing Core-set selection on both the prior and target distribution. The FID scores of the models are considerably worse when Core-set sampling is used on either distribution alone.
sections.heading: 4.8 EXAMINATION OF SAMPLING FACTORS
sections.text: Another important hyper-parameter for training GANs using Core-set selection is the sampling factor. In Table 7 we varied the factors by which both the prior and the target distributions were over-sampled. We see that using 4 for the sampling factor for the prior and 8 for the sampling factor for the target distribution results in the best performance. One interesting observation: that the performance eventually starts degrading as the sampling factor is increased. Since the greedy algorithm in Alg. 1 sequentially selects the point that is the furthest away from the the already sampled set, we
  believe that when the sampling factors are set too high, the algorithm becomes sensitive to outliers. See the appendix for more discussion of this phenomenon.
sections.heading: 5 RELATED WORK
sections.text: Variance Reduction in GANs: Researchers have proposed reducing variance in GAN training from an optimization perspective, by directly changing the way each of the networks are optimized. Some have proposed applying the extragradient method (Chavdarova et al., 2019), and others have proposed casting the minimax two-player game as a variational-inequality problem (Gidel et al., 2018). Brock et al. (2018) recently proposed reducing variance by using large mini-batches.
  Stability in GAN Training: Stabilizing GANs has been extensively studied theoretically. Researchers have worked on improving the dynamics of the two player minimax game in a variety of ways (Nagarajan & Kolter, 2017; Mescheder et al., 2018; Mescheder, 2018; Li et al., 2017b; Arora et al., 2017). Training instability has been linked to the architectural properties of GANs: especially to the discriminator (Miyato et al., 2018). Proposed architectural stabilization techniques include using Convolutional Neural Networks (CNNs) (Radford et al., 2015), using very large batch sizes (Brock et al., 2018), using an ensemble of the discriminators (Durugkar et al., 2016), using spectral normalization for the discriminator (Miyato et al., 2018), adding self-attention layers for the generator and discriminator networks (Vaswani et al., 2017; Zhang et al., 2018) and using iterative updates to a global generator and discriminator using an ensemble(Chavdarova & Fleuret, 2018). Different objectives have also been proposed to stabilize GAN training (Arjovsky et al., 2017; Gulrajani et al., 2017; Li et al., 2017a; Mao et al., 2017; Mroueh & Sercu, 2017; Bellemare et al., 2017).
  Core-set Selection: Core-set sampling has been widely studied from an algorithmic perspective in attempts to find better approximate solutions to the original NP-Hard problem (Agarwal et al., 2005; Clarkson, 2010; Pratap & Sen, 2018). The optimality of the sub-sampled solutions have also been studied theoretically (Barahona & Chudak, 2005; Goldman, 1971). See Phillips (2016) for a recent survey on Core-set selection algorithms. Core-sets have been applied to many machine learning problems such as k-means and approximate clustering (Har-Peled & Mazumdar, 2004; Har-Peled & Kushal, 2007; Bādoiu et al., 2002)), active learning for SVMs (Tsang et al., 2005; 2007), unsupervised subset selection for hidden Markov models (Wei et al., 2013) scalable Bayesian inference, (Huggins et al., 2016) and mixture models (Feldman et al., 2011). We are not aware of Core-set selection being applied to GANs.
  Core-set Selection in Deep Learning: Core-set selection is largely underexplored in the Deep Learning literature, but interest has recently increased. Sener & Savarese (2017) proposed to use Core-set sampling as a batch-mode active learning sampler for CNNs. Their method used the embeddings of a trained network to sample from. Mussay et al. (2019) proposed using Core-set selection on the activations of a neural network for network compression. Core-set selection has also been used in continual learning to sample points for episodic memory (Nguyen et al., 2017).
sections.heading: 6 CONCLUSION
sections.text: In this work we present a general way to mimic using a large batch-size in GANs while minimizing computational overhead. This technique uses Core-set selection and improves performance in a wide variety of contexts. This work also suggets further research: a similar method could be applied to other learning tasks where large mini-batches may be useful.
sections.heading: A APPENDIX
sections.text: A.1 POTENTIAL DISTORTING AFFECTS OF CORE-SET SAMPLING
  Theoretically, Core-set sampling of the training distribution can cause some distortion of the distribution learned by the generator. However, there are good ways to mitigate this, as we will discuss. Moreover, in cases where Core-set sampling causes more distortion, a baseline GAN will tend to distort things in the opposite direction.
  In more detail: We train GANs using 4 different algorithms on a mixture of two Gaussians with mixing coefficients of 0.01 and 0.99. For all 4 experiments, we use a batch size of 10. The results are as follows:
  Vanilla GAN: Training a ‘vanilla’ GAN on this mixture of two Gaussians results in the 0.01-mode being completely dropped. This is consistent with existing results on GANs. It’s also important because it suggests that, even if Core-set sampling is unavoidably distorting (which it’s not - see below), there might not be a non-distorting baseline that works in the same situation.
  Core-set Sampling Training a GAN with Core-set sampling (sampling factor of 20) results in considerable distortion: 90.9% of samples are from the 0.99-mode and 8.9% of samples are from the 0.01-mode (the rest of the samples were over 4 standard deviations from either mean) - so the 0.01 mode is over-represented by about a factor of 10. This makes a lot of sense: the final batch size is 10, and we take 200 samples to start, so the expected number of 0.01-mode samples in our original batch is 2. Core-set sampling will ensure we keep at least 1 of those 2 in our final batch of 10, yielding a 10% representation for a mode that should only have 1% representation. It’s worth pointing out that you have to make the skew in mixture components quite high relative to the batch size for this to matter, but there likely exist interesting data-sets that have this characteristic.
  Thus, we test two methods for reducing the distortion:
  Anneal Sampling Factors: Training a GAN with Core-set sampling but annealing the sampling factor from 20 to 2 during training results in 98.3% and 1.6% of samples from the 0.99 and 0.01 modes, respectively. This is a substantial reduction in distortion.
  Fine-Tune on Randomly Sampled Data: Training a GAN with Core-set sampling to start and then random sampling near the end results in 99.5% and 0.5% of samples from the 0.99 and 0.01 modes, respectively, for our best try. This method resulted in some instability - the longer the GAN is training randomly, the more likely the GAN was to drop the 0.01 mode. For this reason we would probably recommend the annealing method in practice.
  Final Observations: We have two more observations to make about this: First, the FID should in principle be sensitive to such distortions, and so the fact Core-set sampling was able to improve the FID in some sense suggests that – on CIFAR, LSUN, and ImageNet — the distortion was not that significant. Second, Azadi et al. (2018) seems like another promising way to reduce distortion, but we did not test it since the annealing method described above seems satisfactory.