
Thinking Inside the Ball: NearOptimal Minimization of the Maximal Loss
We characterize the complexity of minimizing max_i∈[N] f_i(x) for convex...
read it

Minimum Cost Flows, MDPs, and ℓ_1Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
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...
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...
read it

SemiStreaming Bipartite Matching in Fewer Passes and Less Space
We provide algorithms with improved pass and space complexities for appr...
read it

Instance Based Approximations to Profile Maximum Likelihood
In this paper we provide a new efficient algorithm for approximately com...
read it

LargeScale Methods for Distributionally Robust Optimization
We propose and analyze algorithms for distributionally robust optimizati...
read it

Coordinate Methods for Matrix Games
We develop primaldual coordinate methods for solving bilinear saddlepo...
read it

Bipartite Matching in Nearlylinear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)time randomized algorithm for maximum cardinali...
read it

Efficiently Solving MDPs with Stochastic Mirror Descent
We present a unified framework based on primaldual stochastic mirror de...
read it

WellConditioned Methods for IllConditioned Systems: Linear Regression with SemiRandom Noise
Classical iterative algorithms for linear system solving and regression ...
read it

FullyDynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
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...
read it

Faster Divergence Maximization for Faster Maximum Flow
In this paper we provide an algorithm which given any medge nvertex di...
read it

Acceleration with a Ball Optimization Oracle
Consider an oracle which takes a point x and returns the minimizer of a ...
read it

A General Framework for Symmetric Property Estimation
In this paper we provide a general framework for estimating symmetric pr...
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...
read it

Highprecision Estimation of Random Walks in Small Space
In this paper, we provide a deterministic Õ(log N)space algorithm for e...
read it

Faster Matroid Intersection
In this paper we consider the classic matroid intersection problem: give...
read it

Faster Energy Maximization for Faster Maximum Flow
In this paper we provide an algorithm which given any medge nvertex di...
read it

Solving Linear Programs with Sqrt(rank) Linear System Solves
We present an algorithm that given a linear program with n variables, m ...
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 ...
read it

Nearoptimal Approximate Discrete and Continuous Submodular Function Minimization
In this paper we provide improved running times and oracle complexities ...
read it

Solving Discounted Stochastic TwoPlayer Games with NearOptimal Time and Sample Complexity
In this paper, we settle the sampling complexity of solving discounted t...
read it

Improved Girth Approximation and Roundtrip Spanners
In this paper we provide improved algorithms for approximating the girth...
read it

Variance Reduction for Matrix Games
We present a randomized primaldual algorithm that solves the problem _x...
read it

NearOptimal Methods for Minimizing StarConvex Functions and Beyond
In this paper, we provide nearoptimal accelerated firstorder methods f...
read it

Complexity of Highly Parallel NonSmooth Convex Optimization
A landmark result of nonsmooth convex optimization is that gradient des...
read it

A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport
Optimal transportation, or computing the Wasserstein or “earth mover's” ...
read it

Parallel Reachability in Almost Linear Work and Square Root Depth
In this paper we provide a parallel algorithm that given any nnode med...
read it

Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Estimating symmetric properties of a distribution, e.g. support size, co...
read it

MemorySample Tradeoffs for Linear Regression with Small Error
We consider the problem of performing linear regression over a stream of...
read it

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
In this paper we consider the problem of computing spectral approximatio...
read it

Deterministic Approximation of Random Walks in Small Space
We give a deterministic, nearly logarithmicspace algorithm that given a...
read it

A Rank1 Sketch for Matrix Multiplicative Weights
We show that a simple randomized sketch of the matrix multiplicative wei...
read it

Efficient Structured Matrix Recovery and NearlyLinear Time Algorithms for Solving Inverse Symmetric MMatrices
In this paper we show how to recover a spectral approximations to broad ...
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...
read it

Solving Directed Laplacian Systems in NearlyLinear Time through Sparse LU Factorizations
We show how to solve directed Laplacian systems in nearlylinear time. G...
read it

Towards Optimal Running Times for Optimal Transport
In this work, we provide faster algorithms for approximating the optimal...
read it

PerronFrobenius Theory in Nearly Linear Time: Positive Eigenvectors, Mmatrices, Graph Kernels, and Other Applications
In this paper we provide nearly linear time algorithms for several probl...
read it

Coordinate Methods for Accelerating ℓ_∞ Regression and Faster Approximate Maximum Flow
In this paper we provide faster algorithms for approximately solving ℓ_∞...
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 ϵ...
read it

Efficient O(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse
In this paper we consider the problem of efficiently computing ϵsketche...
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...
read it

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
We give a deterministic Õ( n)space algorithm for approximately solving ...
read it

Efficient Convex Optimization with Membership Oracles
We consider the problem of minimizing a convex function over a convex se...
read it

Accelerating Stochastic Gradient Descent
There is widespread sentiment that it is not possible to effectively uti...
read it

Parallelizing Stochastic Approximation Through MiniBatching and TailAveraging
This work characterizes the benefits of averaging techniques widely used...
read it

Efficient Algorithms for Largescale Generalized Eigenvector Computation and Canonical Correlation Analysis
This paper considers the problem of canonicalcorrelation analysis (CCA)...
read it

Streaming PCA: Matching Matrix Bernstein and NearOptimal Finite Sample Guarantees for Oja's Algorithm
This work provides improved guarantees for streaming principle component...
read it
Aaron Sidford
is this you? claim profile
Assistant professor of Management Science and Engineering and, by courtesy, of Computer Science at Stanford University.