Online Multi-Class Selection with Group Fairness Guarantee

• URL: http://arxiv.org/abs/2510.21055v1
• Date: Thu, 23 Oct 2025 23:59:49 GMT
• Title: Online Multi-Class Selection with Group Fairness Guarantee
• Authors: Faraz Zargari, Hossein Nekouyan, Lyndon Hallett, Bo Sun, Xiaoqi Tan,
• Abstract summary: We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents.<n>We introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution.<n>We also propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency.
• Score: 3.8723467409682617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literature. First, we introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, we develop a randomized algorithm based on a relax-and-round framework. The algorithm first computes a fractional solution using a resource reservation approach -- referred to as the set-aside mechanism -- to enforce fairness across classes. The subsequent rounding step preserves these fairness guarantees without degrading performance. Additionally, we propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency in practical settings.

Related papers

• Randomized multi-class classification under system constraints: a unified approach via post-processing [8.354034992258482]
  We study the problem of multi-class classification under system-level constraints expressible as linear functionals over randomized classifiers.<n>We propose a post-processing approach that adjusts a given base classifier to satisfy general constraints without retraining.
  arXiv  Detail & Related papers  (2025-12-16T09:53:22Z)
• Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective [9.867914513513453]
  We present an oracle-efficient algorithm capable of achieving small-loss bounds with improved rates in greater generality than previous work.<n>We also present a variant for differentially private learning that attains optimal rates, again under our separation condition.
  arXiv  Detail & Related papers  (2025-02-14T16:52:50Z)
• Online Fair Allocation of Perishable Resources [1.4952056744888913]
  We consider a practically motivated variant of the canonical online fair allocation problem. A decision-maker has a budget of perishable resources to allocate over a fixed number of rounds. The goal is to construct a sequence of allocations that is envy-free and efficient.
  arXiv  Detail & Related papers  (2024-06-04T15:14:10Z)
• Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints [0.0]
  We present conservative distributed multi-task learning in linear contextual bandits with heterogeneous agents.<n>The exact context is unknown, and only a context distribution is available to the agents.<n>Our algorithm constructs a pruned action set during each round to ensure the constraints are met.<n>It includes synchronized sharing of estimates among agents via a central server.
  arXiv  Detail & Related papers  (2024-01-21T18:43:55Z)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
  We introduce a class of bandit algorithms that meet the two objectives of performance incentivization and robustness simultaneously.<n>We show that settings where the principal has no information about the arms' performance characteristics can be handled by combining ideas from second price auctions with our algorithms.
  arXiv  Detail & Related papers  (2023-12-13T06:54:49Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Individually Fair Learning with One-Sided Feedback [15.713330010191092]
  We consider an online learning problem with one-sided feedback, in which the learner is able to observe the true label only for positively predicted instances. On each round, $k$ instances arrive and receive classification outcomes according to a randomized policy deployed by the learner. We then construct an efficient reduction from our problem of online learning with one-sided feedback and a panel reporting fairness violations to the contextual semi-bandit problem.
  arXiv  Detail & Related papers  (2022-06-09T12:59:03Z)
• Contextual Model Aggregation for Fast and Robust Federated Learning in Edge Computing [88.76112371510999]
  Federated learning is a prime candidate for distributed machine learning at the network edge. Existing algorithms face issues with slow convergence and/or robustness of performance. We propose a contextual aggregation scheme that achieves the optimal context-dependent bound on loss reduction.
  arXiv  Detail & Related papers  (2022-03-23T21:42:31Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  We casting online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$m resource constraints. Our framework allows the decision maker to handle its evidence flexibility and costoretic functions.
  arXiv  Detail & Related papers  (2022-02-28T12:10:48Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  We provide the first oracle-efficient, no-regret algorithms in this setting. We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
  arXiv  Detail & Related papers  (2022-02-09T19:22:34Z)
• A new perspective on classification: optimally allocating limited resources to uncertain tasks [4.169130102668252]
  In credit card fraud detection, for instance, a bank can only assign a small subset of transactions to their fraud investigations team. We argue that using classification to address task uncertainty is inherently suboptimal as it does not take into account the available capacity. We present a novel solution using learning to rank by directly optimizing the assignment's expected profit given limited capacity.
  arXiv  Detail & Related papers  (2022-02-09T10:14:45Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.