Minimax Estimation of Functionals of Discrete Distributions

Jiantao Jiao, Kartik Venkat, Yanjun Han, Tsachy Weissman

Research output: Contribution to journalArticlepeer-review


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) = ∑i=1S - pi ln pi and 2) Fα(P) = ∑i=1S piα, α > 0. We obtain the minimax 2 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 nsamples, 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.

Original languageEnglish (US)
Article number7060676
Pages (from-to)2835-2885
Number of pages51
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - May 1 2015


  • Chow-Liu algorithm
  • Mean squared error
  • Rényi entropy
  • approximation theory
  • entropy estimation
  • high dimensional statistics
  • maximum likelihood estimator
  • minimax lower bound
  • minimax-optimality
  • nonsmooth functional estimation
  • polynomial approximation

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Minimax Estimation of Functionals of Discrete Distributions'. Together they form a unique fingerprint.

Cite this