論文の概要: On the Price of Differential Privacy for Hierarchical Clustering
- arxiv url: http://arxiv.org/abs/2504.15580v1
- Date: Tue, 22 Apr 2025 04:39:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-30 22:25:02.013784
- Title: On the Price of Differential Privacy for Hierarchical Clustering
- Title（参考訳）: 階層クラスタリングにおける微分プライバシーの価格について
- Authors: Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang, Samson Zhou,
- Abstract要約: 本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。
以上の結果から,提案アルゴリズムはコストの面では良好に動作し,大規模グラフに対するスケーラビリティも良好であることがわかった。
- 参考スコア（独自算出の注目度）: 21.64775530337936
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clustering involve sensitive user information, therefore motivating recent studies on differentially private hierarchical clustering under the rigorous framework of Dasgupta's objective. However, it has been shown that any privacy-preserving algorithm under edge-level differential privacy necessarily suffers a large error. To capture practical applications of this problem, we focus on the weight privacy model, where each edge of the input graph is at least unit weight. We present a novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting. In particular, our algorithm achieves $O(\log^{1.5}n/\varepsilon)$ multiplicative error for $\varepsilon$-DP and runs in polynomial time, where $n$ is the size of the input graph, and the cost is never worse than the optimal additive error in existing work. We complement our algorithm by showing if the unit-weight constraint does not apply, the lower bound for weight-level DP hierarchical clustering is essentially the same as the edge-level DP, i.e. $\Omega(n^2/\varepsilon)$ additive error. As a result, we also obtain a new lower bound of $\tilde{\Omega}(1/\varepsilon)$ additive error for balanced sparsest cuts in the weight-level DP model, which may be of independent interest. Finally, we evaluate our algorithm on synthetic and real-world datasets. Our experimental results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.
- Abstract（参考訳）: 階層的クラスタリングは、クラスタの階層構造にデータを整理することを目的とした、基本的な教師なしの機械学習タスクである。
階層的クラスタリングの多くの応用は、センシティブなユーザ情報を含むため、ダシュプタの目的の厳密な枠組みの下で、微分的にプライベートな階層的クラスタリングに関する最近の研究を動機付けている。
しかしながら、エッジレベルの差分プライバシーの下でのプライバシー保護アルゴリズムは、必ず大きなエラーを被ることが示されている。
この問題の現実的な応用を捉えるため、我々は、入力グラフの各エッジが少なくとも単位重みとなる重みプライバシーモデルに焦点をあてる。
本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。
特に、我々のアルゴリズムは$O(\log^{1.5}n/\varepsilon)$乗算誤差を$\varepsilon$-DPで達成し、多項式時間で実行される。
単位重み制約が適用されない場合、重みレベルDP階層的クラスタリングの下位境界は本質的にエッジレベルDPと同じであり、例えば$\Omega(n^2/\varepsilon)$加法誤差である。
結果として、ウェイトレベルDPモデルにおいて、バランスの取れたスペルストカットに対して$\tilde{\Omega}(1/\varepsilon)$加法誤差が新たに得られる。
最後に,本アルゴリズムを合成および実世界のデータセット上で評価する。
実験の結果,提案アルゴリズムはコストの面では良好であり,大規模グラフに対するスケーラビリティも良好であることがわかった。
関連論文リスト
- Private Geometric Median [10.359525525715421]
データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。
我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
論文 参考訳（メタデータ） (2024-06-11T16:13:09Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Improved Analysis of Sparse Linear Regression in Local Differential
Privacy Model [38.66115499136791]
局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。
そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。
その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
論文 参考訳（メタデータ） (2023-10-11T10:34:52Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37: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) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳（メタデータ） (2021-12-07T11:26:41Z) - Differentially Private Federated Learning via Inexact ADMM [0.0]
差分プライバシー(DP)技術は、データプライバシを推論攻撃から保護するために、フェデレーション付き学習モデルに適用することができる。
我々は,信頼領域のサブプロブレム列を解く乗算器アルゴリズムのDP不正確な交互方向法を開発した。
提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも22%削減すると同時に,データプライバシのレベルも同等に向上する。
論文 参考訳（メタデータ） (2021-06-11T02:28:07Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。