🤖 machine learning

Strategic PAC Learnability via Geometric Definability

This paper demonstrates that while strategic behavior can render even simple hypothesis classes unlearnable, imposing a geometric definability assumption based on first-order formulas over $\mathbb{R}_{\mathtt{exp}}$ restores PAC learnability by ensuring the induced strategic complexity remains controlled.

Original authors: Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a university admissions officer trying to decide who gets in. You have a set of rules (a "classifier") based on grades and test scores. But here's the catch: applicants aren't just passive data points; they are smart, strategic players. If they know your rules, they might study harder, retake a test, or even fake a hobby just to cross the line and get accepted.

This is the world of Strategic Classification. The big question researchers ask is: If we can learn a good rule for normal people, can we still learn a good rule when people are actively trying to game the system?

This paper, "Strategic PAC Learnability via Geometric Definability," tackles that question with a mix of bad news, good news, and a very specific mathematical "safety net."

The Bad News: Strategy Can Break Everything

The authors start with a surprising discovery. You might think that if your learning problem is simple (like sorting people into "Yes" or "No" based on a single number), it should stay simple even if people try to cheat.

The Analogy: Imagine you are playing a game where you have to guess a secret number between 0 and 10. It's easy. But now, imagine that before you guess, the person hiding the number is allowed to move it up or down by 1 unit. You might think, "No big deal, I'll just guess a range."

The paper proves that in some cases, this tiny ability to move the number turns a simple game into an impossible one. They constructed a scenario where the original rule was incredibly simple (so simple it had a "complexity score" of 1), but once the applicants were allowed to move their features slightly (like moving within a radius of 1), the learning problem became infinitely complex.

The Takeaway: Just because a problem looks simple and the "cost" of cheating is low, it doesn't mean the problem remains learnable. Strategic behavior can turn an easy task into a broken one.

The Good News: Geometry Saves the Day

So, is all hope lost? No. The authors realized that the "bad" examples they built were mathematically "wild" and artificial. They looked for a way to say, "Okay, let's only look at problems that follow the normal rules of geometry and arithmetic."

They introduced a concept called Geometric Definability.

The Analogy: Think of the world of math as a giant toolbox.

The "Wild" Toolbox: Contains tools that can draw infinite, wiggly, repeating patterns (like a sine wave that never stops). These are the tools that break learning.
The "Tame" Toolbox: Contains only standard tools: addition, subtraction, multiplication, division, and maybe a few special ones like exponentials ( $e^x$ ) and logarithms ( $\log x$ ). These tools can draw circles, lines, curves, and shapes, but they can't draw those infinite, crazy, repeating patterns.

The paper argues that if your rules and your "cheating costs" can be described using only the Tame Toolbox (mathematicians call this the structure $\mathbb{R}_{exp}$ ), then learning is saved.

If your system is built with these "tame" geometric rules:

It remains learnable. You can still find a good classifier.
We can count the cost. They provide formulas to calculate exactly how many examples (samples) you need to learn the rule. The more complex the formula describing your rules, the more data you need, but it's always a finite, manageable number.

The "How-To" Guide: From Theory to Numbers

The paper doesn't just say "it works"; it gives you a ruler to measure how well it works.

Qualitative Guarantee: If your rules are "tame" (definable in $\mathbb{R}_{exp}$ ), you are guaranteed that learning is possible.
Quantitative Guarantee: If your rules are even simpler (using only polynomials, no exponentials), the authors give you a specific formula to calculate the exact number of students you need to interview to get a perfect admissions rule.
The "Existential" Shortcut: They show that many real-world problems (like measuring distance between people or comparing probability distributions) naturally fit into a specific type of "tame" formula called an "existential formula." For these, they provide explicit, sharp bounds on how much data is needed.

Real-World Examples They Cover

The authors show that this isn't just abstract math; it covers many things we actually use:

Distance: If "cheating" means moving your features a certain distance (like Euclidean distance or $L_p$ norms), this works.
Information Theory: If "cheating" involves changing a probability distribution (using KL divergence), this works.
Neural Networks: If your classifier is a neural network with standard activation functions (like ReLU or Sigmoid), and the cost of changing inputs is "tame," the system is learnable.

The Limitations (The "Fine Print")

The paper is honest about where this safety net fails.

Infinite Loops: If your rules involve infinite, repeating patterns (like a sine wave that goes on forever), the "tame" math doesn't apply, and the problem might be unlearnable again.
Integration: If the cost of cheating is defined by a complex integral (a sum over an infinite range) that doesn't simplify into a neat formula, the current method doesn't cover it.

Summary

In short, the paper says:

Don't assume strategy is safe. A simple learning problem can become impossible if people try to game the system in weird ways.
But, if the rules are "geometrically tame," you are safe. If your rules and the cost of cheating can be described using standard math operations (plus $e$ and $\log$ ), then the problem remains solvable.
We can measure the difficulty. The paper gives you the math to calculate exactly how much data you need to learn these strategic rules, turning a vague worry into a concrete calculation.

It's a bridge between the chaotic reality of strategic behavior and the orderly world of mathematical learning theory, showing us exactly where the bridge holds strong and where it might collapse.

Technical Summary: Strategic PAC Learnability via Geometric Definability

Problem Statement
Strategic classification addresses learning scenarios where individuals modify their features at a cost to influence a classifier's decision. A fundamental question in this field is whether the learnability of an underlying hypothesis class $\mathcal{H}$ is preserved when individuals act strategically. Specifically, does the induced strategic hypothesis class $\mathcal{H}^N$ (where $N$ represents the cost-induced neighborhood relation) remain PAC-learnable, and how does its sample complexity relate to the complexity of $\mathcal{H}$ and the cost structure?

Prior work has established positive results for specific settings, such as linear classifiers with norm costs or classes closed under input scaling. However, the general relationship between combinatorial simplicity (e.g., low VC dimension) and strategic learnability remained unresolved. The paper investigates whether "simple" cost structures and hypothesis classes are sufficient to guarantee that strategic behavior does not render a learning problem intractable.

Methodology and Framework
The authors employ a dual approach: demonstrating the failure of learnability in general combinatorial settings and restoring it through geometric definability assumptions rooted in model theory.

Negative Result (Combinatorial Simplicity is Insufficient):
The paper constructs a counterexample showing that strategic behavior can destroy learnability even in the simplest settings. They define a hypothesis class $\mathcal{H}$ over the real line $\mathbb{R}$ with VC dimension 1 and a uniform interval neighborhood system (points can move within a fixed radius $r$ ). Despite the minimal complexity of both the class and the cost structure, the induced strategic class $\mathcal{H}^N$ is shown to have infinite VC dimension, rendering it non-PAC-learnable. This construction relies on encoding arbitrary subsets of indices into disjoint intervals, allowing the strategic transformation to shatter arbitrarily large finite sets.
Positive Result (Geometric Definability):
To overcome the negative result, the authors introduce a structural assumption: Geometric Definability. They model both the hypothesis class and the neighborhood relation using first-order formulas over the structure $\mathbb{R}_{\exp}$ (the real field expanded with the exponential function).
- $\mathbb{R}_{\exp}$ -Definability: Hypotheses and neighborhoods are defined by formulas involving arithmetic operations ( $+, \cdot$ ), comparisons ( $<, =$ ), and the exponential function ( $\exp$ ), along with logarithms (via $\exp$ ). This captures a broad range of natural classes, including linear classifiers, polynomial threshold functions, neural networks with standard activations, and cost functions based on $\ell_p$ norms, Wasserstein distance, and KL divergence.
- Strategic Transformation as Existential Quantification: The induced strategic hypothesis $h^N(x) = 1$ if and only if $\exists x' \in N_x$ such that $h(x') = 1$ . This introduces an existential quantifier to the defining formula.
- Model-Theoretic Tools: The analysis leverages the fact that $\mathbb{R}_{\exp}$ is an o-minimal structure (Wilkie's theorem). In o-minimal structures, definable sets admit finite cell decompositions and have polynomially bounded growth functions. The authors utilize results from tame topology and effective cell decomposition (specifically for restricted Pfaffian sets) to bound the growth function of the induced strategic class.

Key Contributions and Results

Strategic Non-Learnability:
The paper proves that strategic behavior can turn a learnable problem (VC dimension 1) into a non-learnable one (infinite VC dimension) even under simple interval neighborhoods. This demonstrates that combinatorial simplicity alone is insufficient to guarantee strategic learnability.
Qualitative Learnability via $\mathbb{R}_{\exp}$ :
Main Theorem 2 establishes that if both the hypothesis class $\mathcal{H}$ and the neighborhood system $N$ are definable in $\mathbb{R}_{\exp}$ , then the induced strategic class $\mathcal{H}^N$ is PAC-learnable. The sample complexity is controlled by the number of parameters $k$ used in the defining formulas. Specifically, the growth function $\Pi_{\mathcal{H}^N}(m)$ is bounded by $C m^k$ , implying finite VC dimension. This result relies on the o-minimality of $\mathbb{R}_{\exp}$ and the polynomial growth theorem for definable families.
Quantitative Bounds (Semialgebraic Case):
Main Theorem 3 provides explicit, constructive bounds for the case where definitions are restricted to the language of the real field $\mathbb{R}$ (quantifier-free formulas involving polynomials, i.e., semialgebraic sets). By applying quantitative quantifier elimination (Tarski-Seidenberg), the authors derive explicit bounds on the VC dimension and sample complexity in terms of the description complexity $D$ (number of polynomials and their degrees).
- Result: $VC(\mathcal{H}^N) = O(k^2 l \log D)$ and sample complexity scales similarly.
Quantitative Bounds (Existential $\mathbb{R}_{\exp}$ Case):
Main Theorem 4 extends the quantitative analysis to the full $\mathbb{R}_{\exp}$ setting, restricted to existential formulas ( $\Sigma_1$ ). This covers many natural strategic settings (e.g., $\ell_p$ balls, Earth Mover Distance) where the neighborhood relation is defined by an existential quantifier.
- The authors define "format" ( $F$ ) and "degree" ( $D$ ) for these formulas.
- Result: $VC(\mathcal{H}^N) = O_F(\log D)$ and sample complexity is $O\left(\frac{k \log(1/\varepsilon) + \gamma(F) \log D + \log(1/\delta)}{\varepsilon}\right)$ , where $\gamma$ is an explicitly computable function.
- The proof utilizes effective cell decomposition theorems for restricted Pfaffian structures to handle the exponential function.

Significance and Claims
The paper claims to resolve the tension between combinatorial simplicity and strategic learnability by identifying geometric tameness as the crucial factor.

Limitation of Combinatorial Measures: The work demonstrates that low VC dimension of the base class does not imply learnability under strategic manipulation; the structure of the cost function and the hypothesis class matters fundamentally.
Restoration via Definability: By restricting attention to "tame" geometric classes (definable in $\mathbb{R}_{\exp}$ ), the paper shows that strategic learnability is restored. The complexity of the strategic class is controlled by the logical complexity (number of parameters, format, and degree) of the defining formulas rather than the raw combinatorial complexity of the induced class.
Scope: The framework captures a wide array of practical settings, including polynomial classifiers, decision trees, neural networks with common activations, and various distance metrics ( $\ell_p$ , KL, Wasserstein).
Limitations: The authors note that their positive results rely on the "tameness" of the structures. Neighborhoods with unbounded oscillatory or periodic structures (e.g., defined by $\sin$ ) fall outside the $\mathbb{R}_{\exp}$ framework and can lead to non-learnability. Furthermore, the quantitative bounds for $\mathbb{R}_{\exp}$ are currently restricted to existential formulas; universal quantifiers are handled only qualitatively.

In summary, the paper establishes that while strategic behavior can catastrophically increase learning complexity in general, this pathology is avoided for a broad and natural class of geometric problems defined by first-order logic over the reals with exponentiation. The sample complexity of these problems is governed by the descriptive complexity of the underlying geometric definitions.