論文の概要: Multi-Objective Submodular Maximization with Differential Privacy
- arxiv url: http://arxiv.org/abs/2606.05596v1
- Date: Thu, 04 Jun 2026 02:18:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-05 22:39:44.488174
- Title: Multi-Objective Submodular Maximization with Differential Privacy
- Title（参考訳）: 微分プライバシーを用いた多目的部分モジュラ最大化
- Authors: Ting Hou, Yanhao Wang, Yiping Wang, Cen Chen, Minghao Zhao, Fan Dang,
- Abstract要約: 差分プライバシー(DP)下での濃度制約を考慮した多目的サブモジュラー(MOSM)について検討する。
2つの新しいアルゴリズムを提案する: 1つは古典的欲求アルゴリズムを拡張し、もう1つはトランケーション手法を採用する。
- 参考スコア（独自算出の注目度）: 14.693713179350505
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In this paper, we study multi-objective submodular maximization (MOSM) subject to a cardinality constraint under differential privacy (DP). Specifically, we aim to select a set of at most $k \in \mathbb{Z}_{+}$ elements to maximize the minimum of $d > 1$ monotone submodular functions while satisfying $\varepsilon$-DP. Although extensive studies have been conducted on both differentially private single-objective submodular maximization on sensitive data and non-private MOSM, to the best of our knowledge, there has not yet been any prior work on MOSM with DP. We propose two novel algorithms: the first extends the classic greedy algorithm and the second employs a truncation technique, both of which are integrated with DP mechanisms for privacy protection and achieve approximation guarantees for MOSM. Finally, we conduct numerical experiments on two submodular maximization applications, namely maximum coverage and facility location, in multi-objective settings to validate the efficacy and efficiency of our proposed algorithms.
- Abstract（参考訳）: 本稿では,差分プライバシ(DP)下での濃度制約を考慮したMOSM(multi-jective submodular maximization)について検討する。
具体的には、少なくとも$k \in \mathbb{Z}_{+}$要素の集合を選択して、$\varepsilon$-DPを満足しながら、$d > 1$モノトン部分モジュラ函数を最大化する。
機密データと非私的MOSMの差分的単目的サブモジュラー最大化に関する広範な研究が行われてきたが、我々の知る限りでは、DPを用いたMOSMに関する先行研究は行われていない。
2つの新しいアルゴリズムを提案する: 1つは古典的欲求アルゴリズムを拡張し、2つ目はトランケーション手法を採用し、どちらもプライバシー保護のためのDPメカニズムと統合され、MOSMの近似保証を実現する。
最後に,提案アルゴリズムの有効性と有効性を検証するため,多目的設定における2つの部分モジュラー最大化アプリケーション,すなわち最大カバレッジと施設位置に関する数値実験を行った。
関連論文リスト
- Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。
また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-23T02:30:01Z) - Online Two-Stage Submodular Maximization [15.29193118676418]
オンライン2段階のサブモジュール最適化(O2SSM)問題を導入し、サブモジュールの目的をオンライン形式で明らかにする。
実データセットを用いた実験により,オンラインアルゴリズムの性能を実証的に検証した。
論文 参考訳（メタデータ） (2025-10-22T11:18:54Z) - LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.35609820607923]
大規模言語モデル(LLM)は、アルゴリズム設計を支援する新しい機会を提供する。
LLM4CMOは,2つの人口構成をもつ2段階のフレームワークをベースとした新しいCMOEAである。
LLMは複雑な進化最適化アルゴリズムの開発において効率的な共同設計者として機能する。
論文 参考訳（メタデータ） (2025-08-16T02:00:57Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Multi-objective Evolutionary Algorithms are Generally Good: Maximizing
Monotone Submodular Functions over Sequences [44.11102526976392]
本稿では,シーケンス上のモノトーン部分モジュラ関数を最大化する問題クラスについて検討する。
EAは、部分モジュラ最適化の問題を解くための優れた近似保証を達成できる。
例えば、タスクの達成、情報ゲインの最大化、探索と追跡、レコメンデーションシステムなど、様々なアプリケーションに関する実証研究は、GSEMOの優れた性能を示している。
論文 参考訳（メタデータ） (2021-04-20T10:36:10Z) - Planning with Submodular Objective Functions [118.0376288522372]
準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。
本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
論文 参考訳（メタデータ） (2020-10-22T16:55:12Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳（メタデータ） (2020-06-24T04:37:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。