論文の概要: Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings
- arxiv url: http://arxiv.org/abs/2202.03237v1
- Date: Mon, 7 Feb 2022 14:43:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-08 18:13:53.335171
- Title: Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings
- Title（参考訳）: 効率のよいパレート・オプティカル・フェアネス・アクティビティ・アモルティゼーションのためのexpohedronの導入
- Authors: Till Kletti, Jean-Michel Renders and Patrick Loiseau
- Abstract要約: 我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
- 参考スコア（独自算出の注目度）: 9.066817876491053
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of computing a sequence of rankings that maximizes
consumer-side utility while minimizing producer-side individual unfairness of
exposure. While prior work has addressed this problem using linear or quadratic
programs on bistochastic matrices, such approaches, relying on Birkhoff-von
Neumann (BvN) decompositions, are too slow to be implemented at large scale.
In this paper we introduce a geometrical object, a polytope that we call
expohedron, whose points represent all achievable exposures of items for a
Position Based Model (PBM). We exhibit some of its properties and lay out a
Carath\'eodory decomposition algorithm with complexity $O(n^2\log(n))$ able to
express any point inside the expohedron as a convex sum of at most $n$
vertices, where $n$ is the number of items to rank. Such a decomposition makes
it possible to express any feasible target exposure as a distribution over at
most $n$ rankings. Furthermore we show that we can use this polytope to recover
the whole Pareto frontier of the multi-objective fairness-utility optimization
problem, using a simple geometrical procedure with complexity $O(n^2\log(n))$.
Our approach compares favorably to linear or quadratic programming baselines in
terms of algorithmic complexity and empirical runtime and is applicable to any
merit that is a non-decreasing function of item relevance. Furthermore our
solution can be expressed as a distribution over only $n$ permutations, instead
of the $(n-1)^2 + 1$ achieved with BvN decompositions. We perform experiments
on synthetic and real-world datasets, confirming our theoretical results.
- Abstract（参考訳）: 我々は,消費者側の利便性を最大化する一連のランキングを計算し,生産者側個人の露出の不公平さを最小化する問題を考える。
それまでの作業では、ビスト確率行列上の線形プログラムや二次プログラムを用いてこの問題に対処してきたが、バーホフ・ヴォン・ノイマン(Birkhoff-von Neumann, BvN)分解に依存するアプローチは、大規模に実装するには遅すぎる。
本稿では,測位モデル (PBM) の項目のすべての達成可能な露光をポイントとする幾何学的対象,すなわち「露光子」と呼ぶポリトープを紹介する。
我々は、その性質のいくつかを示し、複素数 $o(n^2\log(n))$ を持つキャラth\'eodory 分解アルゴリズムを配置し、expohedron 内の任意の点を最大$n$頂点の凸和として表現し、ここで $n$ はランク付けすべきアイテムの数である。
このような分解により、少なくとも$n$のランクの分布として実現可能なターゲット露光を表現できる。
さらに、このポリトープを用いて、複雑さ$O(n^2\log(n))$の単純な幾何学的手順を用いて、多目的フェアネスユーティリティ最適化問題のパレートフロンティア全体を復元できることを示す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から線形あるいは二次的なプログラミングベースラインと比較し,項目関連性の非減少関数であるメリットに適用可能である。
さらに、我々の解は、BvN分解で達成された$(n-1)^2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
合成および実世界のデータセットの実験を行い、理論的結果を確認する。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings [7.6275971668447005]
消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。
本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。
さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
論文 参考訳（メタデータ） (2024-02-22T05:48:54Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳（メタデータ） (2021-03-15T11:20:31Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。