Timezone: »
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.
Author Information
David Alvarez-Melis (Microsoft)
Vikas Garg (Aalto University/YaiYai Ltd)
Adam Kalai (Microsoft Research New England (-(-_(-_-)_-)-))
More from the Same Authors
-
2021 : Programming Puzzles »
Tal Schuster · Ashwin Kalyan · Alex Polozov · Adam Kalai -
2021 Spotlight: Towards optimally abstaining from prediction with OOD test examples »
Adam Kalai · Varun Kanade -
2022 : Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplings »
Frederike Lübeck · Charlotte Bunne · Gabriele Gut · Jacobo Sarabia del Castillo · Lucas Pelkmans · David Alvarez-Melis -
2022 : Modular Flows: Differential Molecular Generation »
Yogesh Verma · Samuel Kaski · Markus Heinonen · Vikas Garg -
2022 : Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplings »
Frederike Lübeck · Charlotte Bunne · Gabriele Gut · Jacobo Sarabia del Castillo · Lucas Pelkmans · David Alvarez-Melis -
2022 : Provably expressive temporal graph networks »
Amauri Souza · Diego Mesquita · Samuel Kaski · Vikas Garg -
2022 : Modular Flows: Differential Molecular Generation »
Yogesh Verma · Samuel Kaski · Markus Heinonen · Vikas Garg -
2022 : Language Models Can Teach Themselves to Program Better »
Patrick Haluptzok · Matthew Bowers · Adam Kalai -
2023 Poster: Compositional Sculpting of Iterative Generative Processes »
Timur Garipov · Sebastiaan De Peuter · Ge Yang · Vikas Garg · Samuel Kaski · Tommi Jaakkola -
2023 Poster: Going beyond persistent homology using persistent homology »
Johanna Immonen · Amauri Souza · Vikas Garg -
2023 Oral: Going beyond persistent homology using persistent homology »
Johanna Immonen · Amauri Souza · Vikas Garg -
2022 Spotlight: Are GANs overkill for NLP? »
David Alvarez-Melis · Vikas Garg · Adam Kalai -
2022 : Panel »
Vikas Garg · Pan Li · Srijan Kumar · Emanuele Rossi · Shenyang Huang -
2022 : KeyNote 3 by Vikas Garg: Provably Powerful Temporal Graph Networks »
Vikas Garg -
2022 : A Theory of Unsupervised Translation for Understanding Animal Communication »
Shafi Goldwasser · David Gruber · Adam Kalai · Orr Paradise -
2022 : Generating Synthetic Datasets by Interpolating along Generalized Geodesics »
Jiaojiao Fan · David Alvarez-Melis -
2022 Poster: Modular Flows: Differential Molecular Generation »
Yogesh Verma · Samuel Kaski · Markus Heinonen · Vikas Garg -
2022 Poster: Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms »
Surbhi Goel · Sham Kakade · Adam Kalai · Cyril Zhang -
2022 Poster: Symmetry-induced Disentanglement on Graphs »
Giangiacomo Mercatali · Andre Freitas · Vikas Garg -
2022 Poster: Provably expressive temporal graph networks »
Amauri Souza · Diego Mesquita · Samuel Kaski · Vikas Garg -
2021 : Programming Puzzles »
Tal Schuster · Ashwin Kalyan · Alex Polozov · Adam Kalai -
2021 Poster: Towards optimally abstaining from prediction with OOD test examples »
Adam Kalai · Varun Kanade -
2019 Poster: Solving graph compression via optimal transport »
Vikas Garg · Tommi Jaakkola -
2019 Poster: Generative Models for Graph-Based Protein Design »
John Ingraham · Vikas Garg · Regina Barzilay · Tommi Jaakkola -
2019 Poster: Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms »
Vikas Garg · Tamar Pichkhadze -
2018 Poster: Learning SMaLL Predictors »
Vikas Garg · Ofer Dekel · Lin Xiao -
2018 Poster: Supervising Unsupervised Learning »
Vikas Garg · Adam Kalai -
2018 Spotlight: Supervising Unsupervised Learning »
Vikas Garg · Adam Kalai -
2016 Poster: Learning Tree Structured Potential Games »
Vikas Garg · Tommi Jaakkola -
2011 Poster: Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression »
Sham M Kakade · Adam Kalai · Varun Kanade · Ohad Shamir -
2009 Poster: Potential-Based Agnostic Boosting »
Adam Kalai · Varun Kanade