Acceleration by randomization: randomized first order algorithms

for large-scale convex optimization

Arkadi Nemirovski

Abstract: In 1995, Grigoriadis and Khachiyan proposed the very first

sublinear time randomized algorithm for matrix games. In the talk, we

discuss recent explanation, extensions and modifications of this

surprising result and outline their potential applications in large-scale Signal

Processing and Semidefinite Programming.