Analysis of two gradient-based algorithms for on-line regression
Nicolò Cesa‐Bianchi · 1997
In this paper we present a new analysis, within the on-line regression framework, of two algorithms: Gradient Descent and Exponentiated Gradient.Both algorithms update their parameters based on the gradient of the loss function; however, their update rules are substantially different.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.This extends 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.)