vix.ing · top · new · best · stats · spec

Aaron Sidford

  1. Principal Component Projection Without Principal Component Analysis
    2016/02/22 by Roy Frostig, Frostig, Roy, Cameron Musco +5 · 1 voice · 1 citation
    Computer Science · Mathematics · #Matrix Theory and Algorithms #Tensor decomposition and applications #Stochastic Gradient Optimization Techniques
  2. Lower bounds for finding stationary points I
    2019/06/07 by Yair Carmon, John C. Duchi, Oliver Hinder +1 · 25 citations
    Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs
  3. "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient\n Descent on Non-Convex Functions
    2017/05/08 by Yair Carmon, Carmon, Yair, Oliver Hinder +5 · 15 citations
    Medicine · Engineering · #Bone and Joint Diseases #Sparse and Compressive Sensing Techniques #Glioma Diagnosis and Treatment
  4. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
    2023/09/28 by Jan van den Brand, Brand, Jan van den, Li Chen +13 · 18 citations
    Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods #Advanced Graph Theory Research
  5. Large-Scale Methods for Distributionally Robust Optimization
    2020/10/12 by Daniel Lévy, Levy, Daniel, Yair Carmon +5 · 9 citations
    Business, Management and Accounting · Decision Sciences · Engineering · #Advanced Control Systems Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Supply Chain and Inventory Management
  6. Efficient Inverse Maintenance and Faster Algorithms for Linear\n Programming
    2015/03/05 by Yin Tat Lee, Aaron Sidford, Lee, Yin Tat +1 · 7 citations
    Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
  7. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected\n Graphs, and its Multicommodity Generalizations
    2013/04/08 by Jonathan A. Kelner, Kelner, Jonathan A., Yin Tat Lee +5 · 6 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
  8. Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
    2019/06/27 by Oliver Hinder, Hinder, Oliver, Aaron Sidford +3 · 7 citations
    Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  9. Geometric Median in Nearly Linear Time
    2016/06/16 by Michael B. Cohen, Yin Tat Lee, Cohen, Michael B. +7 · 6 citations
    Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Point processes and geometric inequalities
  10. Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
    2020/09/03 by Jan van den Brand, Brand, Jan van den, Yin-Tat Lee +13 · 8 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
  11. Optimal and Adaptive Monteiro-Svaiter Acceleration
    2022/05/30 by Yair Carmon, Danielle Hausler, Carmon, Yair +7 · 8 citations
    Mathematics · Engineering · Computer Science · #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques #Matrix Theory and Algorithms
  12. Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
    2021/12/01 by Jan van den Brand, Yu Gao, Brand, Jan van den +11 · 8 citations
    Computer Science · #Adversarial Robustness in Machine Learning #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data
  13. Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
    2017/10/27 by Aaron Sidford, Sidford, Aaron, Mengdi Wang +5 · 6 citations
    Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reinforcement Learning in Robotics
  14. Single Pass Spectral Sparsification in Dynamic Streams
    2014/07/04 by Michael Kapralov, Yin Tat Lee, Kapralov, Michael +7 · 5 citations
    Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs
  15. Un-regularizing: approximate proximal point and faster stochastic\n algorithms for empirical risk minimization
    2015/06/24 by Roy Frostig, Rong Ge, Frostig, Roy +5 · 6 citations
    Computer Science · Decision Sciences · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Risk and Portfolio Optimization #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  16. Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
    2021/06/13 by Yujia Jin, Aaron Sidford, Jin, Yujia +1 · 6 citations
    Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems #Reinforcement Learning in Robotics
  17. Complexity of Highly Parallel Non-Smooth Convex Optimization
    2019/06/25 by Sébastien Bubeck, Bubeck, Sébastien, Qijia Jiang +7 · 4 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  18. Faster Algorithms for Computing the Stationary Distribution, Simulating\n Random Walks, and More
    2016/08/10 by Michael B. Cohen, Cohen, Michael B., Jon Kelner +9 · 3 citations
    Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Graph theory and applications #Quantum Computing Algorithms and Architecture
  19. Subquadratic Submodular Function Minimization
    2016/10/31 by Deeparnab Chakrabarty, Chakrabarty, Deeparnab, Yin Tat Lee +5 · 3 citations
    Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques
  20. Solving Tall Dense Linear Programs in Nearly Linear Time
    2020/02/06 by Jan van den Brand, Yin Tat Lee, Brand, Jan van den +5 · 5 citations
    Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs
  21. Near-optimal method for highly smooth convex optimization
    2018/12/19 by Sébastien Bubeck, Bubeck, Sébastien, Qijia Jiang +7 · 3 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  22. ReSQueing Parallel and Private Stochastic Convex Optimization
    2023/01/01 by Yair Carmon, Arun Jambulapati, Carmon, Yair +11 · 4 citations
    Computer Science · Engineering · Mathematics · #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  23. Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
    2016/02/22 by Prateek Jain, Jain, Prateek, Chi Jin +7 · 2 citations
    Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural and Evolutionary Computing (cs.NE) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  24. Efficient Convex Optimization with Membership Oracles
    2017/06/22 by Yin Tat Lee, Lee, Yin Tat, Aaron Sidford +3 · 2 citations
    Computer Science · Decision Sciences · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Bandit Algorithms Research
  25. Improved Lower Bounds for Submodular Function Minimization
    2022/07/09 by Deeparnab Chakrabarty, Chakrabarty, Deeparnab, Andrei Graur +5 · 3 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)
  26. Stochastic Bias-Reduced Gradient Methods
    2021/06/17 by Hilal Asi, Asi, Hilal, Yair Carmon +7 · 3 citations
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  27. Faster Matroid Intersection
    2019/11/25 by Deeparnab Chakrabarty, Yin Tat Lee, Chakrabarty, Deeparnab +7 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  28. Faster Eigenvector Computation via Shift-and-Invert Preconditioning
    2016/05/26 by Dan Garber, Garber, Dan, Elad Hazan +11 · 3 citations
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  29. Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
    2018/10/04 by AmirMahdi Ahmadinejad, Arun Jambulapati, Ahmadinejad, AmirMahdi +5 · 2 citations
    Computer Science · Mathematics · #Advanced Graph Neural Networks #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Optimization and Control (math.OC)
  30. Faster Divergence Maximization for Faster Maximum Flow
    2020/03/19 by Yang P. Liu, Liu, Yang P., Aaron Sidford +1 · 3 citations
    Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Commutative Algebra and Its Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation
  31. Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
    2023/01/31 by AmirMahdi Ahmadinejad, John Peebles, Ahmadinejad, AmirMahdi +7 · 3 citations
    Mathematics · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Quantum optics and atomic interactions #Random Matrices and Applications
  32. Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
    2021/05/04 by Yair Carmon, Arun Jambulapati, Carmon, Yair +5 · 2 citations
    Computer Science · Decision Sciences · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Probability and Risk Models #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques
  33. A Simple, Combinatorial Algorithm for Solving SDD Systems in\n Nearly-Linear Time
    2013/01/28 by Jonathan A. Kelner, Lorenzo Orecchia, Kelner, Jonathan A. +5 · 1 citation
    Computer Science · Mathematics · #Matrix Theory and Algorithms #Advanced Optimization Algorithms Research #Graph Theory and Algorithms
  34. Path Finding I :Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves
    2013/12/23 by Yin Tat Lee, Lee, Yin Tat, Aaron Sidford +1 · 1 citation
    Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Polynomial and algebraic computation
  35. Matrix Completion in Almost-Verification Time
    2023/08/07 by Jonathan A. Kelner, Kelner, Jonathan A., Jerry Li +7 · 2 citations
    Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Blind Source Separation Techniques
  36. Quantum speedups for stochastic optimization
    2023/08/03 by Aaron Sidford, Chenyi Zhang, Sidford, Aaron +1 · 3 citations
    Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
  37. Sparsifying generalized linear models
    2023/11/29 by Arun Jambulapati, James R. Lee, Jambulapati, Arun +5 · 2 citations
    Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Optimization and Mathematical Programming #Sparse and Compressive Sensing Techniques
  38. Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
    2019/08/29 by Aaron Sidford, Mengdi Wang, Sidford, Aaron +5 · 1 citation
    Computer Science · Decision Sciences · #Adversarial Robustness in Machine Learning #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics
  39. Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
    2024/06/11 by Arun Jambulapati, Jambulapati, Arun, Aaron Sidford +3 · 3 citations
    Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
  40. Leverage Score Sampling for Faster Accelerated Regression and ERM
    2017/11/22 by Naman Agarwal, Sham M. Kakade, Agarwal, Naman +9 · 2 citations
    Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Matrix Theory and Algorithms
  41. Accelerated Methods for Non-Convex Optimization
    2016/11/02 by Yair Carmon, Carmon, Yair, John C. Duchi +5 · 2 citations
    Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  42. Coordinate Methods for Matrix Games
    2020/09/17 by Yair Carmon, Carmon, Yair, Yujia Jin +5 · 2 citations
    Computer Science · Decision Sciences · Mathematics · #Stochastic Gradient Optimization Techniques #Advanced Bandit Algorithms Research #Markov Chains and Monte Carlo Methods
  43. Semi-Random Sparse Recovery in Nearly-Linear Time
    2022/03/08 by Jonathan A. Kelner, Kelner, Jonathan A., Jerry Li +7 · 1 citation
    Computer Science · Engineering · Medicine · #Advanced MRI Techniques and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  44. Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
    2016/04/13 by Rong Ge, Ge, Rong, Chi Jin +7 · 1 citation
    Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Topological and Geometric Data Analysis
  45. Truncated Variance Reduced Value Iteration
    2024/05/21 by Yujia Jin, Jin, Yujia, Ishani Karmarkar +5 · 2 citations
    Computer Science · #Neural Networks and Applications
  46. Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
    2024/06/11 by Yujia Jin, Ishani Karmarkar, Jin, Yujia +7 · 1 citation
    Physics and Astronomy · #Atomic and Subatomic Physics Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Nuclear Physics and Applications #Radiation Detection and Scintillator Technologies
  47. Eulerian Graph Sparsification by Effective Resistance Decomposition
    2024/08/19 by Arun Jambulapati, Sushant Sachdeva, Jambulapati, Arun +7 · 2 citations
    Computer Science · #Advanced Graph Neural Networks #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms
  48. A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions
    2023/11/17 by Yair Carmon, Carmon, Yair, Arun Jambulapati +5 · 1 citation
    Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques