論文の概要: PREM: Privately Answering Statistical Queries with Relative Error

• arxiv url: http://arxiv.org/abs/2502.14809v1
• Date: Thu, 20 Feb 2025 18:32:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 17:44:12.496278
• Title: PREM: Privately Answering Statistical Queries with Relative Error
• Title（参考訳）: PreM: 相対エラーで統計的クエリをプライベートに答える
• Authors: Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Sushant Sachdeva,
• Abstract要約: 合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
• 参考スコア（独自算出の注目度）: 91.98332694700046
• License:
• Abstract: We introduce $\mathsf{PREM}$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a relative error guarantee for statistical queries under $(\varepsilon, \delta)$ differential privacy (DP). Namely, for a domain ${\cal X}$, a family ${\cal F}$ of queries $f : {\cal X} \to \{0, 1\}$, and $\zeta > 0$, our framework yields a mechanism that on input dataset $D \in {\cal X}^n$ outputs a synthetic dataset $\widehat{D} \in {\cal X}^n$ such that all statistical queries in ${\cal F}$ on $D$, namely $\sum_{x \in D} f(x)$ for $f \in {\cal F}$, are within a $1 \pm \zeta$ multiplicative factor of the corresponding value on $\widehat{D}$ up to an additive error that is polynomial in $\log |{\cal F}|$, $\log |{\cal X}|$, $\log n$, $\log(1/\delta)$, $1/\varepsilon$, and $1/\zeta$. In contrast, any $(\varepsilon, \delta)$-DP mechanism is known to require worst-case additive error that is polynomial in at least one of $n, |{\cal F}|$, or $|{\cal X}|$. We complement our algorithm with nearly matching lower bounds.
• Abstract（参考訳）: 本稿では,合成データを生成するための新しいフレームワークである$\mathsf{PREM}$(Private Relative Error Multiplicative weight update)を紹介し,$(\varepsilon, \delta)$差分プライバシー(DP)の下での統計的クエリに対する相対誤差保証を実現する。 すなわち、ドメイン${\cal X}$に対して、クエリ$f : {\cal X} \to \{0, 1\}$, and $\zeta > 0$のファミリ${\cal F}$に対して、我々のフレームワークは入力データセット$D \in {\cal X}^n$で合成データセット$\widehat{D} \in {\cal X}^n$を出力し、$D$で${\cal F}$のすべての統計的クエリ、すなわち$\sum_{x \in D} f(x)$ for $f \in {\cal F}$は、$\widehat{D}$で対応する値の乗算係数が$$1 \pm \zeta$$$$$$$$$1\widehat{D}$$\log |\log |\log |\log/n$$$$1/$/$である。 対照的に、任意の$(\varepsilon, \delta)$-DPメカニズムは、少なくとも$n, |{\cal F}|$, $|{\cal X}|$の多項式である最悪の加法誤差を必要とすることが知られている。 我々はアルゴリズムをほぼ一致する下界で補完する。

関連論文リスト

• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Terminal Embeddings in Sublinear Time [14.959896180728832]
  我々は、$T$を前処理して、サブ線形時間における$qinmathbbRd$の端末埋め込み画像の計算をサポートする、ほぼ線形空間のデータ構造を得る方法を示す。 この研究の主な貢献は、端末の埋め込みを計算するための新しいデータ構造を提供することです。
  論文  参考訳（メタデータ） (2021-10-17T00:50:52Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Simplest non-additive measures of quantum resources [77.34726150561087]
  我々は $cal E(rhootimes N) = E(e;N) ne Ne$ で説明できる測度について研究する。
  論文  参考訳（メタデータ） (2021-06-23T20:27:04Z)
• Sharper bounds for online learning of smooth functions of a single variable [0.0]
  ここでは$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$を示します。 また、$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$ も示します。
  論文  参考訳（メタデータ） (2021-05-30T23:06:21Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Learning and Testing Variable Partitions [13.575794982844222]
  我々は $mathcalO(k n2)(delta + epsilon)$ が、任意の $epsilon > 0$ に対して $tildemathcalO(n2 mathrmpoly (1/epsilon)$ で学習可能であることを示す。 また、両面のテスタでさえ$k = 2$の場合に$Omega(n)$クエリが必要であることも示しています。
  論文  参考訳（メタデータ） (2020-03-29T10:12:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。