論文の概要: Deletion Robust Submodular Maximization over Matroids

• arxiv url: http://arxiv.org/abs/2201.13128v1
• Date: Mon, 31 Jan 2022 11:15:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-01 22:35:46.025830
• Title: Deletion Robust Submodular Maximization over Matroids
• Title（参考訳）: マトロイドによる脱落ロバスト部分モジュラー最大化
• Authors: Paul D\"utting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
• Abstract要約: 古典的マトロイド制約の下で, 問題の削除頑健バージョンについて検討する。 定数係数近似アルゴリズムを提案し、その空間複雑性はマトロイドのランク$k$に依存する。 実世界のデータセット上でのアルゴリズムの有効性を示す詳細な実験結果を用いて理論的結果を補完する。
• 参考スコア（独自算出の注目度）: 27.83996903538686
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximizing a monotone submodular function is a fundamental task in machine learning. 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 $(3.582+O(\varepsilon))$-approximation algorithm with summary size $O(k + \frac{d \log k}{\varepsilon^2})$. In the streaming setting we provide a $(5.582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d \log k}{\varepsilon^2})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.
• Abstract（参考訳）: 単調部分モジュラ関数の最大化は機械学習の基本的な課題である。 本稿では,古典的なマトロイド制約の下で,問題の削除ロバストなバージョンについて検討する。 ここでの目標は、敵がいくつかの要素を削除した後でも、高い値独立セットを含むデータセットの小さなサイズのサマリを抽出することである。 我々は,空間複雑性がマトロイドのランク $k$ と削除された要素の $d$ に依存する定数近似アルゴリズムを提案する。 集中的な設定では、要約サイズ$O(k + \frac{d \log k}{\varepsilon^2})$の$(3.582+O(\varepsilon))$-近似アルゴリズムを示す。 ストリーミング設定では、サマリサイズとメモリが$O(k + \frac{d \log k}{\varepsilon^2})$で$(5.582+O(\varepsilon))$-approximationアルゴリズムを提供します。 我々は,実世界のデータセットに対するアルゴリズムの有効性を示す詳細な実験分析を行い,理論結果を補完する。

関連論文リスト

• 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。 本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。 マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-06-01T17:54:15Z)
• Fully Dynamic Submodular Maximization over Matroids [27.83996903538686]
  マトロイド制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習における複数の応用において古典的なアルゴリズム上の問題である。 我々は、この古典的な問題を完全に動的に研究し、そこでは、要素をリアルタイムで挿入および削除できる。 我々の主な結果は、$tildeO(k2)$の償却更新時間(加算と削除数)で効率的なデータ構造を維持し、$k$がマトロイドのランクである4ドルの近似解を生成するランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-31T14:55:47Z)
• Deletion Robust Non-Monotone Submodular Maximization over Matroids [27.83996903538686]
  古典的マトロイド制約の下で, 問題の削除頑健バージョンについて検討する。 定数係数近似アルゴリズムを提案し、その空間複雑性はマトロイドのランク$k$に依存する。 ストリーミング設定では、サマリサイズとメモリを備えた99.435 + O(varepsilon)$-approximationアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-08-16T07:51:58Z)
• 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)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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