論文の概要: Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees
- arxiv url: http://arxiv.org/abs/2302.00037v2
- Date: Tue, 23 May 2023 22:10:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 02:10:22.777095
- Title: Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees
- Title（参考訳）: 確率近似保証を用いた微分原始階層クラスタリング
- Authors: Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad,
Vahab Mirrokni
- Abstract要約: 階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 79.59010418610625
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hierarchical Clustering is a popular unsupervised machine learning method
with decades of history and numerous applications. We initiate the study of
differentially private approximation algorithms for hierarchical clustering
under the rigorous framework introduced by (Dasgupta, 2016). We show strong
lower bounds for the problem: that any $\epsilon$-DP algorithm must exhibit
$O(|V|^2/ \epsilon)$-additive error for an input dataset $V$. Then, we exhibit
a polynomial-time approximation algorithm with $O(|V|^{2.5}/
\epsilon)$-additive error, and an exponential-time algorithm that meets the
lower bound. To overcome the lower bound, we focus on the stochastic block
model, a popular model of graphs, and, with a separation assumption on the
blocks, propose a private $1+o(1)$ approximation algorithm which also recovers
the blocks exactly. Finally, we perform an empirical study of our algorithms
and validate their performance.
- Abstract（参考訳）: 階層的クラスタリング(Hierarchical Clustering)は、数十年の歴史と多数のアプリケーションを持つ、一般的な教師なし機械学習手法である。
我々は(dasgupta, 2016) によって導入された厳密な枠組みの下で階層的クラスタリングのための微分プライベート近似アルゴリズムの研究を開始する。
任意の$\epsilon$-DPアルゴリズムは入力データセットの$V$に対して$O(|V|^2/ \epsilon)$-additiveエラーを示さなければならない。
次に,$O(|V|^{2.5}/ \epsilon)$-additiveエラーを用いた多項式時間近似アルゴリズムと,下界を満たす指数時間アルゴリズムを示す。
下限を克服するために、グラフの一般的なモデルである確率的ブロックモデルに焦点をあて、ブロックを分離仮定して、ブロックを正確に復元するプライベートな1+o(1)$近似アルゴリズムを提案する。
最後に,アルゴリズムの実証的研究を行い,その性能を検証した。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - 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) - 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) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。
我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
論文 参考訳（メタデータ） (2021-11-25T09:31:15Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。