2020

Making Method of Moments Great Again? -- How can GANs learn distributions

Li, Yuanzhi, Dou, Zehao

Understand

Generative Adversarial Networks (GANs) are widely used models to learn complex real-world distributions.

In GANs, the training of the generator usually stops when the discriminator can no longer distinguish the generator's output from the set of training examples.
A central question of GANs is that when the training stops, whether the generated distribution is actually close to the target distribution, and how the training process reaches to such configurations efficiently? In this paper, we established a theoretical results towards understanding this generator-discriminator training process.
We empirically observe that during the earlier stage of the GANs training, the discriminator is trying to force the generator to match the low degree moments between the generator's output and the target distribution.

Built on

Can SGD Learn Recurrent Neural Networks with Provable Generalization?
Original
Zeyuan Allen-Zhu and Yuanzhi Li · 1902
Earlier work this paper cites.
What Can ResNet Learn Efficiently, Going Beyond Kernels?
Original
Zeyuan Allen-Zhu and Yuanzhi Li · 1905
Earlier work this paper cites.
Matrix perturbation theory
Gilbert W Stewart · 1990
Earlier work this paper cites.
Universal approximation bounds for superpositions of a sigmoidal function
Andrew R Barron · 1993
Earlier work this paper cites.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel A Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
A spectral algorithm for learning mixture models
Santosh Vempala and Grant Wang · 2004
Earlier work this paper cites.
K-means has polynomial smoothed complexity
David Arthur, Bodo Manthey, and Heiko Röglin · 2009
Earlier work this paper cites.
An elementary proof of anti-concentration of polynomials in gaussian variables
Shachar Lovett · 2010
Earlier work this paper cites.
Settling the polynomial learnability of mixtures of gaussians
Ankur Moitra and Gregory Valiant · 2010
Earlier work this paper cites.
A spectral algorithm for latent dirichlet allocation
Anima Anandkumar, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Yi-Kai Liu · 2012
Earlier work this paper cites.
Concentration and moment inequalities for polynomials of independent random variables
Warren Schudy and Maxim Sviridenko · 2012
Earlier work this paper cites.
Tensor decompositions for learning latent variable models
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky · 2014
Earlier work this paper cites.
New algorithms for learning incoherent and overcomplete dictionaries
Sanjeev Arora, Rong Ge, and Ankur Moitra · 2014
Earlier work this paper cites.
Smoothed analysis of tensor decompositions
Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan · 2014
Earlier work this paper cites.
Generative adversarial nets
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio · 2014
Earlier work this paper cites.
Escaping from saddle points—online stochastic gradient for tensor decomposition
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan · 2015
Earlier work this paper cites.
Unsupervised representation learning with deep convolutional generative adversarial networks
Original
Alec Radford, Luke Metz, and Soumith Chintala · 2015
Earlier work this paper cites.
Lazysvd: Even faster svd decomposition yet without agonizing pain
Zeyuan Allen-Zhu and Yuanzhi Li · 2016
Earlier work this paper cites.
A latent variable model approach to pmi-based word embeddings
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski · 2016
Earlier work this paper cites.
Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity
Amit Daniely, Roy Frostig, and Yoram Singer · 2016
Earlier work this paper cites.
Deep learning without poor local minima
Kenji Kawaguchi · 2016
Earlier work this paper cites.
Recovery guarantee of non-negative matrix factorization via alternating updates
Yuanzhi Li, Yingyu Liang, and Andrej Risteski · 2016
Earlier work this paper cites.
No bad local minima: Data independent training error guarantees for multilayer neural networks
Original
Daniel Soudry and Yair Carmon · 2016
Earlier work this paper cites.
Diversity leads to generalization in neural networks
Original
Bo Xie, Yingyu Liang, and Le Song · 2016
Earlier work this paper cites.
Doubly accelerated methods for faster cca and generalized eigendecomposition
Zeyuan Allen-Zhu and Yuanzhi Li · 2017
Earlier work this paper cites.
First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate
Zeyuan Allen-Zhu and Yuanzhi Li · 2017
Earlier work this paper cites.
Wasserstein gan
Original
Martin Arjovsky, Soumith Chintala, and Léon Bottou · 2017
Earlier work this paper cites.
Generalization and equilibrium in generative adversarial nets (gans)
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang · 2017
Earlier work this paper cites.
Theoretical properties of the global optimizer of two layer neural network
Original
Digvijay Boob and Guanghui Lan · 2017
Earlier work this paper cites.

Similar

Globally optimal gradient descent for a convnet with gaussian inputs
Original
Alon Brutzkus and Amir Globerson · 2017
Cited alongside, same era.
Understanding gans: the lqg setting
Original
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse · 2017
Cited alongside, same era.
Learning one-hidden-layer neural networks with landscape design
Rong Ge, Jason D. Lee, and Tengyu Ma · 2017
Cited alongside, same era.
Learning one-hidden-layer neural networks with landscape design
Original
Rong Ge, Jason D Lee, and Tengyu Ma · 2017
Cited alongside, same era.
Improved training of wasserstein gans
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville · 2017
Cited alongside, same era.
Gans trained by a two time-scale update rule converge to a local nash equilibrium
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter · 2017
Cited alongside, same era.
Progressive growing of gans for improved quality, stability, and variation
Original
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen · 2017
Cited alongside, same era.
Mmd gan: Towards deeper understanding of moment matching network
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos · 2017
Cited alongside, same era.
Provable alternating gradient descent for non-negative matrix factorization with strong correlations
Yuanzhi Li and Yingyu Liang · 2017
Cited alongside, same era.
Convergence analysis of two-layer neural networks with relu activation
Original
Yuanzhi Li and Yang Yuan · 2017
Cited alongside, same era.
The numerics of gans
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger · 2017
Cited alongside, same era.
Gradient descent gan optimization is locally stable
Vaishnavh Nagarajan and J Zico Kolter · 2017
Cited alongside, same era.

Then

Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Later among the works it cites.
Learning overparameterized neural networks via stochastic gradient descent on structured data
Yuanzhi Li and Yingyu Liang · 2018
Later among the works it cites.
Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang · 2018
Later among the works it cites.
The well-tempered lasso
Yuanzhi Li and Yoram Singer · 2018
Later among the works it cites.
Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks
Original
Tengyuan Liang and James Stokes · 2018
Later among the works it cites.
Spectral normalization for generative adversarial networks
Original
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida · 2018
Later among the works it cites.
Polynomial convergence of gradient descent for training one-hidden-layer neural networks
Original
Santosh Vempala and John Wilmes · 2018
Later among the works it cites.
Self-attention generative adversarial networks
Original
Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena · 2018
Later among the works it cites.
Learning one-hidden-layer relu networks via gradient descent
Original
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu · 2018
Later among the works it cites.
Stochastic gradient descent optimizes over-parameterized deep relu networks
Original
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu · 2018
Later among the works it cites.
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
Original
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang · 2019
Later among the works it cites.
A convergence theory for deep learning via over-parameterization
Original
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song · 2019
Later among the works it cites.
On the convergence rate of training recurrent neural networks
Original
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song · 2019
Later among the works it cites.
On exact computation with an infinitely wide neural net
Original
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang · 2019
Later among the works it cites.
Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks
Original
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang · 2019
Later among the works it cites.
Generalization bounds of stochastic gradient descent for wide and deep neural networks
Yuan Cao and Quanquan Gu · 2019
Later among the works it cites.
Linearized two-layers neural networks in high dimension
Original
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari · 2019
Later among the works it cites.
Finite depth and width corrections to the neural tangent kernel
Original
Boris Hanin and Mihai Nica · 2019
Later among the works it cites.
Sgd learns one-layer networks in wgans
Original
Qi Lei, Jason D Lee, Alexandros G Dimakis, and Constantinos Daskalakis · 2019
Later among the works it cites.
Towards explaining the regularization effect of initial large learning rate in training neural networks
Original
Yuanzhi Li, Colin Wei, and Tengyu Ma · 2019
Later among the works it cites.
On gradient descent ascent for nonconvex-concave minimax problems
Original
Tianyi Lin, Chi Jin, and Michael I Jordan · 2019
Later among the works it cites.
A priori estimates of the population risk for two-layer neural networks
Chao Ma, Lei Wu, et al · 2019
Later among the works it cites.
A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach
Original
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil · 2019
Later among the works it cites.
Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation
Original
Greg Yang · 2019
Later among the works it cites.
An improved analysis of training over-parameterized deep neural networks
Difan Zou and Quanquan Gu · 2019
Later among the works it cites.
Backward feature correction: How deep learning performs deep learning
Original
Zeyuan Allen-Zhu and Yuanzhi Li · 2020
Closest in time.
Feature purification: How adversarial training performs robust deep learning
Original
Zeyuan Allen-Zhu and Yuanzhi Li · 2020
Closest in time.
Towards understanding ensemble, knowledge distillation and self-distillation in deep learning
Original
Zeyuan Allen-Zhu and Yuanzhi Li · 2020
Closest in time.
Learning over-parametrized two-layer neural networks beyond ntk
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…