Absolute Loss Bounds for Prediction using Linear Functions
No Thumbnail Available
Date
1996-07-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We prove new absolute loss bounds for learning linear functions in the standard on-line prediction model. These bounds are on the difference between the sum of absolute prediction errors made by the learning algorithm, and the best sum of absolute prediction errors that can be obtained by fixing a linear function in some class. Known results imply that our bounds on this difference cannot be improved by more than a constant factor.