# Aaron Sidford

Orcid: 0000-0003-2675-7610Affiliations:

- Stanford University, CA, USA

According to our database

Collaborative distances:

^{1}, Aaron Sidford authored at least 141 papers between 2013 and 2024.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Dataset Other## Links

#### On csauthors.net:

## Bibliography

2024

Oper. Res. Lett., 2024

CoRR, 2024

CoRR, 2024

CoRR, 2024

CoRR, 2024

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

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

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

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

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract).

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization.

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Proceedings of the International Conference on Machine Learning, 2023

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

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

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Proceedings of the International Conference on Machine Learning, 2022

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

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

Theory Comput., 2021

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.

SIAM J. Comput., 2021

Math. Program., 2021

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

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

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

Proceedings of the 38th International Conference on Machine Learning, 2021

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

Math. Program., 2020

CoRR, 2020

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

CoRR, 2020

CoRR, 2020

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

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

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Proceedings of the 37th International Conference on Machine Learning, 2020

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Proceedings of the Conference on Learning Theory, 2020

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

CoRR, 2019

CoRR, 2019

CoRR, 2019

CoRR, 2019

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

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

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

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

Proceedings of the Conference on Learning Theory, 2019

Proceedings of the Conference on Learning Theory, 2019

2018

SIAM J. Optim., 2018

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

CoRR, 2018

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

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

Proceedings of the Conference On Learning Theory, 2018

Proceedings of the Conference On Learning Theory, 2018

2017

SIAM J. Comput., 2017

Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification.

J. Mach. Learn. Res., 2017

Inf. Process. Lett., 2017

CoRR, 2017

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

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

CoRR, 2016

CoRR, 2016

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

CoRR, 2016

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

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

Proceedings of the 33nd International Conference on Machine Learning, 2016

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

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

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

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

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

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