3 ms·
Nice write up, the 'it's not gradient descent due to rewards adaptiveness' I don't understand, most usages of GD are non vanilla and adaptive.
by antman 5y ago
Nice write up, the 'it's not gradient descent due to rewards adaptiveness' I don't understand, most usages of GD are non vanilla and adaptive.
- deleted 5y ago[deleted]
- enriquto 5y agoYes, the article is beautiful and clearly written but it seems that this insight is wrong. The algorithm can indeed be regarded as a stochastic gradient descent with approximate descent directions.
- TimonKnigge 5y agoNot exactly -- multiplicative weights is a special case of mirror descent (as is gradient descent). It arises doing prox-steps on the simplex using the negative entropy as a regularizer (rather than the usual Euclidian distance, as is the case with gradient descent). In particular, if you do regular gradient descent then the runtime will be exponentially worse (the \log n in the guarantee will become a \sqrt{n}). Here's an interesting lecture on the topic: https://nisheethvishnoi.files.wordpress.com/2018/05/lecture42.pdf https://nisheethvishnoi.files.wordpress.com/2018/05/lecture4...