Minimax Estimation of Discrete Distributions Under $\ell _{1}$ Loss

By Yanjun Han, Jiantao Jiao, Tsachy Weissman. 2014

48 citations recorded by the source corpus.

We consider the problem of discrete distribution estimation under l1 loss. We provide tight upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the support size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H/ln n, while the asymptotic minimax risk is H/ ln n. Moreover, we show that a hard-thresholding estimator oblivious to the unknown upper bound H, is essentially minimax. However, if we constrain the estimates to lie in the simplex of probability distributions, then the asymptotic minimax risk is again 2H/ ln n. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (I1 divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

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

Learning discrete distributions: user vs item-level privacy (2020, background): “Well known results on non-private discrete distribution estimation (see [Kamath et al., 2015, Han et al., 2015]) characterize the min-max user complexity as S∗m,α = Θ ( k mα2 ) .”
Minimax Rates of Estimating Approximate Differential Privacy (2019, methodology): “ estimated is not smooth, and use functional approximation to estimate a smoothed version of the property. This has been widely successful in support recovery [WY19], density estimation with ‘ 1 loss [HJW15], and estimating Renyi entropy [AOST17]. more recently, this technique has been applied to es”
Formal Limitations on the Measurement of Mutual Information (2018, background): “Past work on analyzing minimax bounds likewise assume small support (Jiao et al., 2015; Han et al., 2015; Kandasamy et al., 2015).”
Estimating Mutual Information for Discrete-Continuous Mixtures (2017, background): “Novel entropy estimators with sub-linear sample complexity have been proposed [48, 53, 19, 21, 20, 23].”