Strategic PAC Learnability via Geometric Definability

Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich[1ex] · 2026

Read Strategic PAC Learnability via Geometric Definability by Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich[1ex] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13426.txt.

Introduction

Yuval Filmus and four colleagues study whether strategic classification can stay learnable when people alter features at a cost to sway a classifier. The authors first show guarantees fail in general: a VC dimension 1 class on the real line can induce an infinite VC class. Strategic behaviour can thus make an easy learning problem non-learnable. They then require hypotheses and costs to be definable by first-order formulas over the real exponential field. Under that assumption, learnability is preserved, with sample complexity set by formula size.

Catalog record

CREATORYuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich[1ex]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130868
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13426

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strategic PAC Learnability via Geometric Definability Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich[1ex] Abstract 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 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 ℝ 𝚎𝚡𝚙 \mathbb{R}_{\mathtt{exp}} . 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 \ell_{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. 1 1 footnotetext: Faculty of Mathematics, Technion – Israel Institute of Technology. 2 2 footnotetext: Faculty of Computer Science, Technion – Israel Institute of Technology. 3 3 footnotetext: Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology. 4 4 footnotetext: Google Research. † † footnotetext: Emails: [email protected] , [email protected] , [email protected] , [email protected] , [email protected] 1 Introduction The field of strategic classification studies learning in settings where individuals can modify their features in response to a classifier, at some cost, in order to obtain a favorable outcome [ 17 , 27 ] . For example, consider a university that designs a rule for admissions based on applicants’ features such as grades, test scores, or extracurricular activities. Once this rule is made public, prospective students may adapt their behavior to meet the requirements — by studying harder, retaking exams, or investing in private tutoring. While such adaptations may improve their chances of admission, they also change the distribution of inputs seen by the classifier. The university’s true goal, however, is to admit students who will successfully graduate and contribute to society, rather than those who merely optimize for the admission rule. This illustrates an inherent tension between systems that aim to make accurate predictions and individuals who benefit from being classified as positive. Applications of this kind arise in many domains, including loan approval, hiring, university admissions, scholarships, social benefit programs, and medical eligibility. The central objective in strategic classification is therefore to learn a classifier that is accurate under such strategic behavior, i.e., achieves strategic robustness. A fundamental question in learning theory is which hypothesis classes are learnable, and how many samples are needed. Despite over a decade of sustained research, the implications of strategic behavior on learnability and sample complexity remain poorly understood. This gap persists even in simple and well-studied settings, where the cost function is uniform across individuals, feature manipulation is unconstrained by causal relationships, and the classifier is fully known to the agents. A natural intuition is that if a hypothesis class is learnable and the cost function is “simple,” then the induced strategic class should also be learnable, since local input perturbations are unlikely to cause significant statistical degradation. Indeed, the literature provides several positive results supporting this view: linear classes with semi-norm costs [ 57 , 47 ] ; polytope classes, piecewise-linear classes, and classes closed under input scaling with \ell_{p} costs [ 50 ] ; and general classes with separable costs [ 27 ] or discrete manipulation graphs [ 18 ] . However, these results stop short of resolving the basic general question: does learnability of a hypothesis class, together with a well-behaved cost structure, imply learnability under strategic behavior? Combinatorial simplicity is not enough. Our first result shows that, in full generality, the answer to the above question is negative. We consider perhaps the simplest possible setting: a hypothesis class with VC dimension 1 , defined over the real line, together with a uniform and highly regular cost structure in which each point x can move within distance at most 1 (i.e., its neighborhood is an interval of radius 1 around x ). Despite this extreme simplicity, we construct a class for which the induced strategic class is not learnable. This result demonstrates that learnability is not preserved under strategic behavior, even under minimal combinatorial complexity and very simple cost structures. Geometric structure restores learnability. The negative result above suggests that strategic learnability requires structure beyond combinatorial simplicity. We therefore turn to a broad and well-studied family of learning problems with geometric structure . By geometric, we mean that the instance space is \mathbb{R}^{d} , and that both the hypothesis class \mathcal{H} and the cost function are described using a fixed collection of basic operations, such as the arithmetic operations, comparison operators, and functions such as \exp and \log . This setting captures many standard classes in machine learning, including linear classifiers, polynomial threshold functions, intersections of halfspaces, decision trees with polynomial decision nodes, neural networks with common activation functions, as well as cost functions based on distances such as \ell_{p} norms or KL divergence. Within this framework, we focus on a basic and canonical strategic setting: each point x is associated with a cost-induced neighborhood N_{x} to which it can move freely, but cannot move outside of it—i.e., N_{x} is the set of points to which moving is potentially cost-effective. Our goal is to understand when the induced strategic class is learnable, and to characterize its sample complexity. Despite its simplicity, this setting is already non-trivial, and serves as a natural platform for developing our approach. Moreover, we believe the techniques we introduce extend beyond this setting to more general models of strategic behavior. A key feature of strategic classification is that it naturally introduces existential quantification . Indeed, for a hypothesis h , let h^{\prime} denote the induced strategic hypothesis. An input x is labeled positively after adaptation if and only if there exists a point x^{\prime} in its neighborhood that is labeled positively by h : h^{\prime}(x)=+1\iff\exists x^{\prime}\text{ s.t. }(x^{\prime}\in N_{x})\wedge(h(x^{\prime})=+1). (1) Thus, the induced strategic hypotheses are defined by formulas that include existential quantifiers. This observation plays a central role in our approach. To formalize our geometric setting, we model hypotheses and neighborhoods as being definable by first-order formulas over the reals. As a first intuition, this can be viewed as specifying a procedure that, given h\in\mathcal{H} and points x,x^{\prime} , determines whether h(x)=1 and whether x^{\prime} lies in the neighborhood of x using only the allowed operations (i.e., arithmetic operations, comparisons, \exp , and \log ). However, this intuition is not entirely accurate: allowing quantifiers extends this framework beyond purely algorithmic descriptions. For example, a formula of the form \psi(x)=\exists x^{\prime}\,\varphi(x,x^{\prime}) can express properties that require searching for

Read the complete text