The Taub Faculty of Computer Science Events and Talks

We design a new stochastic first-order algorithm for approximately solving matrix games as well as the more general problem of minimizing the maximum of smooth convex functions. Our central tool is ball oracle acceleration: a technique for minimizing any convex function with a small number of calls to a ball oracle that minimizes the same function restricted to a small ball around the query point. To design an efficient ball oracle for our problems of interest we leverage stochastic gradient descent, softmax smoothing, rejection sampling, and sketching. For a large number of general smooth functions, our algorithm obtains optimal gradient query complexity. For matrix games, it improves over all previous runtime bounds in a range of problem parameters.

Based on joint work with Arun Jambulapati, Yujia Jin, and Aaron Sidford.