
Statistical Query Lower Bounds for ListDecodable Linear Regression
We study the problem of listdecodable linear regression, where an adver...
read it

Clustering Mixture Models in AlmostLinear Time via ListDecodable Mean Estimation
We study the problem of listdecodable mean estimation, where an adversa...
read it

Boosting in the Presence of Massart Noise
We study the problem of boosting the accuracy of a weak learner in the (...
read it

Agnostic Proper Learning of Halfspaces under Gaussian Marginals
We study the problem of agnostically learning halfspaces under the Gauss...
read it

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
We study the problem of agnostic learning under the Gaussian distributio...
read it

OutlierRobust Learning of Ising Models Under Dobrushin's Condition
We study the problem of learning Ising models satisfying Dobrushin's con...
read it

The Sample Complexity of Robust Covariance Testing
We study the problem of testing the covariance matrix of a highdimensio...
read it

Hardness of Learning Halfspaces with Massart Noise
We study the complexity of PAC learning halfspaces in the presence of Ma...
read it

Small Covers for NearZero Sets of Polynomials and Learning Latent Variable Models
Let V be any vector space of multivariate degreed homogeneous polynomia...
read it

Robustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomialtime algorithm for the problem of robustly estimati...
read it

ListDecodable Mean Estimation in NearlyPCA Time
Traditionally, robust statistics has focused on designing estimators tol...
read it

A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
We study the problem of PAC learning homogeneous halfspaces in the prese...
read it

Optimal Testing of Discrete Distributions with High Probability
We study the problem of testing discrete distributions with a focus on t...
read it

Rapid Approximate Aggregation with DistributionSensitive Interval Guarantees
Aggregating data is fundamental to data analytics, data exploration, and...
read it

Outlier Robust Mean Estimation with Subgaussian Rates via Stability
We study the problem of outlier robust highdimensional mean estimation ...
read it

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
We study the computational complexity of adversarially robust proper lea...
read it

NearOptimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
We study the fundamental problems of agnostically learning halfspaces an...
read it

Algorithms and SQ Lower Bounds for PAC Learning OneHiddenLayer ReLU Networks
We study the problem of PAC learning onehiddenlayer ReLU networks with...
read it

ListDecodable Mean Estimation via Iterative MultiFiltering
We study the problem of listdecodable mean estimation for bounded covar...
read it

ListDecodable Mean Estimation via Iterative MultiFitering
We study the problem of listdecodable mean estimation for bounded cova...
read it

NonConvex SGD Learns Halfspaces with Adversarial Label Noise
We study the problem of agnostically learning homogeneous halfspaces in ...
read it

Learning Halfspaces with Tsybakov Noise
We study the efficient PAC learnability of halfspaces in the presence of...
read it

Approximation Schemes for ReLU Regression
We consider the fundamental problem of ReLU regression, where the goal i...
read it

Efficiently Learning Adversarially Robust Halfspaces with Noise
We study the problem of learning adversarially robust halfspaces in the ...
read it

Robustly Learning any Clusterable Mixture of Gaussians
We study the efficient learnability of highdimensional Gaussian mixture...
read it

HighDimensional Robust Mean Estimation via Gradient Descent
We study the problem of highdimensional robust mean estimation in the p...
read it

Efficient Algorithms for Multidimensional Segmented Regression
We study the fundamental problem of fixed design multidimensional segme...
read it

Learning Halfspaces with Massart Noise Under Structured Distributions
We study the problem of learning halfspaces with Massart noise in the di...
read it

OutlierRobust HighDimensional Sparse Estimation via Iterative Filtering
We study highdimensional sparse estimation tasks in a robust setting wh...
read it

Recent Advances in Algorithmic HighDimensional Robust Statistics
Learning in the presence of outliers is a fundamental problem in statist...
read it

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
We study the problem of properly learning large margin halfspaces in th...
read it

A Polynomial Time Algorithm for LogConcave Maximum Likelihood via Locally Exponential Families
We consider the problem of computing the maximum likelihood multivariate...
read it

DistributionIndependent PAC Learning of Halfspaces with Massart Noise
We study the problem of distributionindependent PAC learning of halfsp...
read it

Communication and Memory Efficient Testing of Discrete Distributions
We study distribution testing with communication and memory constraints ...
read it

Faster Algorithms for HighDimensional Robust Covariance Estimation
We study the problem of estimating the covariance matrix of a highdimen...
read it

Equipping Experts/Bandits with Longterm Memory
We propose the first reductionbased approach to obtaining longterm mem...
read it

On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games
Weighted voting games are a family of cooperative games, typically used ...
read it

A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Logconcave Densities
We study the problem of computing the maximum likelihood estimator (MLE)...
read it

HighDimensional Robust Mean Estimation in NearlyLinear Time
We study the fundamental problem of highdimensional mean estimation in ...
read it

Degreed Chow Parameters Robustly Determine Degreed PTFs (and Algorithmic Applications)
The degreed Chow parameters of a Boolean function f: {1,1}^n →R are it...
read it

Efficient Algorithms and Lower Bounds for Robust Linear Regression
We study the problem of highdimensional linear regression in a robust m...
read it

Testing Identity of Multidimensional Histograms
We investigate the problem of identity testing for multidimensional hist...
read it

Sever: A Robust MetaAlgorithm for Stochastic Optimization
In high dimensions, most machine learning methods are brittle to even a ...
read it

NearOptimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Logconcave Densities
We study the problem of learning multivariate logconcave densities with...
read it

Fast and Sample NearOptimal Algorithms for Learning Multidimensional Histograms
We study the problem of robustly learning multidimensional histograms. ...
read it

Testing Conditional Independence of Discrete Distributions
We study the problem of testing conditional independence for discrete di...
read it

ListDecodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
We study the problem of listdecodable Gaussian mean estimation and the ...
read it

Differentially Private Identity and Closeness Testing of Discrete Distributions
We investigate the problems of identity and closeness testing over a dis...
read it

Learning Geometric Concepts with Nasty Noise
We study the efficient learnability of geometric concept classes  speci...
read it

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
We study the fundamental problem of learning the parameters of a highdi...
read it
Ilias Diakonikolas
is this you? claim profile
Assistant Professor and Andrew and Erna Viterbi Early Career Chair in the Department of Computer Science at the University of Southern California