Nikos Zarifis

ICML Conference 2025 Conference Paper

Online Linear Classification with Massart Noise

• Ilias Diakonikolas
• Vasilis Kontonis
• Christos Tzamos
• Nikos Zarifis

We study the task of online learning in the presence of Massart noise. Specifically, instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the context $\boldsymbol{x}$ is selected adversarially but the label $y$ presented to the learner disagrees with the ground-truth label of $\boldsymbol{x}$ with unknown probability at most $\eta$. We focus on the fundamental class of $\gamma$-margin linear classifiers and present the first computationally efficient algorithm that achieves mistake bound $\eta T + o(T)$. We point out that the mistake bound achieved by our algorithm is qualitatively tight for computationally efficient algorithms; this follows from the fact that, even in the offline setting, achieving 0-1 error better than $\eta$ requires super-polynomial time under standard complexity assumptions. We extend our online learning model to a $k$-arm contextual bandit setting where the rewards—instead of satisfying commonly used realizability assumptions—are consistent, in expectation, with some linear ranking function with weight vector $\boldsymbol{w}^\ast$. Given a list of contexts $\boldsymbol{x}_1, \ldots \boldsymbol{x}_k$, if $\boldsymbol{w}^*\cdot \boldsymbol{x}_i > \boldsymbol{w}^* \cdot \boldsymbol{x}_j$, the expected reward of action $i$ must be larger than that of $j$ by at least $\Delta$. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least $(1-1/k) \Delta T - o(T)$ bigger than choosing a random action at every round.

FOCS Conference 2025 Conference Paper

Robust Learning of Multi-index Models via Iterative Subspace Approximation

• Ilias Diakonikolas
• Giannis Iakovidis
• Daniel M. Kane
• Nikos Zarifis

We study the task of learning Multi-Index Models (MIMs) in the presence of label noise under the Gaussian distribution. A K-MIM on ℝ d is any function f that only depends on a K-dimensional subspace, i. e. , f(x) = g(Wx) for a link function g on ℝ K and a K × d matrix W. We consider a class of well-behaved MIMs with finite ranges that satisfy certain regularity properties. Our main contribution is a general noise-tolerant learning algorithm for this class whose complexity is qualitatively optimal in the Statistical Query (SQ) model. At a high-level, our algorithm attempts to iteratively construct better approximations to the defining subspace by computing low-degree moments of our function conditional on its projection to the subspace computed thus far, and adding directions with relatively large empirical moments. For well-behaved MIMs, we show that this procedure efficiently finds a subspace V so that f(x) is close to a function of the projection of x onto V, which can then be found by brute-force. Conversely, for functions for which these conditional moments do not necessarily help in finding better subspaces, we prove an SQ lower bound providing evidence that no efficient algorithm exists. As concrete applications of our general algorithm, we provide significantly faster noise-tolerant learners for two well-studied concept classes: •Multiclass Linear Classifiers A multiclass linear classifier is any function f: ℝ d → [K] of the form f(x) = argmax i∈[K] (w (i) •x+t i ), where w (i) ∈ ℝ d and t i ∈ ℝ. We give a constant-factor approximate agnostic learner for this class, i. e. , an algorithm that achieves 0-1 error O(OPT)+ϵ. Our algorithm has sample complexity N = O(d)2 poly(K/ϵ) and computational complexity poly(N). This is the first constant-factor agnostic learner for this class whose complexity is a fixed-degree polynomial in d. In the agnostic model, it was previously known that achieving error OPT+ϵ requires time d poly(1/ϵ), even for K = 2. Perhaps surprisingly, we prove an SQ lower bound showing that achieving error OPT+ϵ, for ϵ = 1/poly(K), incurs complexity d Ω(K) even for the simpler case of Random Classification Noise. •Intersections of Halfspaces An intersection of K halfspaces is any function f: ℝ d → {±1} such that there exist K halfspaces h i (x) with f(x) = 1 if and only if h i (x) = 1 for all i ∈ [K]. We give an approximate agnostic learner for this class achieving 0-1 error $K\tilde O({\text{OPT}}) + \varepsilon $. Our algorithm has sample complexity N = O(d 2 )2 poly(K/ϵ) and computational complexity poly(N). This is the first agnostic learner for this class with near-optimal dependence on OPT in its error, whose complexity is a fixed-degree polynomial in d. Previous algorithms either achieved significantly worse error guarantees, or incurred d poly(1/ϵ) time (even for K = 2). Furthermore, we show that in the presence of random classification noise, the complexity of our algorithm is significantly better, scaling polynomially with 1/ϵ.

NeurIPS Conference 2025 Conference Paper

Robustly Learning Monotone Single-Index Models

• Puqian Wang
• Nikos Zarifis
• Ilias Diakonikolas
• Jelena Diakonikolas

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 contribution is the first computationally efficient algorithm for this learning task, achieving a constant factor approximation, that succeeds for the class of {\em all} monotone activations with bounded moment of order $2 + \zeta, $ for $\zeta > 0. $ This class in particular includes all monotone Lipschitz functions and even discontinuous functions like (possibly biased) halfspaces. Prior work for the case of unknown activation either does not attain constant factor approximation or succeeds for a substantially smaller family of activations. The main conceptual novelty of our approach lies in developing an optimization framework that steps outside the boundaries of usual gradient methods and instead identifies a useful vector field to guide the algorithm updates by directly leveraging the problem structure, properties of Gaussian spaces, and regularity of monotone functions.

NeurIPS Conference 2024 Conference Paper

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

• Ilias Diakonikolas
• Nikos Zarifis

We study the problem of PAC learning $\gamma$-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be $\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. Prior computationally efficient algorithms for the problem incur sample complexity $\tilde{O}(1/(\gamma^4 \epsilon^3))$ and achieve 0-1 error of $\eta+\epsilon$, where $\eta<1/2$ is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on $1/\epsilon$ is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity $\widetilde{\Theta}(1/(\gamma^2 \epsilon^2))$, nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.

FOCS Conference 2024 Conference Paper

Agnostically Learning Multi-Index Models with Queries

• Ilias Diakonikolas
• Daniel M. Kane
• Vasilis Kontonis
• Christos Tzamos
• Nikos Zarifis

We study the power of query access for the fundamental task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels of the examples and the goal is to compute a hypothesis that is competitive with the best-fit function in a known class, i. e. , it achieves error opt $+\epsilon$, where opt is the error of the best function in the class. We focus on a general family of Multi-Index Models (MIMs), which are d-variate functions that depend only on few relevant directions, i. e. , have the form $g$ (Wx) for an unknown link function $g$ and a $k\times d$ matrix W. Multi-index models cover a wide range of commonly studied function classes, including real-valued function classes such as constant-depth neural networks with ReLU activations, and Boolean concept classes such as intersections of halfspaces. Our main result shows that query access gives significant runtime improvements over random examples for agnostically learning both real-valued and Boolean-valued MIMs. Under standard regularity assumptions for the link function (namely, bounded variation or surface area), we give an agnostic query learner for MIMs with running time $O(k)^{\text{poly}(1/\epsilon}$ ) poly $(d)$. In contrast, algorithms that rely only on random labeled examples inherently require $d^{\text{poly}(1/\epsilon}$ samples and runtime, even for the basic problem of agnostically learning a single ReLU or a halfspace. As special cases of our general approach, we obtain the following results: •For the class of depth-ℓ, width-S ReLU networks on $\mathbb{R}^{d}$, our agnostic query learner runs in time poly $(d)2^{\text{poly}(\ell S/\epsilon)}$. This bound qualitatively matches the runtime of an algorithm by [1] for the realizable PAC setting with random examples. •For the class of arbitrary intersections of $k$ halfspaces on $\mathbb{R}^{d}$, our agnostic query learner runs in time poly $(d)2^{\text{poly}(\log(k)/\epsilon)}$. Prior to our work, no improvement over the agnostic PAC model complexity (without queries) was known, even for the case of a single halfspace. In both these settings, we provide evidence that the $2^{\text{poly}(1/\epsilon)}$ runtime dependence is required for proper query learners, even for agnosticallylearning a single ReL U or halfspace. Our algorithmic result establishes a strong computational separation between the agnostic PAC and the agnostic PAC+Query models under the Gaussian distribution for a range of natural function classes. Prior to our work, no such separation was known for any natural concept class - even for the case of a single halfspace, for which it was an open problem posed by Feldman [2]. Our results are enabled by a general dimension-reduction technique that leverages query access to estimate gradients of (a smoothed version of) the underlying label function.

NeurIPS Conference 2024 Conference Paper

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 costlier than the others. Our main positive result is a new algorithm for reliable learning of Gaussian halfspaces on $\mathbb{R}^d$ with sample and computational complexity $d^{O(\log (\min\{1/\alpha, 1/\epsilon\}))}\min (2^{\log(1/\epsilon)^{O(\log (1/\alpha))}}, 2^{\mathrm{poly}(1/\epsilon)})$, where $\epsilon$ is the excess error and $\alpha$ is the bias of the optimal halfspace. We complement our upper bound with a Statistical Query lower bound suggesting that the $d^{\Omega(\log (1/\alpha))}$ dependence is best possible. Conceptually, our results imply a strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting.

ICML Conference 2024 Conference Paper

Robustly Learning Single-Index Models via Alignment Sharpness

• Nikos Zarifis
• Puqian Wang
• Ilias Diakonikolas
• Jelena Diakonikolas

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 approximation to the optimal loss, that succeeds under a range of distributions (including log-concave distributions) and a broad class of monotone and Lipschitz link functions. This is the first efficient constant factor approximate agnostic learner, even for Gaussian data and for any nontrivial class of link functions. Prior work for the case of unknown link function either works in the realizable setting or does not attain constant factor approximation. The main technical ingredient enabling our algorithm and analysis is a novel notion of a local error bound in optimization that we term alignment sharpness and that may be of broader interest.

NeurIPS Conference 2024 Conference Paper

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

• Puqian Wang
• Nikos Zarifis
• Ilias Diakonikolas
• Jelena Diakonikolas

A single-index model (SIM) is a function of the form $\sigma(\mathbf{w}^{\ast} \cdot \mathbf{x})$, where$\sigma: \mathbb{R} \to \mathbb{R}$ is a known link function and $\mathbf{w}^{\ast}$ is a hidden unit vector. We study the task of learning SIMs in the agnostic (a. k. a. adversarial label noise) model with respect to the $L^2_2$-loss under the Gaussian distribution. Our main result is a sample and computationally efficient agnostic proper learner that attains $L^2_2$-error of $O(\mathrm{OPT})+\epsilon$, where $\mathrm{OPT}$ is the optimal loss. The sample complexity of our algorithm is $\tilde{O}(d^{\lceil k^{\ast}/2\rceil}+d/\epsilon)$, where $k^{\ast}$ is the information-exponent of $\sigma$ corresponding to the degree of its first non-zero Hermite coefficient. This sample bound nearly matches known CSQ lower bounds, even in the realizable setting. Prior algorithmic work in this setting had focused on learning in the realizable case or in the presence of semi-random noise. Prior computationally efficient robust learners required significantly stronger assumptions on the link function.

STOC Conference 2024 Conference Paper

Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs

• Ilias Diakonikolas
• Daniel M. Kane
• Vasilis Kontonis
• Sihan Liu
• Nikos Zarifis

NeurIPS Conference 2023 Conference Paper

Efficient Testable Learning of Halfspaces with Adversarial Label Noise

• Ilias Diakonikolas
• Daniel Kane
• Vasilis Kontonis
• Sihan Liu
• Nikos Zarifis

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 introduced testable learning model, one is required to produce a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data. Our tester-learner runs in time $\text{poly}(d/\epsilon)$ and outputs a halfspace with misclassification error $O(\text{opt})+\epsilon$, where $\text{opt}$ is the 0-1 error of the best fitting halfspace. At a technical level, our algorithm employs an iterative soft localization technique enhanced with appropriate testers to ensure that the data distribution is sufficiently similar to a Gaussian. Finally, our algorithm can be readily adapted to yield an efficient and testable active learner requiring only $d ~ \text{polylog}(1/\epsilon)$ labeled examples.

NeurIPS Conference 2023 Conference Paper

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

• Ilias Diakonikolas
• Jelena Diakonikolas
• Daniel Kane
• Puqian Wang
• Nikos Zarifis

We study the problem of learning general (i. e. , not necessarily homogeneous) halfspaces with Random Classification Noise under the Gaussian distribution. We establish nearly-matching algorithmic and Statistical Query (SQ) lower bound results revealing a surprising information-computation gap for this basic problem. Specifically, the sample complexity of this learning problem is $\widetilde{\Theta}(d/\epsilon)$, where $d$ is the dimension and $\epsilon$ is the excess error. Our positive result is a computationally efficient learning algorithm with sample complexity$\tilde{O}(d/\epsilon + d/\max(p, \epsilon))^2)$, where $p$ quantifies the bias of the target halfspace. On the lower bound side, we show that any efficient SQ algorithm (or low-degree test)for the problem requires sample complexity at least $\Omega(d^{1/2}/(\max(p, \epsilon))^2)$. Our lower bound suggests that this quadratic dependence on $1/\epsilon$ is inherent for efficient algorithms.

ICML Conference 2023 Conference Paper

Robustly Learning a Single Neuron via Sharpness

• Puqian Wang
• Nikos Zarifis
• Ilias Diakonikolas
• Jelena Diakonikolas

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 family of activations including ReLUs, approximates the optimal $L_2^2$-error within a constant factor. Notably, our algorithm succeeds under much milder distributional assumptions compared to prior work. The key ingredient enabling our results is a novel connection to local error bounds from optimization theory.

ICML Conference 2022 Conference Paper

Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent

• Ilias Diakonikolas
• Vasilis Kontonis
• Christos Tzamos
• Nikos Zarifis

We study the problem of learning general {—} i. e. , not necessarily homogeneous {—} halfspaces with adversarial label noise under the Gaussian distribution. Prior work has provided a sophisticated polynomial-time algorithm for this problem. In this work, we show that the problem can be solved directly via online gradient descent applied to a sequence of natural non-convex surrogates. This approach yields a simple iterative learning algorithm for general halfspaces with near-optimal sample complexity, runtime, and error guarantee. At the conceptual level, our work establishes an intriguing connection between learning halfspaces with adversarial noise and online optimization that may find other applications.

STOC Conference 2022 Conference Paper

Learning general halfspaces with general Massart noise under the Gaussian distribution

• Ilias Diakonikolas
• Daniel M. Kane
• Vasilis Kontonis
• Christos Tzamos
• Nikos Zarifis

We study the problem of PAC learning halfspaces on ℝ d with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the label of each point x with unknown probability η( x ) ≤ η, for some parameter η ∈ [0,1/2]. The goal is to find a hypothesis with misclassification error of OPT + є, where OPT is the error of the target halfspace. This problem had been previously studied under two assumptions: (i) the target halfspace is homogeneous (i.e., the separating hyperplane goes through the origin), and (ii) the parameter η is strictly smaller than 1/2. Prior to this work, no nontrivial bounds were known when either of these assumptions is removed. We study the general problem and establish the following: [leftmargin = *] For η <1/2, we give a learning algorithm for general halfspaces with sample and computational complexity d O η (log(1/γ)) poly (1/є), where γ max{є, min{ Pr [ f ( x ) = 1], Pr [ f ( x ) = −1]} } is the “bias” of the target halfspace f . Prior efficient algorithms could only handle the special case of γ = 1/2. Interestingly, we establish a qualitatively matching lower bound of d Ω(log(1/γ)) on the complexity of any Statistical Query (SQ) algorithm. For η = 1/2, we give a learning algorithm for general halfspaces with sample and computational complexity O є (1) d O (log(1/є)) . This result is new even for the subclass of homogeneous halfspaces; prior algorithms for homogeneous Massart halfspaces provide vacuous guarantees for η=1/2. We complement our upper bound with a nearly-matching SQ lower bound of d Ω(log(1/є) ) , which holds even for the special case of homogeneous halfspaces. Taken together, our results qualitatively characterize the complexity of learning general halfspaces with general Massart noise under Gaussian marginals. Our techniques rely on determining the existence (or non-existence) of low-degree polynomials whose expectations distinguish Massart halfspaces from random noise.

STOC Conference 2021 Conference Paper

Efficiently learning halfspaces with Tsybakov noise

• Ilias Diakonikolas
• Daniel M. Kane
• Vasilis Kontonis
• Christos Tzamos
• Nikos Zarifis

We study the problem of PAC learning homogeneous halfspaces with Tsybakov noise. In the Tsybakov noise model, the label of every example is independently flipped with an adversarially controlled probability that can be arbitrarily close to 1/2 for a fraction of the examples. We give the first polynomial-time algorithm for this fundamental learning problem. Our algorithm learns the true halfspace within any desired accuracy and succeeds under a broad family of well-behaved distributions including log-concave distributions.

ICML Conference 2021 Conference Paper

Learning Online Algorithms with Distributional Advice

• Ilias Diakonikolas
• Vasilis Kontonis
• Christos Tzamos
• Ali Vakilian
• Nikos Zarifis

We study the problem of designing online algorithms given advice about the input. While prior work had focused on deterministic advice, we only assume distributional access to the instances of interest, and the goal is to learn a competitive algorithm given access to i. i. d. samples. We aim to be competitive against an adversary with prior knowledge of the distribution, while also performing well against worst-case inputs. We focus on the classical online problems of ski-rental and prophet-inequalities, and provide sample complexity bounds for the underlying learning tasks. First, we point out that for general distributions it is information-theoretically impossible to beat the worst-case competitive-ratio with any finite sample size. As our main contribution, we establish strong positive results for well-behaved distributions. Specifically, for the broad class of log-concave distributions, we show that $\mathrm{poly}(1/\epsilon)$ samples suffice to obtain $(1+\epsilon)$-competitive ratio. Finally, we show that this sample upper bound is close to best possible, even for very simple classes of distributions.

TCS Journal 2021 Journal Article

Reallocating multiple facilities on the line

• Dimitris Fotakis
• Loukas Kavouras
• Panagiotis Kostopanagiotis
• Philip Lazos
• Stratis Skoulakis
• Nikos Zarifis

We study the K-Facility Reallocation problem on the real line, where we maintain K facility locations over T stages, based on the stage-dependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. The K-Facility Reallocation problem was introduced by de Keijzer and Wojtczak, where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider the online K-Facility Reallocation problem, where the algorithm becomes aware of agent locations in a stage-by-stage fashion. By exploiting an interesting connection to the classical K-server problem, we present a constant-competitive algorithm for K = 2 facilities.

NeurIPS Conference 2020 Conference Paper

Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals

• Ilias Diakonikolas
• Daniel Kane
• Nikos Zarifis

We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. In the former problem, given labeled examples $(\bx, y)$ from an unknown distribution on $\R^d \times \{ \pm 1\}$, whose marginal distribution on $\bx$ is the standard Gaussian and the labels $y$ can be arbitrary, the goal is to output a hypothesis with 0-1 loss $\opt+\eps$, where $\opt$ is the 0-1 loss of the best-fitting halfspace. In the latter problem, given labeled examples $(\bx, y)$ from an unknown distribution on $\R^d \times \R$, whose marginal distribution on $\bx$ is the standard Gaussian and the labels $y$ can be arbitrary, the goal is to output a hypothesis with square loss $\opt+\eps$, where $\opt$ is the square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lower bounds of $d^{\poly(1/\eps)}$ for both of these problems. Our SQ lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.

NeurIPS Conference 2020 Conference Paper

Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

• Ilias Diakonikolas
• Vasilis Kontonis
• Christos Tzamos
• Nikos Zarifis

We study the problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model. For a broad family of structured distributions, including log-concave distributions, we show that non-convex SGD efficiently converges to a solution with misclassification error $O(\opt)+\eps$, where $\opt$ is the misclassification error of the best-fitting halfspace. In sharp contrast, we show that optimizing any convex surrogate inherently leads to misclassification error of $\omega(\opt)$, even under Gaussian marginals.

IJCAI Conference 2019 Conference Paper

Reallocating Multiple Facilities on the Line

• Dimitris Fotakis
• Loukas Kavouras
• Panagiotis Kostopanagiotis
• Philip Lazos
• Stratis Skoulakis
• Nikos Zarifis

We study the multistage K-facility reallocation problem on the real line, where we maintain K facility locations over T stages, based on the stage-dependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. K-facility reallocation problem was introduced by (B. D. Kaijzer and D. Wojtczak, IJCAI 2018), where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider online K-facility reallocation, where the algorithm becomes aware of agent locations in a stage-by stage fashion. By exploiting an interesting connection to the classical K-server problem, we present a constant-competitive algorithm for K = 2 facilities.