On the difficulty of unbiased alpha divergence minimization

Tomas Geffner, Justin Domke

Introduction

Variational Inference (VI) is a cornerstone of modern probabilistic machine learning, but it is not without its flaws. While standard VI relies on minimizing the Kullback-Leibler (KL) divergence, this approach is notorious for "variance underestimation"—it tends to fit the mode of a target distribution while ignoring its broader spread.

Alpha-divergences (where $\alpha > 0$) offer a compelling alternative by penalizing under-dispersion, theoretically leading to much better uncertainty estimates. However, optimizing these objectives with unbiased gradients has proven to be an absolute nightmare in high dimensions. This paper rigorously explains why these methods fail, proving that the Signal-to-Noise Ratio (SNR) of these gradient estimators decays exponentially with the number of dimensions, making convergence practically impossible for even moderately complex models.

Beyond KL Divergence: The Promise and Peril of Alpha

In standard VI (where $\alpha \to 0$), optimization is generally stable. But when researchers attempt to use alpha-divergences to capture broader uncertainty, the existing optimization methods fall into two problematic categories:

  1. Biased methods, which fail to find the true minimum in high dimensions.
  2. Unbiased methods, which are notoriously "temperamental" and scale poorly.

Historically, the failure of unbiased methods was vaguely attributed to "high variance." However, this paper looks deeper, demonstrating that raw variance is only half the story. The true culprit is the catastrophic collapse of the Signal-to-Noise Ratio (SNR).

The Root of the Problem: Signal-to-Noise Ratio (SNR)

The authors analyze the optimization problem through the lens of SNR, defined as the squared norm of the expected gradient (the true learning signal) divided by the expectation of the squared norm of the estimator (the noise).

To study this, they introduce a novel gradient estimator called the Double Reparameterization Estimator ($g_\alpha^{drep}$). By applying the reparameterization trick twice, this estimator is highly stable and deterministically zero at the optimum. The authors then provide exact theoretical SNR bounds for fully-factorized distributions and full-rank Gaussians.

Estimator variance, SNR, and true gradient norm. The middle panel clearly illustrates the catastrophic collapse of SNR for alpha > 0 compared to standard VI (alpha = 0).

One of the most critical insights from this analysis is that low variance is a trap. Optimization can fail completely even when the gradient estimator exhibits "low variance." If the true gradient (the signal) shrinks faster than the variance, the SNR still plummets. The "noise" effectively drowns out the "learning signal," leaving the optimizer wandering aimlessly.

The Exponential Curse of Dimensionality

The most striking theoretical finding is the "Exponential Curse." For any $\alpha \neq 0$, the SNR decreases exponentially with the dimensionality of the problem ($d$).

Why does this happen? In high dimensions, small discrepancies between the approximating distribution and the target in each individual dimension multiply together. Because each of these discrepancy terms is less than one, their product leads to a rapid, exponential collapse of the SNR. In stark contrast, for standard VI ($\alpha \to 0$), the SNR decreases at most linearly as $1/d$.

Empirical Evidence: When Optimization Flatlines

The paper validates its theoretical claims using a mix of synthetic and real-world datasets, ranging from low-dimensional benchmarks like the Iris dataset ($d=4$) to moderately sized ones like the Australian dataset ($d=14$) and larger synthetic models ($d \approx 40$ to $128$).

Optimization error over iterations for varying dimensions and alpha values. Notice the complete failure to converge at higher dimensions (d=128) for any alpha > 0, regardless of sample size N.

The empirical results are stark:

  • Massive Sample Complexity: For a 128-dimensional Gaussian with $\alpha=0.4$, obtaining a reliable gradient would require roughly 4 billion ($4 \times 10^9$) independent samples per step.
  • Rapid Optimization Failure: While optimization on the 4-dimensional Iris dataset converged quickly, the 14-dimensional Australian dataset required 10,000 samples per step just to maintain convergence. By the time dimensionality reached $d \approx 40$, optimization made zero progress regardless of the sample size.
  • Optimizer Invariance: This failure persists even when using sophisticated adaptive optimizers like Adam. Because Adam's effective step size approaches zero when the SNR is extremely low, the issue is intrinsic to the gradient estimator itself, not the choice of optimizer.

Conclusion and Future Directions

The paper paints an intentionally pessimistic picture of current unbiased approaches to alpha-divergence minimization. By proving that the failure stems from an exponential decay in SNR—even in "easy" cases like factorized and Gaussian families—the authors strongly suggest that a general-purpose, unbiased algorithm for high-dimensional models might be fundamentally unachievable using current gradient techniques.

Moving forward, the research community may need to pivot. The authors suggest exploring "biased" methods that behave more predictably in high dimensions, or inventing entirely new ways of estimating gradients that can bypass this SNR collapse. There is also a compelling hinted link between this failure and the "curse of dimensionality" observed in self-normalized importance sampling, opening new avenues for theoretical exploration.

Summary updated

Abstract

Several approximate inference algorithms have been proposed to minimize an alpha-divergence between an approximating distribution and a target distribution. Many of these algorithms introduce bias,...
BibTeX
@inproceedings{geffner2021difficulty,
  author = {Tomas Geffner and Justin Domke},
  title = {{On the difficulty of unbiased alpha divergence minimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=BeZBFqQSeq},
}
Figure