Differential Privacy with Multiple Selections

• URL: http://arxiv.org/abs/2407.14641v1
• Date: Fri, 19 Jul 2024 19:34:51 GMT
• Title: Differential Privacy with Multiple Selections
• Authors: Ashish Goel, Zhihao Jiang, Aleksandra Korolova, Kamesh Munagala, Sahasrajit Sarmasarkar,
• Abstract summary: We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one that matches best with their private features.
• Score: 52.5653572324012
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one from these that matches best with their private features. When the user feature is one-dimensional -- on an infinite line -- and the accuracy measure is defined w.r.t some increasing function $\mathfrak{h}(.)$ of the distance on the line, we precisely characterize the optimal mechanism that satisfies differential privacy. The specification of the optimal mechanism includes both the distribution of the noise that the user adds to its private value, and the algorithm used by the server to determine the set of results to send back as a response and further show that Laplace is an optimal noise distribution. We further show that this optimal mechanism results in an error that is inversely proportional to the number of results returned when the function $\mathfrak{h}(.)$ is the identity function.

Related papers

• PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds [9.47030623916154]
  We propose a differentially private decentralized learning method (termed PrivSGPVR) which employs gradient push with variance reduction and guarantees privacy for each node. Our theoretical analysis shows that, under DP noise with constant variance, PrivGPS-VR achieves a sub-linear convergence rate of $mathcalO (1/sqrtnK)$.
  arXiv  Detail & Related papers  (2024-05-04T11:22:53Z)
• Near-Universally-Optimal Differentially Private Minimum Spanning Trees [0.0]
  We prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the $ell_infty$ neighbor relation. We show that one may implement the exponential mechanism for MST in time, and that this results in universal near-optimality for both the $ell_infty$ and the $ell_infty$ neighbor relations.
  arXiv  Detail & Related papers  (2024-04-23T13:39:25Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm. Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• On Differential Privacy for Federated Learning in Wireless Systems with Multiple Base Stations [90.53293906751747]
  We consider a federated learning model in a wireless system with multiple base stations and inter-cell interference. We show the convergence behavior of the learning process by deriving an upper bound on its optimality gap. Our proposed scheduler improves the average accuracy of the predictions compared with a random scheduler.
  arXiv  Detail & Related papers  (2022-08-25T03:37:11Z)
• 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)
• Tight and Robust Private Mean Estimation with Few Users [16.22135057266913]
  We study high-dimensional mean estimation under user-level differential privacy. We design an $(eps,delta)$-differentially private mechanism using as few users as possible.
  arXiv  Detail & Related papers  (2021-10-22T16:02:21Z)
• Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions [73.33961743410876]
  A soft-max function has two main efficiency measures: approximation and smoothness. We identify the optimal approximation-smoothness tradeoffs for different measures of approximation and smoothness. This leads to novel soft-max functions, each of which is optimal for a different application.
  arXiv  Detail & Related papers  (2020-10-22T05:19:58Z)

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.