Technical Summary: Approximating f-Divergences with Rank Statistics

Problem Statement

Quantifying discrepancies between probability distributions is fundamental to statistics and machine learning, particularly for tasks like hypothesis testing and implicit generative modeling. A prominent class of such measures is f-divergences (e.g., Kullback-Leibler, Total Variation, Hellinger), which are defined via the density ratio $d\mu/d\nu$. However, reliably estimating f-divergences from samples is challenging, especially in moderate-to-high dimensions. Most existing approaches require explicit density-ratio estimation or rely on variational formulations (e.g., MINE, f-GAN) that involve delicate function-class choices and adversarial training, often suffering from instability and high sample complexity. While "sliced" methods (like Sliced Wasserstein) have successfully reduced high-dimensional problems to 1D comparisons, a robust, scalable, and optimization-free estimator for general f-divergences in high dimensions remains an open challenge.

Methodology

The paper introduces a rank-statistic approximation of f-divergences that avoids explicit density estimation by operating directly on the distribution of ranks.

1. One-Dimensional Rank-Statistic Construction

The core construction relies on the Probability Integral Transform (PIT). For a reference distribution $\nu$ and a target $\mu$, if $X \sim \mu$ and $\tilde{Y}_1, \dots, \tilde{Y}_K \sim \nu$ are independent, the rank statistic $A^{(K)}_{\mu|\nu}$ counts how many $\tilde{Y}_j$ are less than or equal to $X$.

• Rank Histogram: The probability mass function (PMF) of this rank statistic, denoted $Q^{(K)}_{\mu|\nu}$, forms a discrete "rank histogram" on $\{0, \dots, K\}$. If $\mu = \nu$, this histogram is uniform.
• Discrete f-Divergence: The approximation of the continuous f-divergence $D_{f,\nu}(\mu)$ is defined as the discrete f-divergence between the rank histogram $Q^{(K)}_{\mu|\nu}$ and the uniform distribution $U_K$:
  $$D^{(K)}_{f,\nu}(\mu) := D_f(Q^{(K)}_{\mu|\nu} \parallel U_K) = \frac{1}{K+1} \sum_{n=0}^K f\left((K+1)Q^{(K)}_{\mu|\nu}(n)\right)$$
  Here, $K$ is a resolution parameter. This estimator is optimization-free, relying only on sorting and counting operations.

2. Theoretical Properties

The authors establish several key theoretical properties:

• Monotonicity and Lower Bound: The estimator $D^{(K)}_{f,\nu}(\mu)$ is non-decreasing with respect to $K$ and serves as a strict lower bound for the true f-divergence: $D^{(K)}_{f,\nu}(\mu) \leq D^{(K+1)}_{f,\nu}(\mu) \leq D_{f,\nu}(\mu)$.
• Convergence Rates: Under mild regularity assumptions on the quantile-domain density ratio $r = \frac{d\mu}{d\nu} \circ Q_\nu$, the estimator converges to the true divergence as $K \to \infty$. The convergence rate depends on the smoothness of $r$:
  • $O(K^{-\alpha/2})$ if $r$ is Hölder continuous ($C^{0,\alpha}$).
  • $O(K^{-1})$ if $r$ is twice continuously differentiable ($C^2$) or if $r$ is Lipschitz and $f$ is $C^2$.
• Statistical Guarantees: The paper derives finite-sample deviation bounds showing the estimation error scales as $O(1/\sqrt{N} + 1/\sqrt{M})$ and proves asymptotic normality for the estimator.

3. High-Dimensional Extension: Sliced Rank-Statistic f-Divergence

To handle multivariate data in $\mathbb{R}^d$, the authors define the sliced rank-statistic f-divergence by averaging the univariate construction over random projections:
$$SD^{(K)}_{f,\nu}(\mu) := \int_{S^{d-1}} D^{(K)}_{f,\nu_s}(\mu_s) \, d\sigma(s)$$
where $\mu_s$ and $\nu_s$ are the pushforwards of $\mu$ and $\nu$ along a direction $s$ on the unit sphere, and $\sigma$ is the uniform measure on the sphere. This inherits the lower-bound and monotonicity properties of the 1D case.

Key Contributions

1. Optimization-Free Estimator: A new class of f-divergence estimators that replace density-ratio estimation with simple rank counting, avoiding the instabilities of variational/adversarial training.
2. Theoretical Analysis: Proof that the estimator is a monotone lower bound of the true divergence, with quantitative convergence rates based on the regularity of the density ratio. Finite-sample concentration bounds and asymptotic normality are also established.
3. Sliced Extension: A scalable high-dimensional extension via random projections, inheriting the theoretical guarantees of the univariate case.
4. Generative Transport Dynamics: A particle-based transport algorithm (Sliced Rank-Proximal Transport) that minimizes the rank-statistic divergence to move a particle cloud toward a target distribution, demonstrated on toy problems and image datasets.

Experimental Results

The paper validates the approach through several benchmarks:

• Dimensionality Scaling: In synthetic experiments comparing KL divergence estimation against neural baselines (MINE-style), the rank-statistic estimator tracks the ground truth closely and stabilizes faster with increasing sample size, particularly in dimensions $d=5$ and $d=10$, where neural baselines exhibit higher variance.
• Resolution Sensitivity: Experiments on 1D mismatch families (mean shifts, scale changes, multimodality, heavy tails) show that increasing $K$ systematically reduces the approximation gap. The convergence rate aligns with theoretical predictions (e.g., $O(K^{-1})$ for smooth scale changes, slower for heavy tails).
• Sliced Performance: In high-dimensional settings ($d \in \{2, 5, 10, 20, 50\}$), the sliced estimator provides stable approximations. While the ratio of the sliced estimate to the true divergence deviates slightly in high dimensions (especially for non-Gaussian or anisotropic cases), the method remains robust.
• Generative Modeling:
  • Toy Data: The rank-proximal transport dynamics successfully transport particles from a Gaussian prior to complex 2D targets (checkerboard, rings, spirals, mixtures).
  • CIFAR-10: The method is used as a learning objective for implicit generative models. Using a center-outward rank-proximal transport (CO-RPT) update, the method generates structured images matching low- and mid-level statistics of CIFAR-10.
  • MNIST Pretraining: Pretraining DCGAN generators with rank-statistic f-divergences (TV, KL, JS, Hellinger) improves the precision-recall trade-off compared to standard DCGAN training, with different f-generators favoring either precision or recall.

Significance and Claims

The paper claims that rank-statistic f-divergences offer a stable, data-efficient, and optimization-free alternative to neural density-ratio estimators and variational objectives. By relying on order statistics rather than density estimation, the method avoids the "curse of dimensionality" associated with density estimation while maintaining a clear variational structure.

The authors position this work as a generalization of previous rank-based TV-divergence approximations to arbitrary f-divergences, enabling the use of differentiable generators for learning tasks. They highlight that the method is particularly effective in scenarios with limited samples or where adversarial training is unstable.

Limitations Acknowledged:

• Projection Complexity: In high dimensions, if the discrepancy is concentrated in specific low-dimensional subspaces or complex dependencies, a finite number of random projections $L$ may miss informative directions.
• Discretization: The choice of finite $K$ introduces approximation error and may distort the objective's geometry, requiring careful tuning or adaptive schedules.
• Scalability: While avoiding density estimation, the sliced approach still incurs costs linear in the number of projections $L$ and the resolution $K$, which can be significant for very large datasets.

The authors suggest future work in developing variance-reduced projection schemes, adaptive selection of $K$ and $L$, and integrating these divergences into formal flow frameworks for generative modeling.