# Strategic PAC Learnability via Geometric Definability

arXiv: https://arxiv.org/abs/2605.13426 · HTML: https://mlsanity.com/paper/2605.13426/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 57 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 19 of 19)

- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification is Causal Modeling in Disguise](https://mlsanity.com/paper/1910.10362/) (2019)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Causal Strategic Linear Regression](https://mlsanity.com/paper/2002.10066/) (2020)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Strategic Classification with Non-Linear Classifiers](https://mlsanity.com/paper/2505.23443/) (2025)

## Abstract (arXiv)

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension 1 on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over ℝ_mathttexp. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including ℓp distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.