Fair Active Ranking from Pairwise Preferences
- URL: http://arxiv.org/abs/2402.03252v1
- Date: Mon, 5 Feb 2024 18:09:48 GMT
- Title: Fair Active Ranking from Pairwise Preferences
- Authors: Sruthi Gorantla and Sara Ahmadian
- Abstract summary: Given a set of $n$ items that belong to disjoint groups, our goal is to find an $(epsilon, delta)$-PACF-Ranking according to a fair objective function that we propose.
We present both group-blind and group-aware algorithms and analyze their sample parameters.
- Score: 6.102498508368527
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the problem of probably approximately correct and fair (PACF)
ranking of items by adaptively evoking pairwise comparisons. Given a set of $n$
items that belong to disjoint groups, our goal is to find an $(\epsilon,
\delta)$-PACF-Ranking according to a fair objective function that we propose.
We assume access to an oracle, wherein, for each query, the learner can choose
a pair of items and receive stochastic winner feedback from the oracle. Our
proposed objective function asks to minimize the $\ell_q$ norm of the error of
the groups, where the error of a group is the $\ell_p$ norm of the error of all
the items within that group, for $p, q \geq 1$. This generalizes the objective
function of $\epsilon$-Best-Ranking, proposed by Saha & Gopalan (2019).
By adopting our objective function, we gain the flexibility to explore
fundamental fairness concepts like equal or proportionate errors within a
unified framework. Adjusting parameters $p$ and $q$ allows tailoring to
specific fairness preferences. We present both group-blind and group-aware
algorithms and analyze their sample complexity. We provide matching lower
bounds up to certain logarithmic factors for group-blind algorithms. For a
restricted class of group-aware algorithms, we show that we can get reasonable
lower bounds. We conduct comprehensive experiments on both real-world and
synthetic datasets to complement our theoretical findings.
Related papers
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct.
Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
arXiv Detail & Related papers (2024-06-18T08:54:04Z) - Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds.
The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
arXiv Detail & Related papers (2024-05-31T19:26:05Z) - Monotone Individual Fairness [3.20902205123321]
We revisit the problem of online learning with individual fairness, where an online learner strives to maximize predictive accuracy while ensuring similar individuals are treated similarly.
We consider auditing schemes that are capable of aggregating feedback from any number of auditors.
We present an oracle-efficient algorithm achieving an upper bound of $(mathcalO(T2/3+2b),mathcalO(T5/6-b))$ for regret, number of fairness violations, for $0leq b leq$.
arXiv Detail & Related papers (2024-03-11T15:32:56Z) - Detection of Groups with Biased Representation in Ranking [28.095668425175564]
We study the problem of detecting groups with biased representation in the top-$k$ ranked items.
We propose efficient search algorithms for two different fairness measures.
arXiv Detail & Related papers (2022-12-30T10:50:02Z) - Sampling Ex-Post Group-Fair Rankings [8.963918049835375]
We propose two algorithms to sample a random group-fair ranking from the distribution $D$ mentioned above.
Our problem formulation works even when there is implicit bias, incomplete relevance information, or only ordinal ranking is available.
We give empirical evidence that our algorithms compare favorably against recent baselines for fairness and ranking utility on real-world data sets.
arXiv Detail & Related papers (2022-03-02T05:59:26Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
We study the linear contextual bandit problem in the presence of adversarial corruption.
We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
arXiv Detail & Related papers (2021-10-25T02:53:24Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
We consider the basic problem of querying an expert oracle for labeling a dataset in machine learning.
We present a randomized batch algorithm that operates on a round-by-round basis to label the samples and achieves a query rate of $O(fracNk2)$.
In addition, we present an adaptive greedy query scheme, which achieves an average rate of $approx 0.2N$ queries per sample with triplet queries.
arXiv Detail & Related papers (2021-10-05T20:15:35Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem.
We show that by making few queries, the problem becomes easier to solve.
arXiv Detail & Related papers (2021-06-04T02:32:26Z) - Multi-group Agnostic PAC Learnability [7.9649015115693444]
We study "multi-group agnostic PAC learnability"
We provide a characterization of the loss functions for which such a predictor is guaranteed to exist.
Our results unify and extend previous positive and negative results from the multi-group fairness literature.
arXiv Detail & Related papers (2021-05-20T18:43:36Z) - Fair for All: Best-effort Fairness Guarantees for Classification [11.818794470895837]
Group-based notions of fairness try to equalize absolute measures of performance across known groups.
We propose a notion whose guarantee, on each group $g$ in a class $mathcalG$, is relative to the performance of the best classifier on $g$.
We test our algorithms on real-world data sets, and present interesting comparative insights on their performance.
arXiv Detail & Related papers (2020-12-18T13:22:14Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers.
We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
arXiv Detail & Related papers (2020-02-26T16:19:09Z)
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.