PaperlayerView exact revision on arXiv

Source-linked AI summary

GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium

Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, Sepp Hochreiter

arXiv:1706.08500v6cs.LGstat.ML

TL;DR

The paper addresses the unresolved convergence of stochastic GAN training. It introduces TTUR with separate discriminator and generator learning rates, extends the analysis to Adam, and proposes FID; the authors report convergence to a stationary local Nash equilibrium and improved learning in experiments.

  • Problem

    Convergence properties for general GANs trained with stochastic mini-batch gradients remain an open challenge under realistic assumptions.

  • Method

    The paper introduces TTUR with separate discriminator and generator learning rates, proves its convergence using stochastic approximation, analyzes Adam as heavy ball with friction, and introduces FID.

  • Results

    TTUR and Adam converge to a stationary local Nash equilibrium, while experiments report improved GAN learning and FID that is more consistent than the Inception Score.

  • Takeaways & Limitations

    Separate time scales provide a convergence framework for GAN training, and FID offers a consistency-based measure for evaluating generated images.

  • Takeaways & Limitations

    The convergence analysis assumes locally stable ODE attractors and other stated assumptions, and practical learning rates must be found for each experiment.

Abstract

from arXiv · show

Generative Adversarial Networks (GANs) excel at creating realistic images with complex models for which maximum likelihood is infeasible. However, the convergence of GAN training has still not been proved. We propose a two time-scale update rule (TTUR) for training GANs with stochastic gradient descent on arbitrary GAN loss functions. TTUR has an individual learning rate for both the discriminator and the generator. Using the theory of stochastic approximation, we prove that the TTUR converges under mild assumptions to a stationary local Nash equilibrium. The convergence carries over to the popular Adam optimization, for which we prove that it follows the dynamics of a heavy ball with friction and thus prefers flat minima in the objective landscape. For the evaluation of the performance of GANs at image generation, we introduce the "Fréchet Inception Distance" (FID) which captures the similarity of generated images to real ones better than the Inception Score. In experiments, TTUR improves learning for DCGANs and Improved Wasserstein GANs (WGAN-GP) outperforming conventional GAN training on CelebA, CIFAR-10, SVHN, LSUN Bedrooms, and the One Billion Word Benchmark.

Introduction

GAN training is a game whose convergence remains difficult to establish for general stochastic mini-batch learning. The paper introduces TTUR, proves local convergence, analyzes Adam, and proposes FID for evaluation.

  • GANs train a generator and discriminator in an adversarial game, making convergence to a Nash equilibrium nontrivial for gradient descent.
  • General GAN convergence remains an open challenge because prior proofs often require strong assumptions, linear discriminators, expectations, or infinitely many examples.
  • TTUR assigns separate learning rates to the discriminator and generator and proves convergence to a stationary local Nash equilibrium.
  • Adam is described as heavy ball with friction, yielding a second-order differential equation and a tendency toward flat minima.
  • FID is introduced as a GAN evaluation measure that is more consistent than the Inception Score.

Two Time-Scale Update Rule for GANs

The paper formulates GAN training as a two-time-scale stochastic approximation, assigning separate learning rates to discriminator and generator updates. Under stated regularity, noise, and local-attractor assumptions, the updates converge almost surely to a stationary local Nash equilibrium.

  • Update rule: The framework allows original, improved, and Wasserstein GAN losses rather than restricting analysis to one min-max objective.The discriminator and generator use stochastic gradients of their respective loss functions.
  • Update rule: TTUR assigns separate learning rates b(n) and a(n) to discriminator and generator updates, respectively.The analysis treats GAN gradients as stochastic approximations generated from randomly sampled mini-batches.
  • Assumptions: Convergence analysis assumes Lipschitz gradients, martingale-difference gradient noise, and additional conditions stated for the two stochastic updates.The assumptions include bounded-gradient conditions in the Robbins–Monro mini-batch setting.
  • Assumptions: For each generator parameter, the discriminator ODE must have a locally asymptotically stable attractor λ(θ), while the generator ODE must have a locally asymptotically stable attractor θ∗.These local attractors replace the unique global asymptotically stable equilibria required in earlier work.
  • Convergence: Under the assumptions, the updates converge almost surely to (θ∗, λ(θ∗)), which is a stationary local Nash equilibrium.Equal time-scales provide only repeated visits to an environment of the solution, which may be very large.

Adam Follows an HBF ODE and Ensures TTUR Convergence

The paper characterizes Adam through Heavy Ball with Friction dynamics and uses this connection to extend TTUR convergence analysis. Adam’s update uses first- and second-moment estimates, while the resulting dynamics settle at flatter minima.

  • Adam update rule: Adam maintains exponentially averaged first and second moments of the gradient, then updates parameters using their componentwise normalized ratio.The update includes learning rate a, averaging factors β1 and β2, and stabilizing term ϵ.
  • HBF dynamics and convergence: Theorem 2 represents Adam, under stationary gradient second moments, as a differential equation that permits perturbed-ODE TTUR analysis.The theorem assumes a lower-bounded, continuously differentiable objective and specific β1 and β2 schedules.
  • HBF dynamics and convergence: Adam with TTUR converges when the gradient ∇f is L-Lipschitz, extending the convergence argument through two time-scale stochastic approximation.The analysis is stated for stationary second moments of the gradient.
  • HBF dynamics and convergence: Adam follows Heavy Ball with Friction dynamics, whose Lyapunov energy decreases along trajectories and favors settling at a flat minimum after overshooting a local minimum.The HBF energy is E(t) = 1/2| ˙θ(t)|2+f(θ(t)), with ˙E(t) = −a | ˙θ(t)|2 < 0.

Experiments

The experiments evaluate FID and compare TTUR with conventional one-time-scale training across toy, image, and language settings. TTUR generally improves stability, convergence behavior, and final evaluation metrics.

  • Performance Measure: FID compares Gaussian approximations of real and generated image features using their means and covariances.The features come from an Inception coding layer, and the Gaussian distance is the Fréchet distance, also known as Wasserstein-2 distance.
  • Performance Measure: FID increases monotonically as Gaussian noise, blur, geometric distortions, salt-and-pepper noise, or ImageNet contamination intensify.The paper reports that this behavior is consistent with disturbance level and human judgment, unlike the less consistent Inception Score.
  • Simple Toy Data: In a noisy toy saddle-point problem, TTUR with a faster x update reaches the saddle point faster than equal learning rates.The comparison tracks function values, parameter norms, and (x, y) trajectories; TTUR with a slower y update also converges but more slowly.
  • DCGAN on Image Data: For DCGANs on CelebA, CIFAR-10, SVHN, and LSUN Bedrooms, TTUR is more stable and achieves lower FID than one-time-scale training.The comparison uses mean FID and the range across 8 runs; the paper also reports divergence of all one-time-scale runs for CelebA and LSUN Bedrooms.
  • WGAN-GP on Image Data: For WGAN-GP on CIFAR-10 and LSUN Bedrooms, TTUR reaches lower FIDs than one-time-scale training.TTUR permits a higher discriminator learning rate because the paper reports that it stabilizes learning.
  • WGAN-GP on Language Data: On the One Billion Word benchmark, TTUR outperforms original WGAN-GP training using normalized JSD from 4-gram and 6-gram statistics.The results average performance over 10 runs and align comparisons to wall-clock time.

Conclusion

The paper introduces TTUR, proves convergence to a stationary local Nash equilibrium, extends the analysis to Adam, and proposes FID for GAN evaluation.

  • TTUR converges to a stationary local Nash equilibrium for GAN training.
  • Adam is described by heavy-ball-with-friction dynamics and tends to find flat minima while avoiding small local minima.
  • FID measures similarity between generated and real images better than the Inception Score.
  • TTUR consistently outperforms conventional one-time-scale GAN training across CelebA, CIFAR-10, SVHN, LSUN Bedrooms, and the One Billion Word Benchmark.

A1 Fréchet Inception Distance (FID)

FID compares generated and real data through Gaussian statistics of Inception features, and its values increase consistently as image disturbances become stronger.

  • The Inception Score does not compare synthetic samples with real-world sample statistics, motivating FID as an alternative distance.
  • FID compares generated and real distributions using means and covariances of Inception coding-layer features.The feature distributions are modeled as multidimensional Gaussians, whose difference is measured by the Fréchet distance.
  • FID was evaluated on Gaussian noise, blur, black rectangles, swirls, salt-and-pepper noise, and ImageNet contamination of CelebA.
  • The Inception Score is transformed into the Inception Distance because the score has a maximal value.
  • FID increases monotonically with disturbance level, whereas the Inception Score fluctuates.
  • DCGAN samples on CelebA are shown with FIDs of 500 versus 300, 133 versus 100, and 45 versus 13; WGAN-GP samples have FID 3.

A2 Two Time-Scale Stochastic Approximation Algorithms

Two-time-scale stochastic approximation couples fast and slow iterations with different step sizes, requiring the slower iterate to use the smaller step size.

  • Two-time-scale algorithms consist of two coupled iterations that use different step sizes.
  • The slower iterate uses the smaller step size, while the faster iterate uses the larger step size.
  • At time n, the iterates map a fast variable w_n and a slow variable θ_n to new values.
  • The framework assigns separate step sizes, additive Markov noise processes, and random Markov processes to the slow and fast iterates.

A2.1.1 Additive Noise

The additive-noise convergence result states that, under specified assumptions, the coupled stochastic iterates converge almost surely to an equilibrium determined by the slow variable.

  • The convergence theorem applies to the coupled iterates under these assumptions.
  • The assumptions include conditions on update functions and learning rates.
  • The fast iterate is assumed to have a unique globally asymptotically stable equilibrium λ(θ) that is Lipschitz.
  • The slow iterate is assumed to have a unique globally asymptotically stable equilibrium θ*.
  • The iterates are assumed to remain bounded.
  • Borkar’s theorem states that the iterates converge almost surely to (θ*, λ(θ*) ) when its assumptions are satisfied.

Comments

This section discusses assumptions and technical caveats underlying convergence analyses for stochastic approximation, including bounded noise, mini-batch sampling, weight decay, and proof limitations.

  • Noise assumptions: Mini-batch gradients satisfy the martingale-difference noise condition when indices are sampled uniformly without using past events.Bounded gradients additionally provide bounded noise moments.
  • Weight decay: Weight decay addresses instability caused by region-wise constant discriminators and degenerate second-order derivatives.Without weight decay, a locally constant discriminator can leave the generator with zero gradient and an unstable Nash equilibrium.
  • Proof basis: The main convergence proof relies on results concerning perturbations of ordinary differential equations.This connects the GAN analysis to established stochastic-approximation theory.
  • Related convergence assumptions: The stochastic-approximation framework permits more general noise than martingale-difference sequences, including non-additive noise and settings without bounded iterates under other assumptions.The cited prior results are described as lacking proofs.

A2.1.2 Linear Update, Additive Noise, and Markov Chain

This section formulates linear two-time-scale stochastic approximation with additive noise and Markov-chain extensions, then states assumptions and convergence results for the iterates.

  • Markov-chain setting: The Markov-chain extension models actor-critic learning, with the actor as the slow iterate and the critic as the fast iterate.The environment is driven by actor actions and observed by both processes.
  • Update structure: The fast iterate uses a linear update driven by g(.) and G(.), while the slower process H_n drives changes in θ_n.The framework separates fast and slow dynamics through distinct iterates and update functions.
  • Assumptions: The assumptions include a Markov process on a Polish space, transition kernels, bounded martingale-difference noise, and solutions to Poisson equations.The Poisson equations define averaged quantities and correction functions for the fast iterate.
  • Convergence theorem: The convergence theorem states that, under the assumptions, the iterates defined by the two update equations satisfy the corresponding convergence result.The section identifies this as Theorem 4 attributed to Konda and Tsitsiklis.
  • Extensions: The framework can accommodate nonlinear update rules, dependence of H_n on w_n, and random processes affecting H_n when boundedness conditions hold.The nonlinear case treats linearization errors within the cited framework.

A2.1.3 Additive Noise and Controlled Markov Processes

This section extends stochastic-approximation analysis to controlled Markov processes and discusses assumptions, convergence, linear-rate results, and GAN-specific limitations and consequences.

  • Framework: The general framework uses nonlinear update functions, additive noise, and controlled Markov processes.It is presented as the most general iterate class considered in this development.
  • Controlled Markov processes: Controlled processes are governed by iterates and may include additional random controls, with transition kernels defined for the fast and slow processes.The processes take values in compact metric spaces under the stated assumptions.
  • Assumptions: The analysis assumes regularity conditions including continuity, Lipschitz properties, bounded noise moments, learning-rate conditions, and existence of fast-iterate solutions.When occupation measures are not singleton, the fast dynamics are expressed as a differential inclusion.
  • Stability: An asymptotically stable fast equilibrium λ(θ) with a Lipschitz dependence on θ supports stability of the coupled ordinary differential equation.A Lyapunov function is used for the associated stable set.
  • Convergence: Under the stated assumptions and eventual compact containment of w_n within the attraction domain, the iterates converge to an internally chain transitive set of the differential inclusion.This is the cited Karmakar–Bhatnagar convergence theorem.
  • GAN-specific scope: TTUR convergence assumes the generator learning rate eventually becomes small enough for discriminator convergence, while perturbation size also depends on losses, gradients, architecture, and regularization.Thus, the generator learning rate modulates rather than solely determines discriminator perturbations.
  • GAN-specific scope: Equal learning rates can produce different generator and discriminator dynamics, as shown by decreasing discriminator loss and increasing generator loss in a DCGAN CelebA experiment.The experiment used learning rate 0.0005 for both networks.
Loading 1706.08500v6…