Daniel M. Kane

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...

0 Yuqian Cheng, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/22/2023

SQ Lower Bounds for Learning Bounded Covariance GMMs

We study the complexity of learning mixtures of separated Gaussians with...

0 Ilias Diakonikolas, et al. ∙

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 ℝ^...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 02/13/2023

Do PAC-Learners Learn the Marginal Distribution?

We study a foundational variant of Valiant and Vapnik and Chervonenkis' ...

0 Max Hopkins, et al. ∙

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...

0 Daniel M. Kane, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 10/25/2022

Gaussian Mean Testing Made Simple

We study the following fundamental hypothesis testing problem, which we ...

0 Ilias Diakonikolas, et al. ∙

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 ...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 07/14/2022

Near-Optimal Bounds for Testing Histogram Distributions

We investigate the problem of testing whether a discrete probability dis...

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

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...

5 Ilias Diakonikolas, et al. ∙

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...

4 Ilias Diakonikolas, et al. ∙

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...

6 Ilias Diakonikolas, et al. ∙

research

∙ 04/26/2022

Streaming Algorithms for High-Dimensional Robust Statistics

We study high-dimensional robust statistics tasks in the streaming model...

6 Ilias Diakonikolas, et al. ∙

research

∙ 12/16/2021

Non-Gaussian Component Analysis via Lattice Basis Reduction

Non-Gaussian Component Analysis (NGCA) is the following distribution lea...

3 Ilias Diakonikolas, et al. ∙

research

∙ 09/26/2021

Quantum Money from Quaternion Algebras

We propose a new idea for public key quantum money. In the abstract sens...

0 Daniel M. Kane, et al. ∙

research

∙ 09/23/2021

Outlier-Robust Sparse Estimation via Non-Convex Optimization

We explore the connection between outlier-robust high-dimensional statis...

1 Yu Cheng, et al. ∙

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...

11 Ilias Diakonikolas, et al. ∙

research

∙ 07/12/2021

Forster Decomposition and Learning Halfspaces with Noise

A Forster transform is an operation that turns a distribution into one w...

10 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, 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

∙ 02/10/2021

Agnostic Proper Learning of Halfspaces under Gaussian Marginals

We study the problem of agnostically learning halfspaces under the Gauss...

5 Ilias Diakonikolas, et al. ∙

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...

1 Ilias Diakonikolas, et al. ∙

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...

5 Ilias Diakonikolas, et al. ∙

research

∙ 12/31/2020

The Sample Complexity of Robust Covariance Testing

We study the problem of testing the covariance matrix of a high-dimensio...

12 Ilias Diakonikolas, et al. ∙

research

∙ 12/17/2020

Hardness of Learning Halfspaces with Massart Noise

We study the complexity of PAC learning halfspaces in the presence of Ma...

0 Ilias Diakonikolas, et al. ∙

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...

9 Ilias Diakonikolas, et al. ∙

research

∙ 12/03/2020

Robustly Learning Mixtures of k Arbitrary Gaussians

We give a polynomial-time algorithm for the problem of robustly estimati...

3 Ainesh Bakshi, 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

∙ 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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 09/18/2020

Prisoners, Rooms, and Lightswitches

We examine a new variant of the classic prisoners and lightswitches puzz...

0 Daniel M. Kane, et al. ∙

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...

5 Ilias Diakonikolas, et al. ∙

research

∙ 07/30/2020

Outlier Robust Mean Estimation with Subgaussian Rates via Stability

We study the problem of outlier robust high-dimensional mean estimation ...

2 Ilias Diakonikolas, et al. ∙

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...

1 Ilias Diakonikolas, et al. ∙

research

∙ 07/12/2020

Robust Learning of Mixtures of Gaussians

We resolve one of the major outstanding problems in robust statistics. I...

0 Daniel M. Kane, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/18/2020

List-Decodable Mean Estimation via Iterative Multi-Filtering

We study the problem of list-decodable mean estimation for bounded covar...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/18/2020

List-Decodable Mean Estimation via Iterative Multi-Fitering

We study the problem of list-decodable mean estimation for bounded cova...

0 Ilias Diakonikolas, et al. ∙

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}, ...

3 Max Hopkins, et al. ∙

research

∙ 11/14/2019

Recent Advances in Algorithmic High-Dimensional Robust Statistics

Learning in the presence of outliers is a fundamental problem in statist...

39 Ilias Diakonikolas, et al. ∙

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...

7 Ilias Diakonikolas, et al. ∙

research

∙ 07/08/2019

The Power of Comparisons for Actively Learning Linear Classifiers

In the world of big data, large but costly to label datasets dominate ma...

4 Max Hopkins, et al. ∙

Daniel M. Kane

Featured Co-authors