zbMATH — the first resource for mathematics

Exponentiated gradient versus gradient descent for linear predictors. (English) Zbl 0872.68158
Summary: We consider two algorithms for on-line prediction based on a linear model. The algorithms are the well-known gradient descent (GD) algorithm and a new algorithm, which we call \(\text{EG}^\pm\). They both maintain a weight vector using simple updates. For the GD algorithm, the update is based on subtracting the gradient of the squared error made on a prediction. The \(\text{EG}^\pm\) algorithm uses the components of the gradient in the exponents of factors that are used in updating the weight vector multiplicatively. We present worst-case loss bounds for \(\text{EG}^\pm\) and compare them to previously known bounds for the GD algorithm. The bounds suggest that the losses of the algorithms are in general incomparable, but \(\text{EG}^\pm\) has a much smaller loss if only few components of the input are relevant for the predictions. We have performed experiments which show that our worst-case upper bounds are quite tight already on simple artificial data.

68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI