Ilias Diakonikolas

The Effect of Layer Ordering in Hybrid Architectures

John Cooper, Mingchen Ma, Jiaqi Mo +4

Hybrid attention is rapidly becoming the dominant architectural choice for frontier models. Despite their successes, such architectures complicate model design by introducing addit…

Efficiently Learning Drifting Halfspaces with Massart Noise

Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1

We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labe…

Robust Regression of General ReLUs with Queries

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma

We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setti…

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma

We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples $(x, y)$ from a distribution over $\mathbb{R}^d \tim…

Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models

John Cooper, Ilias Diakonikolas, Mingchen Ma +1

Hybrid sequence models--combining Transformer and state-space model layers--seek to gain the expressive versatility of attention as well as the computational efficiency of state-sp…

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

We study mean estimation for a Gaussian distribution with identity covariance in $R^{d}$ under a missing data scheme termed realizable $ε$ -contamination model. In this model…

Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination

Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1

We study the basic task of mean estimation in the presence of mean-shift contamination. In the mean-shift contamination model, an adversary is allowed to replace a small constant f…

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…

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…

cs.LG2025★ 1 cited

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…

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 $K$ -MIM is a function $f : R^{d} \to R$ 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 $k$ -mixtures of Gaussians ( $k$ -GMMs) on $R^{d}$ . This task is known to have complexity $d^{Ω (k)}$ 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 $K$ -MIM is any function $f$ that only depends on a $K$ -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…

Active Learning of General Halfspaces: Label Queries vs Membership Queries

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma

We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on $R^{d}$ in the presence of some form of query access. In th…

Reliable Learning of Halfspaces under Gaussian Marginals

Ilias Diakonikolas, Lisheng Ren, Nikos Zarifis

We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012). The reliable PAC model captures learning scenarios where one type of error is…

Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise

Shuyao Li, Sushrut Karmalkar, Ilias Diakonikolas +1

We study the problem of learning a single neuron with respect to the $L_{2}^{2}$ -loss in the presence of adversarial distribution shifts, where the labels can be arbitrary, and the goa…

Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models

Puqian Wang, Nikos Zarifis, Ilias Diakonikolas +1

A single-index model (SIM) is a function of the form $σ (w^{*} \cdot x)$ , where $σ : R \to R$ is a known link function and $w^{*}$ …

Sum-of-squares lower bounds for Non-Gaussian Component Analysis

Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang +1

Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d.\ samples from a distrib…