論文の概要: Dynamic Algorithms for Matroid Submodular Maximization
- arxiv url: http://arxiv.org/abs/2306.00959v2
- Date: Tue, 26 Dec 2023 12:30:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-28 01:59:12.788879
- Title: Dynamic Algorithms for Matroid Submodular Maximization
- Title（参考訳）: マトロイドサブモジュラー最大化のための動的アルゴリズム
- Authors: Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi
Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
- Abstract要約: マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。
本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。
マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
- 参考スコア（独自算出の注目度）: 11.354502646593607
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Submodular maximization under matroid and cardinality constraints are
classical problems with a wide range of applications in machine learning,
auction theory, and combinatorial optimization. In this paper, we consider
these problems in the dynamic setting, where (1) we have oracle access to a
monotone submodular function $f: 2^{V} \rightarrow \mathbb{R}^+$ and (2) we are
given a sequence $\mathcal{S}$ of insertions and deletions of elements of an
underlying ground set $V$.
We develop the first fully dynamic $(4+\epsilon)$-approximation algorithm for
the submodular maximization problem under the matroid constraint using an
expected worst-case $O(k\log(k)\log^3{(k/\epsilon)})$ query complexity where $0
< \epsilon \le 1$. This resolves an open problem of Chen and Peng (STOC'22) and
Lattanzi et al. (NeurIPS'20).
As a byproduct, for the submodular maximization under the cardinality
constraint $k$, we propose a parameterized (by the cardinality constraint $k$)
dynamic algorithm that maintains a $(2+\epsilon)$-approximate solution of the
sequence $\mathcal{S}$ at any time $t$ using an expected worst-case query
complexity $O(k\epsilon^{-1}\log^2(k))$. This is the first dynamic algorithm
for the problem that has a query complexity independent of the size of ground
set $V$.
- Abstract（参考訳）: マトロイドおよび濃度制約の下での部分モジュラー最大化は、機械学習、オークション理論、組合せ最適化において幅広い応用を持つ古典的な問題である。
本稿では,(1) oracle が単調部分モジュラ関数 $f: 2^{v} \rightarrow \mathbb{r}^+$ にアクセスし,(2) 基底となる基底集合 $v$ の要素の挿入と削除の順序 $\mathcal{s}$ が与えられる動的設定において,これらの問題を考察する。
行列制約の下でのサブモジュラー最大化問題に対する最初のフルダイナミックな$(4+\epsilon)$-approximationアルゴリズムを、期待最悪の$O(k\log(k)\log^3{(k/\epsilon)})$クエリ複雑性を用いて開発する。
これはChen and Peng (STOC'22) と Lattanzi et al. (NeurIPS'20) の開問題を解く。
副生成物として、濃度制約の下の部分モジュラ最大化のために、(濃度制約の$k$)動的アルゴリズムをパラメータ化し、$(2+\epsilon)$-approximate solution of the sequence $\mathcal{S}$ at any time $t$ using a expected worst-case complexity $O(k\epsilon^{-1}\log^2(k))$とする。
これは、基底集合の大きさに依存しないクエリ複雑性を持つ問題に対する最初の動的アルゴリズムである。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - A Dynamic Algorithm for Weighted Submodular Cover Problem [11.354502646593607]
基底集合の要素を挿入・削除する動的設定における部分モジュラー被覆問題について検討する。
本稿では,更新毎に多対数クエリの複雑さを用いてO(epsilon-1)$-bicriteria近似を求めるランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-13T21:00:41Z) - Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。
本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文 参考訳（メタデータ） (2024-05-20T02:24:58Z) - Dynamic Non-monotone Submodular Maximization [11.354502646593607]
濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。
我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
論文 参考訳（メタデータ） (2023-11-07T03:20:02Z) - 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) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。
これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
論文 参考訳（メタデータ） (2021-11-05T00:04:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。