• Home
• PUBLICATIONS
• GROUP MEMBERS
  
• SOFTWARE
  
• Useful Links
  

Please also check our google scholar pages and arxiv for latest works

2019

• On Exact Computation with an Infinitely Wide Neural Net. NeurIPS 2019 spotlight (Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang)
• Implicit Regularization in Deep Matrix Factorization. NeurIPS 2019 spotlight (Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo)
• Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets. NeurIPS 2019 (Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Sanjeev Arora, Rong Ge)
• Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle. NeruIPS 2019 (Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang)
  
• Online Sampling from Log-Concave Distributions. NeurIPS 2019 (Holden Lee, Oren Mangoubi, Nisheeth K. Vishnoi)
• A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML 2019 (Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, Nikunj Saunshi)
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. ICML 2019 (Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang)
  
• Width Provably Matters in Optimization for Deep Linear Neural Networks. ICML 2019 (Simon S. Du, Wei Hu)
• Efficient Full-Matrix Regularization. ICML 2019 (Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, Yi Zhang)
  
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks. ICLR 2019 (Sanjeev Arora, Nadav Cohen, Noah Golowich, Wei Hu)
• Theoretical Analysis of Auto Rate-Tuning by Batch Normalization. ICLR 2019 (Sanjeev Arora, Zhiyuan Li, Kaifeng Lyu)
  
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks. ICLR 2019 (Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LuCun, Nathan Srebro)
• Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees. ICLR 2019 (Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, Tengyu Ma)
  
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity. AISTATS 2019 (Simon S. Du, Wei Hu)
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. (Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, Dingli Yu)
  
• A Simple Saliency Method That Passes the Sanity Checks. (Arushi Gupta, Sanjeev Arora)
• Learning Self-Correctable Policies and Value Functions from Demonstrations with Negative Sampling. (Yuping Luo, Huazhe Xu, Tengyu Ma)
  
• Calibration, Entropy Rates, and Memory in Language Models. (Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang)
  
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee. (Wei Hu, Zhiyuan Li, Dingli Yu)
• Extreme Tensoring for Low-Memory Preconditioning. (Xinyi Chen, Naman Agarwal, Elad Hazan, Cyril Zhang, Yi Zhang)
  

2018

• Spectral Filtering for General Linear Dynamical Systems. NeurIPS 2018 oral (Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang)
  
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced. NeurIPS 2018 (Simon S. Du, Wei Hu, Jason D. Lee) (Best paper at ICML 2018 Workshop on Nonconvex Optimization)
  
• Online Improper Learning with an Approximation Oracle. NeurIPS 2018 (Elad Hazan, Wei Hu, Yuanzhi Li, Zhiyuan Li)
  
• Neon2: Finding Local Minima via First-Order Oracles. NeurIPS 2018 (Zeyuan Allen-Zhu, Yuanzhi Li)
• A La Carte Embedding: Cheap but Effective Induction of Semantic Feature Vectors. ACL 2018 (Mikhail Khodak, Nikunj Saunshi, Yingyu Liang, Tengyu Ma, Brandon Stewart, Sanjeev Arora)
  
• An Analysis of the t-SNE Algorithm for Data Visualization. COLT 2018 (Sanjeev Arora, Wei Hu, Pravesh K. Kothari)
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations. COLT 2018 (Yuanzhi Li, Tengyu Ma, Hongyang Zhang) (Best paper)
• Learning Mixtures of Linear Regressions with Nearly Optimal Complexity. COLT 2018 (Yuanzhi Li, Yingyu Liang)
• The Well Tempered Lasso. ICML 2018 (Yuanzhi Li, Yoram Singer)
  
• Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits. ICML 2018 (Zeyuan Allen-Zhu, Sebastien Bubeck, Yuanzhi Li)
  
• An Alternative View: When Does SGD Escape Local Minima? ICML 2018 (Robert Kleinberg, Yuanzhi Li, Yang Yuan)
  
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization. ICML 2018 (Sanjeev Arora, Nadav Cohen, Elad Hazan)
  
• Stronger Generalization Bounds for Deep Nets via a Compression Approach. ICML 2018 (Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang)
  
• A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs. ICLR 2018 (Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, Kiran Vodrahalli)
  
• Not-So-Random Features. ICLR 2018 (Brian Bullins, Cyril Zhang, Yi Zhang)
• Do GANs Learn the Distribution? Some Theory and Empirics. ICLR 2018 (Sanjeev Arora, Andrej Risteski, Yi Zhang)
  
• Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing. STOC 2018 (Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, Avi Wigderson)
  
• An homotopy method for Lp regression provably beyond self-concordance and in input-sparsity time. STOC 2018 (Sebastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li)
  
• Sparsity, variance and curvature in multi-armed bandits. ALT 2018 (Sebastien Bubeck, Michael B. Cohen, Yuanzhi Li)
  
• An Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model. SODA 2018 (Xi Chen, Yuanzhi Li, Jieming Mao)
• Linear Algebraic Structure of Word Senses, with Applications to Polysemy. TACL 2018 (Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski)
• Gradient Descent Learns Linear Dynamical Systems. JLMR, 19(29):1−44, 2018. (Moritz Hardt, Tengyu Ma, Benjamin Recht)

2017

• Convergence Analysis of Two-layer Neural Networks with ReLU Activation. NIPS 2017 (Yuanzhi Li, Yang Yuan)
  
• On the Optimization Landscape of Tensor decompositions. NIPS 2017 (Rong Ge, Tengyu Ma) (Best paper in the NIPS 2016 Workshop on Nonconvex Optimization for Machine Learning: Theory and Practice)
• Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls. NIPS 2017 spotlight (Zeyuan Allen-Zhu, Elad Hazan, Wei Hu, Yuanzhi Li)
• Much Faster Algorithms for Matrix Scaling. FOCS 2017 (Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, Avi Wigderson)
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate. FOCS 2017 (Zeyuan Allen-Zhu, Yuanzhi Li)
  
• Generalization and Equilibrium in Generative Adversarial Nets (GANs). ICML 2017 (Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, Yi Zhang)
• Near-Optimal Design of Experiments via Regret Minimization. ICML 2017 (Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, Yining Wang)
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster Matrix Multiplicative Weight Updates. ICML 2017 (Zeyuan Allen-Zhu, Yuanzhi Li)
• Faster Principal Component Regression and Stable Matrix Chebyshev Approximation. ICML 2017 (Zeyuan Allen-Zhu, Yuanzhi Li)
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition. ICML 2017 (Zeyuan Allen-Zhu, Yuanzhi Li)
  
• Differentially Private Clustering in High-Dimensional Euclidean Spaces. ICML 2017 (Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, Hongyang Zhang)
• Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations. ICML 2017 (Yuanzhi Li, Yingyu Liang)
• Provable Learning of Noisy-or Networks. STOC 2017 (Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski)
• A Simple but Tough-to-Beat Baseline for Sentence Embeddings. ICLR 2017 (Sanjeev Arora, Yingyu Liang, Tengyu Ma)
• Identity Matters in Deep Learning. ICLR 2017 (Moritz Hardt, Tengyu Ma)
• Diverse Neural Network Learns True Target Functions. AISTAT 2017 (Bo Xie, Yingyu Liang, Le Song)
  
• Mapping Between Natural Movie fMRI Responses and Word-Sequence Representations. Neuroimage 2017 (Kiran Vodrahalli, Po-Hsuan Chen, Yingyu Liang, Janice Chen, Esther Yong, Christopher Honey, Peter Ramadge, Ken Norman, Sanjeev Arora)
  

2016

• RAND-WALK: A latent variable generative model approach to word embeddings. TACL 2016 (Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski)
• A Non-generative Framework and Convex Relaxations for Unsupervised Learning. NIPS 2016 (Elad Hazan, Tengyu Ma)
  
• Matrix Completion has No Spurious Local Minimum. NIPS 2016 (Rong Ge, Jason Lee, Tengyu Ma) (Best Student Paper)
  
• Polynomial-time Tensor Decompositions with Sum-of-squares. FOCS 2016 (Tengyu Ma, Jonathan Shi, David Steurer)
  
• Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality. STOC 2016 (Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff)
  
• LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain. NIPS 2016 (Zeyuan Allen-Zhu, Yuanzhi Li)
  
• Algorithms and Matching Lower Bounds for Approximately-Convex Optimization. NIPS 2016 (Yuanzhi Li, Andrej Risteski)
  
• Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods. NIPS 2016 (Yuanzhi Li, Andrej Risteski)
  
• Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates. NIPS 2016 (Yingyu Liang, Yuanzhi Li, Andrej Risteski)
  
• Communication-Efficient Distributed Kernel Principal Component Analysis. KDD 2016 (Maria-Florina Balcan, Yingyu Liang, Le Song, David Woodruff, Bo Xie)
  
• On routing disjoint paths in bounded treewidth graphs. SWAT 2016 (Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski)
  
• How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods. COLT 2016 (Andrej Risteski)
  
• Simple, Efficient, and Neural Algorithms for Sparse Coding. COLT 2016 (Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra. )
  
• Recovery Guarantee of Weighted Low-Rank Approximation via Alternating Minimization. ICML 2016 (Yingyu Liang, Yuanzhi Li, Andrej Risteski)
  
• Provable Algorithms for Inference in Topic Models. ICML 2016 (Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra)
  
• Scalable Influence Maximization for Multiple Products in Continuous-Time Diffusion Networks. JMLR 2016 (Nan Du, Yingyu Liang, Maria-Florina Balcan, Manuel Gomez-Rodriguez, Hongyuan zha, Le Song)
  
• Clustering Under Perturbation Resilience. SICOMP 2016 (Maria-Florina Balcan, Yingyu Liang)
  

2015

• Why are deep nets reversible: A simple theory, with implications for training. (Sanjeev Arora, Yingyu Liang, Tengyu Ma)
  
• Online Learning of Eigenvectors. ICML 2015 (Dan Garber, Elad Hazan, Tengyu Ma)
  
• Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms. RANDOM/APPROX 2015 (Rong Ge, Tengyu Ma)
  
• Label optimal regret bounds for online local learning. COLT 2015 (Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski)
  
• Simple, efficient and neural algorithms for sparse coding. COLT 2015 (Sanjeev Arora, Rong Ge, Ankur Moitra)
  
• Sum-of-Squares Lower Bounds for Sparse PCA. NIPS 2015 (Tengyu Ma, Avi Wigderson)
  
• On some provably correct cases of variational inference for topic models. NIPS 2015 (Pranjal Awasthi, Andrej Risteski)
  
• Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients. NIPS 2015 (Bo Xie, Yingyu Liang, Le Song)
  
• Distributed Frank-Wolfe Algorithm: A Unified Framework for Communication-Efficient Sparse Learning. SDM 2015 (Aurelien Bellet, Yingyu Liang, Alireza Bagheri Garakani, Maria-Florina Balcan, Fei Sha)
  

2014

• Provable bounds for learning some deep representations. ICML 2014. (Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma.)
  
• New algorithms for learning overcomplete and incoherent dictionaries. COLT 2014 (Sanjeev Arora, Rong Ge, Ankur Moitra)
  
• On Communication Cost of Distributed Statistical Estimation and Dimensionality. NIPS 2014 (Ankit Garg, Tengyu Ma, Huy Nguyen)
  
• Skeletal rigidity of phylogenetic trees. DAM 2014 (Howard Cheng, Satyan L. Devadoss, Brian Li, Andrej Risteski)
  
• Robust Hierarchical Clustering. JMLR 2014 (Maria-Florina Balcan, Yingyu Liang)
  
• Scalable Kernel Methods via Doubly Stochastic Gradients. NIPS 2014 (Bo Dai, Xie Dai, Niao He, Yingyu Liang, Anant Raj, Maria-Florina Balcan, Le Song)
  
• Learning Time-Varying Coverage Functions. NIPS 2014 (Nan Du, Yingyu Liang, Maria-Florina Balcan, and Le Song)
  
• Improved Distributed Principal Component Analysis. NIPS 2014 (Maria-Florina Balcan, Yingyu Liang, Vandana Kanchanapally, David Woodruff)
  
• Influence Function Learning in Information Diffusion Networks. ICML 2014 (Nan Du, Yingyu Liang, Maria-Florina Balcan, Le Song)
  

2013

• A practical algorithm for topic modeling with provable guarantees. ICML 2013 (Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, Yichen Wu, Michael Zhu)
  
• Distributed k-Means and k-Median Clustering on General Topologies. NIPS 2013 (Maria-Florina Balcan, Steven Ehrlich, Yingyu Liang)
  
• Modeling and Detecting Community Hierarchies. SIMBAD 2013 (Maria-Florina Balcan, Yingyu Liang)
  
• Efficient Semi-supervised and Active Learning of Disjunctions. ICML 2013 (Maria-Florina Balcan, Christopher Berlind, Yingyu Liang, Steven Ehrlich)
  

2012

• Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. NIPS 2012 (Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva)
• Learning topic models: going beyond SVD. FOCS 2012 (Sanjeev Arora, Rong Ge, Ankur Moitra)
• Finding overlapping communities in a social network: towards a rigorous approach. EC 2012 (Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck)
• Computing a Nonnegative Matrix Factorization: Provably. STOC 2012 (Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra.)