Yu Cheng

  • Home
  • Research
  • Misc

Publications by topic

    Machine Learning

    High-Dimensional Robust Statistics:
    • 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 in Nearly-Linear Time. (arXiv)
      Yu Cheng, Honghao Lin. ICLR 2021.
    Non-Convex Optimization:
    • 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:
    • 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:
    • Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation.
      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

    • 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.