Minimax Rate-Optimal Estimation of Divergences between Discrete Distributions

Abstract

We study the minimax estimation of $\alpha$-divergences between discrete distributions for integer $\alpha \ge 1$, which include the Kullback--Leibler divergence and the ${\chi }^2$-divergences as special examples. Dropping the usual theoretical tricks to acquire independence, we construct the first minimax rate-optimal estimator which does not require any Poissonization, sample splitting, or explicit construction of approximating polynomials. The estimator uses a hybrid approach which solves a problem-independent linear program based on moment matching in the non-smooth regime, and applies a problem-dependent bias-corrected plug-in estimator in the smooth regime, with a soft decision boundary between these regimes.

This (v5) is a significantly revised version of (v2), and fixed some typos in (v4)

References in corpus (3)

• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional
• Minimax Estimation of the $L_1$ Distance
• On Estimation of $L_r$-Norms in Gaussian White Noise Models

Cited by in corpus (6)

• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• On Estimation of $L_r$-Norms in Gaussian White Noise Models
• F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits
• Quantum query complexity of entropy estimation
• Performance Guarantees for Quantum Neural Estimation of Entropies