論文の概要: Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds
- arxiv url: http://arxiv.org/abs/2605.15943v1
- Date: Fri, 15 May 2026 13:27:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-18 21:22:26.29313
- Title: Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds
- Title（参考訳）: 確率ブロックモデルにおけるノードプライベートなコミュニティ推定:トラクタブルアルゴリズムと下界
- Authors: Laurentiu Marchis, Ethan D'souza, Tomáš Flídr, Po-Ling Loh,
- Abstract要約: 一定数のコミュニティを持つブロックモデルにおいて,コミュニティ回復の古典的問題を考察する。
グラフ構造におけるノードワイズ変化に対して安定なアルゴリズムを探索し,差分プライバシー制約として正式に定義する。
- 参考スコア（独自算出の注目度）: 4.001518483170137
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the classical problem of community recovery in stochastic block models with a fixed number of communities, with a twist: We seek algorithms that are stable with respect to node-wise changes in the graph structure, formally defined as a differential privacy constraint. The algorithms we develop are based on spectral clustering, where we introduce privacy to the community recovery pipeline in the form of directly privatizing the adjacency matrix; private PCA; private convex optimization; private low-rank matrix estimation; and private approximate subspace estimation. Straightforward applications of existing private algorithms lead to a rapid increase in the privacy parameter $ε$ in order to ensure consistent estimation under node differential privacy, in contrast with the simpler setting of edge privacy. To alleviate these issues, we develop novel algorithms based on (1) sampling from an exponential mechanism with a Lipschitz extension and (2) a general framework for constructing smooth projections from the space of undirected graphs to the space of bounded-degree graphs, which can then be combined with various edge-private algorithms. Importantly, the methods we develop are all computable in polynomial-time as a function of the number of nodes in the graph. We also develop novel lower bounds on the growth rate of $ε$ required in order to achieve consistent community estimation under node privacy. On a technical note, our paper highlights the complications that arise when analyzing private algorithms under the non-standard scaling $ε\rightarrow \infty$ and proposes some solutions. We also provide a novel application of the HGR maximal correlation from information theory in the context of accuracy amplification in PAC learning, which may be of independent interest.
- Abstract（参考訳）: グラフ構造におけるノードワイズ変化に対して安定なアルゴリズムを求めるが、これは正式には差分プライバシー制約として定義される。
そこでは,隣接行列を直接民営化する手法,プライベートPCA,プライベート凸最適化,プライベート低ランク行列推定,プライベート近似部分空間推定という形で,コミュニティリカバリパイプラインにプライバシを導入する。
既存のプライベートアルゴリズムのストレートフォワード適用は、エッジプライバシのより単純な設定とは対照的に、ノード差分プライバシの下で一貫した推定を保証するために、プライバシパラメータのε$を急速に増加させる。
これらの問題を緩和するために、(1)リプシッツ拡張を用いた指数関数機構からのサンプリングと(2)無向グラフの空間から有界グラフの空間への滑らかな射影を構築するための一般的な枠組みに基づく新しいアルゴリズムを開発し、それを様々なエッジプライベートなアルゴリズムと組み合わせることができる。
重要なことに、我々が開発する手法はすべて、グラフ内のノード数の関数として多項式時間で計算可能である。
また、ノードプライバシの下で一貫したコミュニティ推定を達成するために、必要な$ε$の成長率に関する新たな低い限界も開発する。
技術的には、非標準スケーリング$ε\rightarrow \infty$の下でプライベートアルゴリズムを解析する際に生じる複雑さを強調し、いくつかの解決策を提案する。
また,PAC学習における精度増幅の文脈における情報理論からのHGR最大相関の新たな応用について述べる。
関連論文リスト
- Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。
本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。
このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
論文 参考訳（メタデータ） (2026-02-12T17:49:07Z) - Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits [0.8122270502556375]
シャッフル差分プライバシーと連立差分プライバシーに基づく一般化線形文脈帯域のアルゴリズムを提案する。
逆の文脈では、$tildeO(dsqrtT/sqrtvarepsilon)$ regret というジョイントDPアルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-01-31T00:15:20Z) - Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
エッジ差分プライバシー(DP)下におけるスペクトルグラフクラスタリングの問題点について検討する。
具体的には, (i) エッジフリップによるグラフ摂動と, エッジプライバシを強制する隣接行列シャッフルを併用したグラフ摂動, (ii) 次元と複雑性の複雑さを低減するために低次元空間における加法的ガウス雑音を伴うプライベートグラフプロジェクション, (iii) 収束性を維持しながらエッジDPを確保するために反復的にガウス雑音を分散するノイズの多いパワーイテレーション手法である。
論文 参考訳（メタデータ） (2025-10-08T15:30:27Z) - Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
コンテキストによるカーネルの帯域幅の問題について考察する。
基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。
我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-18T03:54:49Z) - Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。
最適率を達成するための情報重み付け回帰手法を提案する。
特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
論文 参考訳（メタデータ） (2025-02-18T18:35:24Z) - Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。
微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。
これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-02-13T02:05:45Z) - Dynamic Privacy Allocation for Locally Differentially Private Federated
Learning with Composite Objectives [10.528569272279999]
本稿では,強い凸性を持つが非滑らかな問題に対する差分プライベートなフェデレーション学習アルゴリズムを提案する。
提案アルゴリズムは、共有情報に人工ノイズを加えてプライバシーを確保するとともに、時間変化のノイズ分散を動的に割り当て、最適化誤差の上限を最小化する。
解析結果から,提案手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2023-08-02T13:30:33Z) - Differentially Private Domain Adaptation with Theoretical Guarantees [46.37771025567305]
多くのアプリケーションでは、ラベル付きデータの処分におけるラベル付きデータはプライバシー上の制約を受けており、比較的制限されている。
これは、パブリックソースからプライベートターゲットドメインへのドメイン適応を監督する現代の問題である。
我々は、理論的な学習保証の恩恵を受けるために、一般の学習者を利用する。
論文 参考訳（メタデータ） (2023-06-15T04:03:06Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。
均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。
我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
論文 参考訳（メタデータ） (2021-02-24T18:52:24Z) - Differentially Private Correlation Clustering [23.93805663525436]
相関クラスタリングは教師なし機械学習で広く使われている手法である。
個人のプライバシーが懸念されるアプリケーションに動機づけられて、微分プライベート相関クラスタリングの研究を開始します。
論文 参考訳（メタデータ） (2021-02-17T17:27:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。