論文の概要: Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
- arxiv url: http://arxiv.org/abs/2402.18020v1
- Date: Wed, 28 Feb 2024 03:30:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 06:59:15.592209
- Title: Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
- Title（参考訳）: 地域差分プライベートコア分解法とデンストグラフのためのタイターバウンド
- Authors: Monika Henzinger, A. R. Sricharan, Leqi Zhu,
- Abstract要約: Dhulipalaらは、局所的な差分プライバシーの挑戦的で実践的に関係のある設定において、コア分解を近似するための最初のメカニズムを与えた。
近似的および正確なコア分解機構の加法誤差に関する第1の下位境界を示す。
また、局所モデルにおいて、ほぼ一致する加法誤差境界を持つ完全かつ近似的なコア分解の機構を与える。
- 参考スコア（独自算出の注目度）: 3.9674156047739495
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Computing the core decomposition of a graph is a fundamental problem that has recently been studied in the differentially private setting, motivated by practical applications in data mining. In particular, Dhulipala et al. [FOCS 2022] gave the first mechanism for approximate core decomposition in the challenging and practically relevant setting of local differential privacy. One of the main open problems left by their work is whether the accuracy, i.e., the approximation ratio and additive error, of their mechanism can be improved. We show the first lower bounds on the additive error of approximate and exact core decomposition mechanisms in the centralized and local model of differential privacy, respectively. We also give mechanisms for exact and approximate core decomposition in the local model, with almost matching additive error bounds. Our mechanisms are based on a black-box application of continual counting. They also yield improved mechanisms for the approximate densest subgraph problem in the local model.
- Abstract（参考訳）: グラフのコア分解を計算することは、データマイニングの実践的応用によって動機付けられた微分プライベートな環境で最近研究されている基本的な問題である。
特に、Dhulipala et al [FOCS 2022]は、局所的な差分プライバシーの挑戦的で実践的に関係のある設定において、コア分解を近似するための最初のメカニズムを与えた。
彼らの研究で残された主要な問題の一つは、そのメカニズムの精度、すなわち近似比と加法誤差を改善することができるかどうかである。
偏微分プライバシの集中モデルと局所モデルにおいて、近似的および正確なコア分解機構の加算誤差に関する第1下位境界をそれぞれ示す。
また、局所モデルにおいて、ほぼ一致する加法誤差境界を持つ完全かつ近似的なコア分解の機構を与える。
我々のメカニズムは連続的な数え上げのブラックボックスの応用に基づいている。
また、局所モデルにおける近似的な高密度部分グラフ問題のメカニズムも改善した。
関連論文リスト
- Stability and Generalization of the Decentralized Stochastic Gradient
Descent Ascent Algorithm [80.94861441583275]
本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。
本研究は,D-SGDAの一般化における各因子の影響を解析した。
また、最適凸凹設定を得るために一般化とバランスをとる。
論文 参考訳（メタデータ） (2023-10-31T11:27:01Z) - Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels [10.580858171606167]
入力/出力共分散演算子の固有デカイに依存するスケッチサイズを小さくして、最適に近い速度を得る方法を示す。
提案手法は,非スケッチなメソッドを抽出可能なベンチマークデータセット上で,最先端のパフォーマンスを実現するための拡張性を示す。
論文 参考訳（メタデータ） (2023-02-20T18:00:21Z) - Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the
Large-Composition Regime [12.420941209631742]
本研究では,多数の構成の限界における最適微分プライバシー機構の設計について検討する。
この体制では、最高のプライバシーメカニズムは、Kullback-Leiblerの発散を最小限にするものである。
我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
論文 参考訳（メタデータ） (2022-06-25T20:05:50Z) - ER: Equivariance Regularizer for Knowledge Graph Completion [107.51609402963072]
我々は、新しい正規化器、すなわち等分散正規化器(ER)を提案する。
ERは、頭と尾のエンティティ間の意味的等価性を利用することで、モデルの一般化能力を高めることができる。
実験結果から,最先端関係予測法よりも明確かつ実質的な改善が示された。
論文 参考訳（メタデータ） (2022-06-24T08:18:05Z) - Gromov-Wasserstein Discrepancy with Local Differential Privacy for
Distributed Structural Graphs [7.4398547397969494]
本稿では,グラフニューラルネットワークから学習したノード埋め込みのGW差分を分析するためのプライバシー保護フレームワークを提案する。
我々の実験は,$varilon$-LDPアルゴリズムによって保証される強力なプライバシー保護により,提案フレームワークがグラフ学習におけるプライバシを保存するだけでなく,GW距離下でのノイズ構造指標も提示することを示した。
論文 参考訳（メタデータ） (2022-02-01T23:32:33Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳（メタデータ） (2021-12-07T11:26:41Z) - MIRACLE: Causally-Aware Imputation via Learning Missing Data Mechanisms [82.90843777097606]
欠落データに対する因果認識型計算アルゴリズム(MIRACLE)を提案する。
MIRACLEは、欠落発生機構を同時にモデル化することにより、ベースラインの計算を反復的に洗練する。
我々は、MIRACLEが一貫してイミューテーションを改善することができることを示すために、合成および様々な公開データセットに関する広範な実験を行う。
論文 参考訳（メタデータ） (2021-11-04T22:38:18Z) - Differentially Private Sliced Wasserstein Distance [5.330240017302619]
差分プライバシ(DP)フレームワーク下での分散の分散を計算する観点を考察する。
Sliced Wasserstein Distance に焦点をあてて,DP の勾配型衛生法に代えて根本問題に取り組む。
論文 参考訳（メタデータ） (2021-07-05T08:06:02Z) - Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
多くの機械学習アプリケーションは、2つの競合する目標を達成する表現を学習する。
ミニマックスゲーム理論の定式化は、精度と不変性の基本的なトレードオフを表す。
分類と回帰の双方において,この一般的かつ重要な問題を情報論的に解析する。
論文 参考訳（メタデータ） (2020-12-19T15:24:04Z) - Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
ローカルな見積もりの交換は、プライベートデータに基づくデータの推測を可能にする。
すべてのエージェントで独立して選択された摂動により、パフォーマンスが著しく低下する。
本稿では,特定のヌル空間条件に従って摂動を構成する代替スキームを提案する。
論文 参考訳（メタデータ） (2020-10-23T10:35:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。