|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-00-083
Adaptive
and Self-Confident
On-Line Learning Algorithms
Peter Auer
Nicolo' Cesa-Bianchi
Claudio Gentile
Abstract
In this paper, we study the family of quasi-additive learning
algorithms applied to on-line linear regression problems. The on-line
algorithms in this family are efficient and easy to implement. They
work well with various losses and, furthermore, they are very robust
to noise, i.e., one can prove that their cumulative loss on any
data sequence cannot grow much faster than the loss of the best off-line
linear predictor on the same data sequence. However, to achieve these
performance bounds, the learning rate must be optimized based on a
posteriori information. This information depends on the whole
sequence of examples and thus it is not available to any strictly
on-line algorithm.
In this paper, we introduce new techniques for adaptively tuning the
learning rate as the data sequence is progressively revealed. Our
techniques allow us to prove essentially the same performance bounds
as if we knew the optimal learning rate in advance. the information
needed to optimally tune the learning rate. Moreover, such techniques
apply to a wide class of on-line algorithms, including p-norm
algorithms for generalized linear regression and Weighted Majority
for linear regression with absolute loss.
We emphasize that our adaptive tunings are radically different from
previous techniques, such as the so-called doubling trick. Whereas
the doubling trick restarts the on-line algorithm several times using
a constant learning rate for each run, our methods save information
by changing the value of the learning rate very smoothly. In fact,
for Weighted Majority over a finite set of experts our analysis provides
a better leading constant than the doubling trick.
Download
Compressed Postscript
|