b'Jerry Li'

research

∙ 08/07/2023

Matrix Completion in Almost-Verification Time

We give a new framework for solving the fundamental problem of low-rank ...

0 Jonathan A. Kelner, et al. ∙

research

∙ 07/18/2023

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

We consider the question of Gaussian mean testing, a fundamental task in...

0 Clément L. Canonne, et al. ∙

research

∙ 05/04/2023

Automatic Prompt Optimization with "Gradient Descent" and Beam Search

Large Language Models (LLMs) have shown impressive performance as genera...

0 Reid Pryzant, et al. ∙

research

∙ 04/05/2023

Query lower bounds for log-concave sampling

Log-concave sampling has witnessed remarkable algorithmic advances in re...

0 Sinho Chewi, et al. ∙

research

∙ 11/11/2022

Controlling Commercial Cooling Systems Using Reinforcement Learning

This paper is a technical overview of DeepMind and Google's recent work ...

0 Jerry Luo, et al. ∙

research

∙ 10/13/2022

The Complexity of NISQ

The recent proliferation of NISQ devices has made it imperative to under...

0 Sitan Chen, et al. ∙

research

∙ 09/22/2022

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

We provide theoretical convergence guarantees for score-based generative...

1 Sitan Chen, et al. ∙

research

∙ 06/10/2022

Tight Bounds for State Tomography with Incoherent Measurements

We consider the classic question of state tomography: given copies of an...

0 Sitan Chen, et al. ∙

research

∙ 05/31/2022

Learning (Very) Simple Generative Models Is Hard

Motivated by the recent empirical successes of deep generative models, w...

0 Sitan Chen, et al. ∙

research

∙ 04/14/2022

Tight Bounds for Quantum State Certification with Incoherent Measurements

We consider the problem of quantum state certification, where we are giv...

0 Sitan Chen, et al. ∙

research

∙ 04/08/2022

Learning Polynomial Transformations

We consider the problem of learning high dimensional polynomial transfor...

0 Sitan Chen, et al. ∙

research

∙ 03/08/2022

Semi-Random Sparse Recovery in Nearly-Linear Time

Sparse recovery is one of the most fundamental and well-studied inverse ...

0 Jonathan A. Kelner, et al. ∙

research

∙ 01/18/2022

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

Arguably the most fundamental question in the theory of generative adver...

0 Sitan Chen, et al. ∙

research

∙ 12/31/2021

On Distinctive Properties of Universal Perturbations

We identify properties of universal adversarial perturbations (UAPs) tha...

6 Sung-Min Park, et al. ∙

research

∙ 12/01/2021

Quantum advantage in learning from experiments

Quantum technology has the potential to revolutionize how we acquire and...

11 Hsin-Yuan Huang, et al. ∙

research

∙ 12/01/2021

Clustering Mixtures with Almost Optimal Separation in Polynomial Time

We consider the problem of clustering mixtures of mean-separated Gaussia...

0 Jerry Li, et al. ∙

research

∙ 11/10/2021

Exponential separations between learning with and without quantum memory

We study the power of quantum memory for learning properties of quantum ...

0 Sitan Chen, et al. ∙

research

∙ 11/10/2021

A Hierarchy for Replica Quantum Advantage

We prove that given the ability to make entangled measurements on at mos...

0 Sitan Chen, et al. ∙

research

∙ 06/22/2021

Robust Regression Revisited: Acceleration and Improved Estimation Rates

We study fast algorithms for statistical regression problems under the s...

0 Arun Jambulapati, et al. ∙

research

∙ 06/16/2021

Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation

We study the problem of list-decodable mean estimation, where an adversa...

2 Ilias Diakonikolas, et al. ∙

research

∙ 06/05/2021

Sparsification for Sums of Exponentials and its Algorithmic Applications

Many works in signal processing and learning theory operate under the as...

0 Jerry Li, et al. ∙

research

∙ 02/25/2021

Toward Instance-Optimal State Certification With Incoherent Measurements

We revisit the basic problem of quantum state certification: given copie...

0 Sitan Chen, et al. ∙

research

∙ 12/28/2020

Byzantine-Resilient Non-Convex Stochastic Gradient Descent

We study adversary-resilient stochastic distributed optimization, in whi...

0 Zeyuan Allen-Zhu, et al. ∙

research

∙ 11/19/2020

List-Decodable Mean Estimation in Nearly-PCA Time

Traditionally, robust statistics has focused on designing estimators tol...

0 Ilias Diakonikolas, et al. ∙

research

∙ 09/13/2020

Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

Researchers currently use a number of approaches to predict and substant...

11 Matthew Brennan, et al. ∙

research

∙ 08/05/2020

Aligning AI With Shared Human Values

We show how to assess a language model's knowledge of basic concepts of ...

13 Dan Hendrycks, et al. ∙

research

∙ 08/04/2020

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

Classical iterative algorithms for linear system solving and regression ...

0 Jerry Li, et al. ∙

research

∙ 07/31/2020

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

We study the problem of estimating the mean of a distribution in high di...

9 Samuel B. Hopkins, et al. ∙

research

∙ 07/13/2020

Security and Machine Learning in the Real World

Machine learning (ML) models deployed in many safety- and business-criti...

38 Ivan Evtimov, et al. ∙

research

∙ 06/24/2020

RL Unplugged: Benchmarks for Offline Reinforcement Learning

Offline methods for reinforcement learning have the potential to help br...

10 Caglar Gulcehre, et al. ∙

research

∙ 06/23/2020

Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time

Robust covariance estimation is the following, well-studied problem in h...

12 Jerry Li, et al. ∙

research

∙ 06/12/2020

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

We develop two methods for the following fundamental statistical task: g...

0 Arun Jambulapati, et al. ∙

research

∙ 04/16/2020

Entanglement is Necessary for Optimal Quantum Property Testing

There has been a surge of progress in recent years in developing algorit...

0 Sébastien Bubeck, et al. ∙

research

∙ 03/24/2020

Efficient Algorithms for Multidimensional Segmented Regression

We study the fundamental problem of fixed design multidimensional segme...

0 Ilias Diakonikolas, et al. ∙

research

∙ 03/24/2020

An empirical investigation of the challenges of real-world reinforcement learning

Reinforcement learning (RL) has proven its worth in a series of artifici...

9 Gabriel Dulac-Arnold, et al. ∙

research

∙ 02/24/2020

Learning Structured Distributions From Untrusted Batches: Faster and Simpler

We revisit the problem of learning from untrusted batches introduced by ...

0 Sitan Chen, et al. ∙

research

∙ 02/19/2020

Randomized Smoothing of All Shapes and Sizes

Randomized smoothing is a recently proposed defense against adversarial ...

0 Greg Yang, et al. ∙

research

∙ 02/12/2020

Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent

We give the first approximation algorithm for mixed packing and covering...

0 Arun Jambulapati, et al. ∙

research

∙ 12/16/2019

Finding the Mode of a Kernel Density Estimate

Given points p_1, ..., p_n in R^d, how do we find a point x which maximi...

0 Jasper C. H. Lee, et al. ∙

research

∙ 12/16/2019

Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments

We consider the problem of learning a mixture of linear regressions (MLR...

0 Sitan Chen, et al. ∙

research

∙ 11/19/2019

Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers

We study how to estimate a nearly low-rank Toeplitz covariance matrix T ...

0 Hannah Lawrence, et al. ∙

research

∙ 11/05/2019

Efficiently Learning Structured Distributions from Untrusted Batches

We study the problem, introduced by Qiao and Valiant, of learning from u...

0 Sitan Chen, et al. ∙

research

∙ 06/26/2019

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

We study two problems in high-dimensional robust statistics: robust mean...

0 Yihe Dong, et al. ∙

research

∙ 06/09/2019

Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers

Recent works have shown the effectiveness of randomized smoothing as a s...

4 Hadi Salman, et al. ∙

research

∙ 05/14/2019

Sample Efficient Toeplitz Covariance Estimation

We study the query complexity of estimating the covariance matrix T of a...

0 Yonina C. Eldar, et al. ∙

research

∙ 03/19/2019

How Hard Is Robust Mean Estimation?

Robust mean estimation is the problem of estimating the mean μ∈R^d of a ...

0 Samuel B. Hopkins, et al. ∙

research

∙ 02/07/2019

On Mean Estimation for General Norms with Statistical Queries

We study the problem of mean estimation for high-dimensional distributio...

0 Jerry Li, et al. ∙

research

∙ 11/01/2018

Spectral Signatures in Backdoor Attacks

A recent line of work has uncovered a new form of data poisoning: so-cal...

2 Brandon Tran, et al. ∙

research

∙ 08/26/2018

Twin-GAN -- Unpaired Cross-Domain Image Translation with Weight-Sharing GANs

We present a framework for translating unlabeled images from one domain ...

0 Jerry Li, et al. ∙

research

∙ 05/01/2018

Privately Learning High-Dimensional Distributions

We design nearly optimal differentially private algorithms for learning ...

0 Gautam Kamath, et al. ∙

Jerry Li

Featured Co-authors