論文の概要: Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints

• arxiv url: http://arxiv.org/abs/2006.15744v1
• Date: Sun, 28 Jun 2020 23:18:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-16 03:07:06.845557
• Title: Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints
• Title（参考訳）: マトロイド制約付き高速かつプライベートなサブモジュラーおよび$k$-サブモジュラー関数の最大化
• Authors: Akbar Rafiey, Yuichi Yoshida
• Abstract要約: 差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 27.070004659301162
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed for this problem. Many machine learning problems, including data summarization and influence maximization, can be naturally modeled as the problem of maximizing monotone submodular functions. However, when such applications involve sensitive data about individuals, their privacy concerns should be addressed. In this paper, we study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We provide $(1-\frac{1}{\mathrm{e}})$-approximation algorithm which improves upon the previous results in terms of approximation guarantee. This is done with an almost cubic number of function evaluations in our algorithm. Moreover, we study $k$-submodularity, a natural generalization of submodularity. We give the first $\frac{1}{2}$-approximation algorithm that preserves differential privacy for maximizing monotone $k$-submodular functions subject to matroid constraints. The approximation ratio is asymptotically tight and is obtained with an almost linear number of function evaluations.
• Abstract（参考訳）: 一定の制約の下で非負の単調な部分モジュラー関数を最大化する問題は、過去10年間、集中的に研究され、この問題に対して幅広い効率的な近似アルゴリズムが開発されてきた。 データ要約や影響最大化を含む多くの機械学習問題は、自然にモノトーンサブモジュラー関数を最大化する問題としてモデル化することができる。 しかし、個人に関する機密データを含む場合、プライバシー上の懸念に対処する必要がある。 本稿では,差分プライバシーの枠組みにおいて,マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 1-\frac{1}{\mathrm{e}})$近似アルゴリズムを提供する。 これは我々のアルゴリズムでほぼ3分の1の関数評価によって行われる。 さらに、サブモジュラリティの自然な一般化である$k$-submodularityを研究する。 単調な$k$-submodular関数をマットロイド制約下で最大化するために差分プライバシーを保存する最初の$\frac{1}{2}$-approximationアルゴリズムを与える。 近似比は漸近的にタイトであり、ほぼ線形な関数評価で得られる。

関連論文リスト

• Dynamic Non-monotone Submodular Maximization [11.354502646593607]
  濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。 我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
  論文  参考訳（メタデータ） (2023-11-07T03:20:02Z)
• Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
  未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。 この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
  論文  参考訳（メタデータ） (2023-03-17T13:32:33Z)
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice [5.543220407902113]
  濃度制約を受ける有界整数格子上の単調部分モジュラ函数を最大化する問題を考える。 特に、DR-部分モジュラ函数の最大化、すなわち減少するリターン特性を示す整数格子上で定義される関数に焦点をあてる。 提案したアルゴリズムを整数格子に適用することは、設定された領域に対する目標問題を減らし、最も高速に設定された部分モジュラーアルゴリズムを適用するなど、他のアルゴリズムよりも高速である。
  論文  参考訳（メタデータ） (2021-11-19T12:07:16Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)
• Differentially Private Decomposable Submodular Maximization [12.835348339847762]
  分解可能部分モジュラ函数の微分プライベート制約問題について検討する。 部分モジュラ函数の和の形を取ると、部分モジュラ函数は分解可能である。 一般マトロイド制約下では単調および非単調の分解可能部分モジュラーの差分プライベートアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-05-29T17:59:46Z)

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

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