67 citations · 97 across the 5 of their papers we have counts for
13 papers
A Direct Iteration Parallel Algorithm for Optimal Transport
Arun Jambulapati, Aaron Sidford, Kevin Tian
Optimal transportation, or computing the Wasserstein or ``earth mover's'' distance between two distributions, is a fundamental primitive which arises in many learning and statistic…
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
Estimating symmetric properties of a distribution, e.g. support size, coverage, entropy, distance to uniformity, are among the most fundamental problems in algorithmic statistics.…
Leverage Score Sampling for Faster Accelerated Regression and ERM
Naman Agarwal, Sham Kakade, Rahul Kidambi +3
Given a matrix and a vector , we show how to compute an -approximate solution to the regression problem $ \min_{x\in\m…
Lower Bounds for Finding Stationary Points II: First-Order Methods
Yair Carmon, John C. Duchi, Oliver Hinder +1
We establish lower bounds on the complexity of finding -stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic…
Efficient Spectral Sketches for the Laplacian and its Pseudoinverse
Arun Jambulapati, Aaron Sidford
In this paper we consider the problem of efficiently computing -sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance , we seek to constr…
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Jack Murtagh, Omer Reingold, Aaron Sidford +1
We give a deterministic -space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating h…