Aaron Sidford

Computing Lewis weights to high precision using local relative smoothness COLT 2026 Convex optimization with p-norm oracles ALT 2026 Fast, Parallel, Query-Efficient Binary Classification COLT 2026 Randomization for Faster Exact Optimization of Discounted Markov Decision Processes COLT 2026 Reusing Samples in Variance Reduction ALT 2026 Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization COLT 2024 Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract) COLT 2024 Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting NeurIPS 2024 Truncated Variance Reduced Value Iteration NeurIPS 2024 Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract) IJCAI 2023 Moments, Random Walks, and Limits for Spectrum Approximation COLT 2023 Parallel Submodular Function Minimization NeurIPS 2023 Quantum speedups for stochastic optimization NeurIPS 2023 Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling ICML 2023 Semi-Random Sparse Recovery in Nearly-Linear Time COLT 2023 Structured Semidefinite Programming for Recovering Structured Preconditioners NeurIPS 2023 Towards Optimal Effective Resistance Estimation NeurIPS 2023 Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales COLT 2022 Efficient Convex Optimization Requires Superlinear Memory COLT 2022 On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood NeurIPS 2022 Optimal and Adaptive Monteiro-Svaiter Acceleration NeurIPS 2022 RECAPP: Crafting a More Efficient Catalyst for Convex Optimization ICML 2022 Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods COLT 2022 Stochastic Bias-Reduced Gradient Methods NeurIPS 2021 The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood COLT 2021 Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss COLT 2021 Towards Tight Bounds on the Sample Complexity of Average-reward MDPs ICML 2021 Acceleration with a Ball Optimization Oracle NeurIPS 2020 Efficiently Solving MDPs with Stochastic Mirror Descent ICML 2020 Instance Based Approximations to Profile Maximum Likelihood NeurIPS 2020 Large-Scale Methods for Distributionally Robust Optimization NeurIPS 2020 Leverage Score Sampling for Faster Accelerated Regression and ERM ALT 2020 Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond COLT 2020 Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity AISTATS 2020 A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport NeurIPS 2019 A General Framework for Symmetric Property Estimation NeurIPS 2019 Complexity of Highly Parallel Non-Smooth Convex Optimization NeurIPS 2019 Near-optimal method for highly smooth convex optimization COLT 2019 Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives COLT 2019 Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG NeurIPS 2019 Variance Reduction for Matrix Games NeurIPS 2019 Accelerating Stochastic Gradient Descent for Least Squares Regression COLT 2018 Efficient Convex Optimization with Membership Oracles COLT 2018 Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression NeurIPS 2018 Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model NeurIPS 2018 Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification JMLR 2018 “Convex Until Proven Guilty”: Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions ICML 2017 Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis ICML 2016 Faster Eigenvector Computation via Shift-and-Invert Preconditioning ICML 2016 Principal Component Projection Without Principal Component Analysis ICML 2016 Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm COLT 2016 Competing with the Empirical Risk Minimizer in a Single Pass COLT 2015 Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization ICML 2015