# Strategic Classification with Non-Linear Classifiers

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 39 references that are in the map.
- First posted on arXiv 29 May 2025.

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

- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Causal Strategic Linear Regression](https://mlsanity.com/paper/2002.10066/) (2020)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Strategic Classification with Graph Neural Networks](https://mlsanity.com/paper/2205.15765/) (2022)
- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Performative Recommendation: Diversifying Content via Strategic Incentives](https://mlsanity.com/paper/2302.04336/) (2023)
- [Non-linear Welfare-Aware Strategic Learning](https://mlsanity.com/paper/2405.01810/) (2024)
- [Classification with Strategically Withheld Data](https://mlsanity.com/paper/2012.10203/) (2020)
- [Strategic Classification With Externalities](https://mlsanity.com/paper/2410.08032/) (2024)
- [The VC-dimension of k-vertex d-polytopes](https://mlsanity.com/paper/2004.04841/) (2020)

## Built on by (most cited first, 4 of 4)

- [Strategic PAC Learnability via Geometric Definability](https://mlsanity.com/paper/2605.13426/) (2026)
- [Ambiguous Strategic Classification](https://mlsanity.com/paper/2606.10137/) (2026)
- [Non-Linear Strategic Classification Made Practical](https://mlsanity.com/paper/2606.28204/) (2026)
- [Robust Strategic Classification under Decision-Dependent Cost Uncertainty](https://mlsanity.com/paper/2606.30136/) (2026)

## Abstract (arXiv)

In strategic classification, the standard supervised learning setting is extended to support the notion of strategic user behavior in the form of costly feature manipulations made in response to a classifier. While standard learning supports a broad range of model classes, the study of strategic classification has, so far, been dedicated mostly to linear classifiers. This work aims to expand the horizon by exploring how strategic behavior manifests under non-linear classifiers and what this implies for learning. We take a bottom-up approach showing how non-linearity affects decision boundary points, classifier expressivity, and model class complexity. Our results show how, unlike the linear case, strategic behavior may either increase or decrease effective class complexity, and that the complexity decrease may be arbitrarily large. Another key finding is that universal approximators (e.g., neural nets) are no longer universal once the environment is strategic. We demonstrate empirically how this can create performance gaps even on an unrestricted model class.