Fugu-MT 論文翻訳(概要): Fully Dynamic Submodular Maximization over Matroids

論文の概要: Fully Dynamic Submodular Maximization over Matroids

arxiv url: http://arxiv.org/abs/2305.19918v1
Date: Wed, 31 May 2023 14:55:47 GMT
ステータス: 処理完了
システム内更新日: 2023-06-01 15:50:25.602201
Title: Fully Dynamic Submodular Maximization over Matroids
Title（参考訳）: マトロイドのフルダイナミックサブモジュラー最大化
Authors: Paul D\"utting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
Abstract要約: マトロイド制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習における複数の応用において古典的なアルゴリズム上の問題である。我々は、この古典的な問題を完全に動的に研究し、そこでは、要素をリアルタイムで挿入および削除できる。我々の主な結果は、$tildeO(k2)$の償却更新時間(加算と削除数)で効率的なデータ構造を維持し、$k$がマトロイドのランクである4ドルの近似解を生成するランダム化アルゴリズムである。
参考スコア（独自算出の注目度）: 27.83996903538686
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an $\tilde{O}(k^2)$ amortized update time (in the number of additions and deletions) and yields a $4$-approximate solution, where $k$ is the rank of the matroid.
Abstract（参考訳）: マトロイド制約の下で単調な部分モジュラー関数を最大化することは、データマイニングと機械学習に複数の応用がある古典的なアルゴリズム問題である。この古典的な問題を、要素をリアルタイムで挿入・削除できる完全にダイナミックな設定で検討する。我々の主な結果は、$\tilde{O}(k^2)$の償却更新時間(加算数と削除数)で効率的なデータ構造を維持し、$k$がマトロイドのランクである4ドルの近似解を生成するランダム化アルゴリズムである。

関連論文リスト

Dynamic Non-monotone Submodular Maximization [11.354502646593607]
濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
論文参考訳（メタデータ） (2023-11-07T03:20:02Z)
Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
我々は、ユニタリティ制約の研究に現代の機械学習技術を適用した。我々は、そのような解に対する既知の限界を以前の境界を超えるような新しい位相あいまいな解を求める。
論文参考訳（メタデータ） (2023-08-18T10:29:26Z)
Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
論文参考訳（メタデータ） (2023-06-01T17:54:15Z)
Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文参考訳（メタデータ） (2023-02-02T18:52:14Z)
Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T14:37:21Z)
Deletion Robust Submodular Maximization over Matroids [27.83996903538686]
古典的マトロイド制約の下で, 問題の削除頑健バージョンについて検討する。定数係数近似アルゴリズムを提案し、その空間複雑性はマトロイドのランク$k$に依存する。実世界のデータセット上でのアルゴリズムの有効性を示す詳細な実験結果を用いて理論的結果を補完する。
論文参考訳（メタデータ） (2022-01-31T11:15:56Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文参考訳（メタデータ） (2021-06-02T22:03:36Z)
Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文参考訳（メタデータ） (2021-04-13T23:21:01Z)
A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文参考訳（メタデータ） (2021-02-15T07:10:33Z)
Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint [13.357957711519134]
制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
論文参考訳（メタデータ） (2020-07-09T18:15:01Z)
Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文参考訳（メタデータ） (2020-06-28T23:18:58Z)

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