Estimation of mutual information from observed samples is a basic primitive in machine
learning, useful in several learning tasks including correlation mining, information …

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 …

Hypergraph partitioning is an important problem in machine learning, computer vision and
network analytics. A widely used method for hypergraph partitioning relies on minimizing a …

Consider the problem of estimating the Shannon entropy of a distribution over elements from
independent samples. We show that the minimax mean-square error is within the universal …

There is a folkloric belief that a depth-$\Theta (m) $ quantum circuit is needed to estimate the
trace of the product of $ m $ density matrices (ie, a multivariate trace), a subroutine crucial to …

The problem of estimating the Kullback-Leibler divergence D (P∥ Q) between two unknown
distributions P and Q is studied, under the assumption that the alphabet size k of the …

Mobile CrowdSensing (MCS) has emerged as a novel paradigm for performing large-scale
sensing tasks. Many incentive mechanisms have been proposed to encourage user …

We give a brief survey of the literature on the empirical estimation of entropy, differential
entropy, relative entropy, mutual information and related information measures. While those …

It was shown recently that estimating the Shannon entropy H (p) of a discrete k-symbol
distribution p requires Θ (k/log k) samples, a number that grows near-linearly in the support …

We study concentration inequalities for the Kullback–Leibler (KL) divergence between the
empirical distribution and the true distribution. Applying a recursion technique, we improve …