Differentially Private Gomory-Hu Trees

• URL: http://arxiv.org/abs/2408.01798v1
• Date: Sat, 3 Aug 2024 14:50:03 GMT
• Title: Differentially Private Gomory-Hu Trees
• Abstract summary: We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $varepsilon$-DP, runs in time, and can be used to compute cuts that are $tildeO(n/varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s.
• Score: 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.

Related papers

• Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers [9.297355862757838]
  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.<n>We give a bounded-time $(varepsilon,)$-differentially private algorithm which, for every $n$-vertex unweighted graph $G$, outputs a non-negative weighted synthetic graph.
  arXiv  Detail & Related papers  (2026-07-21T08:35:05Z)
• New Algorithmic Directions in Optimal Transport and Applications for Product Spaces [5.9725566031600925]
  We study optimal transport between two high-dimensional distributions $mu,nu$ in $Rn$ from an algorithmic perspective.<n>Running time depends on the dimension rather than the full representation size of $mu,nu$.<n>For any $mathcalS$ of Gaussian measure $varepsilon$, most $Phin$ samples can be mapped to $mathcalS$ within distance $O(sqrtlog 1/varepsilon)$ in $poly(n/varepsilon)$
  arXiv  Detail & Related papers  (2025-09-25T19:58:06Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory. We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds. We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• A Tight VC-Dimension Analysis of Clustering Coresets with Applications [19.213536807823836]
  We consider coresets for $k$-clustering problems, where the goal is to assign points to centers minimizing powers of distances.<n>Given a point set $P$, a coreset $Omega$ is a small weighted subset that approximates the cost of $P$ for all candidate solutions.<n>We obtain improved $k$-median coreset bounds for the following metrics.
  arXiv  Detail & Related papers  (2025-01-11T17:00:57Z)
• Differentially Private Kernel Density Estimation [11.526850085349155]
  We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE)<n>We study the mathematical problem: given a similarity function $f$ and a private dataset $X subset mathbbRd$, our goal is to preprocess $X$ so that for any query $yinmathbbRd$, we approximate $sum_x in X f(x, y)$ in a differentially private fashion.
  arXiv  Detail & Related papers  (2024-09-03T08:01:19Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted $n$-sized label-feature sample of at most $epsilon n$ arbitrary outliers. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on $(Sigma,Xi) nor the operator norm of $Xi$.
  arXiv  Detail & Related papers  (2022-09-06T23:37:31Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$. We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
  arXiv  Detail & Related papers  (2021-11-02T05:26:10Z)
• Coresets for Decision Trees of Signals [19.537354146654845]
  We provide the first algorithm that outputs such a $(k,varepsilon)$-coreset for emphevery such matrix $D$. This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry.
  arXiv  Detail & Related papers  (2021-10-07T05:49:55Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
  We provide finite sample guarantees for the classical ChowLiu algorithm (IEEE Trans.Inform.Theory, 1968) We show that for a specific tree $T$, with $widetildeO (|Sigma|2nvarepsilon-1)$ samples from a distribution $P$ over $Sigman$, one can efficiently learn the closest KL divergence.
  arXiv  Detail & Related papers  (2020-11-09T02:08:56Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  We show an algorithm that runs in time $widetildeO(T(N, d) log kappa / mathrmpoly (varepsilon))$, where $T(N, d)$ is the time it takes to multiply a $d times N$ matrix by its transpose. Our runtime matches that of the fastest algorithm for covariance estimation without outliers, up to poly-logarithmic factors.
  arXiv  Detail & Related papers  (2020-06-23T20:21:27Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.