New method makes non-linear strategic classification practical
Lagrangian duality and implicit function theorem enable practical strategic classifiers.
Strategic classification considers how users may game a model to get favorable outcomes. Until now, practical methods were mostly limited to linear classifiers because non-linear settings made the strategic response computationally intractable. In this paper, Geary, Gao, and Gouk introduce a technique that approximates the best response by exploiting Lagrangian duality. They rewrite the strategic response as a constrained optimization problem, constructing a Lagrangian that works with first-order optimization methods.
This approach reproduces closed-form solutions in linear settings and extends naturally to non-linear ones. Crucially, they show how the Implicit Function Theorem can compute the total gradient of the loss with respect to classifier parameters during learning, connecting parameters directly to strategic behavior. Experimental results on common datasets demonstrate improved strategic accuracy, making non-linear strategic classification viable for real-world applications.
- Exploits Lagrangian duality to approximate best responses in non-linear strategic settings.
- Uses the Implicit Function Theorem to compute gradients through the strategic response during training.
- Achieves improved strategic accuracy on standard ML datasets versus prior linear-only approaches.
Why It Matters
Enables robust non-linear models that account for user gaming, improving fairness and reliability in practice.