論文の概要: Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice

• arxiv url: http://arxiv.org/abs/2111.10175v1
• Date: Fri, 19 Nov 2021 12:07:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-22 16:11:58.335287
• Title: Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
• Title（参考訳）: 整数格子上の単調部分モジュラー関数最大化のためのランダム化アルゴリズム
• Authors: Alberto Schiabel and Vyacheslav Kungurtsev and Jakub Marecek
• Abstract要約: 濃度制約を受ける有界整数格子上の単調部分モジュラ函数を最大化する問題を考える。 特に、DR-部分モジュラ函数の最大化、すなわち減少するリターン特性を示す整数格子上で定義される関数に焦点をあてる。 提案したアルゴリズムを整数格子に適用することは、設定された領域に対する目標問題を減らし、最も高速に設定された部分モジュラーアルゴリズムを適用するなど、他のアルゴリズムよりも高速である。
• 参考スコア（独自算出の注目度）: 5.543220407902113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization problems with set submodular objective functions have many real-world applications. In discrete scenarios, where the same item can be selected more than once, the domain is generalized from a 2-element set to a bounded integer lattice. In this work, we consider the problem of maximizing a monotone submodular function on the bounded integer lattice subject to a cardinality constraint. In particular, we focus on maximizing DR-submodular functions, i.e., functions defined on the integer lattice that exhibit the diminishing returns property. Given any epsilon > 0, we present a randomized algorithm with probabilistic guarantees of O(1 - 1/e - epsilon) approximation, using a framework inspired by a Stochastic Greedy algorithm developed for set submodular functions by Mirzasoleiman et al. We then show that, on synthetic DR-submodular functions, applying our proposed algorithm on the integer lattice is faster than the alternatives, including reducing a target problem to the set domain and then applying the fastest known set submodular maximization algorithm.
• Abstract（参考訳）: 集合部分モジュラー目的関数の最適化問題には実世界の多くの応用がある。 同じ項目を1回以上選択できるような離散的なシナリオでは、領域は2要素集合から有界整数格子へと一般化される。 本研究では,濃度制約を受ける有界整数格子上の単調部分モジュラ関数を最大化する問題を考える。 特に、drm-submodular関数、すなわち減少する戻り値特性を示す整数格子上で定義される関数の最大化に焦点をあてる。 任意の epsilon > 0 が与えられたとき、Mirzasoleiman らによる部分モジュラ函数の設定のために開発された確率的グリーディアルゴリズムに着想を得たフレームワークを用いて、O(1 - 1/e - epsilon)近似の確率的保証を持つランダム化アルゴリズムを提案する。 次に, 合成DR-部分モジュラー関数において, 提案したアルゴリズムを整数格子に適用することは, 対象問題を目標領域に還元し, 最高速の集合部分モジュラー最大化アルゴリズムを適用するなど, 選択肢よりも高速であることを示す。

関連論文リスト

• Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
  Submodularは、人工知能の分野における様々な分野に広く応用されている。 部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。 証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
  論文  参考訳（メタデータ） (2023-08-21T11:48:34Z)
• Supermodular Rank: Set Function Decomposition and Optimization [2.578242050187029]
  格子上の函数の超モジュラー階数を定義する。 準モジュラーランクを類似的に定義する。 部分モジュラ分解を用いて集合関数を最適化する。
  論文  参考訳（メタデータ） (2023-05-24T02:09:28Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
  まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。 第二に、完全適応部分モジュラリティの概念を導入する。 提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
  論文  参考訳（メタデータ） (2020-07-08T15:54:28Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)

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

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