{"id":"arxiv/2605.13426","url":"https://arxiv.org/abs/2605.13426","tags":["cs.LG","math.AG"],"score":0,"title":"Strategic PAC Learnability via Geometric Definability","domain":"cs.LG","source":"arxiv","authors":["Yuval Filmus","Shay Moran","Elizaveta Nesterova","Nir Rosenfeld","Alexander Shlimovich"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-13","reactions":{}}