論文の概要: Algorithmic Challenges in Ensuring Fairness at the Time of Decision
- arxiv url: http://arxiv.org/abs/2103.09287v3
- Date: Fri, 18 Oct 2024 21:29:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-22 13:15:17.764464
- Title: Algorithmic Challenges in Ensuring Fairness at the Time of Decision
- Title(参考訳): 意思決定時の公正性の確保におけるアルゴリズム的課題
- Authors: Jad Salem, Swati Gupta, Vijay Kamble,
- Abstract要約: 社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で最適化される。
最近の訴訟は、アルゴリズムによる価格設定の慣行を展開している企業を非難している。
凸最適化の文脈において、遠心自由というよく研究された公正性の概念を導入する。
- 参考スコア(独自算出の注目度): 6.228560624452748
- License:
- Abstract: Algorithmic decision-making in societal contexts, such as retail pricing, loan administration, recommendations on online platforms, etc., can be framed as stochastic optimization under bandit feedback, which typically requires experimentation with different decisions for the sake of learning. Such experimentation often results in perceptions of unfairness among people impacted by these decisions; for instance, there have been several recent lawsuits accusing companies that deploy algorithmic pricing practices of price gouging. Motivated by the changing legal landscape surrounding algorithmic decision-making, we introduce the well-studied fairness notion of envy-freeness within the context of stochastic convex optimization. Our notion requires that upon receiving decisions in the present time, groups do not envy the decisions received by any of the other groups, both in the present as well as the past. This results in a novel trajectory-constrained stochastic optimization problem that renders existing techniques inapplicable. The main technical contribution of this work is to show problem settings where there is no gap in achievable regret (up to logarithmic factors) when envy-freeness is imposed. In particular, in our main result, we develop a near-optimal envy-free algorithm that achieves $\tilde{O}(\sqrt{T})$ regret for smooth convex functions that satisfy the PL inequality. This algorithm has a coordinate-descent structure, in which we carefully leverage gradient information to ensure monotonic sampling along each dimension, while avoiding overshooting the constrained optimum with high probability. This latter aspect critically uses smoothness and the structure of the envy-freeness constraints, while the PL inequality allows for sufficient progress towards the optimal solution. We discuss several open questions that arise from this analysis, which may be of independent interest.
- Abstract(参考訳): 小売価格やローン管理、オンラインプラットフォームでのレコメンデーションなどの社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で確率的最適化とみなすことができる。
このような実験は、しばしば、これらの決定に影響された人々の間で不公平な認識をもたらし、例えば、価格上昇のアルゴリズム的な価格設定プラクティスを展開している企業を非難する訴訟が、最近いくつか発生している。
アルゴリズムによる意思決定を取り巻く法的な状況の変化に触発され、確率的凸最適化の文脈において、遠近自由というよく研究された公正性の概念を導入する。
我々の考えは、現在、決定を受ける際に、グループは、現在と過去の両方において、他のどのグループによっても受けられる決定をうらやましくはしない、というものである。
これにより、既存の手法を適用できないような、トラジェクトリ制約付き確率最適化問題が発生する。
この研究の主な技術的貢献は、うらやましい自由が課されるとき、達成可能な後悔(対数的要因まで)にギャップがない問題設定を示すことである。
特に, PLの不等式を満たす滑らかな凸関数に対して, $\tilde{O}(\sqrt{T})$ regret を達成できる準最適エンビーフリーアルゴリズムを開発した。
このアルゴリズムは、勾配情報を慎重に利用して各次元のモノトニックサンプリングを確保するとともに、制約された最適値を高い確率でオーバーシュートすることを避ける。
この後者の側面は滑らかさとエンビ自由度制約の構造を批判的に用い、PL不等式は最適解への十分な前進を可能にする。
この分析から生じるいくつかのオープンな質問について論じるが、これは独立した関心事かもしれない。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models [4.156757591117864]
本稿では,問題に対する仮定を最小化しながら,改善された後悔境界を実現する新しいアルゴリズムを提案する。
本手法は, 一般関数空間を考慮し, 動的価格設定によく用いられる線形評価モデルを超えて拡張する。
論文 参考訳(メタデータ) (2024-06-24T23:43:56Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳(メタデータ) (2023-10-21T18:38:13Z) - Rate-Optimal Policy Optimization for Linear Markov Decision Processes [65.5958446762678]
最安値の$widetilde O (sqrt K)$ regret, $K$はエピソード数を表す。
我々の研究は、バンディットフィードバックのある設定において最適な収束率(w.r.t.$K$)を確立する最初のものである。
現在、最適なレート保証を持つアルゴリズムは知られていない。
論文 参考訳(メタデータ) (2023-08-28T15:16:09Z) - Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods [0.6554326244334866]
シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。
シャープネスは、通常不明な問題固有の定数を伴い、再起動スキームは通常収束率を減少させる。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
論文 参考訳(メタデータ) (2023-01-05T19:01:41Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳(メタデータ) (2022-12-12T21:37:36Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳(メタデータ) (2022-05-02T08:48:22Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
マルコフ連鎖の適応制御のためのRBMLE(Reward-Biased Maximum Likelihood Estimate)を提案した。
我々は、現在最先端のアルゴリズムと同様に、$mathcalO( log T)$が$T$の時間的水平線上で後悔していることを示します。
論文 参考訳(メタデータ) (2020-11-16T06:09:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。