Hacker News Reader

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.

View on HN

Not 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/lecture4...

Reply on news.ycombinator.com