Jerry Li

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Black-Box k-to-1-PCA Reductions: Theory and Applications.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Learning Polynomial Transformations via Generalized Tensor Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Structured Semidefinite Programming for Recovering Structured Preconditioners.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Matrix Completion in Almost-Verification Time.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

When Does Adaptivity Help for Quantum State Learning?

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Automatic Prompt Optimization with "Gradient Descent" and Beam Search.

[BibT_eX]

[DOI]

Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023

Semi-Random Sparse Recovery in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

The Complexity of NISQ.

[BibT_eX]

[DOI]

CoRR, 2022

Tight Bounds for State Tomography with Incoherent Measurements.

[BibT_eX]

[DOI]

CoRR, 2022

Learning Polynomial Transformations.

[BibT_eX]

[DOI]

CoRR, 2022

Clustering mixtures with almost optimal separation in polynomial time.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Clustering mixture models in almost-linear time via list-decodable mean estimation.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Robust Model Selection and Nearly-Proper Learning for GMMs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Learning (Very) Simple Generative Models Is Hard.

[BibT_eX]

[DOI]

Yuanzhi Li

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

Tight Bounds for Quantum State Certification with Incoherent Measurements.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Toward Instance-Optimal State Certification With Incoherent Measurements.

[BibT_eX]

[DOI]

Ryan O'Donnell

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

The Price of Tolerance in Distribution Testing.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

On Distinctive Properties of Universal Perturbations.

[BibT_eX]

[DOI]

CoRR, 2021

Quantum advantage in learning from experiments.

[BibT_eX]

[DOI]

CoRR, 2021

A Hierarchy for Replica Quantum Advantage.

[BibT_eX]

[DOI]

CoRR, 2021

Sparsification for Sums of Exponentials and its Algorithmic Applications.

[BibT_eX]

[DOI]

CoRR, 2021

Robustness meets algorithms.

[BibT_eX]

[DOI]

Commun. ACM, 2021

Robust Regression Revisited: Acceleration and Improved Estimation Rates.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

List-Decodable Mean Estimation in Nearly-PCA Time.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Aligning AI With Shared Human Values.

[BibT_eX]

[DOI]

Proceedings of the 9th International Conference on Learning Representations, 2021

Byzantine-Resilient Non-Convex Stochastic Gradient Descent.

[BibT_eX]

[DOI]

Zeyuan Allen-Zhu

Faeze Ebrahimianghazani

Dan Alistarh

Proceedings of the 9th International Conference on Learning Representations, 2021

Exponential Separations Between Learning With and Without Quantum Memory.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Finding an Approximate Mode of a Kernel Density Estimate.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Security and Machine Learning in the Real World.

[BibT_eX]

[DOI]

CoRR, 2020

Efficient Algorithms for Multidimensional Segmented Regression.

[BibT_eX]

[DOI]

Ilias Diakonikolas

Anastasia Voloshinov

CoRR, 2020

Positive semidefinite programming: mixed, parallel, and width-independent.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Learning mixtures of linear regressions in subexponential time via Fourier moments.

[BibT_eX]

[DOI]

Zhao Song

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Efficiently learning structured distributions from untrusted batches.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Sample Efficient Toeplitz Covariance Estimation.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing.

[BibT_eX]

[DOI]

Arun Jambulapati

Kevin Tian

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization.

[BibT_eX]

[DOI]

Fred Zhang

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning Structured Distributions From Untrusted Batches: Faster and Simpler.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time.

[BibT_eX]

[DOI]

Guanghao Ye

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Randomized Smoothing of All Shapes and Sizes.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Low-Rank Toeplitz Matrix Estimation Via Random Ultra-Sparse Rulers.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE International Conference on Acoustics, 2020

Entanglement is Necessary for Optimal Quantum Property Testing.

[BibT_eX]

[DOI]

Sébastien Bubeck

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Robust Estimators in High-Dimensions Without the Computational Intractability.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Finding the Mode of a Kernel Density Estimate.

[BibT_eX]

[DOI]

CoRR, 2019

Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

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

[BibT_eX]

[DOI]

Yihe Dong

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Sever: A Robust Meta-Algorithm for Stochastic Optimization.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

On Mean Estimation for General Norms with Statistical Queries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Privately Learning High-Dimensional Distributions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

How Hard is Robust Mean Estimation?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Principled approaches to robust machine learning and beyond.

[BibT_eX]

[DOI]

Jerry Zheng Li

PhD thesis, 2018

Mixture models, robustness, and sum of squares proofs.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Distributionally Linearizable Data Structures.

[BibT_eX]

[DOI]

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Spectral Signatures in Backdoor Attacks.

[BibT_eX]

[DOI]

Brandon Tran

Aleksander Madry

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Byzantine Stochastic Gradient Descent.

[BibT_eX]

[DOI]

Dan Alistarh

Zeyuan Allen-Zhu

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

On the Limitations of First-Order Approximation in GAN Dynamics.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms.

[BibT_eX]

[DOI]

Ilias Diakonikolas

Ludwig Schmidt

Proceedings of the Conference On Learning Theory, 2018

2017

Exact Model Counting of Query Expressions: Limitations of Propositional Methods.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2017

Robust Sparse Estimation Tasks in High Dimensions.

[BibT_eX]

[DOI]

CoRR, 2017

Towards Understanding the Dynamics of Generative Adversarial Networks.

[BibT_eX]

[DOI]

CoRR, 2017

Sample-Optimal Density Estimation in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Power of Choice in Priority Scheduling.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Communication-Efficient Distributed Learning of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Being Robust (in High Dimensions) Can Be Practical.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Computationally Efficient Robust Sparse Estimation in High Dimensions.

[BibT_eX]

[DOI]

Sivaraman Balakrishnan

Simon S. Du

Aarti Singh

Proceedings of the 30th Conference on Learning Theory, 2017

Robust and Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities.

[BibT_eX]

[DOI]

Ludwig Schmidt

Proceedings of the 30th Conference on Learning Theory, 2017

2016

ZipML: An End-to-end Bitwise Framework for Dense Generalized Linear Models.

[BibT_eX]

[DOI]

CoRR, 2016

QSGD: Randomized Quantization for Communication-Optimal Stochastic Gradient Descent.

[BibT_eX]

[DOI]

CoRR, 2016

Fast Algorithms for Segmented Regression.

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k.

[BibT_eX]

[DOI]

Jerry Zheng Li

Ludwig Schmidt

CoRR, 2015

The SprayList: a scalable relaxed priority queue.

[BibT_eX]

[DOI]

Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2015

Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms.

[BibT_eX]

[DOI]

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Replacing Mark Bits with Randomness in Fibonacci Heaps.

[BibT_eX]

[DOI]