論文の概要: Approximate DBSCAN under Differential Privacy

• arxiv url: http://arxiv.org/abs/2508.08749v2
• Date: Wed, 13 Aug 2025 14:25:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-14 14:06:00.575992
• Title: Approximate DBSCAN under Differential Privacy
• Title（参考訳）: 微分プライバシー下における近似DBSCAN
• Authors: Yuan Qiu, Ke Yi,
• Abstract要約: 本稿では、差分プライバシー(DP)の下でのDBSCAN問題を再考する。 既存のDP-DBSCANアルゴリズムは、入力点のクラスタラベルを公開することを目的としている。 本研究では,スパンの概念に基づくDP-DBSCANの代替定義を提案する。
• 参考スコア（独自算出の注目度）: 16.142659947559903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper revisits the DBSCAN problem under differential privacy (DP). Existing DP-DBSCAN algorithms aim at publishing the cluster labels of the input points. However, we show that both empirically and theoretically, this approach cannot offer any utility in the published results. We therefore propose an alternative definition of DP-DBSCAN based on the notion of spans. We argue that publishing the spans actually better serves the purposes of visualization and classification of DBSCAN. Then we present a linear-time DP-DBSCAN algorithm achieving the sandwich quality guarantee in any constant dimensions, as well as matching lower bounds on the approximation ratio. A key building block in our algorithm is a linear-time algorithm for constructing a histogram under pure-DP, which is of independent interest. Finally, we conducted experiments on both synthetic and real-world datasets to verify the practical performance of our DP-DBSCAN algorithm.
• Abstract（参考訳）: 本稿では、差分プライバシー(DP)の下でのDBSCAN問題を再検討する。 既存のDP-DBSCANアルゴリズムは、入力点のクラスタラベルを公開することを目的としている。 しかし、実証的・理論的に、この手法は公表された結果には何の効用も与えないことを示す。 そこで本研究では,スパンの概念に基づくDP-DBSCANの代替定義を提案する。 我々は,DBSCANの可視化と分類のために,スパンの公開が有効であると主張している。 次に,一定次元のサンドイッチ品質保証を実現する線形時間DP-DBSCANアルゴリズムを提案する。 提案アルゴリズムのキービルディングブロックは,Pure-DPの下でヒストグラムを構築する線形時間アルゴリズムである。 最後に、DP-DBSCANアルゴリズムの実用性能を検証するために、合成データセットと実世界のデータセットの両方で実験を行った。

関連論文リスト

• Differentially Private Random Block Coordinate Descent [51.62669821275571]
  スケッチ行列を用いて各反復における確率の異なる複数の座標を選択する差分プライベートな座標降下法を提案する。 提案アルゴリズムはDP-CDと従来のDP-SGDの両方を一般化し,有効性を保証する。
  論文  参考訳（メタデータ） (2024-12-22T15:06:56Z)
• CURATE: Scaling-up Differentially Private Causal Graph Discovery [8.471466670802817]
  因果グラフ発見(CGD)におけるユーザのプライバシを確保するために、差分プライバシー(DP)が採用されている。 CURATEは、適応的なプライバシー予算を持つDP-CGDフレームワークである。 CURATEは従来のDP-CGDアルゴリズムに比べてプライバシー保護の少ない高効率を実現していることを示す。
  論文  参考訳（メタデータ） (2024-09-27T18:00:38Z)
• Synthesizing Tight Privacy and Accuracy Bounds via Weighted Model Counting [5.552645730505715]
  2つの中核的な課題は、DPアルゴリズムの分布の表現的でコンパクトで効率的な符号化を見つけることである。 プライバシーと正確性に縛られた合成法を開発することで、最初の課題に対処する。 DPアルゴリズムに固有の対称性を活用するためのフレームワークを開発する。
  論文  参考訳（メタデータ） (2024-02-26T19:29:46Z)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) を使用して、差分プライバシ(DP)がモデルパフォーマンス劣化の犠牲となることを保証する。 DPSGD-GCに代わる新しいエラーフィードバック(EF)DPアルゴリズムを提案する。 提案アルゴリズムに対するアルゴリズム固有のDP解析を確立し,R'enyi DPに基づくプライバシ保証を提供する。
  論文  参考訳（メタデータ） (2023-11-24T17:56:44Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Differentially Private Federated Learning via Inexact ADMM with Multiple Local Updates [0.0]
  我々は,複数の局所的な更新を施した乗算器アルゴリズムのDP不正確な交互方向法を開発した。 当社のアルゴリズムでは,各イテレーション毎に$barepsilon$-DPを提供しており,$barepsilon$はユーザが管理するプライバシ予算である。 提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも31%削減すると同時に,データプライバシのレベルが同じであることを実証する。
  論文  参考訳（メタデータ） (2022-02-18T19:58:47Z)
• Differentially Private Federated Learning via Inexact ADMM [0.0]
  差分プライバシー(DP)技術は、データプライバシを推論攻撃から保護するために、フェデレーション付き学習モデルに適用することができる。 我々は,信頼領域のサブプロブレム列を解く乗算器アルゴリズムのDP不正確な交互方向法を開発した。 提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも22%削減すると同時に,データプライバシのレベルも同等に向上する。
  論文  参考訳（メタデータ） (2021-06-11T02:28:07Z)
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times [51.61278695776151]
  フェデレートラーニング(FL)は、分散クライアント間で機械学習モデルを協調的にトレーニングする際のプライバシ保護でよく知られている。 最近の研究では、naive flは勾配リーク攻撃の影響を受けやすいことが指摘されている。 ディファレンシャルプライバシ(dp)は、勾配漏洩攻撃を防御するための有望な対策として現れる。
  論文  参考訳（メタデータ） (2021-01-11T19:43:12Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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