論文の概要: Faster Private Minimum Spanning Trees

• arxiv url: http://arxiv.org/abs/2408.06997v1
• Date: Tue, 13 Aug 2024 16:00:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-14 16:55:31.512303
• Title: Faster Private Minimum Spanning Trees
• Title（参考訳）: より高速なプライベート最小スパンニングツリー
• Authors: Rasmus Pagh, Lukas Retschmeier,
• Abstract要約: 本稿では,時間内で動作中の既存手法の実用性に適合する新しい差分プライベートMSTアルゴリズムを提案する。 我々は,少なくとも$O(n2)$カットエッジを$O(sqrtn log n)$ timeでサンプリングすることのできるデータ構造を示す。
• 参考スコア（独自算出の注目度）: 11.72102598708538
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Motivated by applications in clustering and synthetic data generation, we consider the problem of releasing a minimum spanning tree (MST) under edge-weight differential privacy constraints where a graph topology $G=(V,E)$ with $n$ vertices and $m$ edges is public, the weight matrix $\vec{W}\in \mathbb{R}^{n \times n}$ is private, and we wish to release an approximate MST under $\rho$-zero-concentrated differential privacy. Weight matrices are considered neighboring if they differ by at most $\Delta_\infty$ in each entry, i.e., we consider an $\ell_\infty$ neighboring relationship. Existing private MST algorithms either add noise to each entry in $\vec{W}$ and estimate the MST by post-processing or add noise to weights in-place during the execution of a specific MST algorithm. Using the post-processing approach with an efficient MST algorithm takes $O(n^2)$ time on dense graphs but results in an additive error on the weight of the MST of magnitude $O(n^2\log n)$. In-place algorithms give asymptotically better utility, but the running time of existing in-place algorithms is $O(n^3)$ for dense graphs. Our main result is a new differentially private MST algorithm that matches the utility of existing in-place methods while running in time $O(m + n^{3/2}\log n)$ for fixed privacy parameter $\rho$. The technical core of our algorithm is an efficient sublinear time simulation of Report-Noisy-Max that works by discretizing all edge weights to a multiple of $\Delta_\infty$ and forming groups of edges with identical weights. Specifically, we present a data structure that allows us to sample a noisy minimum weight edge among at most $O(n^2)$ cut edges in $O(\sqrt{n} \log n)$ time. Experimental evaluations support our claims that our algorithm significantly improves previous algorithms either in utility or running time.
• Abstract（参考訳）: クラスタリングや合成データ生成のアプリケーションによって動機付けられ、グラフトポロジーが$G=(V,E)$と$m$ edgeがパブリックで、重量行列が$\vec{W}\in \mathbb{R}^{n \times n}$がプライベートである場合、エッジウェイトな差分プライバシー制約の下で最小スパンニングツリー(MST)をリリースする問題を考える。 ウェイト行列は、各エントリにおいて少なくとも$\Delta_\infty$で異なる場合、すなわち、$\ell_\infty$隣り合う関係を考えると、隣人と見なされる。 既存のプライベートMSTアルゴリズムは、$\vec{W}$で各エントリにノイズを付加し、後処理によってMSTを推定するか、特定のMSTアルゴリズムの実行中に重みにノイズを付加する。 効率的なMSTアルゴリズムを用いた後処理アプローチでは、高密度グラフ上では$O(n^2)$時間を要するが、MSTの重みの加算誤差は$O(n^2\log n)$になる。 インプレースアルゴリズムは漸近的に優れているが、既存のインプレースアルゴリズムの実行時間は密度グラフに対して$O(n^3)$である。 我々の主な成果は、固定プライバシパラメータ$\rho$に対して、時間$O(m + n^{3/2}\log n)$を実行しながら、既存のインプレースメソッドのユーティリティにマッチする新しい微分プライベートMSTアルゴリズムです。 我々のアルゴリズムの技術的コアは、全てのエッジ重みを$\Delta_\infty$の倍数に離散化し、同じ重みを持つエッジのグループを形成する、Report-Noisy-Maxの効率的なサブ線形時間シミュレーションである。 具体的には、少なくとも$O(n^2)$のカットエッジを$O(\sqrt{n} \log n)$の時間でサンプリングすることのできるデータ構造を示す。 実験による評価は,本アルゴリズムが実用性や実行時間において,従来のアルゴリズムを大幅に改善することを示すものである。

関連論文リスト

• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
  我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。 時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。 この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
  論文  参考訳（メタデータ） (2024-06-07T11:40:54Z)
• Almost linear time differentially private release of synthetic graphs [6.076406622352115]
  本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。 直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。 これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
  論文  参考訳（メタデータ） (2024-06-04T09:44:24Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。 重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-11-02T05:26:10Z)
• 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)
• Quantum complexity of minimum cut [0.2538209532048867]
  隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。 我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
  論文  参考訳（メタデータ） (2020-11-19T13:51:49Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。 本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。 我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
  論文  参考訳（メタデータ） (2020-08-15T11:06:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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