Aaron Sidford

Reusing Samples in Variance Reduction ALT 2026 Convex optimization with $p$-norm oracles ALT 2026 Truncated Variance Reduced Value Iteration NIPS 2024 Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting NIPS 2024 Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract) COLT 2024 Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization COLT 2024 Moments, Random Walks, and Limits for Spectrum Approximation COLT 2023 Quantum speedups for stochastic optimization NIPS 2023 Structured Semidefinite Programming for Recovering Structured Preconditioners NIPS 2023 Towards Optimal Effective Resistance Estimation NIPS 2023 Parallel Submodular Function Minimization NIPS 2023 Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract) IJCAI 2023 Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling ICML 2023 Semi-Random Sparse Recovery in Nearly-Linear Time COLT 2023 Optimal and Adaptive Monteiro-Svaiter Acceleration NIPS 2022 Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales COLT 2022 Efficient Convex Optimization Requires Superlinear Memory COLT 2022 RECAPP: Crafting a More Efficient Catalyst for Convex Optimization ICML 2022 On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood NIPS 2022 Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods COLT 2022 Stochastic Bias-Reduced Gradient Methods NIPS 2021 Towards Tight Bounds on the Sample Complexity of Average-reward MDPs ICML 2021 Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss COLT 2021 The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood COLT 2021 Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity AISTATS 2020 Large-Scale Methods for Distributionally Robust Optimization NIPS 2020 Acceleration with a Ball Optimization Oracle NIPS 2020 Instance Based Approximations to Profile Maximum Likelihood NIPS 2020 Leverage Score Sampling for Faster Accelerated Regression and ERM ALT 2020 Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond COLT 2020 Efficiently Solving MDPs with Stochastic Mirror Descent ICML 2020 Near-optimal method for highly smooth convex optimization COLT 2019 A General Framework for Symmetric Property Estimation NIPS 2019 Variance Reduction for Matrix Games NIPS 2019 Complexity of Highly Parallel Non-Smooth Convex Optimization NIPS 2019 Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG NIPS 2019 A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport NIPS 2019 Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives COLT 2019 Efficient Convex Optimization with Membership Oracles COLT 2018 Accelerating Stochastic Gradient Descent for Least Squares Regression COLT 2018 Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression NIPS 2018 Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model NIPS 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 Principal Component Projection Without Principal Component Analysis ICML 2016 Faster Eigenvector Computation via Shift-and-Invert Preconditioning ICML 2016 Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation 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