論文の概要: Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings
- arxiv url: http://arxiv.org/abs/2402.14305v1
- Date: Thu, 22 Feb 2024 05:48:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 16:11:57.971504
- Title: Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings
- Title（参考訳）: 繰り返しランキングにおけるグループ間の効率の良いパレート・オプティカル・ユーティリティ・フェアネスを目指して
- Authors: Phuong Dinh Mai, Duc-Trong Le, Tuan-Anh Hoang, Dung D. Le
- Abstract要約: 消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。
本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。
さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
- 参考スコア（独自算出の注目度）: 7.6275971668447005
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we tackle the problem of computing a sequence of rankings with
the guarantee of the Pareto-optimal balance between (1) maximizing the utility
of the consumers and (2) minimizing unfairness between producers of the items.
Such a multi-objective optimization problem is typically solved using a
combination of a scalarization method and linear programming on bi-stochastic
matrices, representing the distribution of possible rankings of items. However,
the above-mentioned approach relies on Birkhoff-von Neumann (BvN)
decomposition, of which the computational complexity is $\mathcal{O}(n^5)$ with
$n$ being the number of items, making it impractical for large-scale systems.
To address this drawback, we introduce a novel approach to the above problem by
using the Expohedron - a permutahedron whose points represent all achievable
exposures of items. On the Expohedron, we profile the Pareto curve which
captures the trade-off between group fairness and user utility by identifying a
finite number of Pareto optimal solutions. We further propose an efficient
method by relaxing our optimization problem on the Expohedron's circumscribed
$n$-sphere, which significantly improve the running time. Moreover, the
approximate Pareto curve is asymptotically close to the real Pareto optimal
curve as the number of substantial solutions increases. Our methods are
applicable with different ranking merits that are non-decreasing functions of
item relevance. The effectiveness of our methods are validated through
experiments on both synthetic and real-world datasets.
- Abstract（参考訳）: 本稿では,(1)消費者の利便性の最大化と(2)生産者間の不公平性の最小化とのパレート・最適バランスを保証し,ランキングの列を計算する問題に取り組む。
このような多目的最適化問題は、典型的には、スカラー化法と双確率行列上の線形計画法を組み合わせることで解決される。
しかし、上記のアプローチは birkhoff-von neumann (bvn) 分解に依存しており、計算複雑性は $\mathcal{o}(n^5)$ であり、n$ はアイテムの数であり、大規模システムでは現実的ではない。
この欠点に対処するために、アイテムのすべての達成可能な露出を表すパームタヘドロンであるExpohedronを用いて、上記の問題に新しいアプローチを導入する。
本研究では,有限個のパレート最適解を同定することで,グループフェアネスとユーザユーティリティのトレードオフを捉えたパレート曲線をプロファイリングする。
さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
さらに、近似パレート曲線は、実質解の数が増加するにつれて、実パレート最適曲線に漸近的に近い。
本手法は項目関連性の非減少関数である異なるランクのメリットを応用できる。
本手法の有効性は,合成データと実世界データの両方を用いた実験により検証される。
関連論文リスト
- Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
最適公正表現はいくつかの有用な構造特性を持つことを示す。
そこで,これらの近似問題は,凹凸プログラミング法により効率的に解けることを示す。
論文 参考訳（メタデータ） (2024-09-26T08:46:48Z) - Preference-Optimized Pareto Set Learning for Blackbox Optimization [1.9628841617148691]
すべての目的を同時に最適化できる単一のソリューションはありません。
典型的なMOO問題では、目的間の好みを交換する最適解(パレート集合)を見つけることが目的である。
我々の定式化は、例えば微分可能なクロスエントロピー法によって解決できる二段階最適化問題につながる。
論文 参考訳（メタデータ） (2024-08-19T13:23:07Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
論文 参考訳（メタデータ） (2022-02-07T14:43:35Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - A Hybrid 2-stage Neural Optimization for Pareto Front Extraction [3.918940900258555]
最適なトレードオフソリューションに対する大きな障害は、それらが必ずしも互いに収束しないことです。
正確かつ費用対効果の高い二段階アプローチを提案する。
論文 参考訳（メタデータ） (2021-01-27T20:56:19Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Consistent Second-Order Conic Integer Programming for Learning Bayesian
Networks [2.7473982588529653]
連続観測データからBNのスパースDAG構造を学習する問題について検討する。
この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。
ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
論文 参考訳（メタデータ） (2020-05-29T00:13:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。