research
∙
07/31/2023
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions
We develop a new technique for proving distribution testing lower bounds...
share
research
∙
07/24/2023
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials
We study the problem of PAC learning a linear combination of k ReLU acti...
research
∙
07/13/2023
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
We study the problem of learning general (i.e., not necessarily homogene...
research
∙
06/28/2023
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
We study the problem of PAC learning γ-margin halfspaces with Random Cla...
research
∙
06/22/2023
SQ Lower Bounds for Learning Bounded Covariance GMMs
We study the complexity of learning mixtures of separated Gaussians with...
research
∙
05/04/2023
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
We study principal component analysis (PCA), where given a dataset in ℝ^...
research
∙
05/01/2023
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
We study the problem of list-decodable Gaussian covariance estimation. G...
research
∙
03/09/2023
Efficient Testable Learning of Halfspaces with Adversarial Label Noise
We give the first polynomial-time algorithm for the testable learning of...
research
∙
02/13/2023
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals
We study the task of agnostically learning halfspaces under the Gaussian...
research
∙
02/13/2023
Do PAC-Learners Learn the Marginal Distribution?
We study a foundational variant of Valiant and Vapnik and Chervonenkis' ...
research
∙
12/21/2022
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points
We prove that for c>0 a sufficiently small universal constant that a ran...
research
∙
12/06/2022
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
The Forster transform is a method of regularizing a dataset by placing i...
research
∙
11/29/2022
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
We study the fundamental task of outlier-robust mean estimation for heav...
research
∙
10/25/2022
Gaussian Mean Testing Made Simple
We study the following fundamental hypothesis testing problem, which we ...
research
∙
10/18/2022
SQ Lower Bounds for Learning Single Neurons with Massart Noise
We study the problem of PAC learning a single neuron in the presence of ...
research
∙
07/28/2022
Cryptographic Hardness of Learning Halfspaces with Massart Noise
We study the complexity of PAC learning halfspaces in the presence of Ma...
research
∙
07/14/2022
Near-Optimal Bounds for Testing Histogram Distributions
We investigate the problem of testing whether a discrete probability dis...
research
∙
06/10/2022
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
We study the problem of list-decodable sparse mean estimation. Specifica...
research
∙
06/09/2022
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
We establish optimal Statistical Query (SQ) lower bounds for robustly le...
research
∙
06/07/2022
Robust Sparse Mean Estimation via Sum of Squares
We study the problem of high-dimensional sparse mean estimation in the p...
research
∙
04/26/2022
Streaming Algorithms for High-Dimensional Robust Statistics
We study high-dimensional robust statistics tasks in the streaming model...
research
∙
12/16/2021
Non-Gaussian Component Analysis via Lattice Basis Reduction
Non-Gaussian Component Analysis (NGCA) is the following distribution lea...
research
∙
09/26/2021
Quantum Money from Quaternion Algebras
We propose a new idea for public key quantum money. In the abstract sens...
research
∙
09/23/2021
Outlier-Robust Sparse Estimation via Non-Convex Optimization
We explore the connection between outlier-robust high-dimensional statis...
research
∙
08/19/2021
Threshold Phenomena in Learning Halfspaces with Massart Noise
We study the problem of PAC learning halfspaces on ℝ^d with Massart nois...
research
∙
07/12/2021
Forster Decomposition and Learning Halfspaces with Noise
A Forster transform is an operation that turns a distribution into one w...
research
∙
06/17/2021
Statistical Query Lower Bounds for List-Decodable Linear Regression
We study the problem of list-decodable linear regression, where an adver...
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
∙
02/10/2021
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
We study the problem of agnostically learning halfspaces under the Gauss...
research
∙
02/08/2021
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
We study the problem of agnostic learning under the Gaussian distributio...
research
∙
02/03/2021
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
We study the problem of learning Ising models satisfying Dobrushin's con...
research
∙
12/31/2020
The Sample Complexity of Robust Covariance Testing
We study the problem of testing the covariance matrix of a high-dimensio...
research
∙
12/17/2020
Hardness of Learning Halfspaces with Massart Noise
We study the complexity of PAC learning halfspaces in the presence of Ma...
research
∙
12/14/2020
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
Let V be any vector space of multivariate degree-d homogeneous polynomia...
research
∙
12/03/2020
Robustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomial-time algorithm for the problem of robustly estimati...
research
∙
11/19/2020
List-Decodable Mean Estimation in Nearly-PCA Time
Traditionally, robust statistics has focused on designing estimators tol...
research
∙
10/04/2020
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
We study the problem of PAC learning homogeneous halfspaces in the prese...
research
∙
09/18/2020
Prisoners, Rooms, and Lightswitches
We examine a new variant of the classic prisoners and lightswitches puzz...
research
∙
09/14/2020
Optimal Testing of Discrete Distributions with High Probability
We study the problem of testing discrete distributions with a focus on t...
research
∙
07/30/2020
Outlier Robust Mean Estimation with Subgaussian Rates via Stability
We study the problem of outlier robust high-dimensional mean estimation ...
research
∙
07/30/2020
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
We study the computational complexity of adversarially robust proper lea...
research
∙
07/12/2020
Robust Learning of Mixtures of Gaussians
We resolve one of the major outstanding problems in robust statistics. I...
research
∙
06/29/2020
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
We study the fundamental problems of agnostically learning halfspaces an...
research
∙
06/22/2020
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
We study the problem of PAC learning one-hidden-layer ReLU networks with...
research
∙
06/18/2020
List-Decodable Mean Estimation via Iterative Multi-Filtering
We study the problem of list-decodable mean estimation for bounded covar...
research
∙
06/18/2020
List-Decodable Mean Estimation via Iterative Multi-Fitering
We study the problem of list-decodable mean estimation for bounded cova...
research
∙
04/23/2020
Point Location and Active Learning: Learning Halfspaces Almost Optimally
Given a finite set X ⊂ℝ^d and a binary linear classifier c: ℝ^d →{0,1}, ...
research
∙
11/14/2019
Recent Advances in Algorithmic High-Dimensional Robust Statistics
Learning in the presence of outliers is a fundamental problem in statist...
research
∙
08/29/2019
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
We study the problem of properly learning large margin halfspaces in th...
research
∙
07/08/2019