Minimax Group Fairness in Strategic Classification

• URL: http://arxiv.org/abs/2410.02513v1
• Date: Thu, 3 Oct 2024 14:22:55 GMT
• Title: Minimax Group Fairness in Strategic Classification
• Authors: Emily Diana, Saeed Sharifi-Malvajerdi, Ali Vakilian,
• Abstract summary: In strategic classification, agents manipulate their features, at a cost, to receive a positive classification outcome from the learner's classifier. We consider learning objectives that have group fairness guarantees in addition to accuracy guarantees. We formalize a fairness-aware Stackelberg game between a population of agents consisting of several groups, with each group having its own cost function.
• Score: 8.250258160056514
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In strategic classification, agents manipulate their features, at a cost, to receive a positive classification outcome from the learner's classifier. The goal of the learner in such settings is to learn a classifier that is robust to strategic manipulations. While the majority of works in this domain consider accuracy as the primary objective of the learner, in this work, we consider learning objectives that have group fairness guarantees in addition to accuracy guarantees. We work with the minimax group fairness notion that asks for minimizing the maximal group error rate across population groups. We formalize a fairness-aware Stackelberg game between a population of agents consisting of several groups, with each group having its own cost function, and a learner in the agnostic PAC setting in which the learner is working with a hypothesis class H. When the cost functions of the agents are separable, we show the existence of an efficient algorithm that finds an approximately optimal deterministic classifier for the learner when the number of groups is small. This algorithm remains efficient, both statistically and computationally, even when H is the set of all classifiers. We then consider cost functions that are not necessarily separable and show the existence of oracle-efficient algorithms that find approximately optimal randomized classifiers for the learner when H has finite strategic VC dimension. These algorithms work under the assumption that the learner is fully transparent: the learner draws a classifier from its distribution (randomized classifier) before the agents respond by manipulating their feature vectors. We highlight the effectiveness of such transparency in developing oracle-efficient algorithms. We conclude with verifying the efficacy of our algorithms on real data by conducting an experimental analysis.

Related papers

• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  Ensemble learning is a method that leverages weak learners to produce a strong learner. We design a smooth and convex objective function that leverages the concept of margin, making the strong learner more discriminative. We then compare our algorithm with random forests of ten times the size and other classical methods across numerous datasets.
  arXiv  Detail & Related papers  (2024-08-06T03:42:38Z)
• Optimally Improving Cooperative Learning in a Social Setting [4.200480236342444]
  We consider a cooperative learning scenario where a collection of networked agents with individually owned classifiers dynamically update their predictions. We show a time algorithm for optimizing the aggregate objective function, and show that optimizing the egalitarian objective function is NP-hard. The performance of all of our algorithms are guaranteed by mathematical analysis and backed by experiments on synthetic and real data.
  arXiv  Detail & Related papers  (2024-05-31T14:07:33Z)
• The Role of Learning Algorithms in Collective Action [8.955918346078935]
  We show that the effective size and success of a collective are highly dependent on the properties of the learning algorithm. This highlights the necessity of taking the learning algorithm into account when studying the impact of collective action in machine learning.
  arXiv  Detail & Related papers  (2024-05-10T16:36:59Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Bayesian Strategic Classification [11.439576371711711]
  We study the study of partial information release by the learner in strategic classification. We show how such partial information release can, counter-intuitively, benefit the learner's accuracy, despite increasing agents' abilities to manipulate.
  arXiv  Detail & Related papers  (2024-02-13T19:51:49Z)
• A Hard-to-Beat Baseline for Training-free CLIP-based Adaptation [121.0693322732454]
  Contrastive Language-Image Pretraining (CLIP) has gained popularity for its remarkable zero-shot capacity. Recent research has focused on developing efficient fine-tuning methods to enhance CLIP's performance in downstream tasks. We revisit a classical algorithm, Gaussian Discriminant Analysis (GDA), and apply it to the downstream classification of CLIP.
  arXiv  Detail & Related papers  (2024-02-06T15:45:27Z)
• Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints [19.29174615532181]
  We introduce a unified framework for randomized subset selection that incorporates group fairness constraints. Our problem involves a global utility function and a set of group utility functions for each group. Our aim is to generate a distribution across feasible subsets, specifying the selection probability of each feasible set.
  arXiv  Detail & Related papers  (2023-04-13T15:02:37Z)
• Towards Diverse Evaluation of Class Incremental Learning: A Representation Learning Perspective [67.45111837188685]
  Class incremental learning (CIL) algorithms aim to continually learn new object classes from incrementally arriving data. We experimentally analyze neural network models trained by CIL algorithms using various evaluation protocols in representation learning.
  arXiv  Detail & Related papers  (2022-06-16T11:44:11Z)
• Early Exiting with Ensemble Internal Classifiers [57.80488632985445]
  Early exiting has gained much attention in the NLP community. We propose a voting-based strategy that considers predictions of all the past internal classifiers to infer the correct label. Experimental results on various NLP tasks show that our proposed objective function and voting-based strategy can achieve better accuracy-speed trade-offs.
  arXiv  Detail & Related papers  (2021-05-28T12:54:11Z)
• Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
  We introduce a fast optimization-based meta-learning method for few-shot classification. Our strategy enables important aspects of the base learner objective to be learned during meta-training. We perform a comprehensive experimental analysis, demonstrating the speed and effectiveness of our approach.
  arXiv  Detail & Related papers  (2020-10-01T15:59:31Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18: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.