Efficient Learning Under Malicious Noise

31 concepts19 papers2 proposals

In standard machine learning, we often assume that noise is "nice"—perhaps a few labels are flipped at random, or features are slightly blurred by Gaussian jitter. However, real-world data is frequently subject to malicious noise, a model where an omniscient adversary can inspect the learning algorithm and strategically corrupt a fraction of both the input features and the target labels.

This research direction focuses on designing algorithms that remain accurate even when an adversary is actively trying to mislead them. The challenge is not just statistical, but computational: how do we find the "true" signal when the outliers are not just random errors, but coordinated attacks?

The Malicious Noise Model

The malicious noise model, formalized in early work on Agnostic Learning by Sellie et al., represents one of the harshest environments for a learner. Unlike simple label noise, where only the output $y$ is corrupted, malicious noise allows an adversary to modify the feature vector $x$ as well.

As Shen notes in Sample-Optimal PAC Learning of Halfspaces with Malicious Noise, this creates a fundamental stability problem. An adversary can strategically place outliers to distort the geometry of the data distribution, shifting the perceived decision boundary. The goal of this field is to achieve an error rate that scales linearly with the noise rate $\eta$, ideally reaching the information-theoretic limit of $2\eta + \epsilon$.

Why Convex Optimization Fails

A natural first instinct is to use standard tools like Support Vector Machines (SVMs) or Logistic Regression. However, Long et al. proved a significant negative result: any algorithm that minimizes a convex loss function is mathematically incapable of tolerating high levels of malicious noise. Convex losses are too sensitive to outliers; a single maliciously placed point far from the boundary can exert enough "pull" to ruin the entire model.

To overcome this, researchers have turned to non-convex strategies, such as localization. Instead of looking at all data points equally, algorithms like those proposed by Diakonikolas et al. use Online Gradient Descent on a sequence of "localized" surrogate losses. By focusing only on points near the current decision boundary, the learner can ignore distant, malicious outliers that would otherwise skew the results.

Algorithmic Breakthroughs in Robustness

Recent progress has moved from theoretical possibility to computational efficiency. Several key mechanisms have emerged:

  • Matrix Multiplicative Weights and Localization: Shen demonstrated in PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time that combining margin-based localization with matrix weights allows for near-optimal noise tolerance in nearly linear time.
  • Sum-of-Squares (SoS) Framework: For regression tasks, Klivans et al. leveraged the SoS hierarchy to create polynomial-time algorithms that are resilient to corruptions in both features and labels, provided the underlying data distribution is "certifiably hypercontractive" (like a Gaussian).
  • Outlier Removal via Semidefinite Programming (SDP): To handle high-dimensional sparse data, Shen et al. introduced techniques that use SDP to identify and prune malicious samples before they can influence the learning process.

Beyond Linear Boundaries

While much of the early success focused on halfspaces (linear classifiers), the field has expanded to more complex models:

  1. Polynomial Threshold Functions (PTFs): Learning non-linear boundaries is significantly harder because noise interacts with higher-order feature correlations. Zeng et al. and Diakonikolas et al. have developed methods to robustly learn these functions by decomposing complex polynomials into more manageable, "non-singular" components.
  2. Stochastic Decision Trees: Blanc et al. showed that even for complex structures like decision trees, it is possible to reach the information-theoretic floor of $2\eta$ error by approximating them with simpler "stochastic-leaf" models.
  3. Neural Networks: Interestingly, Kera et al. suggest that adversarial noise isn't always purely destructive. They argue that wide two-layer networks can actually learn the underlying clean decision boundary by training only on mislabeled adversarial perturbations, suggesting these perturbations contain meaningful feature information.

The Computational Hardness of Robustness

Is it always possible to be robust? Degwekar et al. frame robust classification as a decoding task. If we view the clean data as a signal and the adversary as a noisy channel, the learner's job is to decode the original message.

They propose a "win-win" theorem: either we can find efficient algorithms for robust learning, or the problem is so fundamentally hard that we can use it to build secure cryptographic primitives, like one-way functions. This connection highlights that the limits of our ability to learn from corrupted data are deeply tied to the core questions of computational complexity.

Key Foundational Work

Learning large-margin halfspaces with more malicious noise (2011) — contributed 1 concept elements to this direction.
Toward Efficient Agnostic Learning (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adversarial_data_corruption_e925f77a,
  title = {adversarial data corruption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-data-corruption/rdr_e925f77a2cdd4fe6af267d00f37f93ec},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_adversarial_data_corruption_e925f77a_v1,
  title = {adversarial data corruption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-data-corruption/rdr_e925f77a2cdd4fe6af267d00f37f93ec/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake