Yu Cheng

  • Home
  • Research
  • Teaching
  • Misc
    Yu Cheng

    I am an Assistant Professor in the Mathematics (MSCS) Department of University of Illinois at Chicago. I am part of the MCS group (and part of the CS Theory crowd at UIC).


    I did my PhD in the CS Theory group of the University of Southern California, advised by Shang-Hua Teng. I was a postdoc in the Theory and CS-Econ groups at Duke University.

    In Fall 2019, I am participating the special-year program on Optimization, Statistics, and Theoretical Machine Learning at the Institute for Advanced Study.

    Research: My main research interests lie in the area of machine learning, game theory, and optimization. Recently, my work focuses on designing scalable and provably robust learning algorithms, and addressing the challenges that arise in the interactions between machine learning systems and strategic agents.

    Email: yucheng2 AT uic.edu

    Office address: SEO 416, 851 S Morgan St, Chicago, IL 60607.

    My CV, publications by date and by topic, PhD Thesis.

Publications

  1. Quantitative Judgment Aggregation for Evaluating Contestants.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer.

  2. Distinguishing Distributions When Samples Are Strategically Transformed.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. NeurIPS 2019.

  3. Group Fairness in Committee Selection. (arXiv)
    Yu Cheng, Zhihao Jiang, Kamesh Munagala, Kangning Wang. EC 2019.

  4. Faster Algorithms for High-Dimensional Robust Covariance Estimation. (arXiv)
    Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff. COLT 2019.

  5. When Samples Are Strategically Selected.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. ICML 2019.

  6. A Better Algorithm for Societal Tradeoffs.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2019.

  7. High-Dimensional Robust Mean Estimation in Nearly-Linear Time. (arXiv)
    Yu Cheng, Ilias Diakonikolas, Rong Ge. SODA 2019.

  8. A Simple Mechanism for a Budget-Constrained Buyer. (arXiv)
    Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang. WINE 2018 (Best Paper Award).

  9. Robust Learning of Fixed–Structure Bayesian Networks. (arXiv)
    Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. NeurIPS 2018.

  10. Non-Convex Matrix Completion Against a Semi-Random Adversary. (arXiv)
    Yu Cheng, Rong Ge. COLT 2018.

  11. A Deterministic Protocol for Sequential Asymptotic Learning. (arXiv)
    Yu Cheng, Wade Hann-Caruthers, Omer Tamuz. ISIT 2018.

  12. On the Distortion of Voting with Multiple Representative Candidates. (arXiv)
    Yu Cheng, Shaddin Dughmi, David Kempe. AAAI 2018.

  13. Of the People: Voting Is More Effective with Representative Candidates. (arXiv)
    Yu Cheng, Shaddin Dughmi, David Kempe. EC 2017.

  14. Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. (arXiv)
    Xi Chen, Yu Cheng, Bo Tang. ITCS 2017.

  15. Playing Anonymous Games using Simple Strategies. (arXiv)
    Yu Cheng, Ilias Diakonikolas, Alistair Stewart. SODA 2017.

  16. On the Recursive Teaching Dimension of VC Classes. (ECCC)
    Xi Chen, Yu Cheng, Bo Tang. NIPS 2016.

  17. Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games. (arXiv)
    Umang Bhaskar, Yu Cheng, Young Kun Ko, Chaitanya Swamy. EC 2016.

  18. Mixture Selection, Mechanism Design, and Signaling (arXiv)
    Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng. FOCS 2015.

  19. Signaling in Quasipolynomial Time (arXiv)
    Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Shang-Hua Teng.

  20. Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification (arXiv Part I, Part II)
    Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng. COLT 2015.

Talks

  • Robustness and Strategic Concerns in Machine Learning (slides).
    Nanjing Theory Day 2019, May 2019.
    Shanghai University of Finance and Economics, May 2019.
    University of Virginia, Mar 2019.
    Pennsylvania State University, Mar 2019.
    Washington University in St. Louis, Mar 2019.
    Google NYC, Mar 2019.
    University of Utah, Feb 2018.
    University of Illinois at Chicago, Feb 2018.
    Rensselaer Polytechnic Institute, Feb 2018.
    Shanghai Jiao Tong University, Jan 2019.

  • High-Dimensional Robust Mean Estimation in Nearly-Linear Time (slides).
    ITA Workshop, Feb 2019.
    SODA 2019, Jan 2019.
    Simons Institute (Robust Statistics Workshop, Lightning Talks), Oct 2018.
    Georgia Tech (ACO Student Seminar), Oct 2018.
    TTI Chicago (Robust Statistics Workshop), Aug 2018.

  • Non-Convex Matrix Completion Against a Semi-Random Adversary (slides).
    Google NYC (Machine Learning Seminar), Aug 2018.
    COLT 2018 (talk video), Jul 2018.
    Microsoft Research Redmond (talk video), Apr 2018.

  • On the Distortion of Voting with Multiple Representative Candidates (slides).
    AAAI 2018, Feb 2018.

  • Playing Anonymous Games using Simple Strategies (slides).
    Duke (Algorithms Seminar), Sep 2017.
    China Theory Week 2017, Jul 2017.
    SODA 2017, Jan 2017.
    SoCal Theory Day 2016, Nov 2016.

  • Voting Is More Effective with Representative Candidates (slides).
    EC 2017 (talk video), Jun 2017.

  • Computational Aspects of Optimal Information Revelation (slides).
    Google NYC (Algorithms Seminar, talk video), Apr 2017.
    Duke (CS-Econ Seminar), Mar 2017.
    Caltech (SISL Seminar), Mar 2017.
    USC (CS697: Seminar in CS Research), Nov 2016.
    ITCS 2017 (Graduating Bits), Jan 2017.
    NEGT 2016, Nov 2016.

  • Sparse Newton's Method (slides).
    Duke (Algorithms Seminar), Mar 2017.

  • Query Complexity of Large Games (slides).
    ITCS 2017 (talk video), Jan 2017.

  • Recursive Teaching Dimension of VC Classes.
    NIPS 2016 (3min video), Dec 2016.

  • Hardness of Signaling in Bayesian Games (slides).
    EC 2016, Jul 2016.

  • Mixture Selection, Mechanism Design, and Signaling (slides).
    FOCS 2015 (talk video), Oct 2015.