Group Fairness in Non-monotone Submodular Maximization

• URL: http://arxiv.org/abs/2302.01546v1
• Date: Fri, 3 Feb 2023 04:51:54 GMT
• Title: Group Fairness in Non-monotone Submodular Maximization
• Authors: Jing Yuan, Shaojie Tang
• Abstract summary: We study the non-monotone submodular problem subject to novel group fairness constraints. We develop the first constant-factor approximation algorithms for this problem.
• Score: 19.29174615532181
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximizing a submodular function has a wide range of applications in machine learning and data mining. One such application is data summarization whose goal is to select a small set of representative and diverse data items from a large dataset. However, data items might have sensitive attributes such as race or gender, in this setting, it is important to design \emph{fairness-aware} algorithms to mitigate potential algorithmic bias that may cause over- or under- representation of particular groups. Motivated by that, we propose and study the classic non-monotone submodular maximization problem subject to novel group fairness constraints. Our goal is to select a set of items that maximizes a non-monotone submodular function, while ensuring that the number of selected items from each group is proportionate to its size, to the extent specified by the decision maker. We develop the first constant-factor approximation algorithms for this problem. We also extend the basic model to incorporate an additional global size constraint on the total number of selected items.

Related papers

• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Multi-Teacher Multi-Objective Meta-Learning for Zero-Shot Hyperspectral Band Selection [50.30291173608449]
  We propose a novel multi-objective meta-learning network (M$3$BS) for zero-shot hyperspectral band selection. In M$3$BS, a generalizable graph convolution network (GCN) is constructed to generate dataset-agnostic base. The acquired meta-knowledge can be directly transferred to unseen datasets without any retraining or fine-tuning.
  arXiv  Detail & Related papers  (2024-06-12T07:13:31Z)
• Enhancing Neural Subset Selection: Integrating Background Information into Set Representations [53.15923939406772]
  We show that when the target value is conditioned on both the input set and subset, it is essential to incorporate an textitinvariant sufficient statistic of the superset into the subset of interest. This ensures that the output value remains invariant to permutations of the subset and its corresponding superset, enabling identification of the specific superset from which the subset originated.
  arXiv  Detail & Related papers  (2024-02-05T16:09:35Z)
• 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)
• Achieving Long-term Fairness in Submodular Maximization through Randomization [16.33001220320682]
  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.
  arXiv  Detail & Related papers  (2023-04-10T16:39:19Z)
• 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)
• Group Equality in Adaptive Submodular Maximization [13.619980548779687]
  We study the classic submodular problem subject to a group equality constraint under both non-adaptive and adaptive settings. We develop the first constant approximation algorithm for this problem.
  arXiv  Detail & Related papers  (2022-07-07T15:12:02Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• 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)
• 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.