論文の概要: Differentially Private Clustering in Data Streams
- arxiv url: http://arxiv.org/abs/2307.07449v2
- Date: Mon, 8 Jan 2024 02:32:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 23:39:35.859284
- Title: Differentially Private Clustering in Data Streams
- Title（参考訳）: データストリームにおける異なるプライベートクラスタリング
- Authors: Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong
- Abstract要約: オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
- 参考スコア（独自算出の注目度）: 65.78882209673885
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The streaming model is an abstraction of computing over massive data streams,
which is a popular way of dealing with large-scale modern data analysis. In
this model, there is a stream of data points, one after the other. A streaming
algorithm is only allowed one pass over the data stream, and the goal is to
perform some analysis during the stream while using as small space as possible.
Clustering problems (such as $k$-means and $k$-median) are fundamental
unsupervised machine learning primitives, and streaming clustering algorithms
have been extensively studied in the past. However, since data privacy becomes
a central concern in many real-world applications, non-private clustering
algorithms are not applicable in many scenarios.
In this work, we provide the first differentially private streaming
algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean
data points over a stream with length at most $T$ using $poly(k,d,\log(T))$
space to achieve a constant multiplicative error and a $poly(k,d,\log(T))$
additive error. In particular, we present a differentially private streaming
clustering framework which only requires an offline DP coreset or clustering
algorithm as a blackbox. By plugging in existing results from DP clustering
Ghazi, Kumar, Manurangsi 2020 and Kaplan, Stemmer 2018, we achieve (1) a
$(1+\gamma)$-multiplicative approximation with
$\tilde{O}_\gamma(poly(k,d,\log(T)))$ space for any $\gamma>0$, and the
additive error is $poly(k,d,\log(T))$ or (2) an $O(1)$-multiplicative
approximation with $\tilde{O}(k^{1.5} \cdot poly(d,\log(T)))$ space and
$poly(k,d,\log(T))$ additive error. In addition, our algorithmic framework is
also differentially private under the continual release setting, i.e., the
union of outputs of our algorithms at every timestamp is always differentially
private.
- Abstract（参考訳）: ストリーミングモデルは大規模データストリーム上のコンピューティングの抽象化であり、大規模データ分析を扱う一般的な方法である。
このモデルでは、データポイントのストリームが次々に存在します。
ストリーミングアルゴリズムは、データストリームをパスする唯一の方法であり、可能な限り小さなスペースを使用して、ストリーム中にいくつかの分析を行うことが目標である。
クラスタリング問題($k$-meansや$k$-medianなど)は基本的な教師なし機械学習プリミティブであり、ストリーミングクラスタリングアルゴリズムは過去に広く研究されてきた。
しかし、データプライバシが多くの現実世界アプリケーションにおいて中心的な関心事になっているため、プライベートでないクラスタリングアルゴリズムは多くのシナリオでは適用できない。
本研究では,$k$-means と $k$-median に対する最初の微分的プライベートなストリーミングアルゴリズムを提供する。$k$-means と $k$-median による,$d$-dimensional euclidean データポイントを最大$t$ のストリーム上にクラスタリングし,定数乗算誤差と $poly(k,d,\log(t))$ 加算誤差を達成するために $poly(k,d)$ を用いた。
特に,オフラインDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
DPクラスタリング Ghazi, Kumar, Manurangsi 2020 と Kaplan, Stemmer 2018 の既存の結果をプラグインすることで、(1) a $(1+\gamma)$-multiplicative approximation with $\tilde{O}_\gamma(poly(k,d,\log(T)))$ space for any $\gamma>0$, and the additive error is $poly(k,d,\log(T))$ or (2) a $O(1)$-multiplicative approximation with $\tilde{O}(k^{1.5} \cdot poly(d,\log(T)))$ space and $poly(k,d,\log(T))$ additive error。
さらに、我々のアルゴリズムフレームワークは、連続的なリリース設定の下で微分プライベートであり、すなわち、各タイムスタンプにおけるアルゴリズムの出力の統一は常に微分プライベートである。
関連論文リスト
- Online Differentially Private Synthetic Data Generation [10.177542186664503]
差分プライベートな合成データセットを毎回$t$で生成するオンラインアルゴリズムを開発した。
このアルゴリズムは、$O(log(t)t-1/d)$ for $dgeq 2$と$O(log4.5(t)t-1)$ for $d=1$の近似精度を1-ワッサーシュタイン距離で達成する。
論文 参考訳（メタデータ） (2024-02-12T19:21:14Z) - 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Fair and Representative Subset Selection from Data Streams [4.53279507109072]
ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。
ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-09T07:49:13Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。