summaries: This paper studies goal recognition control given a deceptive opponent, who selects actions to intentionally mislead or confusing the learner to learn the true goal. The problem has been studied in the security game, resource allocation game and Stackelberg game, where the defender is to play a resource allocation game given the best response of the attacker. in this paper, the authors use stochastic-shortest-path MDP to model the attacker's planning problem. The defender's objective is stated in eq (2) and (3) but not explained clearly.

summaries: This paper proposes to use reinforcement learning to model an agent that is reaching goal that it is intended to reach. The authors consider the case where the agent is (1) indifferent to being observed, (2) trying to help an observer reach its goal, and (3) trying to fool the observer into not reach its goal. The paper propose to use a value function to quantify how easy it is to predict where the agent is going ("worst case distinctiveness"). The authors propose to then train an agent to modify the action space to make it difficult for an agent to fool the observer.

summaries: This paper aims to provide a goal recognition framework. The paper reviews previous literature and outlines a model, but it seems to be at the draft stage as it stands as the experiment section is missing (section 4). Also, in some parts the sentences are broken and hard to follow, for example, “Here we formulate the stochastic goal recognition control (S-GRC) problem as an extension of the GRD problem to allows non-optimal agents and stochastic actions, which means the agent’s action are not deterministic and the possible successor states are with probability, the measures we can take are interdictions with cost.”

abstractText: Goal recognition based on the observations of the behaviors collected online has been used to model some potential applications. Newly formulated problem of goal recognition design aims at facilitating the online goal recognition process by performing offline redesign of the underlying environment with hard action removal. In this paper, we propose the stochastic goal recognition control (S-GRC) problem with two main stages: (1) deceptive opponent modeling based on maximum entropy regularized Markov decision processes (MDPs) and (2) goal recognition control under proactively static interdiction. For the purpose of evaluation, we propose to use the worst case distinctiveness (wcd) as a measure of the nondistinctive path without revealing the true goals, the task of S-GRC is to interdict a set of actions that improve or reduce the wcd. We empirically demonstrate that our proposed approach control the goal recognition process based on opponent’s deceptive behavior.

authors:
Mohamadreza Ahmadi
Suda Bharadwaj
Takashi Tanaka
Ufuk Topcu

title: Stochastic games with sensing costs

venue: 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton),

authors:
Stefano V Albrecht
Peter Stone

title: Autonomous agents modelling other agents: A comprehensive survey and open problems

venue: Artificial Intelligence,

authors:
Samuel Ang
Hau Chan
Albert Xin Jiang
William Yeoh

title: Game-theoretic goal recognition models with applications to security domains

venue: In International Conference on Decision and Game Theory for Security,

authors:
Boris Belousov
Jan Peters

title: Entropic regularization of markov decision

venue: processes. Entropy,

authors:
Tathagata Chakraborti
Anagha Kulkarni
Sarath Sreedharan
David E Smith
Subbarao Kambhampati

title: Explicability? legibility? predictability? transparency? privacy? security? the emerging landscape of interpretable agent behavior

venue: In Proceedings of the International Conference on Automated Planning and Scheduling,

authors:
David Ettinger
Philippe Jehiel

title: A theory of deception

venue: American Economic Journal: Microeconomics,

title: Regularization in Reinforcement Learning

venue: PhD thesis, University of Alberta,

authors:
Matthieu Geist
Bruno Scherrer
Olivier Pietquin

title: A theory of regularized markov decision processes

authors:
Jordi Grau-Moya
Felix Leibfried
Haitham Bou-Ammar

title: Balancing two-player stochastic games with soft q-learning

venue: arXiv preprint arXiv:1802.03216,

authors:
Nicolas Le Guillarme
Abdel Illah Mouaddib
Sylvain Gatepaille
Amandine Bellenger

title: Adversarial intention recognition as inverse game-theoretic planning for threat assessment

venue: In IEEE International Conference on Tools with Artificial Intelligence,

title: Acquiring Diverse Robot Skills via Maximum Entropy Deep Reinforcement Learning

venue: PhD thesis, UC Berkeley,

authors:
Ping Hou
William Yeoh
Pradeep Varakantham

title: Revisiting risk-sensitive mdps: New algorithms and results

venue: In Twenty-Fourth International Conference on Automated Planning and Scheduling,

authors:
Sarah Keren
Avigdor Gal
Erez Karpas

title: Goal recognition design

title: Privacy preserving plans in partially observable environments

venue: In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence,

title: Strong stubborn sets for efficient goal recognition design

venue: In Twenty-Eighth International Conference on Automated Planning and Scheduling,

title: Goal recognition design in deterministic environments

venue: Journal of Artificial Intelligence Research,

authors:
Mausam Kolobov
Andrey Kolobov

title: Planning with Markov decision processes. An AI perspective

authors:
Anagha Kulkarni
Siddharth Srivastava
Subbarao Kambhampati

title: Balancing goal obfuscation and goal legibility in settings with cooperative and adversarial observers

venue: arXiv preprint arXiv:1905.10672,

title: A unified framework for planning in adversarial and cooperative environments

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

title: A Game-Theoretic Planning Framework for Intentional Threat Assessment

venue: PhD thesis, Thèse de doctorat, Université de Caen,

authors:
Kyungjae Lee
Sungyub Kim
Sungbin Lim
Sungjoon Choi
Songhwai Oh

title: Tsallis reinforcement learning: A unified framework for maximum entropy reinforcement learning

authors:
Junren Luo
Xiang Ji
Wei Gao
Wanpeng Zhang
Shaofei Chen

title: Goal recognition control under network interdiction using a privacy information

venue: metric. Symmetry,

authors:
Peta Masters
Sebastian Sardina

title: Deceptive path-planning

venue: In IJCAI,

authors:
Gergely Neu
Anders Jonsson
Vicenç Gómez

title: A unified view of entropy-regularized markov decision processes

venue: arXiv preprint arXiv:1705.07798,

authors:
Swetasudha Panda
Yevgeniy Vorobeychik

title: Near-optimal interdiction of factored mdps

venue: In Conference on Uncertainty in Artificial Intelligence,

authors:
Georgios Papoudakis
Filippos Christianos
Arrasy Rahman
Stefano V Albrecht

title: Dealing with non-stationarity in multi-agent deep reinforcement learning

authors:
Ramon Fraga Pereira
Nir Oren
Felipe Meneguzzi

title: Landmark-based approaches for goal recognition as planning

venue: arXiv preprint arXiv:1904.11739,

authors:
Miquel Ramı́rez
Hector Geffner

title: Plan recognition as planning

venue: In Twenty-First International Joint Conference on Artificial Intelligence,

title: Collaborative UAV path planning with deceptive strategies

venue: PhD thesis, Massachusetts Institute of Technology,

title: Logic-based approaches to intention recognition

venue: In Handbook of Research on Ambient Intelligence and Smart Environments: Trends and Perspectives,

authors:
Keren Sarah
Xu Haifeng
Kwapong Kofi
Parkes David
Grosz Barbara

title: Information shaping for enhanced goal recognition of partially-informed agents

venue: In Heuristics and Search for DomainIndependent Planning Workshop of ICAPS,

authors:
Yagiz Savas
Mohamadreza Ahmadi
Takashi Tanaka
Ufuk Topcu

title: Entropy-regularized stochastic games

venue: arXiv preprint arXiv:1907.11543,

authors:
Macheng Shen
Jonathan P How

title: Active perception in adversarial scenarios using maximum entropy deep reinforcement learning

venue: arXiv preprint arXiv:1902.05644,

authors:
DJ Strouse
Max Kleiman-Weiner
Josh Tenenbaum
Matt Botvinick
David J Schwab

title: Learning to share and hide intentions using information regularization

venue: In Advances in Neural Information Processing Systems,

authors:
Gita Sukthankar
Christopher Geib
Hung Hai Bui
David Pynadath
Robert P Goldman

title: Plan, activity, and intent recognition: Theory and practice

title: Depth-first search and linear graph algorithms

venue: SIAM journal on computing,

authors:
Pierre Thodoroff
Audrey Durand
Joelle Pineau
Doina Precup

title: Temporal regularization for markov decision process

authors:
Zheng Tian
Ying Wen
Zhichen Gong
Faiz Punakkath
Shihao Zou
Jun Wang

title: A regularized opponent model with maximum entropy objective

title: Stochastic goal recognition design

authors:
Christabel Wayllace
Sarah Keren
William Yeoh
Avigdor Gal
Erez Karpas

title: Accounting for partial observability in stochastic goal recognition design: Messing with the marauders map. In Heuristics and Search for Domain-Independent Planning Workshop of ICAPS, 2018

authors:
Jing Zhang
Jun Zhuang
Brandon Behlendorf

title: Stochastic shortest path network interdiction with a case study of arizona–mexico border

venue: Reliability Engineering & System Safety,

heading: 1 INTRODUCTION

text:
Goal recognition (GR), also called intention recognition, is the task of inferring the goals of an agent according to the observed actions or states collected online (Sadri, 2011), which enables humans or agents to make proactive response plans. Goal recognition design (GRD) is to deliberately redesign the environment for improved online goal recognition ability (Keren et al., 2014), which includes two key models, the first measures how efficiently and effectively the online goal recognition system performs in a given setting, the second optimizes the goal recognition setting via redesign (Keren et al., 2019). Goal recognition control (GRC) aims at soft action interdiction under bounded resource by adding cost compared to the hard action removal of GRD (Luo et al., 2019), in which the interdiction can be proactively static inhibition or online dynamic block by allocating security resources to protect goals against the attacker.
In fact, under complex environment (both adversarial and cooperative), the information of an opponent’s goals are asymmetric and can not be obtained through communication (Le Guillarme, 2016). Most recent advancements in GR utilize planning recognition as planning (PRAP) (Ramı́rez & Geffner, 2009), generative game-theoretic frameworks (Ang et al., 2017), and goal recognition as planning (GRAP) (Pereira et al., 2019). There are three key assumptions widely used: (1) agents performs optimal plans to real the goals; (2) the environment is fully observable, that is the states and actions of the agents are observable; and (3) the agent’s actions are deterministic. However, these existing frameworks seldom address the deceptive behaviors of actively misleading the goal recognition process. We will relax the first and third assumptions to handle non-optimal agents and stochastic actions. Such as one game-theoretic approach provided with a unified treatment of both threat assessment and response planning in (Guillarme et al., 2017), after evaluating the threat, the defender will allocate road barrier or patrolling force to protect critical infrastructure, as illustrated in Figure 1.
In order to identify the goals and improve security, we employ opponent modeling to deal with the non-stationary strategies stemming from deception, in which maximum entropy regularized Markov decision process (MDP) is utilized to shape the multi-modal adversarial strategies (Shen & How,
2019). After finding the maximal non-distinctive agent path, we are seeking some optimal modifications (e.g., interdiction to block or inhibit action) to accelerate the online goal recognition.
In this work, we propose the stochastic goal recognition design (S-GRC) problem with deceptive opponent modeling and proactive network interdiction: the opponent’s deceptive policy is modeled as one soft multi-criteria decision policy with one tunable parameter to balance goal achievement and deception preference; and the primary objective is offline redesigning the environment by soft action interdiction to control online GR.
To validate the model, we evaluate our approach in two different environment representations: random generated connected graph and real road network. Our experiments demonstrate that (1) deceptive opponent modeling with entropy regularization make it robust to multi-modal stochastic behaviors; (2) soft decision policy based stochastic goal recognition design model for action removal bridge the gap between observation and decision making.

heading: 2 RELATED WORK

heading: 2.1 GOAL RECOGNITION AND DESIGN

text:
Goal Recognition (GR): The ability of inferring the goals of others can assist us to reason about what they are doing, why they are doing it, and what they will do next (Sukthankar et al., 2014). The recognition setting can be generally be divided into keyhole, where the agent is unaware of being observed and recognized as if the agent is looking through a keyhole; adversarial, where the agent is actively hostile to the observations of the actions and the inference of the goals; and intended, where the agent wants to convey the goal to be understood and helps the recognizer to detect the objective (Keren et al., 2019). In this work, we focus on the adversarial setting, where the agent would hide the goal and attempt to thwart the recognition process by deception. GR is strongly related to the topic of privacy-preserving and explainable planning (Keren et al., 2016; Chakraborti et al., 2019; Kulkarni et al.).
Goal Recognition Design (GRD): The GRD problems contains two models: one goal recognition setting analyzed environments, acting agent (attacker), and recognition system (recognizer, observer); one design model of possible ways to change the environment (Keren et al., 2019). The environment will induce a set of possible behaviors for the attacker, GRD can be divided into deterministic GRD (Keren et al., 2019), stochastic GRD (S-GRD) (Wayllace et al., 2018; Wayllace, 2019), GRD for Agents with partial knowledge (GRD-APK) (Sarah et al., 2019), and gametheoretic GRD (Ang et al., 2017; Masters & Sardina, 2017). Also, many design measures have been employed, such as action removal (AR), action sensor refinement (SAR), and action conditioning (AC) (Keren et al., 2018; Wayllace et al., 2018).

heading: 2.2 OPPONENT MODELING AND NETWORK INTERDICTION

text:
Deceptive Opponent Modeling: Opponent modeling has been employed to reason the nonstationary strategies of autonomous agents (Albrecht & Stone, 2018; Papoudakis et al., 2019). Deception involves combination of hiding the truth and showing the false (Masters & Sardina, 2017), which articulated three distinct strategies in each case: dissimulation (masking, repackaging, and dazzling), simulation (mimicking, inventing, and decoying) (Ettinger & Jehiel, 2010). As for deceptive path planning, game-theoretic method (Root, 2005) and model based (Masters & Sardina, 2017) method have been investigated.
Network Interdiction: In recent researches, interdiction has been used to counter the attacker’s behavior, MDP interdiction (Panda & Vorobeychik, 2017), plan interdiction (Vorobeychik & Pritchard, 2018), and network interdiction (Xu et al.) show one promising research thread of Observe-OrientDecide-Act (OODA).

heading: 2.3 REGULARIZED MDPS

text: Most sequential decision-making problems can be described as MDP based reinforcement learning problems or stochastic game problems. Regularization for MDPs can be divided into temporal regularization problems in temporal space (Thodoroff et al., 2018), spatial regularization in feature or state space (Farahmand, 2011; Harrigan), and entropy or information regularization in policy space (Neu et al., 2017; Geist et al., 2019; Belousov & Peters, 2019). Regularized reinforcement learning focuses on the smoothness and sparsity of the value function (Farahmand, 2011), acquiring of diverse robot skills (Haarnoja, 2018), and sparsity and multi-modality of the optimal policy (Lee et al., 2019). Regularized stochastic game employees various entropy constraints to balance or control behavior (Grau-Moya et al., 2018; Savas et al., 2019; Ahmadi et al., 2018; Tian et al., 2019).

heading: 3 STOCHASTIC GOAL RECOGNITION CONTROL

text:
The goal recognition control (GRC) problems try to balance the intended and adversarial goal recognition process under network interdiction (Luo et al., 2019), which extends to assume that the agent can choose to reveal or obfuscate (Kulkarni et al., 2019b;a), share or hide (Strouse et al., 2018) the goals. In this paper, we focus on stochastic GRC (S-GRC) under adversarial, cooperative, and non-stationary environment. The framework of our proposed approach is illustrated in Figure 3.
We embed deceptive opponent modeling and proactive network interdiction into the OODA cycle as two modules, which could bridge the gap between observation and decision-making. The deceptive opponent modeling module will shape the multi-modal opponent, the proactive network interdiction module will provide bounded resource allocation for defense. So, GRC will identify the goals with topological soft q learning and provide proactive interdiction resource allocation.

heading: 3.1 SSP-MDP FOR S-GRC

text:
Different from the GRD problem, we employ more applicable and soft measure of interdiction with bounded resource to control the goal recognition process. With this motivation in mind, we use the Stochastic Shortest-Path MDP (SSP-MDP) (Kolobov & Kolobov, 2012) model, which is widely used for uncertainty given an initial state, a set of goal states, actions with probabilistic outcomes and an action cost function. A SSP-MDP is represented as a tuple 〈S, s0,A,T,C,G〉, which consists a set of states S, a initial state s0, a set of actions A, a transition function T : S×A× S→ [0, 1] of state transition from s to s′ after executing the action a, and a cost function C : S ×A × S → R that gives the cost of executing action a, and a set of terminal goals G ⊆ S. With a cost function to replace the reward function, the objective is to find a optimal policy π so as to minimize the smallest expected cost or travel time of the policy, which forms the map from states to actions.
So, the optimal policy of the SSP-MDP can be find by using the Value Iteration (VI) algorithm, which use a value function V to represent expected costs. The expected cost of an optimal policy π∗ for the starting state s0 ∈ S is the expected cost V (s0), and the expected cost for all states s ∈ S can be calculated by the Bellman equation (Kolobov & Kolobov, 2012):
V (s) = min a∈A ∑ s′∈S T (s, a, s′) [C (s, a, s′) + V (s′)] (1)
A previous work on stochastic shortest path network interdiction modeled the problem as one sequential bi-level attacker-defender game, where the defender moves first by deploying sensors to the arcs in the network maximizing the expected shortest traveling time of the adversary (Zhang et al., 2018). Here we formulate the stochastic goal recognition control (S-GRC) problem as an extension of the GRD problem to allows non-optimal agents and stochastic actions, which means the agent’s action are not deterministic and the possible successor states are with probability, the measures we can take are interdictions with cost. The bounded interdiction resources allocations can better model the real world applications. A S-GRC problem is represented as a tuple P = 〈D,G〉, the domain information D = 〈S, s0,A,T,C,G〉 can be represented as SSP-MDPs. Similar to the S-GRD (Wayllace et al., 2018), we employ a metric to assess the largest number of actions an agent can take or the largest cost an agent will incur before revealing the goal. Given a problem P = 〈D,G〉, the worst case distinctiveness (wcd) of the problem can be defined as:
wcd(P ) = max π∈II Vπ (s0) (2)
So the objective of S-GRC under network interdiction can be reformulated as one optimization problem of finding a subset of actions ∆A∗ ⊂ A:
∆A∗ = argmin ∆A⊂A wcd(P̂ )
s.t. Vπ;s (s0) = Vτ̂ ;ŝ (s0) ∀g ∈ G∑ (1∆A∗ × I) ≤ k
(3)
where P = 〈D̂,G〉 is the problem with domain D̂ = 〈 S, s0, Â,T,C,G 〉 , Â is the redesigned action set with ∆A∗ interdicted, I is the corresponding cost to the interdiction resource, the total interdiction resource allocation is bounded by k.

heading: 3.2 AUGMENTED SSP-MDP WITH SCCS

text:
With the metric wcd, we can measure the maximal number of actions an agent can take before its goal is revealed. However, the formal wcd related metrics for S-GRDs are inconsistent with the intuitive definition, the wcd computation is not Markovian owing to the set of possible goals depend on the observed trajectory to a state. To deal with the uncertain inconsistence, wcdag and
ECD together with topological value iteration are employed to model the problem, in which the augmented MDPs with strongly connected components do not have loops (Wayllace et al.).
The state space of an MDP can be represented as a directed connectivity graph. One example MDP is shown in Figure 3(a), where the states are denoted by nodes, the actions are denoted by edges, the transitions are related to the arrow. The wcd may be infinite when the state space contains some cycle loop, here we can use the Tarjan algorithm (Tarjan, 1972; Hou et al., 2014) to generate strongly connected components (SCCs), which form a directed acyclic graph (DAG) as shown in Figure 3(b).
Augmented SSP-MDP for S-GRC: Given a SSP-MDP, an augmented SSP-MDP〈 S̃, s̃0, Ã, T̃, C̃, G̃ 〉 augments each component of the tuple:
• Each state ŝ ∈ Ŝ is represented by 〈s,G′〉. • The augmented initial state is s̃0 = 〈s0,G〉.
• Each augmented action â ∈ Â is a tuple 〈a,G′〉, where aA and G′ is the set of all goals for which that action is an optimal action.
• The new transition function T̃ : S̃ × Ã × S̃ → [0, 1] gives the probability T̃ (s̃, ã, s̃′), where s̃ = 〈s,G′〉, ã = 〈a,G′〉, and s̃′ = 〈s′,G′ ∩G′′〉, T̃ (s̃, ã, s̃′) = T (s, a, s′), if |G′ ∩G′′| > 1 and equals 0 otherwise.
• The cost function C̃ : S̃ × Ã × S̃ → R+ gives the cost C̃ (s̃, ã, s̃′) of executing action ã in augmented state s̃ and arriving in s̃′′. This cost equals the cost C̃ (s̃, ã, s̃′) = C(s, a, s′) under the same condition as above.
• The augmented goal states G̃ ⊆ S̃ are those augmented states 〈s,G′〉 for which any execution of an augmented action will transition to an augmented state 〈s′,G′′′〉 with one goal or no goals.

heading: 3.3 DECEPTIVE OPPONENT MODELING

text:
As the opponent may change the goals midway to mislead the goal recognition process. We use a binary variable λ ∈ {0, 1} to characterize whether the opponent is a optimal or deceptive with decoy goals.
Depending on λ, the opponent is expected to exhibit different behaviors, which is fully described by an opponent policy πo(aot |st). This model is restrictive since the action probability only depend on the current state. Nonetheless, we use this model only for policy learning, and use a general history dependent opponent policy for the evaluation of the learned autonomous agent policy. Another implicit assumption of this model is that the opponent has full observability over the states. This assumption could be released by modeling the opponent as a POMDP agent.
Neutral Opponent: If the opponent is a civilian, i.e. λ = 0, we assume a simple reactive policy πcil(aot |st) is available to model the opponent:
πo(aot |st, λ = 0) = πcil(aot |st). (4)
Deceptive Opponent: We use the following equation to model an adversarial agent’s policy πo:
πo(aot |st, λ = 1;α, β) =argminπ∈∆{KL(π|πMDPα ) + βKL(π|πo(·|st, λ = 0))}, (5)
πMDPα (a o t |st, λ = 1) = eαQ(st,a o t )/Z(st), (6)
where KL(·|·) denotes the Kullback–Leibler divergence between two distributions, The goalachieving policy πMDPα is associated with the optimal Q function Q(st, a o t ), of a goal-achieving adversary MDP defined later. The temperature parameter α in (6) represents the level of rationality of the adversary. The other parameter β indicates the level of deception. Z(st) is the partition function that normalizes πMDPα .
Soft Q Learning: We use soft-Q learning (Haarnoja, 2018) to learn a stochastic belief space policy. The soft Q learning objective is to maximize the expected reward regularized by the entropy of the policy, ∑
t
Ebt,st,at∼ρπγt[r(bt, st, at) + σH(π(·|bt, st))]. (7)
The parameter σ controls the ‘softness’ of the policy. The nice interpretation of this objective function is maximizing accumulative reward while behaving as uncertain as possible, which is a desired property against an adversary. This maximum entropy problem is solved using soft Q iteration. For discrete action space, the fixed point iteration:
Qsoft(bt, st, at)← rt + γEbt+1,st+1∼ps [Vsoft(bt+1, st+1)], (8) Vsoft(bt, st)← σ log ∑ a∈A exp( 1 σ Qsoft(bt, st, a)), (9)
converges to the optimal soft value functionsQ∗soft and V ∗
soft (Haarnoja, 2018), and the optimal policy can be obtained from:
π∗MaxEnt(at|bt, st) = exp( 1
σ (Q∗soft(bt, st, at)− V ∗soft(bt, st))). (10)

heading: 3.4 PROACTIVE NETWORK INTERDICTION

text: Proactive network interdiction

heading: 4 EXPERIMENTS

heading: 4.1 GRID WORLD

heading: 4.2 NETWORK GRAPH

heading: 4.3 RESULTS

heading: 5 CONCLUSION AND FUTURE WORK

text:
Risk-Sensitive MDPs (Hou et al., 2014) illustrate one applicable scenario where the cost function is constrained with one threshold or deadline.
See Table 1.

heading: ACKNOWLEDGMENTS

text: This work is partially sponsored by the National Natural Science Foundation of China under Grants No. 61702528, No. 61806212.


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.

summaries: 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.

summaries: 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:
Pankaj K Agarwal
Sariel Har-Peled
Kasturi R Varadarajan

title: Geometric approximation via coresets

venue: Combinatorial and computational geometry,

authors:
Sanjeev Arora
Rong Ge
Yingyu Liang
Tengyu Ma
Yi Zhang

title: Generalization and equilibrium in generative adversarial nets (gans)

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Sanjeev Arora
Andrej Risteski
Yi Zhang

title: Do gans learn the distribution? some theory and empirics

authors:
Samaneh Azadi
Catherine Olsson
Trevor Darrell
Ian Goodfellow
Augustus Odena

title: Discriminator rejection sampling

venue: arXiv preprint arXiv:1810.06758,

authors:
Mihai Bādoiu
Sariel Har-Peled
Piotr Indyk

title: Approximate clustering via core-sets

venue: In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing,

authors:
Francisco Barahona
FabiáN A Chudak

title: Near-optimal solutions to large-scale facility location problems

venue: Discrete Optimization,

authors:
Marc G Bellemare
Ivo Danihelka
Will Dabney
Shakir Mohamed
Balaji Lakshminarayanan
Stephan Hoyer
Rémi Munos

title: The cramer distance as a solution to biased wasserstein gradients

venue: arXiv preprint arXiv:1705.10743,

authors:
Andrew Brock
Jeff Donahue
Karen Simonyan

title: Large scale gan training for high fidelity natural image synthesis

venue: arXiv preprint arXiv:1809.11096,

authors:
Varun Chandola
Arindam Banerjee
Vipin Kumar

title: Anomaly detection: A survey

venue: ACM computing surveys (CSUR),

authors:
Tatjana Chavdarova
François Fleuret

title: Sgan: An alternative training of generative adversarial networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Tatjana Chavdarova
Gauthier Gidel
François Fleuret
Simon Lacoste-Julien

title: Reducing noise in gan training with variance reduced extragradient

title: Coresets, sparse greedy approximation, and the frank-wolfe algorithm

venue: ACM Transactions on Algorithms (TALG),

authors:
Sanjoy Dasgupta
Anupam Gupta

title: An elementary proof of a theorem of johnson and lindenstrauss

venue: Random Structures & Algorithms,

title: High-dimensional data analysis: The curses and blessings of dimensionality

venue: AMS math challenges lecture,

authors:
Ishan Durugkar
Ian Gemp
Sridhar Mahadevan

title: Generative multi-adversarial networks

venue: arXiv preprint arXiv:1611.01673,

authors:
Ahmet M Eskicioglu
Paul S Fisher

title: Image quality measures and their performance

venue: IEEE Transactions on communications,

authors:
Reza Zanjirani Farahani
Masoud Hekmatfar

title: Facility location: concepts, models, algorithms and case studies

authors:
William Fedus
Ian Goodfellow
Andrew M Dai

title: Maskgan: better text generation via filling in the

venue: arXiv preprint arXiv:1801.07736,

authors:
Dan Feldman
Matthew Faulkner
Andreas Krause

title: Scalable training of mixture models via coresets

venue: In Advances in neural information processing systems,

authors:
Gauthier Gidel
Hugo Berard
Gaëtan Vignoud
Pascal Vincent
Simon Lacoste-Julien

title: A variational inequality perspective on generative adversarial networks

venue: arXiv preprint arXiv:1802.10551,

title: What’s wrong with mean-squared error? Digital images and human vision, pp

title: Optimal center location in simple networks

venue: Transportation science,

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

title: Generative adversarial nets

authors:
Priya Goyal
Piotr Dollár
Ross Girshick
Pieter Noordhuis
Lukasz Wesolowski
Aapo Kyrola
Andrew Tulloch
Yangqing Jia
Kaiming He

title: Accurate, large minibatch sgd: Training imagenet in 1 hour

venue: arXiv preprint arXiv:1706.02677,

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

title: Improved training of wasserstein gans

authors:
Jiaxian Guo
Sidi Lu
Han Cai
Weinan Zhang
Yong Yu
Jun Wang

title: Long text generation via adversarial training with leaked information

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Sariel Har-Peled
Akash Kushal

title: Smaller coresets for k-median and k-means clustering

venue: Discrete & Computational Geometry,

authors:
Sariel Har-Peled
Soham Mazumdar

title: On coresets for k-means and k-median clustering

venue: In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing,

authors:
Martin Heusel
Hubert Ramsauer
Thomas Unterthiner
Bernhard Nessler
Sepp Hochreiter

title: Gans trained by a two time-scale update rule converge to a local nash equilibrium

authors:
Jonathan Huggins
Trevor Campbell
Tamara Broderick

title: Coresets for scalable bayesian logistic regression

authors:
Phillip Isola
Jun-Yan Zhu
Tinghui Zhou
Alexei A Efros

title: Image-to-image translation with conditional adversarial networks

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On large-batch training for deep learning: Generalization gap and sharp minima

venue: arXiv preprint arXiv:1609.04836,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Rithesh Kumar
Anirudh Goyal
Aaron Courville
Yoshua Bengio

title: Maximum entropy generators for energy-based models

venue: arXiv preprint arXiv:1901.08508,

authors:
Donghwoon Kwon
Hyunjoo Kim
Jinoh Kim
Sang C Suh
Ikkyun Kim
Kuinam J Kim

title: A survey of deep learning-based network anomaly detection

venue: Cluster Computing,

authors:
Christian Ledig
Lucas Theis
Ferenc Huszár
Jose Caballero
Andrew Cunningham
Alejandro Acosta
Andrew Aitken
Alykhan Tejani
Johannes Totz
Zehan Wang

title: Photo-realistic single image super-resolution using a generative adversarial network

authors:
Victor Lempitsky
Yuri Boykov

title: Global optimization for shape fitting

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Chun-Liang Li
Wei-Cheng Chang
Yu Cheng
Yiming Yang
Barnabás Póczos

title: Mmd gan: Towards deeper understanding of moment matching network

authors:
Jerry Li
Aleksander Madry
John Peebles
Ludwig Schmidt

title: Towards understanding the dynamics of generative adversarial networks

venue: arXiv preprint arXiv:1706.09884,

authors:
Xudong Mao
Qing Li
Haoran Xie
Raymond YK Lau
Zhen Wang
Stephen Paul Smolley

title: Least squares generative adversarial networks

venue: In Proceedings of the IEEE International Conference on Computer Vision,

title: On the convergence properties of gan training

venue: arXiv preprint arXiv:1801.04406,

authors:
Lars Mescheder
Andreas Geiger
Sebastian Nowozin

title: Which training methods for gans do actually converge

authors:
Takeru Miyato
Toshiki Kataoka
Masanori Koyama
Yuichi Yoshida

title: Spectral normalization for generative adversarial networks

venue: arXiv preprint arXiv:1802.05957,

authors:
Ben Mussay
Margarita Osadchy
Vladimir Braverman
Samson Zhou
Dan Feldman

title: Dataindependent neural pruning via coresets, 2019

authors:
Vaishnavh Nagarajan
J Zico Kolter

title: Gradient descent gan optimization is locally stable

authors:
Cuong V Nguyen
Yingzhen Li
Thang D Bui
Richard E Turner

title: Variational continual learning

venue: arXiv preprint arXiv:1710.10628,

title: Coresets and sketches

venue: arXiv preprint arXiv:1601.00617,

authors:
Rameshwar Pratap
Sandeep Sen

title: Faster coreset construction for projective clustering via lowrank approximation

venue: In International Workshop on Combinatorial Algorithms,

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Tim Salimans
Han Zhang
Alec Radford
Dimitris Metaxas

title: Improving gans using optimal transport

venue: arXiv preprint arXiv:1803.05573,

authors:
Ozan Sener
Silvio Savarese

title: Active learning for convolutional neural networks: A core-set approach

venue: arXiv preprint arXiv:1708.00489,

authors:
Christopher J Shallue
Jaehoon Lee
Joe Antognini
Jascha Sohl-Dickstein
Roy Frostig
George E Dahl

title: Measuring the effects of data parallelism on neural network training

venue: arXiv preprint arXiv:1811.03600,

authors:
Samarth Sinha
Sayna Ebrahimi
Trevor Darrell

title: Variational adversarial active learning

venue: arXiv preprint arXiv:1904.00370,

authors:
Samuel L Smith
Pieter-Jan Kindermans
Chris Ying
Quoc V Le

title: Don’t decay the learning rate, increase the batch size

venue: arXiv preprint arXiv:1711.00489,

authors:
Christian Szegedy
Sergey Ioffe
Vincent Vanhoucke
Alexander A Alemi

title: Inception-v4, inception-resnet and the impact of residual connections on learning

venue: In Thirty-First AAAI Conference on Artificial Intelligence,

authors:
Ivor W Tsang
James T Kwok
Pak-Ming Cheung

title: Core vector machines: Fast svm training on very large data sets

venue: Journal of Machine Learning Research,

authors:
Ivor W Tsang
Andras Kocsor
James T Kwok

title: Simpler core vector machines with enclosing balls

venue: In Proceedings of the 24th international conference on Machine learning,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Kai Wei
Yuzong Liu
Katrin Kirchhoff
Jeff Bilmes

title: Using document summarization techniques for speech data subset selection

venue: In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Laurence A Wolsey
George L Nemhauser

title: Integer and combinatorial optimization

authors:
Yongqin Xian
Tobias Lorenz
Bernt Schiele
Zeynep Akata

title: Feature generating networks for zero-shot learning

authors:
Jason Yosinski
Jeff Clune
Yoshua Bengio
Hod Lipson

title: How transferable are features in deep neural networks

authors:
Fisher Yu
Ari Seff
Yinda Zhang
Shuran Song
Thomas Funkhouser
Jianxiong Xiao

title: Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop

venue: arXiv preprint arXiv:1506.03365,

authors:
Houssam Zenati
Chuan Sheng Foo
Bruno Lecouat
Gaurav Manek
Vijay Ramaseshan Chandrasekhar

title: Efficient gan-based anomaly detection

venue: arXiv preprint arXiv:1802.06222,

authors:
Han Zhang
Tao Xu
Hongsheng Li
Shaoting Zhang
Xiaogang Wang
Xiaolei Huang
Dimitris N Metaxas

title: Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks

authors:
Han Zhang
Ian Goodfellow
Dimitris Metaxas
Augustus Odena

title: Self-attention generative adversarial networks

venue: arXiv preprint arXiv:1805.08318,

authors:
Jia-Jie Zhu
José Bento

title: Generative adversarial active learning

venue: arXiv preprint arXiv:1702.07956,

authors:
Jun-Yan Zhu
Taesung Park
Phillip Isola
Alexei A Efros

title: Unpaired image-to-image translation using cycle-consistent adversarial networks

venue: In Proceedings of the IEEE international conference on computer vision,

heading: 1 INTRODUCTION

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.

heading: 2 BACKGROUND AND NOTATION

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

heading: 3 USING CORE-SET SAMPLING FOR GANS (OR SMALL-GAN)

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.

heading: 3.1 SAMPLING FROM THE PRIOR

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.

heading: 3.2 SAMPLING FROM THE TARGET DISTRIBUTION

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.

heading: 3.3 GREEDY CORE-SET SELECTION

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.

heading: 3.4 SMALL-GAN

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

heading: 4 EXPERIMENTS

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.

heading: 4.1 IMPLEMENTATION DETAILS

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.

heading: 4.2 MIXTURE OF GAUSSIANS

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.

heading: 4.3 ANOMALY DETECTION

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.

heading: 4.4 IMAGE SYNTHESIS

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.

heading: 4.5 TIMING ANALYSIS

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.

heading: 4.6 ABLATION STUDY

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.

heading: 4.7 EXAMINATION OF MAIN HYPER-PARAMETERS

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.

heading: 4.8 EXAMINATION OF SAMPLING FACTORS

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.

heading: 5 RELATED WORK

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).

heading: 6 CONCLUSION

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.

heading: A APPENDIX

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.