論文の概要: Count-mean Sketch as an Optimized Framework for Frequency Estimation with Local Differential Privacy
- arxiv url: http://arxiv.org/abs/2406.03785v1
- Date: Thu, 6 Jun 2024 06:55:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 16:09:36.761248
- Title: Count-mean Sketch as an Optimized Framework for Frequency Estimation with Local Differential Privacy
- Title（参考訳）: 局所微分プライバシーを用いた周波数推定の最適化フレームワークとしてのカウンタ平均スケッチ
- Authors: Mingen Pan,
- Abstract要約: パラメータの異なるプライベートなCount-Mean Sketch(CMS)アルゴリズムを再検討する。
我々は既存のバイアスを取り除くためにCMSの実装を変更します。
ペアワイズ非依存ハッシュがCMSに十分であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: This paper identifies that a group of state-of-the-art locally-differentially-private (LDP) algorithms for frequency estimation are equivalent to the private Count-Mean Sketch (CMS) algorithm with different parameters. Therefore, we revisit the private CMS, correct errors in the original CMS paper regarding expectation and variance, modify the CMS implementation to eliminate existing bias, and explore optimized parameters for CMS to achieve optimality in reducing the worst-case mean squared error (MSE), $l_1$ loss, and $l_2$ loss. Additionally, we prove that pairwise-independent hashing is sufficient for CMS, reducing its communication cost to the logarithm of the cardinality of all possible values (i.e., a dictionary). As a result, the aforementioned optimized CMS is proven theoretically and empirically to be the only algorithm optimized for reducing the worst-case MSE, $l_1$ loss, and $l_2$ loss when dealing with a very large dictionary. Furthermore, we demonstrate that randomness is necessary to ensure the correctness of CMS, and the communication cost of CMS, though low, is unavoidable despite the randomness being public or private.
- Abstract（参考訳）: 本稿では、周波数推定のための最先端の局所微分プライベート(LDP)アルゴリズム群が、パラメータの異なるプライベート・カウンタ・ミーン・スケッチ(CMS)アルゴリズムと等価であることを示す。
そこで我々は、民間CMSを再検討し、予測と分散に関する元のCMS論文の誤りを正し、既存のバイアスを取り除くためにCMSの実装を変更し、最悪の平均二乗誤差(MSE)、$l_1$損失、$l_2$損失を減らす最適化されたCMSパラメータを探索する。
さらに、対非依存ハッシュはCMSにとって十分であり、その通信コストをすべての可能な値(辞書)の濃度の対数に還元する。
その結果、上記の最適化されたCMSは、非常に大きな辞書を扱う際に、最悪のMSE、$l_1$損失、$l_2$損失を減らすために最適化された唯一のアルゴリズムであると理論的、実証的に証明されている。
さらに、CMSの正当性を確保するためにはランダム性が必要であること、CMSの通信コストは低いが、公開や非公開のランダム性にもかかわらず避けられないことを実証する。
関連論文リスト
- Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
既存の平均推定スキームは、通常、$L_infty$幾何に最適化され、ランダムな回転や、$L$幾何に適応するカシンの表現に依存する。
本稿では,スパシフィケーションに固有のランダム性をDPに組み込んだ,スパシフィケーションガウシアン機構の新たなプライバシ会計手法を提案する。
従来の手法とは異なり、我々の会計アルゴリズムは直接$L$幾何で動作し、ガウスの機構に迅速に収束するMSEが得られる。
論文 参考訳（メタデータ） (2024-05-02T03:48:47Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - 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) - On Private Online Convex Optimization: Optimal Algorithms in
$\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。
また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。
提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
論文 参考訳（メタデータ） (2022-06-16T12:09:47Z) - Learning-augmented count-min sketches via Bayesian nonparametrics [2.9005223064604078]
カウントミンスケッチ(カウントミンスケッチ、英: count-min sketch、CMS)は、データストリーム内のトークンの周波数を推定する時間とメモリ効率のよいランダム化データ構造である。
我々はCMS-DPの代替として、より柔軟に導出する。
CMS-PYP(CMS-PYP)は、PYPプリエントを介してストリームのBNPモデリングに依存する。
論文 参考訳（メタデータ） (2021-02-08T16:02:30Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z) - Breaking the Communication-Privacy-Accuracy Trilemma [19.399122892615573]
分散学習における2つの大きな課題は、ローカルサンプルのプライバシを保持し、それらを中央サーバに効率的に伝達することである。
我々は、最適なプライバシーと通信効率を同時に達成する新しい符号化・復号機構を開発する。
論文 参考訳（メタデータ） (2020-07-22T22:43:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。