論文の概要: Nonstationary Dual Averaging and Online Fair Allocation
- arxiv url: http://arxiv.org/abs/2202.11614v2
- Date: Mon, 17 Oct 2022 16:53:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-19 15:08:27.035783
- Title: Nonstationary Dual Averaging and Online Fair Allocation
- Title（参考訳）: 非定常デュアル平均化とオンラインフェアアロケーション
- Authors: Luofeng Liao, Yuan Gao, Christian Kroer
- Abstract要約: 非定常入力モデルに基づく二値平均化アルゴリズムの新しいオンライン学習結果を開発した。
本研究は,非定常入力モデルとして,敵対的汚職,エルゴディック入力,ブロック非依存入力(周期的入力を含む)の2つに適用した。
- 参考スコア（独自算出の注目度）: 32.85609942201268
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of fairly allocating items to a set of individuals,
when the items are arriving online. A central solution concept in fair
allocation is competitive equilibrium: every individual is endowed with a
budget of faux currency, and the resulting competitive equilibrium is used to
allocate. For the online fair allocation context, the PACE algorithm of Gao et
al. [2021] leverages the dual averaging algorithm to approximate competitive
equilibria. The authors show that, when items arrive i.i.d, the algorithm
asymptotically achieves the fairness and efficiency guarantees of the offline
competitive equilibrium allocation. However, real-world data is typically not
stationary. One could instead model the data as adversarial, but this is often
too pessimistic in practice. Motivated by this consideration, we study an
online fair allocation setting with nonstationary item arrivals. To address
this setting, we first develop new online learning results for the dual
averaging algorithm under nonstationary input models. We show that the dual
averaging iterates converge in mean square to both the underlying optimal
solution of the "true" stochastic optimization problem as well as the
"hindsight" optimal solution of the finite-sum problem given by the sample
path. Our results apply to several nonstationary input models: adversarial
corruption, ergodic input, and block-independent (including periodic) input.
Here, the bound on the mean square error depends on a nonstationarity measure
of the input. We recover the classical bound when the input data is i.i.d. We
then show that our dual averaging results imply that the PACE algorithm for
online fair allocation simultaneously achieves "best of both worlds" guarantees
against any of these input models. Finally, we conduct numerical experiments
which show strong empirical performance against nonstationary inputs.
- Abstract（参考訳）: 私たちは、アイテムがオンラインに届くとき、アイテムを1組の個人にかなり割り当てる問題を考える。
公正な割当における中心的な解の概念は競争均衡であり、各個人はフェーク通貨の予算が与えられ、結果としての競争均衡が割り当てられる。
オンラインフェアアロケーションのコンテキストでは、GaoらのPACEアルゴリズムが使われる。
2021] は双対平均化アルゴリズムを利用して競合平衡を近似する。
著者らは,アイテムが到着すると,アルゴリズムが漸近的にオフラインの競合均衡割当の公平性と効率性を保証することを示した。
しかし、現実世界のデータは通常定常的ではない。
代わりにデータを逆境としてモデル化することは可能だが、実際には悲観的すぎることが多い。
本研究では,非定常アイテムの到着を考慮したオンラインフェアアロケーション設定について検討する。
そこで我々はまず,非定常入力モデルに基づく二値平均化アルゴリズムの新しいオンライン学習結果を開発した。
双対平均化イテレートは「真の」確率的最適化問題の根底にある最適解と、サンプルパスによって与えられる有限サム問題の「ヒンズー」最適解の両方に平均二乗収束することを示した。
本研究は,非定常入力モデルである逆腐敗,エルゴード入力,ブロック非依存入力(周期的入力を含む)に適用する。
ここで、平均二乗誤差の境界は入力の非定常度尺度に依存する。
入力データがi.i.d.であるとき、古典的な境界を回復し、オンラインフェアアロケーションのペースアルゴリズムがこれらの入力モデルに対して「両方の最良」保証を同時に達成することを示す2つの平均化結果を示す。
最後に,非定常入力に対して強い実験性能を示す数値実験を行った。
関連論文リスト
- Fair Bilevel Neural Network (FairBiNN): On Balancing fairness and accuracy via Stackelberg Equilibrium [0.3350491650545292]
バイアスを緩和する現在の方法は、情報損失と精度と公平性のバランスが不十分であることが多い。
本稿では,二段階最適化の原理に基づく新しい手法を提案する。
私たちのディープラーニングベースのアプローチは、正確性と公平性の両方を同時に最適化します。
論文 参考訳（メタデータ） (2024-10-21T18:53:39Z) - Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。
近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。
本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-11T13:44:49Z) - Preventing Discriminatory Decision-making in Evolving Data Streams [8.952662914331901]
機械学習のバイアスは、ここ10年で明らかに注目を集めている。
意思決定システムのバイアスに対処する最も公正な機械学習(fair-ML)は、オフライン設定のみに焦点を当てている。
オンラインシステムが現実世界で広く普及しているにもかかわらず、オンライン設定におけるバイアスを特定し修正する作業は極めて不十分である。
論文 参考訳（メタデータ） (2023-02-16T01:20:08Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - FairBalance: How to Achieve Equalized Odds With Data Pre-processing [15.392349679172707]
本研究は、機械学習ソフトウェアにおける等化オッズフェアネスを達成するための、単純で効果的な前処理アプローチを提供することにより、ソフトウェア工学社会の利益を目指している。
学習データに計算重みを割り当てることで,各階層群のクラス分布のバランスをとる前処理アルゴリズムであるFairBalanceを提案する。
論文 参考訳（メタデータ） (2021-07-17T20:40:45Z) - Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。
ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。
本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
論文 参考訳（メタデータ） (2021-05-11T03:38:16Z) - Can Active Learning Preemptively Mitigate Fairness Issues? [66.84854430781097]
データセットバイアスは、機械学習における不公平な原因の1つです。
不確実性に基づくALで訓練されたモデルが保護クラスの決定において公平であるかどうかを検討する。
また,勾配反転(GRAD)やBALDなどのアルゴリズム的公正性手法の相互作用についても検討する。
論文 参考訳（メタデータ） (2021-04-14T14:20:22Z) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。
様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。
我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
論文 参考訳（メタデータ） (2020-11-18T18:39:17Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。
目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。
提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
論文 参考訳（メタデータ） (2020-07-07T18:25:25Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳（メタデータ） (2020-07-01T14:24:58Z) - Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking
Fairness and Algorithm Utility [54.179859639868646]
Bipartiteランキングは、ラベル付きデータから正の個人よりも上位の個人をランク付けするスコアリング機能を学ぶことを目的としている。
学習したスコアリング機能が、異なる保護グループ間で体系的な格差を引き起こすのではないかという懸念が高まっている。
本稿では、二部構成のランキングシナリオにおいて、それらのバランスをとるためのモデル後処理フレームワークを提案する。
論文 参考訳（メタデータ） (2020-06-15T10:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。