論文の概要: Near-Optimal Differentially Private k-Core Decomposition
- arxiv url: http://arxiv.org/abs/2312.07706v2
- Date: Thu, 29 Feb 2024 03:22:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 12:26:52.789641
- Title: Near-Optimal Differentially Private k-Core Decomposition
- Title（参考訳）: 準最適微分プライベートkコア分解
- Authors: Laxman Dhulipala, George Z. Li, Quanquan C. Liu,
- Abstract要約: 我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。
これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
- 参考スコア（独自算出の注目度）: 2.859324824091086
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the $k$-core decomposition problem under differential privacy via a connection between low round/depth distributed/parallel graph algorithms and private algorithms with small error bounds. They showed that one can output differentially private approximate $k$-core numbers, while only incurring a multiplicative error of $(2 +\eta)$ (for any constant $\eta >0$) and additive error of $\poly(\log(n))/\eps$. In this paper, we revisit this problem. Our main result is an $\eps$-edge differentially private algorithm for $k$-core decomposition which outputs the core numbers with no multiplicative error and $O(\text{log}(n)/\eps)$ additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error. Our result relies on a novel generalized form of the sparse vector technique, which is especially well-suited for threshold-based graph algorithms; thus, we further strengthen the connection between distributed/parallel graph algorithms and differentially private algorithms.
- Abstract（参考訳）: Dhulipala et al \cite{DLRSSY22} による最近の研究は、低ラウンド/ディープス分散/並列グラフアルゴリズムと小さなエラー境界を持つプライベートアルゴリズムとの接続を通じて、差分プライバシー下での$k$-core分解問題の研究を開始した。
彼らは、差分的にプライベートな$k$-core数値を出力できるが、乗法誤差は$(2 +\eta)$(任意の定数$\eta > 0$)と加法誤差は$\poly(\log(n))/\eps$だけであることを示した。
本稿では,この問題を再考する。
我々の主な結果は、$k$-core分解のための$\eps$-edge差分秘密アルゴリズムであり、乗法誤差のないコア番号と$O(\text{log}(n)/\eps)$加法誤差を出力する。
これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
この結果は、特に閾値グラフアルゴリズムに適したスパースベクトル手法の新たな一般化形式に依存しており、分散/並列グラフアルゴリズムと微分プライベートアルゴリズムとの接続をさらに強化する。
関連論文リスト
- Differentially Private Multiway and $k$-Cut [5.893651469750359]
我々は,最小$k$カットおよびマルチウェイカット問題に対して,ほぼ最適な性能を実現する,エッジ微分プライベートアルゴリズムを導入する。
最小$k$-cut問題に対して、我々のアルゴリズムは、近似$k$-cutの個数に対する既知のバウンダリを活用し、固定プライバシーパラメータに対して最適な加算誤差$O(klog n)$のプライベートアルゴリズムを実現する。
論文 参考訳（メタデータ） (2024-07-09T14:46:33Z) - On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳（メタデータ） (2024-06-24T04:06:09Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - 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 Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
我々は、点の挿入と削除の両方を行う$mathbbRd$のデータセットをプライベートにクラスタリングする問題を考える。
連続観測において、$k$-meansの目的に対して、$varepsilon$-differentially private clustering 機構を提供する。
論文 参考訳（メタデータ） (2023-07-07T07:23:56Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。