About

I am a senior research scientist in the Machine Learning and Optimization Group at Microsoft Research Redmond.

In Fall 2018 I was the VMware Research Fellow at the Simons Institute. I did my Ph.D at MIT, where I was fortunate to work with Ankur Moitra. I also did my masters at MIT under the wonderful supervision of Nir Shavit.

My primary research interests are in learning theory and distributed algorithms, but I am broadly interested in many other things in TCS. I particularly like applications of analysis and analytic techniques to TCS problems.

As an undergrad at the University of Washington, I worked on complexity of branching programs, and how we could prove hardness of techniques used for naturally arising learning problems in database theory and AI.

In my free time I enjoy being remarkably mediocre at ultimate frisbee, chess, and piano, amongst other things.

Teaching

I taught a course on robust machine learning at UW in Fall 2019! See the course website for more details. I am also making video lectures, covering and expanding upon some of the material covered in that course.

• Tony Duan (MSR AI Resident, 2019–2020).
• Hadi Salman (MSR AI Resident, 2018–2019).
• Sitan Chen (Research Intern, Summer 2019).

Papers

Theses

• Principled Approaches to Robust Machine Learning and Beyond
  Jerry Li.
  Ph.D thesis
  George M. Sprowls Award for outstanding Ph.D. theses in EECS at MIT
  Note: any stupid jokes in the thesis are the author's own. Please excuse them.
  

• The SprayList: A Scalable Relaxed Priority Queue
  Jerry Li.
  Master's thesis
  

Preprints

• Non-robust Features through the Lens of Universal Perturbations
  Sung Min Park, Kuo-An Wei, Kai Xiao, Jerry Li, Aleksander Mądry
  manuscript

• List-Decodable Mean Estimation in Nearly-PCA Time
  Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
  manuscript

• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
  Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm
  manuscript

• Security and Machine Learning in the Real World
  Ivan Evtimov, Weidong Cui, Ece Kamar, Emre Kıcıman, Tadayoshi Kohno, Jerry Li
  manuscript

• Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semirandom Noise
  Jerry Li, Aaron Sidford, Kevin Tian, Huishuai Zhang
  manuscript

• Finding the Mode of a Kernel Density Estimate
  Jasper C.H. Lee, Jerry Li, Christopher Musco, Jeff M. Phillips, Wai Ming Tai
  manuscript

• Efficient Algorithms for Multidimensional Segmented Regression
  Ilias Diakonikolas, Jerry Li, Anastasia Voloshinov
  manuscript

Conference and Workshop Papers

1. Aligning AI With Shared Human Values
   Dan Hendrycks, Collin Burns, Steven Basart, Andrew Critch, Jerry Li, Dawn Song, Jacob Steinhardt
   to appear, ICLR 2021

2. Byzantine-Resilient Non-Convex Stochastic Gradient Descent
   Dan Alistarh, Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li
   to appear, ICLR 2021

3. Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
   Samuel B. Hopkins, Jerry Li, Fred Zhang
   NeurIPS 2020

4. Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
   Arun Jambulapati, Jerry Li, Kevin Tian
   NeurIPS 2020, Spotlight Presentation

5. Learning Structured Distributions From Untrusted Batches: Faster and Simpler
   Sitan Chen, Jerry Li, Ankur Moitra
   NeurIPS 2020

6. Robust Covariance Estimation in Nearly-Matrix Multiplication Time
   Jerry Li, Guanghao Ye
   NeurIPS 2020

7. Entanglement is Necessary for Optimal Quantum Property Testing
   Sébastien Bubeck, Sitan Chen, Jerry Li
   FOCS 2020

8. Randomized Smoothing of All Shapes and Sizes
   Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, Jerry Li
   ICML 2020

9. Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
   Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, Kevin Tian
   STOC 2020

10. Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
    Sitan Chen, Jerry Li, Zhao Song
    STOC 2020

11. Efficiently Learning Structured Distributions from Untrusted Batches
    Sitan Chen, Jerry Li, Ankur Moitra
    STOC 2020

12. Low-rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers
    Hannah Lawrence, Jerry Li, Cameron Musco, Christopher Musco
    ICASSP 2020

13. The Sample Complexity of Toeplitz Covariance Estimation
    Yonina Eldar, Jerry Li, Cameron Musco, Christopher Musco
    SODA 2020

14. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
    Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, Sébastien Bubeck
    NeurIPS 2019, Spotlight Presentation

15. Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
    Yihe Dong, Samuel B. Hopkins, Jerry Li
    NeurIPS 2019, Spotlight Presentation

16. SEVER: A Robust Meta-Algorithm for Stochastic Optimization
    Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart
    preliminary version in SecML 2018, Oral Presentation
    ICML 2019

17. How Hard is Robust Mean Estimation?
    Samuel B. Hopkins, Jerry Li
    COLT 2019

18. On Mean Estimation For General Norms with Statistical Queries
    Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten
    COLT 2019

19. Privately Learning High-Dimensional Distributions
    Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman
    preliminary version in TPDP 2018
    COLT 2019

20. Spectral Signatures for Backdoor Attacks
    Brandon Tran, Jerry Li, Aleksander Mądry
    NeurIPS 2018

21. Byzantine Stochastic Gradient Descent
    Dan Alistarh, Zeyuan Allen-Zhu, Jerry Li
    NeurIPS 2018

22. On the limitations of first order approximation in GAN dynamics
    Jerry Li, Aleksander Mądry, John Peebles, Ludwig Schmidt
    preliminary version in PADL 2017 as Towards Understanding the Dynamics of Generative Adversarial Networks
    ICML 2018

23. Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
    Ilias Diakonikolas, Jerry Li, Ludwig Schmidt
    COLT 2018

24. Distributionally Linearizable Data Structures
    Dan Alistarh, Trevor Brown, Justin Kopinsky, Jerry Li, Giorgi Nadiradze
    SPAA 2018
    

25. Mixture Models, Robustness, and Sum of Squares Proofs
    Samuel B. Hopkins, Jerry Li
    STOC 2018
    

26. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
    Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart
    SODA 2018
    

27. QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks
    Dan Alistarh, Demjan Grubić, Jerry Li, Ryota Tomioka, Milan Vojnovic
    preliminary version in OPT 2016
    NIPS 2017, Spotlight Presentation
    Invited for presentation at NVIDIA GTC
    [code][poster][video]

28. Being Robust (in High Dimensions) can be Practical
    Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart
    ICML 2017
    [code]
    

29. ZipML: An End-to-end Bitwise Framework for Dense Generalized Linear Models
    Hantian Zhang*, Jerry Li*, Kaan Kara, Dan Alistarh, Ji Liu, Ce Zhang
    *equal contribution
    ICML 2017
    

30. The Power of Choice in Priority Scheduling
    Dan Alistarh, Justin Kopinsky, Jerry Li, Giorgi Nadiradze
    PODC 2017

31. Robust Sparse Estimation Tasks in High Dimensions
    Jerry Li
    COLT 2017
    merged with this paper

32. Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
    Jerry Li, Ludwig Schmidt.
    COLT 2017
    

33. Sample Optimal Density Estimation in Nearly-Linear Time
    Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt.
    SODA 2017
    TCS+ talk by Ilias, which discussed the piecewise polynomial framework and our results at a high level
    

34. Robust Estimators in High Dimensions, without the Computational Intractability
    Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart
    FOCS 2016
    Invited to Highlights of Algorithms 2017
    Invited to appear in special issue of SIAM Journal on Computing for FOCS 2016.
    Invited to appear in Communications of the ACM Research Highlights.
    MIT News, USC Viterbi News

35. Fast Algorithms for Segmented Regression
    Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt
    ICML 2016
    

36. Replacing Mark Bits with Randomness in Fibonacci Heaps
    Jerry Li, John Peebles.
    ICALP 2015
    

37. Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms
    Jayadev Acharya, Ilias Diakonikolas, Chinmay Hegde, Jerry Li, Ludwig Schmidt.
    PODS 2015
    

38. The SprayList: A Scalable Relaxed Priority Queue
    Dan Alistarh, Justin Kopinsky, Jerry Li, Nir Shavit.
    PPoPP 2015, Best Artifact Award
    See also the full version
    [code]
    Slashdot, MIT News

39. On the Importance of Registers for Computability
    Rati Gelashvili, Mohsen Ghaffari, Jerry Li, Nir Shavit.
    OPODIS 2014
    

The following two papers are subsumed by the journal paper Exact Model Counting of Query Expressions: Limitations of Propositional Methods below.

40. Model Counting of Query Expressions: Limitations of Propositional Methods
    Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu.
    ICDT 2014
    Invited to appear in special issue of ACM Transactions on Database Systems for ICDT 2014.

41. Lower bounds for exact model counting and applications in probabilistic databases
    Paul Beame, Jerry Li, Sudeepa Roy, and Dan Suciu.
    UAI 2013, selected for plenary presentation.
    

Journal Papers

• Robust Estimators in High Dimensions without the Computational Intractability
  Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart.
  SIAM Journal on Computing, 48(2), 2019. Special Issue for FOCS 2016.

• Exact Model Counting of Query Expressions: Limitations of Propositional Methods
  Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu.
  ACM Transactions on Database Systems (TODS), Vol. 42, Issue 1, pages 1:1-1:46, March 2017.

Patents

• Efficient training of neural networks
  Dan Alistarh, Jerry Li, Ryota Tomioka, Milan Vojnovic
  

Other Writing

• Tracking Serial Criminals with a Road Metric
  Mark Bun, Jerry Li, Ian Zemke.
  Our 2010 MCM submission, which was awarded an Outstanding Winner prize (the top prize).
  

Talks

• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
  

  • Columbia Theory Seminar, July 2019

• Efficiently Learning from Untrusted Batches
  

  • NYU Computation, Information, and Mathematics Seminar, July 2019

• The Sample Complexity of Toeplitz Covariance Estimation
  

  • MIT Algorithms and Complexity Seminar, May 2019

• Efficient Algorithms for High Dimensional Robust Learning
  

  • MSR AI Seminar, April 2019

• Nearly Optimal Algorithms for Robust Mean Estimation
  

  • MIT Algorithms and Complexity Seminar, February 2019

  • TTIC Machine Learning Seminar, February 2019
    

  • MSR MLO Lunch, January 2019
    

  • UW Theory Seminar, January 2019
    

• "Explicitly" Learning Mixtures of Gaussians
  

  • Simons Fellows Reading Group, September 2018
    

• Robustly Learning a Gaussian in High Dimensions: Getting Optimal Error, Efficiently
  

  • SODA 2018, January 2018
    

• Mixture Models, Robustness, and Sum-of-Squares Proofs
  

  • Google Algorithms Reading Group, July 2018
    

  • Microsoft Research Redmond, December 2017
    

  • MIT Algorithms and Complexity Semniar, November 2017
    

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
  

  • NIPS 2017, December 2017
    

• Being Robust (in High Dimensions) can be Practical
  

  • ICML 2017, August 2017
    

• Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
  

  • COLT 2017, July 2017
    

• Efficient Robust Sparse Estimation in High Dimensions
  

  • COLT 2017, July 2017. Joint with Simon Du
    

• Robust Estimators In High Dimensions without the Computational Intractability [slides]
  

  • TCS+, December 2016 [video]
    

  • FOCS, October 2016 [video]
    

  • ETH Theory Seminar, August 2016
    

  • UW Theory Lunch, July 2016
    

  • MIT Algorithms and Complexity Seminar, June 2016
    

• Quantized Stochastic Gradient Descent
  

  • MIT ML Tea, October 2016
    

• Fast Algorithms for Segmented Regression [slides]
  

  • ICML 2016 [video]
    

• Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms [slides]
  

  • PODS 2015
    

• Model Counting of Query Expressions: Limitations of Propositional Methods [slides]
  

  • ICDT 2015
    

  • MIT Theory Lunch, 2014
    

Misc

• I'm participating in Algorithms Office Hours. If you're affiliated with MIT, and have algorithmic questions, please contact us!
  

• I am on the steering committee for SLOGN*
  

• I organized the Great Ideas in Theoretical Computer Science (aka theory lunch) in the 2013-2014 academic year.
  

• I stole the boombox from the Glorious Office 3 times, then promptly lost it back each time.