論文の概要: Deletion Robust Non-Monotone Submodular Maximization over Matroids
- arxiv url: http://arxiv.org/abs/2208.07582v1
- Date: Tue, 16 Aug 2022 07:51:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-17 12:19:50.496820
- Title: Deletion Robust Non-Monotone Submodular Maximization over Matroids
- Title（参考訳）: マトロイド上の欠失ロバスト非モノトンサブモジュラー最大化
- Authors: Paul D\"utting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard,
Morteza Zadimoghaddam
- Abstract要約: 古典的マトロイド制約の下で, 問題の削除頑健バージョンについて検討する。
定数係数近似アルゴリズムを提案し、その空間複雑性はマトロイドのランク$k$に依存する。
ストリーミング設定では、サマリサイズとメモリを備えた99.435 + O(varepsilon)$-approximationアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 27.83996903538686
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Maximizing a submodular function is a fundamental task in machine learning
and in this paper we study the deletion robust version of the problem under the
classic matroids constraint. Here the goal is to extract a small size summary
of the dataset that contains a high value independent set even after an
adversary deleted some elements. We present constant-factor approximation
algorithms, whose space complexity depends on the rank $k$ of the matroid and
the number $d$ of deleted elements. In the centralized setting we present a
$(4.597+O(\varepsilon))$-approximation algorithm with summary size $O(
\frac{k+d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ that is improved to a
$(3.582+O(\varepsilon))$-approximation with $O(k + \frac{d}{\varepsilon^2}\log
\frac{k}{\varepsilon})$ summary size when the objective is monotone. In the
streaming setting we provide a $(9.435 + O(\varepsilon))$-approximation
algorithm with summary size and memory $O(k + \frac{d}{\varepsilon^2}\log
\frac{k}{\varepsilon})$; the approximation factor is then improved to
$(5.582+O(\varepsilon))$ in the monotone case.
- Abstract（参考訳）: サブモジュラー関数の最大化は機械学習の基本的な課題であり、本論文では古典的なマトロイド制約の下で問題の削除ロバストなバージョンについて研究する。
ここでの目標は、敵がいくつかの要素を削除した後でも、高い値独立セットを含むデータセットの小さなサイズのサマリを抽出することである。
我々は,空間複雑性がマトロイドのランク $k$ と削除された要素の $d$ に依存する定数近似アルゴリズムを提案する。
中央集権的な設定では、$(4.597+o(\varepsilon))$近似アルゴリズムを示し、$o( \frac{k+d}{\varepsilon^2}\log \frac{k}{\varepsilon})$を$(3.582+o(\varepsilon))$近似で$o(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ summary sizeに改良する。
ストリーミング設定では、$(9.435 + o(\varepsilon)$-approximation algorithm with summary size and memory $o(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$; 近似係数は単調の場合$(5.582+o(\varepsilon))$に改善される。
関連論文リスト
- 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Deletion Robust Submodular Maximization over Matroids [27.83996903538686]
古典的マトロイド制約の下で, 問題の削除頑健バージョンについて検討する。
定数係数近似アルゴリズムを提案し、その空間複雑性はマトロイドのランク$k$に依存する。
実世界のデータセット上でのアルゴリズムの有効性を示す詳細な実験結果を用いて理論的結果を補完する。
論文 参考訳（メタデータ） (2022-01-31T11:15:56Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。