論文の概要: 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 で)成り立つが、その誤差に対して高い確率(あるいは予想される)保証しか得られないという驚くべき優位性を持っている。

関連論文リスト

• 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)
• 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)
• 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)
• 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)
• 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)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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