Privacy-Computation trade-offs in Private Repetition and Metaselection

• URL: http://arxiv.org/abs/2410.19012v1
• Date: Tue, 22 Oct 2024 18:33:02 GMT
• Title: Privacy-Computation trade-offs in Private Repetition and Metaselection
• Authors: Kunal Talwar,
• Abstract summary: A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead.
• Score: 28.11248357424981
• License:
• Abstract: A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. These algorithms are closely related to private metaselection algorithms that compete with the best of many private algorithms, and private hyperparameter tuning algorithms that compete with the best hyperparameter settings for a private learning algorithm. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. In this work, we show strong lower bounds for problems of this kind, showing in particular that for any algorithm that preserves the privacy cost up to a constant factor, the failure probability can only fall polynomially in the computational overhead. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead. By carefully combining existing algorithms for metaselection, we prove computation-privacy tradeoffs that nearly match our lower bounds.

Related papers

• Differentially Private Multiway and $k$-Cut [5.893651469750359]
  We introduce edge-differentially private algorithms that achieve nearly optimal performance for minimum $k$-cut and multiway cut problems. For the minimum $k$-cut problem, our algorithms leverage a known bound on the number of approximate $k$-cuts, resulting in a private algorithm with optimal additive error $O(klog n)$ for fixed privacy parameter.
  arXiv  Detail & Related papers  (2024-07-09T14:46:33Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectives [10.528569272279999]
  This paper proposes a differentially private federated learning algorithm for strongly convex but possibly nonsmooth problems. The proposed algorithm adds artificial noise to the shared information to ensure privacy and dynamically allocates the time-varying noise variance to minimize an upper bound of the optimization error. Numerical results show the superiority of the proposed algorithm over state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-08-02T13:30:33Z)
• Private Networked Federated Learning for Nonsmooth Objectives [7.278228169713637]
  This paper develops a networked federated learning algorithm to solve nonsmooth objective functions. We use the zero-concentrated differential privacy notion (zCDP) to guarantee the confidentiality of the participants. We provide complete theoretical proof for the privacy guarantees and the algorithm's convergence to the exact solution.
  arXiv  Detail & Related papers  (2023-06-24T16:13:28Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball. We propose a new algorithmic framework, ProjUnit, for private mean estimation. Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace, normalizes the result, and then runs an optimal algorithm.
  arXiv  Detail & Related papers  (2023-06-07T14:07:35Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Numerical Composition of Differential Privacy [22.523399777002926]
  We give a fast algorithm to optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms.
  arXiv  Detail & Related papers  (2021-06-05T09:20:15Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
  We consider the ubiquitous problem of gaussian process (GP) bandit optimization from the lens of privacy-preserving statistics. We propose a solution for differentially private GP bandit optimization that combines a uniform kernel approximator with random perturbations. Our algorithms maintain differential privacy throughout the optimization procedure and critically do not rely explicitly on the sample path for prediction.
  arXiv  Detail & Related papers  (2021-02-24T18:52:24Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)

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.