Balancing Utility and Fairness in Submodular Maximization (Technical Report)

• URL: http://arxiv.org/abs/2211.00980v4
• Date: Mon, 19 Jun 2023 09:01:20 GMT
• Title: Balancing Utility and Fairness in Submodular Maximization (Technical Report)
• Authors: Yanhao Wang and Yuchen Li and Francesco Bonchi and Ying Wang
• Abstract summary: We propose a new problem called emphBi Maxim Submodularization (BSM) to balance utility and fairness. Since BSM is inapproximable within any constant factor, we focus on designing efficient instance-dependent approximation schemes.
• Score: 27.20340546154524
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Submodular function maximization is a fundamental combinatorial optimization problem with plenty of applications -- including data summarization, influence maximization, and recommendation. In many of these problems, the goal is to find a solution that maximizes the average utility over all users, for each of whom the utility is defined by a monotone submodular function. However, when the population of users is composed of several demographic groups, another critical problem is whether the utility is fairly distributed across different groups. Although the \emph{utility} and \emph{fairness} objectives are both desirable, they might contradict each other, and, to the best of our knowledge, little attention has been paid to optimizing them jointly. To fill this gap, we propose a new problem called \emph{Bicriteria Submodular Maximization} (BSM) to balance utility and fairness. Specifically, it requires finding a fixed-size solution to maximize the utility function, subject to the value of the fairness function not being below a threshold. Since BSM is inapproximable within any constant factor, we focus on designing efficient instance-dependent approximation schemes. Our algorithmic proposal comprises two methods, with different approximation factors, obtained by converting a BSM instance into other submodular optimization problem instances. Using real-world and synthetic datasets, we showcase applications of our proposed methods in three submodular maximization problems: maximum coverage, influence maximization, and facility location.

Related papers

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  We aim to select and rank a group of $k$ items from a ground set $V$ such that the weighted assortment of $k$ is maximized. The results of this research have implications in various fields, including recommendation systems and optimization.
  arXiv  Detail & Related papers  (2023-08-16T19:32:29Z)
• Maximizing Submodular Functions for Recommendation in the Presence of Biases [25.081136190260015]
  Subset selection tasks arise in systems and search engines and ask to select a subset of items that maximize the value for the user. In many applications, inputs have been observed to have social biases that reduce the utility of the output subset. We show that fairness constraint-based interventions can not only ensure proportional representation but also achieve near-optimal utility in the presence of biases.
  arXiv  Detail & Related papers  (2023-05-03T15:20:00Z)
• 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)
• Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
  Federated learning (FL) is a promising privacy-preserving machine learning paradigm over distributed located data. We propose a learning-based reweighting approach to mitigate the effect of noisy labels in FL. Our approach has shown superior performance on several real-world datasets compared to various baselines.
  arXiv  Detail & Related papers  (2022-06-11T16:21:17Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Robust Adaptive Submodular Maximization [26.171841086317574]
  We study two variants of adaptive submodular optimization problems, namely, worst-case adaptive submodular and robust submodular. We develop an adaptive worst-case greedy policy that achieves a $frac1p+1$ constraint ratio against the optimal worst-case utility. We also describe several applications of our theoretical results, including pool-base active learning submodular set cover and adaptive viral marketing.
  arXiv  Detail & Related papers  (2021-07-23T16:22:50Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Maximizing approximately k-submodular functions [21.881345069785105]
  We introduce the problem of maximizing $k$-submodular functions subject to size constraints. The problem finds applications in tasks such as sensor placement. We show that simple greedy algorithms offer approximation guarantees for different types of size constraints.
  arXiv  Detail & Related papers  (2021-01-18T16:48:40Z)
• Supervised Hyperalignment for multi-subject fMRI data alignment [81.8694682249097]
  This paper proposes a Supervised Hyperalignment (SHA) method to ensure better functional alignment for MVP analysis. Experiments on multi-subject datasets demonstrate that SHA method achieves up to 19% better performance for multi-class problems.
  arXiv  Detail & Related papers  (2020-01-09T09:17:49Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.