論文の概要: A closed form scale bound for the $(\epsilon, \delta)$-differentially
private Gaussian Mechanism valid for all privacy regimes
- arxiv url: http://arxiv.org/abs/2012.10523v2
- Date: Thu, 21 Jan 2021 14:01:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-01 18:04:46.273821
- Title: A closed form scale bound for the $(\epsilon, \delta)$-differentially
private Gaussian Mechanism valid for all privacy regimes
- Title(参考訳): すべてのプライバシー制度に有効な(\epsilon, \delta)$-微分的プライベートガウス機構に縛られる閉じた形式スケール
- Authors: Staal A. Vinterbo
- Abstract要約: 同様の閉じた形式 $sigma geq delta (epsilonsqrt2)-1 left (sqrtaz+epsilon + ssqrtazright)$ for $epsilon in (0,1)$ を示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The standard closed form lower bound on $\sigma$ for providing $(\epsilon,
\delta)$-differential privacy by adding zero mean Gaussian noise with variance
$\sigma^2$ is $\sigma > \Delta\sqrt {2}(\epsilon^{-1}) \sqrt {\log \left(
5/4\delta^{-1} \right)}$ for $\epsilon \in (0,1)$. We present a similar closed
form bound $\sigma \geq \Delta (\epsilon\sqrt{2})^{-1} \left(\sqrt{az+\epsilon}
+ s\sqrt{az}\right)$ for $z=-\log(4\delta(1-\delta))$ and $(a,s)=(1,1)$ if
$\delta \leq 1/2$ and $(a,s)=(\pi/4,-1)$ otherwise. Our bound is valid for all
$\epsilon > 0$ and is always lower (better). We also present a sufficient
condition for $(\epsilon, \delta)$-differential privacy when adding noise
distributed according to even and log-concave densities supported everywhere.
- Abstract(参考訳): 分散$\sigma^2$ is $\sigma > \delta\sqrt {2}(\epsilon^{-1}) \sqrt {\log \left(5/4\delta^{-1} \right)}$\epsilon \in (0,1)$である。
同様の閉形式は、$\sigma \geq \Delta (\epsilon\sqrt{2})^{-1} \left(\sqrt{az+\epsilon} + s\sqrt{az}\right)$ for $z=-\log(4\delta(1-\delta))$ and $(a,s)=(1,1)$ if $\delta \leq 1/2$ and $(a,s)=(\pi/4,-1)$である。
我々の境界はすべての$\epsilon > 0$に対して有効であり、常に低い(より低い)。
また,偶数と対数対数対数密度に比例して分布するノイズを付加する場合,$(\epsilon, \delta)$-differential プライバシの十分条件を示す。
関連論文リスト
- $\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) - 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) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - 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) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳(メタデータ) (2021-03-17T18:18:57Z) - Mathematical comparison of classical and quantum mechanisms in
optimization under local differential privacy [0.0]
我々は、$mathrmEC_n(varepsilon)not=mathrmCQ_n(varepsilon)$ for every $nge3$を示し、$mathrmEC_n(varepsilon)$と$mathrmCQ_n(varepsilon)$の差をある方法で見積もる。
論文 参考訳(メタデータ) (2020-11-19T17:05:11Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳(メタデータ) (2020-06-23T20:21:27Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。