Profile Reconstruction from Private Sketches

• URL: http://arxiv.org/abs/2406.01158v1
• Date: Mon, 3 Jun 2024 09:51:28 GMT
• Title: Profile Reconstruction from Private Sketches
• Authors: Hao Wu, Rasmus Pagh,
• Abstract summary: Given a multiset of $n$ items from $mathcalD$, the emphprofile reconstruction problem is to estimate, for $t = 0, 1, dots, n$, the fraction $vecf[t]$ of items in $mathcalD$ that appear exactly $tfty times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset. We show how to speed up their LP-based technique
• Score: 13.929335175122265
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of $\vec{f} = (\vec{f}[0], \dots, \vec{f}[n])$. Using a histogram privatized using discrete Laplace noise, we show how to ``reverse'' the noise, using an approach of Dwork et al.~(ITCS '10). We show how to speed up their LP-based technique from polynomial time to $O(d + n \log n)$, where $d = |\mathcal{D}|$, and analyze the achievable error in the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. In all cases the dependency of the error on $d$ is $O( 1 / \sqrt{d})$ -- we give an information-theoretic lower bound showing that this dependence on $d$ is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee.

Related papers

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• 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)
• 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)
• Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed Data [22.233705161499273]
  We focus on the $ell_1$-norm linear regression in the $epsilon$-DP model. We show that it is possible to achieve an upper bound of $tildeO(sqrtfracdnepsilon)$ with high probability. Our algorithms can also be extended to more relaxed cases where only each coordinate of the data has bounded moments.
  arXiv  Detail & Related papers  (2022-01-10T08:17:05Z)
• Terminal Embeddings in Sublinear Time [14.959896180728832]
  We show how to pre-process $T$ to obtain an almost linear-space data structure that supports computing the terminal embedding image of any $qinmathbbRd$ in sublinear time. Our main contribution in this work is to give a new data structure for computing terminal embeddings.
  arXiv  Detail & Related papers  (2021-10-17T00:50:52Z)
• Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
  We study the case where the population risk function satisfies the Tysbakov Noise Condition (TNC) with some parameter $theta>1$. In the second part, we focus on a special case where the population risk function is strongly convex.
  arXiv  Detail & Related papers  (2021-07-31T22:23:39Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• 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)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)

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.