4 ms·
Yes, 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 descen
by enriquto 5y ago
Yes, 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...