論文の概要: Deciding Differential Privacy of Online Algorithms with Multiple Variables

• arxiv url: http://arxiv.org/abs/2309.06615v1
• Date: Tue, 12 Sep 2023 22:03:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 06:43:22.332360
• Title: Deciding Differential Privacy of Online Algorithms with Multiple Variables
• Title（参考訳）: 複数の変数を持つオンラインアルゴリズムの微分プライバシーの決定
• Authors: Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan, Bishnu Bhusal,
• Abstract要約: 本稿では,このようなアルゴリズムを記述するために,DiPautomaticaと呼ばれるオートマトンモデルを一般化する。 我々のPSPACEアルゴリズムは、与えられたオートマトンが微分プライベートである場合、$mathfrakD$の値も計算する。
• 参考スコア（独自算出の注目度）: 0.41248472494152805
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the problem of checking the differential privacy of online randomized algorithms that process a stream of inputs and produce outputs corresponding to each input. This paper generalizes an automaton model called DiP automata (See arXiv:2104.14519) to describe such algorithms by allowing multiple real-valued storage variables. A DiP automaton is a parametric automaton whose behavior depends on the privacy budget $\epsilon$. An automaton $A$ will be said to be differentially private if, for some $\mathfrak{D}$, the automaton is $\mathfrak{D}\epsilon$-differentially private for all values of $\epsilon>0$. We identify a precise characterization of the class of all differentially private DiP automata. We show that the problem of determining if a given DiP automaton belongs to this class is PSPACE-complete. Our PSPACE algorithm also computes a value for $\mathfrak{D}$ when the given automaton is differentially private. The algorithm has been implemented, and experiments demonstrating its effectiveness are presented.
• Abstract（参考訳）: 本稿では、入力ストリームを処理し、各入力に対応する出力を生成するオンラインランダム化アルゴリズムの差分プライバシーチェックの問題について考察する。 本稿では,複数の実数値ストレージ変数を許容することにより,Dip Automatica (See arXiv:2104.14519) と呼ばれるオートマトンモデルを一般化する。 DiPオートマトンは、プライバシー予算$\epsilon$に依存するパラメトリックオートマトンである。 オートマトン$A$は、ある$\mathfrak{D}$の場合、$\mathfrak{D}\epsilon$-differentially private for all values of $\epsilon>0$である。 微分プライベートなDiPオートマチックのクラスを正確に同定する。 与えられたDiPオートマトンがこのクラスに属するかどうかを決定する問題はPSPACE完全であることを示す。 我々のPSPACEアルゴリズムは、与えられたオートマトンが微分プライベートであるときに、$\mathfrak{D}$の値も計算する。 アルゴリズムが実装され,その有効性を示す実験結果が提示された。

関連論文リスト

• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。 この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
  論文  参考訳（メタデータ） (2024-06-24T04:06:09Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
  プライバシランダム変数の数値合成のための新しいアルゴリズムを提案する。 本アルゴリズムは,メカニズムを自己コンパイルするタスクに対して,$mathrmpolylog(k)$の実行時間とメモリ使用量を達成する。
  論文  参考訳（メタデータ） (2022-07-10T04:25:37Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes [78.27542864367821]
  強化学習(RL)アルゴリズムは、ユーザのプライベートで機密性の高いデータに依存するパーソナライズされたサービスを提供するために使用することができる。 ユーザのプライバシを保護するために、プライバシ保護RLアルゴリズムが要求されている。 線形混合MDPと呼ばれるマルコフ決定過程(MDP)のクラスを学習するための新しい$(varepsilon, delta)$-LDPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-19T17:44:09Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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