|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-99-043
Analysis
of Two Gradient-based Algorithms for On-line Regression
Nicoḷ Cesa-Bianchi
Universita' di Milano, Italy
Received:
19-APR-99
Abstract
In this paper
we present a new analysis of two algorithms, Gradient Descent and
Exponentiated Gradient, for solving regression problems in the on-line
framework. Both these algorithms compute a prediction that depends
linearly on the current instance, and then update the coefficients
of this linear combination according to the gradient of the loss function.
However, the two algorithms have distinctive ways of using the gradient
information for updating the coefficients. For each algorithm, we
show general regression bounds for any convex loss function. Furthermore,
we show special bounds for the absolute and the square loss functions,
thus extending previous results by Kivinen and Warmuth. In the
nonlinear regression case, we show general bounds for pairs of transfer
and loss functions satisfying a certain condition. We apply this result
to the Hellinger loss and the entropic loss in case of logistic regression
(similar results, but only for the entropic loss, were also obtained
by Helmbold et al.using a different analysis.) Finally, we describe
the connection between our approach and a general family of gradient-based
algorithms proposed by Warmuth et al. in recent works.
Download Compressed Postscript
|