Aaron Sidford

is this you? claim profile

∙ 0 followers
MIT ∙ Microsoft ∙ Stanford University

Assistant professor of Management Science and Engineering and, by courtesy, of Computer Science at Stanford University.

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

We characterize the complexity of minimizing max_i∈[N] f_i(x) for convex...
05/04/2021 ∙ by Yair Carmon, et al. ∙ 0 ∙ share

read it
Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances

In this paper we provide new randomized algorithms with improved runtime...
01/14/2021 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

In this paper we provide an O(m (loglog n)^O(1)log(1/ϵ))-expected time a...
11/17/2020 ∙ by Arun Jambulapati, et al. ∙ 0 ∙ share

read it
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

We show that standard extragradient methods (i.e. mirror prox and dual e...
11/12/2020 ∙ by Michael B. Cohen, et al. ∙ 0 ∙ share

read it
Semi-Streaming Bipartite Matching in Fewer Passes and Less Space

We provide algorithms with improved pass and space complexities for appr...
11/06/2020 ∙ by Yujia Jin, et al. ∙ 0 ∙ share

read it
Instance Based Approximations to Profile Maximum Likelihood

In this paper we provide a new efficient algorithm for approximately com...
11/05/2020 ∙ by Nima Anari, et al. ∙ 4 ∙ share

read it
Large-Scale Methods for Distributionally Robust Optimization

We propose and analyze algorithms for distributionally robust optimizati...
10/12/2020 ∙ by Daniel Lévy, et al. ∙ 0 ∙ share

read it
Coordinate Methods for Matrix Games

We develop primal-dual coordinate methods for solving bilinear saddle-po...
09/17/2020 ∙ by Yair Carmon, et al. ∙ 0 ∙ share

read it
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...
09/03/2020 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
Efficiently Solving MDPs with Stochastic Mirror Descent

We present a unified framework based on primal-dual stochastic mirror de...
08/28/2020 ∙ by Yujia Jin, et al. ∙ 0 ∙ share

read it
Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise

Classical iterative algorithms for linear system solving and regression ...
08/04/2020 ∙ by Jerry Li, et al. ∙ 0 ∙ share

read it
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Designing dynamic graph algorithms against an adaptive adversary is a ma...
04/17/2020 ∙ by Aaron Bernstein, et al. ∙ 0 ∙ share

read it
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

In this paper we consider the problem of computing the likelihood of the...
04/06/2020 ∙ by Nima Anari, et al. ∙ 8 ∙ share

read it
Faster Divergence Maximization for Faster Maximum Flow

In this paper we provide an algorithm which given any m-edge n-vertex di...
03/19/2020 ∙ by Yang P. Liu, et al. ∙ 0 ∙ share

read it
Acceleration with a Ball Optimization Oracle

Consider an oracle which takes a point x and returns the minimizer of a ...
03/18/2020 ∙ by Yair Carmon, et al. ∙ 0 ∙ share

read it
A General Framework for Symmetric Property Estimation

In this paper we provide a general framework for estimating symmetric pr...
03/02/2020 ∙ by Moses Charikar, et al. ∙ 0 ∙ share

read it
Solving Tall Dense Linear Programs in Nearly Linear Time

In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...
02/06/2020 ∙ by Jan van den Brand, et al. ∙ 0 ∙ share

read it
High-precision Estimation of Random Walks in Small Space

In this paper, we provide a deterministic Õ(log N)-space algorithm for e...
12/10/2019 ∙ by AmirMahdi Ahmadinejad, et al. ∙ 0 ∙ share

read it
Faster Matroid Intersection

In this paper we consider the classic matroid intersection problem: give...
11/25/2019 ∙ by Deeparnab Chakrabarty, et al. ∙ 0 ∙ share

read it
Faster Energy Maximization for Faster Maximum Flow

In this paper we provide an algorithm which given any m-edge n-vertex di...
10/31/2019 ∙ by Yang P. Liu, et al. ∙ 0 ∙ share

read it
Solving Linear Programs with Sqrt(rank) Linear System Solves

We present an algorithm that given a linear program with n variables, m ...
10/17/2019 ∙ by Yin Tat Lee, et al. ∙ 0 ∙ share

read it
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG

Given a data matrix A∈R^n × d, principal component projection (PCP) and ...
10/15/2019 ∙ by Yujia Jin, et al. ∙ 0 ∙ share

read it
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

In this paper we provide improved running times and oracle complexities ...
08/31/2019 ∙ by Brian Axelrod, et al. ∙ 0 ∙ share

read it
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity

In this paper, we settle the sampling complexity of solving discounted t...
08/29/2019 ∙ by Aaron Sidford, et al. ∙ 12 ∙ share

read it
Improved Girth Approximation and Roundtrip Spanners

In this paper we provide improved algorithms for approximating the girth...
07/25/2019 ∙ by Shiri Chechik, et al. ∙ 0 ∙ share

read it
Variance Reduction for Matrix Games

We present a randomized primal-dual algorithm that solves the problem _x...
07/03/2019 ∙ by Yair Carmon, et al. ∙ 0 ∙ share

read it
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond

In this paper, we provide near-optimal accelerated first-order methods f...
06/27/2019 ∙ by Oliver Hinder, et al. ∙ 0 ∙ share

read it
Complexity of Highly Parallel Non-Smooth Convex Optimization

A landmark result of non-smooth convex optimization is that gradient des...
06/25/2019 ∙ by Sébastien Bubeck, et al. ∙ 0 ∙ share

read it
A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport

Optimal transportation, or computing the Wasserstein or “earth mover's” ...
06/03/2019 ∙ by Arun Jambulapati, et al. ∙ 0 ∙ share

read it
Parallel Reachability in Almost Linear Work and Square Root Depth

In this paper we provide a parallel algorithm that given any n-node m-ed...
05/21/2019 ∙ by Arun Jambulapati, et al. ∙ 0 ∙ share

read it
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation

Estimating symmetric properties of a distribution, e.g. support size, co...
05/21/2019 ∙ by Moses Charikar, et al. ∙ 0 ∙ share

read it
Memory-Sample Tradeoffs for Linear Regression with Small Error

We consider the problem of performing linear regression over a stream of...
04/18/2019 ∙ by Vatsal Sharan, et al. ∙ 0 ∙ share

read it
Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space

In this paper we consider the problem of computing spectral approximatio...
03/28/2019 ∙ by Michael Kapralov, et al. ∙ 0 ∙ share

read it
Deterministic Approximation of Random Walks in Small Space

We give a deterministic, nearly logarithmic-space algorithm that given a...
03/15/2019 ∙ by Jack Murtagh, et al. ∙ 0 ∙ share

read it
A Rank-1 Sketch for Matrix Multiplicative Weights

We show that a simple randomized sketch of the matrix multiplicative wei...
03/07/2019 ∙ by Yair Carmon, et al. ∙ 0 ∙ share

read it
Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices

In this paper we show how to recover a spectral approximations to broad ...
12/15/2018 ∙ by Arun Jambulapati, et al. ∙ 0 ∙ share

read it
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression

In this paper, we obtain improved running times for regression and top e...
11/27/2018 ∙ by Neha Gupta, et al. ∙ 0 ∙ share

read it
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations

We show how to solve directed Laplacian systems in nearly-linear time. G...
11/26/2018 ∙ by Michael B. Cohen, et al. ∙ 0 ∙ share

read it
Towards Optimal Running Times for Optimal Transport

In this work, we provide faster algorithms for approximating the optimal...
10/17/2018 ∙ by Jose Blanchet, et al. ∙ 0 ∙ share

read it
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications

In this paper we provide nearly linear time algorithms for several probl...
10/04/2018 ∙ by AmirMahdi Ahmadinejad, et al. ∙ 0 ∙ share

read it
Coordinate Methods for Accelerating ℓ_∞ Regression and Faster Approximate Maximum Flow

In this paper we provide faster algorithms for approximately solving ℓ_∞...
08/03/2018 ∙ by Aaron Sidford, et al. ∙ 0 ∙ share

read it
Leverage Score Sampling for Faster Accelerated Regression and ERM

Given a matrix A∈R^n× d and a vector b ∈R^d, we show how to compute an ϵ...
11/22/2017 ∙ by Naman Agarwal, et al. ∙ 0 ∙ share

read it
Efficient O(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse

In this paper we consider the problem of efficiently computing ϵ-sketche...
11/02/2017 ∙ by Arun Jambulapati, et al. ∙ 0 ∙ share

read it
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)

This work provides a simplified proof of the statistical minimax optimal...
10/25/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

We give a deterministic Õ( n)-space algorithm for approximately solving ...
08/15/2017 ∙ by Jack Murtagh, et al. ∙ 0 ∙ share

read it
Efficient Convex Optimization with Membership Oracles

We consider the problem of minimizing a convex function over a convex se...
06/22/2017 ∙ by Yin Tat Lee, et al. ∙ 0 ∙ share

read it
Accelerating Stochastic Gradient Descent

There is widespread sentiment that it is not possible to effectively uti...
04/26/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging

This work characterizes the benefits of averaging techniques widely used...
10/12/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis

This paper considers the problem of canonical-correlation analysis (CCA)...
04/13/2016 ∙ by Rong Ge, et al. ∙ 0 ∙ share

read it
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

This work provides improved guarantees for streaming principle component...
02/22/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it

Aaron Sidford

Featured Co-authors