論文の概要: Differential Privacy for Clustering Under Continual Observation

• arxiv url: http://arxiv.org/abs/2307.03430v1
• Date: Fri, 7 Jul 2023 07:23:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-10 13:09:33.717292
• Title: Differential Privacy for Clustering Under Continual Observation
• Title（参考訳）: 連続観測におけるクラスタリングの差分プライバシー
• Authors: Max Dupr\'e la Tour, Monika Henzinger, David Saulpic
• Abstract要約: 我々は、点の挿入と削除の両方を行う$mathbbRd$のデータセットをプライベートにクラスタリングする問題を考える。 連続観測において、$k$-meansの目的に対して、$varepsilon$-differentially private clustering 機構を提供する。
• 参考スコア（独自算出の注目度）: 5.220940151628734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of clustering privately a dataset in $\mathbb{R}^d$ that undergoes both insertion and deletion of points. Specifically, we give an $\varepsilon$-differentially private clustering mechanism for the $k$-means objective under continual observation. This is the first approximation algorithm for that problem with an additive error that depends only logarithmically in the number $T$ of updates. The multiplicative error is almost the same as non privately. To do so we show how to perform dimension reduction under continual observation and combine it with a differentially private greedy approximation algorithm for $k$-means. We also partially extend our results to the $k$-median problem.
• Abstract（参考訳）: 我々は、点の挿入と削除の両方を行う$\mathbb{r}^d$のデータセットをプライベートにクラスタリングする問題を考える。 具体的には、連続観察下での$k$-means目的に対して、$\varepsilon$-differentially private clustering 機構を与える。 これは、更新数$t$の対数のみに依存する加法誤差を伴うこの問題に対する最初の近似アルゴリズムである。 乗算誤差は非プライベート誤差とほとんど同じである。 そこで本研究では,連続観測下で次元の縮小を図り,それを微分プライベートな近似アルゴリズムと組み合わせて$k$-meansを求める方法を示す。 結果も部分的に$k$-median問題に拡張します。

関連論文リスト

• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• Differentially Private Clustering in Data Streams [65.78882209673885]
  オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。 我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
  学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。 本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。 我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
  論文  参考訳（メタデータ） (2022-10-31T03:00:11Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• 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)
• Differentially private $k$-means clustering via exponential mechanism and max cover [6.736814259597673]
  我々は、$k$-meansクラスタリング問題に対して、新しい$(epsilon_p, delta_p)$-differentially privateアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2020-09-02T17:52:54Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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