Coding convex bodies under Gaussian noise, and the Wills functional

Thursday 8 December 2022, 10:15 à 11:15

Salle des séminaires, M.0.1

Jaouad Mourtada

CREST, Paris

We consider the problem of sequential probability assignment in the Gaussian setting, where the goal is to predict (or equivalently compress) a sequence of real-valued observations almost as well as the best Gaussian distribution within some convex constraint set. This can be thought of as an information-theoretic analogue of fixed-design regression.
 
We show that the optimal error is exactly given by a certain functional of the constraint set from convex geometry called the Wills functional. As a consequence, we express the optimal error in terms of basic geometric quantities associated to the convex body, namely its intrinsic volumes. We also present matching (up to universal constants) upper and lower bounds on the optimal error in terms of suitable fixed points associated to geometric complexity measures. Finally, we show some monotonicity properties with respect to noise and sample size, as a consequence of general comparison and log-concavity inequalities for the optimal error.