Computing Strategic Responses to Non-Linear Classifiers

• URL: http://arxiv.org/abs/2511.21560v1
• Date: Wed, 26 Nov 2025 16:30:38 GMT
• Title: Computing Strategic Responses to Non-Linear Classifiers
• Authors: Jack Geary, Boyan Gao, Henry Gouk,
• Abstract summary: We present a novel method for computing the best response by optimising the Lagrangian dual of the Agents' objective.<n>We demonstrate that our method reproduces best responses in linear settings, identifying key weaknesses in existing approaches.
• Score: 9.398661081552335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of strategic classification, where the act of deploying a classifier leads to strategic behaviour that induces a distribution shift on subsequent observations. Current approaches to learning classifiers in strategic settings are focused primarily on the linear setting, but in many cases non-linear classifiers are more suitable. A central limitation to progress for non-linear classifiers arises from the inability to compute best responses in these settings. We present a novel method for computing the best response by optimising the Lagrangian dual of the Agents' objective. We demonstrate that our method reproduces best responses in linear settings, identifying key weaknesses in existing approaches. We present further results demonstrating our method can be straight-forwardly applied to non-linear classifier settings, where it is useful for both evaluation and training.

Related papers

• Strategic Classification with Non-Linear Classifiers [19.50869817974852]
  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.<n>We show how strategic behavior may either increase or decrease effective class complexity, and that the complexity decrease may be arbitrarily large.
  arXiv  Detail & Related papers  (2025-05-29T13:40:03Z)
• Practical Performative Policy Learning with Strategic Agents [8.361090623217246]
  We study the performative policy learning problem, where agents adjust their features in response to a released policy to improve their potential outcomes.<n>We propose a gradient-based policy optimization algorithm with a differentiable classifier as a substitute for the high-dimensional distribution map.
  arXiv  Detail & Related papers  (2024-12-02T10:09:44Z)
• Robust optimization for adversarial learning with finite sample complexity guarantees [1.8434042562191815]
  In this paper we focus on linear and nonlinear classification problems and propose a novel adversarial training method for robust classifiers. We view robustness under a data driven lens, and derive finite sample complexity bounds for both linear and non-linear classifiers in binary and multi-class scenarios. Our algorithm minimizes a worst-case surrogate loss using Linear Programming (LP) and Second Order Cone Programming (SOCP) for linear and non-linear models.
  arXiv  Detail & Related papers  (2024-03-22T13:49:53Z)
• Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning [53.97335841137496]
  We propose an oracle-efficient algorithm, dubbed Pessimistic Least-Square Value Iteration (PNLSVI) for offline RL with non-linear function approximation. Our algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation.
  arXiv  Detail & Related papers  (2023-10-02T17:42:01Z)
• Open World Classification with Adaptive Negative Samples [89.2422451410507]
  Open world classification is a task in natural language processing with key practical relevance and impact. We propose an approach based on underlineadaptive underlinesamples (ANS) designed to generate effective synthetic open category samples in the training stage. ANS achieves significant improvements over state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-03-09T21:12:46Z)
• Fast Offline Policy Optimization for Large Scale Recommendation [74.78213147859236]
  We derive an approximation of these policy learning algorithms that scale logarithmically with the catalogue size. Our contribution is based upon combining three novel ideas. Our estimator is an order of magnitude faster than naive approaches yet produces equally good policies.
  arXiv  Detail & Related papers  (2022-08-08T11:54:11Z)
• MCDAL: Maximum Classifier Discrepancy for Active Learning [74.73133545019877]
  Recent state-of-the-art active learning methods have mostly leveraged Generative Adversarial Networks (GAN) for sample acquisition. We propose in this paper a novel active learning framework that we call Maximum Discrepancy for Active Learning (MCDAL) In particular, we utilize two auxiliary classification layers that learn tighter decision boundaries by maximizing the discrepancies among them.
  arXiv  Detail & Related papers  (2021-07-23T06:57:08Z)
• Provably Correct Optimization and Exploration with Non-linear Policies [65.60853260886516]
  ENIAC is an actor-critic method that allows non-linear function approximation in the critic. We show that under certain assumptions, the learner finds a near-optimal policy in $O(poly(d))$ exploration rounds. We empirically evaluate this adaptation and show that it outperforms priors inspired by linear methods.
  arXiv  Detail & Related papers  (2021-03-22T03:16:33Z)
• Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification [94.55805516167369]
  We propose a new approach for binary classification from m U-sets for $mge2$. Our key idea is to consider an auxiliary classification task called surrogate set classification (SSC)
  arXiv  Detail & Related papers  (2021-02-01T07:36:38Z)
• Sparse Methods for Automatic Relevance Determination [0.0]
  We first review automatic relevance determination (ARD) and analytically demonstrate the need to additional regularization or thresholding to achieve sparse models. We then discuss two classes of methods, regularization based and thresholding based, which build on ARD to learn parsimonious solutions to linear problems.
  arXiv  Detail & Related papers  (2020-05-18T14:08:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.