論文の概要: On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries
- arxiv url: http://arxiv.org/abs/2012.09116v1
- Date: Wed, 16 Dec 2020 17:58:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-03 02:41:11.378909
- Title: On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries
- Title(参考訳): 複数の異なるプライベートクエリを答える際のユニオンバウンド回避について
- Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi
- Abstract要約: このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
- 参考スコア(独自算出の注目度): 49.453751858361265
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study the problem of answering $k$ queries with $(\epsilon,
\delta)$-differential privacy, where each query has sensitivity one. We give an
algorithm for this task that achieves an expected $\ell_\infty$ error bound of
$O(\frac{1}{\epsilon}\sqrt{k \log \frac{1}{\delta}})$, which is known to be
tight (Steinke and Ullman, 2016).
A very recent work by Dagan and Kur (2020) provides a similar result, albeit
via a completely different approach. One difference between our work and theirs
is that our guarantee holds even when $\delta < 2^{-\Omega(k/(\log k)^8)}$
whereas theirs does not apply in this case. On the other hand, the algorithm of
Dagan and Kur has a remarkable advantage that the $\ell_{\infty}$ error bound
of $O(\frac{1}{\epsilon}\sqrt{k \log \frac{1}{\delta}})$ holds not only in
expectation but always (i.e., with probability one) while we can only get a
high probability (or expected) guarantee on the error.
- Abstract(参考訳): 本研究では,各問合せが1つの感度を持つ,$(\epsilon, \delta)$差分プライバシで$k$クエリに応答する問題を考察する。
このタスクのアルゴリズムは、$o(\frac{1}{\epsilon}\sqrt{k \log \frac{1}{\delta}})$の期待値$\ell_\infty$エラーバウンドを達成し、タイトであることが知られている(steinke and ullman, 2016)。
dagan and kur (2020) による最近の研究でも、まったく異なるアプローチで同様の結果が得られている。
私たちの仕事と彼らの仕事との違いの1つは、我々の保証が $\delta < 2^{-\Omega(k/(\log k)^8)}$ であっても成り立つことである。
一方、Dagan と Kur のアルゴリズムは、$\ell_{\infty}$ の誤差境界が $O(\frac{1}{\epsilon}\sqrt{k \log \frac{1}{\delta}})$ が期待されるだけでなく、常に(確率 1 で)成り立つが、その誤差に対して高い確率(あるいは予想される)保証しか得られないという驚くべき優位性を持っている。
関連論文リスト
- Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳(メタデータ) (2023-06-03T04:00:47Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳(メタデータ) (2023-03-10T00:11:18Z) - Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data [22.233705161499273]
我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。
我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
論文 参考訳(メタデータ) (2022-01-10T08:17:05Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - 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) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳(メタデータ) (2021-07-31T22:23:39Z) - 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) - Query complexity of unitary operation discrimination [6.6802048869908965]
ユニタリ演算の識別は、量子計算と情報の基本である。
所望の失敗確率が$epsilon$で、$U$と$V$の識別に必要となるクエリ数を示す。
論文 参考訳(メタデータ) (2020-12-05T03:49:01Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。