Exponentiated Gradient versus Gradient Descent for Linear Predictors Export

@article{citeulike:3736788, abstract = {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 EG ? . 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 EG ? 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 EG ? 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 EG ? 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.}, author = {Kivinen, J. and Warmuth, M. K.}, citeulike-article-id = {3736788}, citeulike-linkout-0 = {http://www.ingentaconnect.com/content/ap/ic/1997/00000132/00000001/art02612}, citeulike-linkout-1 = {http://www.cse.ucsc.edu/~manfred/pubs/J36.pdf}, comment = {=== Advantage of Multiplicative-Update Algorithms === It is shown that the number of mistakes the additive and multiplicative update algorithms make, depend differently on the domain characteristics. Informally speaking, it is shown that the multiplicative update algorithms have advantages in high dimensional problems (i.e., when the number of features is large) and when the target weight vector is sparse (i.e., contain many weights that are close to 0). This explains the recent success in using these methods on high dimensional problems (Golding and Roth, 1996) and suggests that multiplicative-update algorithms might do well on IR applications, provided that a good set of features is selected.}, issn = {0890-5401}, journal = {Information and Computation}, keywords = {exponential-gradient-descent, multiplicative-update, winnow}, month = {January}, pages = {1--63}, posted-at = {2008-12-02 20:01:26}, priority = {4}, publisher = {Academic Press}, title = {Exponentiated Gradient versus Gradient Descent for Linear Predictors}, url = {http://www.ingentaconnect.com/content/ap/ic/1997/00000132/00000001/art02612}, year = {1997} }

TY - JOUR ID - citeulike:3736788 L3 - citeulike-article-id:3736788 N2 - 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 EG ? . 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 EG ? 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 EG ? 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 EG ? 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. JF - Information and Computation SN - 0890-5401 EP - 63 TI - Exponentiated Gradient versus Gradient Descent for Linear Predictors PB - Academic Press SP - 1 KW - exponential-gradient-descent KW - multiplicative-update KW - winnow N1 - === Advantage of Multiplicative-Update Algorithms === It is shown that the number of mistakes the additive and multiplicative update algorithms make, depend differently on the domain characteristics. Informally speaking, it is shown that the multiplicative update algorithms have advantages in high dimensional problems (i.e., when the number of features is large) and when the target weight vector is sparse (i.e., contain many weights that are close to 0). This explains the recent success in using these methods on high dimensional problems (Golding and Roth, 1996) and suggests that multiplicative-update algorithms might do well on IR applications, provided that a good set of features is selected. AU - Kivinen, J AU - Warmuth, MK PY - 1997/01// UR - http://www.ingentaconnect.com/content/ap/ic/1997/00000132/00000001/art02612 ER -