Computational Intractability of Adversarially Robust Learning

29 concepts20 papers1 proposal

In the classical theory of machine learning, if a problem is statistically learnable, we generally assume we can find a solution given enough data and compute. However, a growing body of research suggests that adversarial robustness breaks this assumption. Even when a robust classifier is guaranteed to exist and we have sufficient data to identify it, the actual process of finding that classifier is often computationally intractable.

This "existence-learnability gap" suggests that the vulnerability of modern neural networks to adversarial attacks may not be a failure of architecture or data volume, but a fundamental consequence of computational complexity.

The Statistical-Computational Gap

In standard PAC (Probably Approximately Correct) learning, the difficulty of a task is often measured by its sample complexity—how much data is needed to generalize. Cullina et al. extended this to the adversarial setting by introducing the Adversarial VC-dimension (AVC). They showed that while the data requirements for robust learning are often manageable, the optimization problem—minimizing the adversarial empirical risk—is frequently NP-hard.

This creates a paradox: we might have a dataset that contains a perfectly robust hypothesis, yet no efficient algorithm can locate it. Daniely et al. highlight that while any Empirical Risk Minimization (ERM) algorithm works for simple binary classification, the choice of ERM becomes critical and computationally fraught in more complex settings. In these cases, identifying a hypothesis that minimizes empirical risk becomes a bottleneck that theoretical learnability cannot bypass.

Robustness as a Computational Constraint

If robust classifiers exist, why do our models fail to find them? Bubeck et al. argue that adversarial vulnerability is a byproduct of computational constraints. Their analysis suggests that even when a robust classifier is information-theoretically learnable from a reasonable number of samples, the algorithmic effort required to navigate the optimization landscape may be practically impossible for modern systems.

This perspective is reinforced by Degwekar et al., who present a "win-win" theoretical result: either we can efficiently learn robust classifiers, or the inherent difficulty of doing so allows us to construct powerful cryptographic primitives like one-way functions. This implies that the hardness of robust learning is not just a nuisance, but a deep mathematical property tied to the foundations of computer science.

The Necessity of Improper Learning

One of the most surprising findings in this field involves the distinction between proper and improper learning. Proper learning requires the algorithm to output a model from the same class it started with (e.g., a linear classifier must return a linear classifier).

Montasser et al. proved that for many hypothesis classes, robust learning is only possible if we use improper learning rules. Standard methods like Robust Empirical Risk Minimization (RERM) can fail to generalize robustly even for simple classes where a robust solution is known to exist. However, as Raman et al. note, while improper learners can bridge the statistical gap, they are often theoretically complex and lack the computational efficiency needed for practical deployment.

Hardness Across Different Domains

The theme of intractability appears across various specific learning models:

  • Support Vector Machines (SVMs): Ding et al. proved that finding an optimal defense against poisoning attacks in SVMs is NP-complete, justifying the use of heuristic data-sanitization techniques like DBSCAN over exact optimization.
  • Polynomial Classifiers: Awasthi et al. showed that achieving absolute robustness for classifiers of degree two or higher is computationally intractable, mapping the problem to hard instances of quadratic programming.
  • Randomized Ensembles: Even when using randomization to boost security, Heredia et al. demonstrated that finding the optimal adversarial perturbation to defeat a mixture of classifiers remains an NP-hard problem.

The Cost of Verification and Defense

The difficulty extends beyond training to the evaluation of robustness itself. Cullen et al. found that the "robustness certificates" intended to guarantee safety can actually be weaponized to find vulnerabilities faster, because the gap between a certified lower bound and the actual nearest adversarial example is itself hard to compute.

Furthermore, Gourdeau et al. explored the limits of computable robust learning, discovering that a learner can be robustly learnable in a mathematical sense while being impossible to implement as a program that can calculate its own robust loss.

Ultimately, these papers suggest that the "adversarial arms race" is constrained by a fundamental imbalance: while finding some vulnerability is often easy for an attacker, finding the optimal defense or the most robust model is a computationally intractable task for the defender.

Key Foundational Work

PAC-learning in the presence of evasion adversaries (2018) — contributed 1 concept elements to this direction.
Multiclass Learnability and the ERM principle (2011) — 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_computational_complexity_of_robust_learn_ec20cfca,
  title = {computational complexity of robust learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-robust-learning/rdr_ec20cfcaeeb645759bfde6be05b3d59a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_robust_learn_ec20cfca_v1,
  title = {computational complexity of robust learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-robust-learning/rdr_ec20cfcaeeb645759bfde6be05b3d59a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake