10 citations · 53 across the 28 of their papers we have counts for
29 papers
Efficient Optimization on the Euclidean Sphere: Riemannian Gradient Alignment as a Unifying Principle
Puqian Wang, Nikos Zarifis, Jelena Diakonikolas
Euclidean sphere-constrained optimization problems represent perhaps the most basic class of nonconvex-constrained problems for which there exist efficient optimization algorithms…
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 -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…
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 , where is a known link function and …
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…
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic resu…
Statistical Query Lower Bounds for Learning Truncated Gaussians
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the problem of estimating the mean of an identity covariance Gaussian in the truncated setting, in the regime when the truncation set comes from a low-complexity family $\…
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 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 -loss in the presence of adversarial label noise. We give an efficient algorithm that, for a broad famil…
Efficient Testable Learning of Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We give the first polynomial-time algorithm for the testable learning of halfspaces in the presence of adversarial label noise under the Gaussian distribution. In the recently intr…
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the fundamental problem of learning a single neuron, i.e., a function of the form for monotone activations $σ:\mathbb{R}\ma…
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning halfspaces on with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the labe…
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose sample…
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP dualit…
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, the label of every sample is independently flipped with…