論文の概要: Unbounded Differentially Private Quantile and Maximum Estimation
- arxiv url: http://arxiv.org/abs/2305.01177v1
- Date: Tue, 2 May 2023 03:23:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 15:34:22.273244
- Title: Unbounded Differentially Private Quantile and Maximum Estimation
- Title（参考訳）: 非有界差分量子と最大推定
- Authors: David Durfee
- Abstract要約: 単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。
我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
- 参考スコア（独自算出の注目度）: 5.71097144710995
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we consider the problem of differentially private computation of
quantiles for the data, especially the highest quantiles such as maximum, but
with an unbounded range for the dataset. We show that this can be done
efficiently through a simple invocation of $\texttt{AboveThreshold}$, a
subroutine that is iteratively called in the fundamental Sparse Vector
Technique, even when there is no upper bound on the data. In particular, we
show that this procedure can give more accurate and robust estimates on the
highest quantiles with applications towards clipping that is essential for
differentially private sum and mean estimation. In addition, we show how two
invocations can handle the fully unbounded data setting. Within our study, we
show that an improved analysis of $\texttt{AboveThreshold}$ can improve the
privacy guarantees for the widely used Sparse Vector Technique that is of
independent interest. We give a more general characterization of privacy loss
for $\texttt{AboveThreshold}$ which we immediately apply to our method for
improved privacy guarantees. Our algorithm only requires one $O(n)$ pass
through the data, which can be unsorted, and each subsequent query takes $O(1)$
time. We empirically compare our unbounded algorithm with the state-of-the-art
algorithms in the bounded setting. For inner quantiles, we find that our method
often performs better on non-synthetic datasets. For the maximal quantiles,
which we apply to differentially private sum computation, we find that our
method performs significantly better.
- Abstract（参考訳）: 本研究では,データに対する量子化の差分計算の問題,特に最大値などの最も高い量子化を,データセットに対する非有界範囲で検討する。
これは、データに上限がない場合でも、基本スパースベクトル技法で反復的に呼び出されるサブルーチンである$\textt{AboveThreshold}$を単純な呼び出しで効率的に行うことができることを示す。
特に, この手法により, 最大量子化量に対してより正確かつ堅牢な推定が可能であり, 差分的な和と平均推定に必須なクリッピングへの応用が期待できることを示す。
さらに,2つの呼び出しが完全に束縛されていないデータ設定を処理可能であることを示す。
本研究により,$\texttt{abovethreshold}$ の分析精度が向上し,独立性のある分散ベクトル手法に対するプライバシーの保証が向上することを示した。
我々は、プライバシーの保証を改善する方法に直ちに適用される$\texttt{AboveThreshold}$に対して、より一般的なプライバシー損失の特徴を与える。
我々のアルゴリズムでは、データに1ドルO(n)$のパスしか必要とせず、ソートできないため、各クエリは1ドルO(1)$の時間を要する。
非有界なアルゴリズムと最先端のアルゴリズムを有界な設定で実験的に比較する。
内部量子化では、本手法は非合成データセットでよく機能する。
微分プライベート和計算に応用した最大量子化に対して,本手法は性能が著しく向上することがわかった。
関連論文リスト
- Fast John Ellipsoid Computation with Differential Privacy Optimization [34.437362489150246]
高速なジョン楕円体計算のための微分プライベートアルゴリズムを提案する。
提案手法は, ノイズ摂動とスケッチ処理を統合し, スコアサンプリングを活用し, 効率とプライバシの両立を図る。
論文 参考訳（メタデータ） (2024-08-12T03:47:55Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。
提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
論文 参考訳（メタデータ） (2023-03-01T18:49:10Z) - On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。
アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
論文 参考訳（メタデータ） (2023-02-11T14:45:31Z) - Smooth Anonymity for Sparse Graphs [69.1048938123063]
しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。
本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-07-13T17:09:25Z) - 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) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Differentially Private Quantiles [12.917299605014419]
我々は,$n$のデータポイントから$m$quantilesを同時に推定する指数的メカニズムの例を提案する。
本手法は, 実データと合成データの両方において, 技術の現状を著しく上回っている。
論文 参考訳（メタデータ） (2021-02-16T16:02:59Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。