論文の概要: Differentially Private Approximate Quantiles
- arxiv url: http://arxiv.org/abs/2110.05429v1
- Date: Mon, 11 Oct 2021 17:19:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-12 20:49:52.155631
- Title: Differentially Private Approximate Quantiles
- Title（参考訳）: 微分プライベート近似量子
- Authors: Haim Kaplan, Shachar Schnapp, Uri Stemmer
- Abstract要約: 本研究では、微分プライベート(DP)量子化の問題を研究する。
我々は、真の量子化にできるだけ近い$m$の量子化推定を出力し、DPを保存したい。
- 参考スコア（独自算出の注目度）: 27.950292359069216
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we study the problem of differentially private (DP) quantiles,
in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to
output $m$ quantile estimations which are as close as possible to the true
quantiles and preserve DP. We describe a simple recursive DP algorithm, which
we call ApproximateQuantiles (AQ), for this task. We give a worst case upper
bound on its error, and show that its error is much lower than of previous
implementations on several different datasets. Furthermore, it gets this low
error while running time two orders of magnitude faster that the best previous
implementation.
- Abstract（参考訳）: 本研究では,x$ と quantiles $q_1, ..., q_m \in [0,1]$ が与えられた場合,真の量子タイルに可能な限り近い$m$ の量子タイルを出力し,dp を保存する,微分プライベート (dp) 量子タイルの問題を研究する。
本稿では,AQ(ApproximateQuantiles)と呼ばれる単純な再帰DPアルゴリズムについて述べる。
最悪の場合、そのエラーに上限を与え、そのエラーが、いくつかの異なるデータセットの以前の実装よりもはるかに低いことを示す。
さらに、以前の最良の実装よりも2桁早く実行しながら、この低いエラーを発生させる。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Privately Counting Partially Ordered Data [50.98561191019676]
各データポイントが部分順序を満たす$d$ビットからなる場合、差分プライベートカウントを考える。
私たちの主な技術的貢献は問題固有の$K$-normメカニズムで、時間内に$O(d2)$を実行します。
論文 参考訳（メタデータ） (2024-10-09T13:43:35Z) - Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy [36.04370583654189]
クリッピング機構が$O(max_i x_i cdot loglog U /varepsilon)$のインスタンス最適誤差を実現する方法を示す。
また、この手法を高次元和推定問題とスパースベクトルアグリゲーションに拡張する。
論文 参考訳（メタデータ） (2024-03-15T09:04:00Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳（メタデータ） (2023-06-20T06:13:56Z) - Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。
我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
論文 参考訳（メタデータ） (2023-05-02T03:23:07Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Differentially Private Quantiles [12.917299605014419]
我々は,$n$のデータポイントから$m$quantilesを同時に推定する指数的メカニズムの例を提案する。
本手法は, 実データと合成データの両方において, 技術の現状を著しく上回っている。
論文 参考訳（メタデータ） (2021-02-16T16:02:59Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。