The Conditional Regret-Capacity Theorem for Batch Universal Prediction

--We derive a conditional version of the classical regret-capacity theorem. This result can be used in universal prediction to find lower bounds on the minimal batch regret, which is a recently introduced generalization of the average regret, when batches of training data are available to the predictor . As an example, we apply this result to the class of binary memoryless sources. Finally, we generalize the theorem to R enyi information measures, revealing a deep connection between the conditional R enyi divergence and the conditional Sibson's mutual information. Prediction of the continuation of a sequence from its own past is one of the central problems of statistics, science, and engineering.