Nikos Zarifis

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…

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…

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…

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^{*}$ …

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise

Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1

We study the task of testable learning of general -- not necessarily homogeneous -- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testab…

Online Learning of Halfspaces with Massart Noise

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1

We study the task of online learning in the presence of Massart noise. Instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the con…

Robustly Learning Single-Index Models via Alignment Sharpness

Nikos Zarifis, Puqian Wang, Ilias Diakonikolas +1

We study the problem of learning Single-Index Models under the $L_{2}^{2}$ loss in the agnostic model. We give an efficient learning algorithm, achieving a constant factor approximatio…

Agnostically Learning Multi-index Models with Queries

Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2

We study the power of query access for the task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels and the goal is t…

Self-Directed Linear Classification

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1

In online classification, a learner is presented with a sequence of examples and aims to predict their labels in an online fashion so as to minimize the total number of mistakes. I…

Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2

We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces with Random Classification Noise under the Gaussian distribution. We establish nearly-matchi…

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2

We study the problem of PAC learning $γ$ -margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the…

SQ Lower Bounds for Learning Bounded Covariance GMMs

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1

We study the complexity of learning mixtures of separated Gaussians with common unknown bounded covariance matrix. Specifically, we focus on learning Gaussian mixture models (GMMs)…

Robustly Learning a Single Neuron via Sharpness

Puqian Wang, Nikos Zarifis, 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 label noise. We give an efficient algorithm that, for a broad famil…