The Conditional Regret-Capacity Theorem for Batch Universal Prediction
This work addresses theoretical limits in universal prediction for scenarios with batch data, offering incremental extensions to existing information-theoretic frameworks.
The paper derives a conditional version of the regret-capacity theorem to provide lower bounds on minimal batch regret in universal prediction, applying it to binary memoryless sources and extending it to Rényi information measures to connect conditional Rényi divergence and Sibson's mutual information.
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ényi information measures, revealing a deep connection between the conditional Rényi divergence and the conditional Sibson's mutual information.