Fair Best Arm Identification with Fixed Confidence

• URL: http://arxiv.org/abs/2408.17313v1
• Date: Fri, 30 Aug 2024 14:18:34 GMT
• Title: Fair Best Arm Identification with Fixed Confidence
• Authors: Alessio Russo, Filippo Vannella,
• Abstract summary: We present a novel framework for Best Arm Identification (BAI) under fairness constraints. We propose F-TaS, an algorithm provably matching the sample complexity lower bound. Numerical results show the efficiency of F-TaS in minimizing the sample complexity while achieving low fairness violations.
• Score: 4.6193503399184275
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we present a novel framework for Best Arm Identification (BAI) under fairness constraints, a setting that we refer to as \textit{F-BAI} (fair BAI). Unlike traditional BAI, which solely focuses on identifying the optimal arm with minimal sample complexity, F-BAI also includes a set of fairness constraints. These constraints impose a lower limit on the selection rate of each arm and can be either model-agnostic or model-dependent. For this setting, we establish an instance-specific sample complexity lower bound and analyze the \textit{price of fairness}, quantifying how fairness impacts sample complexity. Based on the sample complexity lower bound, we propose F-TaS, an algorithm provably matching the sample complexity lower bound, while ensuring that the fairness constraints are satisfied. Numerical results, conducted using both a synthetic model and a practical wireless scheduling application, show the efficiency of F-TaS in minimizing the sample complexity while achieving low fairness violations.

Related papers

• Exploration in the Limit [37.0278529107694]
  We introduce a relaxed formulation that requires valid error control with respect to a minimum sample size.<n>This aligns with many real-world settings that often involve weak signals, high desired significance, and post-experiment inference requirements.<n>We develop a novel, anytime-valid confidence sequences over arm indices, and we use it to design a new BAI algorithm for our framework.
  arXiv  Detail & Related papers  (2025-12-31T19:27:59Z)
• Modest-Align: Data-Efficient Alignment for Vision-Language Models [67.48633659305592]
  Cross-modal alignment models often suffer from overconfidence and degraded performance when operating in resource-constrained settings.<n>We propose Modest-Align, a lightweight alignment framework designed for robustness and efficiency.<n>Our method offers a practical and scalable solution for cross-modal alignment in real-world, low-resource scenarios.
  arXiv  Detail & Related papers  (2025-10-24T16:11:10Z)
• Chance-constrained Flow Matching for High-Fidelity Constraint-aware Generation [46.932479632530764]
  Chance-constrained Flow Matching integrates optimization into the sampling process, enabling effective enforcement of hard constraints.<n>Experiments show that CCFM outperforms current state-of-the-art constrained generative models in modeling complex physical systems.
  arXiv  Detail & Related papers  (2025-09-29T17:56:52Z)
• Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
  We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags.<n>Despite the partial observability, the goal is still to achieve small regret at the level of individual examples.<n>We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal.
  arXiv  Detail & Related papers  (2025-05-08T15:45:23Z)
• FedTilt: Towards Multi-Level Fairness-Preserving and Robust Federated Learning [12.713572267830658]
  textttFedTilt is a novel FL that can preserve multi-level fairness and be robust to outliers. We show how tuning tilt values can achieve the two-level fairness and mitigate the persistent outliers.
  arXiv  Detail & Related papers  (2025-03-15T19:57:23Z)
• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint. Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods. We show that our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification.
  arXiv  Detail & Related papers  (2024-10-17T00:49:53Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• ConstraintMatch for Semi-constrained Clustering [32.92933231199262]
  Constrained clustering allows the training of classification models using pairwise constraints only, which are weak and relatively easy to mine. We propose a semi-supervised context whereby a large amount of textitunconstrained data is available alongside a smaller set of constraints, and propose textitConstraintMatch to leverage such unconstrained data.
  arXiv  Detail & Related papers  (2023-11-26T19:31:52Z)
• Deep Boosting Multi-Modal Ensemble Face Recognition with Sample-Level Weighting [11.39204323420108]
  Deep convolutional neural networks have achieved remarkable success in face recognition. The current training benchmarks exhibit an imbalanced quality distribution. This poses issues for generalization on hard samples since they are underrepresented during training. Inspired by the well-known AdaBoost, we propose a sample-level weighting approach to incorporate the importance of different samples into the FR loss.
  arXiv  Detail & Related papers  (2023-08-18T01:44:54Z)
• Breaking the Spurious Causality of Conditional Generation via Fairness Intervention with Corrective Sampling [77.15766509677348]
  Conditional generative models often inherit spurious correlations from the training dataset. This can result in label-conditional distributions that are imbalanced with respect to another latent attribute. We propose a general two-step strategy to mitigate this issue.
  arXiv  Detail & Related papers  (2022-12-05T08:09:33Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We show that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model.
  arXiv  Detail & Related papers  (2022-02-11T03:01:45Z)
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning [29.552894877883883]
  We show that there exists a tradeoff between achieving low regret and identifying an $epsilon$-optimal policy at the instance-optimal rate. We propose and analyze a novel, planning-based algorithm which attains this sample complexity. We show that our algorithm is nearly minimax optimal, and on several examples that our instance-dependent sample complexity offers significant improvements over worst-case bounds.
  arXiv  Detail & Related papers  (2021-08-05T16:34:17Z)
• Best Arm Identification in Spectral Bandits [0.0]
  Best Arm Identification (BAI) is an important challenge in many applications ranging from parameter tuning to clinical trials. We study best-arm identification with fixed confidence in bandit models with graph smoothness constraint.
  arXiv  Detail & Related papers  (2020-05-20T04:12:04Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.