Fugu-MT 論文翻訳(概要): Private Counting of Distinct Elements in the Turnstile Model and Extensions

論文の概要: Private Counting of Distinct Elements in the Turnstile Model and Extensions

arxiv url: http://arxiv.org/abs/2408.11637v1
Date: Wed, 21 Aug 2024 14:06:22 GMT
ステータス: 処理完了
システム内更新日: 2024-08-22 16:47:35.153645
Title: Private Counting of Distinct Elements in the Turnstile Model and Extensions
Title（参考訳）: 旋回モデルと拡張における離散要素のプライベートカウント
Authors: Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner,
Abstract要約: スパースベクトル法に基づく非常に単純なアルゴリズムは、アイテムレベルの$(epsilon,delta)$-differential privacyに対して厳密な加算誤差を実現する。 2つ目の結果は、大規模なアルゴリズムでは、アイテムレベルの差分プライバシからイベントレベルの差分プライバシまでのバウンドが低いことを示すバウンドである。
参考スコア（独自算出の注目度）: 2.5200018924833327
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level $(\epsilon,\delta)$-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level $(\epsilon,\delta)$-differential privacy and item-level $\epsilon$-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023].
Abstract（参考訳）: ストリーム内の異なる要素をプライベートにカウントすることは、機械学習における多くのアプリケーションにおける基本的なデータ分析問題である。ターンタイルモデルにおいて、Jain et al [NeurIPS2023] は、任意の要素の最大リフレナンシによってパラメータ化されるこの問題の研究を開始した。アイテムレベルの$(\epsilon,\delta)$-differentially privateアルゴリズムは、そのパラメータ化に関して加算誤差が厳密である。本研究では,スパースベクトル法に基づく非常に単純なアルゴリズムが,項目レベルの$(\epsilon,\delta)$-差分プライバシと項目レベルの$\epsilon$-差分プライバシに対して,異なるパラメータ化,すなわちすべてのフリップパンシーの和に対して,厳密な加算誤差を実現することを示す。 2つ目の結果は、この問題に対する既存の微分プライベートアルゴリズムを含む、大規模なアルゴリズムのクラスにおいて、アイテムレベルの差分プライバシからイベントレベルの差分プライバシまでのバウンドが低いことを示すバウンドである。これはJainらによるオープンな質問に答えます [NeurIPS2023]。

関連論文リスト

Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
完全動的更新を伴う連続リリースの難易度設定において,グラフを解析するための差分プライベートアルゴリズムについて検討した。これまでの研究では、挿入のみや削除のみを処理できる多くのグラフ問題に対して、差分プライベートなアルゴリズムが提案されてきた。いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。
論文参考訳（メタデータ） (2024-09-26T08:17:49Z)
Making Old Things New: A Unified Algorithm for Differentially Private Clustering [6.320600791108065]
20年前のアルゴリズムは、いずれのモデルでも、わずかに修正可能であることを示す。これは統一された図を提供する: ほとんどすべての既知結果とマッチングする一方で、いくつかの改善を可能にします。
論文参考訳（メタデータ） (2024-06-17T15:31:53Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文参考訳（メタデータ） (2024-06-07T12:07:16Z)
User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文参考訳（メタデータ） (2023-09-21T21:51:55Z)
Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation [3.9476868147424162]
挿入や削除を処理するすべての異なるプライベートなメカニズムは、比較的弱いイベントレベルのプライバシ定義の下でも、最低でもT1/4$の付加エラーがあることを示す。最大フリップパンシー$w$を持つすべてのターンタイルストリームに対して、$O(sqrtw cdot polylog T)$加法誤差で異なる要素の数を連続的に出力するアイテムレベル微分プライベート機構を提案する。
論文参考訳（メタデータ） (2023-06-11T16:54:39Z)
Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
論文参考訳（メタデータ） (2023-05-02T03:23:07Z)
Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models [9.679150363410471]
本稿では,$d$-dimensional Gaussian Mixture Models (GMM) のパラメータを$k$コンポーネントでプライベートに推定する問題について検討する。我々はその問題を非私的な問題に還元する手法を開発した。我々は,Moitra Valiant と[MV10] の非プライベートアルゴリズムを用いて,GMM をブラックボックスとして学習するための$(varepsilon, delta)$-differentially privateアルゴリズムを開発した。
論文参考訳（メタデータ） (2023-03-07T23:24:27Z)
Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文参考訳（メタデータ） (2022-05-05T06:43:46Z)
Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文参考訳（メタデータ） (2021-02-23T18:25:13Z)
Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文参考訳（メタデータ） (2020-08-18T16:22:06Z)
Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
論文参考訳（メタデータ） (2020-07-18T09:12:03Z)

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

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