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 convex domain. We show that the complexity of the problem can be expressed in terms of certain quantities from convex geometry, namely the intrinsic volumes of the convex domain.
We then provide an alternative characterization of the optimal error in terms of complexity parameters of a metric nature, including covering numbers. This characterization extends to general nonconvex domains, and implies in the convex case an isomorphic characterization of the so-called Wills functional. We finally relate and contrast our findings with classical asymptotic results in information theory.
