論文の概要: Fairness in Submodular Maximization over a Matroid Constraint

• arxiv url: http://arxiv.org/abs/2312.14299v1
• Date: Thu, 21 Dec 2023 21:12:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-25 16:50:14.891798
• Title: Fairness in Submodular Maximization over a Matroid Constraint
• Title（参考訳）: マトロイド制約上の部分モジュラー最大化の公平性
• Authors: Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, Thuy-Duong Vuong
• Abstract要約: マトロイド制約上の部分モジュラーは、機械学習における様々な応用における基本的な問題である。 本稿では,品質,公平性,汎用性に異なるトレードオフをもたらす,様々なアルゴリズムと不合理性の結果を提案する。
• 参考スコア（独自算出の注目度）: 14.402156575758559
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attributes such as gender or race. In such settings, it is crucial to guarantee that the selected solution is fairly distributed with respect to this attribute. Recently, fairness has been investigated in submodular maximization under a cardinality constraint in both the streaming and offline settings, however the more general problem with matroid constraint has only been considered in the streaming setting and only for monotone objectives. This work fills this gap. We propose various algorithms and impossibility results offering different trade-offs between quality, fairness, and generality.
• Abstract（参考訳）: マトロイド制約上のサブモジュラー最大化は、機械学習における様々な応用において根本的な問題である。 これらのアプリケーションの中には、性別や人種などのセンシティブな属性を持つデータポイントに対する意思決定を含むものもある。 このような設定では、選択されたソリューションがこの属性に対してかなり分散していることを保証することが重要です。 近年,ストリーミング設定とオフライン設定の両方において,濃度制約の下でのサブモジュラー最大化についてフェアネスが研究されているが,マトロイド制約に関するより一般的な問題はストリーミング設定においてのみ考慮されており,モノトーン目的のみである。 この仕事はこのギャップを埋める。 本稿では,品質,公平性,汎用性に異なるトレードオフをもたらす様々なアルゴリズムと不合理性の結果を提案する。

関連論文リスト

• MultiMax: Sparse and Multi-Modal Attention Learning [60.49318008131978]
  SoftMaxは現代の機械学習アルゴリズムのユビキタスな成分である。 分散性はSoftMaxの変種族によって達成できるが、それらはしばしば代替損失関数を必要とし、多重モダリティを保たない。 入力入力範囲に応じて出力分布を適応的に変調するMultiMaxを提案する。
  論文  参考訳（メタデータ） (2024-06-03T10:51:43Z)
• Fairness in Streaming Submodular Maximization over a Matroid Constraint [19.27202441717429]
  この問題の自然な一般化をマトロイド制約に当てはめる。 ストリーミングアルゴリズムと、効率、品質、公正性のトレードオフを提供する非可視性結果を提供しています。
  論文  参考訳（メタデータ） (2023-05-24T13:10:46Z)
• Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
  オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。 ソフトマージン条件下でのバニラQ関数の類似した結果を示す。 我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
  論文  参考訳（メタデータ） (2023-02-05T14:22:41Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Group Equality in Adaptive Submodular Maximization [13.619980548779687]
  非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。 この問題に対する最初の定数近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-07T15:12:02Z)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to a Knapsack Constraint [26.171841086317574]
  ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。 アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。 私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
  論文  参考訳（メタデータ） (2021-04-10T20:11:11Z)
• Frequency-aware Discriminative Feature Learning Supervised by Single-Center Loss for Face Forgery Detection [89.43987367139724]
  顔の偽造検出は、コンピュータビジョンへの関心をますます高めている。 近年の業績は良好なものとなっているが、いまだに無視できない問題がある。 本稿では,新しい周波数認識型特徴学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-03-16T14:17:17Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  本論文は,最適化が容易なjmmdの統一形式を理論的に導出する。 統合JMMDから、JMMDは分類に有利な特徴ラベル依存を低下させることを示す。 本稿では,その依存を促進する新たなmmd行列を提案し,ラベル分布シフトにロバストな新しいラベルカーネルを考案する。
  論文  参考訳（メタデータ） (2021-01-25T09:46:14Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  min-max問題(英: min-max problem)またはサドル点問題(英: saddle point problem)は、サムゲームにおいても研究されるクラス逆問題である。
  論文  参考訳（メタデータ） (2020-06-15T05:33:42Z)
• Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
  我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。 この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。 近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
  論文  参考訳（メタデータ） (2020-06-01T01:28:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。