論文の概要: Differentially Private Set Representations
- arxiv url: http://arxiv.org/abs/2501.16680v1
- Date: Tue, 28 Jan 2025 03:29:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-29 16:39:56.489302
- Title: Differentially Private Set Representations
- Title（参考訳）: Differentially Private Set Representation
- Authors: Sarvar Patel, Giuseppe Persiano, Joon Young Seo, Kevin Yeo,
- Abstract要約: 本研究では,大宇宙からの大きさの集合を$k$で表すために,差分プライベート(DP)機構の問題を考察する。
最初の構成では、$(epsilon,delta)$-DP表現を生成し、エラー確率は1/(eepsilon + 1)$で、少なくとも1.05 k epsilon cdot log(e)$ bitsで空間を使用する。
また、最大$k epsilon cdot log(e)$ bitsの空間を用いて、同じエラーを持つ純粋な$epsilon$-DP表現のための第2のアルゴリズムも提示する。
- 参考スコア（独自算出の注目度）: 13.576656322669098
- License:
- Abstract: We study the problem of differentially private (DP) mechanisms for representing sets of size $k$ from a large universe. Our first construction creates $(\epsilon,\delta)$-DP representations with error probability of $1/(e^\epsilon + 1)$ using space at most $1.05 k \epsilon \cdot \log(e)$ bits where the time to construct a representation is $O(k \log(1/\delta))$ while decoding time is $O(\log(1/\delta))$. We also present a second algorithm for pure $\epsilon$-DP representations with the same error using space at most $k \epsilon \cdot \log(e)$ bits, but requiring large decoding times. Our algorithms match our lower bounds on privacy-utility trade-offs (including constants but ignoring $\delta$ factors) and we also present a new space lower bound matching our constructions up to small constant factors. To obtain our results, we design a new approach embedding sets into random linear systems deviating from most prior approaches that inject noise into non-private solutions.
- Abstract（参考訳）: 本研究では,大宇宙からの大きさの集合を$k$で表すために,差分プライベート(DP)機構の問題を考察する。
最初の構成では、$(\epsilon,\delta)$-DP表現とエラー確率が1/(e^\epsilon + 1)$を最大で1.05 k \epsilon \cdot \log(e)$ビットとします。
また、最大$k \epsilon \cdot \log(e)$ bitsの空間を用いて、同じ誤差で$\epsilon$-DP表現を純粋な$\epsilon$-DP表現に対して2番目のアルゴリズムを提案する。
私たちのアルゴリズムは、プライバシとユーティリティのトレードオフ(定数を含むが$\delta$ Factorを無視している)の低い境界と一致し、また、構造を小さな定数要素まで一致させる新しい領域も提示します。
そこで本研究では,非私的解にノイズを注入する従来の手法から逸脱した,ランダムな線形系に集合を埋め込む手法を考案した。
関連論文リスト
- Nearly-Linear Time Seeded Extractors with Short Seeds [9.896415488558036]
種子長と出力長の大きい種子抽出機の既設構造を時間内に実行した。
本研究では, コンデンサと古典的手法を併用して, 高ミンエントロピー源のシード抽出器を構築することにより, 強い抽出器が得られることを示す。
また、RAMモデルにおいて真に線形時間で評価できるトレビサン抽出器のインスタンス化を行う。
論文 参考訳（メタデータ） (2024-11-12T01:19:35Z) - Differentially Private Kernel Density Estimation [11.526850085349155]
我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。
類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
論文 参考訳（メタデータ） (2024-09-03T08:01:19Z) - Profile Reconstruction from Private Sketches [13.929335175122265]
$mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。
分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。
LPベースの手法の高速化方法を示します
論文 参考訳（メタデータ） (2024-06-03T09:51:28Z) - Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。
目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。
1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文 参考訳（メタデータ） (2023-11-13T15:53:45Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。