Aaron Sidford

Affiliations:
  • Stanford University, CA, USA


According to our database1, Aaron Sidford authored at least 135 papers between 2013 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2023
Entropy Regularization and Faster Decremental Matching in General Graphs.
CoRR, 2023

Sparsifying generalized linear models.
CoRR, 2023

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions.
CoRR, 2023

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.
CoRR, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
CoRR, 2023

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
CoRR, 2023

Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification.
CoRR, 2023

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Dynamic Maxflow via Dynamic Interior Point Methods.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved girth approximation in weighted undirected graphs.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Quantum speedups for stochastic optimization.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Structured Semidefinite Programming for Recovering Structured Preconditioners.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Towards Optimal Effective Resistance Estimation.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Parallel Submodular Function Minimization.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

The Complexity of Infinite-Horizon General-Sum Stochastic Games.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract).
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.
Proceedings of the International Conference on Machine Learning, 2023

Matrix Completion in Almost-Verification Time.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sparsifying Sums of Norms.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sparse Submodular Function Minimization.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

ReSQueing Parallel and Private Stochastic Convex Optimization.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Semi-Random Sparse Recovery in Nearly-Linear Time.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Moments, Random Walks, and Limits for Spectrum Approximation.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022
Improved iteration complexities for overconstrained <i>p</i>-norm regression.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Faster maxflow via improved dynamic spectral vertex sparsifiers.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Algorithmic trade-offs for girth approximation in undirected graphs.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Computing Lewis Weights to High Precision.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Optimal and Adaptive Monteiro-Svaiter Acceleration.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization.
Proceedings of the International Conference on Machine Learning, 2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Improved Lower Bounds for Submodular Function Minimization.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Efficient Convex Optimization Requires Superlinear Memory.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021
Deterministic Approximation of Random Walks in Small Space.
Theory Comput., 2021

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
SIAM J. Comput., 2021

Lower bounds for finding stationary points II: first-order methods.
Math. Program., 2021

Improved Iteration Complexities for Overconstrained p-Norm Regression.
CoRR, 2021

Minimum cost flows, MDPs, and ℓ<sub>1</sub>-regression in nearly linear time for dense instances.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Stochastic Bias-Reduced Gradient Methods.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Towards Tight Bounds on the Sample Complexity of Average-reward MDPs.
Proceedings of the 38th International Conference on Machine Learning, 2021

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss.
Proceedings of the Conference on Learning Theory, 2021

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood.
Proceedings of the Conference on Learning Theory, 2021

2020
Lower bounds for finding stationary points I.
Math. Program., 2020

Semi-Streaming Bipartite Matching in Fewer Passes and Less Space.
CoRR, 2020

Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise.
CoRR, 2020

Faster Divergence Maximization for Faster Maximum Flow.
CoRR, 2020

Faster energy maximization for faster maximum flow.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Constant girth approximation for directed graphs in subquadratic time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Solving tall dense linear programs in nearly linear time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Large-Scale Methods for Distributionally Robust Optimization.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Acceleration with a Ball Optimization Oracle.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Instance Based Approximations to Profile Maximum Likelihood.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Efficiently Solving MDPs with Stochastic Mirror Descent.
Proceedings of the 37th International Conference on Machine Learning, 2020

Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Coordinate Methods for Matrix Games.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

High-precision Estimation of Random Walks in Small Space.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.
Proceedings of the Conference on Learning Theory, 2020

Leverage Score Sampling for Faster Accelerated Regression and ERM.
Proceedings of the Algorithmic Learning Theory, 2020

Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019
Solving Linear Programs with Sqrt(rank) Linear System Solves.
CoRR, 2019

Improved Girth Approximation and Roundtrip Spanners.
CoRR, 2019

A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport.
CoRR, 2019

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space.
CoRR, 2019

Memory-sample tradeoffs for linear regression with small error.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Efficient profile maximum likelihood for universal symmetric property estimation.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A General Framework for Symmetric Property Estimation.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Variance Reduction for Matrix Games.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Complexity of Highly Parallel Non-Smooth Convex Optimization.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Parallel Reachability in Almost Linear Work and Square Root Depth.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Faster Matroid Intersection.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.
Proceedings of the Conference on Learning Theory, 2019

A Rank-1 Sketch for Matrix Multiplicative Weights.
Proceedings of the Conference on Learning Theory, 2019

Near-optimal method for highly smooth convex optimization.
Proceedings of the Conference on Learning Theory, 2019

2018
Accelerated Methods for NonConvex Optimization.
SIAM J. Optim., 2018

Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices.
CoRR, 2018

Towards Optimal Running Times for Optimal Transport.
CoRR, 2018

Coordinate Methods for Accelerating 𝓁<sub>∞</sub> Regression and Faster Approximate Maximum Flow.
CoRR, 2018

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Stability of the Lanczos Method for Matrix Function Approximation.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Efficient <i>Õ</i>(<i>n</i>/<i>∊</i>) Spectral Sketches for the Laplacian and its Pseudoinverse.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Efficient Convex Optimization with Membership Oracles.
Proceedings of the Conference On Learning Theory, 2018

Accelerating Stochastic Gradient Descent for Least Squares Regression.
Proceedings of the Conference On Learning Theory, 2018

2017
Single Pass Spectral Sparsification in Dynamic Streams.
SIAM J. Comput., 2017

Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification.
J. Mach. Learn. Res., 2017

Arboral satisfaction: Recognition and LP approximation.
Inf. Process. Lett., 2017

Efficient Õ(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse.
CoRR, 2017

Accelerating Stochastic Gradient Descent.
CoRR, 2017

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Subquadratic submodular function minimization.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions.
Proceedings of the 34th International Conference on Machine Learning, 2017

A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares).
Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016
Accelerated Methods for Non-Convex Optimization.
CoRR, 2016

Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging.
CoRR, 2016

Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm.
CoRR, 2016

Routing under balance.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Geometric median in nearly linear time.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis.
Proceedings of the 33nd International Conference on Machine Learning, 2016

Faster Eigenvector Computation via Shift-and-Invert Preconditioning.
Proceedings of the 33nd International Conference on Machine Learning, 2016

Principal Component Projection Without Principal Component Analysis.
Proceedings of the 33nd International Conference on Machine Learning, 2016

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
Iterative methods, combinatorial optimization, and linear programming beyond the universal barrier.
PhD thesis, 2015

Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation.
CoRR, 2015

Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Uniform Sampling for Matrix Approximation.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization.
Proceedings of the 32nd International Conference on Machine Learning, 2015

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Competing with the Empirical Risk Minimizer in a Single Pass.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem.
CoRR, 2013

Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.
CoRR, 2013

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013


  Loading...