Strategic Classification with Non-Linear Classifiers
Benyamin Trachtenberg, Nir Rosenfeld · 2025
Read Strategic Classification with Non-Linear Classifiers by Benyamin Trachtenberg, Nir Rosenfeld (2025) 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-2505-23443.txt.
Introduction
Benyamin Trachtenberg and Nir Rosenfeld study strategic classification with nonlinear models in a 2025 paper. In this setting, users reshape their features at some cost to win a label they want. Most past theory covers linear classifiers, whose straight boundary lines act in ways that are easy to foresee.
Working from the boundary up, the pair show how a curved edge changes the game. Past the linear case, user moves can raise or lower the effective complexity of a model class, and the drop can be without limit. Universal approximators such as neural nets stop being universal once users react to the model. Tests confirm gaps in performance even for model classes with no limits at all. The results reset what learners can promise when people game the classifier.
Catalog record
| CREATOR | Benyamin Trachtenberg, Nir Rosenfeld |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23443
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strategic Classification with Non-Linear Classifiers Benyamin Trachtenberg, Nir Rosenfeld Abstract 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. 1 Introduction Strategic classification considers learning in a setting where users modify their features in response to a deployed classifier to obtain positive predictions [ 4 , 3 , 16 ] . This setting aims to capture a natural tension that can arise between a system aiming to maximize accuracy and its users who seek favorable outcomes. Such a tension is well-motivated across diverse applications, including loan approval, university admission, job hiring, welfare and education programs, and medical services. The field has drawn much attention since its introduction, leading to advances along multiple learning fronts such as generalization [ 33 , 36 , 6 ] , optimization [ 25 ] , loss functions [ 26 , 24 ] , and extensions [ 14 , 18 , 11 , 30 ] . However, despite over a decade of effort, research in strategic classification remains predominantly focused on linear classification. Due to the inherent challenges of strategic learning, this focus has been reasonable, given that linearity has the benefit of inducing a simple form of strategic behavior that permits tractable analysis. Yet, since many realistic applications—including those mentioned above—make regular use of non-linear models, we believe that it is important to establish a better understanding of how non-linearity shapes strategic behavior, and how behavior in turn affects learning. Our paper therefore aims to extend the study of strategic classification to the non-linear regime. Our first observation is that non-linear classifiers induce qualitatively different behavior than linear ones in the strategic setting. Consider first the structure induced by standard linear classifiers. Generally, users in strategic classification are assumed to best-respond to the classifier by modifying their features in a way that maximizes utility (from prediction) minus costs (from modification). For a linear classifier h coupled with the common choice of an \ell_{2} cost, modifications x\mapsto x^{h} manifest as a projection of x onto the linear decision boundary of h as long as it incurs less than a unit cost. This simple form has several implications. First, note that all points ‘move’ in the same direction, making strategic behavior, in effect, one-dimensional. Second, the region of points that move forms a band of unit distance on the negative side of h . This means that the set of points classified as positive forms a halfspace, which implies that the ‘effective classifier’, given by h_{\Delta}(x)\coloneqq h(x^{h}) , is also linear. Third, and as a result, the induced effective model class remains linear. Together, the above suggest that for linear classifiers coupled with \ell_{2} costs, the transition from the standard, non-strategic setting to a strategic one requires anticipating which points move, but otherwise remains similar. One known implication is that the strategic and non-strategic VC dimension of linear classifiers are the same [ 33 ] . Furthermore, the Bayes-optimal strategic classifier can be derived by taking the optimal non-strategic classifier and simply increasing its bias term by one [ 29 ] . Note that this means that any linearly separable problem remains separable, and that strategic classifiers can, in principle, attain the same level of accuracy as their non-strategic counterparts. Thus, while perhaps challenging to solve in practice, the intrinsic difficulty of strategic linear classification remains unchanged. The above, however, is unlikely to hold for non-linear classifiers: once the decision boundary is non-linear, different points will move in different directions. This lends to the possible distortion of the shape of a given classifier, which in turn can change the effective (i.e., strategic) model class. Such changes can have concrete implications on expressivity, generalization, optimization, and attainable accuracy. This motivates the need to explore how strategic responses shape outcomes in non-linear strategic classification, which we believe is crucial as a first step towards developing future methods. Our general approach is to examine—through analysis, examples, and experiments—how objects in the original non-strategic task map to corresponding objects in the induced strategic problem instance. Initially, our conjecture was that strategic behavior acts as a ‘smoothing’ operator on the original decision boundary, but as we show, the actual effect of strategic behavior turns out to be more involved. To build an intuition of the mechanisms at play, we take a bottom-up approach and study three mappings between (i) individual points, (ii) classifiers, and (iii) model classes. For points, we begin by showing that the mapping is not necessarily bijective. As a result, some points on the original decision boundary become ‘wiped out’, while others are ‘expanded’ to become intervals (arcs for \ell_{2} costs) on the induced boundary. We demonstrate several mechanisms that can give rise to both phenomena. For classifiers, we show how the effects on individual points aggregate to modify the entire decision boundary. A key finding is that certain decision boundaries are impossible to express under strategic behavior. We give several examples of reasonable classifier types that cannot exist under strategic behavior, and show that some effective classifiers h_{\Delta} can be traced back to (infinitely) many original classifiers h . The main takeaway is that universal approximators, such as neural networks or RBF kernels, are no longer universal in a strategic environment. Our main contribution lies in our analysis of model classes, where our results build on the observation that the mapping from original to effective classifiers within a class is not necessarily bijective. In particular, because many h can be mapped to the same h_{\Delta} , the VC dimension of the induced model class can shrink even from \infty down to 0, causing model classes that were not learnable in the standard setting to become learnable in the strategic one. That said, the VC dimension of the induced class can generally either grow or shrink. We highlight some conditions that guarantee either of these outcomes, and, in particular, provide an upper bound on the strategic complexity increase for the expressive family of piecewise-linear model classes (e.g., ReLU networks). Our analysis yields several practical takeaways for learning, model selection, and future method development (see Appendix C.10 ). We conclude with experiments that shed light on how strategic behavior may alter the effective complexity and maximum accuracy of the learned model class in practice. 2 Related work Our work focuses on the common setting of supervised binary classification, where non-linear models are highly