論文の概要: Differentially Private Submodular Maximization with a Knapsack Constraint
- arxiv url: http://arxiv.org/abs/2606.14951v1
- Date: Fri, 12 Jun 2026 20:49:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-16 16:21:32.47331
- Title: Differentially Private Submodular Maximization with a Knapsack Constraint
- Title（参考訳）: Knapsack Constraint による分極的部分モジュラー最大化
- Authors: Ron Zadicario, Tova Milo,
- Abstract要約: クナップサック制約(SMK)の対象となる部分モジュラー最適化は、離散的な個々の分野における根本的な問題である。
本研究では,モノトーンと非モノトーンの両方の目的関数を考慮し,差分プライバシー下でのSMK問題を考察する。
単調な目的に対して、最適な$(1-1/e)$-approximation比を達成する微分プライベートアルゴリズムを提案する。
また、同じ設定に対してより効率的なアルゴリズムを提案し、1/2$-approximation を達成する。
- 参考スコア（独自算出の注目度）: 6.345340156849189
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Submodular maximization subject to a knapsack constraint (SMK) is a fundamental problem in discrete optimization, with wide-ranging applications in machine learning and related fields. As these applications increasingly involve sensitive individual data, there is a growing need for high-utility algorithms that provide formal privacy guarantees. In this work, we study the SMK problem under differential privacy, considering both monotone and non-monotone objective functions. For monotone objectives, we propose a differentially private algorithm that achieves the optimal $(1-1/e)$-approximation ratio while significantly improving both additive error and query complexity over prior work. We also present a more efficient algorithm for the same setting, achieving a $1/2$-approximation. For non-monotone objectives, we introduce, to our knowledge, the first differentially private algorithm with provable guarantees, achieving a $1/4$-approximation in expectation and an additive error comparable to the best known for monotone objective functions.
- Abstract（参考訳）: クナップサック制約(SMK)の対象とする部分モジュラ最大化は離散最適化の基本的な問題であり、機械学習や関連する分野に広く応用されている。
これらのアプリケーションは、機密性の高い個人データにますます関与しているため、正式なプライバシー保証を提供する高ユーティリティなアルゴリズムの必要性が高まっている。
本研究では,モノトーンと非モノトーンの両方の目的関数を考慮し,差分プライバシー下でのSMK問題を考察する。
単調な目的に対して、1-1/e)$-approximation比を最適に達成し、前処理よりも加算誤差とクエリの複雑さを著しく改善する微分プライベートアルゴリズムを提案する。
また、同じ設定に対してより効率的なアルゴリズムを提案し、1/2$-approximation を達成する。
非単調な目的に対して、我々は、証明可能な保証を持つ最初の微分プライベートアルゴリズムを導入し、期待値の1/4$近似と、単調な目的関数の最もよく知られた値に匹敵する加算誤差を達成した。
関連論文リスト
- Multi-Objective Submodular Maximization with Differential Privacy [14.693713179350505]
差分プライバシー(DP)下での濃度制約を考慮した多目的サブモジュラー(MOSM)について検討する。
2つの新しいアルゴリズムを提案する: 1つは古典的欲求アルゴリズムを拡張し、もう1つはトランケーション手法を採用する。
論文 参考訳（メタデータ） (2026-06-04T02:18:41Z) - Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates [23.143960802555714]
両レベル最適化について検討し、一方の最適化問題を別の内部にネストする。
個人のプライバシーに関する懸念から、我々は新しい二段階アルゴリズムを開発した。
我々の境界は内部の問題の焦点に依存しない。
論文 参考訳（メタデータ） (2025-06-15T23:21:36Z) - 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) - Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳（メタデータ） (2024-11-27T00:48:48Z) - Dynamic Privacy Allocation for Locally Differentially Private Federated
Learning with Composite Objectives [10.528569272279999]
本稿では,強い凸性を持つが非滑らかな問題に対する差分プライベートなフェデレーション学習アルゴリズムを提案する。
提案アルゴリズムは、共有情報に人工ノイズを加えてプライバシーを確保するとともに、時間変化のノイズ分散を動的に割り当て、最適化誤差の上限を最小化する。
解析結果から,提案手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2023-08-02T13:30:33Z) - Private Networked Federated Learning for Nonsmooth Objectives [7.278228169713637]
本稿では,非平滑な目的関数を解くためのネットワーク型フェデレーション学習アルゴリズムを提案する。
参加者の秘密性を保証するため、ゼロ集中型微分プライバシー概念(zCDP)を用いる。
プライバシ保証とアルゴリズムの正確な解への収束の完全な理論的証明を提供する。
論文 参考訳（メタデータ） (2023-06-24T16:13:28Z) - Differentially Private Domain Adaptation with Theoretical Guarantees [46.37771025567305]
多くのアプリケーションでは、ラベル付きデータの処分におけるラベル付きデータはプライバシー上の制約を受けており、比較的制限されている。
これは、パブリックソースからプライベートターゲットドメインへのドメイン適応を監督する現代の問題である。
我々は、理論的な学習保証の恩恵を受けるために、一般の学習者を利用する。
論文 参考訳（メタデータ） (2023-06-15T04:03:06Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。