Five Miracles of Mirror Descent, Lecture 6/9

Lectures on ``some geometric aspects of randomized online decision making" by Sebastien Bubeck for the summer school HDPA-2019 (High dimensional probability and algorithms) hdpa2019.sciencesconf.org/
Lecture 6:
- Discrete time analysis of mirror descent (with proof derived from the continuous time analysis)
- Revisiting Multiplicative Weights Update (from lecture 2) with discrete time mirror descent
Lecture notes can be found here: hdpa2019.sciencesconf.org/dat...

[@ruiyuanhuang6524]

Hi Sebastien, could you please elaborate on why the discrete regret contains the second order term while the continuous regret equals to the derivative only?

[@SebastienBubeck]

This is because in discrete time you are doing one ``big" step with only the gradient at the start point, while in continuous time you are continuously updating the gradient, so there is some difference between the two processes which has to do with how the gradient is changing along the path, which is exactly a second order term (``the change of the change").

[@ruiyuanhuang6524]

​@@SebastienBubeck Oh I understand it, thank you so much

[@avimohan6594]

@@SebastienBubeck I'd recommend going through Seb's U Washington (Allen School) tutorial where he explains this in much greater detail and clearly extracts the discrete time analysis from the gradient flow analysis.