Research map / Learning theory and algorithms / Sample complexity

Strategic PAC Learnability via Geometric Definability

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: PAC learnability theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows strategic (interval-neighborhood) expansion can make a VC-1 class non-learnable, then proves PAC learnability and explicit ERM/VC bounds for strategic classes when hypotheses and neighborhoods are definable in R_exp (o-minimal/tame geometry).

Problem

Whether learnability of a hypothesis class with a simple cost structure implies learnability of the induced strategic class, and how to bound the sample complexity of strategically induced classes.

Approach

Shows that finite VC dimension and simple uniform neighborhoods do not guarantee strategic learnability, then restores it by assuming both the hypothesis class and cost-induced neighborhood relation are first-order definable over the real exponential field, so the induced strategic class (an existential formula) has polynomially bounded growth function, with explicit bounds for semialgebraic and e

Key results

• There exists a VC-dimension-1 hypothesis class on R whose interval-neighborhood strategic class has infinite VC dimension for every radius r>0.
• Strategic classes definable in R_exp are PAC learnable, with ERM sample complexity O((k log(1/eps) + log(1/delta) + K)/eps) where K is a non-explicit constant.
• Under quantifier-free semialgebraic definitions, VCdim of the strategic class is O(k^2 l log D) with explicit ERM bounds.

Surprising findings

• Strategic response alone can turn a VC-dimension-1 class on the real line into one with infinite VC dimension, even under simple interval neighborhoods.
• Finite VC dimension of the base class is insufficient for strategic learnability even with simple uniform neighborhoods.

Limitations

• Constant K_{H,N} in the general R_exp theorem is non-constructive, relying on Wilkie's o-minimality proof.
• Quantitative bounds apply only to existential formulas; universal quantifiers and distributional (e.g., EMD over measures) neighborhoods are not covered.

Experimental setup

Metrics: VC dimension ERM sample complexity

Builds on: Johnson and Laskowski growth function bound for definable families Goldberg-Jerrum VC bound Sauer-Shelah-Perles lemma Basu-Pollack-Roy quantifier elimination

Closest papers by meaning

• One-Shot Strategic Classification Under Unknown Costs (ICML 2024 · similarity 0.86)
• Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.86)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.85)
• Strategic Classification with Non-Linear Classifiers (NeurIPS 2025 · similarity 0.85)
• Bayesian Strategic Classification (NeurIPS 2024 · similarity 0.85)
• On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.84)