Are GANs overkill for NLP?
Authors: David Alvarez-Melis
Vikas K Garg
Adam Tauman Kalai
Venue: NeurIPS 2022 Accept (2022)
Keywords: generative modeling
maximum likelihood estimation
polynomial reduction
GAN
language model

Abstract: This work offers a novel theoretical perspective on why, despite numerous attempts, adversarial approaches to generative modeling (e.g., GANs) have not been as successful for certain generation tasks, particularly sequential tasks such as Natural Language Generation, as they have in others, such as Computer Vision. In particular, on sequential data such as text, maximum-likelihood approaches are significantly more utilized than GANs. We show that,  while it may seem that maximizing likelihood is inherently different than minimizing distinguishability, this distinction is largely an artifact of the limited representational capacity of the model family, for a wide class of adversarial objectives. We give a theoretical model in which minimizing KL-divergence (i.e., maximizing likelihood) is a more efficient approach to effectively minimizing the same distinguishability criteria that adversarial models seek to optimize. Reductions show that minimizing distinguishability can be seen as simply boosting likelihood for certain families of models including n-gram models and neural networks with a softmax output layer. To achieve a full polynomial-time reduction, a novel next-token distinguishability model is considered. Some preliminary empirical evidence is also provided to substantiate our theoretical analyses.

Are GANs overkill for NLP?
David Alvarez-Melis' Microsoft Research daalvare@microsod com
Vikas Garg" Yai Ltd and Aalto University rgargêcsa il 11. w.m.iiiii....................i.. wwt.met...... edu
Adam Tauman Kalai" Microsoft Research adam@ ka call... a
Abstract
This work offers novel theoretical perspective on why. despite numerous at- tempts, adversarial approaches to generative modeling (e.g., GANs) have not been successful for certain generation tasks, particularly sequential tasks such as Natural Language Generation, as they have in others, such as Computer Vision. In particular, on sequential data such as text, maximum- maximun-likelihood approaches are significantly more utilized than GANs. We show that, while it may seem that maximizing likelihood is inherently different than minimizing distinguishability. this distinction is largely an artifact of the limited representational capacity of the model family, for wide class of adversarial objectives. We give theoretical model in which minimizing KL-divergence (i.e., maximizing likelihood) is a more efficient approach to effectively minimizing the same distinguishability criteria that adversarial models seek to optimize. Reductions show that minimizing dis- tinguishability can be seen simply boosting likelihood for certain families of models including n-gram models and neural networks with a softmax output layer. reduction, novel next-token distinguishability model is considered. Some preliminary empirical evidence is also provided to substantiate our theoretical analyses.
To achieve full polynomial-tin
Introduction
Consider situation where has samples from true distribution p over set X and one wishes to learn to generate similar samples, such as learning to generate English sentences from a large English text corpus. One seeks an approximation q of p which is "close" in some sense and from which samples can efficiently be generated. A common approach to fit these models is Maximum Likelihood Estimation (MLE), which given training from p and parametrized distribution qo seeks parameters 0 that maximize the likelihood qe assigns to training set. MLE has long been one of the most popular methods for fitting generative models of sequential data, such language, where autoregressive neural language models generate remarkably realistic text, e.g., GPT-3 [6] and PaLM [11]. MLE generally involves computing likelihoods qo (x) which can be more challenging some domains than others, e.g., it may be more difficult to estimate the probability of a miin-diimesioonl, real-valued) image than (discrete-valued) sentence.
An alternative approach, Generative Adversarial Networks (GANs), has become popular across several domains, particularly Computer Vision, owing breakthrough realism in the images they output [e.g.. 19, 65]. GANs employ an adversarial approach to generation through a zero-sum game between a generator and a distinguisher in which the generator produces samples x E X which the distinguisher tries to distinguish from real samples from p. Often, both the generator and the distinguisher are differentiable neural networks, though this min-max approach of choosing a model whose outputs are nearly indistinguishable from real examples might be considered for any families of generative models and distinguishers. A major advantage of GANs (particularly for images) is that they can be used for generation without requiring computing likelihoods. This advantage is not
"qqual contribution, alphabetic ordering
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sigmificant for many sequential models such as language models, where computing likelihoods is not difficult.
In contrast, the adversarial approach has yet to demonstrate significant improvements in some other domains such as Natural Language Processing (NLP). One well-known barrier to NLP GANs is that language models produce discrete oulputs (words), so they are not naturally differentiable [18]. However, despite numerous works cireumventing this limitation and adapting GANs to text generation [63, 42, 23, 12], adversarial-ban gains that were seen for images. In particular, language GANs have been shown to under perforr MLE in terms of quality [55] while facing the challenge of lack of diversity due to mode collapse [7],
models have yet to achieve the same popularity or performance
which is a well-known issue with GANs other domains.
1.1 Likelihood and Distinguishability: Two sides of the same coin?
In this work, we suggest a different, fundamental barrier to adopting GANs in domains where MLE is prevalent: the adversarial approach of minimizing distinguishability can be seen as an indirect method of maximizing likelihond on observed data, and hence employing MLE directly can be more efficient. This is the case in NLP where, unlike computer vision, a measure of likelihood called perplexity has been the prevailing metric for training and evaluating language models for decades. We show how GANs boost likelihood in the spirit of, and inspired by, the related celebrated work of Friedman et al. [16] that showed how boosting can be viewed as an iterative approach for logistic regression.
Consider a large finite set or countably infinite set X and family Q of probability distributions over X. For language, these might be n-gram models or neural models. Also consider a family F of distinguishers f X + [0, 1] that aim to distinguish random examples drawn from a distribution p from those sampled from q. For any such classifier f. we call the difference (xf) (xx) [x)]((r)] the distinguishability advantage of f because quantifies the accuracy of f at the task of identifying "fake" examples. A perfect distinguisher would thus have a(f)) = 1, while f(x) 1/2 which predicts at random has a(f)= = O. More formally, imagine picking y E {0. 1} uniformly at random and picking random example x from if y = 1 and from if y = 0. The (randomized) binary classifier that predicts, for any x. ÿ = with probability f(x),, has (expected) accuracy:
1 Σ (())f(x) + &
1 +
= - -1
2 a()
2
Given family F, we define the distinguishabilityy of g from p be d(q) max a(f). Distin- guishability is known to be a lower- on total variation distance (also called statistical distance), measure of distance between distributions that is difficult to directly estimate for large domains X [54]. The "Bayes-optimal" distinguisher simply predicts iff q(x) > p(z). and has advantage equal the total variation distance [see, e.g.. 24]. Clearly d(p) O, i..., p is indistinguishable from itself. Motivated by this observation, numerous adversarial approaches to approximating q have been attempted to minimize distinguishability d(q). If p E Q then d(q) is minimized q p. We first discuss some important aspects of distinguisability.
What adversarial objectives can be analyzed via distinguishability? It is important to emphasize that distinguishability is indeed the objective that several adversarial approaches, such as many variants of GANs, seek to optimize. Depending on the context, it serves the purpose of discriminator or critic. In particular, as established in [54], GANs that are trained based on Kantorovich metric, Mortet-Mourier metric, dual-bounded Lipschitz distance (or the Dudley metric), total variation distance, and kernel distance can all be cast in terms of distinguishability. Thus, in particular, our results hold for GNN formulations such as Wasserstein GANs [1], MMD GANs [33], Fisher GANs [36], and Sobolev GANs [49], for an appropriately chosen family F of distinguishers. For example, we obtain Wasserstein GANs, in its dual form, as special case when F is restricted I-Lipschitz functions in which case it can also be viewed as a special case of the so-called f-GANs [3, 37, 50). Likewise, obtain MMD-GANS when F pertains functions (kernels) defined over ball in some Reproducing Kernel Hilbert Space [4]. Note that distinguishability allows us to accommodate other sophisticared GAN variants such as WGAN-GP [22, 60] that do not suffer from the issue of gradients vanishing on discrete spaces. Recall the WGAN-GP objective can be expressed in our notation as:
Eg]f(=)] - E,]f(>)) + [ (x)]l 1)
2

---

This can be viewed as Lagrangian relaxation of the following hard objective for e >> 0 as:
[x][(())] - [z) S.t.F., ((Ve 1)²] S 6.
Distinguishability advantage can then be readily be expressed as
max f. / [x]((x)) - -,]](x)]
Is distinguishability symmetric or asymmetric? Note that, by definition, distinguishability is asymmetric in the sense that in general g is distinguishable from is different from p is distinguishable from q. Note, however, that we recover integral probability metric (IPM) [54] when -f F for all f E F. Clearly, in this case the notion of distinguishability becomes symmetric as the advantage reduces f [x]](()]]
Thus, distinguishability lets us handle an extremely wide class of discrepancies, symmetric as well as asymmetric.
Example where maximizing likelihood + minimizing distinguishability. When p & Q. mini- mizing distinguishability among E Q may be different than maximizing the likelihood of q. For instance, consider modeling the age in years of humans (say the entire population on earth) as a uniform distribution qm over x E {0. 1, 2,............. ................................ m.. Now, the m which maximizes likelihood would be the age of the oldest person, which is m 119 at the time of this article any smaller m would assign zero probability to the 1ea-year-old and thus to the entire population. However, this distribution is very distinguishable from the true distribution-for instance assigns probability ~ 17% to being over 100 years, which is extremely unlikely among today's 's population. A smaller m < 100 would yield less distinguishable samples. While may seem therefore that distinguishability and likelihood inherently different criteria, as we shall see this is an artificial limitation due to the weakness of family Q.
Of course, the (in)equivalence depends on the families F of distinguishers and Q of probability distri- butions. We give two results showing that maximizing likelihood and minimizing distinguishability are equivalent as long as F and Q are similar in representational capacity, even when p E Q. First, we consider families Q that are "log-lineate over some set F of functions, which include n n-gram models and neural networks whose top layer is a softmax, among others. The equivalence in this case is particularly simple and serves to illustrate how MLE can be a simpler way to reach the same optimum. In this case, Q and F are naturally paired.
Maximizing likelihood minimizing distinguishability for log-linear Q. In the above age ex- ample. the family Q of geometric distributions qo (n) & cxp(-(n) for 0 >> 0 is an example of log-linear family. We show that q can be distinguished from the population distribution p by a function I E F, then folding J into yields new model in Q with greater likelihood. In practice, one only has sample of the true distribution p (not the entire population) and maximizing log-likelihood
is approximation of minimizing KL divergence DKL. (p lI g) = En p(x) log p(z) We give formal statements about minimizing KI-divergence as well.
7(x)*
The conclusion of this first observation is that if GAN were to converge within log-linear family (and making GANs converge is often not an easy feat in practice), it would converge to the MLE.
General polynomial-time reduction. Our second result is polynomial-time reduction from likelihood maximization to next-token distinguishability, without the log-linear requirement. We consider the common case of (unidirectional) sequential models that predict the next token based on the previous tokens, which have several practical advantages including being efficient to compute- the probability of a sequence simply the product of the conditional probabilities of each subsequent word given the previous words. Many state-of the---rrttttt transformer language models such as GPT-3 take this form. Achieving an efficient reduction is challenging due the normalization requirement of computing partition functions. In order to achieve a polynomial-time notion of next-token distinguishabilitt, where the game is as follows: a prefix of tokens is chosen, based on which the generator generates token to follow the prefix. Given the actual next token and the generated next token, the distinguisher aims is to identify which which. Algorithm I leverages a next-token distinguisher to iteratively increase likelihood. In particular, given any target > 0, Theorem I shows that Algorithm will terminate and output an efficiently computable model g which is nearly (to within e) indistinguishable from the truth, and it runs in time polynomial in 1/c.
reduction, we consider a
3

---

If P E Q and one has an optimal distinguisher, one will eventually converge to model close to as has been discussed heavily in the literature. However, our results are also meaningful in the more realistic case where one has imperfect distinguishers.
Contributions. The main contributions of this paper are:
showing that, although in general minimizing distinguishability and maximizing likelihood seem be different, they are in fact closely related,
introducing a new model of next-token distinguishability that is necessary to make the reduction efficient, and offering new perspective on why GANs might have been less successful in NLP and other sequential domains as they have been, e.g., for images.
Organization. We begin by summarizing related work on GANs, especially for text. We then illustrate how GANs can be overkill for the simple case of n-gram models in Section 3. Section covers log-linear models. Section 5 gives explicit bounds general reductions between maximizing likelihood and minimizing distinguishability. Section shows how the reduction can be efficiently computed in the case of sequential inputs, from which propose simple polynomial time algorithm that provably finds a distribution which is inaaly-idisinguuishabll with respect to a given class of discriminator functions. Finally, discuss the relevance of our work in Section 8. All proofs are deferred to the Appendix.
2 Related Work
Generative models. Several approaches to generative modeling have been investigated, especially in the context of images. In particular, impressive results have been obtained recently with variational autoencoders, GANs, normalizing flows, autoregressive models, diffusion processes, and score/energy based models [28, 19, 41, 40, 25, 53, 59, 10]. Generally, training approaches either adversarial; or rely on MIE, contrastive divergence estimation, or score matching [52]. Some connections have begun to emerge between these models, and alternate training procedures have been advocated [9, 53, 62].
A word of caution: Understanding the theoretical underpinnings of generative models with respect to their sample quality is an intriguing question that has been previously investigated by several seminal works such as [27, 21, 39, 56] and requires further analyses. Our objective here is not to claim at all that maximizing likelihood is universally better than adversarial methods or vice-versa, but emphasize that for many problems, in domains like NL.,, the objectives often out to be equivalent mathematically via the notion of distinguishability and maximizing MLEE could provide more efficient (and stable way) of optimizing the common objective. Also, note that maximizing likelihood does not always correlate with the perceptual sample quality [21]. A more comprehensive analysis encompassing the effect of architecture, optimization procedures and issues such as trade-off between perception and distortion [5], training and inference time, mode-collapse etc. is required for better understanding of generative models. In that sense, our message consistent with observations made previously [39, 56, 21] that there is no single model that fits all situations, and the right model depends on the specific requirements of applications.
GANs for text. Since their introduction [19], there has been interest in adapting GANs to text data. The driving motivation was that upp until very recently- samples generated by traditional Mikelihood-based models had been easy to distinguish from huuman-generate text, and the success of image GANs at generating realistic-looking samples suggested a possible avenue to improve the quality of their natural language counterparts.
The first and most significant challenge in adapting GANs text arises from the very nature of this data. Goodfellow [18] points out that GANs require the generator to be differentiable, which poses a challenge for discrete text representations such as one-hot word or character representations. Two of the most popular approaches to circumvent this obstacle are policy gradient techniques (e.g.. REINFORCE [61]] wwiic when applied to language modeling nevertheless often require maximum likelihood pre-training [8, 63])- and the Gumbel--Sftmax approximation [30]. The few adversarial methods that do not require pre-training (e.g.. [42, 45)) have failed to show significant promise in all but a few artificial tasks.

---

This nascent but active line of work seemed to suggest for period of time that GANs might provide a breakthrough text generation. This promise did not fully materialize, and instead the most recent breakthrough came from models building very large transformerrbased architectures like GPT [43, 44, 6] or PaI.M [11] - which are trained with traditional cross-entropy (MI.) objectives.
Yet the question of how GAN-based methods for text compare with likelihood- ones still garners significant interest, and while various works have provided an empirical comparison between them -with most of these suggesting the advantage of MLE-based ones [7]- theoretical explanations have been less explored.
Relating objectives via divergences. The connection between maximum likelihood estimation, distinguishability and divergences between probability distributions has been explored before. For example, it is well known that maximizing likelihood is equivalent to minimizing the KL divergence between certain families of fitted and reference distributions, though this is not the only divergence for which such a connection exists [46]. On the other hand, from the moment GANs were introduced, Goodfellow et al. [19] noted that assuming a perfect discriminator- the adversarial objective divergence. Furthermore, the minimal discrimination error is also directly related to the total variation distance (see, e.g. Hashimoto et al. [24)). On the other hand, for exponential families the gradient of the KL. divergence is known to be related to the discrepancy between distributions [57]. While conceptually similar this line of work, here instead we give an explicit reduction that shows how distinguishability and (log) likelihood are in direct correspondence.
corresponds to minimizing a
Pinsker's inequality is a well-known result linking KL divergence and total variation distance (TVD): TVD < /KL/2. While related, this inequality is not directly relevant to the context of this work. First, while total variation provides an upper bound distinguishability,, it is not computable in general, so it is rarely used as training objective for generative models. On the other hand, being one-sided," it does not imply that reducing TVD reduces KL divergence. Furthermore, Pinsker's is in general a very loose inequality. particularly for the direction of KLD that is equivalent to MLE (i.e., (rI,(y) || qa)), since if p(x) > 0 z yo(x) even for a single x leads to unbounded KL divergence. In contrast, in this work we provide direct reduction directly linking the two criteria of interest: distinguishability and maximum likelihood.
Log-linear language models. In this work we focus our analysis on log-linear models [31, 34], which are widely used in natural language processing (often known in that community as Maximum Entropy -MaxEnt- models) for various tasks. In particular, these models have been cornerstone of both neural [2, 35] and non-neural [47, 26] language modeling.
Boosting. The reduction shown here bears resemblance to boosting. It is well-known that boosting can analyzed through the lens of maximum likelihood (Friedman et al. [16]), while Lebanon and Lafferty [32] formalized the equivalence of AdaBoost and maximum likelihood training for exponential models. More recently, boosting has been applied to generative adversarial models [58, 20), albeit with different approach and objective than the connection drawn in this work.
3 Illustration: GANs for n-gram language models
To illustrate our main point, consider first the simplest model of language: unigram model where the probability of each word is independent, and the end of sentence token EOS has a given probability well. If Ow represents the log-probability of word w, then the log-probability of sentence wi ... W is given by:
log q( [1 w2... wx) = Bw,, + m +... + ow, + fgos-
The MLE parameters 0" can be computed in linear time by simply counting word frequencies.
more roundabout approach fitting a unigram language model would be start with any initial unigram model 4. generate random samples from and compare them to those from One could then distinguish the two by finding word that appears significantly more often in one than in the other. For example, if one generates text from the model and finds that the word "the" occurs much more often in text generated from p. one would then update the parameters by increasing Othe (and
Revvrrse Pinsker's inequalities exist only for particular cases, but they very loose in general [48].
5

---

decreasing Bwr for all other words w' to keep probability distribution). As we shall see later, if this more involved procedure converged, would necessarily converge the same mexximum-likellnne estimator 0"
A similar argument applies any n-gram model in which the probability of each subsequent word is determined only by the previous n 1 words. This is also optimized by frequency counts (a variety of "smoothing" techniques, e.g., adding to counts, also known as Laplace Smoothing [17, 29] are often used as form of regularization on top of these counts). Distinguishers could similarly be used to find a model q that is indistinguishable from p according to n- n-gram frequencies, but again this would simply converge to the MLE parameters.
Equivalence for log-linear models
In this section, we show that there is one optimal log-linear model that both minimizes distinguisha- bility and maximizes log-likelihood. Consider a log-linear model with features f X - [0, 1| i.e. d bounded features fi X + [0, 1J. The model predicts
exp ((f))).))
go(x)
(1)
Zo
where (:-) denotes inner product, E Rd is a parameter vector and Ze = E. exp(0, ((r)) is a normalizing constant called the partition function.
In the unigram example, the features Si would be word counts normalized by dividing by the maximum allowed sentence length (to ensure fi(ar) S 1). In neural network the features fa would correspond to the top layer and 9 computes a softmax. Multiple strategies have been studied for computing estimating the partition function Ze [see, c.g., 14].
As discussed earlier, these feature functions can also be thought of as classifiers that distin- guish examples drawn from from those drawn from qo and the advantage of fi is a(fi) = E. (1(x)410 p(z)). The advantage vector is = {a{fs)) Note that a negative advan- tage be used for distinguishing by using the reverse classifier 1 Ja distinguisher, which has opposite advantage a(1 - fi) = (s))))
Observation 1. The gradient of DxI (p || go) with respect to 0 is the advantage vector alf), i.e. all i = 1,2.....
0D (p qo)
Σ (()))(a())) p(x)) - a(fi).
00;
The above straightforward calculation is well-known is the fact that (pL (p qo) is convex in O. However, we interpret this fact in the context of GANs: searching for 0 which gives a zero-gradient for KL divergence is equivalent While a number of GANs have be designed in various architectures that solve the seemingly more complex problem of ming d(qa), it can generally be more efficient maximize likelihood, which (approximately) minimizes the KL divergence.
finding 0 which is indistinguishable with respect to each fi-
Distinguishability is equivalent to increasing likelihood for general F, Q
In this section, we show how reducing log-loss is equivalent to distinguishing real and generated examples. This is the basis behind single step of our main algorithm (the reduction in this section is efficient for single step, but the increase in runtime would lead to a general exponential-ting algorithm). The bounds here are terms of log-loss, as measured on a specific sample, rather than the abstract KL divergence quantity of the previous section, which cannot be computed exactly using a finite sample. In particular, we show how, if one can distinguish a given distribution from the sample, then one can decrease that distribution's 's log-loss, and vice versa.
For the remainder of this section, we drop 0 from the variable denoting the fitted distribution qe to avoid cluttering the notation. Fix a sample S = (II,..,, E X of n training examples drawn from p. and define the log-loss to be:
7
L(g:
log ((:)) = Esslog ((x)),
71

---

where we use hat on L to denote that the loss is estimated on a (finite) training set S. Likewise, Es[g(æ)) denotes the empirical expectation Ei= (z:).. Note that the expected log-loss over training sets is known as the cross-entropy
H (p, = Es [L: S)],
and hence the expected difference in log-loss between two candidate distributions & and q' is equal to the difference
Es-ip [L S) [(q': = (x (x q')
so minimizing log-loss approximately minimizes the KL divergence. Also, we define the training advantage of distinguisher / X [ to be:
a(f) E,1f(2)) -=ss(())
which is independent of p. depending the sample alone and thus be estimated to arbitrary accuracy using samples generated from q. The lemmas below show how one can use distinguisher reduce log-loss the same training sample, and how to use distribution with lower log-loss to distinguish the two distributions.
Lemma 1. Let a 2 0 and suppose f X - [0,1] has training advantage å(f) 2 a. Then, the probability distribution (x) - ((x)e-=((x)) / where Zg = -xx q(x)e -(f())eef(())) ef(x), has lower log-loss:
il < S) a² d²/2.
Before we give the proof, we note that if f is computed by a neural network and is computed as a neural network with a softmax at the top layer, i.., ((x) = e(v.g(x)) / e(o_g(=)) where g: x + Rd some neural network, then q' is naturally represented as the combined neural network with softmax d' (x) x el(v.-a). ((()) in d dimensions.
This means that if we can distinguish S from q, then we can simply reduce log-loss by down-weighting suspicious samples that satisfy the distinguisher f(x). The difference between this statement and Observation is analogous to the difference between boosting and logistic regression [16]. In logistic regression, one typically fixes the set of features in advance, whereas in boosting this is not possible if there are infinitely many possible classifiers.
Conversely, next show that if o' has lower log-loss than q on the training samples, then can distinguish from these samples.
Lemma 2. For any constant C and distributions q. of such that )g(x) S (xx)) S Cq(x) all X, the distinguisher f X [0, 1] defined by.
1
Cq(a)
f(x) 2 2log C log g'(x))
has training advantage of.
a()) 2 i(g) - L(9)) 2log C
Importantly, due to the logarithmic dependence on C, the above lemma meaningful even g and of are exponentially far apart so long as they have the same support.
Lemma implies a reduction between the problem of distinguishing with nontrivial advantage to non-trivially reducing log-loss for log-linear families. Note that iteratively applying the reduction requires repeated computation of the normalization terms over X, and computing such partition functions is an area of active research-whed it is known how to do efficiently for some classes and not for others. The next section gives an efficient reduction for (unidirectional) sequential models.
Efficient Reduction for Sequential Models
This section gives efficient reduction from distinguishing to MLE for sequential models. This requires showing how one can efficiently compute the normalization terms (partition function) on token-by-token basis for black-box sequential (c.g.. language or auto-regressive) models. The
7

---

key insight for efficiency is that, rather than distinguishing entire sequences from and q. one distinguishes the conditional next-token predictions. particular, rather than generating entire sequences from q, one can generate next-token predictions on all sequence prefixes in the training data.
Clearly, evaluating a neural network over all sequences is infeasible. However, in many applications such NLP, the inputs sequential x (Zi,...,, where every token æ; is taken from large discrete vocabulary. In such cases, the combinatorial nature of the data makes density estimation intractable unless the likelihood computation is broken into small sequential steps by representing the overall probability as the Pr(z) = II, Pr(zy [21, #2, 22....-....11111. -)-1).
In this section we show how a natural extension of the framework described above allows us to achieve efficient reduction for this common type of sequential model. To do so, we define simple generalization the training advantage criterion (2), which now relies on a step-wise distinguisher operating variable-length sequences. Formally, consider language of N-length sequences' of
tokens taken from vocabulary V. and distinguisher functions g U > + [0, 1J, i.e., functions which can take subsequences of any size input. Given sample of sequences, say that has generalized training advantage given by
N
B = B
Eaws
xz-1, - g( mt)]
N
==1
where, by convention, To 0. that ((20 w) (ww). This criterion be interpreted follows. For every length j E (1, first j tokens a frue sequence sampled from S from another j-length sequence in which the last element is replaced by a randomly selected token from the alternate distribution q.
J. N).
is tasked with distinguishing a subsequence consisting of the
Lemma 3. Let b 2 O and suppose g U5 VS - [0, has generalized training advantage A(g) 2 b. We define a distribution o' through its conditional probabilities as:
('x [1,...,; -((x; ; x)-1)e --bbbba( -b(ss......)) / (.)) where now Enf (E1, 25-1) = Ea, {(ū, log-loss than q:
I3-1)e by(at (..-11)))))))))))) Then o' incurs lower i(d:s)= s S) Nb²/2.
The proof is deferred Appendix C.
Next, we use Lemma 3 repeatedly to derive simple algorithm that, given access non-trivial weak distinguishers, returns distribution that is nearly indistinguishable (by that class) from the true distribution p. Formally, let G {g U Vi + [0, 1]} be class of distinguishers. We assume access an oracle Oa Q G which for any g Q returns distinguisher g. In practice, such as in typical GAN training setting, one could think this oracle as being approximated by the subroutine that trains the discriminator. We say that q is i-mnistinguishable by oracle O₂ if its output g has advantage (g S, <
We do need assume that O₂ is optimal in any sense.
Algorithm 1: Boosted weak distinguishers.
Input: Initial model go. corpus S, distinguisher oracle Og, advantage threshold
t 1-00 0
while True do <- Og(ge)
+ Sgt. if <, Output: 4
Compute (z) qe (x)e brar / (z(eee on entire corpus S
t 1-1+1
end
'Padding can be used to handle sequences of variable length.

---

Theorem 1. Let qo be a language model and let e >> O. Algorithm 1 returns distribution q' which is t-indistinguishable from S by oracle Oa- It runs in O (22 Lol TT + n.T (m + n))) time, where Lo Lggo; S) is the log-loss of qo. Ta the runtime of oracle Oa, Tg is the complexity of evaluating any distinguisher on a single impul, = = is the vocabulary size, N is the sequence length and m |S| the number of training sequences.
Thus, Algorithm 1 combined with Theorem and Lemma yields a polynomial time reduction from distinguishing distributions to maximum likelihood estimation for sequential models.
7 An empirical validation of the reductions
We provide empirical validation of Lemma 3. We train a pair of text generator and discriminator using a publicly available implementation" of SegGAN [63]. The generator is pretrained by negative log-likelihood (NLL) minimization. During the adversarial phase training, the generator is trained using policy gradient. After training, we compute the discriminators' generalized training advantage (Equation 2), using finite-sample empirical approximations), and then create a new generator whose next-word logit predictions modified according Lemma 3. We compare the NLL of the original and 'boosted' generators across training epochs, and compare the difference between these to the theoretical lower bound of Lemma 3.
The results, shown in Figure 1 in the Supplement, correspond to the default SeqGAN settings in terms of network capacities and language configuration (maximum sequence length=20, vocabulary size=5000). These results show that the 'boosting' underpinning Lemma 3 does indeed improve likelihood (reduces NLL) as stated, and that the empirical difference is indeed lower-bounded by the gap predicted by theory.
Discussion and conclusions
In this work, we have argued that minimizing log-loss (i.e., KL-divergence) and minimizing statistical distinguishability are tightly related goals. Specifically, if the families of distinguishers and probability distributions are of similar power, then one e.g.. for n-gram language models (and other sequential tasks), for which perplexity (a measure of likelihood) is easy to compute, naturally meaningful, and allows for efficient sampling. Indeed, for long time, minimizing log-loss has been the objective with which most state-of-the-an models have been trained. For such models, Lemma 1 implies that if one distinguish the model from samples by a neural network then one can construct larger neural network with lower log-loss. Hence, one may prefer simply train larger model in the first place for some applications.
a distinguisher to reduce log-loss. This is the case,
Text vs. images. Note that we often can compute conditional likelihoods more efficiently for text data compared to images. The sequential nature of text data allows to compute the normalization terms (and thus the partition function) on a token-by-token basis, thereby enabling us to distinguish the conditional next-token predictions instead of having distinguish full sentences. Similarly, for low dimensional images (such as 8x8, or 4x4), conditional predictions are tractable and thus autoregressive modeling allows for efficient training and sampling. In contrast, MLE based autoregressive models are typically slow for high dimensional real images. In such settings estimating the partition function challenging. so alternative methods such as noise contrastive estimation, score matching, Langevin dynamics, and MCMC sampling in latent space that exploit connections between GANs and energy based models have been preferred [38, 13, 64, 15, 9, 51]. We hope this work fosters further research on the comparative aspects, both pros and cons, of different generative approaches for different NLP and vision applications.
References
[1] M. Arjovsky et al. "Wasserstein Generative Adversarial Networks". In: International Confer- ence on Machine Learning (ICML). 2017, pp. 214-223.
[2] Y. Bengio et al. "A Neural Probabílistic Language Model". In; Journal of Machine Learning Research (JMLR) 3 (2003), pp. 1137-1155.
'nttps://giie htt.:///....caaaaaaaaaaaaaeeeeee

---

[3] G. Biau et al. "Some Theoretical Insights into Wasserstein GANs". In: JMLR (2021).
[4] M. Binkowsk et al. "Demystyfying MMD GANs". In: ICLR. 2018.
[5] Y. Blau and T. Michaeli. "Rethinking Lossy Compression: The Rate-Distortion-Percppiii
Tradeoff". In: International Conference on Machine Learning (ICML). PMLR, 2019, pp. 675-
685.
[6] T. B. Brown et al. Language Models are Few-Shot Learners. 2020. arXiv: 2005 14165 [Cs.
[7]
M. Caccia et al. Language GANs Falling Short. 2018. arXiv: 1811. 02549 [cs , CL]
[8] T. Che al. "Maximun-likelihodd augmented discrete generative adversarial networks". In: arXiv preprint arXiv:/702. 07983 (2017).
[9] T. Che et al. "Your GAN is Secretly an Energy-hased Model and You Should Use Discriminator Driven Latent Sampling". In: Advances Neural Information Processing Systems. Ed. by
H. Larochelle et al. Vol. 33. Curran Associates, Inc., 2020, pp. 12275-12287.
[10] R. T. Q. Chen et al. "Neural Ordinary Differential Equations". In: Advances in Neural Infor- mation Processing Systems. Ed. by S. Bengio et al. Vol. 31. Curran Associates, Inc., 2018.
[11] A. Chowdhery et al. PaLM: Scaling Language Modeling with Pathways. 2022. arXiv: 2204.
02311 [cs.CL),
[12] C. d. M. d' d'Autume et al. "Training language GANs from Scratch". In: arXiv preprint arXiv: 1905 9999099222222... (2019).
[13] B. Dai et al. "Exponential Family Estimation via Adversarial Dynamies Embedding". In: Advances in Neural Information Processing Systems. Vol. 32. 2019.
[14] G. Desjardins et al. "On tracking the partition function". In: Advances in neural information processing systems. 2011, pp. 2501-2509.
[15] C. Finn et al. A Connection between Generative Adversarial Networks, Inverse Reinforcement Learning, and Energy-Based Models. 2016.
[16] J. Friedman et al. "Additive Logistic Regression: a Statistical View of Boosting". In: The Annals of Statistics 38.2 (2000).
[17] J. Good. "The population frequencies of species and the estimation of population parameters". In: Biometrika 40.3-4 (1953), pp. 237-264.
[18] I. Goodfellow. "NIPS 2016 Tutorial: Generative Adversarial Networks". In: arXiv preprint
1xXiv:/701.00100 (2017). [19] I. Goodfellow et al. "Generative Adversarial Nets". In: Advances in Neural Information P Processing Systems (NIPS). 2014, pp. 6672-26800
[20] A. Grover and S. Ermon. "Boosted generative models". In: Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
[21] A. Grover et al. "Flow-GAN: Combining Maximum Likelihood and Adversarial Learning in Generative Models". In: AAAI. AAAI'18/AAA SEAIAAAI///AAAAII
18/EAAT' 2018.
[22] I. Gulrajani et al. "Improved Training of Wasserstein GANs". In: Advances in Neural Informa- tion Processing Systems (NIPS). Vol. 30. 2017.
[23] J. Guo al. "Long text generation via adversarial training with leaked information". In: Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
[24] T. B. Hashimoto et al. "Unifying human and statistical evaluation for natural language genera-
tion". In: Proceedings of NAACL-HLT. 2019, pp. 1689-1701.
[25] J. Ho et al. "Denoising Diffusion Probabilistic Models". In: Advances in Neural Information Processing Systems. Ed. by H. Larochelle et al. Vol. 33. Curran Associates, Inc., 2020, pp. 6840- 6851.
[26] S. Khudanpur and J. Wu. "Maximum entropy techniques for exploiting syntactic, semantic and collocational dependencies in language modeling". In: Computer Speech & Language 14.4 (2000), pp. 355-372.
[27] D. P. Kingma and P. Dhariwal. "Glow: Generative Flow with Invertible 11 Convolutions". In: Neural Information Processing Systems (NIPS). 2018.
[28) D. P. Kingma and M. Welling. "Auto-Encoding Variational Bayes". In: 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings. Ed. by Y. Bengio and Y. LeCun. 2014.
10

---

[29] R. Kneser and H. Ney. "Improved backing-off for gram language modeling". In: 1995 International Conference on Acoustics, Speech, and Signal Processing. Vol. 1. IEEE. 1995, pp. 181-184.
[30] J. Kusner and J. M. Hernández-Lobate "Gans for sequences of discrete elements with the gumbel-softmax distribution". In: arXiv preprint arXiv: 1.04005 (2016).
[31] J. D. Lafferty et al. "Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data". In: International Conference on Machine Learning (ICML). 2001,
pp. 282-289.
[32] G. Lebanon and J. D. Lafferty. "Boosting and Maximum Likelihood for Exponential Models".
In: Advances in Neural Information Processing Systems (NIPS). Ed. by T. G. Dietterich et al.
2002. pp. 447-454.
[33] C.-L. Li al. "MMD GAN: Towards Deeper Understanding of Moment Matching Network".
In: NeurIPS. 2017.
[34] A. McCallum et al. "Maximum Entropy Markov Models for Information Extraction and Segmentation". In: International Conference on Machine Learning (ICML). 2000, pp. 591- 598.
[35] T. Mikolov et al. "Efficient estimation of word representations in vector space". In: arXiv preprint arXiv: /301.388/ (2013).
[36] Y. Mrouch and T. Sercu. "Fisher GAN". In: NeurIPS. 2017.
[37] S. Nowozin et al. "f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization". In: NIPS. 2016.
[38] A. v. d. Oord et al. "Pixel Recurrent Neural Networks". In: (2016).
[39] A. van den Oord and J. Dambre. "Locally-connected transformations for deep GMMs". In:
ICML. 2015.
[40] van den Oord al. "Conditional Image Generation with PixeICNN Decoders". In: Advances in Neural Information Processing Systems. Ed. by D. Lee et al. Vol. 29. Curran Associates, Inc., 2016.
[41] G. Papamakarios et al. "Normalizing Flows for Probabilistic Modeling and Inference". In: J. Mach. Learn. Res. 22 (2021), 57:1-57:64.
[42] Press et al. "I "Language generation with recurrent generative adversarial networks without pre-training". In: 1st Workshop Learning to Generate Natural Language at ICMI 2017. 2017.
[43]
A. Radford et al. "Improving Language Understanding by Generative Pre- Tre-Training. . In: (2018).
[44]
A. Radford et al. "Language models are unsupervised multitask learners". In: OpenAl Blog 1.8 (2019).
[45]
S. Rajeswar et "Adversarial generation of natural language". In: arXiv preprint arXiv: 10929 (2017).
[46] P. Rigollet and J. Weed. "Entropic optimal transport is maximum-likelihone deconvolution".
In: Comptes Rendus Mathematique 1--2 (2018), pp. 1228-1235.
[47] R. Rosenfeld. Adaptive statistical language modeling; maximum entropy approach. Tech. rep.
Carnegie-Mell Mellon University, Department of Computer Science, 1994.
[48]
I. Sason. "On reverse Pinsker inequalities.. In: arXiv preprint arXiv:1503.07118 (2015).
[49] "Sobolev GAN". In:
[50] J. Song and S. Ermon. "Bridging the Gap Between f-GANs and Wasserstein GANs". In: ICML.
2020.
[51] Y. Song and D. P. Kingma. "How to Train Your Energy-Based Models". In: CoRR abs/2101.032 003288 (2021). arXiv: 2101. 03288.
[52] Y. Song et al. "Maximum Likelihood Training of Score-Basee Diffusson Models". In: Advances
in Neural Information Processing Systems. Ed. by A. Beygelzimer et al. 2021.
[53] Y. Song et al. "Score-Based Generative Modeling through Stochastic Differential Equations".
In: International Conference on Learning Representations. 2021.
[54] B. K. Sriperumbudur et al. "On the empirical estimation of integral probability metrics". In:
Electron. J. Stat. 6.none (2012), pp. 1550-1599.

---

[55] G. Tevet et al. "Evaluating Text GANs as Language Models". In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long and Short Pupers). Minneapolis, Minnesota: Association for Computational Linguistics, June 2019, pp. 2241-2247.
[56] L. Theis et al. A note on the evaluation of generative models. 2015.
[57] L. Theis and M. D. Hoffman. "A Trust-region Method for Stochastic Variational Inference
with Applications to Streaming Data". In: International Conference on Machine Learning
(ICML). 2015, pp. 2503-2511.
[58] I. O. Tolstikhin et al. "Adagan: Boosting generative models". In: Advances in Neural Informa- tion Processing Systems. 2017, pp. 5424-5433.
[59] A. Vahdat et al. "Score-based Generative Modeling in Latent Space". In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato et al. Vol. 34, Curran Associates, Inc., 2021, pp. 11877-11302.
[60] X. Wei et al. "Improving the Improved Training of Wasserstein GANs". In: International Conference on Learning Representations (ICLR). 2018.
[61] R. J. Williams. "Simple statistical gradient-following algorithms for connectionist reinforce-
ment learning". In: Machine learning 8.3-4 (1992), pp. 229-256.
[62] O. Yair and T. Michaeli. "Contrastive Divergence Learning is Time Reversal Adversarial Game". In: International Conference on Learning Representations. 2021.
[63] L. Yu et al. "Seqgan: Sequence generative adversarial nets with policy gradient". In: Thirty-
First AAAI Conference on Artificial Intelligence. 2017.
[64] S. Zhai et al. "Adversarial Fisher Vectors for Unsupervised Representation Learning". In: Advances in Neural Information Processing Systems. Ed. by H. Wallach et al. Vol. 32. Curran Associates, Inc., 2019.
[65] H. Zhang et al. Abelf-AAtentioon Generative Adversarial Networks". In: International Confer- ence on Machine Learning (ICML). 2019, pp. 7354-7363.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vIAu3eGC2A6", "reviewer": "Reviewer_vzAW", "summary": "The submission broadly aims at providing arguments for why GANs have not seen much success in sequential generation, as in language, but maximum likelihood models have. \n\nThe submission is entirely theoretical, demonstrating that for a reasonable notion of “distinguishability” of model samples from true samples, one can derive a method to minimize the empirical negative log-likelihood using the output of a classifier that can discriminate (with some effectiveness at least) the model samples from true samples. This derivation connects “distinguishability” (for example, predictions from an adversarial discriminator) with log-likelihood maximization. For sequential models, one can adapt the same procedure to conditional distributions over sequence items, yielding an algorithm reminiscent of boosting, where (possibly-) weak “distinguishers” can be used at each stage to further minimize negative log-likelihood. A run-time analysis of this algorithm is provided.", "questions": "1. Why is Algorithm 1 empirically non-validatable at this stage?\n\n2. How does the recommendation in the paper to perform NLL optimization relate to observations in [4, 5]?\n\n3. Can the method be modified to accommodate unbounded critics?", "limitations": "The authors have discussed potential negative societal impacts.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think some of the phrasing might be a bit misleading to some readers. The abstract suggests that the difference between maximizing likelihood for an explicit model and training an implicit model such as a GAN is “largely artificial”. Having read the paper, I do not find the equivalence this claim seemed to promise: it turns out that the main argument tying the two together is that one can use a differentiating-signal between two distributions to improve log-likelihood for an explicit model. L49-51 claims that GAN training is a “roundabout way of maximizing likelihood on observed data”, but in my reading, the submission does not really substantiate this — it is only shown that a current log-likelihood may be improved if one uses an effective adversary’s predictions to push down probability density at points distinguishable from the true samples by the adversary. In my view, this does not really imply that GAN training is maximum likelihood in disguise in any meaningful sense as seems suggestive in the submission, rather it only suggests that maximum likelihood training may be conducted by using (even weak) adversaries.\n\nThe lack of empirical support is somewhat disappointing, after deriving the algorithm. Algorithm 1 seems implementable, as long as one can design a $g$ that can handle multi-dimensional inputs (or $N$ of them), since Lemma 3 seems to suggest that the normalization is doable by only summing over $|\\mathcal{V}|$ terms. Is there something I’m missing, in terms of practical application, which would explain the lack of empirical validation? Without experimental support, it is unclear if the connection in the paper is actionable: does it buy us anything? The conclusion suggests that the takeaway is that “in applications where it is natural to fit models by minimizing log-loss, it is indeed likely to be a more direct and efficient means of fitting a model”. So is the recommendation that one ought to use “distinguishers” to optimize NLL using the developed procedure? Or that we should directly attempt to optimize NLLs? What would be an example of an unnatural circumstance for fitting models with MLE (recall that for images, flow-based explicit models have been approaching GANs promisingly closely in terms of sample quality, for example [1]; the auto-regressive model PARTI from Google is highly convincing)?\n\nIt would be nice to have some clearer characterization of what is meant by “similar power” in F and Q.\n\nIn general, the question the submission seems to aim to tackle at a high-level (based on the title at the very least) might be too ambitious to settle. With all the moving parts in designing and training a model, such as architectural choices, optimization issues, issues of mode-collapse in generation, and the often unanticipated way they mesh  together (or don’t), the meta-aspects guiding efforts invested by the community on certain approaches over others depending on publicized initial results, pin-pointing reasons for why one class of methods might have seen less success than others is difficult unless a clear technical reason is identified. In my opinion, this submission does not really identify any such issue that clearly informs us why GAN training might be “overkill for NLP”. Once again, recall how the dominant narrative of “GANs are best for image generation, and nothing else comes close” has changed significantly in recent times to “flow, diffusion, and autoregressive models are starting to look really really good!”. \n\nTypo in L349: “to” —> “two”\n\n\nSome related work that are relevant:\n\n — L144-151 does not take into account variants of GANs, such as the WGAN-GP [2], that do not suffer from gradients vanishing on discrete-spaces. More generally, how does the discussion in the paper relate to cases like WGANs where the critic outputs are not in [0, 1]?\n\n — FlowGAN [3] is one relevant work. They report that, in their framework, optimizing for likelihood in a hybrid model results in poor sample quality but good likelihoods, and conversely, using adversarial training results in opposite trends. Related to this observation are the broader observations in [4, 5] about how improved likelihoods need not correspond to improved sample quality in practice for high-dimensional data. \n\nOverall, \n\n — While the paper seems to have decent elements of originality in it,\n\n — and is very clearly written,\n\n — but does not seem to deliver sufficiently in order to be of much practical significance at the current stage. \n\n\n[1] Glow, Kingma and Dhariwal, 2018\n\n[2] WGAN-GP, Gulrajani et al., 2017\n\n[3] FlowGAN, Grover et al., 2018\n\n[4] Locally-connected transformations for deep GMMs, van den Oörd and Dambre, 2015\n\n[5] A note on the evaluation of generative models, Theis et al., 2016.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "c3oaoTwpKEh", "reviewer": "Reviewer_broM", "summary": "This paper analyzes why GANs underperform MLE in natural language generation tasks. The authors argue that minimizing KL-divergence like MLE is a more efficient approach compared with minimizing the same distinguishability criteria in adversarial models. The authors also propose that minimizing distinguishability can be regarded as boosting likelihood for certain families of models including n-gram models and neural networks with a softmax output layer.", "questions": "I have included my questions in the weaknesses part.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. It’s essential and meaningful to give a theoretical analysis on why text GANs fall short. The authors try to connect the minimization of distinguishability and the boosting of the MLE training objective, which is an interesting perspective.\n\nWeaknesses:\n\n1. The organization of this paper should be largely improved. It’s hard for me to follow the detailed derivation because there is always a gap between consecutive formulas. Also, as a paper focusing on text GANs, most parts are about general GANs which are not directly related to texts. For example, the authors mention GANs based on the n-gram model in Section 3. But the sequential formulation of q(x) where $x=w_1 w_2 \\cdots w_t$ is not applied to the following derivation in Section 4 and 5. I feel that many parts of this paper are used to analyze general GANs (such image GANs), which are divergent from the title.\n2. As mentioned in Section 2, the non-differentiable problem of text GANs is always solved by policy gradient or Gumbel-Softmax approximation. I wonder whether the following theoretical analysis consider this step because it plays an important role in the performance of text GANs from the existing works.\n3. Since this paper proposes a specific algorithm (i.e., Algorithm 1 in Section 6), the authors should conduct an experiment (at least on synthetic data) to show the effectiveness of the proposed algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9wCI82UNEFb", "reviewer": "Reviewer_UUT1", "summary": "In this paper, the authors show maximizing likelihood is effectively minimizing distinguishability for log-linear Q. Authors suggest a polynomial-time reduction from likelihood maximization to next-token distinguishability. If the distinguisher has an advantage over a threshold, then a generator network with lower log-loss can be constructed accordingly. Since in sequential domains (eg, text) the likelihood is easier to compute, one might prefer to use MLE in the first place. ", "questions": "Q1: \n\nWhat’s the difference between “distinguisher” and “discriminator”? If they’re the same, maybe authors should unify the terms.\n\nQ2: \n\nIt’s known that MLE minimizes KL divergence and GAN minimizes JS divergence, but this paper assumes GAN minimizes distinguishability. On line 70, “Motivated by this observation, numerous adversarial approaches to approximating q have been attempted to minimize distinguishability d(q)”. Is it an observation, assumption or statement? Can you prove that GAN is indeed minimizing distinguishability (e.g., with what kind of loss for generator/discriminator, using what kind objective, and give the optimal value for D)?\n\nQ3: \n\nWhen you say “distinguishable” or “distinguishability”, is it symmetrical (like JS) or asymmetrical (like KL)? Do “q is distinguishable from p” and “p is distinguishable from q” mean the same thing? \n\nIf it’s asymmetrical (like KL), then it’s not surprising that maximizing likelihood and minimizing distinguishability yield the same convergence in most cases. But I don’t think GANs are using an asymmetrical objective (because discriminator treats real and fake samples equally).\n\nIf it’s symmetrical, then the example about ages you give in line 72-82 does not seem right to me. “A smaller m < 100 would yield less distinguishable samples”. Any q with m < 100 assigns zero probability to ages over 100, hence real samples (with 100+ ages) are very distinguishable from samples in q.  \n\nActually in the ages example, MLE(KL) and GAN(JS) both yields m=119 as the optimal point.\n\nQ4: \n\nDoes your argument work on next-token level GAN only? By next-token level, I mean the generator takes sentence prefix as input, and output the distribution for the next token, and the discriminator takes in prefix + next_token, and predicts a score for only the next_token (assuming prefix is always real). \n\nAnother set of GAN is sentence-level, where discriminator takes in a whole sentence and predicts only one score. This kind of GAN suffers from sparse reward (with RL) or sampling difficulties. \n\nOn next-token level, it’s no news GAN is almost identical as MLE. So the conclusion is not surprising. However the mathematics and proofs in the paper is valuable.\n\nQ5: \n\nI still wonder what makes the fundamental difference between GAN in text and vision. Is it because text models are sequential (so likelihood is easy to compute)? Let’s say if you have an autoregressive image generator which generates small pictures (say 8x8) pixel after pixel, and each pixel is an int in [0,255]. Will your conclusion apply to this kind of sequential model? Will MLE work better than GAN?\n\nCorrect me if I am wrong or misunderstand your point.", "limitations": "I can completely understand this is a theoretical paper, but any experiment (even on toy/synthetic datasets) will further confirm the arguments made by this paper and examine to what extend all the assumptions stand.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nIt’s well known that GANs don’t work so well in the domain of text compared to MLE, yet a thorough investigation is still lacking. The paper offers new and detailed insights into this phenomenon. Previous works explain this as the consequences of having discrete tokens, being not differentiable, sparse reward, optimization challenges, etc. This paper chose a different angle by showing how GAN and MLE are actually closely related.\n\nThe usage of “distinguishability” to analyze GAN is new.\n\nThe general reduction is useful and solid. It’s good to see asymptotic analysis.\n\nThe argument is backed with mathematics derivations. An essential algorithm is given. Assumptions are clearly given before claims.\n\nThe final conclusion is straightforward and clear.\n\nOverall this paper is working on a topic with significance. People do care why GANs can/cannot work on text. This paper is making contributions and casting new insights into this problem.\n\n# Weaknesses\n\nThe introduction of “distinguishability” is abrupt to me. See Q2.\n\nThe relation of distinguishability, likelihood(KL divergence) and JS divergence should be discussed further. See Q2 Q3.\n\nIt seems this paper focuses on next-token level GANs and not sentence level GAN. See Q4.\n\n“GANs are overkill for NLP” seems too strong a claim, unless you can be very sure that you cover all types of GAN in NLP.\n\nIn general, I'm positive for this paper, but I still have some concerns that need to be addressed.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7qjsqB2K95k", "reviewer": "Reviewer_jtPN", "summary": "This paper argues that training a GAN, which minimizes distinguishability between a learned and actual distribution, and maximizing likelihood, are often equivalent for NLP tasks. They do this by (i) giving a case where minimizing distinguishability is not the same as maximizing likelihood due to limitations in the set of possible generates, then (ii) showing how training a GAN is equivalent to maximizing likelihood for n-gram models, then (iii) showing how training distinguishing reduces log loss, and finally (iv) showing a polynomial-time reductions from a distinguishing distribution to an MLE for sequence models.", "questions": "* [140-141]: Is it the case that likelihood-based models generated text that could be easily distinguished from humans? I think fake-news detection, etc. has been an issue for at least 5 years? \n* What is novel about the next-token distinguisher? Is this not a direct application of the standard GAN objective for classification to sequence modeling? ", "limitations": "N/A. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* The paper gives good theoretical motivation for an empirical phenomenon that, to the best of my knowledge, wasn't well understood. In particular, previous explanations argued that \n* The exposition in the paper is great; the authors help motivate with simple cases where distinguishability + MLE are different, then show how they're the same in an intuitive and realistic case, then provide general theory\n* The explicit polynomial time reduction seems like a strong theoretical contribution.  \n\nWeaknesses\n* The main weakness is the lack of empirical validation; in particular, it would've been nice to see if GANs actually do end up at the MLE in simple cases, and whether the rate at which they do is slower, as argued in the paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept