FLAIR external seminar: Universal coding under Gaussian noise, and the Wills functional

Sequential probability assignment is a classical prediction problem, wherein one aims to assign a large probability to a sequence of observations revealed one at a time. This problem is closely related to that of lossless data compression (also called universal coding) in information theory. We study this problem in the case where the base model is a subset of the standard Gaussian model, with mean constrained to a general convex domain. We show that the hardness of the problem can be expressed in terms of certain quantities from convex geometry, namely the intrinsic volumes of the constraint set. We then provide an alternative characterization of the optimal error in terms of metric complexity measures, which also holds in the general nonconvex case. We finally relate and contrast our findings with classical asymptotic results in information theory.