論文の概要: 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桁早く実行しながら、この低いエラーを発生させる。
関連論文リスト
- Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances [15.990720051907864]
Subset-of-Signalsモデルはヘテロスケダティック平均推定のベンチマークとして機能する。
我々のアルゴリズムは、このオープンな問題を対数的要因に分解する。
たとえ$d=2$であっても、我々の手法は各サンプルのばらつきを知るのに匹敵するレートを可能にします。
論文 参考訳(メタデータ) (2023-12-05T01:13:10Z) - 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) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳(メタデータ) (2020-08-12T15:40:21Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳(メタデータ) (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。