Online convex optimization seems to have an endless zoo of algorithms: Online Gradient Descent, Follow the Regularized Leader, Multiplicative Weights, Mirror Descent, and many more. But how different are these algorithms, really?
In this talk, we'll try to dismantle this zoo, one algorithm at a time. We'll start by seeing why linear losses are essentially all we need to understand online convex optimization. Then we'll introduce two seemingly different philosophies for making decisions: following the gradient and following the (regularized) leader. Surprisingly, these often turn out to be two ways of describing the same algorithm. Finally, we'll see how changing a regularizer gives rise to apparently different algorithms, including Multiplicative Weights.
