論文の概要: Online Two-Stage Submodular Maximization

• arxiv url: http://arxiv.org/abs/2510.19480v1
• Date: Wed, 22 Oct 2025 11:18:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:15.731977
• Title: Online Two-Stage Submodular Maximization
• Title（参考訳）: オンライン2段階部分モジュラ最大化
• Authors: Iasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis, Evimaria Terzi,
• Abstract要約: オンライン2段階のサブモジュール最適化(O2SSM)問題を導入し、サブモジュールの目的をオンライン形式で明らかにする。 実データセットを用いた実験により,オンラインアルゴリズムの性能を実証的に検証した。
• 参考スコア（独自算出の注目度）: 15.29193118676418
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set so an objective selected u.a.r. from the collection attains a high maximal value, on average, when optimized over the restricted ground set. We introduce the Online Two-Stage Submodular Maximization (O2SSM) problem, in which the submodular objectives are revealed in an online fashion. We study this problem for weighted threshold potential functions, a large and important subclass of monotone submodular functions that includes influence maximization, data summarization, and facility location, to name a few. We design an algorithm that achieves sublinear $(1 - 1/e)^2$-regret under general matroid constraints and $(1 - 1/e)(1-e^{-k}k^k/k!)$-regret in the case of uniform matroids of rank $k$; the latter also yields a state-of-the-art bound for the (offline) 2SSM problem. We empirically validate the performance of our online algorithm with experiments on real datasets.
• Abstract（参考訳）: 単調な部分モジュラー関数の集合が与えられた場合、二段部分モジュラー最大化(2SSM) [Balkanski et al , 2016] の目標は基底集合を制限することであり、制限された基底集合に最適化された場合、その集合から選択された目的 u.a.r. が平均して高い最大値を得る。 オンライン2段階のサブモジュール最適化(O2SSM)問題を導入し、サブモジュールの目的をオンライン形式で明らかにする。 本稿では,重み付きしきい値ポテンシャル関数について,影響の最大化,データ要約,施設位置などのモノトン部分モジュラー関数の大規模かつ重要なサブクラスについて検討する。 一般のマトロイド制約の下でサブリニア$(1 - 1/e)^2$-regret と 1 - 1/e)(1-e^{-k}k^k/k!)$-regret を実現するアルゴリズムを設計する。 実データセットを用いた実験により,オンラインアルゴリズムの性能を実証的に検証した。

関連論文リスト

• Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
  マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。 1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。 第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
  論文  参考訳（メタデータ） (2025-09-26T17:16:34Z)
• Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization [56.78271181959529]
  SubLoRAは、サブモジュール関数に基づくローランド適応(LoRA)のランク決定方法である。 提案手法は, 理論的基礎, 2次精度, 実用計算効率の両立を図っている。
  論文  参考訳（メタデータ） (2025-07-02T15:56:40Z)
• Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization [11.296845424426062]
  2段階の準モジュラー問題の目的は、サブモジュラーである与えられた訓練関数を用いて、基底集合を減少させることである。 この問題は、データの要約を含む様々な領域に応用されている。
  論文  参考訳（メタデータ） (2023-09-11T01:00:10Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。 本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
  論文  参考訳（メタデータ） (2023-08-16T19:32:29Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• 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)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
  非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。 また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-09T12:32:14Z)

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

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