Strategic Classification with Randomised Classifiers

• URL: http://arxiv.org/abs/2502.01313v1
• Date: Mon, 03 Feb 2025 12:41:55 GMT
• Title: Strategic Classification with Randomised Classifiers
• Authors: Jack Geary, Henry Gouk,
• Abstract summary: We consider the problem of strategic classification, where a learner must build a model to classify agents based on features that have been strategically modified. We show that, under certain conditions, the optimal randomised classifier can achieve better accuracy than the optimal deterministic classifier. We conclude that randomisation has the potential to alleviate some issues that could be faced in practice without introducing any substantial downsides.
• Score: 11.732535996238003
• License:
• Abstract: We consider the problem of strategic classification, where a learner must build a model to classify agents based on features that have been strategically modified. Previous work in this area has concentrated on the case when the learner is restricted to deterministic classifiers. In contrast, we perform a theoretical analysis of an extension to this setting that allows the learner to produce a randomised classifier. We show that, under certain conditions, the optimal randomised classifier can achieve better accuracy than the optimal deterministic classifier, but under no conditions can it be worse. When a finite set of training data is available, we show that the excess risk of Strategic Empirical Risk Minimisation over the class of randomised classifiers is bounded in a similar manner as the deterministic case. In both the deterministic and randomised cases, the risk of the classifier produced by the learner converges to that of the corresponding optimal classifier as the volume of available training data grows. Moreover, this convergence happens at the same rate as in the i.i.d. case. Our findings are compared with previous theoretical work analysing the problem of strategic classification. We conclude that randomisation has the potential to alleviate some issues that could be faced in practice without introducing any substantial downsides.

Related papers

• Teaching Models To Survive: Proper Scoring Rule and Stochastic Optimization with Competing Risks [6.9648613217501705]
  When data are right-censored, survival analysis can compute the "time to event" We introduce a strictly proper censoring-adjusted separable scoring rule that can be optimized on a subpart of the data. Compared to 11 state-of-the-art models, this model, MultiIncidence, performs best in estimating the probability of outcomes in survival and competing risks.
  arXiv  Detail & Related papers  (2024-06-20T08:00:42Z)
• When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
  Cascades are a classical strategy to enable inference cost to vary adaptively across samples. A deferral rule determines whether to invoke the next classifier in the sequence, or to terminate prediction. Despite being oblivious to the structure of the cascade, confidence-based deferral often works remarkably well in practice.
  arXiv  Detail & Related papers  (2023-07-06T04:13:57Z)
• Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker [57.49330031751386]
  We find achievable information-theoretic lower bounds on loss in the presence of a test-time attacker for multi-class classifiers on any discrete dataset. We provide a general framework for finding the optimal 0-1 loss that revolves around the construction of a conflict hypergraph from the data and adversarial constraints.
  arXiv  Detail & Related papers  (2023-02-21T15:17:13Z)
• On the Role of Randomization in Adversarially Robust Classification [13.39932522722395]
  We show that a randomized ensemble outperforms the hypothesis set in adversarial risk. We also give an explicit description of the deterministic hypothesis set that contains such a deterministic classifier.
  arXiv  Detail & Related papers  (2023-02-14T17:51:00Z)
• Anomaly Detection using Ensemble Classification and Evidence Theory [62.997667081978825]
  We present a novel approach for novel detection using ensemble classification and evidence theory. A pool selection strategy is presented to build a solid ensemble classifier. We use uncertainty for the anomaly detection approach.
  arXiv  Detail & Related papers  (2022-12-23T00:50:41Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm. Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
  arXiv  Detail & Related papers  (2022-01-26T19:59:14Z)
• Selecting the suitable resampling strategy for imbalanced data classification regarding dataset properties [62.997667081978825]
  In many application domains such as medicine, information retrieval, cybersecurity, social media, etc., datasets used for inducing classification models often have an unequal distribution of the instances of each class. This situation, known as imbalanced data classification, causes low predictive performance for the minority class examples. Oversampling and undersampling techniques are well-known strategies to deal with this problem by balancing the number of examples of each class.
  arXiv  Detail & Related papers  (2021-12-15T18:56:39Z)
• Scalable Optimal Classifiers for Adversarial Settings under Uncertainty [10.90668635921398]
  We consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender. We show that this low-dimensional characterization enables to develop a training method to compute provably approximately optimal classifiers in a scalable manner.
  arXiv  Detail & Related papers  (2021-06-28T13:33:53Z)
• The Role of Randomness and Noise in Strategic Classification [7.972516140165492]
  We investigate the problem of designing optimal classifiers in the strategic classification setting. We show that in many natural cases, the imposed optimal solution has the structure where players never change their feature vectors. We also show that a noisier signal leads to better equilibria outcomes.
  arXiv  Detail & Related papers  (2020-05-17T21:49:41Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)
• Fairness Measures for Regression via Probabilistic Classification [0.0]
  Algorithmic fairness involves expressing notions such as equity, or reasonable treatment, as quantifiable measures that a machine learning algorithm can optimise. This is in part because classification fairness measures are easily computed by comparing the rates of outcomes, leading to behaviours such as ensuring the same fraction of eligible men are selected as eligible women. But such measures are computationally difficult to generalise to the continuous regression setting for problems such as pricing, or allocating payments. For the regression setting we introduce tractable approximations of the independence, separation and sufficiency criteria by observing that they factorise as ratios of different conditional probabilities of the protected attributes.
  arXiv  Detail & Related papers  (2020-01-16T21:53:26Z)

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.