論文の概要: Decomposable Submodular Maximization in Federated Setting

• arxiv url: http://arxiv.org/abs/2402.00138v1
• Date: Wed, 31 Jan 2024 19:32:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-02 17:53:11.425954
• Title: Decomposable Submodular Maximization in Federated Setting
• Title（参考訳）: フェデレーション設定における分解可能部分モジュラ最大化
• Authors: Akbar Rafiey
• Abstract要約: 本稿では,デコンポザブルな部分モジュラ最適化のためのエミュレートされた最適化設定を提案する。 この設定では、クライアントは独自の好み関数を持ち、これらの好みの重み付けを最大化する必要がある。 このアルゴリズムは, 上述の手法が存在する場合でも, 近似解が得られることが保証されていることを示す。
• 参考スコア（独自算出の注目度）: 4.07926531936425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular functions, as well as the sub-class of decomposable submodular functions, and their optimization appear in a wide range of applications in machine learning, recommendation systems, and welfare maximization. However, optimization of decomposable submodular functions with millions of component functions is computationally prohibitive. Furthermore, the component functions may be private (they might represent user preference function, for example) and cannot be widely shared. To address these issues, we propose a {\em federated optimization} setting for decomposable submodular optimization. In this setting, clients have their own preference functions, and a weighted sum of these preferences needs to be maximized. We implement the popular {\em continuous greedy} algorithm in this setting where clients take parallel small local steps towards the local solution and then the local changes are aggregated at a central server. To address the large number of clients, the aggregation is performed only on a subsampled set. Further, the aggregation is performed only intermittently between stretches of parallel local steps, which reduces communication cost significantly. We show that our federated algorithm is guaranteed to provide a good approximate solution, even in the presence of above cost-cutting measures. Finally, we show how the federated setting can be incorporated in solving fundamental discrete submodular optimization problems such as Maximum Coverage and Facility Location.
• Abstract（参考訳）: サブモジュラー関数、および分解可能なサブモジュラー関数のサブクラス、およびそれらの最適化は、機械学習、レコメンデーションシステム、福祉最大化における幅広い応用に現れる。 しかし、数百万の成分関数を持つ分解可能な部分モジュラ関数の最適化は計算上は不可能である。 さらに、コンポーネント関数はプライベートであり(例えば、ユーザー好み関数を表すかもしれない)、広く共有することはできない。 これらの問題に対処するため、分解可能な部分モジュラ最適化のためのフェデレーション最適化設定を提案する。 この設定では、クライアントは独自の好み関数を持ち、これらの好みの重み付けを最大化する必要がある。 この設定では、クライアントはローカルソリューションに向かって並列に小さなローカルステップを踏んで、そのローカルな変更を中央サーバに集約します。 多数のクライアントに対応するために、アグリゲーションはサブサンプルセットでのみ実行される。 さらに、並列ローカルステップのストレッチ間の間欠的にのみアグリゲーションを行い、通信コストを大幅に削減する。 以上のようなコスト削減対策が存在する場合でも,我々のフェデレーションアルゴリズムは近似解が得られることが保証されている。 最後に,最大範囲や施設位置といった基本離散部分モジュラー最適化問題を解くために,フェデレーション設定をどのように組み込むかを示す。

関連論文リスト

• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。 ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。 提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
  論文  参考訳（メタデータ） (2023-10-10T00:21:10Z)
• Maximizing Submodular Functions for Recommendation in the Presence of Biases [25.081136190260015]
  サブセット選択タスクはシステムや検索エンジンで発生し、ユーザの価値を最大化する項目のサブセットを選択するように要求する。 多くの応用において、入力は出力サブセットの有用性を減らす社会的バイアスを持つことが観察されている。 公平性制約に基づく介入は,比例表現の確保だけでなく,バイアスの存在下での準最適性も達成できることを示す。
  論文  参考訳（メタデータ） (2023-05-03T15:20:00Z)
• Balancing Utility and Fairness in Submodular Maximization (Technical Report) [27.20340546154524]
  実用性と公平性のバランスをとるために,emphBi Maxim Submodularization (BSM) と呼ばれる新しい問題を提案する。 BSMは任意の定数係数で近似できないため、効率的なインスタンス依存近似スキームの設計に焦点をあてる。
  論文  参考訳（メタデータ） (2022-11-02T09:38:08Z)
• A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions [18.570591025615453]
  本稿では,高コストで評価可能なマルチモーダル目的関数に対する局所的・言語的ソリューションの集合を見つけるためのマルチモーダルBOフレームワークを開発する。 目的関数とその一階微分の結合分布を解析的に導出する。 本稿では、マルチモーダル設定によく知られたBO取得関数の変種を導入し、提案フレームワークの性能を実証する。
  論文  参考訳（メタデータ） (2022-10-13T00:10:13Z)
• Streaming Adaptive Submodular Maximization [19.29174615532181]
  実用関数の新しいクラス、半政治的な部分モジュラー関数を導入する。 本研究では,ストリームベース環境下での半政治的部分モジュラ関数の最大化に有効なアルゴリズムの開発を行う。
  論文  参考訳（メタデータ） (2022-08-17T02:05:10Z)
• Group Equality in Adaptive Submodular Maximization [13.619980548779687]
  非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。 この問題に対する最初の定数近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-07T15:12:02Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。 このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。 すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  目的関数を滑らかな局所関数と凸(おそらく非滑らか)結合関数の和とするマルチエージェント共有最適化問題について検討する。
  論文  参考訳（メタデータ） (2020-06-15T19:40:24Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  少数のデータポイントで学習したガウス過程を訓練した空間定式化を提案する。 このアプローチはまた、より小さく、計算的にもより安価なサブソルバを低いバウンディングに導く。 提案手法の順序の順序による時間収束を,総じて低減する。
  論文  参考訳（メタデータ） (2020-05-21T20:59:11Z)

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

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