論文の概要: Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications

• arxiv url: http://arxiv.org/abs/2411.05318v1
• Date: Fri, 08 Nov 2024 04:20:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:53:41.023676
• Title: Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
• Title（参考訳）: モノトン$k$-submodular Maximizationの公正性:アルゴリズムとその応用
• Authors: Yanhui Zhu, Samik Basu, A. Pavan,
• Abstract要約: 我々は、fair $k$submodular問題を研究し、実行時間$mathO(knB)$で$frac13$近似を開発する。 我々は$k$-submodular関数がアクセスできないが、ほぼアクセス可能な場合にのみ近似を保証する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Submodular optimization has become increasingly prominent in machine learning and fairness has drawn much attention. In this paper, we propose to study the fair $k$-submodular maximization problem and develop a $\frac{1}{3}$-approximation greedy algorithm with a running time of $\mathcal{O}(knB)$. To the best of our knowledge, our work is the first to incorporate fairness in the context of $k$-submodular maximization, and our theoretical guarantee matches the best-known $k$-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a $(\frac{1}{3} - \epsilon)$ approximation with $\mathcal{O}(\frac{kn}{\epsilon} \log \frac{B}{\epsilon})$ evaluations of the function $f$. Furthermore, for both algorithms, we provide approximation guarantees when the $k$-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical research and examined the practical implications of fairness. Specifically, we have addressed the question: ``What is the price of fairness?" through case studies on influence maximization with $k$ topics and sensor placement with $k$ types. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.
• Abstract（参考訳）: サブモジュール最適化は機械学習においてますます顕著になり、公正さが注目を集めている。 本稿では,fair $k$-submodular maximization問題を調査し,$\mathcal{O}(knB)$のランニング時間を持つ$\frac{1}{3}$-approximation greedyアルゴリズムを提案する。 我々の知る限り、我々の研究は、最初に$k$-submodular maximizationという文脈で公正さを取り入れたものであり、我々の理論的保証は、フェアネス制約のない最もよく知られた$k$-submodular maximizationの結果と一致する。 さらに我々は,$$(\frac{1}{3} - \epsilon)$を$\mathcal{O}(\frac{kn}{\epsilon} \log \frac{B}{\epsilon})$で近似する高速しきい値ベースのアルゴリズムを開発した。 さらに、両方のアルゴリズムに対して、$k$-submodular 関数がアクセスできないが、ほぼアクセス可能な場合にのみ近似保証を提供する。 我々は,実証的研究を通じて理論的な知見を広く検証し,フェアネスの実践的意義について検討した。 具体的には、$k$のトピックによる影響の最大化と$k$の型によるセンサ配置のケーススタディを通じて、「公正さの価格は何ですか?」という疑問に対処しました。 実験結果から, 公正性の制約が解の質を著しく損なうことはないことが示された。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint [18.290666675596984]
  非単調制約部分モジュラー・サブアニメーションは、様々な機械学習応用において重要な役割を果たす。 既存のアルゴリズムは、近似保証と実用効率のトレードオフにしばしば苦労する。 我々は,$0.385$-approximationの保証と$O(n+k2)$の低い,実用的なクエリ複雑性を組み合わせた新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-22T20:56:57Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Minimum Cost Adaptive Submodular Cover [4.680686256929023]
  適応部分モジュラ函数の最小コスト被覆の問題を考える。 このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
  論文  参考訳（メタデータ） (2022-08-17T15:26:47Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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