Fugu-MT 論文翻訳(概要): Optimal partition selection with Rényi differential privacy

論文の概要: Optimal partition selection with Rényi differential privacy

arxiv url: http://arxiv.org/abs/2603.09167v2
Date: Wed, 11 Mar 2026 01:42:51 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-12 14:12:44.261872
Title: Optimal partition selection with Rényi differential privacy
Title（参考訳）: Rényi差分プライバシーを用いた最適分割選択
Authors: Charlie Harrison, Pasin Manurangsi,
Abstract要約: 最適アルゴリズムの拡張を$L2$の有界分割選択のために提案する。我々のプリミティブは、アートパーティション選択アルゴリズムの状態に簡単にプラグイン可能であることを示す。
参考スコア（独自算出の注目度）: 24.85689199092059
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A common problem in private data analysis is the partition selection problem, where each user holds a set of partitions (e.g. keys in a GROUP BY operation) from a possibly unbounded set. The challenge here is in maximizing the set of released partitions while respecting a differential privacy constraint. Previous work [Desfontaines et al., PoPETS 2022] presented an optimal $(\varepsilon, δ)$-DP algorithm when each user submits only a single partition. We generalize this approach to find the optimal algorithm under $δ$-approximate $(α, \varepsilon)$-Rényi differential privacy (RDP), which allows much tighter analysis under composition. Motivated by the non-existence of a general optimality result in the case where users submit multiple partitions each, we present an extension of our optimal algorithm tuned for $L^2$ bounded weighted partition selection which can be used as a drop-in improvement over the Gaussian mechanism any time the partition frequency is not also needed. We show that our primitive can be easily plugged into state of the art partition selection algorithms (PolicyGaussian from [Gopi et al., ICML 2020] and MAD2R from [Chen et al., ICML 2025]), improving performance both for parallel and sequential adaptive algorithms. Finally, we show that there is an inherent cost to algorithms which do support releasing the frequency as well as the partitions. Specifically, we formulate a basic notion of optimal approximate RDP algorithm for partition selection using additive noise, and show that there is a numerical separation between additive and non-additive noise mechanisms for this problem.
Abstract（参考訳）: プライベートデータ分析における一般的な問題はパーティション選択の問題であり、各ユーザが非有界なセットからパーティションのセット(例えばGROUP BY操作のキー)を保持する。ここでの課題は、差分プライバシー制約を尊重しながら、リリースされたパーティションの集合を最大化することです。以前の作業 [Desfontaines et al , PoPETS 2022] では,各ユーザがひとつのパーティションのみを提出した場合に,最適な $(\varepsilon, δ)$-DP アルゴリズムが提示されていた。このアプローチを一般化して、$δ$-approximate $(α, \varepsilon)$-Rényi差分プライバシー(RDP)の下で最適なアルゴリズムを求める。ユーザが複数のパーティションを送信した場合の一般最適性の非存在感に動機付けられて,分割周波数が不要な場合にも,ガウス機構に対するドロップイン改善として使用できる,$L^2$の有界重み付きパーティション選択のために調整された最適アルゴリズムの拡張を示す。我々のプリミティブは、最先端のパーティション選択アルゴリズム([Gopi et al , ICML 2020]のPolicyGaussianと[Chen et al , ICML 2025]のMAD2Rに簡単にプラグインでき、並列および逐次適応アルゴリズムの性能を向上させることができる。最後に、分割だけでなく周波数の解放もサポートするアルゴリズムには本質的にコストがかかることを示す。具体的には、加算雑音を用いた分割選択のための最適近似RDPアルゴリズムの基本概念を定式化し、この問題に対して加算雑音と非付加雑音の数値的分離が存在することを示す。

関連論文リスト

Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文参考訳（メタデータ） (2024-11-27T00:48:48Z)
Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文参考訳（メタデータ） (2024-05-28T19:02:30Z)
Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文参考訳（メタデータ） (2023-09-27T17:09:36Z)
A 2-opt Algorithm for Locally Optimal Set Partition Optimization [0.0]
我々は,最大$O(N2)$時間と$O(N)$空間で局所最適解を生成するアルゴリズムを開発した。アルゴリズムは任意の入力精度を処理でき、正や整数の入力を必要としない。
論文参考訳（メタデータ） (2023-03-14T20:25:56Z)
Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文参考訳（メタデータ） (2022-05-05T06:43:46Z)
Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
論文参考訳（メタデータ） (2021-09-10T11:53:34Z)
No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
論文参考訳（メタデータ） (2021-02-24T18:52:24Z)
SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文参考訳（メタデータ） (2020-06-12T05:00:44Z)
Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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