論文の概要: Monotone Individual Fairness
- arxiv url: http://arxiv.org/abs/2403.06812v1
- Date: Mon, 11 Mar 2024 15:32:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-12 18:36:20.946646
- Title: Monotone Individual Fairness
- Title（参考訳）: モノトーンの個性
- Authors: Yahav Bechavod
- Abstract要約: オンライン学習者が予測精度を最大化し、類似した個人が同じように扱われることを保証することを目的として、オンライン学習の問題を個別の公正さで再考する。
監査者からのフィードバックを集約できる監査方式を検討する。
ここでは, 後悔, フェアネス違反の数に対して$(mathcalO(T2/3+2b),mathcalO(T5/6-b))$を0leq b leq$で上限とするオラクル効率アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 3.20902205123321
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of online learning with individual fairness, where an
online learner strives to maximize predictive accuracy while ensuring that
similar individuals are treated similarly. We first extend the frameworks of
Gillen et al. (2018); Bechavod et al. (2020), which rely on feedback from human
auditors regarding fairness violations, as we consider auditing schemes that
are capable of aggregating feedback from any number of auditors, using a rich
class we term monotone aggregation functions. We then prove a characterization
for such auditing schemes, practically reducing the analysis of auditing for
individual fairness by multiple auditors to that of auditing by
(instance-specific) single auditors. Using our generalized framework, we
present an oracle-efficient algorithm achieving an upper bound frontier of
$(\mathcal{O}(T^{1/2+2b}),\mathcal{O}(T^{3/4-b}))$ respectively for regret,
number of fairness violations, for $0\leq b \leq 1/4$. We then study an online
classification setting where label feedback is available for
positively-predicted individuals only, and present an oracle-efficient
algorithm achieving an upper bound frontier of
$(\mathcal{O}(T^{2/3+2b}),\mathcal{O}(T^{5/6-b}))$ for regret, number of
fairness violations, for $0\leq b \leq 1/6$. In both settings, our algorithms
improve on the best known bounds for oracle-efficient algorithms. Furthermore,
our algorithms offer significant improvements in computational efficiency,
greatly reducing the number of required calls to an (offline) optimization
oracle per round, to $\tilde{\mathcal{O}}(\alpha^{-2})$ in the full information
setting, and $\tilde{\mathcal{O}}(\alpha^{-2} + k^2T^{1/3})$ in the partial
information setting, where $\alpha$ is the sensitivity for reporting fairness
violations, and $k$ is the number of individuals in a round.
- Abstract（参考訳）: オンライン学習者は、類似した個人が同じように扱われることを確実にしながら、予測精度を最大化しようと試みる。
我々はまず,多数の監査者からのフィードバックを集約可能な監査スキームを,リッチクラスでモノトン集約関数(monotone aggregate function)と呼ぶことから検討し,まず,公正違反に関する人間の監査者からのフィードバックに依存するGillen et al. (2018), Bechavod et al. (2020) のフレームワークを拡張した。
そして、このような監査方式の特徴を実証し、複数の監査者による個別の公正度に対する監査の分析を、(インスタンス固有の)単一監査者による監査と比較する。
一般化された枠組みを用いて、後悔と公正な違反の数に対してそれぞれ$(\mathcal{O}(T^{1/2+2b}),\mathcal{O}(T^{3/4-b})$の上限フロンティアを達成するオラクル効率アルゴリズムを、$0\leq b \leq 1/4$に対して提示する。
次に、正に予測された個人のみにラベルフィードバックが利用できるオンライン分類環境について検討し、その上界フロンティアが$(\mathcal{O}(T^{2/3+2b}),\mathcal{O}(T^{5/6-b})$に対して$0\leq b \leq 1/6$となるようなオラクル効率のアルゴリズムを提示する。
両方の設定において、我々のアルゴリズムはオラクル効率のアルゴリズムの最もよく知られた境界を改善している。
さらに、本アルゴリズムは計算効率を大幅に改善し、1ラウンドあたりの(オフライン)最適化オラクルへの要求呼び出し数を大幅に削減し、全情報設定で$\tilde{\mathcal{o}}(\alpha^{-2})$、部分情報設定で$\tilde{\mathcal{o}}(\alpha^{-2} + k^2t^{1/3})$となり、$\alpha$はフェアネス違反を報告するための感度であり、$k$はラウンド内の個人数である。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Fair Active Ranking from Pairwise Preferences [6.102498508368527]
解離群に属する$n$の項目が与えられたとき、我々のゴールは、我々が提案する公正な目的関数に従って$(epsilon, delta)$-PACF-Rankingを見つけることである。
グループブラインドとグループアウェアの両方のアルゴリズムを提示し,そのサンプルパラメータを解析する。
論文 参考訳（メタデータ） (2024-02-05T18:09:48Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - Oracle Efficient Online Multicalibration and Omniprediction [15.476402844435704]
オンライン逆境設定における全方位予測について検討する。
我々は、無限ベンチマーククラス$F$に対してよく定義された新しいオンラインマルチキャリブレーションアルゴリズムを開発した。
我々は、我々のレートが改善できる範囲について、上と下の境界を示す。
論文 参考訳（メタデータ） (2023-07-18T06:34:32Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Individually Fair Learning with One-Sided Feedback [15.713330010191092]
我々は,学習者が正に予測されたインスタンスに対してのみ真のラベルを観察できる,一方的なフィードバックを伴うオンライン学習問題を考察する。
各ラウンドで$k$インスタンスが到着し、学習者が配置したランダム化ポリシーに従って分類結果を受け取る。
そこで我々は,一方的なフィードバックによるオンライン学習の問題から,文脈的半帯域問題に対する公平性違反を報告したパネルを構築。
論文 参考訳（メタデータ） (2022-06-09T12:59:03Z) - Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries [29.598518028635716]
オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。
このスムーズな分析設定のために,本研究は,スムーズな相手を持つオンライン学習のための最初のオラクル効率のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-17T09:49:40Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。