Speaker: Shubanshu Shekar

Abstract: The problem of sequential prediction with log loss arises in several practical applications such as compression, portfolio optimization and density estimation. The measure of performance in the prediction game is the regret, that is, the suboptimality of the predicted distributions with respect to the best constant distribution selected from a reference (or hypothesis) class in hindsight. Prior work in this area has focused on two settings: the well-specified case, in which the data is generated from a distribution within the reference class, and the individual-sequence setting, in which there are no probabilistic assumptions on the data source. In both these settings, the minimax regret has been characterized exactly in terms of properties of the reference class. In this paper, the authors consider an intermediate setting, called the PAC setting, where the observations are assumed to be drawn from an arbitrary i.i.d. source. https://arxiv.org/abs/2102.00050