Operations Research Seminar: Sebastian Stich

Randomized Algorithms for Convex Optimization

Sebastian STICH, CORE, Université catholique de Louvain

In the last years, randomized optimization algorithms, and especially coordinate descent methods attracted more and more attention in the optimization community. These methods often replace the efficient  ̶  but often relative expensive  ̶  iterations of the classical methods with much cheaper  ̶  but less efficient  ̶  updates. Consequently, such methods can be applied to problems of very big size. This application is sometimes also theoretically justified by very attractive worst-case efficiency guarantees.

In this talk, we will introduce randomized analogues of the classical primal-, dual- and accelerated schemes and provide the corresponding complexity estimates on unconstrained convex optimization problems. We also discuss important applications where the randomized schemes dominate the classical methods.

If time allows, we will also present two randomized variable metric schemes that can be viewed as analogues of second order methods like Newton’s method and BFGS.