Source-linked AI summary
Estimating divergence functionals and the likelihood ratio by convex risk minimization
XuanLong Nguyen, Martin J. Wainwright, Michael I. Jordan
TL;DR
The paper studies estimation of divergence functionals and likelihood ratios for two unknown distributions. It uses a variational characterization of f-divergences to construct convex M-estimators, analyzes their consistency and rates, and develops efficient kernel implementations. Under smoothness conditions, the likelihood-ratio and KL-divergence estimators achieve optimal minimax rates in the stated regimes.
Problem
Estimating divergences and likelihood ratios between two multivariate distributions from samples is a central problem, including KL divergence, mutual information, and entropy estimation.
Method
The method uses a non-asymptotic variational characterization of f-divergences to formulate convex empirical-risk M-estimators, including efficient RKHS implementations.
Results
For smooth function classes with α > d/2, the likelihood-ratio and KL-divergence estimators achieve optimal minimax rates n^-α/(d+2α) and n^-1/2, respectively.
Takeaways & Limitations
The framework provides computationally efficient estimators for likelihood ratios and f-divergence functionals, with simulations illustrating their convergence behavior and practical viability.
Takeaways & Limitations
The RKHS model for log G is investigated empirically because the main convergence theorem does not directly apply when its required condition fails.
Abstract
from arXiv · showhide
We develop and analyze $M$-estimation methods for divergence functionals and the likelihood ratios of two probability distributions. Our method is based on a non-asymptotic variational characterization of $f$-divergences, which allows the problem of estimating divergences to be tackled via convex empirical risk optimization. The resulting estimators are simple to implement, requiring only the solution of standard convex programs. We present an analysis of consistency and convergence for these estimators. Given conditions only on the ratios of densities, we show that our estimators can achieve optimal minimax rates for the likelihood ratio and the divergence functionals in certain regimes. We derive an efficient optimization algorithm for computing our estimates, and illustrate their convergence behavior and practical viability by simulations.
1 Introduction
The paper addresses divergence and likelihood-ratio estimation from samples using M-estimators derived from a variational characterization of f-divergences. Under smoothness conditions, the estimators achieve optimal minimax rates for likelihood-ratio and KL-divergence estimation.
- Motivation: Divergence estimation asks how to estimate the divergence between two multivariate distributions from samples drawn from each.The problem includes KL divergence, mutual information, and Shannon entropy estimation.
- Contributions: The proposed M-estimators estimate both f-divergence functionals and likelihood density ratios, with primary emphasis on KL divergence.The methodology applies more broadly to Ali-Silvey distances, also called f-divergences.
- Method: A non-asymptotic variational characterization converts f-divergence estimation into a Bayes decision problem and convex empirical risk optimization.The same reformulation yields estimators for both the divergence and the likelihood ratio.
- Theory: For smooth function classes with smoothness α > d/2, likelihood-ratio and KL-divergence estimates achieve minimax rates n^-α/(d+2α) and n^-1/2, respectively.These rates are stated as optimal in the minimax sense.
- Computation: The paper provides an efficient RKHS implementation that reduces estimation to a convex program involving the kernel Gram matrix.The method is illustrated empirically on several KL-divergence estimation instances.
- Scope: The paper analyzes consistency and convergence rates, develops computational procedures, and demonstrates estimator behavior through simulations.The paper is organized around variational characterization, statistical analysis, kernel algorithms, and simulation results.
2 M-estimators for KL divergence and the density ratio
This section constructs M-estimators for KL divergence and density ratios by specializing an f-divergence variational representation to empirical distributions. The resulting procedures optimize over function classes, with convex and penalized formulations supporting practical computation.
- Variational characterization: f-divergences form a broad family generated by convex lower semi-continuous functions, including KL, total variation, and Hellinger distances.Different choices of φ produce different divergences.
- Variational characterization: The variational representation lower-bounds the divergence over a function class, with equality when the class contains a suitable subgradient of φ at the density ratio.The equality condition is expressed through the subdifferential ∂φ(q0/p0).
- KL specialization: For KL divergence, the variational supremum is attained at the true density ratio g0 = p0/q0.The KL representation follows from the conjugate dual of its generating convex function.
- Empirical estimators: With unknown P and Q, the estimators replace them by empirical distributions formed from independent samples and optimize over a prespecified function class G.The empirical distributions are constructed from samples drawn independently from P and Q.
- Estimator design: Estimator E1 constrains the complexity of G through a fixed bound M*, while estimator E2 uses an explicit penalty I(g) with regularization parameter λn > 0.Both approaches require controlling approximation and estimation through the permitted function class.
- Computation: For RKHS function classes, the optimization problems can be reduced to finite-dimensional convex programs and solved efficiently by standard methods.The resulting estimates include both the KL divergence and, when the supremum is attained, the density ratio.
3 Consistency and convergence rate analysis
The paper establishes consistency for divergence and likelihood-ratio estimators under entropy and envelope conditions, then derives convergence rates, including optimal rates for Sobolev classes in the stated regime.
- Consistency: The analysis measures divergence error directly and likelihood-ratio error using generalized Hellinger distance.
- Consistency: Under the theorem’s assumptions, both the KL-divergence estimate and likelihood-ratio estimate are almost surely consistent.
- Consistency: Hellinger consistency can be obtained under milder entropy requirements without requiring boundedness of every function in G from below.
- Consistency: The analysis separates approximation error from estimation error and assumes the true likelihood ratio belongs to G, making approximation error zero.
- Convergence rates: hQ(g0, bgn) = OP(n^-1/(γ̄G+2)) under the stated entropy conditions, while KL-divergence error is OP(n^-1/2) under an alternative condition set.
- Convergence rates: For Sobolev classes, the likelihood-ratio Hellinger rate matches the minimax rate, and the n^-1/2 divergence rate is also optimal.
- Convergence rates: Estimator E2 also achieves the minimax rate for density-ratio estimation in Hellinger distance in the stated Sobolev setting.
4 Algorithmic implementation and simulation examples
The practical implementation uses RKHS-based versions of estimator E2, converts them to finite-dimensional convex programs, and evaluates their convergence through simulations across distribution families and dimensions.
- Algorithmic implementation: For kernel-based G, dual conversion reduces computation to an n-dimensional convex program involving the RKHS Gram matrix.
- Kernel-based estimators: Estimator E2 is developed with either G or log G assigned an RKHS structure, using a Gaussian kernel in both cases.
- Kernel-based estimators: The Gaussian RKHS is chosen because it is sufficiently rich while remaining amenable to efficient optimization.
- Simulation design: The simulations vary sample sizes from 100 to 10^4 or more across Gaussian, beta, Gaussian-mixture, and multivariate Gaussian distributions.
- Simulation results: M2 generally has the best convergence rates across the reported one-, two-, and three-dimensional examples, while M1 can fail to converge in the last example.
- Simulation results: WKV is sensitive to partition size and performs noticeably worse in the three-dimensional examples, whereas increased dimension has only a mild implementation-complexity effect on the proposed method.
5 Some extensions
The extensions apply the variational principle to alternative f-divergences, likelihood-ratio estimation, and divergence functionals, with consistency and rate results under corresponding function-class conditions.
- Likelihood-ratio estimation: Alternative convex functions φ generate a family of likelihood-ratio estimators through the inverse of φ′ when φ is differentiable and strictly convex.The estimated quantity bfn targets f0 = ∂φ(q0/p0), while bDφ targets the divergence.
- Likelihood-ratio estimation: Non-differentiable φ cannot be inverted directly, but can still produce estimators of other objects, including thresholded likelihood ratios for variational distance.For the piecewise-linear choice, ∂φ(u) = sign(u −1), so bfn estimates the thresholded likelihood ratio.
- Consistency and rates: The general analysis defines a Bregman-type distance dφ and establishes consistency of bfn in that distance under empirical-process conditions.For KL divergence, the relevant distance can be replaced by a proper metric such as L2 or Hellinger to obtain standard convergence results.
- Consistency and rates: The χ-square divergence yields an L2(Q)-based estimator that is consistent at rate n^-2/(γ+2), under weaker conditions than the Hellinger-based analysis.The weaker conditions follow because the L2(Q) metric is dominated by the Hellinger metric.
- Divergence-functional estimation: Divergence estimation can use an estimated likelihood ratio inside an integral under Q, and a Taylor expansion separates empirical error from approximation error.When α ≥ d/4, the Taylor remainder is below O(n^-1/2), so the optimal divergence rate depends on estimating the remaining integral.
6 Conclusions
The paper develops M-estimators for likelihood ratios and f-divergence functionals using variational characterizations, with efficient optimization and analyzed statistical behavior.
- Contributions: M-estimation methods target both likelihood ratios and f-divergence functionals of two unknown multivariate distributions.The framework extends beyond KL divergence to general integral functionals of likelihood ratios.
- Computational implications: The estimators admit efficient optimization algorithms in high-dimensional function spaces.The conclusion describes the methods as computationally amenable to efficient algorithms.
A Proof of Lemma 2
The passage presents successive steps in a proof, beginning with a condition for x > 0 and continuing through an estimation-procedure statement.
- The proof first introduces a statement conditioned on x > 0.
- A logarithmic expression appears as an intermediate part of the argument.
- The proof then invokes the estimation procedure to state a resulting claim.
B Proof of Lemma 3
The proof of Lemma 3 begins from the estimator’s defining inequality and controls the resulting convex-functional comparison.
- Proof argument: The estimator definition supplies the starting inequality for the proof.The proof then compares both sides as convex functionals of g.
- Proof argument: Convexity implies that midpoint interpolation preserves the comparison needed for the bound.The argument applies F((u + v)/2) ≤ F(v) when F(u) ≤ F(v).
- Proof argument: Lemma 2 provides the final inequality in the proof.The proof identifies the last step as a direct application of Lemma 2.
C Proof of Lemma 4
The lemma connects the estimator’s divergence-related quantity to Hellinger distance and uses convexity to control the relevant functional.
- The distance quantity is related to the squared Hellinger distance between g0 and g.
- Convexity and Jensen’s inequality provide the key comparison used in the proof.
- The proof invokes a standard generalized-Hellinger-distance inequality for the final bound.
D Proof of Theorem 2
The theorem proof controls empirical-process fluctuations using Bernstein and Hellinger metrics, peeling, and entropy bounds, then establishes a rate for the likelihood-ratio estimator.
- The proof equips the relevant function class with Bernstein distance and relates it to Hellinger distance.
- Bracketing entropy under Bernstein distance is related to bracketing entropy under Hellinger distance for the transformed class.
- Peeling decomposes the function class into Hellinger layers, applies union bounds, and controls empirical-process suprema within each layer.
- n^-1/(γ̄_G+2) bounds h_Q(g0, ĝ_n) in P-probability when p0/q0 is bounded above.
- The minimax lower-bound argument reduces to nonparametric density estimation and uses a hypercube construction with Assouad’s lemma.
F Some calculations for Theorem 4
These calculations specialize the divergence analysis through the conjugate of φ(u)=1/u and transform the function class into positive square-root functions.
- The conjugate dual of φ(u)=1/u is finite only on the negative half-line and equals −v when v<0.
- Restricting F to negative functions permits the transformation g:=√−F, producing a class G of positive functions.
- The true and estimated functions are transformed similarly, with g0:=√−f0 and g:=√−bfn.
- For this choice of φ, the divergence notation is rewritten in terms of the transformed functions.
G Results from empirical process theory
The appendix states empirical-process results under envelope, entropy, and Bernstein-distance conditions; these results provide bounds used in the convergence analysis.
- The appendix presents two standard empirical-process results adapted from van de Geer’s theorems.
- One result assumes an integrable envelope function and entropy control for the function class.
- Another result assumes bounded Bernstein distance and conditions involving constants C and C1.
- Under these conditions, the empirical process is bounded.