論文の概要: Differentially Private Approximate Pattern Matching

• arxiv url: http://arxiv.org/abs/2311.07415v1
• Date: Mon, 13 Nov 2023 15:53:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 23:22:19.359309
• Title: Differentially Private Approximate Pattern Matching
• Title（参考訳）: 微分プライベート近似パターンマッチング
• Authors: Teresa Anna Steiner,
• Abstract要約: 我々は差分プライバシー下での$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)
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the $k$-approximate pattern matching problem under differential privacy, where the goal is to report or count all substrings of a given string $S$ which have a Hamming distance at most $k$ to a pattern $P$, or decide whether such a substring exists. In our definition of privacy, individual positions of the string $S$ are protected. To be able to answer queries under differential privacy, we allow some slack on $k$, i.e. we allow reporting or counting substrings of $S$ with a distance at most $(1+\gamma)k+\alpha$ to $P$, for a multiplicative error $\gamma$ and an additive error $\alpha$. We analyze which values of $\alpha$ and $\gamma$ are necessary or sufficient to solve the $k$-approximate pattern matching problem while satisfying $\epsilon$-differential privacy. Let $n$ denote the length of $S$. We give 1) an $\epsilon$-differentially private algorithm with an additive error of $O(\epsilon^{-1}\log n)$ and no multiplicative error for the existence variant; 2) an $\epsilon$-differentially private algorithm with an additive error $O(\epsilon^{-1}\max(k,\log n)\cdot\log n)$ for the counting variant; 3) an $\epsilon$-differentially private algorithm with an additive error of $O(\epsilon^{-1}\log n)$ and multiplicative error $O(1)$ for the reporting variant for a special class of patterns. The error bounds hold with high probability. All of these algorithms return a witness, that is, if there exists a substring of $S$ with distance at most $k$ to $P$, then the algorithm returns a substring of $S$ with distance at most $(1+\gamma)k+\alpha$ to $P$. Further, we complement these results by a lower bound, showing that any algorithm for the existence variant which also returns a witness must have an additive error of $\Omega(\epsilon^{-1}\log n)$ with constant probability.
• Abstract（参考訳）: 本稿では、差分プライバシー下での$k$-approximateパターンマッチング問題について考察する。ここでは、与えられた文字列のすべてのサブストリングを報告またはカウントすることを目的としており、最大で$k$のハミング距離を持つ$S$をパターン$P$に設定するか、そのようなサブストリングが存在するかどうかを決定する。 プライバシの定義では、文字列$S$の個々の位置が保護されます。 差分プライバシーの下でクエリに答えられるためには、$k$のスラック、すなわち、最大$(1+\gamma)k+\alpha$から$P$までのレポートやサブストリングを、乗算誤差$\gamma$と加算エラー$\alpha$に対して許可する。 我々は、$\epsilon$-differential privacyを満足しながら、$k$-approximateパターンマッチング問題を解決するのに、$\alpha$と$\gamma$の値が必要なのか、あるいは十分なのかを分析する。 $n$は$S$の長さを表す。 我々は与える 1)$\epsilon$-differentially private algorithm with an additive error of $O(\epsilon^{-1}\log n)$ and no multiplicative error for the existence variant。 2)$\epsilon$-differentially private algorithm with an additive error $O(\epsilon^{-1}\max(k,\log n)\cdot\log n)$ for the counting variant; 3)$\epsilon$-differentially private algorithm with an additive error of $O(\epsilon^{-1}\log n)$ and multiplicative error $O(1)$ for the reporting variant for a special class of pattern。 誤差境界は高い確率で保持される。 これら全てのアルゴリズムが証人を返す、すなわち、距離が最大$k$から$P$の$S$のサブストリングが存在するなら、アルゴリズムは距離が最大$(1+\gamma)k+\alpha$の$S$のサブストリングを最大$P$に返す。 さらに、これらの結果を下界で補い、証人を返す存在変種に対する任意のアルゴリズムは、一定の確率で$\Omega(\epsilon^{-1}\log n)$の加法誤差を持つ必要があることを示す。

関連論文リスト

• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• Differentially Private Set Representations [13.576656322669098]
  本研究では,大宇宙からの大きさの集合を$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のアルゴリズムも提示する。
  論文  参考訳（メタデータ） (2025-01-28T03:29:00Z)
• Continual Counting with Gradual Privacy Expiration [15.87191465142231]
  提案アルゴリズムは,大規模なプライバシー有効期限関数に対して,O(log(T)/epsilon)$の加算誤差を実現する。 我々の経験的評価は、自然ベースラインアルゴリズムよりも大きな値の$d$に対する経験的プライバシ損失が著しく小さく、徐々に増加するプライバシー損失を達成していることを示している。
  論文  参考訳（メタデータ） (2024-06-06T07:20:16Z)
• 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)
• 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)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。 一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
  論文  参考訳（メタデータ） (2020-12-16T17:58:45Z)
• Query complexity of unitary operation discrimination [6.6802048869908965]
  ユニタリ演算の識別は、量子計算と情報の基本である。 所望の失敗確率が$epsilon$で、$U$と$V$の識別に必要となるクエリ数を示す。
  論文  参考訳（メタデータ） (2020-12-05T03:49:01Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)

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

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