Computer Science/Discrete Mathematics Seminar I

Consider an oracle which takes a point $x$ and returns the minimizer of a convex function $f$ in an $\ell_2$ ball of radius $r$ around $x$. While it is straightforward to show that $\approx r^{-1}$ queries to this oracle suffice to minimize $f$ to high accuracy in a unit ball, perhaps surprisingly, we established recently that $r^{-2/3}$ queries is the tight rate up to logarithmic factors. The resulting framework, also known as ball acceleration, has advanced the state-of-the-art for a host of fundamental optimization problems exhibiting local stability. I will provide an overview of the ball acceleration framework, its approximation-tolerant implementation, and its applications, with an emphasis on parallel and private variants of stochastic convex optimization and outstanding open directions.