Combining Batch and Online Prediction
Yaniv Fogel, Meir Feder · 2024
We study a variation of the stochastic, realizable batch learning problem where there is a training set of$N$symbols and the prediction is then tested over$L$symbols. We prove an equivalent of the Redundancy-Capacity Theorem, find the leading term of the regret for the multinomial case and also discuss, informally, a general parametric hypothesis class. We implement a variant of the Arimoto-Blahut algorithm to calculate the optimal minimax redundancy and show, for the binary case, the resulting regret and the approximated capacity-achieving prior.