Coding convex bodies under Gaussian noise, and the Wills functional

Abstract:
We consider the problem of sequential probability assignment in the Gaussian setting, where one aims to predict (or equivalently compress) a sequence of real-valued observations almost as well as the best Gaussian distribution with mean constrained to a general domain. First, in the case of a convex constraint set K, we express the hardness of the prediction problem (the minimax regret) in terms of the intrinsic volumes of K. We then establish a comparison inequality for the minimax regret in the general nonconvex case, which underlines the metric nature of this quantity and generalizes the Slepian-Sudakov-Fernique comparison principle for the Gaussian width. Motivated by this inequality, we present a sharp (up to universal constants) characterization of the considered functional for a general nonconvex set, in terms of metric complexity measures. This implies isomorphic estimates for the log-Laplace transform of the intrinsic volume sequence of a convex body. We finally relate and contrast our findings with classical asymptotic results in information theory.

Bio:
Jaouad Mourtada is an Assistant Professor in the Department of Statistics at ENSAE/CREST. Prior to that, he was a postdoctoral researcher at the Laboratory for Computational and Statistical Learning at the University of Genoa. He recieved his Ph.D. in the Center for Applied Mathematics (CMAP) at École Polytechnique. His research interests are at the intersection of statistics and learning theory, specifically in understanding the complexity of prediction and estimation problems.