A Unified Approach to Universal Prediction: Generalized Upper and Lower
  Bounds
  We study sequential prediction of real-valued, arbitrary and unknown
sequences under the squared error loss as well as the best parametric predictor
out of a large, continuous class of predictors. Inspired by recent results from
computational learning theory, we refrain from any statistical assumptions and
define the performance with respect to the class of general parametric
predictors. In particular, we present generic lower and upper bounds on this
relative performance by transforming the prediction task into a parameter
learning problem. We first introduce the lower bounds on this relative
performance in the mixture of experts framework, where we show that for any
sequential algorithm, there always exists a sequence for which the performance
of the sequential algorithm is lower bounded by zero. We then introduce a
sequential learning algorithm to predict such arbitrary and unknown sequences,
and calculate upper bounds on its total squared prediction error for every
bounded sequence. We further show that in some scenarios we achieve matching
lower and upper bounds demonstrating that our algorithms are optimal in a
strong minimax sense such that their performances cannot be improved further.
As an interesting result we also prove that for the worst case scenario, the
performance of randomized algorithms can be achieved by sequential algorithms
so that randomized algorithms does not improve the performance.
