Aggregating Algorithm for a Space of Analytic Functions

Author: Mikhail Dashevskiy

Source: Algorithmic Learning Theory, 19th International Conference, ALT 2008, Budapest, October 2008, Proceedings,
Lecture Notes in Artificial Intelligence 5254, pp. 214 - 226, Springer, 2008.

Abstract. In this paper the problem of Prediction with Expert Advice is considered. We apply an existing algorithm, the Aggregating Algorithm, to a specific class of experts. This class of experts approximates the class of continuous functions and in this way it is close to a natural way of describing a possible dependence between two variables (continuous). We develop an explicit algorithm and prove an upper bound on the difference between the loss of our algorithm and the loss of the best expert, which has the order of the squared logarithm of the number of steps of the algorithm. This bound is the squared logarithm of the number of steps which is an intermediate result between existing bounds of the logarithm of the number of steps and the square root of the number of steps.

©Copyright 2008, Springer