論文の概要: Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

• arxiv url: http://arxiv.org/abs/2508.02182v1
• Date: Mon, 04 Aug 2025 08:26:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 13:27:24.953317
• Title: Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
• Title（参考訳）: 多次元AboveThreshold機構による準最適差分グラフアルゴリズム
• Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu,
• Abstract要約: SVTを多次元ベクトルに一般化する新しい一般化スパースベクトル法を定式化する。 アプリケーションとして、我々は以前よりもバウンダリが良い多くの重要なグラフ問題を解く。 我々は、$O(epsilon-1log n)$加法誤差と$O(n)$ラウンドでの乗算誤差のない$k$コア分解に対して、厳密なローカルエッジDPアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 5.4971134662997025
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k$-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of $n$ due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. As an application, we solve a number of important graph problems with better bounds than previous work. We apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including $k$-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge DP algorithm for $k$-core decomposition with $O(\epsilon^{-1}\log n)$ additive error and no multiplicative error in $O(n)$ rounds. We also give a new $(2+\eta)$-factor multiplicative, $O(\epsilon^{-1}\log n)$ additive error algorithm in $O(\log^2 n)$ rounds for any constant $\eta > 0$. Both of these results are asymptotically tight against our new lower bound of $\Omega(\log n)$ for any constant-factor approximation algorithm for $k$-core decomposition. Our new algorithms for $k$-core also directly lead to new algorithms for densest subgraph and low out-degree ordering. Our novel private defective coloring algorithms uses number of colors proportional to the arboricity of the graph.
• Abstract（参考訳）: 多くの微分プライベートおよび古典的非プライベートグラフアルゴリズムは、各頂点のいくつかの性質がしきい値を満たすかどうかを決定することに決定的に依存する。 例えば、$k$-core分解問題の場合、古典的な剥離アルゴリズムは、誘導度がしきい値以下になると頂点を反復的に除去する。 スパースベクター技術(SVT)は一般に、非プライベートなしきい値クエリを、わずかな加算損失の精度でプライベートなものに変換するために用いられる。 しかし、グラフ設定におけるSVTの単純適用は、すべての頂点にSVTを適用するため、合成により$n$の係数でエラーを増幅する。 本稿では,複数次元のベクトルに対してSVTを一般化する多次元AboveThreshold(MAT)機構と呼ばれる,新しい一般化スパースベクトル手法を定式化することによって,この問題を解決する。 アプリケーションとして、我々は以前よりもバウンダリが良い多くの重要なグラフ問題を解く。 我々は MAT 機構を用いて,$k$-core 分解,高密度部分グラフ,低外秩序化,頂点カラー化など,様々な問題に対する改善された境界値の集合を求める。 我々は、$O(\epsilon^{-1}\log n)$加法誤差と$O(n)$ラウンドでの乗法誤差のない$k$コア分解に対して、厳密なローカルエッジDPアルゴリズムを与える。 また、新しい$(2+\eta)$-factor乗法、$O(\epsilon^{-1}\log n)$ additive error algorithm in $O(\log^2 n)$ rounds for any constant $\eta > 0$を与える。 これらの結果は、fk$-core分解に対する任意の定数係数近似アルゴリズムに対して、新しい下限の$\Omega(\log n)$に対して漸近的に厳密である。 当社の$k$-coreの新しいアルゴリズムは、高密度なサブグラフと低外度順序付けのための新しいアルゴリズムにも直接結びついています。 グラフの空白度に比例した色数を利用する。

関連論文リスト

• Robust random graph matching in Gaussian models via vector approximate message passing [0.0]
  我々は,n1-o(1)$の任意の逆摂動の下で頑健な効率的なランダムグラフマッチング型アルゴリズムを提案する。 我々のアルゴリズムは,n1-o(1)$の任意の逆摂動の下で頑健な,最初の効率的なランダムグラフマッチング型アルゴリズムである。
  論文  参考訳（メタデータ） (2024-12-21T03:15:38Z)
• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。 具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
  論文  参考訳（メタデータ） (2024-08-21T01:39:42Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。 我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。 我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
  論文  参考訳（メタデータ） (2023-06-23T01:28:24Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。 我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
  論文  参考訳（メタデータ） (2021-12-15T03:45:39Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• 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)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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