Minimax Estimation of the $L_1$ Distance

Abstract

We consider the problem of estimating the $L_1$ distance between two discrete probability measures $P$ and $Q$ from empirical data in a nonasymptotic and large alphabet setting. When $Q$ is known and one obtains $n$ samples from $P$, we show that for every $Q$, the minimax rate-optimal estimator with $n$ samples achieves performance comparable to that of the maximum likelihood estimator (MLE) with $n\ln n$ samples. When both $P$ and $Q$ are unknown, we construct minimax rate-optimal estimators whose worst case performance is essentially that of the known $Q$ case with $Q$ being uniform, implying that $Q$ being uniform is essentially the most difficult case. The \emph{effective sample size enlargement} phenomenon, identified in Jiao \emph{et al.} (2015), holds both in the known $Q$ case for every $Q$ and the $Q$ unknown case. However, the construction of optimal estimators for $\Vert P-Q{\Vert }_1$ requires new techniques and insights beyond the approximation-based method of functional estimation in Jiao \emph{et al.} (2015).

to appear on IEEE Transactions on Information Theory

References in corpus (1)

• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional

Cited by in corpus (6)

• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Measuring Quantum Entropy
• On Estimation of $L_r$-Norms in Gaussian White Noise Models
• Minimax Rate-Optimal Estimation of Divergences between Discrete Distributions
• Optimal Estimation of Simultaneous Signals Using Absolute Inner Product with Applications to Integrative Genomics