Yu Cheng

  • Home
  • Research
  • Misc

Publications by topic

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

Machine Learning

High-Dimensional Robust Statistics:

  • Robust Gaussian Covariance Estimation via Nonconvex Optimization.
    (α-β) Binhao Chen, Yu Cheng, Rong Ge, Jay Sarva.
  • Outlier-Robust Phase Retrieval in Nearly-Linear Time.
    (α-β) Yu Cheng, Haichen Dong, Rong Ge, Alessio Mazzetto.
  • 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.
  • Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time. (arXiv)
    (α-β) Yu Cheng, Honghao Lin. ICLR 2021.
  • High-Dimensional Robust Mean Estimation via Gradient Descent. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge, Mahdi Soltanolkotabi. ICML 2020.
  • Faster Algorithms for High-Dimensional Robust Covariance Estimation. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff. COLT 2019.
  • High-Dimensional Robust Mean Estimation in Nearly-Linear Time. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Rong Ge. SODA 2019.
  • Robust Learning of Fixed–Structure Bayesian Networks. (arXiv)
    (α-β) Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. NeurIPS 2018.

Non-Convex Optimization:

  • Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization.
    Xing Gao, Binhao Chen, Yu Cheng. AISTATS 2026.
  • Robust Matrix Sensing in the Semi-Random Model.
    Xing Gao, Yu Cheng. NeurIPS 2023.
  • 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.
  • Non-Convex Matrix Completion Against a Semi-Random Adversary. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Rong Ge. COLT 2018.

Strategic Aspects of Learning:

  • Efficient Algorithms for Planning with Participation Constraints. (arXiv)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. EC 2022.
  • Planning with Participation Constraints. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2022.
  • Classification with Few Tests through Self-Selection. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2021.
  • Automated Mechanism Design for Classification with Partial Verification. (arXiv)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2021.
  • Distinguishing Distributions When Samples Are Strategically Transformed. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. NeurIPS 2019.
  • When Samples Are Strategically Selected. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. ICML 2019.
  • A Deterministic Protocol for Sequential Asymptotic Learning. (arXiv)
    (α-β) Yu Cheng, Wade Hann-Caruthers, Omer Tamuz. ISIT 2018.

Other Topics:

  • Hiding Data Helps: On the Benefits of Masking for Sparse Coding. (arXiv)
    Muthu Chidambaram, Chenwei Wu, Yu Cheng, Rong Ge. ICML 2023.
  • On the Recursive Teaching Dimension of VC Classes. (ECCC, talk video)
    (α-β) Xi Chen, Yu Cheng, Bo Tang. NIPS 2016.
  • 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.

Game Theory

Mechanism Design and Signaling:

  • A Simple Mechanism for a Budget-Constrained Buyer. (arXiv)
    (α-β) Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang. WINE 2018 (Best Paper Award).
  • 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.
  • 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.

Fairness and Social Choice:

  • Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion.
    (α-β) Gabriel Chen, Yu Cheng, Alice Wang. SOSA 2027.
  • Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction. (arXiv)
    Yixuan Even Xu, Hanrui Zhang, Yu Cheng, Vincent Conitzer. NeurIPS 2024.
  • Fair for All: Best-effort Fairness Guarantees for Classification. (arXiv)
    Anilesh K. Krishnaswamy, Zhihao Jiang, Kangning Wang, Yu Cheng, Kamesh Munagala. AISTATS 2021.
  • Group Fairness in Committee Selection. (arXiv)
    (α-β) Yu Cheng, Zhihao Jiang, Kamesh Munagala, Kangning Wang. EC 2019.
  • A Better Algorithm for Societal Tradeoffs. (pdf)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2019.
  • On the Distortion of Voting with Multiple Representative Candidates. (arXiv, slides)
    (α-β) Yu Cheng, Shaddin Dughmi, David Kempe. AAAI 2018.
  • Of the People: Voting Is More Effective with Representative Candidates. (arXiv, slides, talk video)
    (α-β) Yu Cheng, Shaddin Dughmi, David Kempe. EC 2017.

Equilibrium Computation and Efficiency:

  • How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
    (α-β) Yu Cheng, Tianle Jiang.
  • Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation. (arXiv)
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. EC 2023.
  • Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. (arXiv, slides, talk video)
    (α-β) Xi Chen, Yu Cheng, Bo Tang. ITCS 2017.
  • Playing Anonymous Games Using Simple Strategies. (arXiv, slides)
    (α-β) Yu Cheng, Ilias Diakonikolas, Alistair Stewart. SODA 2017.

Graph Theory

  • 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.
  • 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.
  • Sparsification of Directed Graphs via Cut Balance. (arXiv)
    (α-β) Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, Kevin Sun. ICALP 2021.