1 citations · 2 across the 34 of their papers we have counts for
15 papers · 1 filter
PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1
This work studies information-computation gaps for statistical problems. A common approach for providing evidence of such gaps is to show sample complexity lower bounds (that are s…
Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
Learning intersections of halfspaces is a central problem in Computational Learning Theory. Even for just two halfspaces, it remains a major open question whether learning is possi…
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Ilias Diakonikolas, Chao Gao, Daniel M. Kane +2
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a di…
Linear Regression under Missing or Corrupted Coordinates
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2
We study multivariate linear regression under Gaussian covariates in two settings, where data may be erased or corrupted by an adversary under a coordinate-wise budget. In the inco…
Robustly Learning Monotone Single-Index Models
Puqian Wang, Nikos Zarifis, Ilias Diakonikolas +1
We consider the basic problem of learning Single-Index Models with respect to the square loss under the Gaussian distribution in the presence of adversarial label noise. Our main c…
Replicable Distribution Testing
Ilias Diakonikolas, Jingyi Gao, Daniel Kane +2
We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probabili…
Distributionally Robust Optimization with Adversarial Data Contamination
Shuyao Li, Ilias Diakonikolas, Jelena Diakonikolas
Distributionally Robust Optimization (DRO) provides a framework for decision-making under distributional uncertainty, yet its effectiveness can be compromised by outliers in the tr…
On Fine-Grained Distinct Element Estimation
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +3
We study the problem of distributed distinct element estimation, where servers each receive a subset of a universe and aim to compute a -approximation to…
Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A -MIM is a function that depends only…
On Learning Parallel Pancakes with Mostly Uniform Weights
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the complexity of learning -mixtures of Gaussians (-GMMs) on . This task is known to have complexity in full generality. To circumvent this…
Faster Algorithms for Agnostically Learning Disjunctions and their Implications
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
We study the algorithmic task of learning Boolean disjunctions in the distribution-free agnostic PAC model. The best known agnostic learner for the class of disjunctions over $\{0,…
Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of l…
Robust Learning of Multi-index Models via Iterative Subspace Approximation
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution. A -MIM is any function that only depends on a -dimensional subsp…
Robustly Learning Monotone Generalized Linear Models via Data Augmentation
Nikos Zarifis, Puqian Wang, Ilias Diakonikolas +1
We study the task of learning Generalized Linear models (GLMs) in the agnostic model under the Gaussian distribution. We give the first polynomial-time algorithm that achieves a co…
A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
Ilias Diakonikolas, Nikos Zarifis
We study the problem of PAC learning -margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is…