Minimax Estimation of the $L_1$ Distance

By Jiantao Jiao, Yanjun Han, Tsachy Weissman. 2017

57 citations recorded by the source corpus.

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 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 effective sample size enlargement phenomenon, identified by Jiao et al. , holds both in the known $Q$ case for every $Q$ and the $Q$ unknown case. However, the construction of optimal estimators for $\|P-Q\|_{1}$ requires new techniques and insights beyond the approximation-based method of functional estimation by Jiao et al.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Minimax Rates of Estimating Approximate Differential Privacy (2019, methodology): “i entropy [AOST17]. more recently, this technique has been applied to estimate certain divergences between two unknown distributions, for Kullback-Leibler divergence [HJW16], total variation distance [JHW18], and identity testing [DKW18]. With carefully designed estimators, these approximation-based”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, background): “This imprecise null testing problem has been studied for a variety of metric choices in Valiant and Valiant (2011), Acharya, Daskalakis and Kamath (2015), Jiao, Han and Weissman (2017) and Daskalakis, Kamath and Wright (2018).”