論文の概要: Variational Optimization for the Submodular Maximum Coverage Problem

• arxiv url: http://arxiv.org/abs/2006.05583v1
• Date: Wed, 10 Jun 2020 00:50:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 04:56:00.503838
• Title: Variational Optimization for the Submodular Maximum Coverage Problem
• Title（参考訳）: submodular maximum coverage問題に対する変分最適化
• Authors: Jian Du, Zhigang Hua, Shuang Yang
• Abstract要約: この問題に対する最初の変分近似は、ネムハウザーの発散に基づくものである。 いくつかの公開データセットといくつかのアプリケーションタスクでそれを実証的に評価する。
• 参考スコア（独自算出の注目度）: 11.734438054316147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We examine the \emph{submodular maximum coverage problem} (SMCP), which is related to a wide range of applications. We provide the first variational approximation for this problem based on the Nemhauser divergence, and show that it can be solved efficiently using variational optimization. The algorithm alternates between two steps: (1) an E step that estimates a variational parameter to maximize a parameterized \emph{modular} lower bound; and (2) an M step that updates the solution by solving the local approximate problem. We provide theoretical analysis on the performance of the proposed approach and its curvature-dependent approximate factor, and empirically evaluate it on a number of public data sets and several application tasks.
• Abstract（参考訳）: 我々は,広範囲のアプリケーションに関連する問題である \emph{submodular maximum coverage problem} (smcp) について検討する。 我々はネムハウザーの発散に基づくこの問題に対する最初の変分近似を提案し、変分最適化を用いて効率よく解けることを示す。 このアルゴリズムは、(1)変動パラメータを推定してパラメータ化された \emph{modular} 下限を最大化するeステップ、(2)局所近似問題を解くことで解を更新するmステップの2つのステップを交互に行う。 提案手法の性能と曲率依存性の近似因子に関する理論的解析を行い,いくつかの公開データセットといくつかのアプリケーションタスクで実証的に評価した。

関連論文リスト

• Consistent Submodular Maximization [27.266085572522847]
  定性制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習におけるいくつかの応用において古典的な最適化課題である。 本稿では, 安定解を持ちながら, ストリーミング方式で要素が到着し, 最適解に対する定数近似が維持されるという, 一貫性の制約のある動的環境において, この問題を考察する。 この設定では、一貫性と近似品質のトレードオフが異なるアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2024-05-30T11:59:58Z)
• Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
  本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。 数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
  論文  参考訳（メタデータ） (2023-08-31T14:16:30Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression [34.99564569478268]
  我々は,任意の$ell_p$近似誤差に対して,そのような解を効率よく最小時間で得る方法を示す。 本稿では, 凸関数を一括フィッティングする手法を提案し, 最適性を保証するとともに, 略スパースアフィン領域を提案する。
  論文  参考訳（メタデータ） (2020-11-06T15:17:00Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)
• On the implementation of a global optimization method for mixed-variable problems [0.30458514384586394]
  このアルゴリズムは、グットマンの放射基底関数と、レジスとシューメーカーの計量応答面法に基づいている。 これら2つのアルゴリズムの一般化と改良を目的としたいくつかの修正を提案する。
  論文  参考訳（メタデータ） (2020-09-04T13:36:56Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  複数の異なる損失を最小化しなければならない最適化問題を考える。 提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
  論文  参考訳（メタデータ） (2020-07-14T09:50:33Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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