30 citations · 37 across the 4 of their papers we have counts for
4 papers
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions
Yair Carmon, Arun Jambulapati, Yujia Jin +1
We design algorithms for minimizing over a -dimensional Euclidean or simplex domain. When each is -Lipschitz and -smooth, our method computes…
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
Adam Bouland, Yosheb Getachew, Yujia Jin +2
We give a quantum algorithm for computing an -approximate Nash equilibrium of a zero-sum game in a payoff matrix with bounded entries. Given a standard quantum orac…
Competing with the Empirical Risk Minimizer in a Single Pass
Roy Frostig, Rong Ge, Sham M. Kakade +1
In many estimation problems, e.g. linear and logistic regression, we wish to minimize an unknown objective given only unbiased samples of the objective function. Furthermore, we ai…
Single Pass Spectral Sparsification in Dynamic Streams
Michael Kapralov, Yin Tat Lee, Cameron Musco +2
We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions…