論文の概要: Making Old Things New: A Unified Algorithm for Differentially Private Clustering
- arxiv url: http://arxiv.org/abs/2406.11649v1
- Date: Mon, 17 Jun 2024 15:31:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-18 14:03:05.494594
- Title: Making Old Things New: A Unified Algorithm for Differentially Private Clustering
- Title（参考訳）: 古いものを新しくする: 差分的プライベートクラスタリングのための統一アルゴリズム
- Authors: Max Dupré la Tour, Monika Henzinger, David Saulpic,
- Abstract要約: 20年前のアルゴリズムは、いずれのモデルでも、わずかに修正可能であることを示す。
これは統一された図を提供する: ほとんどすべての既知結果とマッチングする一方で、いくつかの改善を可能にします。
- 参考スコア（独自算出の注目度）: 6.320600791108065
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithms: the landscape of private clustering algorithms is therefore quite intricate. In this paper, we show that a 20-year-old algorithm can be slightly modified to work for any of these models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them and extend it to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.
- Abstract（参考訳）: データ分析と教師なし学習の基盤として、プライベートクラスタリングの問題は、様々なプライバシモデルの下で広く研究されている。
偏微分プライバシーが最初の問題であり、局所的およびシャッフル変動についても研究されている。
それぞれのケースで目標は、最小限のエラーでクラスタリングをプライベートに計算するアルゴリズムを設計することである。
それぞれのバリエーションの研究は、新しいアルゴリズムを生み出した: プライベートクラスタリングアルゴリズムの展望は、非常に複雑である。
本稿では,これらのモデルに対して,20年前のアルゴリズムをわずかに修正できることを示す。
これは、ほとんどすべての既知結果と一致しながら、そのいくつかを改善して、新たなプライバシモデル、連続的な監視設定、入力が時間とともに変化している場合、アルゴリズムが各ステップで新しいソリューションを出力しなければならない、という、統一されたイメージを提供する。
関連論文リスト
- Differential privacy and Sublinear time are incompatible sometimes [12.776401866635844]
片方向境界に基づく単純な問題は、差分プライベートアルゴリズムとサブ線形時間アルゴリズムの両方をもたらすことを示す。
我々は、微分プライベートである厳密な'サブ線形時間アルゴリズムを認めない。
論文 参考訳（メタデータ） (2024-07-09T22:33:57Z) - 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) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳（メタデータ） (2022-12-06T12:42:11Z) - Stochastic Differentially Private and Fair Learning [7.971065005161566]
我々は、収束することが保証されるフェアラーニングのための最初の微分プライベートアルゴリズムを提供する。
われわれのフレームワークは、人口格差や均等化オッズなど、さまざまな公平さを許容できるほど柔軟である。
本アルゴリズムは,複数の(非バイナリ)機密属性を持つ非バイナリ分類タスクに適用可能である。
論文 参考訳（メタデータ） (2022-10-17T06:54:57Z) - Differentially Private Correlation Clustering [23.93805663525436]
相関クラスタリングは教師なし機械学習で広く使われている手法である。
個人のプライバシーが懸念されるアプリケーションに動機づけられて、微分プライベート相関クラスタリングの研究を開始します。
論文 参考訳（メタデータ） (2021-02-17T17:27:48Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳（メタデータ） (2020-09-15T17:28:42Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms [95.73230376153872]
本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。
我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。
次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
論文 参考訳（メタデータ） (2020-07-18T09:12:03Z) - Differentially Private k-Means Clustering with Guaranteed Convergence [5.335316436366718]
反復的なクラスタリングアルゴリズムは、データの背後にある洞察を学習するのに役立ちます。
敵は、背景知識によって個人のプライバシーを推測することができる。
このような推論攻撃に対して個人のプライバシを保護するため、反復クラスタリングアルゴリズムの差分プライバシー(DP)を広く研究している。
論文 参考訳（メタデータ） (2020-02-03T22:53:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。