Fairness in Streaming Submodular Maximization over a Matroid Constraint

• URL: http://arxiv.org/abs/2305.15118v2
• Date: Thu, 19 Oct 2023 15:22:19 GMT
• Title: Fairness in Streaming Submodular Maximization over a Matroid Constraint
• Authors: Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, Jakub Tarnawski
• Abstract summary: We study the natural generalization of this problem to a matroid constraint. We give streaming algorithms as well as impossibility results that provide trade-offs between efficiency, quality and fairness.
• Score: 19.27202441717429
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as gender or race, it becomes important to enforce fairness to avoid bias and discrimination. This has spurred significant interest in developing fair machine learning algorithms. Recently, such algorithms have been developed for monotone submodular maximization under a cardinality constraint. In this paper, we study the natural generalization of this problem to a matroid constraint. We give streaming algorithms as well as impossibility results that provide trade-offs between efficiency, quality and fairness. We validate our findings empirically on a range of well-known real-world applications: exemplar-based clustering, movie recommendation, and maximum coverage in social networks.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Fairness in Submodular Maximization over a Matroid Constraint [14.402156575758559]
  Submodular over a matroid constraint is a fundamental problem with various applications in machine learning. We propose various algorithms and impossibility results offering different tradeoffs between quality, fairness, and generality.
  arXiv  Detail & Related papers  (2023-12-21T21:12:39Z)
• Amortizing intractable inference in large language models [56.92471123778389]
  We use amortized Bayesian inference to sample from intractable posterior distributions. We empirically demonstrate that this distribution-matching paradigm of LLM fine-tuning can serve as an effective alternative to maximum-likelihood training. As an important application, we interpret chain-of-thought reasoning as a latent variable modeling problem.
  arXiv  Detail & Related papers  (2023-10-06T16:36:08Z)
• Boosting Fair Classifier Generalization through Adaptive Priority Reweighing [59.801444556074394]
  A performance-promising fair algorithm with better generalizability is needed. This paper proposes a novel adaptive reweighing method to eliminate the impact of the distribution shifts between training and test data on model generalizability.
  arXiv  Detail & Related papers  (2023-09-15T13:04:55Z)
• Online and Streaming Algorithms for Constrained $k$-Submodular Maximization [25.15934533974176]
  Constrained $k$-submodular is a general framework that captures many discrete optimization problems such as ad allocation, influence, personalized recommendation, and many others. In this work, we develop single-pass streaming and online algorithms for $k$-submodular constrained with both monotone and general (possibly non-monotone) objectives.
  arXiv  Detail & Related papers  (2023-05-25T12:53:17Z)
• Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
  We train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model. A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations. We propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement.
  arXiv  Detail & Related papers  (2022-06-08T04:09:13Z)
• 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)
• Learning Centric Power Allocation for Edge Intelligence [84.16832516799289]
  Edge intelligence has been proposed, which collects distributed data and performs machine learning at the edge. This paper proposes a learning centric power allocation (LCPA) method, which allocates radio resources based on an empirical classification error model. Experimental results show that the proposed LCPA algorithm significantly outperforms other power allocation algorithms.
  arXiv  Detail & Related papers  (2020-07-21T07:02:07Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)
• Robust Submodular Minimization with Applications to Cooperative Modeling [0.0]
  This paper studies the problem of robust submodular Minimization subject to constraints. Constrained Submodular Minimization arises in several applications such as co-operative cuts in image segmentation, co-operative matchings in image correspondence, etc.
  arXiv  Detail & Related papers  (2020-01-25T20:40:37Z)

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.