Misc

Fisher divergence
- Insight from Ermon: Kind of a derivative of the KL divergence, once it’s been convolved with Gaussian noise
Kolmogorov complexity of a sequence is length of shortest possible description (program)
- It’s the theoretical minimum description length (MDL)
- Kolmogorov random: when K(s) ≥ len(s)
Minimum description length (MDL): TODO

KL divergence

KL(p||q): p is target/truth. q is our “channel.” How far is q from p?
- KL = cross-entropy - entropy
As objective function (minimized). qθ is always the distribution being changed.
- KL(p||qθ)
  - mean-seeking, inclusive (more principled because approximates the full distribution)
  - requires normalization wrt pp (i.e., often not computationally convenient)
- KL(qθ||p)
  - mode-seeking, exclusive
  - no normalization wrt pp (i.e., computationally convenient)
- Mnemonic: "When the truth comes first, you get the whole truth" (h/t Philip Resnik). Here "whole truth" corresponds to the inclusiveness of KL(p||q)KL(p||q).
- Illustration

Estimators over just samples $x \sim q(x)$

Estimator	Bias	Variance	Comments
$k_1 = \log\frac{p(x)}{q(x)} = -\log r$	no bias	high variance	Naive
$k_2 = \frac{1}{2}(\log\frac{p(x)}{q(x)})^2 = \frac{1}{2}(\log r)^2$	biased	low variance	$\ge 0$
$k_3 = (r-1) - \log r$	no bias	low variance	$\ge 0$

Idea for $k_3$: add a control variate, something that “cancels out” the variance of $k_1$, i.e. something that both (1) we know has no bias / 0 expectation, and (2) is negatively correlated with $k_1$.