論文の概要: Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling

• arxiv url: http://arxiv.org/abs/2510.11640v1
• Date: Mon, 13 Oct 2025 17:20:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:30.476689
• Title: Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
• Title（参考訳）: デンストグラフの連続的リリース: サブサンプリングによるプライバシ増幅とサブリニア空間
• Authors: Felix Zhou,
• Abstract要約: エッジ微分プライベート(DP)グラフアルゴリズムのサブ線形空間連続リリースモデルについて検討する。 我々の主な成果は、最高の静的DPアルゴリズムの加算誤差と一致する最初の連続リリースDSGアルゴリズムである。 グラフDP設定にグラフの密度化を導入し、エッジを追加して初期サブサンプリングをトリガーし、事前の作業によって生じる誤差や空間の余分な対数要素を除去する。
• 参考スコア（独自算出の注目度）: 2.0607844057825324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms, with a focus on the densest subgraph problem (DSG) in the insertion-only setting. Our main result is the first continual release DSG algorithm that matches the additive error of the best static DP algorithms and the space complexity of the best non-private streaming algorithms, up to constants. The key idea is a refined use of subsampling that simultaneously achieves privacy amplification and sparsification, a connection not previously formalized in graph DP. Via a simple black-box reduction to the static setting, we obtain both pure and approximate-DP algorithms with $O(\log n)$ additive error and $O(n\log n)$ space, improving both accuracy and space complexity over the previous state of the art. Along the way, we introduce graph densification in the graph DP setting, adding edges to trigger earlier subsampling, which removes the extra logarithmic factors in error and space incurred by prior work [ELMZ25]. We believe this simple idea may be of independent interest.
• Abstract（参考訳）: 本稿では,挿入専用設定における高密度部分グラフ問題(DSG)に着目し,エッジ微分プライベートグラフアルゴリズムのサブ線形空間連続リリースモデルについて検討する。 我々の主な成果は、最高の静的DPアルゴリズムの加算誤差と、最高の非プライベートストリーミングアルゴリズムの空間複雑さとを一致させる、最初の連続リリースDSGアルゴリズムである。 鍵となる考え方は、プライバシーの増幅とスパース化を同時に達成するサブサンプリングの洗練された利用である。 静的設定に単純なブラックボックス還元を適用すれば、$O(\log n)$加法誤差と$O(n\log n)$空間を持つ純粋および近似DPアルゴリズムが得られ、従来の最先端よりも精度と空間の複雑さが向上する。 その過程で,グラフDP設定にグラフの密度化を導入し,先行処理による誤差や空間の余分な対数要素を除去するエッジを付加する。 私たちは、この単純なアイデアは独立した関心事かもしれないと信じています。

関連論文リスト

• On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
  本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。 以上の結果から,提案アルゴリズムはコストの面では良好に動作し,大規模グラフに対するスケーラビリティも良好であることがわかった。
  論文  参考訳（メタデータ） (2025-04-22T04:39:40Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches [12.184984662899868]
  相関凸最適化(SCO)問題を再考する。 DP-SCO(ポリログ因子まで)の最適速度を1つのエポックで達成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-04T18:59:42Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。