論文の概要: Fast Submodular Function Maximization

• arxiv url: http://arxiv.org/abs/2305.08367v1
• Date: Mon, 15 May 2023 06:00:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-16 16:01:34.035526
• Title: Fast Submodular Function Maximization
• Title（参考訳）: 高速サブモジュラー関数最大化
• Authors: Lianke Qin, Zhao Song, Yitan Wang
• Abstract要約: 部分モジュラ関数の最大値を効率的に計算する方法を検討する。 各イテレーションでは、データセットは漸進的に変更されるか変更されない。 本稿では,新しい探索木データ構造に基づく新しい手法を提案する。本アルゴリズムでは,$widetildeO(nk + kd2 + nd)$時間のみを要している。
• 参考スコア（独自算出の注目度）: 15.090593955414137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular functions have many real-world applications, such as document summarization, sensor placement, and image segmentation. For all these applications, the key building block is how to compute the maximum value of a submodular function efficiently. We consider both the online and offline versions of the problem: in each iteration, the data set changes incrementally or is not changed, and a user can issue a query to maximize the function on a given subset of the data. The user can be malicious, issuing queries based on previous query results to break the competitive ratio for the online algorithm. Today, the best-known algorithm for online submodular function maximization has a running time of $O(n k d^2)$ where $n$ is the total number of elements, $d$ is the feature dimension and $k$ is the number of elements to be selected. We propose a new method based on a novel search tree data structure. Our algorithm only takes $\widetilde{O}(nk + kd^2 + nd)$ time.
• Abstract（参考訳）: サブモジュール関数は、文書要約、センサー配置、画像分割など、多くの実世界の応用がある。 これらすべてのアプリケーションにおいて、キーとなるビルディングブロックは、サブモジュラー関数の最大値を効率的に計算する方法である。 オンライン版とオフライン版の両方について検討する。各イテレーションでデータセットが漸進的に変更されるか変更されないか,ユーザがクエリを発行することで,データの特定のサブセット上で関数を最大化することができる。 ユーザは悪意があり、以前のクエリ結果に基づいてクエリを発行することで、オンラインアルゴリズムの競合比を損なうことができる。 現在、オンライン部分モジュラー関数の最大化のための最もよく知られているアルゴリズムは、実行時間$O(n k d^2)$で、$n$は要素の総数、$d$は特徴次元、$k$は選択すべき要素の数である。 本稿では,新しい探索木データ構造に基づく新しい手法を提案する。 我々のアルゴリズムは$\widetilde{O}(nk + kd^2 + nd)$時間しかかからない。

関連論文リスト

• Linear Submodular Maximization with Bandit Feedback [7.926559636438099]
  準モジュラー目的関数 $f:2UtomathbbR_geq 0$, ここでは $f=sum_i=1dw_iF_i$ に対する近似アルゴリズムの開発を検討する。 F_i$ 関数へのオラクルアクセスが期待できるが、係数 $w_i$ は未知であり、$f$ はノイズの多いクエリによってのみアクセス可能である。 我々のアルゴリズムは、$fの線形構造を利用していないアルゴリズムと比較して、サンプル効率の点で大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2024-07-02T18:40:52Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。 本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
  論文  参考訳（メタデータ） (2023-08-16T19:32:29Z)
• Fully Dynamic Submodular Maximization over Matroids [27.83996903538686]
  マトロイド制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習における複数の応用において古典的なアルゴリズム上の問題である。 我々は、この古典的な問題を完全に動的に研究し、そこでは、要素をリアルタイムで挿入および削除できる。 我々の主な結果は、$tildeO(k2)$の償却更新時間(加算と削除数)で効率的なデータ構造を維持し、$k$がマトロイドのランクである4ドルの近似解を生成するランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-31T14:55:47Z)
• 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)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Very Fast Streaming Submodular Function Maximization [6.734843312980923]
  サブモジュール関数アルゴリズムは、より高い計算とメモリ要求を犠牲にして最悪のケース近似を提供する。 我々は,最悪のケースを無視するが,高い確率で優れた解を提供する3-Sievesと呼ばれる新しい部分モジュラ関数アルゴリズムを提案する。 我々のアルゴリズムは現在の最先端のアルゴリズムよりも優れており、同時にリソースが少ないことも示している。
  論文  参考訳（メタデータ） (2020-10-20T06:36:14Z)
• The Sparse Vector Technique, Revisited [67.57692396665915]
  我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。 この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。 一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-02T10:50:52Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。 線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。 我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
  論文  参考訳（メタデータ） (2020-09-10T16:35:54Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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