67 citations · 176 across the 22 of their papers we have counts for
11 papers · 1 filter
Instance Based Approximations to Profile Maximum Likelihood
Nima Anari, Moses Charikar, Kirankumar Shiragur +1
In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimat…
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
Michael B. Cohen, Aaron Sidford, Kevin Tian
We show that standard extragradient methods (i.e. mirror prox and dual extrapolation) recover optimal accelerated rates for first-order minimization of smooth convex functions. To…
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Sepehr Assadi, Arun Jambulapati, Yujia Jin +2
We provide -pass semi-streaming algorithms for computing -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…
Large-Scale Methods for Distributionally Robust Optimization
Daniel Levy, Yair Carmon, John C. Duchi +1
We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and divergence uncertainty sets. We prove th…
Coordinate Methods for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We develop primal-dual coordinate methods for solving bilinear saddle-point problems of the form which contain linear p…
Efficiently Solving MDPs with Stochastic Mirror Descent
Yujia Jin, Aaron Sidford
We present a unified framework based on primal-dual stochastic mirror descent for approximately solving infinite-horizon Markov decision processes (MDPs) given a generative model.…