5
$\begingroup$

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$?

I know there is a well-known exponentiated gradient descent (EG) algorithm, which gives $w_{t+1}\propto w_t\exp[-\lambda_t\nabla f(w_t)]$, I'm just wondering if a more general multiplicative gradient descent like the one given above exists?

Thanks!

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
8
$\begingroup$

The most general form of such algorithms are named Mirror-Descent. This algorithm is an extension of gradient descent for non-Euclidean geometries.

For a formal explanation on how multiplicative weights (or exponentiated gradient descent) is a particular setup for Mirror-Descent see Appendix A.2 from http://arxiv.org/abs/1407.1537

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks! I guess the update $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$ update, which is a "direct" multiplicative extension of additive gradient descent, is not meaningful anyway, it needs to be exponentiated first to make the variables remain positive. This falls into the MD framework. $\endgroup$
    – thinkbear
    Commented Sep 15, 2014 at 2:17
  • $\begingroup$ Precisely. And most importantly, in all these 'experts' type of algorithms you are implicitly searching for probability distributions $\sum_i w_i=1$, $w_i\geq 0$, which is a simplex setup and thus you can use entropy as distance generating function. That's where the formulae come from. $\endgroup$
    – Cristóbal Guzmán
    Commented Sep 15, 2014 at 4:04
0
$\begingroup$

You may also be interested in knowing about Exponentiated Gradient +/- (EG+/-), described by Warmuth and Kivinen on page 15 here (https://users.soe.ucsc.edu/~manfred/pubs/J36.pdf).

In EG+/- you maintain two sets of weights, one representing the positive side of the weights and a second representing the negative side of the weight. In use you combine the positive and negative weights, but maintain the separately for the updates.

The update is described quite succinctly there on page 15, the intuition is that the update method generates a set of values a little above or below 1 based on the gradient which is multiplied into the weights to draw them up or down as appropriate.

I've applied the update method in a fully connected feedforward network in this code: http://github.com/davidparks21/experimental_neural_network_matlab

At present I've demonstrated, and a few other papers on EG applied to neural networks have also found, that it tends to out perform standard additive gradient descent updates in the presence of heavy amounts of noise, however additive GD tends to out perform EG+- on noise-free datasets, MNIST as an example as such. The data sets I've demonstrated the improvement on have had noise added, I haven't yet demonstrate the same on a real world data set (thought it's on my todo list).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .