Strategic Classification with Non-Linear Classifiers

• URL: http://arxiv.org/abs/2505.23443v1
• Date: Thu, 29 May 2025 13:40:03 GMT
• Title: Strategic Classification with Non-Linear Classifiers
• Authors: Benyamin Trachtenberg, Nir Rosenfeld,
• Abstract summary: We show how strategic user behavior manifests under non-linear classifiers.<n>Key finding is that universal approximators are no longer universal once the environment is strategic.
• Score: 13.175123810033124
• License: http://creativecommons.org/licenses/by/4.0/
• 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 classes complexity. A 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.

Related papers

• SelEx: Self-Expertise in Fine-Grained Generalized Category Discovery [55.72840638180451]
  Generalized Category Discovery aims to simultaneously uncover novel categories and accurately classify known ones. Traditional methods, which lean heavily on self-supervision and contrastive learning, often fall short when distinguishing between fine-grained categories. We introduce a novel concept called self-expertise', which enhances the model's ability to recognize subtle differences and uncover unknown categories.
  arXiv  Detail & Related papers  (2024-08-26T15:53:50Z)
• Learnability Gaps of Strategic Classification [68.726857356532]
  We focus on addressing a fundamental question: the learnability gaps between strategic classification and standard learning. We provide nearly tight sample complexity and regret bounds, offering significant improvements over prior results. Notably, our algorithm in this setting is of independent interest and can be applied to other problems such as multi-label learning.
  arXiv  Detail & Related papers  (2024-02-29T16:09:19Z)
• PILoRA: Prototype Guided Incremental LoRA for Federated Class-Incremental Learning [41.984652077669104]
  Experimental results on standard datasets indicate that our method outperforms the state-of-the-art approaches significantly. Our method exhibits strong robustness and superiority in different settings and degrees of data heterogeneity.
  arXiv  Detail & Related papers  (2024-01-04T06:46:19Z)
• Few-Shot Class-Incremental Learning via Training-Free Prototype Calibration [67.69532794049445]
  We find a tendency for existing methods to misclassify the samples of new classes into base classes, which leads to the poor performance of new classes. We propose a simple yet effective Training-frEE calibratioN (TEEN) strategy to enhance the discriminability of new classes.
  arXiv  Detail & Related papers  (2023-12-08T18:24:08Z)
• Continual Learning for LiDAR Semantic Segmentation: Class-Incremental and Coarse-to-Fine strategies on Sparse Data [12.749063878119737]
  This paper analyzes the problem of class incremental learning applied to point cloud semantic segmentation. Different CL strategies were adapted to LiDAR point clouds and tested, tackling both classic fine-tuning scenarios and the Coarse-to-Fine learning paradigm.
  arXiv  Detail & Related papers  (2023-04-08T10:28:42Z)
• Strategic Classification with Graph Neural Networks [10.131895986034316]
  Using a graph for learning introduces inter-user dependencies in prediction. We propose a differentiable framework for strategically-robust learning of graph-based classifiers.
  arXiv  Detail & Related papers  (2022-05-31T13:11:25Z)
• Learning to Generate Novel Classes for Deep Metric Learning [24.048915378172012]
  We introduce a new data augmentation approach that synthesizes novel classes and their embedding vectors. We implement this idea by learning and exploiting a conditional generative model, which, given a class label and a noise, produces a random embedding vector of the class. Our proposed generator allows the loss to use richer class relations by augmenting realistic and diverse classes, resulting in better generalization to unseen samples.
  arXiv  Detail & Related papers  (2022-01-04T06:55:19Z)
• Self-Supervised Class Incremental Learning [51.62542103481908]
  Existing Class Incremental Learning (CIL) methods are based on a supervised classification framework sensitive to data labels. When updating them based on the new class data, they suffer from catastrophic forgetting: the model cannot discern old class data clearly from the new. In this paper, we explore the performance of Self-Supervised representation learning in Class Incremental Learning (SSCIL) for the first time.
  arXiv  Detail & Related papers  (2021-11-18T06:58:19Z)
• Learning Debiased and Disentangled Representations for Semantic Segmentation [52.35766945827972]
  We propose a model-agnostic and training scheme for semantic segmentation. By randomly eliminating certain class information in each training iteration, we effectively reduce feature dependencies among classes. Models trained with our approach demonstrate strong results on multiple semantic segmentation benchmarks.
  arXiv  Detail & Related papers  (2021-10-31T16:15:09Z)
• Class-Incremental Learning with Generative Classifiers [6.570917734205559]
  We propose a new strategy for class-incremental learning: generative classification. Our proposal is to learn the joint distribution p(x,y), factorized as p(x|y)p(y), and to perform classification using Bayes' rule. As a proof-of-principle, here we implement this strategy by training a variational autoencoder for each class to be learned.
  arXiv  Detail & Related papers  (2021-04-20T16:26:14Z)
• CLASTER: Clustering with Reinforcement Learning for Zero-Shot Action Recognition [52.66360172784038]
  We propose a clustering-based model, which considers all training samples at once, instead of optimizing for each instance individually. We call the proposed method CLASTER and observe that it consistently improves over the state-of-the-art in all standard datasets.
  arXiv  Detail & Related papers  (2021-01-18T12:46:24Z)
• PAC-Learning for Strategic Classification [18.60310393343275]
  We introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem.
  arXiv  Detail & Related papers  (2020-12-06T16:29:27Z)

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.