論文の概要: Trading-off price for data quality to achieve fair online allocation
- arxiv url: http://arxiv.org/abs/2306.13440v2
- Date: Mon, 4 Dec 2023 15:27:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-05 23:10:32.058783
- Title: Trading-off price for data quality to achieve fair online allocation
- Title(参考訳): 公平なオンラインアロケーションを実現するためのデータ品質の取引価格
- Authors: Mathieu Molina, Nicolas Gast, Patrick Loiseau, Vianney Perchet
- Abstract要約: オンラインアロケーションの問題は、長期的公正なペナルティに該当すると考えられる。
両問題を共同で解き,$mathcalO(sqrtT)$で有界な後悔を示すアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 25.154957931903525
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of online allocation subject to a long-term fairness
penalty. Contrary to existing works, however, we do not assume that the
decision-maker observes the protected attributes -- which is often unrealistic
in practice. Instead they can purchase data that help estimate them from
sources of different quality; and hence reduce the fairness penalty at some
cost. We model this problem as a multi-armed bandit problem where each arm
corresponds to the choice of a data source, coupled with the online allocation
problem. We propose an algorithm that jointly solves both problems and show
that it has a regret bounded by $\mathcal{O}(\sqrt{T})$. A key difficulty is
that the rewards received by selecting a source are correlated by the fairness
penalty, which leads to a need for randomization (despite a stochastic
setting). Our algorithm takes into account contextual information available
before the source selection, and can adapt to many different fairness notions.
We also show that in some instances, the estimates used can be learned on the
fly.
- Abstract(参考訳): オンラインアロケーションの問題は、長期的公正なペナルティの対象となる。
しかし、既存の作業とは対照的に、意思決定者が保護された属性を観察しているとは考えません。
代わりに、異なる品質のソースからデータを評価するのに役立つデータを購入することができるため、ある程度のコストでフェアネスペナルティを低減できる。
我々は、この問題を、各アームがデータソースの選択に対応し、オンラインアロケーション問題と組み合わせたマルチアームバンディット問題としてモデル化する。
両問題を共同で解くアルゴリズムを提案し,$\mathcal{o}(\sqrt{t})$ で区切られた後悔を示す。
重要な困難は、ソースを選択することで得られる報酬がフェアネスペナルティによって相関し、(確率的な設定にもかかわらず)ランダム化の必要性が生じることである。
本アルゴリズムは,ソース選択前に利用可能な文脈情報を考慮して,多種多様なフェアネス概念に適応できる。
また、いくつかの例では、使用済みの見積もりをオンザフライで学習できることも示しています。
関連論文リスト
- Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Striking a Balance: An Optimal Mechanism Design for Heterogenous
Differentially Private Data Acquisition for Logistic Regression [8.45602005745865]
プライバシに敏感な販売者から収集したデータに対してロジスティック回帰を行う際の問題点について検討する。
データは非公開であるため、販売者は支払いを通じてインセンティブを得る必要がある。
論文 参考訳(メタデータ) (2023-09-19T05:51:13Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-21T00:17:24Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳(メタデータ) (2023-01-31T03:49:00Z) - The Power and Limitation of Pretraining-Finetuning for Linear Regression
under Covariate Shift [127.21287240963859]
本研究では,対象データに基づく事前学習と微調整を併用した伝達学習手法について検討する。
大規模な線形回帰インスタンスの場合、$O(N2)$ソースデータによる転送学習は、$N$ターゲットデータによる教師あり学習と同じくらい効果的である。
論文 参考訳(メタデータ) (2022-08-03T05:59:49Z) - Understanding Unfairness in Fraud Detection through Model and Data Bias
Interactions [4.159343412286401]
アルゴリズムの不公平性は、データ内のモデルとバイアスの間の相互作用に起因すると我々は主張する。
フェアネスブラインドMLアルゴリズムが示す公平さと正確さのトレードオフに関する仮説を、異なるデータバイアス設定下で検討する。
論文 参考訳(メタデータ) (2022-07-13T15:18:30Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳(メタデータ) (2022-03-18T08:03:20Z) - Nonstationary Dual Averaging and Online Fair Allocation [32.85609942201268]
非定常入力モデルに基づく二値平均化アルゴリズムの新しいオンライン学習結果を開発した。
本研究は,非定常入力モデルとして,敵対的汚職,エルゴディック入力,ブロック非依存入力(周期的入力を含む)の2つに適用した。
論文 参考訳(メタデータ) (2022-02-23T16:50:24Z) - Fairer LP-based Online Allocation [13.478067250930101]
本稿では,リニアプログラム(LP)に基づくオンラインリソース割り当て問題について考察する。
内部点LPソルバを用いて不公平な資源支出を動的に検出するフェアアルゴリズムを提案する。
提案手法は最適化インスタンスの制約としてフェアネス要件を定式化せず,アルゴリズム設計の観点からこの問題に対処する。
論文 参考訳(メタデータ) (2021-10-27T17:45:20Z) - The Importance of Modeling Data Missingness in Algorithmic Fairness: A
Causal Perspective [14.622708494548363]
機械学習のためのトレーニングデータセットには、ある種の欠落があることが多い。
この欠如は、無視されると、モデルのデプロイ時にトレーニング手順のフェアネス保証を無効にする。
一般的な公平性アルゴリズムで使用される様々な分布が、トレーニングデータから回復できない、または回復できない条件を示します。
論文 参考訳(メタデータ) (2020-12-21T16:10:00Z) - Algorithmic Decision Making with Conditional Fairness [48.76267073341723]
条件付きフェアネスを、条件付きフェアネス変数の条件付けにより、より健全なフェアネス計量として定義する。
本稿では,アルゴリズム決定の精度と公平性のトレードオフを追跡するために,導出条件公正規則化器(DCFR)を提案する。
論文 参考訳(メタデータ) (2020-06-18T12:56:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。