DeLTA seminar by Tim van Erven

Speaker

Tim van Erven, University of Amsterdam (https://www.timvanerven.nl/)

Title

Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability

Abstract

We consider the fundamental problem of estimating a discrete distribution on a domain of size K with high probability in Kullback-Leibler divergence. Quite surprisingly, the minimax rate was not known for this setting. We pin it down up to a doubly logarithmic factor. Our upper bound uses techniques from online learning to construct a novel estimator via online-to-batch conversion. For the lower bound, we show that it cannot be obtained using Fano's inequality or any other method based on the standard reduction to hypothesis testing. Instead we need to introduce a new reduction to what we call weak hypothesis testing.

This is joint work with Dirk van der Hoeven and Julia Olkhovskaia.
Paper link: https://arxiv.org/abs/2507.17316

________________________________________________
You can subscribe to the DeLTA Seminar mailing list by sending an empty email to delta-seminar-join@list.ku.dk.
Online calendar: https://calendar.google.com/calendar/embed?src=c_bm6u2c38ec3ti4lbfjd13c2aqg%40group.calendar.google.com&ctz=Europe%2FCopenhagen
DeLTA Lab page: https://sites.google.com/diku.edu/delta