Achieving Long-term Fairness in Submodular Maximization through Randomization

• URL: http://arxiv.org/abs/2304.04700v1
• Date: Mon, 10 Apr 2023 16:39:19 GMT
• Title: Achieving Long-term Fairness in Submodular Maximization through Randomization
• Authors: Shaojie Tang, Jing Yuan, Twumasi Mensah-Boateng
• Abstract summary: It is important to implement fairness-aware algorithms when dealing with data items that may contain sensitive attributes like race or gender. We investigate the problem of maximizing a monotone submodular function while meeting group fairness constraints.
• Score: 16.33001220320682
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular function optimization has numerous applications in machine learning and data analysis, including data summarization which aims to identify a concise and diverse set of data points from a large dataset. It is important to implement fairness-aware algorithms when dealing with data items that may contain sensitive attributes like race or gender, to prevent biases that could lead to unequal representation of different groups. With this in mind, we investigate the problem of maximizing a monotone submodular function while meeting group fairness constraints. Unlike previous studies in this area, we allow for randomized solutions, with the objective being to calculate a distribution over feasible sets such that the expected number of items selected from each group is subject to constraints in the form of upper and lower thresholds, ensuring that the representation of each group remains balanced in the long term. Here a set is considered feasible if its size does not exceed a constant value of $b$. Our research includes the development of a series of approximation algorithms for this problem.

Related papers

• Learning Submodular Sequencing from Samples [11.528995186765751]
  This paper addresses the problem of selecting and ranking items in a sequence to optimize some composite submodular function. We present an algorithm that achieves an approximation ratio dependent on the curvature of the individual submodular functions.
  arXiv  Detail & Related papers  (2024-09-09T01:33:13Z)
• 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)
• Group Fairness in Non-monotone Submodular Maximization [19.29174615532181]
  We study the non-monotone submodular problem subject to novel group fairness constraints. We develop the first constant-factor approximation algorithms for this problem.
  arXiv  Detail & Related papers  (2023-02-03T04:51:54Z)
• Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms [17.57585822765145]
  We propose an exact algorithm that is suitable for small datasets as well as a $frac1-varepsilon integer integer5$-approximation algorithm for any $varepsilon in (0, 1)$ that scales to large datasets. Experiments on real-world datasets demonstrate the superior performance of our proposed algorithms over existing ones.
  arXiv  Detail & Related papers  (2023-01-05T13:02:35Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Towards Group Robustness in the presence of Partial Group Labels [61.33713547766866]
  spurious correlations between input samples and the target labels wrongly direct the neural network predictions. We propose an algorithm that optimize for the worst-off group assignments from a constraint set. We show improvements in the minority group's performance while preserving overall aggregate accuracy across groups.
  arXiv  Detail & Related papers  (2022-01-10T22:04:48Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Fairness in Streaming Submodular Maximization: Algorithms and Hardness [20.003009252240222]
  We develop the first streaming approximation for submodular under fairness constraints, for both monotone and non-monotone functions. We validate our findings on DPP-based movie recommendation, clustering-based summarization, and maximum coverage in social networks.
  arXiv  Detail & Related papers  (2020-10-14T22:57:07Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)
• 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.