論文の概要: Scalable Differentially Private Clustering via Hierarchically Separated Trees

• arxiv url: http://arxiv.org/abs/2206.08646v1
• Date: Fri, 17 Jun 2022 09:24:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-20 15:46:58.953029
• Title: Scalable Differentially Private Clustering via Hierarchically Separated Trees
• Title（参考訳）: 階層的分離木によるスケーラブルな微分プライベートクラスタリング
• Authors: Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz, David Saulpic, Chris Schwiegelshohn, Sergei Vassilvitskii
• Abstract要約: 我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
• 参考スコア（独自算出の注目度）: 82.69664595378869
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the private $k$-median and $k$-means clustering problem in $d$ dimensional Euclidean space. By leveraging tree embeddings, we give an efficient and easy to implement algorithm, that is empirically competitive with state of the art non private methods. We prove that our method computes a solution with cost at most $O(d^{3/2}\log n)\cdot OPT + O(k d^2 \log^2 n / \epsilon^2)$, where $\epsilon$ is the privacy guarantee. (The dimension term, $d$, can be replaced with $O(\log k)$ using standard dimension reduction techniques.) Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical, runs in near-linear, $\tilde{O}(nkd)$, time and scales to tens of millions of points. We also show that our method is amenable to parallelization in large-scale distributed computing environments. In particular we show that our private algorithms can be implemented in logarithmic number of MPC rounds in the sublinear memory regime. Finally, we complement our theoretical analysis with an empirical evaluation demonstrating the algorithm's efficiency and accuracy in comparison to other privacy clustering baselines.
• Abstract（参考訳）: 我々は、次元ユークリッド空間におけるプライベートな$k$-medianおよび$k$-meansクラスタリング問題を研究する。 ツリー埋め込みを利用することで、効率的で実装が容易なアルゴリズムを提供し、そのアルゴリズムは最先端の非プライベートメソッドと実証的に競合する。 提案手法は,最大で$O(d^{3/2}\log n)\cdot OPT + O(k d^2 \log^2 n / \epsilon^2)$で解を計算する。 (次元項 $d$ は標準次元還元法を用いて $o(\log k)$ に置き換えることができる。 ) 最悪の場合の保証は最先端のプライベートクラスタリング手法よりも悪いが、我々が提案するアルゴリズムは実用的であり、ほぼ線形で$\tilde{o}(nkd)$、時間とスケールで数千万ポイントまで動作している。 また,本手法は大規模分散コンピューティング環境での並列化に適していることを示す。 特に、我々のプライベートアルゴリズムは、サブ線形メモリシステムにおけるMPCラウンドの対数で実装可能であることを示す。 最後に、我々の理論解析を、他のプライバシクラスタリングベースラインと比較してアルゴリズムの効率と精度を示す経験的評価で補完する。

関連論文リスト

• Private Geometric Median [10.359525525715421]
  データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。 我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
  論文  参考訳（メタデータ） (2024-06-11T16:13:09Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• 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)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Systematically improving existing k-means initialization algorithms at nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
  PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。 与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
  論文  参考訳（メタデータ） (2022-02-08T15:56:30Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)

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

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