Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
arXiv:2106.02619
Abstract
Generative adversarial networks (GANs) are among the most successful models for learning high-complexity, real-world distributions. However, in theory, due to the highly non-convex, non-concave landscape of the minmax training objective, GAN remains one of the least understood deep learning models. In this work, we formally study how GANs can efficiently learn certain hierarchically generated distributions that are close to the distribution of real-life images. We prove that when a distribution has a structure that we refer to as Forward Super-Resolution, then simply training generative adversarial networks using stochastic gradient descent ascent (SGDA) can learn this distribution efficiently, both in sample and time complexities. We also provide empirical evidence that our assumption "forward super-resolution" is very natural in practice, and the underlying learning mechanisms that we study in this paper (to allow us efficiently train GAN via SGDA in theory) simulates the actual learning process of GANs on real-world problems.
arXiv commentv2 polishes writing
References in corpus (35)
- Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
- GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- On Exact Computation with an Infinitely Wide Neural Net
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Generalization and Equilibrium in Generative Adversarial Nets (GANs)
- Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
- On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
- The Numerics of GANs
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
- Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
- No bad local minima: Data independent training error guarantees for multilayer neural networks
- A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
- Recovery Guarantees for One-hidden-layer Neural Networks
- Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
- Learning One-hidden-layer Neural Networks with Landscape Design
- On the Convergence Rate of Training Recurrent Neural Networks
- Exact Recovery of Sparsely-Used Dictionaries
- What Can ResNet Learn Efficiently, Going Beyond Kernels?
- An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
- Diverse Neural Network Learns True Target Functions
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- Learning One-hidden-layer ReLU Networks via Gradient Descent
- Understanding GANs: the LQG Setting
- Approximability of Discriminators Implies Diversity in GANs
- Theoretical properties of the global optimizer of two layer neural network
- Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates
- Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations
- SGD Learns One-Layer Networks in WGANs
- Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
- Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK