Learning with User-Level Privacy

• URL: http://arxiv.org/abs/2102.11845v1
• Date: Tue, 23 Feb 2021 18:25:13 GMT
• Title: Learning with User-Level Privacy
• Authors: Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, Ananda Theertha Suresh
• Abstract summary: We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
• Score: 61.62978104304273
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We propose and analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution ($m \ge 1$ samples), providing more stringent but more realistic protection against information leaks. We show that for high-dimensional mean estimation, empirical risk minimization with smooth losses, stochastic convex optimization, and learning hypothesis class with finite metric entropy, the privacy cost decreases as $O(1/\sqrt{m})$ as users provide more samples. In contrast, when increasing the number of users $n$, the privacy cost decreases at a faster $O(1/n)$ rate. We complement these results with lower bounds showing the worst-case optimality of our algorithm for mean estimation and stochastic convex optimization. Our algorithms rely on novel techniques for private mean estimation in arbitrary dimension with error scaling as the concentration radius $\tau$ of the distribution rather than the entire range. Under uniform convergence, we derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $\tau$, and apply it to solve the learning tasks we consider.

Related papers

• Efficient Sparse Least Absolute Deviation Regression with Differential Privacy [10.414082115202003]
  We develop a fast privacy-preserving learning solution for a sparse robust regression problem. Our algorithm achieves a fast estimation by reformulating the sparse LAD problem as a penalized least square estimation problem. We show that our algorithm can achieve better privacy and statistical accuracy trade-off compared with the state-of-the-art privacy-preserving regression algorithms.
  arXiv  Detail & Related papers  (2024-01-02T17:13:34Z)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  We show how to shuffle $(epsilon_i,delta_i)$-PLDP setting with personalized privacy parameters. We prove that shuffled $(epsilon_i,delta_i)$-PLDP process approximately preserves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  arXiv  Detail & Related papers  (2023-12-22T02:31:46Z)
• Discrete Distribution Estimation under User-level Local Differential Privacy [37.65849910114053]
  We study discrete distribution estimation under user-level local differential privacy (LDP) In user-level $varepsilon$-LDP, each user has $mge1$ samples and the privacy of all $m$ samples must be preserved simultaneously.
  arXiv  Detail & Related papers  (2022-11-07T18:29:32Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• 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)
• Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training [12.386462516398469]
  Finding efficient, easily implementable differentially private (DP) algorithms that offer strong excess risk bounds is an important problem in modern machine learning. We provide the tightest known $(epsilon, 0)$-DP population loss bounds and fastest runtimes under the presence of smoothness and strong convexity. We apply our theory to two learning frameworks: tilted ERM and adversarial learning frameworks.
  arXiv  Detail & Related papers  (2021-02-09T08:47:06Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)

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.