Fugu-MT 論文翻訳(概要): Differentially Private Clustering in Data Streams

論文の概要: Differentially Private Clustering in Data Streams

arxiv url: http://arxiv.org/abs/2307.07449v3
Date: Thu, 02 Oct 2025 13:35:31 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-03 16:59:19.364526
Title: Differentially Private Clustering in Data Streams
Title（参考訳）: データストリームにおける異なるプライベートクラスタリング
Authors: Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong,
Abstract要約: 私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
参考スコア（独自算出の注目度）: 56.26040303056582
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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 may not be as applicable in many scenarios. In this work, we provide the first differentially private algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream with length at most $T$ using space that is sublinear (in $T$) in the continual release setting where the algorithm is required to output a clustering at every timestep. We achieve (1) 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, or (2) a $(1+\gamma)$-multiplicative approximation with $\tilde{O}_\gamma(poly(k,2^{O_\gamma(d)},\log(T)))$ space for any $\gamma>0$, and the additive error is $poly(k,2^{O_\gamma(d)},\log(T))$. Our main technical contribution is a differentially private clustering framework for data streams which only requires an offline DP coreset or clustering algorithm as a blackbox.
Abstract（参考訳）: クラスタリング問題($k$-meansや$k$-medianなど)は基本的な教師なし機械学習プリミティブであり、ストリーミングクラスタリングアルゴリズムは過去に広く研究されてきた。しかし、データプライバシが多くの実世界のアプリケーションにおいて中心的な関心事になっているため、プライベートでないクラスタリングアルゴリズムは、多くのシナリオでは適用できないかもしれない。本研究では,最大で最大$T$のストリーム上のEuclideanデータポイントの$k$-meansと$k$-medianクラスタリングに対して,連続的なリリース設定においてサブ線形な空間($T$)を用いて,アルゴリズムがクラスタリングを毎回出力する必要がある,最初の微分プライベートなアルゴリズムを提供する。 O(1)$-multiplicative approximation with $\tilde{O}(k^{1.5} \cdot poly(d,\log(T)))$ space and $poly(k,d,\log(T))$ additive error, or (2) a $ 1+\gamma)$-multiplicative approximation with $\tilde{O}_\gamma(poly(k,2^{O_\gamma(d)},\log(T)))$ space for any $\gamma>0$, and the additive error is $poly(k,2^{O_\gamma(d)},\log(T)$$。当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。

関連論文リスト

Private Continual Counting of Unbounded Streams [11.941250828872189]
入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。一般的な2倍のトリックを使用すると、$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。先行研究で研究された関数 $frac1sqrt1-z$ の対数摂動に基づく新しい行列分解を導入する。
論文参考訳（メタデータ） (2025-06-17T23:09:53Z)
Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
論文参考訳（メタデータ） (2025-05-29T17:21:20Z)
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)
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)
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)

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

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