Ilias Diakonikolas

research

∙ 09/20/2023

GLM Regression with Oblivious Corruptions

We demonstrate the first algorithms for the problem of regression for ge...

0 Ilias Diakonikolas, et al. ∙

research

∙ 08/06/2023

Self-Directed Linear Classification

In online classification, a learner is presented with a sequence of exam...

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

∙ 06/13/2023

Robustly Learning a Single Neuron via Sharpness

We study the problem of learning a single neuron with respect to the L_2...

0 Puqian Wang, 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

∙ 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/17/2022

Learning a Single Neuron with Adversarial Label Noise via Gradient Descent

We study the fundamental problem of learning a single neuron, i.e., a fu...

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

∙ 09/10/2021

ReLU Regression with Massart Noise

We study the fundamental problem of ReLU regression, where the goal is t...

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

∙ 06/14/2021

Boosting in the Presence of Massart Noise

We study the problem of boosting the accuracy of a weak learner in the (...

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

∙ 08/10/2020

Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees

Aggregating data is fundamental to data analytics, data exploration, and...

0 Stephen Macke, 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

∙ 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

∙ 06/11/2020

Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

We study the problem of agnostically learning homogeneous halfspaces in ...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/11/2020

Learning Halfspaces with Tsybakov Noise

We study the efficient PAC learnability of halfspaces in the presence of...

0 Ilias Diakonikolas, et al. ∙

Ilias Diakonikolas

Featured Co-authors