Fugu-MT 論文翻訳(概要): Better Private Algorithms for Correlation Clustering

論文の概要: Better Private Algorithms for Correlation Clustering

arxiv url: http://arxiv.org/abs/2202.10747v1
Date: Tue, 22 Feb 2022 09:05:08 GMT
ステータス: 処理完了
システム内更新日: 2022-02-23 16:53:54.798907
Title: Better Private Algorithms for Correlation Clustering
Title（参考訳）: 相関クラスタリングのためのより良いプライベートアルゴリズム
Authors: Daogao Liu
Abstract要約: 差分プライバシー制約の下で相関クラスタリングを再検討する。一般グラフ上での予測の最適コストと比較して,$TildeO(n1.5)$加法誤差を実現する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In machine learning, correlation clustering is an important problem whose goal is to partition the individuals into groups that correlate with their pairwise similarities as much as possible. In this work, we revisit the correlation clustering under the differential privacy constraints. Particularly, we improve previous results and achieve an $\Tilde{O}(n^{1.5})$ additive error compared to the optimal cost in expectation on general graphs. As for unweighted complete graphs, we improve the results further and propose a more involved algorithm which achieves $\Tilde{O}(n \sqrt{\Delta^*})$ additive error, where $\Delta^*$ is the maximum degrees of positive edges among all nodes.
Abstract（参考訳）: 機械学習において、相関クラスタリングは、個人を可能な限りペアの類似性と相関するグループに分割することを目的とする重要な問題である。本研究では,差分プライバシー制約下での相関クラスタリングを再検討する。特に、一般的なグラフ上での予測の最適コストと比較して、以前の結果を改善し、$\Tilde{O}(n^{1.5})$加法誤差を達成する。非重みのない完全グラフについては、さらに改良を行い、より複雑なアルゴリズムを提案し、全てのノードの正の辺の最大度を$\Tilde{O}(n \sqrt{\Delta^*})$加法誤差とする。

関連論文リスト

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)
Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
論文参考訳（メタデータ） (2023-12-12T20:09:07Z)
Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文参考訳（メタデータ） (2023-05-28T15:33:24Z)
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)
The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文参考訳（メタデータ） (2021-10-20T23:46:35Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Differentially Private Correlation Clustering [23.93805663525436]
相関クラスタリングは教師なし機械学習で広く使われている手法である。個人のプライバシーが懸念されるアプリケーションに動機づけられて、微分プライベート相関クラスタリングの研究を開始します。
論文参考訳（メタデータ） (2021-02-17T17:27:48Z)
Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-02-28T04:21:53Z)
Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文参考訳（メタデータ） (2020-02-26T16:19:09Z)
Query-Efficient Correlation Clustering [13.085439249887713]
相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
論文参考訳（メタデータ） (2020-02-26T15:18:20Z)

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