論文の概要: Differentially Private Gomory-Hu Trees

• arxiv url: http://arxiv.org/abs/2408.01798v1
• Date: Sat, 3 Aug 2024 14:50:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-06 18:21:07.283678
• Title: Differentially Private Gomory-Hu Trees
• Title（参考訳）: 異なる私的ゴモリー・フの木
• Authors: Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu,
• Abstract要約: 我々は,近似Gomory-Hu木を演算する差分プライベート(DP)アルゴリズムを設計する。 我々のアルゴリズムは$varepsilon$-DPであり、時間内で動作し、$tildeO(n/varepsilon)$-additive approximations of the Min-s$-$t$-Cuts in $G$ for all different $s.
• 参考スコア（独自算出の注目度）: 13.591231541692288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-Hu tree is a well-studied problem in graph algorithms and has received considerable attention. In particular, a long line of work recently culminated in constructing a Gomory-Hu tree in almost linear time [Abboud, Li, Panigrahi and Saranurak, FOCS 2023]. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, as [Dalirrooyfard, Mitrovi\'c and Nevmyvaka, NeurIPS 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega(n)$ additive error even with $(1, 0.1)$-DP and allowing for a multiplicative error term. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth and Ullman, TCC 2012] and $O(\sqrt{mn} \cdot \text{polylog}(n/\delta) / \varepsilon)$ for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024], both of which are implied by differential private algorithms that preserve all cuts in the graph. An important technical ingredient of our main result is an $\varepsilon$-DP algorithm for computing minimum Isolating Cuts with $\tilde{O}(n / \varepsilon)$ additive error, which may be of independent interest.
• Abstract（参考訳）: 無向で重み付けされた$n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$は$V$上の重み付き木であり、任意の異なる頂点の対に対して$s, t \in V$, the Min-$s$-$t$-Cut on $T$は$G$上のMin-$s$-$t$-Cutもまた$G$上のMin-$s$-$t$-Cutである。 Gomory-Hu木を計算することはグラフアルゴリズムにおいてよく研究されている問題であり、かなりの注目を集めている。 特に、近年の長い研究は、ほぼ直線時間でゴモリー・フの木(Abboud, Li, Panigrahi and Saranurak, FOCS 2023)を構築する上で頂点に達した。 我々は,近似Gomory-Hu木を演算する差分プライベート(DP)アルゴリズムを設計する。 我々のアルゴリズムは$\varepsilon$-DPであり、多項式時間で実行され、$\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in the $G$ for all different $s, t \in V$ with high probability。 我々の誤差境界は基本的に最適であり、[Dalirrooyfard, Mitrovi\'c and Nevmyvaka, NeurIPS 2023] は、単一のMin-$s$-$t$-Cutをプライベートに出力するには、$(1, 0.1)$-DPでも$\Omega(n)$加法誤差が必要であり、乗法誤差項が可能であることを示した。 Min-$s$-$t$-Cuts は $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth and Ullman, TCC 2012] と $O(\sqrt{mn} \cdot \text{polylog}(n/\delta) / \varepsilon)$ for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024] である。 我々の主な成果の重要な技術的要素は、最小Isolating Cutsを$\tilde{O}(n / \varepsilon)$加法誤差で計算する$\varepsilon$-DPアルゴリズムである。

関連論文リスト

• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。 本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
  論文  参考訳（メタデータ） (2022-09-06T23:37:31Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• 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)
• Coresets for Decision Trees of Signals [19.537354146654845]
  仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。 これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
  論文  参考訳（メタデータ） (2021-10-07T05:49:55Z)
• 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)
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
  古典的ChowLiuアルゴリズム(IEEE Trans.Inform.Theory, 1968)に対する有限サンプル保証を提供する。 特定の木の$T$に対して、$widetildeO (|Sigma|2nvarepsilon-1)$の分布からのサンプルを$P$ over $Sigman$とすると、最も近いKL分岐を効率的に学習できる。
  論文  参考訳（メタデータ） (2020-11-09T02:08:56Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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