summaries: This paper proposes to consider the mixed equilibrium objective function for GANS. The authors generalize the mirror descent/mirror prox to handle continuous games. The technical challenge is to write those algorithms in infinite dimensional spaces. This reviewer finds this however to be a mere technicality, and there seems to be no conceptual obstruction. In fact other paper have already written this, see for example ``Mirror Descent Learning in Continuous Games" by Zhou et al. at CDC 2017 (I'm sure there are other references too).

summaries: This paper extends the mirror-descent and mirror-prox algorithms to infinite dimensional Banach spaces so that they can be applied to solve the mixed Nash equilibrium of the popular generative adversarial networks. The main technical results appear to be formal but straightforward extensions of existing techniques in finite dimensional spaces. A sample-based practical algorithm is proposed so that the infinite dimensional algorithms can still be computed. Experiments are a bit disappointing as the authors only used visual appeal as an evaluation criterion. (I understand why the authors chose to do so but as an algorithmic paper, resorting to an evaluation based on visual appeal is almost always unsatisfactory.)

abstractText: We reconsider the training objective of Generative Adversarial Networks (GANs) from the mixed Nash Equilibria (NE) perspective. Inspired by the classical prox methods, we develop a novel algorithmic framework for GANs via an infinite-dimensional two-player game and prove rigorous convergence rates to the mixed NE. We then propose a principled procedure to reduce our novel prox methods to simple sampling routines, leading to practically efficient algorithms. Finally, we provide experimental evidence that our approach outperforms methods that seek pure strategy equilibria, such as SGD, Adam, and RMSProp, both in speed and quality.

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

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

venue: In International Conference on Machine Learning,

authors:
Maximilian Balandat
Walid Krichene
Claire Tomlin
Alexandre Bayen

title: Minimizing regret on reflexive banach spaces and nash equilibria in continuous zero-sum games

venue: In Advances in Neural Information Processing Systems,

authors:
David Balduzzi
Sebastien Racaniere
James Martens
Jakob Foerster
Karl Tuyls
Thore Graepel

title: The mechanics of n-player differentiable games

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Shane Barratt
Rishi Sharma

title: A note on the inception score

venue: arXiv preprint arXiv:1801.01973,

title: Pros and cons of gan evaluation measures

venue: arXiv preprint arXiv:1802.03446,

title: Orf523: Mirror descent, part i/ii, 2013a. URL https://blogs

title: Orf523: Mirror descent, part ii/ii, 2013b. URL https://blogs

title: Orf523: Mirror prox, 2013c. URL https://blogs.princeton.edu/ imabandit/2013/04/23/orf523-mirror-prox

title: Implementations of (theoretical) generative adversarial networks and comparison without cherry-picking

authors:
Pratik Chaudhari
Anna Choromanska
Stefano Soatto
Yann LeCun
Carlo Baldassi
Christian Borgs
Jennifer Chayes
Levent Sagun
Riccardo Zecchina

title: Entropy-sgd: Biasing gradient descent into wide valleys

venue: In International Conference on Learning Representations,

authors:
Pratik Chaudhari
Adam Oberman
Stanley Osher
Stefano Soatto
Guillaume Carlier

title: Deep relaxation: partial differential equations for optimizing deep neural networks

venue: Research in the Mathematical Sciences,

authors:
Partha Dasgupta
Eric Maskin

title: The existence of equilibrium in discontinuous economic games

venue: i: Theory. The Review of economic studies,

authors:
Constantinos Daskalakis
Andrew Ilyas
Vasilis Syrgkanis
Haoyang Zeng

title: Training GANs with optimism

authors:
Gintare Karolina Dziugaite
Daniel Roy

title: Entropy-sgd optimizes the prior of a pacbayes bound: Generalization properties of entropy-sgd and data-dependent priors

authors:
Ian Gemp
Sridhar Mahadevan

title: Global convergence to the equilibrium of gans using variational inequalities

venue: arXiv preprint arXiv:1808.01531,

title: Elementary principles in statistical mechanics

authors:
Gauthier Gidel
Hugo Berard
Pascal Vincent
Simon Lacoste-Julien

title: A variational inequality perspective on generative adversarial nets

venue: arXiv preprint arXiv:1802.10551,

authors:
Gauthier Gidel
Reyhane Askari Hemmat
Mohammad Pezeshki
Gabriel Huang
Remi Lepriol
Simon Lacoste-Julien
Ioannis Mitliagkas

title: Negative momentum for improved game dynamics

venue: arXiv preprint arXiv:1807.04740,

title: A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points

venue: Proceedings of the American Mathematical Society,

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

title: Generative adversarial nets

venue: In Advances in neural information processing systems,

title: Entropy and information theory

venue: Springer Science & Business Media,

authors:
Paulina Grnarova
Kfir Y Levy
Aurelien Lucchi
Thomas Hofmann
Andreas Krause

title: An online learning approach to generative adversarial networks

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

title: Improved training of wasserstein gans

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

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

venue: arXiv preprint,

authors:
Anatoli Juditsky
Arkadi Nemirovski

title: First order methods for nonsmooth convex largescale optimization, ii: utilizing problems structure

venue: Optimization for Machine Learning,

authors:
Anatoli Juditsky
Arkadi Nemirovski
Claire Tauvel

title: Solving variational inequalities with stochastic mirror-prox algorithm

venue: Stochastic Systems,

authors:
Taeksoo Kim
Moonsu Cha
Hyunsoo Kim
Jung Kwon Lee
Jiwon Kim

title: Learning to discover cross-domain relations with generative adversarial networks

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Chunyuan Li
Changyou Chen
David E Carlson
Lawrence Carin

title: Preconditioned stochastic gradient langevin dynamics for deep neural networks

venue: In AAAI,

authors:
Tengyuan Liang
James Stokes

title: Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks

venue: arXiv preprint arXiv:1802.06132,

authors:
Mario Lucic
Karol Kurach
Marcin Michalski
Sylvain Gelly
Olivier Bousquet

title: Are gans created equal? a large-scale study

authors:
Panayotis Mertikopoulos
Houssam Zenati
Bruno Lecouat
Chuan-Sheng Foo
Vijay Chandrasekhar
Georgios Piliouras

title: Mirror descent in saddle-point problems: Going the extra (gradient) mile

venue: arXiv preprint arXiv:1807.02629,

authors:
Lars Mescheder
Sebastian Nowozin
Andreas Geiger

title: The numerics of gans

title: Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems

venue: SIAM Journal on Optimization,

authors:
AS Nemirovsky
DB Yudin

title: Problem complexity and method efficiency in optimization

title: Primal-dual subgradient methods for convex problems

venue: Mathematical programming,

authors:
Frans A Oliehoek
Rahul Savani
Jose Gallego
Elise van der Pol
Roderich Groß

title: Beyond local nash equilibria for adversarial networks

venue: arXiv preprint arXiv:1806.07268,

authors:
Albert Pumarola
Antonio Agudo
Aleix M Martinez
Alberto Sanfeliu
Francesc Moreno-Noguer

title: Ganimation: Anatomically-aware facial animation from a single image

authors:
Albert Pumarola
Antonio Agudo
Alberto Sanfeliu
Francesc Moreno-Noguer

title: Unsupervised person image synthesis in arbitrary poses

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

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Casper Kaae Sønderby
Jose Caballero
Lucas Theis
Wenzhe Shi
Ferenc Huszár

title: Amortised map inference for image super-resolution

authors:
Tijmen Tieleman
Geoffrey Hinton

title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude

venue: COURSERA: Neural networks for machine learning,

title: Topics in optimal transportation

venue: Number 58. American Mathematical Soc.,

authors:
Zhaowen Wang
Ding Liu
Jianchao Yang
Wei Han
Thomas Huang

title: Deep networks for image super-resolution with sparse prior

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

authors:
Max Welling
Yee W Teh

title: Bayesian learning via stochastic gradient langevin dynamics

venue: In Proceedings of the 28th International Conference on Machine Learning

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:
Jun-Yan Zhu
Taesung Park
Phillip Isola
Alexei A Efros

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

venue: In IEEE International Conference on Computer Vision,

heading: 1 Introduction

text:
The Generative Adversarial Network (GAN) (Goodfellow et al., 2014) has become one of the most powerful paradigms in learning real-world distributions, especially for image-related data. It has been successfully applied to a host of applications such as image translation (Isola et al., 2017; Kim et al., 2017; Zhu et al., 2017), super-resolution imaging (Wang et al., 2015), pose editing (Pumarola et al., 2018b), and facial animation (Pumarola et al., 2018a).
Despite of the many accomplishments, the major hurdle blocking the full impact of GAN is its notoriously difficult training phase. In the language of game theory, GAN seeks for a pure strategy equilibrium, which is well-known to be ill-posed in many scenarios (Dasgupta & Maskin, 1986). Indeed, it is known that a pure strategy equilibrium might not exist (Arora et al., 2017), might be degenerate (Sønderby et al., 2017), or cannot be reliably reached by existing algorithms (Mescheder et al., 2017).
Empirically, it has also been observed that common algorithms, such as SGD or Adam (Kingma & Ba, 2015), lead to unstable training. While much efforts have been devoted into understanding the training dynamics of GANs (Balduzzi et al., 2018; Gemp & Mahadevan, 2018; Gidel et al., 2018a;b; Liang & Stokes, 2018), a provably convergent algorithm for general GANs, even under reasonably strong assumptions, is still lacking.
In this paper, we address the above problems with the following contributions:
1. We propose to study the mixed Nash Equilibrium (NE) of GANs: Instead of searching for an optimal pure strategy which might not even exist, we optimize over the set of probability distributions over pure strategies of the networks. The existence of a solution to such problems was long established amongst the earliest game theory work (Glicksberg, 1952), leading to well-posed optimization problems.
2. We demonstrate that the prox methods of (Nemirovsky & Yudin, 1983; Nemirovski, 2004), which are fundamental building blocks for solving two-player games with finitely many strategies, can be extended to continuously many strategies, and hence applicable to training GANs. We provide an elementary proof for their convergence rates to learning the mixed NE.
3. We construct a principled procedure to reduce our novel prox methods to certain sampling tasks that were empirically proven easy by recent work (Chaudhari et al., 2017; 2018; Dziugaite & Roy, 2018). We further establish heuristic guidelines to greatly scale down the memory and computational costs, resulting in simple algorithms whose per-iteration complexity is almost as cheap as SGD.
4. We experimentally show that our algorithms consistently achieve better or comparable performance than popular baselines such as SGD, Adam, and RMSProp (Tieleman & Hinton, 2012).
Related Work: While the literature on training GANs is vast, to our knowledge, there exist only few papers on the mixed NE perspective. The notion of mixed NE is already present in (Goodfellow et al., 2014), but is stated only as an existential result. The authors of (Arora et al., 2017) advocate the mixed strategies, but do not provide a provably convergent algorithm. (Oliehoek et al., 2018) also considers mixed NE, but only with finitely many parameters. The work (Grnarova et al., 2018) proposes a provably convergent algorithm for finding the mixed NE of GANs under the unrealistic assumption that the discriminator is a single-layered neural network. In contrast, our results are applicable to arbitrary architectures, including popular ones (Arjovsky et al., 2017; Gulrajani et al., 2017).
Due to its fundamental role in game theory, many prox methods have been applied to study the training of GANs (Daskalakis et al., 2018; Gidel et al., 2018a; Mertikopoulos et al., 2018). However, these works focus on the classical pure strategy equilibria and are hence distinct from our problem formulation. In particular, they give rise to drastically different algorithms from ours and do not provide convergence rates for GANs.
In terms of analysis techniques, our framework is closely related to (Balandat et al., 2016), but with several important distinctions. First, the analysis of (Balandat et al., 2016) is based on dual averaging (Nesterov, 2009), while we consider Mirror Descent and also the more sophisticated Mirror-Prox (see Section 3). Second, unlike our work, (Balandat et al., 2016) do not provide any convergence rate for learning mixed NE of two-player games. Finally, (Balandat et al., 2016) is only of theoretical interest with no practical algorithm.
Notation: Throughout the paper, we use z to denote a generic variable and Z ⊆ Rd its domain. We denote the set of all Borel probability measures on Z by M(Z), and the set of all functions on Z by F(Z).1 We write dµ = ρdz to mean that the density function of µ ∈ M(Z) with respect to the Lebesgue measure is ρ. All integrals without specifying the measure are understood to be with respect to Lebesgue. For any objective of the form minxmaxy F (x,y), we say that (xT ,yT ) is an O ( T−1/2 ) -NE if maxx,y{F (xT ,y) −
F (x,yT )} = O ( T−1/2 ) . Similarly we can define O ( T−1 ) -NE. The symbol ‖·‖L∞ denotes the L∞-norm of functions, and ‖·‖TV denotes the total variation norm of probability measures.

heading: 2 Problem Formulation

text: We review standard results in game theory in Section 2.1, whose proof can be found in (Bubeck, 2013a;b;c). Section 2.2 relates training of GANs to the two-player game in Section 2.1, thereby suggesting to generalize the prox methods to infinite dimension.

heading: 2.1 Preliminary: Prox Methods for Finite Games

text:
Consider the classical formulation of a two-player game with finitely many strategies:
min p∈∆m max q∈∆n
〈q,a〉 − 〈q, Ap〉 , (1)
where A is a payoff matrix, a is a vector, and ∆d := { z ∈ Rd | ∑d i=1 zi = 1 } is the proba-
bility simplex, representing the mixed strategies (i.e., probability distributions) over d pure strategies. A pair (pNE, qNE) achieving the min-max value in (1) is called a mixed NE.
Assume that the matrix A is too expensive to evaluate whereas the (stochastic) gradients of (1) are easy to obtain. Under such settings, a celebrated algorithm, the so-called entropic Mirror Descent (entropic MD), learns an O ( T−1/2 ) -NE: Let φ(z) := ∑d i=1 zi log zi be the
entropy function and φ?(y) := log ∑d i=1 e yi = supz∈∆d{〈z,y〉 − φ(z)} be its Fenchel dual.
1Strictly speaking, our derivation requires mild regularity (see Appendix A.1) assumptions on the probability measure and function classes, which are met by most practical applications.
For a learning rate η and an arbitrary vector b ∈ Rd, define the MD iterates as
z′ = MDη (z, b) ≡ z′ = ∇φ? (∇φ(z)− ηb) ≡ z′i = zie −ηbi∑d
i=1 zie −ηbi
, ∀1 ≤ i ≤ d. (2)
The equivalence of the last two formulas in (2) can be readily checked.
Denote by p̄T := 1 T ∑T t=1 pt and q̄T := 1 T ∑T t=1 qt the ergodic average of two sequences {pt}Tt=1 and {qt}Tt=1. Then, with a properly chosen step-size η, we have{ pt+1 = MDη ( pt,−A>qt
) qt+1 = MDη (qt,−a+Apt)
⇒ (p̄T , q̄T ) is an O ( T− 1/2 ) -NE.
Moreover, a slightly more complicated algorithm, called the entropic Mirror-Prox (entropy MP) (Nemirovski, 2004), achieves faster rate than the entropic MD:{ pt = MDη ( p̃t,−A>q̃t ) , p̃t+1 = MDη ( p̃t,−A>qt ) qt = MDη (q̃t,−a+Ap̃t) , q̃t+1 = MDη (q̃t,−a+Apt) ⇒ (p̄T , q̄T ) is an O ( T−1 ) -NE.
If, instead of deterministic gradients, one uses unbiased stochastic gradients for entropic MD and MP, then both algorithms achieve O ( T−1/2 ) -NE in expectation.

heading: 2.2 Mixed Strategy Formulation for Generative Adversarial Networks

text:
For illustration, let us focus on the Wasserstein GAN (Arjovsky et al., 2017), and we perform a common bilinearization trick that dates back at least to the early game theory literature (Glicksberg, 1952), and is also well-known in optimal transport theory (Villani, 2003).
The training objective of Wasserstein GAN is
min θ∈Θ max w∈W EX∼Preal [fw(X)]− EX∼Pθ [fw(X)], (3)
where Θ is the set of parameters for the generator and W the set of parameters for the discriminator f , typically both taken to be neural nets. As mentioned in the introduction, such an optimization problem can be ill-posed, which is also supported by empirical evidence.
The high-level idea of our approach is, instead of solving (3) directly, we focus on the mixed strategy formulation of (3). In other words, we consider the set of all probability distributions over Θ andW, and we search for the optimal distribution that solves the following program:
min ν∈M(Θ) max µ∈M(W) Ew∼µEX∼Preal [fw(X)]− Ew∼µEθ∼νEX∼Pθ [fw(X)]. (4)
Define the function g :W → R by g(w) := EX∼Preal [fw(X)] and the operator G :M(Θ)→ F(W) as (Gν)(w) := Eθ∼ν,X∼Pθ [fw(X)]. Denoting 〈µ, h〉 := Eµh2 for any probability measure µ and function h, we may rewrite (4) as
min ν∈M(Θ) max µ∈M(W)
〈µ, g〉 − 〈µ,Gν〉 . (5)
Furthermore, the Fréchet derivative (the analogue of gradient in infinite dimension) of (5) with respect to µ is simply g − Gν, and the derivative of (5) with respect to ν is −G†µ, where G† :M(W)→ F(Θ) is the adjoint operator of G defined via the relation
∀µ ∈M(W), ν ∈M(Θ), 〈µ,Gν〉 = 〈 ν,G†µ 〉 . (6)
One can easily check that (G†µ)(θ) := EX∼Pθ,w∼µ[fw(X)] achieves the equality in (6).
To summarize, the mixed strategy formulation of Wasserstein GAN is (5), whose derivatives can be expressed in terms of g and G. We now make the crucial observation that (5) is the infinite-dimensional analogue of (1): The distributions over finite strategies are replaced with probability measures over a continuous parameter set, the vector a is replaced with a function g, the matrix A is replaced with a linear operator3 G, and the gradients are replaced with Fréchet derivatives. Based on Section 2.1, it is then natural to ask:
2It should be noted that 〈µ, h〉 is NOT an inner product, and rather is the dual pairing in Banach spaces (Halmos, 2013).
3The linearity of G trivially follows from the linearity of expectation.
Can the entropic Mirror Descent and Mirror-Prox be extended to infinite dimension to solve (5)? Can we retain the convergence rates?
We provide an affirmative answer to both questions in the next section.
Remark. The derivation in Section 2.2 can be applied to any GAN objective.

heading: 3 Infinite-Dimensional Prox Methods

text: This section builds a rigorous infinite-dimensional formalism in parallel to the finitedimensional prox methods and proves their convergence rates. While simple in retrospect, to our knowledge, these results are new.

heading: 3.1 Preparation: The Mirror Descent Iterates

text:
We first recall the notion of (Fréchet) derivative in infinite-dimensional spaces. A (nonlinear) functional Φ : M(Z) → R is said to possess a derivative at µ ∈ M(Z) if there exists a function dΦ(µ) ∈ F(Z) such that, for all µ′ ∈M(Z), we have
Φ(µ+ µ′) = Φ(µ) + 〈µ′,dΦ(µ)〉+ o( ). Similarly, a (nonlinear) functional Φ? : F(Z)→ R is said to possess a derivative at h ∈ F(Z) if there exists a measure dΦ?(h) ∈M(Z) such that, for all h′ ∈ F(Z), we have
Φ?(h+ h′) = Φ?(h) + 〈dΦ?(h), h′〉+ o( ). The most important functionals in this paper are the (negative) Shannon entropy
µ ∈M(Z), Φ(µ) := ∫ dµ log dµ
dz
and its Fenchel dual
h ∈ F(Z), Φ?(h) := log ∫ ehdz.
The first result of our paper is to show that, in direct analogy to (2), the infinite-dimensional MD iterates can be expressed as:
Theorem 1 (Infinite-Dimensional Mirror Descent, informal). For a learning rate η and an arbitrary function h, we can equivalently define
µ+ = MDη (µ, h) ≡ µ+ = dΦ? (dΦ(µ)− ηh) ≡ dµ+ = e−ηhdµ∫ e−ηhdµ . (7)
Moreover, most the essential ingredients in the analysis of finite-dimensional prox methods can be generalized to infinite dimension.
See Theorem 4 of Appendix A for precise statements and a long list of“essential ingredients of prox methods” generalizable to infinite dimension.

heading: 3.2 Infinite-Dimensional Prox Methods and Convergence Rates

text:
Armed with results in Section 3.1, we now introduce two “conceptual” algorithms for solving the mixed NE of Wasserstein GANs: The infinite-dimensional entropic MD in Algorithm 1 and MP in Algorithm 2. These algorithms iterate over probability measures and cannot be directly used in practice, but they possess rigorous convergence rates, and hence motivate the reduction procedure in Section 4 to come.
Algorithm 1: Infinite-Dimensional Entropic MD
Input: Initial distributions µ1, ν1, learning rate η for t = 1, 2, . . . , T − 1 do νt+1 = MDη ( νt,−G†µt ) , µt+1 = MDη (µt,−g +Gνt);
return ν̄T = 1 T ∑T t=1 νt and µ̄T = 1 T ∑T t=1 µt.
Algorithm 2: Infinite-Dimensional Entropic MP
Input: Initial distributions µ̃1, ν̃1, learning rate η for t = 1, 2, . . . , T do νt = MDη ( ν̃t,−G†µ̃t ) , µt = MDη (µ̃t,−g +Gν̃t);
ν̃t+1 = MDη ( ν̃t,−G†µt ) , µ̃t+1 = MDη (µ̃t,−g +Gνt);
return ν̄T = 1 T ∑T t=1 νt and µ̄T = 1 T ∑T t=1 µt.
Theorem 2 (Convergence Rates). Let Φ(µ) = ∫
dµ log dµdz . Let M be a constant such that max [ ‖−g +Gν‖L∞ , ∥∥G†µ∥∥L∞] ≤ M , and L be such that ‖G(ν − ν′)‖L∞ ≤ L ‖ν − ν′‖TV and
∥∥G†(µ− µ′)∥∥L∞ ≤ L ‖µ− µ′‖TV. Let D(·, ·) be the relative entropy, and denote by D0 := D(µNE, µ1) +D(νNE, ν1) the initial distance to the mixed NE. Then
1. Assume that we have access to the deterministic derivatives { −G†µt }T t=1 and
{g −Gν}Tt=1. Then Algorithm 1 achieves O ( T−1/2 ) -NE with η = 2M √ D0 T , and
Algorithm 2 achieves O ( T−1 ) -NE with η = 4L .
2. Assume that we have access to stochastic derivatives { −Ĝ†µt }T t=1 and { ĝ − Ĝν }T t=1
such that max [ E ∥∥∥−ĝ + Ĝν∥∥∥ L∞ ,E ∥∥∥Ĝ†µ∥∥∥ L∞ ] ≤ M ′, and the variance is upper bounded by σ2. Assume also that the bias of stochastic derivatives sat-
isfies max [∥∥∥E[−ĝ + Ĝν] + g −Gν∥∥∥ L∞ , ∥∥∥E[Ĝ†µ]−G†µ∥∥∥ L∞ ] ≤ τ . Then Algo-
rithm 1 with stochastic derivatives achieves O ( T−1/2 ) -NE in expectation with
η = √
D0 T(4τ+M′/4) , and Algorithm 2 with stochastic derivatives achieves( O ( T−1/2 ) +O(τ) ) -NE in expectation with η = min [ 4√ 3L , √ 2D0 3Tσ2 ] .
The proof can be found in Appendix B and C.
Remark. If, as in previous work (Arora et al., 2017), we assume the output of the discriminator to be bounded by U , then we have M,M ′ ≤ 2U and L ≤ U in Theorem 2. The constant error term for stochastic MP is standard; see, e.g., (Juditsky et al., 2011).

heading: 4 From Theory to Practice

text:
Section 4.1 reduces Algorithm 1 and Algorithm 2 to a sampling routine (Welling & Teh, 2011) that has widely been used in machine learning. Section 4.2 proposes to further simplify the algorithms by summarizing a batch of samples by their mean.
For simplicity, we will only derive the algorithm for entropic MD; the case for entropic MP is similar but requires more computation. To ease the notation, we assume η = 1 throughout this section as η does not play an important role in the derivation below.

heading: 4.1 Implementable Entropic MD: From Probability Measure to Samples

text:
Consider Algorithm 1. The reduction consists of three steps.
Step 1: Reformulating Entropic Mirror Descent Iterates
The definition of the MD iterate (7) relates the updated probability measure µt+1 to the current probability measure µt, but it tells us nothing about the density function of µt+1, from which we want to sample. Our first step is to express (7) in a more tractable form. By recursively applying (7) and using Theorem 4.10 in Appendix A, we have, for some
constants C1, ..., CT−1,
dΦ(µT ) = dΦ(µT−1)− (−g +GνT−1) + CT−1 = dΦ(µT−2)− (−g +GνT−2)− (−g +GνT−1) + CT−1 + Ct−2
= · · · = dΦ(µ1)− ( −(T − 1)g +G
T−1∑ s=1 νs
) +
T−1∑ s=1 Cs.
For simplicity, assume that µ1 is uniform so that dΦ(µ1) is a constant function. Then, by (13) and that dΦ? (dΦ(µT )) = dµT , we see that the density function of µT is simply
dµT = exp{(T−1)g−G∑T−1s=1 νs}dw∫ exp{(T−1)g−G∑T−1s=1 νs}dw . Similarly, we have dνT = exp{G†∑T−1s=1 µs}dθ∫ exp{G†∑T−1s=1 µs}dθ .
Step 2: Empirical Approximation for Stochastic Derivatives
The derivatives of (5) involve the function g and operator G. Recall that g requires taking expectation over the real data distribution, which we do not have access to. A common approach is to replace the true expectation with its empirical average:
g(w) = EX∼Preal [fw(X)] ' 1
n n∑ i=1 fw(X real i ) , ĝ(w)
where Xi’s are real data and n is the batch size. Clearly, ĝ is an unbiased estimator of g.
On the other hand, Gνt and G †µt involve expectation over νt and µt, respectively, and also over the fake data distribution Pθ. Therefore, if we are able to draw samples from µt and νt, then we can again approximate the expectation via the empirical average:
θ(1),θ(2), ...,θ(n ′) ∼ νt, { X (j) i }n i=1 ∼ Pθ(j) , Ĝνt(w) ' 1 nn′ n∑ i=1 n′∑ j=1 fw ( X (j) i )
w(1),w(2), ...,w(n ′) ∼ µt, {Xi}ni=1 ∼ Pθ, Ĝ†µt(θ) '
1
nn′ n∑ i=1 n′∑ j=1 fw(j) (Xi) .
Now, assuming that we have obtained unbiased stochastic derivatives − ∑t s=1 Ĝ
†µs and∑t s=1 ( −ĝ + Ĝνs ) , how do we actually draw samples from µt+1 and νt+1? Provided we can
answer this question, then we can start with two easy-to-sample distributions (µ1, ν1), and then we will be able to draw samples from (µ2, ν2). These samples in turn will allow us to draw samples from (µ3, ν3), and so on. Therefore, it only remains to answer the above question. This leads us to:
Step 3: Sampling by Stochastic Gradient Langevin Dynamics
For any probability distribution with density function e−hdz, the Stochastic Gradient Langevin Dynamics (SGLD) (Welling & Teh, 2011) iterates as
zk+1 = zk − γ∇̂h(zk) + √ 2γ ξk, (8)
where γ is the step-size, ∇̂h is an unbiased estimator of ∇h, is the thermal noise, and ξk ∼ N (0, I) is a standard normal vector, independently drawn across different iterations.
Suppose we start at (µ1, ν1). Plugging h← −Ĝ†µ1 and h← −ĝ + Ĝν1 into (8), we obtain, for {Xi}ni=1 ∼ Pθk , {w(j)}n ′ j=1 ∼ µ1, standard normal ξk, ξ′k, and Xreali ∼ Preal, {θ(j)}n ′
j=1 ∼ ν1, {X(j)i } ∼ Pθ(j) , the following update rules:
θk+1 = θk + γ∇θ  1 nn′ n∑ i=1 n′∑ j=1 fw(j) (Xi) +√2γ ξk wk+1 = wk + γ∇w  1 n n∑ i=1 fwk(X real i )− 1 nn′ n∑ i=1 n′∑ j=1 fwk ( X (j) i )+√2γ ξ′k.
The theory of (Welling & Teh, 2011) states that, for large enough k, the iterates of SGLD above (approximately) generate samples according to the probability measures (µ2, ν2). We can then apply this process recursively to obtain samples from (µ3, ν3), (µ4, ν4), ...(µT , νT ). Finally, since the entropic MD and MP output the averaged measure (µ̄T , ν̄T ), it suffices to pick a random index t̂ ∈ {1, 2, ..., T} and then output samples from (µt̂, νt̂). Putting Step 1-3 together, we obtain Algorithm 4 and 5 in Appendix D.
Remark. In principle, any first-order sampling method is valid above. In the experimental section, we also use a RMSProp-preconditioned version of the SGLD (Li et al., 2016).

heading: 4.2 Summarizing Samples by Averaging: A Simple yet Effective Heuristic

text:
Although Algorithm 4 and 5 are implementable, they are quite complicated and resourceintensive, as the total computational complexity is O(T 2). This high complexity comes from the fact that, when computing the stochastic derivatives, we need to store all the historical samples and evaluate new gradients at these samples.
An intuitive approach to alleviate the above issue is to try to summarize each distribution by only one parameter. To this end, the mean of the distribution is the most natural candidate, as it not only stablizes the algorithm, but also is often easier to acquire than the actual samples. For instance, computing the mean of distributions of the form e−hdz, where h is a loss function defined by deep neural networks, has been empirically proven successful in (Chaudhari et al., 2017; 2018; Dziugaite & Roy, 2018) via SGLD. In this paper, we adopt the same approach as in (Chaudhari et al., 2017) where we use exponential damping (the β term in Algorithm 3) to increase stability. Algorithm 3, dubbed the Mirror-GAN, shows how to encompass this idea into entropic MD; the pseudocode for the similar Mirror-Prox-GAN can be found in Algorithm 6 of Appendix D.
Algorithm 3: Mirror-GAN: Approximate Mirror Decent for GANs
Input: w̄1, θ̄1 ← random initialization, {γt}Tt=1, { t}Tt=1, {Kt}T−1t=1 , β (see Appendix D for meaning of the hyperparameters), standard normal noise ξk, ξ ′ k. for t = 1, 2, . . . , T − 1 do w̄t,w (1) t ← wt;
θ̄t,θ (1) t ← θt; for k = 1, 2, . . . ,Kt do Generate A = {X1, . . . , Xn} ∼ Pθ(k)t ;
θ (k+1) t = θ (k) t + γt n∇θ ∑ Xi∈A fwt(Xi) + √ 2γt tξk; Generate B = {Xreal1 , . . . , Xrealn } ∼ Preal; Generate B′ = {X ′1, . . . , X ′n} ∼ Pθt ;
w (k+1) t = w (k) t + γt n ∇w ∑ Xreali ∈B f w (k) t (Xreali )− γt n ∇w ∑ X′i∈B′ f w (k) t (X ′i) + √ 2γt tξ ′ k;
w̄t ← (1− β)w̄t + βw(k+1)t ; θ̄t ← (1− β)θ̄t + βθ(k+1)t ;
wt+1 ← (1− β)wt + βw̄t; θt+1 ← (1− β)θt + βθ̄t;
return wT ,θT .

heading: 5 Experimental Evidence

text:
The purpose of our experiments is twofold. First, we use established baselines to demonstrate that Mirror- and Mirror-Prox-GAN consistently achieve better or comparable performance than common algorithms. Second, we report that our algorithms are stable and always improve as the training process goes on. This is in contrast to unstable training algorithms, such as Adam, which often collapse to noise as the iteration count grows. (Cha, 2017).
We use visual quality of the generated images to evaluate different algorithms. We avoid reporting numerical metrics, as recent studies (Barratt & Sharma, 2018; Borji, 2018; Lucic et al., 2018) suggest that these metrics might be flawed. Setting of the hyperparameters and more auxiliary results can be found in Appendix E.

heading: 5.1 Synthetic Data

text:
We repeat the synthetic setup as in (Gulrajani et al., 2017). The tasks include learning the distribution of 8 Gaussian mixtures, 25 Gaussian mixtures, and the Swiss Roll. For both the generator and discriminator, we use two MLPs with three hidden layers of 512 neurons. We choose SGD and Adam as baselines, and we compare them to Mirror- and Mirror-Prox-GAN. All algorithms are run up to 105 iterations4. The results of 25 Gaussian mixtures are shown in Figure 1; An enlarged figure of 25 Gaussian Mixtures and other cases can be found in Appendix E.1.
As Figure 1 shows, SGD performs poorly in this task, while the other algorithms yield reasonable results. However, compared to Adam, Mirror- and Mirror-Prox-GAN fit the true distribution better in two aspects. First, the modes found by Mirror- and Mirror-ProxGAN are more accurate than the ones by Adam, which are perceivably biased. Second, Mirror- and Mirror-Prox-GAN perform much better in capturing the variance (how spread the blue dots are), while Adam tends to collapse to modes. These observations are consistent throughout the synthetic experiments; see Appendix E.1.

heading: 5.2 Real Data

text:
For real images, we use the LSUN bedroom dataset (Yu et al., 2015). We have also conducted a similar study with MNIST; more results can be found in Appendix E.2.
We use the same architecture (DCGAN) as in (Radford et al., 2015) with batch normalization. As the networks become deeper in this case, the gradient magnitudes differ significantly across different layers. As a result, non-adaptive methods such as SGD or SGLD do not perform well in this scenario. To alleviate such issues, we replace SGLD by the RMSProppreconditioned SGLD (Li et al., 2016) for our sampling routines. For baselines, we consider two adaptive gradient methods: RMSprop and Adam. We also include two contemporary algorithms, the Simultaneous and Alternated Extra-Adam, from the concurrent ICLR submission (Gidel et al., 2018a).
Figure 2 shows the results at the 105th iteration. The RMSProp, Alternated Extra-Adam and Mirror-GAN produce images with reasonable quality, while Adam and simultaneous Extra-Adam output noise. The visual quality of Alternated Extra-Adam and Mirror-GAN are comparable, and are better than RMSProp, as RMSProp sometimes generates blurry images (the (3, 3)- and (1, 5)-th entry of Figure 8.(b)).
It is worth mentioning that Adam can learn the true distribution at intermediate iterations, but later on suffers from mode collapse and finally degenerates to noise; see Appendix E.2.2.
4One iteration here means using one mini-batch of data. It does not correspond to the T in our algorithms, as there might be multiple SGLD iterations within each time step t.

heading: 6 Conclusions

text: Our goal of systematically understanding and expanding on the game theoretic perspective of mixed NE along with stochastic Langevin dynamics for training GANs is a promising research vein. While simple in retrospect, we provide guidelines in developing approximate infinite-dimensional prox methods that mimic closely the provable optimization framework to learn the mixed NE of GANs. Our proposed Mirror- and Mirror-Prox-GAN algorithm feature cheap per-iteration complexity while rapidly converging to solutions of good quality.

heading: A A Framework for Infinite-Dimensional Mirror Descent

heading: A.1 A note on the regularity

text:
It is known that the (negative) Shannon entropy is not Fréchet differentiable in general. However, below we show that the Fréchet derive can be well-defined if we restrict the probability measures to within the set
M(Z) :={all probability measures on Z that admit densities w.r.t. the Lebesgue measure, and the density is continuous and positive almost everywhere on Z}.
We will also restrict the set of functions to be bounded and integrable: F(Z) := { all bounded continuous functions f on Z such that ∫ e−f <∞ } .
It is important to notice that µ ∈ M(Z) and h ∈ F(Z) implies µ′ = MDη (µ, h) ∈ M(Z); this readily follows from the formula (7).

heading: A.2 Properties of Entropic Mirror Map

text:
The total variation of a (possibly non-probability) measure µ ∈M(Z) is defined as (Halmos, 2013)
‖µ‖TV = sup ‖h‖L∞≤1
∫ hdµ = sup
‖h‖L∞≤1 〈µ, h〉 .
Recall the standard topology induced by ‖·‖TV and ‖·‖L∞ for measures and functions (Halmos, 2013), respectively. Whenever we speak about continuity or differentiability below, it is understood to be w.r.t. to the standard topology. Notice also that the G operator defined in (5) is bounded if the discriminator fw is bounded, and hence continous (Halmos, 2013).
We depart from the fundamental Gibbs Variational Principle, which dates back to the earliest work of statistical mechanics (Gibbs, 1902). For two probability measures µ, µ′, denote their relative entropy by (the reason for this notation will become clear in (14))
DΦ(µ, µ ′) := ∫ Z dµ log dµ dµ′ .
By the definition of M(Z), it is clear that the relative entropy is well-defined for any µ, µ′ ∈M(Z). Theorem 3 (Gibbs Variation Principle). Let h ∈ F(Z) and µ′ ∈ M(Z) be a reference measure. Then
log ∫ Z ehdµ′ = sup µ∈M(Z) 〈µ, h〉 −DΦ(µ, µ′), (9)
and equality is achieved by dµ? = e hdµ′∫ Z e hdµ′ .
Part of the following theorem is folklore in the mathematics and learning community. However, to the best of our knowledge, the relation to the entropic MD has not been systematically studied before, as we now do.
Theorem 4. For a probability measure dµ = ρdz, let Φ(µ) = ∫ ρ log ρdz be the negative
Shannon entropy, and let Φ?(h) = log ∫ Z e hdz. Then
1. Φ? is the Fenchel conjugate of Φ:
Φ?(h) = sup µ∈M(Z) 〈µ, h〉 − Φ(µ); (10)
Φ(µ) = sup h∈F(Z)
〈µ, h〉 − Φ?(h). (11)
2. The derivatives admit the expression
dΦ(µ) = 1 + log ρ = arg max h∈F(Z)
〈µ, h〉 − Φ?(h); (12)
dΦ?(h) = ehdz∫ Z e hdz = arg max µ∈M(Z) 〈µ, h〉 − Φ(µ). (13)
3. The Bregman divergence of Φ is the relative entropy:
DΦ(µ, µ ′) = Φ(µ)− Φ(µ′)− 〈µ− µ′,dΦ(µ′)〉 = ∫ Z dµ log dµ dµ′ . (14)
4. Φ is 4-strongly convex with respect to the total variation norm: For all λ ∈ (0, 1),
Φ(λµ+ (1− λ)µ′) ≤ λΦ(µ) + (1− λ)Φ(µ′)− 1 2 · 4λ(1− λ)‖µ− µ′‖2TV. (15)
5. The following duality relation holds: For any constant C, we have
∀µ, µ′ ∈M(Z), DΦ(µ, µ′) = DΦ? (dΦ(µ′),dΦ(µ)) = DΦ? (dΦ(µ′) + C, dΦ(µ)) . (16)
6. Φ? is 14 -smooth with respect to ‖ · ‖L∞ :
∀h, h′ ∈ F(Z), ‖dΦ?(h)− dΦ?(h′)‖TV ≤ 1 4 ‖h− h′‖L∞ . (17)
7. Alternative to (17), we have the equivalent characterization of Φ?:
∀h, h′ ∈ F(Z), Φ?(h) ≤ Φ?(h′) + 〈dΦ?(h′), h− h′〉+ 1 2 · 1 4 ‖h− h′‖2L∞ . (18)
8. Similar to (16), we have
∀h, h′, DΦ?(h, h′) = DΦ(dΦ?(h′),dΦ?(h)). (19)
9. The following three-point identity holds for all µ, µ′, µ′′ ∈M(Z):
〈µ′′ − µ,dΦ(µ′)− dΦ(µ)〉 = DΦ(µ, µ′) +DΦ(µ′′, µ)−DΦ(µ′′, µ′). (20)
10. Let the Mirror Descent iterate be defined as in (7). Then the following statements are equivalent:
(a) µ+ = MDη (µ, h). (b) There exists a constant C such that dΦ(µ+) = dΦ(µ)− ηh+ C.
In particular, for any µ′, µ′′ ∈M(Z) we have
Let 〈µ′ − µ′′, ηh〉 = 〈µ′ − µ′′,dΦ(µ)− dΦ(µ+)〉 . (21)

heading: Proof.

text:
1. Equation (10) is simply the Gibbs variational principle (9) with dµ← dz. By (10), we know that
∀h ∈ F(Z), Φ(µ) ≥ 〈µ, h〉 − log ∫ Z ehdz. (22)
But for dµ = ρdz, the function h := 1 + log ρ saturates the equality in (22).
2. We prove a more general result on the Bregman divergence DΦ in (23) below.
Let dµ = ρdz,dµ′ = ρ′dz, and dµ′′ = ρ′′dz ∈ M(Z). Let > 0 be small enough such that (ρ+ ρ′′)dz is absolutely continuous with respect to dµ′; note that this is possible because µ, µ′, and µ′′ ∈M(Z). We compute
DΦ(ρ+ ρ ′′, ρ′) = ∫ Z (ρ+ ρ′′) log ρ+ ρ′′ ρ′
= ∫ Z ρ log ρ ρ′ + ∫ Z ρ log ( 1 + ρ′′ ρ ) + ∫ Z ρ′′ log ρ ρ′ + ∫ Z ρ′′ log ( 1 + ρ′′ ρ ) (i) =
∫ Z ρ log ρ ρ′ + ∫ Z ρ′′ + ∫ Z ρ′′ log ρ ρ′ + 2 ∫ Z ρ′′2 ρ + o( )
= DΦ(ρ, ρ ′) + ∫ Z ρ′′ ( 1 + log ρ ρ′ ) + o( ),
where (i) uses log(1 + t) = t+ o(t) as t→ 0. In short, for all µ′, µ′′ ∈M(Z),
dµDΦ(µ, µ ′)(µ′′) = 〈 µ′′, 1 + log ρ
ρ′
〉 (23)
which means dµDΦ(µ, µ ′) = 1 + log ρρ′ . The formula (12) is the special case when dµ′ ← dz. We now turn to (13). For every h ∈ F(Z), we need to show that the following holds for every h′ ∈ F(Z):
Φ?(h+ h′)−Φ?(h) = log ∫ Z eh+ h ′ dz− log ∫ Z ehdz = ∫ Z h′ eh∫ Z e h dz+o( ). (24)
Define an auxiliary function
T ( ) := log ∫ Z eh∫ Z e h e h ′ dz.
Notice that T (0) = 0 and T is smooth as a function of . Thus, by the Intermediate Value Theorem,
Φ?(h+ h′)− Φ?(h) = T ( )− T (0)
= ( − 0) · d d T (·) ∣∣∣∣ ′
for some ′ ∈ [0, ]. A direct computation shows d
d T (·) ∣∣∣∣ ′ = ∫ Z h′ eh+ ′h′∫ Z e h+ ′h′ dz.
Hence it suffices to prove e h+ ′h′∫ Z e h+ ′h′ = eh∫ Z e h + o(1) in . To this end, let C = sup |h′| <∞. Then eh∫ Z e h e−2 ′C ≤ e h+ ′h′∫ Z e h+ ′h′ ≤ e h∫ Z e h e2 ′C . It remains to use et = 1 + t+ o(t) and ′ ≤ .
3. Let dµ = ρdz and dµ′ = ρ′dz. We compute
DΦ(µ, µ ′) = Φ(µ)− Φ(µ′)− 〈µ− µ′,dΦ(µ′)〉
= ∫ Z ρ log ρdz − ∫ Z ρ′ log ρ′dz − 〈µ− µ′, 1 + log ρ′〉 by (12)
= ∫ Z ρ log ρ ρ′ dz
= ∫ Z dµ log dµ dµ′ .
4. Define µλ = λµ + (1 − λ)µ′. By (14) and the classical Pinsker’s inequality (Gray, 2011), we have
Φ(µ) ≥ Φ(µλ) + 〈(1− λ)(µ− µ′),dΦ(µλ)〉+ 2‖(1− λ)(µ− µ′)‖2TV, (25) Φ(µ′) ≥ Φ(µλ) + 〈λ(µ′ − µ),dΦ(µλ)〉+ 2‖λ(µ− µ′)‖2TV. (26)
Equation (15) follows by multiplying with λ and 1 − λ respectively and summing the two inequalities up.
5. Let µ = ρdz and µ′ = ρ′dz. Then, by the definition of Bregman divergence and (12), (13),
DΦ?(dΦ(µ ′),dΦ(µ)) = Φ?(dΦ(µ′))− Φ?(dΦ(µ))− 〈 e1+log ρdz∫ Z e 1+log ρ , 1 + log ρ′ − 1− log ρ 〉 = log
∫ Z e1+log ρ ′ − log ∫ Z e1+log ρ + ∫ Z ρ log ρ ρ′
= ∫ Z ρ log ρ ρ′ = DΦ(µ, µ ′)
since ∫ Z ρdz = ∫ Z ρ ′dz = 1. This proves the first equality.
For the second equality, we write
DΦ?(dΦ(µ ′) + C,dΦ(µ)) = Φ?(dΦ(µ′) + C)− Φ?(dΦ(µ))− 〈 e1+log ρdz∫ Z e 1+log ρ , 1 + log ρ′ + C − 1− log ρ 〉 = log
∫ Z e1+log ρ ′+C − log ∫ Z e1+log ρ + ∫ Z ρ log ρ ρ′ − C
= ∫ Z ρ log ρ ρ′ = DΦ(µ, µ ′) = DΦ?(dΦ(µ ′),dΦ(µ))
where we have used the first equality in the last step.
6. Let µh = dΦ ?(h), µh′ = dΦ ?(h′), and µλ = λµh + (1 − λ)µh′ for some λ ∈ (0, 1). By Pinsker’s inequality and (14), we have
Φ(µλ) ≥ Φ(µh) + 〈µλ − µh,dΦ(µh)〉+ 2‖µλ − µh‖2TV, (27) Φ(µλ) ≥ Φ(µh′) + 〈µλ − µh′ ,dΦ(µh′)〉+ 2‖µλ − µh′‖2TV. (28)
Now, notice that
〈µλ − µh,dΦ(µh)〉 = 〈µλ − µh,dΦ(dΦ?(h))〉
= 〈 µλ − µh,dΦ ( ehdz∫ Z e h )〉 by (13)
= 〈 µλ − µh, 1 + h− log ∫ Z eh 〉
by (12)
= 〈µλ − µh, h〉 and, similarly, we have 〈µλ − µh′ ,dΦ(µh′)〉 = 〈µλ − µh′ , h′〉. Multiplying (27) by λ and (28) by 1− λ, summing the two up, and using the above equalities, we get
Φ(µλ)− ( λΦ(µh) + (1− λ)Φ(µh′) ) + λ(1− λ) 〈µh − µh′ , h− h′〉 ≥ 2λ(1− λ) ‖µh − µh′‖2TV .
By (15), we know that Φ(µλ)− ( λΦ(µh) + (1− λ)F (µh′) ) ≤ −2λ(1− λ) ‖µh − µh′‖2TV .
Moreover, by definition of the total variation norm, it is clear that
〈µh − µh′ , h− h′〉 ≤ ‖µh − µh′‖TV ‖h− h ′‖L∞ . (29)
Combing the last three inequalities gives (17).
7. Let K be a positive integer and k ∈ {0, 1, 2, . . . ,K}. Set λk = kK and h ′′ = h− h′.
Then
Φ?(h)− Φ?(h′) = Φ?(h′ + λKh′′)− Φ?(h′ + λ0h′′)
= K−1∑ k=0 ( Φ?(h′ + λk+1h ′′)− Φ?(h′ + λkh′′) ) . (30)
By convexity of Φ?, we have
Φ?(h′ + λk+1h ′′)− Φ?(h′ + λkh′′) ≤ 〈dΦ?(h′ + λk+1h′′), (λk+1 − λk)h′′〉
= 1
K 〈dΦ?(h′ + λk+1h′′), h′′〉 . (31)
By (29) and (17), we may further upper bound (31) as
Φ?(h′ + λk+1h ′′)− Φ?(h′ + λkh′′) ≤
1
K
( 〈dΦ?(h′), h′′〉+ 〈dΦ?(h′ + λk+1h′′)− dΦ?(h′), h′′〉 ) ≤ 1 K ( 〈dΦ?(h′), h′′〉+ ‖dΦ?(h′ + λk+1h′′)− dΦ?(h′)‖TV ‖h ′′‖L∞ ) ≤ 1 K ( 〈dΦ?(h′), h′′〉+ λk+1 4 ‖h′′‖2L∞ ) . (32)
Summing up (32) over k, we get, in view of (30),
Φ?(h)− Φ?(h′) ≤ 〈dΦ?(h′), h′′〉+ 1 4 ‖h′′‖2L∞ K−1∑ k=0 λk+1
= 〈dΦ?(h′), h′′〉+ 1 4 · K + 1 2K ‖h′′‖2L∞ . (33)
Since K is arbitrary, we may take K →∞ in (33), which is (18).
8. Straightforward calculation shows
DΦ?(h, h ′) = log ∫ Z eh − log ∫ Z eh ′ − ∫ Z eh ′∫ eh′ (h− h′) .
On the other hand, by definition of the Bregman divergence and (12), (13), we have
DΦ(dΦ ?(h′),dΦ?(h)) = ∫ Z eh ′∫ Z e h′ h′ − log ∫ Z eh ′ − ∫ Z eh∫ Z e h h+ log ∫ Z eh
− ∫ Z ( 1 + h− log ∫ Z eh )( eh ′∫ Z e h′ − e h∫ Z e h )
= ∫ Z eh ′∫ eh′ (h′ − h)− log ∫ Z eh ′ + log ∫ Z eh = Φ?(h)− Φ?(h′)− 〈dΦ?(h′), h− h′〉 = DΦ?(h, h ′).
9. By definition of the Bregman divergence, we have
DΦ(µ, µ ′) = Φ(µ)− Φ(µ′)− 〈µ− µ′,dΦ(µ′)〉 ,
DΦ(µ ′′, µ) = Φ(µ′′)− Φ(µ)− 〈µ′′ − µ,dΦ(µ)〉 ,
DΦ(µ ′′, µ′) = Φ(µ′′)− Φ(µ′)− 〈µ′′ − µ′,dΦ(µ′)〉 .
Equation (20) then follows by straightforward calculations.
10. First, let µ+ = MDη (µ, h). Then if µ+ = ρ+dz and µ = ρdz, then (7) implies
ρ+ = ρe−ηh∫ Z ρe −ηh .
By (12), we therefore have
dΦ(µ+) = 1 + log ρ+ = 1 + log ρ− ηh− log ∫ Z ρe−ηh
whence (21) holds with C = − log ∫ Z ρe −ηh.
Conversely, assume that dΦ(µ+) = dΦ(µ)− ηh+C for some constant C, and apply dΦ? to both sides. The left-hand side becomes
dΦ? ( dΦ(µ+) ) = dΦ?(1 + log ρ+)
= ρ+dz∫ ρ+dz = ρ+dz = dµ+,
where as the formula (13) implies that
dΦ? (dΦ(µ)− ηh+ C) = e 1+log ρ−ηh+C∫ Z e 1+log ρ−ηh+C dz
= ρe−ηhdz∫ Z ρe −ηh = e−ηhdµ∫ Z e −ηhdµ .
Combining the two equalities gives dµ+ = e−ηhdµ∫ Z e −ηhdµ which exactly means µ+ = MDη (µ, h).

heading: B Proof of Convergence Rates for Infinite-Dimensional Mirror Descent

heading: B.1 Mirror Descent, Deterministic Derivatives

text:
By the definition of the algorithm, (21), and the three-point identity (20), we have, for any µ ∈M(W),
〈µt − µ,−g +Gνt〉 = 1
η 〈µt − µ,dΦ(µt)− dΦ(µt+1)〉
= 1
η
( DΦ(µ, µt)−DΦ(µ, µt+1) +DΦ(µt, µt+1) ) . (34)
By item 10 of Theorem 4, there exists a constant Ct such that
dΦ(µt+1) = dΦ(µt)− η (−g +Gνt) + Ct. (35)
Using (16), we see that
DΦ(µt, µt+1) = DΦ?(dΦ(µt+1),dΦ(µt)) = DΦ? ( dΦ(µt+1)− Ct,dΦ(µt) )
≤ 1 8 ‖dΦ(µt+1)− Ct − dΦ(µt)‖2L∞ by (18) = η2
8 ‖−g +Gνt‖2L∞ by (35)
≤ η 2M2
8 .
Consequently, we have
T∑ t=1 〈µt − µ,−g +Gνt〉 = T∑ t=1 1 η ( DΦ(µ, µt)−DΦ(µ, µt+1) +DΦ(µt, µt+1) ) ≤ DΦ(µ, µ1)
η + ηM2T 8 . (36)
Exactly the same argument applied to νt’s yields, for any ν ∈M(Θ),
T∑ t=1 〈 νt − ν,−G†µt 〉 ≤ DΦ(ν, ν1) η + ηM2T 8 . (37)
Summing up (36) and (37), substituting µ← µNE, ν ← νNE and dividing by T , we get
1
T T∑ t=1 ( 〈µt − µNE,−g +Gνt〉+ 〈 νt − νNE,−G†µt) 〉 ) ≤ D0 ηT + ηM2 4 . (38)
The left-hand side of (38) can be simplified to
1
T T∑ t=1 ( 〈µt − µNE,−g +Gνt〉+ 〈 νt − νNE,−G†µt 〉 ) = 1 T T∑ t=1 ( 〈µNE − µt, g〉 − 〈µNE, Gνt〉+ 〈µt, GνNE〉 ) = 〈µNE, g −Gν̄T 〉 − 〈µ̄T , g −GνNE〉 .
(39)
By definition of the Nash Equilibrium, we have
〈µ̄T , g −GνNE〉 ≤ 〈µNE, g −GνNE〉 ≤ 〈µNE, g −Gν̄T 〉 , (40) 〈µ̄T , g −GνNE〉 ≤ 〈µ̄T , g −Gν̄T 〉 ≤ 〈µNE, g −Gν̄T 〉 ,
which implies
|〈µ̄T , g −Gν̄T 〉 − 〈µNE, g −GνNE〉| ≤ 〈µNE, g −Gν̄T 〉 − 〈µ̄T , g −GνNE〉 . (41)
Combining (51)-(54), we conclude that
η = 2
M √ D0 T ⇒ |〈µ̄T , g −Gν̄T 〉 − 〈µNE, g −GνNE〉| ≤M √ D0 T .

heading: B.2 Mirror Descent, Stochastic Derivatives

text:
We first write〈 µt − µ, η(−ĝ + Ĝνt) 〉 = 〈µt − µ, η(−g +Gνt)〉+ 〈 µt − µ, η [ − ĝ + Ĝνt + g −Gνt ]〉 .
Taking conditional expectation and using the bias estimate of stochastic derivatives, we conclude that
E 〈 µt − µ, η(−ĝ + Ĝνt) 〉 ≤ 〈µt − µ, η(−g +Gνt)〉+ ‖µt − µ‖TV · ητ
≤ 〈µt − µ, η(−g +Gνt)〉+ 2ητ .
Therefore, using exactly the same argument leading to (36), we may obtain
E T∑ t=1 〈 µt − µ,−ĝ + Ĝνt 〉 ≤ EDΦ(µ, µ1) η + ηM ′2T 8 + 2ηTτ.
The rest is the same as with deterministic derivatives.

heading: C Proof of Convergence Rates for Infinite-Dimensional Mirror-Prox

text:
We first need a technical lemma, which is Lemma 6.2 of (Juditsky & Nemirovski, 2011) tailored to our infinite-dimensional setting. We give a slightly different proof.
Lemma 5. Given any µ ∈ M(Z) and h, h′ ∈ F(Z), let µ = MDη (µ̃, h) and µ̃+ = MDη (µ̃, h
′). Let Φ be α-strongly convex (recall that α = 4 when Φ is the entropy). Then, for any µ? ∈M(Z), we have
〈µ− µ?, ηh′〉 ≤ DΦ(µ?, µ̃)−DΦ(µ?, µ̃+) + η2
2α ‖h− h′‖2L∞ −
α 2 ‖µ− µ̃‖2TV . (42)
Proof. Recall from (15) that entropy is α-strongly convex with respect to ‖·‖TV. We first write
〈µ− µ?, ηh′〉 = 〈µ̃+ − µ?, ηh′〉+ 〈µ− µ̃+, ηh〉+ 〈µ− µ̃+, η(h′ − h)〉 . (43)
For the first term, (20) and (21) implies
〈µ̃+ − µ?, ηh′〉 = 〈µ̃+ − µ?,dΦ(µ̃)− dΦ(µ̃+)〉 = −DΦ(µ̃+, µ̃)−DΦ(µ?, µ̃+) +DΦ(µ?, µ̃). (44)
Similarly, the second term of the right-hand side of (43) can be written as
〈µ− µ̃+, ηh〉 = −DΦ(µ, µ̃)−DΦ(µ̃+, µ) +DΦ(µ̃+, µ̃). (45)
Hölder’s inequality for the third term gives
〈µ− µ̃+, η(h′ − h)〉 ≤ ‖µ− µ̃+‖TV ‖η(h ′ − h)‖L∞
≤ α 2 ‖µ− µ̃+‖2TV + 1 2α ‖η(h′ − h)‖2L∞ . (46)
Finally, recall that Φ is α-strongly convex, and hence we have
−DΦ(µ̃+, µ) ≤ − α
2 ‖µ− µ̃+‖2TV , −DΦ(µ, µ̃) ≤ −
α 2 ‖µ− µ̃‖2TV . (47)
The lemma follows by combining inequalities (44)-(47) in (43).

heading: C.1 Mirror-Prox, Deterministic Derivatives

text:
Let α = 4, µ̄T := 1 T ∑T t=1 µt, and ν̄T := 1 T ∑T t=1 νt.
In Lemma 5, substituting µ? ← µNE, µ̃ ← µ̃t, h ← −g + Gν̃t (so that µ = µt) and h′ ← −g +Gνt (so that µ̃+ = µ̃t+1), we get
〈µt − µNE, η(−g +Gνt)〉 ≤ DΦ(µNE, µ̃t)−DΦ(µNE, µ̃t+1)+ η2
2α ‖G(νt − ν̃t)‖2L∞−
α 2 ‖µ̃t − µt‖2TV .
(48) Similarly, we have〈 νt − νNE,−ηG†µt 〉 ≤ DΦ(νNE, ν̃t)−DΦ(νNE, ν̃t+1)+ η2
2α ∥∥G†(µt − µ̃t)∥∥2L∞−α2 ‖ν̃t − νt‖2TV . (49)
Since ‖G(νt − ν̃t)‖L∞ ≤ L · ‖νt − ν̃t‖TV and ∥∥G†(µt − µ̃t)∥∥L∞ ≤ L · ‖µt − µ̃t‖TV, summing up (48) and (49) yields
〈µt − µNE, η(−g +Gνt)〉+ 〈 νt − νNE,−ηG†µt) 〉 ≤ DΦ(µNE, µ̃t)−DΦ(µNE, µ̃t+1) +DΦ(νNE, ν̃t)−DΦ(νNE, ν̃t+1)
+
( η2L2
2α − α 2
)( ‖µ̃t − µt‖2TV + ‖ν̃t − νt‖ 2 TV ) ≤ DΦ(µNE, µ̃t)−DΦ(µNE, µ̃t+1) +DΦ(νNE, ν̃t)−DΦ(νNE, ν̃t+1)
if η ≤ αL = 4 L . Summing up the last inequality over t and using DΦ(·, ·) ≥ 0, we obtain
1
T T∑ t=1 ( 〈µt − µNE, η(−g +Gνt)〉+ 〈 νt − νNE,−ηG†µt) 〉 ) ≤ DΦ(µNE, µ̃1) +DΦ(νNE, ν̃1) T = D0 T . (50) The left-hand side of (50) can be simplified to
1
T T∑ t=1 ( 〈µt − µNE, η(−g +Gνt)〉+ 〈 νt − νNE,−ηG†µt) 〉 ) = η T T∑ t=1 ( 〈µNE − µt, g〉 − 〈µNE, Gνt〉+ 〈µt, GνNE〉 ) = η ( 〈µNE, g −Gν̄T 〉 − 〈µ̄T , g −GνNE〉 ) .
(51)
By definition of the (µNE, νNE), we have
〈µ̄T , g −GνNE〉 ≤ 〈µNE, g −GνNE〉 ≤ 〈µNE, g −Gν̄T 〉 , (52) 〈µ̄T , g −GνNE〉 ≤ 〈µ̄T , g −Gν̄T 〉 ≤ 〈µNE, g −Gν̄T 〉 ,
which implies
| 〈µ̄T , g −Gν̄T 〉 − 〈µNE, g −GνNE〉 | ≤ 〈µNE, g −Gν̄T 〉 − 〈µ̄T , g −GνNE〉 . (53)
Combining (50)-(53), we conclude
η ≤ 4 L ⇒ | 〈µ̄T , g −Gν̄T 〉 − 〈µNE, g −GνNE〉 | ≤ D0 Tη .

heading: C.2 Mirror-Prox, Stochastic Derivatives

text:
Let α = 4, µ̄T := 1 T ∑T t=1 µt, and ν̄T := 1 T ∑T t=1 νt. Set the step-size to η =
min [ α√ 3L , √ αD0 6Tσ2 ] .
In Lemma 5, substituting µ? ← µNE, µ̃ ← µ̃t, h ← −ĝ + Ĝν̃t (so that µ = µt), and h′ ← −ĝ + Ĝνt (so that µ̃+ = µ̃t+1), we get〈 µt − µNE, η(−ĝ + Ĝνt) 〉 ≤ DΦ(µNE, µ̃t)−DΦ(µNE, µ̃t+1)+ η2
2α ∥∥∥Ĝνt − Ĝν̃t∥∥∥2 L∞ −α 2 ‖µ̃t − µt‖2TV .
(54)
Note that E ∥∥∥Ĝνt − Ĝν̃t∥∥∥2
L∞ ≤ 3
( E ∥∥∥Ĝνt −Gνt∥∥∥2
L∞ + E ‖Gνt −Gν̃t‖2L∞ + E ∥∥∥Gν̃t − Ĝν̃t∥∥∥2 L∞ ) ≤ 6σ2 + 3L2E ‖νt − ν̃t‖2TV .
Therefore, taking expectation conditioned on the history for both sides of (54) and using the bias estimates of the stochastic derivatives, we get
〈µt − µNE, η(−g +Gνt)〉 ≤ EDΦ(µNE, µ̃t)− EDΦ(µNE, µ̃t+1) + 3η2σ2
α
+ 3η2L2
2α E ‖νt − ν̃t‖2TV −
α 2 E ‖µ̃t − µt‖2TV + 2ητ.
Similarly, we have〈 νt − νNE,−ηG†µt 〉 ≤ EDΦ(νNE, ν̃t)− EDΦ(νNE, ν̃t+1) + 3η2σ2
α
+ 3η2L2
2α E ‖µt − µ̃t‖2TV −
α 2 E ‖ν̃t − νt‖2TV + 2ητ.
Summing up the last two inequalities over t with η ≤ α√ 3L then yields
1
T T∑ t=1 ( 〈µt − µNE,−g +Gνt〉+ 〈 νt − νNE,−G†µt) 〉 ) ≤ D0 ηT + 6ησ2 α + 4τ
≤ max [ 2 √ 6σ2D0 αT , 2 √ 3LD0 αT ] + 4τ.
by definition of η. The rest is the same as with deterministic derivatives.
Algorithm 4: Approx Inf Mirror Decent Input: W [1],Θ[1]← n′ samples from random initialization, {γt}T−1t=1 , { t} T−1 t=1 , {K} T−1 t=1 , n, n ′, standard normal noise ξk, ξ ′ k. for t = 1, 2, . . . , T − 1 do C ← ∪ts=1W [s], D ← ∪ts=1Θ[s] ; w
(1) t ← UNIF(W [t]), θ (1) t ← UNIF(Θ[t]);
for k = 1, 2, . . . ,Kt, . . . ,Kt + n ′ do
Generate A = {X1, . . . , Xn} ∼ Pθ(k)t ; θ (k+1) t = θ (k) t + γt nn′∇θ ∑ Xi∈A ∑ w∈C fw(Xi) + √ 2γt tξk; Generate B = {Xreal1 , . . . , Xrealn } ∼ Preal; B′ ← {} ; for each θ ∈ D do
Generate B̃ = {X ′1, . . . , X ′n} ∼ Pθ; B′ ← B′ ∪ B̃;
w (k+1) t = w (k) t +
γtt
n ∇w ∑ Xreali ∈B f w (k) t (Xreali )− γt nn′ ∇w ∑ X′i∈B′ f w (k) t (X ′i) + √ 2γt tξ ′ k;
W [t+ 1]← { w
(K+1) t , . . . ,w (K+n′) t } , Θ[t+ 1]← { θ (K+1) t , . . . ,θ (K+n′) t } ;
idx← UNIF(1, 2, . . . , T ); return W [idx],Θ[idx].

heading: D Omitted Pseudocodes in the Main Text

text:
We use the following notation for the hyperparameters of our algorithms:
n : number of samples in the data batch.
n′ : number of samples for each probability measure.
γt : SGLD step-size at iteration t.
t : thermal noise of SGLD at iteration t.
Kt : warmup steps for SGLD at iteration t.
β : exponential damping factor in the weighted average.
The approximate infinite-dimensional entropic MD and MP in Section 4.1 are depicted in Algorithm 4 and 5, respectively. Algorithm 6 gives the heuristic version of the entropic Mirror-Prox.

heading: E Details and More Results of Experiments

text:
This section contains all the details regarding our experiments, as well as more results on synthetic and real datasets.
Algorithm 5: Approx Inf Mirror-Prox
Input: W̃ [1], Θ̃[1]← n′ samples from random initialization, {γt}Tt=1, { t}Tt=1, {Kt}Tt=1, n, n′, standard normal noise ξk, ξ′k, ξ′′k , ξ′′′k . for t = 1, 2, . . . , T do
C ← W̃ [t] ∪ ( ∪t−1s=1W [s] ) , D ← Θ̃[t] ∪ ( ∪t−1s=1Θ[s] ) ; w (1) t ← UNIF(W̃ [t]), θ (1) t ← UNIF(Θ̃[t]); for k = 1, 2, . . . ,Kt, . . . ,Kt + n ′ do
Generate A = {X1, . . . , Xn} ∼ Pθ(k)t ; θ (k+1) t = θ (k) t + γt nn′∇θ ∑ Xi∈A ∑ w∈C fw(Xi) + √ 2γt tξk; Generate B = {Xreal1 , . . . , Xrealn } ∼ Preal; B′ ← {}; for each θ ∈ D do
Generate B̃ = {X ′1, . . . , X ′n} ∼ Pθ; B′ ← B′ ∪ B̃;
w (k+1) t = w (k) t +
γtt
n ∇w ∑ Xreali ∈B f w (k) t (Xreali )− γt nn′ ∇w ∑ X′i∈B′ f w (k) t (X ′i) + √ 2γt tξ ′ k;
W [t]← { w
(K+1) t , . . . ,w (K+n′) t } , Θ[t]← { θ (K+1) t , . . . ,θ (K+n′) t } ;
C ′ ← ∪ts=1W [s], D′ ← ∪ts=1Θ[s] ; w̃
(1) t+1 ← UNIF(W̃ [t]), θ̃ (1) t+1 ← UNIF(Θ̃[t]) ;
for k = 1, 2, . . . ,Kt, . . . ,Kt + n ′ do
Generate A = {X1, . . . , Xn} ∼ Pθ̃(k)t ; θ̃ (k+1) t+1 = θ̃ (k) t+1 + γt nn′∇θ ∑ Xi∈A ∑ w∈C′ fw(Xi) + √ 2γt tξ ′′ k ; Generate B = {Xreal1 , . . . , Xrealn } ∼ Preal; B′ ← {}; for each θ ∈ D′ do
Generate B̃ = {X ′1, . . . , X ′n} ∼ Pθ; B′ ← B′ ∪ B̃;
w̃ (k+1) t+1 = w̃ (k) t+1 +
γtt
n ∇w ∑ Xreali ∈B f w̃ (k) t+1 (Xreali )− γt nn′ ∇w ∑ X′i∈B′ f w̃ (k) t+1 (X ′i) + √ 2γt tξ ′′′ k );
W̃ [t+ 1]← { w̃
(K+1) t+1 , . . . , w̃ (K+n′) t+1 } , Θ̃[t+ 1]← { θ̃ (K+1) t+1 , . . . , θ̃ (K+n′) t+1 } ;
idx← UNIF(1, 2, . . . , T ); return W [idx],Θ[idx].
Network Architectures: For all experiments, we consider the gradient-penalized discriminator (Gulrajani et al., 2017) as a soft constraint alternative to the original Wasserstein GANs, as it is known to achieve much better performance. The gradient penalty parameter is denoted by λ below.
For synthetic data, we use fully connected networks for both the generator and discriminator. They consist of three layers, each of them containing 512 neurons, with ReLU as nonlinearity.
For MNIST, we use convolutional neural networks identical to (Gulrajani et al., 2017) as the generator and discriminator.5 The generator uses a sigmoid function to map the output to range [0, 1].
5Their code is available on https://github.com/igul222/improved_wgan_training.
Algorithm 6: Mirror-Prox-GAN: Approximate Mirror-Prox for GANs
Input: w̃1, θ̃1 ← random initialization, w0 ← w̃1,θ0 ← θ̃1, {γt}Tt=1, { t}Tt=1, {Kt}Tt=1, β, standard normal noise ξk, ξ ′ k, ξ ′′ k , ξ ′′′ k . for t = 1, 2, . . . , T do
w̄t, w̄t+1, w̃ (1) t , w̃ (1) t+1 ← w̃t, θ̄t, θ̄t+1, θ̃ (1) t , θ̃ (1) t+1 ← θ̃t; for k = 1, 2, . . . ,Kt do Generate A = {X1, . . . , Xn} ∼ Pθ(k)t ;
θ (k+1) t = θ (k) t + γt n∇θ ∑ Xi∈A fw̃t(Xi) + √ 2γt tξk; Generate B = {Xreal1 , . . . , Xrealn } ∼ Preal; Generate B′ = {X ′1, . . . , X ′n} ∼ Pθ̃t ;
w (k+1) t = w (k) t + γt n ∇w ∑ Xreali ∈B f w (k) t (Xreali )− γt n ∇w ∑ X′i∈B′ f w (k) t (X ′i) + √ 2γt tξ ′ k;
w̄t ← (1− β)w̄t + βw(k+1)t ; θ̄t ← (1− β)θ̄t + βθ(k+1)t ;
wt ← (1− β)wt−1 + βw̄t; θt ← (1− β)θt−1 + βθ̄t;
for k = 1, 2, . . . ,Kt do Generate A = {X1, . . . , Xn} ∼ Pθ̃(k)t+1 ;
θ̃ (k+1) t+1 = θ̃ (k) t+1 + γt n∇θ ∑ Xi∈A fwt(Xi) + √ 2γt tξ ′′ k ; Generate B = {Xreal1 , . . . , Xrealn } ∼ Preal; Generate B′ = {X ′1, . . . , X ′n} ∼ Pθt ;
w (k+1) t+1 = w (k) t+1 + γt n ∇w ∑ Xreali ∈B f w (k) t+1 (Xreali )− γt n ∇w ∑ X′i∈B′ f w (k) t+1 (X ′i) + √ 2γt tξ ′′′ k ;
w̄t+1 ← (1− β)w̄t+1 + βw(k+1)t+1 ; θ̄t+1 ← (1− β)θ̄t+1 + βθ(k+1)t+1 ;
w̃t+1 ← (1− β)w̃t + βw̄t+1; θ̃t+1 ← (1− β)θ̃t + βθ̄t+1;
return wT ,θT .
For LSUN bedroom, we use DCGAN (Radford et al., 2015), except that the number of the channels in each layer is half of the original model, and the last sigmoid function of the discriminator is removed. The output of the generator is mapped to [0, 1] by hyperbolic tangent and a linear transformation. The architecture contains batch normalization layer to ensure the stability of the training. For our Mirror- and Mirror-Prox-GAN, the Gaussian noise from SGLD is not added to parameters in batch normalization layers, as the batch normalization creates strong dependence among entries of the weight matrix and was not covered by our theory.
Hyperparameter setting: The hyperparameter setting is summarized in Table 1. For baselines (SGD, RMSProp, Adam), we use the settings identical to (Gulrajani et al., 2017). For our proposed Mirror- and Mirror-Prox-GAN, we set the damping factor β to be 0.9. For
Kt, γt and t, we use the simple exponential scheduling:
Kt = b(1 + 10−5)tc. γt = γ × (1− 10−5)t, γ in Table 1. t = × (1− 5× 10−5)t, in Table 1.
The idea is that the initial iterations are very noisy, and hence it makes sense to take less SGLD steps. As the iteration counts grow, the algorithms learn more meaningful parameters, and we should increase the number of SGLD steps as well as decreasing the step-size γt and thermal noise t to make the sampling more accurate. This is akin to the warmup steps in the sampling literature.

heading: E.1 Synthetic Data

text:
Figure 3, 4, and 5 show results on learning 8 Gaussian mixtures, 25 Gaussian mixtures, and the Swiss Roll. As in the case for 25 Gaussian mixtures, we find that Mirror- and Mirror-
Prox-GAN can better capture the variance of the true distribution, as well as finding the unbiased modes.
In Figure 6, we plot the data generated after 104, 2×104, 5×104, 8×104, and 105 iterations by different algorithms fro 25 Gaussian mixtures. It is clear that Mirror- and Mirror-ProxGAN find the modes of the distribution faster. In practice, it was observed that the noise introduced by SGLD quickly drives the iterates to non-trivial parameter regions, whereas SGD tends to get stuck at very bad local minima. Adam, as an adaptive algorithm, is capable of escaping bad local minima, however at a rate slower than Mirror- and Mirror-Prox-GAN. The quality of Adam’s final solution is also not as good as Mirror- and Mirror-Prox-GAN; see the discussions in Section 5.1.

heading: E.2 Real Data

text:
E.2.1 MNSIT
Results on MNIST dataset are shown in Figure 7. The models are trained by each algorithm for 105 iterations. We can see that all algorithms achieve comparable performance. Therefore, the dataset seems too weak to be a discriminator for different algorithms.
E.2.2 LSUN Bedroom
More results on the LSUN bedroom dataset are shown in Figure 8. We show images generated after 4 × 104, 8 × 104, and 105 iterations by each algorithm. We can see that the MirrorGAN and Alternated Extra-Adam outperform vanilla RMSProp. Adam was able to obtain meaningful images in early stages of training. However, further iterations do not improve the image quality of Adam. In contrast, they lead to severe mode collapse at the 8× 104th iteration, and converge to noise later on. Simultaneous Extra-Adam completely fails in this task.
Finally, for reference, we report the Inception Score in Table 2.
104 iterations 2× 104 iterations 5× 104 iterations 8× 104 iterations 105 iterations
4× 104 iterations 8× 104 iterations 105 iterations
(a) RMSProp
(b) Adam
(c) Mirror-GAN, Algorithm 3

title: Finding Mixed Nash Equilibria of Generative Adversarial Networks


summaries: This paper explored the means of tuning the neural network models using less parameters. The authors evaluated the case where only the batch normalisation related parameters are fine tuned, along with the last layer, would generate competitive classification results, while using very few parameters comparing with fine tuning the whole network model. However, several questions are raised concerning the experiment design and analysis:

summaries: the paper introduces a new way of fine-tuning neural networks. Instead of re-training the whole model or fine-tuning the last few layers, the authors propose to fine-tune a small set of model patches that affect the network at different layers. The results show that this way of fine-tuning is superior to above mentioned typical ways either in accuracy or in the number of tuned parameters in three different settings: transfer learning, multi-task learning and domain adaptation.

abstractText: We introduce a novel method that enables parameter-efficient transfer and multitask learning with deep neural networks. The basic approach is to learn a model patch a small set of parameters that will specialize to each task, instead of finetuning the last layer or the entire network. For instance, we show that learning a set of scales and biases is sufficient to convert a pretrained network to perform well on qualitatively different problems (e.g. converting a Single Shot MultiBox Detection (SSD) model into a 1000-class image classification model while reusing 98% of parameters of the SSD feature extractor). Similarly, we show that re-learning existing low-parameter layers (such as depth-wise convolutions) while keeping the rest of the network frozen also improves transfer-learning accuracy significantly. Our approach allows both simultaneous (multi-task) as well as sequential transfer learning. In several multi-task learning problems, despite using much fewer parameters than traditional logits-only fine-tuning, we match singletask performance.

authors:
Olah
Mike Schuster
Jonathon Shlens
Benoit Steiner
Ilya Sutskever
Kunal Talwar
Paul Tucker
Vincent Vanhoucke
Vijay Vasudevan
Fernanda Viégas
Oriol Vinyals
Pete Warden
Martin Wattenberg
Martin Wicke
Yuan Yu
Xiaoqiang Zheng

title: TensorFlow: Large-scale machine learning

venue: on heterogeneous systems,

authors:
Fei Chen
Zhenhua Dong
Zhenguo Li
Xiuqiang He

title: Federated meta-learning for recommendation

venue: arXiv preprint arXiv:1802.07876,

title: Xception: Deep learning with depthwise separable convolutions

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Y. Cui
Y. Song
C. Sun
A. Howard
S. Belongie

title: Large Scale Fine-Grained Categorization and Domain-Specific Transfer Learning

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

venue: In CVPR09,

authors:
Jeff Donahue
Yangqing Jia
Oriol Vinyals
Judy Hoffman
Ning Zhang
Eric Tzeng
Trevor Darrell

title: Decaf: A deep convolutional activation feature for generic visual recognition

venue: Proceedings of the 31st International Conference on Machine Learning,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: arXiv preprint arXiv:1703.03400,

authors:
Elad Hoffer
Itay Hubara
Daniel Soudry

title: Fix your classifier: the marginal value of training the last weight

venue: layer. CoRR,

authors:
Andrew G. Howard
Menglong Zhu
Bo Chen
Dmitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: Mobilenets: Efficient convolutional neural networks for mobile vision applications

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: accelerating deep network training by reducing internal covariate shift

venue: In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume

authors:
Sangwook Kim
Swathi Kavuri
Minho Lee

title: Deep network with support vector machines

venue: Neural Information Processing,

authors:
Jakub Konečný
H. Brendan McMahan
Felix X. Yu
Peter Richtarik
Ananda Theertha Suresh
Dave Bacon

title: Federated learning: Strategies for improving communication efficiency

venue: In NIPS Workshop on Private Multi-Party Machine Learning,

authors:
Jonathan Krause
Michael Stark
Jia Deng
Li Fei-Fei

title: 3d object representations for finegrained categorization

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

title: Quantizing deep convolutional networks for efficient inference: A whitepaper

venue: ArXiv e-prints,

title: Learning multiple layers of features from tiny images

venue: Technical report, University of Toronto,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E. Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems

venue: Annual Conference on Neural Information Processing Systems

authors:
Yanghao Li
Naiyan Wang
Jianping Shi
Jiaying Liu
Xiaodi Hou

title: Revisiting batch normalization for practical domain adaptation

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C Lawrence Zitnick

title: Microsoft coco: Common objects in context

venue: In European conference on computer vision,

authors:
Wei Liu
Dragomir Anguelov
Dumitru Erhan
Christian Szegedy
Scott Reed
Cheng-Yang Fu
Alexander C Berg

title: Ssd: Single shot multibox detector

authors:
Ningning Ma
Xiangyu Zhang
Hai-Tao Zheng
Jian Sun

title: Shufflenet v2: Practical guidelines for efficient cnn architecture design

venue: arXiv preprint arXiv:1807.11164,

authors:
Subhransu Maji
Esa Rahtu
Juho Kannala
Matthew Blaschko
Andrea Vedaldi

title: Fine-grained visual classification of aircraft

venue: arXiv preprint arXiv:1306.5151,

authors:
Guido F Montufar
Razvan Pascanu
Kyunghyun Cho
Yoshua Bengio

title: On the number of linear regions of deep neural networks

venue: Advances in Neural Information Processing Systems

authors:
Alex Nichol
John Schulman

title: Reptile: a scalable metalearning algorithm

venue: arXiv preprint arXiv:1803.02999,

authors:
M-E. Nilsback
A. Zisserman

title: Automated flower classification over a large number of classes

venue: In Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing,

authors:
Amir Rosenfeld
John K. Tsotsos

title: Intriguing properties of randomly weighted networks: Generalizing while learning next to nothing

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Inverted residuals and linear bottlenecks: Mobile networks for classification, detection and segmentation

venue: arXiv preprint arXiv:1801.04381,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

title: Approximation algorithms for cascading prediction models

venue: In ICML,

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer vision

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

authors:
Jason Yosinski
Jeff Clune
Yoshua Bengio
Hod Lipson

title: How transferable are features in deep neural networks

venue: In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2,

authors:
Xiangyu Zhang
Xinyu Zhou
Mengxiao Lin
Jian Sun

title: Shufflenet: An extremely efficient convolutional neural network for mobile devices

authors:
Bolei Zhou
Agata Lapedriza
Aditya Khosla
Aude Oliva
Antonio Torralba

title: Places: A 10 million image database for scene recognition

venue: IEEE transactions on pattern analysis and machine intelligence,

heading: 1 INTRODUCTION

text:
Deep neural networks have revolutionized many areas of machine intelligence and are now used for many vision tasks that even few years ago were considered nearly impenetrable (Krizhevsky et al., 2012; Simonyan & Zisserman, 2014; Liu et al., 2016). Advances in neural networks and hardware is resulting in much of the computation being shifted to consumer devices, delivering faster response, and better security and privacy guarantees (Konečný et al., 2016; Howard et al., 2017).
As the space of deep learning applications expands and starts to personalize, there is a growing need for the ability to quickly build and customize models. While model sizes have dropped dramatically from >50M parameters of the pioneering work of AlexNet (Krizhevsky et al., 2012) and VGG (Simonyan & Zisserman, 2014) to <5M of the recent Mobilenet (Sandler et al., 2018; Howard et al., 2017) and ShuffleNet (Zhang et al., 2017; Ma et al., 2018), the accuracy of models has been improving. However, delivering, maintaining and updating hundreds of models on the embedded device is still a significant expense in terms of bandwidth, energy and storage costs.
While there still might be space for improvement in designing smaller models, in this paper we explore a different angle: we would like to be able to build models that require only a few parameters to be trained in order to be re-purposed to a different task, with minimal loss in accuracy compared to a model trained from scratch. While there is ample existing work on compressing models and learning as few weights as possible (Rosenfeld & Tsotsos, 2018; Sandler et al., 2018; Howard et al., 2017) to solve a single task, to the best of our awareness, there is no prior work that tries to minimize the number of model parameters when solving many tasks together.
Our contribution is a novel learning paradigm in which each task carries its own model patch – a small set of parameters – that, along with a shared set of parameters constitutes the model for that task (for a visual description of the idea, see Figure 1, left side). We put this idea to use in two scenarios: a) in transfer learning, by fine-tuning only the model patch for new tasks, and b) in multi-task learning, where each task performs gradient updates to both its own model patch, and the
∗Work done while at Google.
shared parameters. In our experiments (Section 5), the largest patch that we used is smaller than 10% of the size of the entire model. We now describe our contribution in detail.
Transfer learning We demonstrate that, by fine-tuning less than 35K parameters in MobilenetV2 (Sandler et al., 2018) and InceptionV3 (Szegedy et al., 2016), our method leads to significant accuracy improvements over fine-tuning only the last layer (102K-1.2M parameters, depending on the number of classes) on multiple transfer learning tasks. When combined with fine-tuning the last layer, we train less than 10% of the model’s parameters in total.We also show the effectiveness of our method over last-layer-based fine-tuning on transfer learning between completely different problems, namely COCO-trained SSD model (Liu et al., 2016) to classification over ImageNet (Deng et al., 2009).
Multi-task learning We explore a multi-task learning paradigm wherein multiple models that share most of the parameters are trained simultaneously (see Figure 1, right side). Each model has a task-specific model patch. Training is done in a distributed manner; each task is assigned a subset of available workers that send independent gradient updates to both shared and task-specific parameters using standard optimization algorithms. Our results show that simultaneously training two such MobilenetV2 (Sandler et al., 2018) models on ImageNet (Deng et al., 2009) and Places365 (Zhou et al., 2017) reach accuracies comparable to, and sometimes higher than individually trained models.
Domain adaptation We apply our multi-task learning paradigm to domain adaptation. For ImageNet (Deng et al., 2009), we show that we can simultaneously train MobilenetV2 (Sandler et al., 2018) models operating at 5 different resolution scales, 224, 192, 160, 128 and 96, while sharing more than 98% of the parameters and resulting in the same or higher accuracy as individually trained models. This has direct practical benefit in power-constrained operation, where an application can switch to a lower resolution to save on latency/power, without needing to ship separate models and having to make that trade-off decision at the application design time. The cascade algorithm from Streeter (2018) can further be used to reduce the average running time by about 15% without loss in accuracy.
The rest of the paper is organized as follows: we describe our method in Section 2 and discuss related work in Section 3. In Section 4, we present simple mathematical intuition that contrasts the expressiveness of logit-only fine-tuning and that of our method. Finally, in Section 5, we present detailed experimental results.

heading: 2 METHOD

text:
The central concept in our method is that of a model patch. It is essentially a small set of perchannel transformations that are dispersed throughout the network resulting in only a tiny increase in the number of model parameters.
Suppose a deep networkM is a sequence of layers represented by their parameters (weights, biases), W1, . . . ,Wn. We ignore non-trainable layers (e.g., some kinds of activations) in this formulation. A model patch P is a set of parameters W′i1 , . . . ,W ′ ik
, 1 ≤ i1, . . . , ik ≤ n that, when applied to M, adds layers at positions i1, . . . , in. Thus, a patched model
M′ = W1, . . . ,Wi1 ,W′i1 , . . . ,Win ,W ′ in , . . . ,Wn
In this paper, we introduce two kinds of patches. We will see below that they can be folded with the other layers in the network, eliminating the need to perform any explicit addition of layers. In Section 5, we shed some light on why the particular choice of these patches is important.
Scale-and-bias patch This patch applies per-channel scale and bias to every layer in the network. In practice this transformations can often be absorbed into normalization layer such as Batch Normalization (Ioffe & Szegedy, 2015). Let X be an activation tensor. Then, the batch-normalized version of X
BN(X) = γ X− µ(X) σ(X) + β
where µ(X), σ(X) are mean and standard deviation computed per minibatch, and γ, β are learned via backpropagation. These statistics are computed as mini-batch average, while during inference they are computed using global averages.
The scale-and-bias patch corresponds to all the γ, β, µ, σ in the network. Using BN as the model patch also satisfies the criterion that the patch size should be small. For instance, the BN parameters in both MobilenetV2 (Sandler et al., 2018) and InceptionV3 network performing classification on ImageNet amounts to less than 40K parameters, of about 1% for MobilenetV2 that has 3.5 million Parameters, and less than 0.2% for Inception V3 that has 25 million parameters.
While we utilize batch normalization in this paper, we note that this is merely an implementation detail and we can use explicit biases and scales with similar results.
Depthwise-convolution patch The purpose of this patch is to re-learn spatial convolution filters in a network. Depth-wise separable convolutions were introduced in deep neural networks as way to reduce number of parameters without losing much accuracy (Howard et al., 2017; Chollet, 2017). They were further developed in Sandler et al. (2018) by adding linear bottlenecks and expansions.
In depthwise separable convolutions, a standard convolution is decomposed into two layers: a depthwise convolution layer, that applies one convolutional filter per input channel, and a pointwise layer that computes the final convolutional features by linearly combining the depthwise convolutional layers’ output across channels. We find that the set of depthwise convolution layers can be repurposed as a model patch. They are also lightweight - for instance, they account for less than 3% of MobilenetV2’s parameters when training on ImageNet.
Next, we describe how model patches can be used in transfer and multi-task learning.
Transfer learning In transfer learning, the task is to adapt a pretrained model to a new task. Since the output space of the new task is different, it necessitates re-learning the last layer. Following our approach, we apply a model patch and train the patched parameters, optionally also the last layer. The rest of the parameters are left unchanged. In Section 5, we discuss the inclusion/exclusion of the last layer. When the last layer is not trained, it is fixed to its random initial value.
Multitask learning We aim to simultaneously, but independently, train multiple neural networks that share most weights. Unlike in transfer learning, where a large fraction of the weights are kept frozen, here we learn all the weights. However, each task carries its own model patch, and trains a patched model. By training all the parameters, this setting offers more adaptability to tasks while not compromising on the total number of parameters.
To implement multi-task learning, we use the distributed TensorFlow paradigm1: a central parameter server receives gradient updates from each of the workers and updates the weights. Each worker reads the input, computes the loss and sends gradients to the parameter server. We allow subsets of workers to train different tasks; workers thus may have different computational graphs, and taskspecific input pipelines and loss functions. A visual depiction of this setting is shown in Figure 1.
1https://www.tensorflow.org/guide/extend/architecture

heading: 3 RELATED WORK

text:
One family of approaches (Yosinski et al., 2014; Donahue et al., 2014) widely used by practitioners for domain adaptation and transfer learning is based on fine-tuning only the last layer (or sometimes several last layers) of a neural network to solve a new task. Fine-tuning the last layer is equivalent to training a linear classifier on top of existing features. This is typically done by running SGD while keeping the rest of the network fixed, however other methods such as SVM has been explored as well (Kim et al., 2013). It has been repeatedly shown that this approach often works best for similar tasks (for example, see Donahue et al. (2014)).
Another frequently used approach is to use full fine-tuning (Cui et al., 2018) where a pretrained model is simply used as a warm start for the training process. While this often leads to significantly improved accuracy over last-layer fine-tuning, downsides are that 1) it requires one to create and store a full model for each new task, and 2) it may lead to overfitting when there is limited data. In this work, we are primarily interested in approaches that allow one to produce highly accurate models while reusing a large fraction of the weights of the original model, which also addresses the overfitting issue.
While the core idea of our method is based on learning small model patches, we see significant boost in performance when we fine-tune the patch along with last layer (Section 5). This result is somewhat in contrast with Hoffer et al. (2018), where the authors show that the linear classifier (last layer) does not matter when training full networks. Mapping out the conditions of when a linear classifier can be replaced with a random embedding is an important open question.
Li et al. (2016) show that re-computing batch normalization statistics for different domains helps to improve accuracy. In Rosenfeld & Tsotsos (2018) it was suggested that learning batch normalization layers in an otherwise randomly initialized network is sufficient to build non-trivial models. Recomputing batch normalization statistics is also frequently used for model quantization where it prevents the model activation space from drifting (Krishnamoorthi, 2018). In the present work, we significantly broaden and unify the scope of the idea and scale up the approach by performing transfer and multi-task learning across completely different tasks, providing a powerful tool for many practical applications.
Our work has interesting connections to meta-learning (Nichol & Schulman, 2018; Finn et al., 2017; Chen et al., 2018). For instance, when training data is not small, one can allow each task to carry a small model patch in the Reptile algorithm of Nichol & Schulman (2018) in order to increase expressivity at low cost.

heading: 4 ANALYSIS

text:
Experiments (Section 5) show that model-patch based fine-tuning, especially with the scale-andbias patch, is comparable and sometimes better than last-layer-based fine-tuning, despite utilizing a significantly smaller set of parameters. At a high level, our intuition is based on the observation that individual channels of hidden layers of neural network form an embedding space, rather than correspond to high-level features. Therefore, even simple transformations to the space could result in significant changes in the target classification of the network.
In this section (and in Appendix A), we attempt to gain some insight into this phenomenon by taking a closer look at the properties of the last layer and studying low-dimensional models.
A deep neural network performing classification can be understood as two parts:
1. a network base corresponding to a function F : Rd → Rn mapping d-dimensional input space X into an n-dimensional embedding space G, and
2. a linear transformation s : Rn → Rk mapping embeddings to logits with each output component corresponding to an individual class.
An input x ∈ X producing the output o := s(F (x)) ∈ Rk is assigned class c iff ∀i 6= c, oi < oc. We compare fine-tuning model patches with fine-tuning only the final layer s. Fine-tuning only the last layer has a severe limitation caused by the fact that linear transformations preserve convexity.
It is easy to see that, regardless of the details of s, the mapping from embeddings to logits is such that if both ξa, ξb ∈ G are assigned label c, the same label is assigned to every ξτ := τξb + (1 − τ)ξa for 0 ≤ τ ≤ 1. Indeed, [s(ξτ )]c = τobc + (1 − τ)oac > τobi + (1 − τ)oai = [s(ξτ )]i for any i 6= c and 0 ≤ τ ≤ 1, where oa := s(ξa) and ob := s(ξb). Thus, if the model assigns inputs {xi|i = 1, . . . , nc} some class c, then the same class will also be assigned to any point in the preimage of the convex hull of {F (xi)|i = 1, . . . , nc}. This property of the linear transformation s limits one’s capability to tune the model given a new input space manifold. For instance, if the input space is “folded” by F and the neighborhoods of very different areas of the input space X are mapped to roughly the same neighborhood of the embedding space, the final layer cannot disentangle them while operating on the embedding space alone (should some new task require differentiating between such “folded” regions).
We illustrate the difference in expressivity between model-patch-based fine-tuning and last-layerbased fine-tuning in the cases of 1D (below) and 2D (Appendix A) inputs and outputs. Despite the simplicity, our analysis provides useful insights into how by simply adjusting biases and scales of a neural network, one can change which regions of the input space are folded and ultimately the learned classification function.
In what follows, we will work with a construct introduced by Montufar et al. (2014) that demonstrates how neural networks can “fold” the input space X a number of times that grows exponentially with the neural network depth2. We consider a simple neural network with one-dimensional inputs and outputs and demonstrate that a single bias can be sufficient to alter the number of “folds”, the topology of the X → G mapping. More specifically, we illustrate how the number of connected components in the preimage of a one-dimensional segment [ξa, ξb] can vary depending on a value of a single bias variable.
As in Montufar et al. (2014), consider the following function:
q(x; b) ≡ 2ReLU ( [1,−1, . . . , (−1)p−1] · vT (x; b) + bp ) ,
where
v(x; b) ≡ [max(0, x + b0),max(0, 2x − 1 + b1), . . . ,max(0, 2x − (p − 1) + bp−1)],
p is an even number, and b = (b0, . . . , bp) is a (p + 1)–dimensional vector of tunable parameters characterizing q. Function q(x; b) can be represented as a two-layer neural network with ReLU activations.
Set p = 2. Then, this network has 2 hidden units and a single output value, and is capable of “folding” the input space twice. Defining F to be a composition of k such functions
F (x; b(1), . . . , b(k)) ≡ q(q(. . . q(q(x; b(1)); b(2)); . . . ; b(k−1)); b(k)), (1)
we construct a neural network with 2k layers that can fold input domain R up to 2k times. By plotting F (x) for k = 2 and different values of b(1)0 while fixing all other biases to be zero, it is easy to observe that the preimage of a segment [0.2, 0.4] transitions through several stages (see figure 2), in which it: (a) first contains 4 disconnected components for b(1)0 > −0.05, (b) then 3 for b (1) 0 ∈ (−0.1,−0.05], (c) 2 for b (1) 0 ∈ (−0.4,−0.1], (d) becomes a simply connected segment for b (1) 0 ∈ [−0.45,−0.4] and (e) finally becomes empty when b (1) 0 < −0.45. This result can also be extended to k > 2, where, by tuning b(1)0 , the number of “folds“ can vary from 2 k to 0.

heading: 5 EXPERIMENTS

text:
We evaluate the performance of our method in both transfer and multi-task learning using the image recognition networks MobilenetV2 (Sandler et al., 2018) and InceptionV3 (Szegedy et al., 2016) and a variety of datasets: ImageNet (Deng et al., 2009), CIFAR-10/100 (Krizhevsky, 2009), Cars (Krause
2In other words, F−1(ξ) for some ξ contains an exponentially large number of disconnected components.
et al., 2013), Aircraft (Maji et al., 2013), Flowers-102 (Nilsback & Zisserman, 2008) and Places365 (Zhou et al., 2017). An overview of these datasets can be found in Table 1. We also show preliminary results on transfer learning across completely different types of tasks using MobilenetV2 and Single-Shot Multibox Detector (SSD) (Liu et al., 2016) networks.
We use both scale-and-bias (S/B) and depthwise-convolution patches (DW) in our experiments. Both MobilenetV2 and InceptionV3 have batch normalization - we use those parameters as the S/B patch. MobilenetV2 has depthwise-convolutions from which we construct the DW patch. In our experiments, we also explore the effect of fine-tuning the patches along with the last layer of the network. We compare with two scenarios: 1) only fine-tuning the last layer, and 2) fine-tuning the entire network.
We use TensorFlow (Abadi et al., 2015), and NVIDIA P100 and V100 GPUs for our experiments. Following the standard setup of Mobilenet and Inception we use 224×224 images for MobilenetV2 and 299×299 for InceptionV3. As a special-case, for Places-365 dataset, we use 256×256 images. We use RMSProp optimizer with a learning rate of 0.045 and decay factor 0.98 per 2.5 epochs.

heading: 5.1 LEARNING WITH RANDOM WEIGHTS

text: To demonstrate the expressivity of the biases and scales, we perform an experiment on MobilenetV2, where we learn only the scale-and-bias patch while keeping the rest of the parameters frozen at their initial random state. The results are shown in Table 3 (right side). It is quite striking that simply adjusting biases and scales of random embeddings provides features powerful enough that even a linear classifier can achieve a non-trivial accuracy. Furthermore, the synergy exhibited by the combination of the last layer and the scale-and-bias patch is remarkable.

heading: 5.2 TRANSFER LEARNING

text:
We take MobileNetV2 and InceptionV3 models pretrained on ImageNet (Top1 accuracies 71.8% and 76.6% respective), and fine-tune various model patches for other datasets.
Results on InceptionV3 are shown in Table 2. We see that fine-tuning only the scale-and-bias patch (using a fixed, random last layer) results in comparable accuracies as fine-tuning only the last layer while using fewer parameters. Compared to full fine-tuning (Cui et al., 2018), we use orders of magnitude fewer parameters while achieving nontrivial performance. Our results using MobilenetV2 are similar (more on this later).
In the next experiment, we do transfer learning between completely different tasks. We take an 18-category object detection (SSD) model (Liu et al., 2016) pretrained on COCO images (Lin et al.,
2014) and repurpose it for image classification on ImageNet. The SSD model uses MobilenetV2 (minus the last layer) as a featurizer for the input image. We extract it, append a linear layer and then fine-tune. The results are shown in Table 3. Again, we see the effectiveness of training the model patch along with the last layer - a 2% increase in the parameters translates to 19.4% increase in accuracy.
Next, we discuss the effect of learning rate. It is common practice to use a small learning rate when fine-tuning the entire network. The intuition is that, when all parameters are trained, a large learning rate results in network essentially forgetting its initial starting point. Therefore, the choice of learning rate is a crucial factor in the performance of transfer learning. In our experiments (Appendix B.2, Figure 9) we observed the opposite behavior when fine-tuning only small model patches: the accuracy grows as learning rate increases. In practice, fine-tuning a patch that includes the last layer is more stable w.r.t. the learning rate than full fine-tuning or fine-tuning only the scale-and-bias patch.
Finally, an overview of results on MobilenetV2 with different learning rates and model patches is shown in Figure 3. The effectiveness of small model patches over fine-tuning only the last layer is again clear. Combining model patches and fine-tuning results in a synergistic effect. In Appendix B, we show additional experiments comparing the importance of learning custom bias/scale with simply updating batch-norm statistics (as suggested by Li et al. (2016)).

heading: 5.3 MULTI-TASK LEARNING

text:
In this section we show that, when using model-specific patches during multi-task training, it leads to performance comparable to that of independently trained models, while essentially using a single model.
We simultaneously train MobilenetV2 (Sandler et al., 2018) on two large datasets: ImageNet and Places365. Although the network architecture is the same for both datasets, each model has its own private patch that, along with the rest of the model weights constitutes the model for that dataset. We choose a combination of the scale-and-bias patch, and the last layer as the private model patch in this experiment. The rest of the weights are shared and receive gradient updates from all tasks.
In order to inhibit one task from dominating the learning of the weights, we ensure that the learning rates for different tasks are comparable at any given point in time. This is achieved by setting hyperparameters such that the ratio of dataset size and the number of epochs per learning rate decay step is the same for all tasks. We assign the same number of workers for each task in the distributed learning environment. The results are shown in Table 4.
Multi-task validation accuracy using a separate S/B patch for each model, is comparable to singletask accuracy, while considerably better than the setup that only uses separate logit-layer for each task, while using only using 1% more parameters (and 50% less than the independently trained setup).

heading: 5.4 DOMAIN ADAPTATION

text:
In this experiment, each task corresponds to performing classification of ImageNet images at a different resolution. This problem is of great practical importance because it allows one to build very compact set of models that can operate at different speeds that can be chosen at inference time depending on power and latency requirements. Unlike in Section 5.3, we only have the scaleand-bias patch private to each task; the last layer weights are shared. We use bilinear interpolation to scale images before feeding them to the model. The learning rate schedule is the same as in Section 5.3.
The results are shown in Table 5. We compare our approach with S/B patch only against two baseline setups. All shared is where all parameters are shared across all models and individually trained is a much more expensive setup where each resolution has its own model. As can be seen from the table, scale-and-bias patch allows to close the accuracy gap between these two setups and even leads to a slight increase of accuracy for a couple of the models at the cost of 1% of extra parameters per each resolution.

heading: 6 CONCLUSIONS, OPEN QUESTIONS AND FUTURE WORK

text: We introduced a new way of performing transfer and multi-task learning where we patch only a very small fraction of model parameters, that leads to high accuracy on very different tasks, compared to traditional methods. This enables practitioners to build a large number of models with small incremental cost per model. We have demonstrated that using biases and scales alone allows pretrained neural networks to solve very different problems. While we see that model patches can adapt to a fixed, random last layer (also noted in Hoffer et al. (2018)), we see a significant accuracy boost when we allow the last layer also to be trained. It is important to close this gap in our understanding of when the linear classifier is important for the final performance. From an analytical perspective, while we demonstrated that biases alone maintain high expressiveness, more rigorous analysis that would allow us to predict which parameters are important, is still a subject of future work. From practical perspective, cross-domain multi-task learning (such as segmentation and classification) is a promising direction to pursue. Finally our approach provides for an interesting extension to the federated learning approach proposed in Konečný et al. (2016), where individual devices ship their gradient updates to the central server. In this extension we envision user devices keeping their local private patch to maintain personalized model while sending common updates to the server.

heading: A ANALYSIS: 2D CASE

text:
Here we show an example of a simple network that “folds” input space in the process of training and associates identical embeddings to different points of the input space. As a result, fine-tuning the final linear layer is shown to be insufficient to perform transfer learning to a new dataset. We also show that the same network can learn alternative embedding that avoids input space folding and permits transfer learning.
Consider a deep neural network mapping a 2D input into 2D logits via a set of 5 ReLU hidden layers: 2D input→ 8D state→ 16D state→ 16D state→ 8D state→m-D embedding (no ReLU) → 2D logits (no ReLU). Since the embedding dimension is typically smaller than the input space dimension, but larger than the number of categories, we first choose the embedding dimension m to be 2. This network is trained (applying sigmoid to the logits and using cross entropy loss function) to map (x, y) pairs to two classes according to the groundtruth dependence depicted in figure 4(a). Learned function is shown in figure 4(c). The model is then fine-tuned to approximate categories shown in figure 4(b). Fine-tuning all variables, the model can perfectly fit this new data as shown in figure 4(d).
Once the set of trainable parameters is restricted, model fine-tuning becomes less efficient. Figures 4(A) through 4(E) show output values obtained after fine-tuning different sets of parameters. In particular, it appears that training the last layer alone (see figure 4(E; top)) is insufficient to adjust to new training data, while training biases and scales allows to approximate new class assignment (see figure 4(C; top)). Notice that a combination of all three types of trainable parameters (biases, scales and logits) frequently results in the best function approximation even if the initial state is chosen to be random (see figure 4(A)-(E); bottom row).
Interestingly, poor performance of logit fine-tuning seen in figure 4(E) extends to higher embedding dimensions as well. Plots similar to those in figure 4, but generated for the model with the embedding dimension m of 4 are shown in figure 5. In this case, we can see that the final layer fine-tuning is again insufficient to achieve successful transfer learning. As the embedding dimension goes higher, last layer fine-tuning eventually reaches acceptable results (see figure 6 showing results for m = 8).
The explanation behind poor logit fine-tuning results can be seen by plotting the embedding space of the original model with m = 2 (see figure 7(a)). Both circular regions are assigned the same embedding and the final layer is incapable of disentangling them. But it turns out that the same network could have learned a different embedding that would make last layer fine-tuning much more efficient. We show this by training the network on the classes shown in figure 7(b). This class assignment breaks the symmetry and the new learned embedding shown in figure 7(c) can now be used to adjust to new class assignments shown in figure 7(d), (e) and (f) by fine-tuning the final layer alone.

heading: B ADDITIONAL EXPERIMENTS

text:
B.1 ADJUSTING BATCH-NORMALIZATION STATISTICS
The results of Li et al. (2016) suggested that adjusting Batch Normalization statistics helps with domain adaption. Interestingly we found that it significantly worsens results for transfer learning, unless bias and scales are allows to learn. We find that fine-tuning on last layer with batch-norm statistics readjusted to keep activation space at mean 0/variance 1, makes the network to significantly under-perform compared to fine-tuning with frozen statistics. Even though adding learned bias/scales signifcanty outperforms logit-only based fine-tuning. We summarize our experiments in Table 6
B.2 ACCURACY VS. LEARNING RATE

heading: C MODEL CASCADES

text: An application of domain adaptation using model patches is cost-efficient model cascades. We employ the algorithm from Streeter (2018) which takes several models (of varying costs) performing the same task, and determines a cascaded model with the same accuracy as the best task but lower average cost. Applying it to MobilenetV2 models on multiple resolutions that we trained via multitask learning, we are able to lower the average cost of MobilenetV2 inference by 15.2%. Note that, in order to achieve this, we only need to store 5% more model parameters than for a single model.

heading: D NOTE ABOUT TRAINING SPEED

text: Generally, we did not see a large variation in training speed. All fine-tuning approaches needed 50-200K steps depending on the learning rate and the training method. While different approaches definitely differ in the number of steps necessary for convergence, we find these changes to be comparable to changes in other hyperparameters such as learning rate.