Competitive On-line Linear Regression

Neural Information Processing SystemsPublished 1 December 1997

Vladimir Vovk

Citations58

TL;DR

It is shown that the Aggregating Algorithm attains the optimal constant in the authors' bound, whereas the constant attained by the ridge regression procedure in general can be 4 times worse.

Abstract

We apply a general algorithm for merging prediction strategies (the Aggregating Algorithm) to the problem of linear regression with the square loss; our main assumption is that the response variable is bounded. It turns out that for this particular problem the Aggregating Algorithm resembles, but is slightly different from, the well-known ridge estimation procedure. From general results about the Aggregating Algorithm we deduce a guaranteed bound on the difference between our algorithm's performance and the best, in some sense, linear regression function's performance. We show that the AA attains the optimal constant in our bound, whereas the constant attained by the ridge regression procedure in general can be 4 times worse.

Keywords

Computer ScienceDecision Sciences

The Nature of Statistical Learning Theory

39,279 Citations1995Vladimir Vapnik

Information and ComputationThe Weighted Majority Algorithm

2,022 Citations1994N. Littlestone, Manfred K. Warmuth

Information and ComputationExponentiated Gradient versus Gradient Descent for Linear Predictors

880 Citations1997Jyrki Kivinen, Manfred K. Warmuth

The bounds suggest that the losses of the algorithms are in general incomparable, but EG(+/-) has a much smaller loss if only a few components of the input are relevant for the predictions, which is quite tight already on simple artificial data.

Journal of Computer and System SciencesA Game of Prediction with Expert Advice

292 Citations1998Vladimir Vovk

IEEE Transactions on Neural NetworksWorst-case quadratic loss bounds for prediction using linear functions and gradient descent

150 Citations1996Nicolò Cesa‐Bianchi, Philip M. Long +1 more

This work studies the performance of gradient descent when applied to the problem of online linear prediction in arbitrary inner product spaces and proves worst-case bounds on the sum of the squared prediction errors under various assumptions concerning the amount of a priori information about the sequence to predict.

Learning probabilistic prediction functions

94 Citations1988Alfredo De Santis, George Markowsky +1 more

The question of how to learn rules, when those rules make probabilistic statements about the future, is considered and two results related to these distinct goals are given.

IEEE Transactions on Information TheoryA decision-theoretic extension of stochastic complexity and its applications to learning

92 Citations1998Kenji Yamanishi

Through the ESC, the notion of extended stochastic complexity is introduced and its effectiveness in design and analysis of learning algorithms in on-line prediction and batch-learning scenarios is demonstrated, giving a unifying view of the most effective learning algorithms that have been explored in computational learning theory.

Lecture notes in computer scienceTight worst-case loss bounds for predicting with expert advice

88 Citations1995David Haussler, Jyrki Kivinen +1 more

This work considers on-line algorithms for predicting binary or continuous-valued outcomes, when the algorithm has available the predictions made by N experts, and shows that for a large class of loss functions, with binary outcomes the total loss of the algorithm proposed by Vovk exceeds the total losses of the best expert at most by the amount c ln N, where c is a constant determined by the loss function.

Predicting a binary sequence almost as well as the optimal biased coin

68 Citations1996Yoav Freund

It is shown that for the case of the logarithmic loss, the derived algorithm is equivalent to the Bayes algorithm with Jeffreys prior, that was studied by Xie and Barron under probabilistic assumptions.

View PDF

The Annals of StatisticsPrediction in the Worst Case

63 Citations1991Dean P. Foster

View PDF