Yu Cheng

  • Home
  • Research
  • Misc
Yu Cheng

I am an assistant professor in the Department of Computer Science at Brown University, where I am part of the theory group.


I received my Ph.D. from the University of Southern California, advised by Shang-Hua Teng. I was a postdoc at Duke University, a visiting member at the Institute for Advanced Study, and an assistant professor at the University of Illinois Chicago.

My Research: My main research interests include machine learning, optimization, and game theory. My recent work focuses on the design and analysis of scalable and provably robust algorithms for machine learning, especially in the areas of high-dimensional robust statistics, non-convex optimization, and learning with strategic agents.

Email: yu_cheng AT brown.edu

Office: CIT 413, 115 Waterman St, Providence, RI 02906.

My CV and papers (by date or by topic).

Teaching

  • Spring 2027: CSCI 2952Q: Robust Algorithms for Machine Learning.
  • Fall 2026: CSCI 0500: Data Structures, Algorithms, and Intractability: An Introduction.
  • Fall 2025: CSCI 0500: Data Structures, Algorithms, and Intractability: An Introduction.
  • Spring 2025: CSCI 1520: Algorithmic Aspects of Machine Learning.
  • Fall 2024: CSCI 2952Q: Robust Algorithms for Machine Learning.
  • Spring 2024: CSCI 1952Q: Algorithmic Aspects of Machine Learning.
  • Fall 2023: CSCI 2952Q: Robust Algorithms for Machine Learning.
  • Spring 2023: CSCI 1952Q: Algorithmic Aspects of Machine Learning.
  • Fall 2022: CSCI 2952Q: Robust Algorithms for Machine Learning.
  • Fall 2021: MCS 401: Computer Algorithms I.
  • Fall 2021: MCS 425: Codes and Cryptography.
  • Fall 2020: MCS 401: Computer Algorithms I.
  • Fall 2020: MCS 425: Codes and Cryptography.
  • Spring 2020: MCS 425: Codes and Cryptography.
  • Spring 2020: MCS 590: Spectral Graph Theory.

Research Group

Ph.D. Students
Hrithik Nambiar (co-advised with Amy Greenwald)
Natanon Therdpraisan (co-advised with Ellis Hershkowitz)
Binhao Chen
Undergraduate Students
Gabriel Chen
Alice Wang
Former Ph.D. Students
Xing Gao (co-advised with Lev Reyzin)
Former Undergraduate Students
Tianle Jiang
Jay Sarva
Haichen Dong
Honghao Lin

Publications

Papers labeled (α-β) indicate equal contribution with authors ordered alphabetically.

  1. Robust Gaussian Covariance Estimation via Nonconvex Optimization.
    (α-β) Binhao Chen, Yu Cheng, Rong Ge, Jay Sarva.
  2. Outlier-Robust Phase Retrieval in Nearly-Linear Time.
    (α-β) Yu Cheng, Haichen Dong, Rong Ge, Alessio Mazzetto.
  3. How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
    (α-β) Yu Cheng, Tianle Jiang.
  4. Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion.
    (α-β) Gabriel Chen, Yu Cheng, Alice Wang. SOSA 2027.
  5. On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Tianle Jiang, Pachara Sawettamalya, Huacheng Yu. ESA 2026.
  6. Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization.
    Xing Gao, Binhao Chen, Yu Cheng. AISTATS 2026.
  7. Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction. (arXiv)
    Yixuan Even Xu, Hanrui Zhang, Yu Cheng, Vincent Conitzer. NeurIPS 2024.
  8. Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. (arXiv)
    (α-β) Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang. PODS 2024.
  9. Robust Matrix Sensing in the Semi-Random Model.
    Xing Gao, Yu Cheng. NeurIPS 2023.
  10. Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing. (arXiv)
    Shuyao Li, Yu Cheng, Ilias Diakonikolas, Jelena Diakonikolas, Rong Ge, Stephen J. Wright. NeurIPS 2023.
  11. Hiding Data Helps: On the Benefits of Masking for Sparse Coding. (arXiv)
    Muthu Chidambaram, Chenwei Wu, Yu Cheng, Rong Ge. ICML 2023.
  12. Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation. (arXiv)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. EC 2023.
  13. Outlier-Robust Sparse Estimation via Non-Convex Optimization. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge, Shivam Gupta, Daniel M. Kane, Mahdi Soltanolkotabi. NeurIPS 2022.
  14. Efficient Algorithms for Planning with Participation Constraints. (arXiv)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. EC 2022.
  15. Planning with Participation Constraints. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2022.
  16. Sparsification of Directed Graphs via Cut Balance. (arXiv)
    (α-β) Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, Kevin Sun. ICALP 2021.
  17. Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time. (arXiv)
    (α-β) Yu Cheng, Honghao Lin. ICLR 2021.
  18. Fair for All: Best-effort Fairness Guarantees for Classification. (arXiv)
    Anilesh K. Krishnaswamy, Zhihao Jiang, Kangning Wang, Yu Cheng, Kamesh Munagala. AISTATS 2021.
  19. Classification with Few Tests through Self-Selection. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2021.
  20. Automated Mechanism Design for Classification with Partial Verification. (arXiv)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2021.
  21. High-Dimensional Robust Mean Estimation via Gradient Descent. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge, Mahdi Soltanolkotabi. ICML 2020.
  22. Distinguishing Distributions When Samples Are Strategically Transformed. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. NeurIPS 2019.
  23. Group Fairness in Committee Selection. (arXiv)
    (α-β) Yu Cheng, Zhihao Jiang, Kamesh Munagala, Kangning Wang. EC 2019.
  24. Faster Algorithms for High-Dimensional Robust Covariance Estimation. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff. COLT 2019.
  25. When Samples Are Strategically Selected. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. ICML 2019.
  26. A Better Algorithm for Societal Tradeoffs. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2019.
  27. High-Dimensional Robust Mean Estimation in Nearly-Linear Time. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge. SODA 2019.
  28. A Simple Mechanism for a Budget-Constrained Buyer. (arXiv)
    (α-β) Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang. WINE 2018 (Best Paper Award).
  29. Robust Learning of Fixed–Structure Bayesian Networks. (arXiv)
    (α-β) Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. NeurIPS 2018.
  30. Non-Convex Matrix Completion Against a Semi-Random Adversary. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Rong Ge. COLT 2018.
  31. A Deterministic Protocol for Sequential Asymptotic Learning. (arXiv)
    (α-β) Yu Cheng, Wade Hann-Caruthers, Omer Tamuz. ISIT 2018.
  32. On the Distortion of Voting with Multiple Representative Candidates. (arXiv, slides)
    (α-β) Yu Cheng, Shaddin Dughmi, David Kempe. AAAI 2018.
  33. Computational Aspects of Optimal Information Revelation. (pdf, slides, talk video)
    Yu Cheng. Ph.D. Thesis. University of Southern California, 2017.
  34. Of the People: Voting Is More Effective with Representative Candidates. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Shaddin Dughmi, David Kempe. EC 2017.
  35. Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. (arXiv, slides, talk video)
    (α-β) Xi Chen, Yu Cheng, Bo Tang. ITCS 2017.
  36. Playing Anonymous Games Using Simple Strategies. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Alistair Stewart. SODA 2017.
  37. On the Recursive Teaching Dimension of VC Classes. (ECCC, talk video)
    (α-β) Xi Chen, Yu Cheng, Bo Tang. NIPS 2016.
  38. Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games. (arXiv, slides)
    (α-β) Umang Bhaskar, Yu Cheng, Young Kun Ko, Chaitanya Swamy. EC 2016.
  39. Mixture Selection, Mechanism Design, and Signaling (arXiv, slides, talk video)
    (α-β) Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng. FOCS 2015.
  40. Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification (arXiv Part I and Part II, slides)
    (α-β) Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng. COLT 2015.