research
∙
08/07/2023
Matrix Completion in Almost-Verification Time
We give a new framework for solving the fundamental problem of low-rank ...
share
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...
research
∙
05/04/2023
Automatic Prompt Optimization with "Gradient Descent" and Beam Search
Large Language Models (LLMs) have shown impressive performance as genera...
research
∙
04/05/2023
Query lower bounds for log-concave sampling
Log-concave sampling has witnessed remarkable algorithmic advances in re...
research
∙
11/11/2022
Controlling Commercial Cooling Systems Using Reinforcement Learning
This paper is a technical overview of DeepMind and Google's recent work ...
research
∙
10/13/2022
The Complexity of NISQ
The recent proliferation of NISQ devices has made it imperative to under...
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...
research
∙
06/10/2022
Tight Bounds for State Tomography with Incoherent Measurements
We consider the classic question of state tomography: given copies of an...
research
∙
05/31/2022
Learning (Very) Simple Generative Models Is Hard
Motivated by the recent empirical successes of deep generative models, w...
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...
research
∙
04/08/2022
Learning Polynomial Transformations
We consider the problem of learning high dimensional polynomial transfor...
research
∙
03/08/2022
Semi-Random Sparse Recovery in Nearly-Linear Time
Sparse recovery is one of the most fundamental and well-studied inverse ...
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...
research
∙
12/31/2021
On Distinctive Properties of Universal Perturbations
We identify properties of universal adversarial perturbations (UAPs) tha...
research
∙
12/01/2021
Quantum advantage in learning from experiments
Quantum technology has the potential to revolutionize how we acquire and...
research
∙
12/01/2021
Clustering Mixtures with Almost Optimal Separation in Polynomial Time
We consider the problem of clustering mixtures of mean-separated Gaussia...
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 ...
research
∙
11/10/2021
A Hierarchy for Replica Quantum Advantage
We prove that given the ability to make entangled measurements on at mos...
research
∙
06/22/2021
Robust Regression Revisited: Acceleration and Improved Estimation Rates
We study fast algorithms for statistical regression problems under the s...
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...
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...
research
∙
02/25/2021
Toward Instance-Optimal State Certification With Incoherent Measurements
We revisit the basic problem of quantum state certification: given copie...
research
∙
12/28/2020
Byzantine-Resilient Non-Convex Stochastic Gradient Descent
We study adversary-resilient stochastic distributed optimization, in whi...
research
∙
11/19/2020
List-Decodable Mean Estimation in Nearly-PCA Time
Traditionally, robust statistics has focused on designing estimators tol...
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...
research
∙
08/05/2020
Aligning AI With Shared Human Values
We show how to assess a language model's knowledge of basic concepts of ...
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 ...
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...
research
∙
07/13/2020
Security and Machine Learning in the Real World
Machine learning (ML) models deployed in many safety- and business-criti...
research
∙
06/24/2020
RL Unplugged: Benchmarks for Offline Reinforcement Learning
Offline methods for reinforcement learning have the potential to help br...
research
∙
06/23/2020
Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time
Robust covariance estimation is the following, well-studied problem in h...
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...
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...
research
∙
03/24/2020
Efficient Algorithms for Multidimensional Segmented Regression
We study the fundamental problem of fixed design multidimensional segme...
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...
research
∙
02/24/2020
Learning Structured Distributions From Untrusted Batches: Faster and Simpler
We revisit the problem of learning from untrusted batches introduced by ...
research
∙
02/19/2020
Randomized Smoothing of All Shapes and Sizes
Randomized smoothing is a recently proposed defense against adversarial ...
research
∙
02/12/2020
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
We give the first approximation algorithm for mixed packing and covering...
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...
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...
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 ...
research
∙
11/05/2019
Efficiently Learning Structured Distributions from Untrusted Batches
We study the problem, introduced by Qiao and Valiant, of learning from u...
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...
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...
research
∙
05/14/2019
Sample Efficient Toeplitz Covariance Estimation
We study the query complexity of estimating the covariance matrix T of a...
research
∙
03/19/2019
How Hard Is Robust Mean Estimation?
Robust mean estimation is the problem of estimating the mean μ∈R^d of a ...
research
∙
02/07/2019
On Mean Estimation for General Norms with Statistical Queries
We study the problem of mean estimation for high-dimensional distributio...
research
∙
11/01/2018
Spectral Signatures in Backdoor Attacks
A recent line of work has uncovered a new form of data poisoning: so-cal...
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 ...
research
∙
05/01/2018