65 citations · 187 across the 18 of their papers we have counts for
25 papers
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…
A near-optimal algorithm for approximating the John Ellipsoid
Michael B. Cohen, Ben Cousins, Yin Tat Lee +1
We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matche…
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
This paper shows how to solve linear programs of the form with variables in time where is the e…
Constant Arboricity Spectral Sparsifiers
Timothy Chu, Michael B. Cohen, Jakub W. Pachocki +1
We show that every graph is spectrally similar to the union of a constant number of forests. Moreover, we show that Spielman-Srivastava sparsifiers are the union of O(logn) forests…
Metrical task systems on trees via mirror descent and unfair gluing
Sébastien Bubeck, Michael B. Cohen, James R. Lee +1
We consider metrical task systems on tree metrics, and present an -competitive randomized algorithm based on the mirror descent framework introduce…