Yuanzhi Li

If the facts don't fit the theory, change the facts - Einstein.  

I'm a PhD student in the Computer Science Department at Princeton University, advised by Sanjeev Arora. Previously I obtained my B.S.E. degree at Tsinghua University.

I am working on Theoretical Machine Learning, in particular, designing efficient, provable algorithms for practical machine learning problems. I am also very interested in convex/non-convex geometry.


$l at princeton.edu, replace $ with my first name.


  • Linear algebraic structure of word senses, with applications to polysemy. With Sanjeev Arora Yingyu Liang, Tengyu Ma and Andrej Risteski. Manuscript
  • Faster Principal Component Regression via Optimal Polynomial Approximation to sgn(x). With Zeyuan Allen-Zhu. Submitted
  • Fast Global Convergence of Online PCA. With Zeyuan Allen-Zhu. Submitted
  • Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition. With Zeyuan Allen-Zhu. Submitted
  • RAND-WALK: a latent variable model approach to word embeddings. With Sanjeev Arora, Yingyu Liang, Tengyu Ma and Andrej Risteski. Accepted to Transactions of the Association for Computational Linguistics (TACL)
  • Even Faster SVD Decomposition Yet Without Agonizing Pain. With Zeyuan Allen-Zhu. NIPS 2016
  • Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods. With Andrej Risteski. NIPS 2016
  • Tight algorithms and lower bounds for approximately convex optimization. With Andrej Risteski. NIPS 2016
  • Non-negative matrix factorization using a decode-and-update approach. With Yingyu Liang and Andrej Risteski. NIPS 2016
  • Recovery guarantee of weighted low-rank approximation via alternating minimization. With Yingyu Liang and Andrej Risteski. ICML 2016
  • A Theoretical Analysis of NDCG Ranking Measures. With Yining Wang, Liwei Wang, Di He, Wei Chen and Tie-Yan Liu. COLT 2013
  • ...
  • Teaching

  • COS423: Theory of Algorithms, Fall 2016. TA
  • COS521: Advance algorithm design, Spring 2016. TA