論文の概要: Improved Counting under Continual Observation with Pure Differential Privacy
- arxiv url: http://arxiv.org/abs/2408.07021v1
- Date: Tue, 13 Aug 2024 16:36:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 16:55:31.484303
- Title: Improved Counting under Continual Observation with Pure Differential Privacy
- Title（参考訳）: 純微分プライバシーによる連続観測によるカウントの改善
- Authors: Joel Daniel Andersson, Rasmus Pagh, Sahel Torkamani,
- Abstract要約: 我々は、プライバシーと精度のトレードオフを改善するために、$k$-ary number system with $textit negative digits$を使用するバイナリツリー機構の新たな一般化を提案する。
我々のメカニズムは、全ての「最適」$(varepsilon,delta)$-differentially private factorizationメカニズムに対して平均2乗誤差を改善する。
- 参考スコア（独自算出の注目度）: 10.428888893980739
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Counting under continual observation is a well-studied problem in the area of differential privacy. Given a stream of updates $x_1,x_2,\dots,x_T \in \{0,1\}$ the problem is to continuously release estimates of the prefix sums $\sum_{i=1}^t x_i$ for $t=1,\dots,T$ while protecting each input $x_i$ in the stream with differential privacy. Recently, significant leaps have been made in our understanding of this problem under $\textit{approximate}$ differential privacy, aka. $(\varepsilon,\delta)$$\textit{-differential privacy}$. However, for the classical case of $\varepsilon$-differential privacy, we are not aware of any improvement in mean squared error since the work of Honaker (TPDP 2015). In this paper we present such an improvement, reducing the mean squared error by a factor of about 4, asymptotically. The key technique is a new generalization of the binary tree mechanism that uses a $k$-ary number system with $\textit{negative digits}$ to improve the privacy-accuracy trade-off. Our mechanism improves the mean squared error over all 'optimal' $(\varepsilon,\delta)$-differentially private factorization mechanisms based on Gaussian noise whenever $\delta$ is sufficiently small. Specifically, using $k=19$ we get an asymptotic improvement over the bound given in the work by Henzinger, Upadhyay and Upadhyay (SODA 2023) when $\delta = O(T^{-0.92})$.
- Abstract（参考訳）: 連続観察下でのカウントは、差分プライバシーの分野でよく研究されている問題である。
x_1,x_2,\dots,x_T \in \{0,1\}$の更新ストリームが与えられた場合、問題は、ストリーム内の各入力$x_i$を差分プライバシで保護しながら、プレフィックスの和$\sum_{i=1}^t x_i$ for $t=1,\dots,T$の見積もりを継続的にリリースすることである。
最近、この問題の理解において、$\textit{approximate}$differential privacy, aka という大きな飛躍があった。
$(\varepsilon,\delta)$$\textit{-differential privacy}$.$(\varepsilon,\delta)$
しかし、古典的な$\varepsilon$-differential privacyのケースでは、Honaker(TPDP 2015)の作業以来、平均2乗誤差の改善を意識していません。
本稿では, 平均二乗誤差を約4倍に減らし, 漸近的に改善する。
鍵となるテクニックは、プライバシーと精度のトレードオフを改善するために$$k$-ary number system with $\textit{ negative digits}$を使用するバイナリツリー機構の新たな一般化である。
我々のメカニズムは、すべての「最適」$(\varepsilon,\delta)$-differentially private factorization mechanismに対して平均2乗誤差を改善する。
具体的には、$k=19$ を用いて、$\delta = O(T^{-0.92})$ のとき、ヘンジンガー、ウパディー、そして Upadhyay (SODA 2023) によって与えられる境界に対する漸近的な改善が得られる。
関連論文リスト
- Better Gaussian Mechanism using Correlated Noise [1.450405446885067]
分散を$(sqrtd + 1)/4$にスケールしたガウス変数として分布するランダム変数を追加することで、独立雑音サンプルの分散を$(d + sqrtd)/4$でのみスケールできることを示す。
私たちのメカニズムの中心的な考え方はシンプルで、そのテクニックは柔軟です。
論文 参考訳（メタデータ） (2024-08-13T12:31:03Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Differential privacy for symmetric log-concave mechanisms [0.0]
データベースクエリ結果にランダムノイズを加えることは、プライバシを達成するための重要なツールである。
我々は、すべての対称および対数凹形ノイズ密度に対して、$(epsilon, delta)$-differential privacyに対して十分かつ必要な条件を提供する。
論文 参考訳（メタデータ） (2022-02-23T10:20:29Z) - Infinitely Divisible Noise in the Low Privacy Regime [9.39772079241093]
ユーザ間でデータを分散し、共有しないフェデレーション学習は、プライバシ保護機械学習に対する一般的なアプローチとして現れている。
実数値データに対して、最初の可除な無限ノイズ分布を提示し、$varepsilon$-differential privacyを実現する。
論文 参考訳（メタデータ） (2021-10-13T08:16:43Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - A bounded-noise mechanism for differential privacy [3.9596068699962323]
ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。
我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
論文 参考訳（メタデータ） (2020-12-07T16:03:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。