Book
- Algorithmic Aspects of Machine Learning (Draft)
Cambridge University Press, Summer 2018
Essays
- Robustness Meets Algorithms Technical Perspective: Jacob Steinhardt
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Communications of the ACM May 2021, Research Highlights
- Learning Topic Models -- Provably and Efficiently Technical Perspective: David Blei
with Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, David Sontag, Yichen Wu and Michael Zhu
Communications of the ACM April 2018, Research Highlights
- Disentangling Gaussians Technical Perspective: Santosh Vempala
with Adam Kalai and Greg Valiant
Communications of the ACM February 2012, Research Highlights
See also this related paper of Belkin and Sinha
Manuscripts
- Precise Error Rates for Computationally Efficient Testing
with Alex Wein
Manuscript, 2023
Papers
- Structure Learning of Hamiltonians from Real-time Evolution
with Ainesh Bakshi, Allen Liu and Ewin Tang
Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), to appear
- Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
with Noah Golowich and Dhruv Rohatgi
Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), to appear
- High-Temperature Gibbs States are Unentangled and Efficiently Preparable
with Ainesh Bakshi, Allen Liu and Ewin Tang
Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), to appear
- The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
with Noah Golowich
Proceedings of the 1st Annual Reinforcement Learning Conference (RLC 2024), to appear
- Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
with Noah Golowich
Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024), to appear
- The Power of an Adversary in Glauber Dynamics
with Byron Chin, Elchanan Mossel and Colin Sandon
Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024), to appear
- Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
with Noah Golowich and Dhruv Rohatgi
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), to appear
- Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
with Ainesh Bakshi, Allen Liu and Ewin Tang
Invited to the SIAM Journal on Computing Special Issue for STOC 2024
Quantum Information Processing (QIP 2024) Invited Plenary
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), to appear
- Provable Benefits of Score Matching
with Chirag Pabbaraju, Anish Sevekari, Holden Lee, Andrej Risteski and Dhruv Rohatgi
Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Spotlight
- Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
with Zongchen Chen, Kuikui Liu and Nitya Mani
Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023)
- Tensor Decompositions Meet Control Theory:
Learning General Mixtures of Linear Dynamical Systems
with Ainesh Bakshi, Allen Liu and Morris Yau
Proceedings of the 40th International Conference on Machine Learning (ICML 2023)
- A New Approach to Learning Linear Dynamical Systems
with Ainesh Bakshi, Allen Liu and Morris Yau
Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)
- Planning and Learning in Partially Observable Systems via Filter Stability
with Noah Golowich and Dhruv Rohatgi
Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)
- Distilling Model Failures as Directions in Latent Space
with Saachi Jain, Hannah Lawrence and Aleksander Madry
The 11th International Conference on Learning Representations (ICLR 2023) Spotlight
- Provably Auditing Ordinary Least Squares in Low Dimensions
with Dhruv Rohatgi
The 11th International Conference on Learning Representations (ICLR 2023)
- From Algorithms to Connectivity and Back: Finding a Giant Component in Random k-SAT
with Zongchen Chen and Nitya Mani
Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
- Robust Voting Rules from Algorithmic Robust Statistics
with Allen Liu
Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
- Learning in Observable POMDPs, without Computationally Intractable Oracles
with Noah Golowich and Dhruv Rohatgi
Advances in Neural Information Processing Systems 35 (NeurIPS 2022)
- Robust Model Selection and Nearly-Proper Learning for GMMs
with Jerry Li and Allen Liu
Advances in Neural Information Processing Systems 35 (NeurIPS 2022)
- Polynomial Time Guarantees for the Burer-Monteiro Method
with Diego Cifuentes
Advances in Neural Information Processing Systems 35 (NeurIPS 2022)
- Minimax Rates for Robust Community Detection
with Allen Liu
Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022)
- Can Q-Learning be Improved with Advice?
with Noah Golowich
Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)
- Learning GMMs with Nearly Optimal Robustness Guarantees
with Allen Liu
Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)
- Kalman Filtering with Adversarial Corruptions
with Sitan Chen, Frederic Koehler and Morris Yau
Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
- A No-go Theorem for Acceleration in the Hyperbolic Plane
with Linus Hamilton
Advances in Neural Information Processing Systems 34 (NeurIPS 2021)
- Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
with Sitan Chen, Frederic Koehler and Morris Yau
Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021)
- Learning to Sample from Censored Markov Random Fields
with Elchanan Mossel and Colin Sandon
Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)
- Settling the Robust Learnability of Mixtures of Gaussians
with Allen Liu
Journal of the ACM, to appear
Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)
- Algorithmic Foundations for the Diffraction Limit
with Sitan Chen
Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)
- Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
with Sitan Chen, Frederic Koehler and Morris Yau
Advances in Neural Information Processing Systems 33 (NeurIPS 2020), Spotlight
- Tensor Completion Made Practical
with Allen Liu
Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
- Learning Structured Distributions from Untrusted Batches: Faster and Simpler
with Sitan Chen and Jerry Li
Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
- Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
with Jonathan Kelner, Frederic Koehler and Raghu Meka
Advances in Neural Information Processing Systems 33 (NeurIPS 2020), Spotlight
- Rigorous Guarantees for Tyler's M-estimator via Quantum Expansion
with Cole Franks
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)
- Parallels Between Phase Transitions and Circuit Complexity?
with Elchanan Mossel and Colin Sandon
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)
- Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation
with Allen Liu
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)
- Efficiently Learning Structured Distributions from Untrusted Batches
with Sitan Chen and Jerry Li
Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC 2020)
- Spectral Methods from Tensor Networks
with Alex Wein
Invited to the SIAM Journal on Computing Special Issue for STOC 2019
Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)
- Learning Restricted Boltzmann Machines via Influence Maximization
with Guy Bresler and Frederic Koehler
Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)
- Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their
Applications
with Sitan Chen
Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)
- How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
with Younhun Kim, Frederic Koehler, Elchanan Mossel and Govind Ramnarayan
Journal of Computational Biology Special Issue for RECOMB 2019
Proceedings of the 23rd Intl. Conference on Research in Computational Molecular Biology (RECOMB 2019)
- The Paulsen Problem Made Simple
with Linus Hamilton
Israel Journal of Mathematics
Proceedings of the 10th Annual Innovations in Theoretical Computer Science (ITCS 2019)
- Improved Bounds for Sampling Colorings via Linear Programming
with Sitan Chen, Michelle Delcourt, Guillem Perarnau and Luke Postle
Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
- Efficiently Learning Mixtures of Mallows Models
with Allen Liu
Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018)
- Optimality and Suboptimality of PCA I: Spiked Random Matrix Models
with Amelia Perry, Alex Wein and Afonso Bandeira
Annals of Statistics, 2018
- Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
- Message-Passing Algorithms for Synchronization Problems over Compact Groups
with Amelia Perry, Alex Wein and Afonso Bandeira
Communications on Pure and Applied Mathematics, 2018
- Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
with Linus Hamilton and Frederic Koehler
Advances in Neural Information Processing Systems 30 (NIPS 2017)
- Learning Determinantal Point Processes with Moments and Cycles
with John Urschel, Victor-Emmanuel Brunel and Philippe Rigollet
Proceedings of the 34th International Conference on Machine Learning (ICML 2017)
- Being Robust (in High Dimensions) Can Be Practical
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Proceedings of the 34th International Conference on Machine Learning (ICML 2017)
- Maximum Likelihood Estimation of Determinantal Point Processes
with Victor-Emmanuel Brunel, Philippe Rigollet and John Urschel
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017)
- Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
Journal of the ACM
Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017)
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
with Boaz Barak, Sam Hopkins, Jonathan Kelner, Pravesh Kothari and Aaron Potechin
SIAM Journal on Computing Special Issue for FOCS 2016
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
- Robust Estimators in High Dimensions without the Computational Intractability
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Invited to Communications of the ACM, Research Highlights
SIAM Journal on Computing Special Issue for FOCS 2016
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
- Provable Algorithms for Inference in Topic Models
with Sanjeev Arora, Rong Ge, Frederic Koehler and Tengyu Ma
Proceedings of the 33rd International Conference on Machine Learning (ICML 2016)
- How Robust are Reconstruction Thresholds for Community Detection?
with Will Perry and Alex Wein
Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016)
- Noisy Tensor Completion via the Sum-of-Squares Hierarchy
with Boaz Barak
Mathematical Programming, Series B Special Issue
Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016)
- Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree
with Boaz Barak, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer and John Wright
Workshop on Approximation, Randomization and Combinatorial Optimization (APPROX 2015)
- Simple, Efficient and Neural Algorithms for Sparse Coding
with Sanjeev Arora, Rong Ge and Tengyu Ma
Proceedings of the 28th Annual Conference on Learning Theory (COLT 2015)
- Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015)
- New Algorithms for Learning Incoherent and Overcomplete Dictionaries
with Sanjeev Arora and Rong Ge
Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014)
- Smoothed Analysis of Tensor Decompositions
with Aditya Bhaskara, Moses Charikar and Aravindan Vijayaraghavan
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)
- A Polynomial Time Approximation Scheme for Fault-tolerant Distributed
Storage
with Constantinos Daskalakis, Anindya De, Ilias Diakonikolas and Rocco Servedio
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
- A Polynomial Time Algorithm for Lossy Population Recovery
with Michael Saks
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
- Algorithms and Hardness for Robust Subspace Recovery
with Moritz Hardt
Proceedings of the 26th Annual Conference on Learning Theory (COLT 2013)
- A Practical Algorithm for Topic Modeling with Provable Guarantees
with Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, David Sontag, Yichen Wu and Michael Zhu
Invited to Communications of the ACM, Research Highlights
Proceedings of the 30th International Conference on Machine Learning (ICML 2013)
- An Information Complexity Approach to Extended Formulations
with Mark Braverman
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013)
- An Almost Optimal Algorithm for Computing Nonnegative Rank
SIAM Journal on Computing
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
- Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
with Sanjeev Arora, Rong Ge and Sushant Sachdeva
Algorithmica Special Issue for Machine Learning
Advances in Neural Information Processing Systems 25 (NIPS 2012)
- Learning Topic Models -- Going Beyond SVD
with Sanjeev Arora and Rong Ge
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
- Computing a Nonnegative Matrix Factorization -- Provably
with Sanjeev Arora, Rong Ge and Ravi Kannan
SIAM Journal on Computing Special Issue for STOC 2012
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)
- Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
with Noga Alon and Benny Sudakov
Journal of the European Mathematical Society
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)
- On Entropy and Extensions of Posets
with Tom Leighton
Manuscript, 2011
- Efficient and Explicit Coding for Interactive Communication
with Ran Gelles and Amit Sahai
IEEE Transactions on Information Theory
Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011)
- Pareto Optimal Solutions for Smoothed Analysts
with Ryan O'Donnell
SIAM Journal on Computing Special Issue for STOC 2011
Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011)
- Dueling Algorithms Related: MIT News
with Nicole Immorlica, Adam Kalai, Brendan Lucier, Andrew Postlewaite and Moshe Tennenholtz
Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011)
- Capacitated Metric Labeling
with Matthew Andrews, Mohammadtaghi Hajiaghayi and Howard Karloff
Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
- Settling the Polynomial Learnability of Mixtures of Gaussians
with Greg Valiant
Invited to Communications of the ACM, Research Highlights
Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)
- Vertex Sparsifiers and Abstract Rounding Algorithms
with Moses Charikar, Tom Leighton and Shi Li
Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)
- Efficiently Learning Mixtures of Two Gaussians
with Adam Kalai and Greg Valiant
Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010)
- Extensions and Limits to Vertex Sparsification
with Tom Leighton
Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010)
- Vertex Sparsification and Oblivious Reductions
SIAM Journal on Computing Special Issue for FOCS 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)
- Some Results on Greedy Embeddings in Metric Spaces
with Tom Leighton
Discrete and Computational Geometry (Invited)
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)
Thesis
- Vertex Sparsification and Universal Rounding Algorithms
George M. Sprowls Award for Best PhD Thesis in Computer Science
Ph.D. Thesis 2011
- A Solution to the Papadimitriou-Ratajczak Conjecture
William A. Martin Memorial Award for Best Master's Thesis in Computer Science
S. M. Thesis 2009