Group Equality in Adaptive Submodular Maximization

• URL: http://arxiv.org/abs/2207.03364v4
• Date: Tue, 29 Aug 2023 02:44:33 GMT
• Title: Group Equality in Adaptive Submodular Maximization
• Authors: Shaojie Tang, Jing Yuan
• Abstract summary: 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.
• Score: 13.619980548779687
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both non-adaptive and adaptive settings. It has been shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to under- or over-representation of some particular groups. This motivates us to study the submodular maximization problem with group equality, where we aim to select a group of items to maximize a (possibly non-monotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations.

Related papers

• 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)
• Balancing Utility and Fairness in Submodular Maximization (Technical Report) [27.20340546154524]
  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.
  arXiv  Detail & Related papers  (2022-11-02T09:38:08Z)
• 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)
• Partial-Adaptive Submodular Maximization [28.24164217929491]
  Most studies on adaptive submodular problem focus on fully adaptive setting. In this paper, we explore the problem of partial-adaptive submodular where one is allowed to make multiple selections in a batch simultaneously. Our approach enjoys the benefits of adaptivity while reducing the time spent on waiting for the observations from past selections.
  arXiv  Detail & Related papers  (2021-11-01T14:48:41Z)
• 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)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to a Knapsack Constraint [26.171841086317574]
  We study the non-monotone adaptive submodular problem subject to a knapsack constraint. The state of an item is initially unknown, one must select an item in order to reveal the state of that item. Our main contribution is to develop a sampling-based randomized algorithm that achieves a $frac1$ approximation for maximizing an adaptive submodular function.
  arXiv  Detail & Related papers  (2021-04-10T20:11:11Z)
• Optimization-Inspired Learning with Architecture Augmentations and Control Mechanisms for Low-Level Vision [74.9260745577362]
  This paper proposes a unified optimization-inspired learning framework to aggregate Generative, Discriminative, and Corrective (GDC) principles. We construct three propagative modules to effectively solve the optimization models with flexible combinations. Experiments across varied low-level vision tasks validate the efficacy and adaptability of GDC.
  arXiv  Detail & Related papers  (2020-12-10T03:24:53Z)
• Planning with Submodular Objective Functions [118.0376288522372]
  We study planning with submodular objective functions, where instead of maximizing cumulative reward, the goal is to maximize the value induced by a submodular function. Our framework subsumes standard planning and submodular objective with cardinality constraints as special cases.
  arXiv  Detail & Related papers  (2020-10-22T16:55:12Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks. This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions. We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  Continuous submodularity is a class of functions with a wide spectrum of applications. We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
  arXiv  Detail & Related papers  (2020-06-24T04:37:31Z)
• 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)

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.