Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Faster Matrix Game Solvers Via Ball Oracle Acceleration
event speaker icon
Yair Carmon (Tel-Aviv university)
event date icon
Wednesday, 06.03.2024, 12:15
event location icon
Taub 201
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.