|
|
|
|
|
|
by TimonKnigge
1808 days ago
|
|
|
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... |
|
|