Prediction With Expert Advice Under Discounted Loss
The paper describes the application of the idea of Shortcut Defensive Forecasting to compete under discounted loss. It suggests a modification of the Aggregating Algorithm for that. The arXiv technical report contains more detailed description of the idea of the modification, and of the theorems which are possible to prove.
The problem of prediction with expert advice under discounted loss is considered. The cumulative discounted loss is defined as for , , loss function (mixable or not), and discounting factors . In the case when , there is no discounting. The case when is the most popular and is called exponential discounting. The following theorem is the main result of the paper (we state it here only for the -mixable loss functions, but the paper describes the general case). It holds when the number of experts is finite.
Theorem. Learner has a strategy guaranteeing that, for any and for any , it holds
The algorithm works as follows.
For non-mixable but convex and bounded games, a modification of the Weak Aggregating Algorithm is used to prove an upper bound on the discounted loss of the learner.
Theorem. Suppose that is a non-empty convex game and for all and . Learner has a strategy guaranteeing that, for any and for any , it holds
where and .
For the discounted square loss function, it is possible to compete with linear and kernelized linear experts in the online regression framework. Denote by the matrix of size consisting of the rows of the input vectors . Let also , i.e., is a diagonal matrix .
Theorem. For any , there exists a prediction strategy for Learner in online regression protocol achieving, for every and for any linear predictor ,
If, in addition, for all , then
Interestingly, instead of the time variable (as in the bound for Aggregating Algorithm Regression), we have . For exponential discounting for all , we have .
The method which achieves the bound for linear regression is similar to online weighed least squares.