Minimax Estimation of Functionals of Discrete Distributions

By Jiantao Jiao, Kartik Venkat, Yanjun Han, Tsachy Weissman. 2014

269 citations recorded by the source corpus.

We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size S is unknown and may be comparable with or even much larger than the number of observations n. We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy H(P) = ΣSi=1 -pi ln pi and 2) Fα(P) = ΣSi=1 pαi, α > 0. We obtain the minimax L2 rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity n × S/ln S for entropy estimation. We also demonstrate that the sample complexity for estimating Fα(P), 0 <; α <; 1, is n×S1/α/ln S, which can be achieved by our estimator but not the MLE. For 1 <; α <; 3/2, we show the minimax L2 rate for estimating Fα(P) is (n ln n)-2(α-1) for infinite support size, while the maximum L2 rate for the MLE is n-2(α-1). For all the above cases, the behavior of the minimax rate-optimal estimators with n samples is essentially that of the MLE (plug-in rule) with n ln n samples, which we term “effective sample size enlargement.” We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information estimator yielded by our framework leads to significant performance boosts over the Chow-Liu algorithm in learning graphical models. The wide use of information measure estimation suggests that the insights and estimators obtained in this paper could be broadly applicable.

How researchers see this paper

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

Citations in the corpus

Formal Limitations on the Measurement of Mutual Information (2018, background): “Hence we show that without making strong assumptions on the population distribution, such as the small support assumption in Valiant and Valiant (2011) and minimax bounds (Jiao et al., 2015), it is generally impossible to guarantee an accurate estimate of mutual information.”
Instance optimal learning of discrete distributions (2016, background): “(See also [25] for another perspective on emulating n logn samples using only n.”
A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions (2017, background): “Moreover, (Paninski, 2003) showed that C(H(p),∆k, ε) is sublinear in k, (Valiant & Valiant, 2011a) showed that the optimal dependence on k is k/ log k and (Wu & Yang, 2016; Jiao et al., 2015) obtained the optimal dependence on both k, and ε, and showed that C(H(p),∆k, ε) = Θ ( k log k · 1 ε ) .”
Minimax Rate-optimal Estimation of KL Divergence between Discrete Distributions (2016, methodology): “, the scaled 1 norm 1 n ∑n i=1 |θi| in the Gaussian model [11], the Shannon entropy ∑S i=1 −pi ln pi [1], [12]–[14], the mutual information [1], the power sum function ∑S i=1 p α i [1], the Rényi entropy ln ∑S i=1 p α i 1−α [15] and the L1 distance ∑S i=1 |pi − qi| [16] in Multinomial and Poisson mo”
Chebyshev polynomials, moment matching, and optimal estimation of the unseen (2015, methodology): “The technique of polynomial approximation has been previously used for estimating non-smooth functions (Lq-norms) in Gaussian models [19, 22, 4] and more recently for estimating information quantities (entropy and power sums) on large discrete alphabets [43, 20].”
Demystifying fixed k-nearest neighbor information estimators (2016, background): “A canonical question in all these applications is to estimate the information theoretic quantities from samples, typically supposed to be drawn i.i.d. from an unknown distribution.”
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].”
Estimating Renyi Entropy of Discrete Distributions (2014, methodology): “For completeness, we also include a proof for the case α < 1, which is slightly different from the one in [16].”
On the Robustness of Information-Theoretic Privacy Measures and Mechanisms (2018, background): “Finally, we remark that the estimation of information metrics from a limited number of samples has been studied recently by, for example, Jiao et al. [28] and Wu and Yang [29].”
Estimating the Unseen (2013, result): “Similar results were also independently obtained more recently [23, 48].”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, methodology): “[10] showed that the minimax rate in estimating Fα(P ), 1 < α < 3/2, is (n lnn) −2(α−1) as long as S & n lnn, which is achieved using the general methodology developed therein for constructing minimax rate-optimal estimators for nonsmooth functionals.”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “DP Le Cam’s method Le Cam’s method (Lemma 1 of Yu (1997)) is widely used to prove lower bounds for composite hypothesis testings such as uniformity testing (Paninski, 2008), density estimation (Yu, 1997; Ray and Schmidt-Hieber, 2018), and estimating functionals of distributions (Jiao et al., 2015; W”
Minimax Estimation of the $L_1$ Distance (2017, methodology): “The general approximation-based method in [7] is as follows.”