Things Bayes can't do
This reveals a fundamental limitation of Bayesian methods in universal prediction for arbitrary predictor sets, which is significant for theoretical machine learning and statistics.
The paper tackles the problem of constructing a single predictor that performs as well as the best in an arbitrary set C for forecasting conditional probabilities, showing that such predictors exist but cannot be Bayesian with a prior on C, in contrast to cases where a predictor in C achieves vanishing error.
The problem of forecasting conditional probabilities of the next event given the past is considered in a general probabilistic setting. Given an arbitrary (large, uncountable) set C of predictors, we would like to construct a single predictor that performs asymptotically as well as the best predictor in C, on any data. Here we show that there are sets C for which such predictors exist, but none of them is a Bayesian predictor with a prior concentrated on C. In other words, there is a predictor with sublinear regret, but every Bayesian predictor must have a linear regret. This negative finding is in sharp contrast with previous results that establish the opposite for the case when one of the predictors in $C$ achieves asymptotically vanishing error. In such a case, if there is a predictor that achieves asymptotically vanishing error for any measure in C, then there is a Bayesian predictor that also has this property, and whose prior is concentrated on (a countable subset of) C.