Fugu-MT 論文翻訳(概要): Differentially-Private Sublinear-Time Clustering

論文の概要: Differentially-Private Sublinear-Time Clustering

arxiv url: http://arxiv.org/abs/2112.13751v1
Date: Mon, 27 Dec 2021 16:01:30 GMT
ステータス: 処理完了
システム内更新日: 2021-12-28 18:54:52.273187
Title: Differentially-Private Sublinear-Time Clustering
Title（参考訳）: 微分プライベートサブリニア時間クラスタリング
Authors: Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Abstract要約: クラスタリングは教師なし機械学習において必須のプリミティブである。本稿では,研究の自然的かつ意欲的な方向性として,サブ線形時間差分的クラスタリングの問題を提起する。
参考スコア（独自算出の注目度）: 9.399840807973543
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Clustering is an essential primitive in unsupervised machine learning. We bring forth the problem of sublinear-time differentially-private clustering as a natural and well-motivated direction of research. We combine the $k$-means and $k$-median sublinear-time results of Mishra et al. (SODA, 2001) and of Czumaj and Sohler (Rand. Struct. and Algorithms, 2007) with recent results on private clustering of Balcan et al. (ICML 2017), Gupta et al. (SODA, 2010) and Ghazi et al. (NeurIPS, 2020) to obtain sublinear-time private $k$-means and $k$-median algorithms via subsampling. We also investigate the privacy benefits of subsampling for group privacy.
Abstract（参考訳）: クラスタリングは教師なし機械学習において必須のプリミティブである。本稿では,研究の自然な方向性として,サブ線形時間差分的クラスタリングの問題を提起する。 mishra et al. (soda, 2001) と czumaj and sohler (rand. struct. and algorithms, 2007) の k$-means と $k$-median sublinear-time の結果と、balcan et al. (icml 2017) と gupta et al. (soda, 2010) と ghazi et al. (neurips, 2020) のプライベートクラスタリングに関する最近の結果とを組み合わせることで、サブサンプリングを通じてサブリニアタイムのプライベート $k$-means と $k$median アルゴリズムを得ることができる。グループプライバシに対するサブサンプリングのプライバシーメリットについても検討する。

関連論文リスト

Differential privacy and Sublinear time are incompatible sometimes [12.776401866635844]
片方向境界に基づく単純な問題は、差分プライベートアルゴリズムとサブ線形時間アルゴリズムの両方をもたらすことを示す。我々は、微分プライベートである厳密な'サブ線形時間アルゴリズムを認めない。
論文参考訳（メタデータ） (2024-07-09T22:33:57Z)
Privacy-preserving Continual Federated Clustering via Adaptive Resonance Theory [11.190614418770558]
クラスタリング領域では、フェデレーション学習フレームワーク(フェデレーションクラスタリング)を用いた様々なアルゴリズムが活発に研究されている。本稿では,プライバシ保護型継続フェデレーションクラスタリングアルゴリズムを提案する。合成および実世界のデータセットによる実験結果から,提案アルゴリズムはクラスタリング性能が優れていることが示された。
論文参考訳（メタデータ） (2023-09-07T05:45:47Z)
Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文参考訳（メタデータ） (2023-07-14T16:11:22Z)
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)
Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文参考訳（メタデータ） (2021-12-29T08:13:56Z)
Differentially Private Algorithms for Clustering with Stability Assumptions [0.76146285961466]
安定な入力をクラスタリングするためのより単純なアルゴリズムを提案する。我々はWasserstein距離とk-meansコストの両方でその実用性を分析する。我々のアルゴリズムは、k-medianインスタンスの「ニッチ」と微分プライバシの局所モデルのためのストレートフォワードアナログを持つ。
論文参考訳（メタデータ） (2021-06-11T00:45:39Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
Differentially Private Correlation Clustering [23.93805663525436]
相関クラスタリングは教師なし機械学習で広く使われている手法である。個人のプライバシーが懸念されるアプリケーションに動機づけられて、微分プライベート相関クラスタリングの研究を開始します。
論文参考訳（メタデータ） (2021-02-17T17:27:48Z)
Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文参考訳（メタデータ） (2020-08-18T16:22:06Z)

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