論文の概要: On the Complexity of Dynamic Submodular Maximization

• arxiv url: http://arxiv.org/abs/2111.03198v1
• Date: Fri, 5 Nov 2021 00:04:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-09 00:50:27.096913
• Title: On the Complexity of Dynamic Submodular Maximization
• Title（参考訳）: 動的部分モジュラー最大化の複雑性について
• Authors: Xi Chen, Binghui Peng
• Abstract要約: 濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。 これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
• 参考スコア（独自算出の注目度）: 15.406670088500087
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of $n$ insertions and deletions. We show that any algorithm that maintains a $(0.5+\epsilon)$-approximate solution under a cardinality constraint, for any constant $\epsilon>0$, must have an amortized query complexity that is $\mathit{polynomial}$ in $n$. Moreover, a linear amortized query complexity is needed in order to maintain a $0.584$-approximate solution. This is in sharp contrast with recent dynamic algorithms of [LMNF+20, Mon20] that achieve $(0.5-\epsilon)$-approximation with a $\mathsf{poly}\log(n)$ amortized query complexity. On the positive side, when the stream is insertion-only, we present efficient algorithms for the problem under a cardinality constraint and under a matroid constraint with approximation guarantee $1-1/e-\epsilon$ and amortized query complexities $\smash{O(\log (k/\epsilon)/\epsilon^2)}$ and $\smash{k^{\tilde{O}(1/\epsilon^2)}\log n}$, respectively, where $k$ denotes the cardinality parameter or the rank of the matroid.
• Abstract（参考訳）: 我々は,n$挿入と削除のストリーム上で単調部分モジュラ関数を最大化する問題に対する動的アルゴリズムについて検討する。 濃度制約の下で$(0.5+\epsilon)$-approximate の解を維持するアルゴリズムは、定数 $\epsilon>0$ に対して$\mathit{polynomial}$ in $n$ の償却クエリ複雑性を持つ必要がある。 さらに、0.584$-approximateソリューションを維持するには、線形アモータイズされたクエリの複雑さが必要である。 これは[lmnf+20, mon20] の最近の動的アルゴリズムとは対照的で、$(0.5-\epsilon)$近似を$\mathsf{poly}\log(n)$ amortized query complexityで達成している。 正の側では、ストリームが挿入のみである場合、基数制約の下で、近似付きマトロイド制約の下で問題に対する効率的なアルゴリズムを示し、1-1/e-\epsilon$ と amortized query complexities $\smash{o(\log (k/\epsilon)/\epsilon^2)}$ と $\smash{k^{\tilde{o}(1/\epsilon^2)}\log n}$ をそれぞれ示す。

関連論文リスト

• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Fast algorithms for k-submodular maximization subject to a matroid constraint [10.270420338235237]
  マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。 我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-07-26T07:08:03Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。 本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。 マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-06-01T17:54:15Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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