Timezone: »

Dimension-free empirical entropy estimation
Doron Cohen · Aryeh Kontorovich · Aaron Koolyk · Geoffrey Wolfer

Thu Dec 09 04:30 PM -- 06:00 PM (PST) @

We seek an entropy estimator for discrete distributions with fully empirical accuracy bounds. As stated, this goal is infeasible without some prior assumptions on the distribution. We discover that a certain information moment assumption renders the problem feasible. We argue that the moment assumption is natural and, in some sense, {\em minimalistic} --- weaker than finite support or tail decay conditions. Under the moment assumption, we provide the first finite-sample entropy estimates for infinite alphabets, nearly recovering the known minimax rates. Moreover, we demonstrate that our empirical bounds are significantly sharper than the state-of-the-art bounds, for various natural distributions and non-trivial sample regimes. Along the way, we give a dimension-free analogue of the Cover-Thomas result on entropy continuity (with respect to total variation distance) for finite alphabets, which may be of independent interest.

Author Information

Doron Cohen (Ben-Gurion University of the Negev)
Aryeh Kontorovich (Ben Gurion University)
Aaron Koolyk (Hebrew University of Jerusalem, Israel)
Geoffrey Wolfer (Tokyo University of Agriculture and Technology)

More from the Same Authors