142 citations · 338 across the 19 of their papers we have counts for
29 papers
Statistical Query Lower Bounds for List-Decodable Linear Regression
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +2
We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set of labeled examples $(x, y…
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart +1
We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. O…
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane +2
We study high-dimensional sparse estimation tasks in a robust setting where a constant fraction of the dataset is adversarially corrupted. Specifically, we focus on the fundamental…
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
Brian Axelrod, Ilias Diakonikolas, Anastasios Sidiropoulos +2
We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given points…
A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart
We study the problem of computing the maximum likelihood estimator (MLE) of multivariate log-concave densities. Our main result is the first computationally efficient algorithm for…
Reachability for Branching Concurrent Stochastic Games
Kousha Etessami, Emanuel Martinov, Alistair Stewart +1
We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperf…
Efficient Algorithms and Lower Bounds for Robust Linear Regression
Ilias Diakonikolas, Weihao Kong, Alistair Stewart
We study the problem of high-dimensional linear regression in a robust model where an -fraction of the samples can be adversarially corrupted. We focus on the fundamental settin…
Sever: A Robust Meta-Algorithm for Stochastic Optimization
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
In high dimensions, most machine learning methods are brittle to even a small fraction of structured outliers. To address this, we introduce a new meta-algorithm that can take in a…
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos +1
We study the problem of learning multivariate log-concave densities with respect to a global loss function. We obtain the first upper bound on the sample complexity of the maximum…
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We study the problem of list-decodable Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. We develop a set of techniques that y…
Testing Conditional Independence of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane +1
We study the problem of testing \emph{conditional independence} for discrete distributions. Specifically, given samples from a discrete random variable on domain $[\ell…
Sharp Bounds for Generalized Uniformity Testing
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We study the problem of generalized uniformity testing \cite{BC17} of a discrete probability distribution: Given samples from a probability distribution over an {\em unknown} d…
Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We study the efficient learnability of geometric concept classes - specifically, low-degree polynomial threshold functions (PTFs) and intersections of halfspaces - when a fraction…
Fourier-Based Testing for Families of Distributions
Clément L. Canonne, Ilias Diakonikolas, Alistair Stewart
We study the general problem of testing whether an unknown distribution belongs to a specified family of distributions. More specifically, given a distribution family …
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an -fraction of our samples were chosen by…
Being Robust (in High Dimensions) Can Be Practical
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can t…
Testing Bayesian Networks
Clement Canonne, Ilias Diakonikolas, Daniel Kane +1
This work initiates a systematic investigation of testing high-dimensional structured distributions by focusing on testing Bayesian networks -- the prototypical family of directed…
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We describe a general technique that yields the first {\em Statistical Query lower bounds} for a range of fundamental high-dimensional learning problems involving Gaussian distribu…
Playing Anonymous Games using Simple Strategies
Yu Cheng, Ilias Diakonikolas, Alistair Stewart
We investigate the complexity of computing approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any -player anonymous game with a bo…
Efficient Robust Proper Learning of Log-concave Distributions
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We study the {\em robust proper learning} of univariate log-concave distributions (over continuous and discrete domains). Given a set of samples drawn from an unknown target distri…
Robust Learning of Fixed-Structure Bayesian Networks
Yu Cheng, Ilias Diakonikolas, Daniel Kane +1
We investigate the problem of learning Bayesian networks in a robust model where an -fraction of the samples are adversarially corrupted. In this work, we study the fully observ…
Learning Multivariate Log-concave Distributions
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We study the problem of estimating multivariate log-concave probability density functions. We prove the first sample complexity upper bound for learning log-concave densities on $\…
Robust Estimators in High Dimensions without the Computational Intractability
Ilias Diakonikolas, Gautam Kamath, Daniel Kane +3
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an -fraction of the samples. Such questions…
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We give an algorithm for properly learning Poisson binomial distributions. A Poisson binomial distribution (PBD) of order is the discrete probability distribution of the sum of…