Generative Adversarial Networks

A GAN consists of two neural networks with opposing objectives, trained jointly via Gradient Descent and Backpropagation-style optimization. The generator $G_\theta: \mathcal{Z} \to \mathcal{X}$ maps a latent noise vector $z \sim p_z$ (typically $z \sim \mathcal{N}(0, I)$ or $\text{Uniform}[-1,1]^d$) to a synthetic sample $G_\theta(z)$ in data space. The discriminator $D_\phi: \mathcal{X} \to [0,1]$ is a binary classifier that outputs the probability that an input $x$ came from the real data distribution $p_{data}$ rather than from $G$. Crucially, $G$ never sees real training data. It only receives a gradient signal through $D$: the derivative of $D$'s output with respect to $D$'s input, backpropagated further through $G$'s parameters. This is what makes generation implicit — there is no explicit formula for $p_G(x)$, the distribution induced by pushing $p_z$ through $G$. We can sample from $p_G$ (run $G$ forward), but we cannot evaluate its density. The training objective is the minimax game:

Read this as: $D$ wants to maximize $V$ by assigning high probability (close to 1) to real samples and low probability (close to 0) to fakes; $G$ wants to minimize $V$, i.e., make $D(G(z))$ close to 1 so the second term becomes very negative (log of something near 1 is close to 0, undermining $D$). This is a zero-sum game: $D$'s gain is $G$'s loss. Formally it is a Nash-equilibrium-seeking process over two function classes (neural network parameter spaces), not a single joint optimization — this distinction is exactly why training a GAN behaves very differently from training an ordinary supervised classifier.

Setup. Choose architectures for $G_\theta$ and $D_\phi$ (typically convolutional networks for images). Choose a noise prior $p_z$. Initialize $\theta, \phi$ randomly.

Alternating optimization. In each iteration: 1. Sample a minibatch of real data and a minibatch of noise; update $D$ to increase $V$ (a few steps, often just one). 2. Sample a fresh minibatch of noise; update $G$ to decrease $V$ (one step). A crucial practical fix, introduced in the original 1963 minimax formulation's neural instantiation, is the non-saturating generator loss: instead of minimizing $\log(1 - D(G(z)))$ (whose gradient vanishes when $D$ is confidently correct, i.e., $D(G(z)) \approx 0$, early in training), the generator instead maximizes $\log D(G(z))$. Both losses share the same fixed point but the non-saturating version supplies much stronger gradients when $G$ is weak. ``` Algorithm: GAN Training (non-saturating variant) Input: real dataset X, noise prior p_z, learning rates η_D, η_G, discriminator steps per generator step k Initialize discriminator parameters φ, generator parameters θ for iteration = 1, 2, ... do

# ---- Discriminator phase: k steps ---- for step = 1 to k do sample minibatch {x_1, ..., x_m} from X sample minibatch {z_1, ..., z_m} from p_z

# fake samples via current generator (no grad needed into θ here) x̂_i ← G_θ(z_i) for i = 1..m L_D ← -(1/m) Σ_i [ log D_φ(x_i) + log(1 - D_φ(x̂_i)) ] φ ← φ - η_D ∇_φ L_D # gradient DESCENT on the negative of V end for

# ---- Generator phase: 1 step ---- sample minibatch {z_1, ..., z_m} from p_z x̂_i ← G_θ(z_i) for i = 1..m L_G ← -(1/m) Σ_i log D_φ(x̂_i) # non-saturating loss θ ← θ - η_G ∇_θ L_G end for return θ, φ ``` Notes on correctness of the pseudocode:

• $D$'s gradient step is ascent on $V(D,G)$, implemented as descent on $-V$, i.e. the standard binary cross-entropy loss with real samples labeled 1 and fake samples labeled 0.
• During the $D$ update, gradients must not flow into $\theta$ (the fake batch is treated as a constant input to $D$); during the $G$ update, $\phi$ is held fixed and gradients flow through $D_\phi(G_\theta(z))$ back into $\theta$ only.
• The base case is the random initialization: at iteration 0, $D$ is a coin flip and $G$ produces noise-like output; the invariant maintained across iterations is that $D$ is always trained to (approximately) reach its optimum for the current $G$ before $G$ is updated — this is what the inner loop of $k$ steps approximates.

Time complexity per iteration. Let $C_G$ and $C_D$ be the cost of one forward+backward pass through $G$ and $D$ respectively, on a batch of size $m$. One full iteration costs $O(k \cdot (C_D)) + O(C_G + C_D)$ — the discriminator phase runs $k$ forward/backward passes through $D$ (plus $k$ forward passes through $G$ to generate fakes, though these can be cheap if $\theta$ is frozen and reused), and the generator phase runs one forward/backward through both networks. In practice $k=1$ is common, giving a per-iteration cost of the same order as training an ordinary classifier plus an ordinary regressor jointly: $O(C_G + C_D)$ per iteration, i.e. linear in network size and batch size, identical in order to standard supervised training — GANs do not introduce a big-O overhead over ordinary deep network training. The overhead is entirely in how many iterations are needed to reach a usable equilibrium, which is not captured by per-step complexity and is empirically much larger and less predictable than for supervised classifiers.

Space complexity. $O(|\theta| + |\phi| + m \cdot d)$ for parameters and the activations of the current minibatch (dimension $d$), same order as training two separate feedforward-style networks — no additional asymptotic memory cost is inherent to the adversarial framing itself.

Correctness — what is being optimized, and what is the fixed point? Fix $G$. For any fixed generator, the inner maximization over $D$ has a clean closed form. Writing $p_g$ for the density induced by $G$, the value function is

For each fixed $x$, this integrand is of the form $a \log y + b \log(1-y)$ with $a = p_{data}(x), b = p_g(x)$, maximized over $y \in (0,1)$. Taking the derivative and setting it to zero:

So the optimal discriminator for a fixed $G$ is

This matches intuition: where $p_{data}$ dominates $p_g$, $D^*$ is close to 1; where $p_g$ dominates, $D^*$ is close to 0; where they're equal, $D^* = 1/2$. Substituting $D^*_G$ back into $V$ gives the effective generator objective, which algebra shows equals

where $JSD$ is the Jensen–Shannon divergence, a symmetric, bounded ($\in [0, \log 2]$) divergence between distributions. Since $JSD(p\|q) \ge 0$ with equality iff $p = q$, we get $C(G) \ge -\log 4$ with equality iff $p_g = p_{data}$. This is the correctness argument: the global minimum of the outer minimization over $G$ is achieved exactly when the generator's distribution matches the true data distribution, and at that point the optimal discriminator is $D^*(x) = 1/2$ everywhere — it cannot do better than a coin flip because the two distributions are literally identical.

Caveats on the proof (be honest about the gap between theory and practice).

• The argument assumes $D$ and $G$ have unlimited capacity and that at every outer step $D$ is trained fully to its optimum $D^*_G$ — neither holds for finite neural networks trained with a few gradient steps.
• The proof establishes existence and uniqueness of the global equilibrium in distribution space, but says nothing about whether gradient-based alternating optimization actually converges to it — alternating gradient descent on a minimax objective is not guaranteed to converge even in simple bilinear games, and can cycle or oscillate. This gap between theory and observed training instability (mode collapse, non-convergence, vanishing gradients when $D$ is too strong) is exactly what GAN Training Dynamics and Failure Modes addresses.
• Because $p_g$ is never written explicitly, we cannot directly evaluate $JSD(p_{data}\|p_g)$ during training; it is only a theoretical tool for the proof, not a quantity monitored in practice.

Consider a toy 1-D setting to make the abstract game concrete. Suppose the true data distribution is $p_{data} = \mathcal{N}(5, 1)$, and at the current training iteration the generator produces $p_g = \mathcal{N}(3, 1)$ (it has not yet converged). $D$ is a simple logistic model $D(x) = \sigma(w x + b)$, currently at $w=1.0, b=-4.0$. Draw a minibatch (m = 4) — 2 real samples, 2 fake samples:

Discriminator loss (binary cross-entropy, matching $-V/m$):

This is much better than the initial coin-flip loss of $\log 2 \approx 0.693$, telling us $D$ has already learned to separate the two clusters (centered at 3 vs 5) reasonably well. Backpropagating $\partial L_D/\partial w, \partial L_D/\partial b$ and taking a gradient step increases $w$ and adjusts $b$ so the decision boundary sharpens around $x \approx 4$.

Generator loss (non-saturating). Using the same $D$ (now momentarily frozen) on the fake batch only:

The gradient $\partial L_G/\partial \theta$ flows backward through $D$'s logit at $\hat x_1, \hat x_2$ (pushing $D(\hat x)$ toward 1, i.e., pushing the logit $\hat x - 4$ upward) and then through $G_\theta(z)$, nudging $\theta$ so that future samples land further to the right — directly toward the real cluster at mean 5. Repeating this alternation over many iterations moves $p_g$'s mean from 3 toward 5 and shrinks the gap the discriminator can exploit, exactly as the JSD argument predicts: as $p_g \to p_{data}$, $D$'s achievable accuracy collapses toward 50%.

Contrast with a trivial case. Note this example is deliberately non-symmetric: $p_g \ne p_{data}$ initially, $D$ is not at 50% accuracy, and the two loss values ($0.316$ vs $1.314$) are meaningfully different — showing the asymmetric, adversarial pull of the game, rather than an already-converged or symmetric toy case that would hide how the gradients actually behave early in training.

The GAN idea emerged from a now-famous account: Goodfellow reportedly sketched the minimax formulation after a late-night bar conversation about whether adversarial competition between two networks could substitute for an explicit likelihood model, and implemented the first version within the same night. The paper's clean two-player game framing borrowed intuition from Game Theory and Minimax Reasoning, while its practical machinery — backpropagation through two coupled networks — rests entirely on ordinary Gradient Descent and Backpropagation applied to each player in turn. Within a year, the field split into a flurry of architectural stabilizations (DCGAN), theoretical reformulations of the divergence being minimized (Wasserstein GAN, f-GANs), and applied variants (pix2pix, CycleGAN, StyleGAN) that made GANs a dominant tool for realistic image and video synthesis before diffusion models later became competitive on sample quality and training stability.

GANs (and their descendants) underlie a wide swath of production and research systems: StyleGAN-family models for photorealistic face and asset synthesis in gaming and film pre-visualization; pix2pix and CycleGAN for image-to-image translation (sketches-to-photos, satellite-to-map imagery, medical image domain adaptation); super-resolution GANs (SRGAN, ESRGAN) used in photo restoration and upscaling pipelines; data augmentation for training classifiers when labeled real data is scarce, especially in medical imaging; and speech synthesis vocoders (e.g., adversarial components in some neural vocoders) that produce more natural-sounding audio than purely regression-trained models. The adversarial training principle — pit a learned critic against a generator — also seeds ideas beyond raw image synthesis, including adversarial robustness testing, domain adaptation, and some reinforcement-learning-adjacent imitation learning setups (e.g., GAIL). Understanding the basic minimax game here is the prerequisite for understanding why these systems are hard to train reliably, which is the subject taken up directly in GAN Training Dynamics and Failure Modes.

Ask the tutor: Why does alternating gradient descent on the GAN minimax objective fail to guarantee convergence, even though the theoretical global equilibrium is unique?