論文の概要: Differentially Private Clustering: Tight Approximation Ratios

• arxiv url: http://arxiv.org/abs/2008.08007v1
• Date: Tue, 18 Aug 2020 16:22:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-27 21:12:09.224507
• Title: Differentially Private Clustering: Tight Approximation Ratios
• Title（参考訳）: 微分プライベートクラスタリング:密接な近似比
• Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi
• Abstract要約: 基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
• 参考スコア（独自算出の注目度）: 57.89473217052714
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors. Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
• Abstract（参考訳）: 差分プライベートクラスタリングの課題について検討する。 Euclidean DensestBall, 1-Cluster, k-means, k-medianなど,いくつかの基本的なクラスタリング問題に対して,任意の非プライベートアルゴリズムで得られるものと同じ近似比を本質的に達成する,効率的な微分プライベートアルゴリズムを提供する。 これにより、ある大きな定数近似係数のみを達成する既存の効率的なアルゴリズムが改善される。 この結果から,サンプルおよびアグリゲートプライバシフレームワークのための改良アルゴリズムも示唆された。 さらに、我々の1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得られることを示す。

関連論文リスト

• From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection [12.993073967843292]
  我々は,未知の地下構造クラスタリングを用いて,半教師付き環境で問題を研究する。 本稿では,クラスタリングアルゴリズムの精度向上のためのサイズ一般化の概念を提案する。 データセット全体においてどのアルゴリズムが最適かを特定するために、データの5%をサブサンプルとして使用しています。
  論文  参考訳（メタデータ） (2024-02-22T06:53:35Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• 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 Correlation Clustering [23.93805663525436]
  相関クラスタリングは教師なし機械学習で広く使われている手法である。 個人のプライバシーが懸念されるアプリケーションに動機づけられて、微分プライベート相関クラスタリングの研究を開始します。
  論文  参考訳（メタデータ） (2021-02-17T17:27:48Z)
• Clustering of Big Data with Mixed Features [3.3504365823045044]
  我々は混合型の大規模データのための新しいクラスタリングアルゴリズムを開発した。 このアルゴリズムは、比較的低い密度値の外れ値とクラスターを検出することができる。 本研究では,本アルゴリズムが実際に有効であることを示す実験結果を示す。
  論文  参考訳（メタデータ） (2020-11-11T19:54:38Z)
• Differentially Private Clustering via Maximum Coverage [7.059472280274009]
  我々は、個々のデータのプライバシーを維持しながら、計量空間におけるクラスタリングの問題を研究する。 一定の乗法誤差と低い加算誤差を持つ差分アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-27T22:11:18Z)
• Differentially Private k-Means Clustering with Guaranteed Convergence [5.335316436366718]
  反復的なクラスタリングアルゴリズムは、データの背後にある洞察を学習するのに役立ちます。 敵は、背景知識によって個人のプライバシーを推測することができる。 このような推論攻撃に対して個人のプライバシを保護するため、反復クラスタリングアルゴリズムの差分プライバシー(DP)を広く研究している。
  論文  参考訳（メタデータ） (2020-02-03T22:53:47Z)

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

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