Computer Science/Discrete Mathematics Seminar I

Advances in Parallel and Private Stochastic Optimization from Ball Acceleration

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.

Date & Time

February 12, 2024 | 11:00am – 12:00pm


Simonyi 101 and Remote Access


Kevin Tian, The University of Texas at Austin