論文の概要: Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2606.07443v1
• Date: Fri, 05 Jun 2026 16:41:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.853295
• Title: Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy
• Title（参考訳）: Sort, Partition, Randomize: 局所的差分プライバシー下での最適二項仮説テスト
• Authors: Elena Ghazi, Jawad Nasser, Flavio Calmon, Ibrahim Issa,
• Abstract要約: 本稿では,二元仮説テストのための局所微分プライベートなメカニズムとして,$varepsilon$-locally differentially private mechanism の最適設計について検討する。 われわれの結果は、プライバシー体制を超えて、完全なプライバシー範囲の正確な最適化を効率的に計算し、特徴づけることを可能にする。
• 参考スコア（独自算出の注目度）: 1.8549313085249317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study optimal design of $\varepsilon$-locally differentially private mechanisms for binary hypothesis testing. Each observation is drawn from one of two known distributions $P_0,P_1$ on a finite alphabet of size $k$, privatized by a mechanism $Q$, and then used to infer which distribution generated the data. We measure testing utility using an $f$-divergence, including total variation, KL, and hockey-stick divergences, between the two induced output distributions. Previous work established structural properties of optimal mechanisms, but only yielded exponential-time algorithms. We prove a sharp structure: for every $\varepsilon$ and every $f$-divergence objective, after sorting the alphabet by likelihood ratio, there exists an optimal mechanism that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label. We call this class Sort-Partition-Randomize (SPR). This characterization yields an exact dynamic program that computes an optimal mechanism in $O(k^3)$ time, and more generally in $O(\ell k^2)$ time with an $\ell$-output budget. Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond asymptotic privacy regimes.
• Abstract（参考訳）: 本稿では,二元仮説テストのための局所微分プライベートなメカニズムを$\varepsilon$で最適に設計する。 各観測は、2つの既知の分布のうちの1つから$P_0,P_1$を$k$の有限アルファベットで描画し、メカニズム$Q$で民営化し、どの分布がデータを生成するかを推測する。 本研究では,2つの出力分布間の全変動,KL,ホッケースティックの発散を含む$f$-divergenceを用いたテストユーティリティの測定を行った。 以前の研究は最適機構の構造的特性を確立したが、指数時間アルゴリズムしか得られなかった。 すべての$\varepsilonとすべての$f$-divergenceの目的に対して、アルファベットを確率比でソートした後、ソートされたアルファベットを連続したブロックに分割し、ブロックラベルにランダムに応答する最適なメカニズムが存在する。 私たちはこのクラスをSort-Partition-Randomize (SPR)と呼びます。 この特徴づけは、$O(k^3)$時間で最適なメカニズムを計算し、より一般的に$O(\ell k^2)$時間で$\ell$-output予算で計算する正確な動的プログラムを生成する。 我々の結果は、漸近的なプライバシー体制を超えて、完全なプライバシー範囲の正確な最適化を効率的に計算し、特徴づけることを可能にする。

関連論文リスト

• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  局所的な差分プライバシーを満足するアルゴリズムを記述し、個人に対して$tildeO(k3/2)$非適応クエリを実行する。 また、Scheff'eグラフをダブする新しいオブジェクトを導入し、$Q$の分散間の差の構造をキャプチャする。
  論文  参考訳（メタデータ） (2025-09-19T17:41:15Z)
• Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning [2.2083091880368855]
  差分的にプライベートな$k$選択問題について検討し、$d$アイテムから最も高いスコアを持つ$k$アイテムの列を特定することを目的とした。 Gillenwaterらによる最近の研究(ICML '22)は、$d,Theta(k)$ possible length-$k$ sequencesの膨大なコレクションから直接サンプリングアプローチを採用している。 時間と空間の複雑さを持つアルゴリズムを改良し、$O(d + k2 / epsilon cdot ln d)$で、$epsilon$はプライバシーを表す。
  論文  参考訳（メタデータ） (2024-11-14T16:06:13Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Efficiently Computing Similarities to Private Datasets [19.99000806126529]
  微分プライベートモデルトレーニングの多くの方法は、クエリポイント(公開データや合成データなど)とプライベートデータとの類似性を計算することに依存している。 類似関数$f$と大きな高次元プライベートデータセット$XサブセットmathbbRd$を与えられた場合、任意のクエリ$y$に対して、X f(x,y)$のsum_xを近似した差分プライベート(DP)データ構造を出力する。
  論文  参考訳（メタデータ） (2024-03-13T19:19:19Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning [7.61316504036937]
  差分プライバシーは、プライバシに敏感なデータに対する機械学習(ML)の最も一般的な方法である。 ビッグデータ分析では、ランダム化されたスケッチ/アグリゲーションアルゴリズムを使用して、高次元データの処理を可能にすることが多い。
  論文  参考訳（メタデータ） (2023-09-03T19:07:31Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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