Section 3b: The convex conjugate and the variational bound

I am working through Mathematical Foundations of Generative AI, Prof. Prathosh AP's public lectures. The playlist is the spine. These notes are my deep dive on each section: a visual when the picture is the point, a detour when a prerequisite is doing real work, and the formula in my own words.

Previously: Section 3a: f-divergences.

Section 3b: The convex conjugate and the variational bound

This is the last part of Week 1, and it fixes the catch from 3a: I cannot compute $D_f$ directly because it needs the densities $P_x(x)$ and $P_\theta(x)$, and I only have samples. By the end of this section, $D_f$ is rewritten using only averages over samples. That rewritten form is the GAN objective in disguise.

The statement I am carrying:

$$D_f(P_x \,|\, P_\theta) \;\ge\; \sup_{T \in \mathcal{T}} \Big( \mathbb{E}{x \sim P_x}[T(x)] \;-\; \mathbb{E}{x \sim P_\theta}\big[f^*(T(x))\big] \Big)$$

where $f^$ is the convex conjugate of $f$, and $T: \mathcal{X} \to \operatorname{dom} f^$ ranges over a class of functions $\mathcal{T}$.

Prerequisites: sup vs max, the convex conjugate itself (the main detour), optimising pointwise inside an integral, and "a max over fewer options can only be smaller." Each gets a short detour.

Roadmap of the derivation: (1) write $f$ as a max over straight lines (conjugate duality) → (2) plug that into the $D_f$ integral → (3) let the best slope depend on $x$, making it a function $T(x)$ → (4) restrict $T$ to a family I can search over, which turns "=" into "≥" → (5) recognise both terms as expectations, which I can estimate from samples.

1. Intuition first

A convex (bowl-shaped) curve can be completely rebuilt from its tangent lines: draw enough of them and their upper envelope traces out the curve exactly. Straight lines are easy to work with, so I replace $f$ by "the best of all straight lines." When I plug that into the divergence, the awkward density ratio separates into two plain averages, one over real data and one over model data. Computing the divergence then becomes a search problem: find the function $T$ that scores real samples high and model samples low.

2. Real-world analogy

I cannot directly measure how different synthetic traffic is from real traffic, because I do not have formulas for either. But I can hire an auditor, $T$: a scoring function that looks at any single request and outputs a number.

• The auditor gets credit for giving real requests high scores: $\mathbb{E}_{P_x}[T(x)]$.
• The auditor pays a penalty for giving synthetic requests high scores: $\mathbb{E}{P\theta}[f^*(T(x))]$.

The auditor's net score only needs request samples from both sources, never a formula. A lazy auditor gets a low net score. The best possible auditor's net score equals the true divergence. So "how different are the two traffic sources?" becomes "how well can the best auditor tell them apart?"

That is precisely what a GAN discriminator is. The generator is the traffic generator trying to fool the auditor.

3. Visual: the conjugate as tangent lines

The core picture is how a convex $f$ relates to its conjugate $f^$. Here $f(u) = u \log u$ (the forward-KL $f$). Drag the slope $t$ and watch the tangent line slide along the curve. The vertical gap shown is $f^(t)$. Then switch on "show envelope".

Things to notice:

1. For each slope $t$, the dashed line $t \cdot u$ sits above the curve at some points. The biggest vertical gap between them (the coral segment) is $f^*(t)$. Shift the dashed line down by exactly that amount and I get the green line, which just touches the curve: a tangent.
2. Turn on the envelope. Each green line lies on or below the purple curve, and together their upper edge is the curve. That is the statement $f^{**} = f$: a convex function is the maximum of its tangent lines.

4. The formula, decoded

Detour 1: sup vs max

$\sup$ ("supremum") means "the smallest upper bound": it behaves like max, but also works when the maximum is approached but never reached. Example: the values $1 - \tfrac1n$ for $n = 1, 2, 3, \dots$ never reach 1, yet their sup is 1. For this course, I read sup as max; the distinction almost never matters for exam purposes.

Back to the main thread. Wherever I see $\sup$ below, I think "best possible."

Detour 2: The convex conjugate

The lectures define it as

$$f^*(t) = \sup_{u \in \operatorname{dom} f} \big( t u - f(u) \big)$$

Read aloud: "for slope $t$, $f^*(t)$ is the largest amount by which the straight line $t \cdot u$ exceeds the curve $f(u)$." That is exactly the coral gap in the widget.

Worked computation for $f(u) = u \log u$:

• I maximise $h(u) = t u - u \log u$ over $u > 0$.
• Set the derivative to zero: $h'(u) = t - (\log u + 1) = 0$ (product rule on $u \log u$ gives $\log u + 1$).
• So $\log u^* = t - 1$, i.e. $u^* = e^{t-1}$. That is the touch point shown in the widget.
• Substitute back: $f^*(t) = t e^{t-1} - e^{t-1}(t-1) = e^{t-1}$.

So the conjugate of the KL function is $f^(t) = e^{t-1}$. Check with the widget at $t = 1$: $u^ = 1$ and $f^*(1) = e^0 = 1$ ✓.

Two properties I keep on hand:

• (i) $f^*$ is also convex.
• (ii) Taking the conjugate twice gives back the original: $f^{**} = f$. Written out:

$$f(u) = \sup_{t \in \operatorname{dom} f^} \big( t u - f^(t) \big)$$

Read aloud: "$f$ at any point $u$ equals the highest tangent line at that point." That is the envelope picture. (This is where lower-semicontinuity from 3a is needed: it is the technical condition that makes $f^{**} = f$ hold exactly.)

Back to the main thread. Property (ii) is the key move. It replaces the awkward $f(\cdot)$ with "the best of a set of straight lines," and straight lines are linear in $u$. Linearity is what will let the density ratio separate into two clean expectations.

Detour 3: Optimising pointwise inside an integral

Suppose I want $\int \sup_t g(x, t)\, dx$. At each $x$, there is a best $t$, and it may differ from one $x$ to another. Collect those best choices into a function: $T(x) = $ "the best $t$ at point $x$." Then

$$\int \sup_t g(x, t)\, dx = \sup_{T} \int g\big(x, T(x)\big)\, dx$$

The sup on the right is over all functions $T$, i.e. a whole lookup table of choices, one per $x$.

Analogy: choosing the best price for each product separately is the same as choosing the best pricing table for the whole catalogue.

Back to the main thread. This is the step where "a number $t$" becomes "a function $T(x)$." The lectures flag it explicitly: "the solution for the inner problem depends on $x$ (a function of $x$)."

Detour 4: A restricted search can only do worse

If I search a smaller set of options, the best I find can only be as good or worse:

$$\max_{\text{small set}} \;\le\; \max_{\text{everything}}$$

Example: the best restaurant within 1 km is never better than the best restaurant in the whole city.

Back to the main thread. In practice I cannot search all functions $T$; I search a restricted family $\mathcal{T}$, such as neural networks of a given shape. That is why the final result is "≥", not "=".

The derivation, step by step

$$
\begin{aligned}
D_f(P_x \,|\, P_\theta)
&= \int P_\theta(x)\, f!\left(\frac{P_x(x)}{P_\theta(x)}\right) dx
&& \text{definition (3a)} \[4pt]
&= \int P_\theta(x)\, \sup_{t}\left( t\,\frac{P_x(x)}{P_\theta(x)} - f^(t) \right) dx
&& f = f^{} \text{ (Detour 2), with } u = \tfrac{P_x}{P_\theta} \[4pt]
&= \int \sup_{t}\Big( t\, P_x(x) - P_\theta(x)\, f^(t) \Big)\, dx
&& \text{move } P_\theta(x) \ge 0 \text{ inside the sup; the ratio cancels} \[4pt]
&= \sup_{T}\int \Big( T(x)\, P_x(x) - P_\theta(x)\, f^\big(T(x)\big) \Big)\, dx
&& \text{best } t \text{ per } x \text{ becomes a function } T(x) \text{ (Detour 3)} \[4pt]
&\ge \sup_{T \in \mathcal{T}}\Big( \int P_x(x)\, T(x)\, dx - \int P_\theta(x)\, f^\big(T(x)\big)\, dx \Big)
&& \text{restrict to a family } \mathcal{T} \text{ (Detour 4); split the integral} \[4pt]
&= \sup_{T \in \mathcal{T}}\Big( \mathbb{E}{x \sim P_x}[T(x)] - \mathbb{E}{x \sim P_\theta}\big[f^*(T(x))\big] \Big)
&& \text{each integral is an expectation (3a, Detour 3)}
\end{aligned}
$$

Look at line 3. Multiplying through by $P_\theta(x)$ cancelled the denominator of the ratio. That is the magic moment: no more division by an unknown density. From there, each density appears alone, multiplying something, which is exactly the form of an expectation.

In plain English: the f-divergence is at least as large as the best achievable "score real samples high, score model samples low" game, and it is exactly equal when the search over $T$ is rich enough.

Why this answers open question (i) from Section 2. Using the law of large numbers from Section 1, both terms become plain sample averages:

$$\widehat{D}f \approx \frac{1}{n}\sum{i=1}^{n} T(x_i) \;-\; \frac{1}{m}\sum_{j=1}^{m} f^*\big(T(g_\theta(z_j))\big), \qquad x_i \in D,\;\; z_j \sim \mathcal{N}(0, I)$$

No density value anywhere. I need only (a) real samples, which I have in $D$, (b) model samples, which I get by running $g_\theta$, and (c) a critic function $T$ to evaluate.

A bonus fact (standard in the f-GAN literature, not spelled out in the Week 1 slides): the bound is tight when $T^*(x) = f'!\left(\frac{P_x(x)}{P_\theta(x)}\right)$, the slope of $f$ at the density ratio. So the optimal critic is secretly computing the density ratio. That is why a trained discriminator "knows" how real each point looks.

5. Tiny worked example

Same coin world as 3a: $P_x = (0.5, 0.5)$, $P_\theta = (0.8, 0.2)$. Forward KL, so $f^*(t) = e^{t-1}$. From 3a, the true $D_{KL} \approx 0.223$.

For any critic $T = (T_1, T_2)$ (a score for each outcome), the bound is

$$\text{bound}(T) = \underbrace{0.5\,T_1 + 0.5\,T_2}{\mathbb{E}{P_x}[T]} \;-\; \underbrace{\big(0.8\,e^{T_1 - 1} + 0.2\,e^{T_2 - 1}\big)}{\mathbb{E}{P_\theta}[f^*(T)]}$$

Try three critics:

What to see:

• Every critic gives a lower bound on the true KL. A bad critic gives a loose bound; it can never overshoot.
• The critic that scores outcome 2 higher does better. Outcome 2 is the one the model under-produces ($u_2 = 2.5$), so it is where real data "looks most real."
• The optimal critic is $f'(u) = 1 + \ln u$, applied to the true ratios from 3a. That is the bonus fact in action. It recovers the divergence exactly.

In real training I would compute those two expectations as averages over samples instead of exact sums, and I would search over critics with gradient ascent instead of by hand.

Notes on the lecture slides

• The slides write $T: \mathcal{X} \to \operatorname{dom} f^$. That is important: the critic's outputs must lie where $f^$ is defined. For KL, $\operatorname{dom} f^* = \mathbb{R}$, so anything goes. For other $f$'s the domain is restricted, which is why Week 2 introduces the output activation $g_f$ that squashes the network's output into $\operatorname{dom} f^*$.
• The last line of the Week 1 notes is heavily garbled in my copy ("PA = T(p)p0(x) T(x)()…"). From context, it is the expectation form above with $\sup_{T \in \mathcal{T}}$, which matches the first line of the Week 2 notes ("$D_f \ge \max_T \mathbb{E}\,T(x) - \mathbb{E}\, f^*(T(x))$").

6. Connect back

This bound is the bridge from Week 1 to Week 2. Week 2 opens by making two substitutions:

1. The critic becomes a neural network: $T(x) \to T_w(x) = g_f(V_w(x))$, with weights $w$ and an $f$-specific output activation $g_f$.
2. Minimise over the generator: I want the smallest divergence, so I wrap a $\min_\theta$ around the bound:

$$\theta^, w^ = \arg\min_\theta \max_w \Big( \mathbb{E}{x \sim P_x}[T_w(x)] - \mathbb{E}{z \sim \mathcal{N}(0, I)}\big[f^*\big(T_w(g_\theta(z))\big)\big] \Big)$$

That min-max is Variational Divergence Minimisation (VDM). The critic $w$ maximises (gets the tightest estimate of the divergence); the generator $\theta$ minimises (shrinks the divergence). Pick the JS-like $f$, and it becomes exactly the GAN objective:

$$\mathbb{E}{x \sim P_x}[\log D_w(x)] + \mathbb{E}{z}\big[\log(1 - D_w(g_\theta(z)))\big]$$

With that, the four open questions from Section 2 all have Week 1 answers: (i) compute the divergence via the variational bound, using samples only; (ii) choose an $f$ from the f-divergence family; (iii) use neural networks for both $g_\theta$ and $T_w$; (iv) solve the min-max with alternating gradient steps, which Week 2 makes concrete.

Quick check (optional)

1. In the worked example, why can no critic $T$ ever give a bound above 0.223?
2. Which single algebra step in the derivation removed the unknown density ratio, and why does that matter?
3. In the sample-average formula $\widehat{D}_f$, where do the two sets of samples come from?

That wraps Week 1. Week 2 turns this bound into a working GAN: the VDM objective, the $g_f$ activations, and alternating training.