Seminar on Computational Learning and Adaptation

Methods for Proving Relative Loss Bounds

Manfred K. Warmuth
Computer Science Department
University of California, Santa Cruz
manfred@cse.ucsc.edu

We consider on-line learning from examples. We start with a parameterized model class and a loss function that assigns each example and model a non-negative loss. The on-line algorithm sees one example at a time and incurs a loss on the current example based on its current model. This model (hypothesis) is updated on-line as more examples are seen by the learner. The best fixed model is chosen off-line. It is the model in the class with the smallest (total) loss on all examples.

The loss of the on-line algorithm on a sequence of examples is typically larger than the loss of the best off-line model. However, the goal of the on-line learner is to minimize the additional loss of the on-line algorithm over the loss of the best off-line model. Thus the off-line model serves as a comparator. Bounds relating the on-line loss to the best off-line loss are called relative loss bounds. Such bounds quantify the price of hiding the future examples from the learner. The bounds hold for arbitrary sequence of examples.

We will review methods for proving such bounds. We will emphasize a method that starts with a divergence measuring the ``distance'' between the parameterized models. This divergence function is used to derive the parameter update of the on-line learner and it becomes the potential function in the proof of the relative loss bound for the same update. Finally we discuss the case when the off-line comparator is allowed to ``shift'' over time. In some cases one can obtain bounds on the additional loss of the on-line algorithm over the loss of the best ``shifting'' off-line model.

Return to the seminar schedule