research
∙
07/24/2023
A faster and simpler algorithm for learning shallow networks
We revisit the well-studied problem of learning a linear combination of ...
share
research
∙
07/03/2023
Learning Mixtures of Gaussians Using the DDPM Objective
Recent works have shown that diffusion models can learn essentially any ...
research
∙
05/19/2023
The probability flow ODE is provably fast
We provide the first polynomial-time convergence guarantees for the prob...
research
∙
04/20/2023
Learning Narrow One-Hidden-Layer ReLU Networks
We consider the well-studied problem of learning a linear combination of...
research
∙
03/06/2023
Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers
We develop a framework for non-asymptotic analysis of deterministic samp...
research
∙
10/26/2022
Learning to predict arbitrary quantum processes
We present an efficient machine learning (ML) algorithm for predicting a...
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
∙
02/10/2022
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
We give superpolynomial statistical query (SQ) lower bounds for learning...
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/01/2021
Quantum advantage in learning from experiments
Quantum technology has the potential to revolutionize how we acquire and...
research
∙
11/11/2021
Kalman Filtering with Adversarial Corruptions
Here we revisit the classic problem of linear quadratic estimation, i.e....
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
∙
11/08/2021
Efficiently Learning Any One Hidden Layer ReLU Network From Queries
Model extraction attacks have renewed interest in the classic problem of...
research
∙
02/25/2021
Toward Instance-Optimal State Certification With Incoherent Measurements
We revisit the basic problem of quantum state certification: given copie...
research
∙
02/02/2021
Symmetric Boolean Factor Analysis with Applications to InstaHide
In this work we examine the security of InstaHide, a recently proposed s...
research
∙
11/23/2020
On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
In this work, we examine the security of InstaHide, a scheme recently pr...
research
∙
10/08/2020
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
In this work we revisit two classic high-dimensional online learning pro...
research
∙
09/28/2020
Learning Deep ReLU Networks Is Fixed-Parameter Tractable
We consider the problem of learning an unknown ReLU network with respect...
research
∙
06/08/2020
Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
In this paper we revisit some classic problems on classification under m...
research
∙
04/28/2020
Learning Polynomials of Few Relevant Dimensions
Polynomial regression is a basic primitive in learning and statistics. I...
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
∙
04/16/2020
Algorithmic Foundations for the Diffraction Limit
For more than a century and a half it has been widely-believed (but was ...
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
∙
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/05/2019
Efficiently Learning Structured Distributions from Untrusted Batches
We study the problem, introduced by Qiao and Valiant, of learning from u...
research
∙
10/30/2018
Improved Bounds for Randomly Sampling Colorings via Linear Programming
A well-known conjecture in computer science and statistical physics is t...
research
∙
04/09/2018
Linear Programming Bounds for Randomly Sampling Colorings
Here we study the problem of sampling random proper colorings of a bound...
research
∙
03/17/2018