論文の概要: Near-optimal node-private community estimation in polynomial-time
- arxiv url: http://arxiv.org/abs/2607.09441v1
- Date: Fri, 10 Jul 2026 14:12:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-13 14:47:12.85867
- Title: Near-optimal node-private community estimation in polynomial-time
- Title（参考訳）: 多項式時間における準最適ノードプライベートコミュニティ推定
- Abstract要約: ブロックモデルの正確な回復のために,Klopp & Zadik の指数時間ノードプライベートアルゴリズムとほぼ一致した高確率ノードプライベートアルゴリズムを提案する。
提案アルゴリズムのプライバシ,ランタイム,ユーティリティを厳密に分析し,コミュニティの数がノード数nと対数的に増加する場合でも,プライバシパラメータepsがlog(n)として増加することで,正確なリカバリの最小値を達成することができることを示した。
- 参考スコア（独自算出の注目度）: 9.8953002257286
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we resolve an open question of Klopp & Zadik (2026) by providing a high-probability polynomial-time, node-private algorithm which nearly matches the performance of their exponential-time node-private algorithm for exact recovery in stochastic block models. Our result involves an explicitly constructed Lipschitz surrogate for the penalized likelihood function, as well as a carefully devised accept-reject algorithm that samples community labels from the corresponding exponential mechanism in polynomial-time. We rigorously analyze the privacy, runtime, and utility of our proposed algorithm, showing that even when the number of communities K grows logarithmically with the number of nodes n, we can achieve the minimax rates for exact recovery with the privacy parameter epsilon growing as log(n), thus matching known lower bounds on the cost of privacy for this setting.
- Abstract（参考訳）: 本稿では,確率ブロックモデルにおける正確な回復のための指数時間ノードプライベートアルゴリズムの性能とほぼ一致する高確率多項式時間ノードプライベートアルゴリズムを提供することにより,Klopp & Zadik (2026) のオープンな問題を解決する。
この結果は, ペナル化確率関数に対して明示的に構築されたリプシッツサロゲートと, 多項式時間で対応する指数的機構からコミュニティラベルをサンプリングする, 慎重に考案されたアセプション・リジェクトアルゴリズムを含む。
我々は,提案アルゴリズムのプライバシ,ランタイム,ユーティリティを厳密に分析し,コミュニティ数Kがノード数nと対数的に増加する場合でも,プライバシパラメータのエプシロンがlog(n)として増加することにより,プライバシパラメータの最小値が得られることを示す。
関連論文リスト
- Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds [4.001518483170137]
一定数のコミュニティを持つブロックモデルにおいて,コミュニティ回復の古典的問題を考察する。
グラフ構造におけるノードワイズ変化に対して安定なアルゴリズムを探索し,差分プライバシー制約として正式に定義する。
論文 参考訳（メタデータ） (2026-05-15T13:27:24Z) - Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。
アルゴリズムは任意の外れ値の小さな部分に対して頑健であり、外れ値の小さな部分の関数として最適誤差率を達成する。
論文 参考訳（メタデータ） (2025-03-31T17:08:12Z) - Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。
微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。
これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-02-13T02:05:45Z) - Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust [5.037313459134419]
本稿では,ErdHos-R'enyiランダムグラフのエッジ密度を推定するアルゴリズムについて述べる。
我々は,アルゴリズムの誤り率を対数的因子まで最適とする情報理論的下界を証明した。
論文 参考訳（メタデータ） (2024-05-26T18:59:44Z) - Private graphon estimation via sum-of-squares [10.00024942014117]
ブロックモデルを学習し,任意のブロックに対して一定の実行時間でグラフトン推定を行うための,最初の純粋ノード微分プライベートアルゴリズムを開発した。
統計的ユーティリティは、これらの問題に対する以前の最良の情報理論(指数時間)ノードプライドメカニズムのそれと一致することを保証している。
論文 参考訳（メタデータ） (2024-03-18T19:54:59Z) - 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) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
本研究は,局所的差分プライバシー(LDP)の制約の下で,集団平均の非パラメトリック,非漸近的統計的推測を行う手法を導出する。
民営化データへのアクセスのみを与えられた場合、$mustar$に対して信頼区間(CI)と時間一様信頼シーケンス(CS)を提示する。
論文 参考訳（メタデータ） (2022-02-17T16:04:49Z) - No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。
均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。
我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
論文 参考訳（メタデータ） (2021-02-24T18:52:24Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。