Abstract-We consider the problem of estimating the LI distance between two discrete probability measures P and Q from empirical data in a nonasymptotic and large alphabet setting. We construct minimax rate-optimal estimators for LI (P, Q) when Q is either known or unknown, and show that the performance of the optimal estimators with n sampies is essentially that of the Maximum Likelihood Estimators (MLE) with n In n sam pies. Hence, we demonstrate that the ejjective sampie size enlargement phenomenon, discovered and discussed in Jiao et al. (2015), holds for this problem as weIl. However, the construction of optimal estimators for LI (P, Q) requires new techniques and insights outside the scope of the Approximation methodology of functional estimation in . I. INTRODUCTlON Statistical functionals are usually used to quantify the fundamental limits of data processing tasks such as data compression (e.g. Shannon entropy [2] ), data transmission (e.g. mutual information [2] ), estimation and testing (e.g. KullbackLeibIer divergence), etc. They measure the difficuIties of the corresponding data processing tasks and shed light on how much improvement one may expect beyond the current state-of-the-art approaches. In this sense, it is of great value to obtain accurate estimates of these functionals in various problems. In this paper, we consider estimating the LI distance be- ql, q2,···, qs), which is defined as: s Throughout we use the squared error loss, i.e., the risk function for an estimator L is defined as The maximum risk of an estimator L, and the minimax risk in estimating LI (P, Q) are defined respectively, where P, Q are given collections of probability measures P and Q, respectively, and the infimum is taken over all possible estimators L. The LI distance is closely related to the Bayes error, i.e., the fundamental limit, in classification problems. Specifically, for a two-class cIassification problem, if the prior probabilities for each cIass are equal, then the minimum probability of error achieved using the optimal cIassifier is given by where Y E {O, I} indicates the class, and PXIY are the classconditional distributions. Hence, the problem of estimating L * in this classification problem is reduced to estimating the LI distance between the two cIass-conditional distributions PX!y=I, PX!y=o from the empirical data. In the statistical learning theory literature, most work on Bayes classification error estimation deals with the case that PX!y=I and PXIY=o are continuous distributions, and it turns out that even in an asymptotic setting it is very difficult to estimate this quantity in this general continuous case. Indeed, we know from [3, Section 8.5] the negative result that for every sampie size n, any estimate of the Bayes error Ln, and any E > 0, there exist some This negative result shows that one needs to look at special cIasses of the class-conditional distributions in order to obtain consistent estimates. In the discrete setting, the seminal work of Valiant and Valiant [4] deserves special mention. They constructed an estimator for LI (P, Q) and showed that when SllnS:S n:S S, it achieves LI error vSI(nlnn), and it is the best possible rate for the constant LI error regime. It is quite simple to argue, as we do in this paper, that the simplest estimator for LI (P, Q), namely plugging in the empirical distribution Pn , Qn and obtaining LI(Pn , Qn) achieves LI error rate V SI n for n 2: S. In this sense, the optimal estimator seems to enlarge the sampIe size n to n In n in the error rate expression. We emphasize that the observed effective sampie size enlargement here is another manifestation of the recently discovered phenomenon in functional estimation of high dimensional objects. There has been arecent wave of study on functional estimation of high dimensional parameters
. Minimax rates for this problem are currently unknown, and it is presently unclear to us under what conditions recent results on estimation of L 1 distances between discrete distributions REF might imply an improved rate as fast as (n log n)
Minimax estimation of the L1 distance
2016 IEEE International Symposium on Information Theory (ISIT)
2016 IEEE International Symposium on Information Theory (ISIT)
Computer Science