論文の概要: Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

• arxiv url: http://arxiv.org/abs/2607.18846v1
• Date: Tue, 21 Jul 2026 08:35:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-22 19:05:05.358863
• Title: Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers
• Title（参考訳）: スペクトル増幅器によるグラフスペクトルとカットのプライベート近似
• Abstract要約: 本稿では,エッジレベルの差分プライバシーの下で,入力グラフのすべてのカットサイズを近似した合成グラフを公開する問題について検討する。 有界時間 $(varepsilon,)$-differentially private algorithm を与え、これはすべての$n$-vertex 未重み付きグラフ $G$ に対して非負重み付き合成グラフを出力する。
• 参考スコア（独自算出の注目度）: 9.297355862757838
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additive error, the optimal worst-case error is $\widetildeΘ(n^{3/2})$. If one allows a small multiplicative slack, an information-theoretic exponential-time mechanism achieves nearly linear additive error, but the best known polynomial-time algorithms have substantially larger error. We give a polynomial-time $(\varepsilon,δ)$-differentially private algorithm which, for every $n$-vertex unweighted graph $G$, outputs a non-negative weighted synthetic graph $\widetilde G$ such that, with high probability, every cut $S\subseteq V(G)$ satisfies \[ |w_G(S)-w_{\widetilde G}(S)| \le γw_G(S)+\widetilde O_{\varepsilon,δ,γ}(n^{13/12+o(1)}). \] This improves the previous polynomial-time worst-case bound $\widetilde O(n^{5/4+o(1)})$ of Aamand et al. (ICML 2025) for mixed multiplicative/additive private cut approximation. The main technical ingredient is a new set of private spectral primitives for bounded-degree graphs, one of them gives spectral error $\widetilde O_δ((nd)^{1/4}/\sqrt\varepsilon)$ in estimating the graph Laplacian for graphs of maximum degree $d$, being the first to beat the standard $\min\{2d,\widetilde O_δ(\sqrt{n}/\varepsilon)\}$ baseline in the high-degree regime. We further develop a primitive with a sharper error dependence on $n$ and $d$ for the downstream cut approximation. Combined with a new edge-sensitive terminal cut oracle with additive error $\widetilde O(n+(n^2M)^{1/3})$ on graphs with $M$ edges, this yields the final worst-case $\widetilde O(n^{13/12+o(1)})$ private cut-release error.
• Abstract（参考訳）: 本稿では,エッジレベルの差分プライバシーの下で,入力グラフのすべてのカットサイズを近似した合成グラフを公開する問題について検討する。 純粋に加法誤差を主張するなら、最適の最悪のエラーは$\widetilde'(n^{3/2})$である。 もし小さな乗法スラックを許すなら、情報理論の指数時間機構は、ほぼ線形加法誤差を達成するが、最もよく知られた多項式時間アルゴリズムは、かなり大きな誤差を持つ。 多項式時間$(\varepsilon,δ)$-differentially private algorithm which, for every $n$-vertex unweighted graph $G$, outputs a non- negative weighted synthetic graph $\widetilde G$ such as high probability, every cut $S\subseteq V(G)$ satisfies \[|w_G(S)-w_{\widetilde G}(S)| \le γw_G(S)+\widetilde O_{\varepsilon,δ,γ}(n^{13/12+o(1)} を与える。 これは、混合乗算/加算プライベートカット近似のための Aamand et al (ICML 2025) の以前の多項式時間最悪のケース境界$\widetilde O(n^{5/4+o(1)})$を改善します。 主な技術的要素は、有界グラフに対する新しいスペクトル原始集合であり、そのうちの1つはスペクトル誤差 $\widetilde O_δ((nd)^{1/4}/\sqrt\varepsilon)$ を最大次数$d$のグラフに対して推定するときに、標準の $\min\{2d,\widetilde O_δ(\sqrt{n}/\varepsilon)\} を打った最初のグラフである。 さらに、下流のカット近似に対して、$n$と$d$のエラー依存性がより鋭いプリミティブを開発する。 新たなエッジに敏感な端末カットオラクルに加算誤差$\widetilde O(n+(n^2M)^{1/3})$$M$ edgesと組み合わせると、最後の最悪のケース$\widetilde O(n^{13/12+o(1)})$private cut-release errorが得られる。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  我々は,分散レベルと出力レベルの両方でエラーを定量化する,Top-$$ attention truncationという統一フレームワークを開発した。 総偏差距離は捨てられたソフトマックスのテール質量と一致し,$mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$を満たすことを示す。
  論文  参考訳（メタデータ） (2025-12-08T15:36:41Z)
• Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism [5.4971134662997025]
  SVTを多次元ベクトルに一般化する新しい一般化スパースベクトル法を定式化する。 アプリケーションとして、我々は以前よりもバウンダリが良い多くの重要なグラフ問題を解く。 我々は、$O(epsilon-1log n)$加法誤差と$O(n)$ラウンドでの乗算誤差のない$k$コア分解に対して、厳密なローカルエッジDPアルゴリズムを与える。
  論文  参考訳（メタデータ） (2025-08-04T08:26:58Z)
• Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts [3.652509571098291]
  微分プライベート (DP) 合成グラフ $G'$ を、任意のグラフ $G'$ のすべてのカットの三角形-モチーフサイズをよく近似する問題について検討する。 このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。
  論文  参考訳（メタデータ） (2025-07-20T06:20:53Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Differentially Private Gomory-Hu Trees [13.591231541692288]
  我々は,近似Gomory-Hu木を演算する差分プライベート(DP)アルゴリズムを設計する。 我々のアルゴリズムは$varepsilon$-DPであり、時間内で動作し、$tildeO(n/varepsilon)$-additive approximations of the Min-s$-$t$-Cuts in $G$ for all different $s.
  論文  参考訳（メタデータ） (2024-08-03T14:50:03Z)
• Almost linear time differentially private release of synthetic graphs [6.076406622352115]
  本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。 直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。 これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
  論文  参考訳（メタデータ） (2024-06-04T09:44:24Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)

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

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