Differentially Private Topological Data Analysis

• URL: http://arxiv.org/abs/2305.03609v2
• Date: Fri, 3 Nov 2023 16:55:55 GMT
• Title: Differentially Private Topological Data Analysis
• Authors: Taegyu Kang, Sehwan Kim, Jinwon Sohn, Jordan Awan
• Abstract summary: This paper is the first to attempt differentially private (DP) topological data analysis (TDA) We show that the commonly used vCech complex has sensitivity that does not decrease as the sample size $n$ increases. We propose using the exponential mechanism whose utility function is defined in terms of the bottleneck distance of the $L1$-DTM persistence diagrams.
• Score: 6.983833229285599
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is the first to attempt differentially private (DP) topological data analysis (TDA), producing near-optimal private persistence diagrams. We analyze the sensitivity of persistence diagrams in terms of the bottleneck distance, and we show that the commonly used \v{C}ech complex has sensitivity that does not decrease as the sample size $n$ increases. This makes it challenging for the persistence diagrams of \v{C}ech complexes to be privatized. As an alternative, we show that the persistence diagram obtained by the $L^1$-distance to measure (DTM) has sensitivity $O(1/n)$. Based on the sensitivity analysis, we propose using the exponential mechanism whose utility function is defined in terms of the bottleneck distance of the $L^1$-DTM persistence diagrams. We also derive upper and lower bounds of the accuracy of our privacy mechanism; the obtained bounds indicate that the privacy error of our mechanism is near-optimal. We demonstrate the performance of our privatized persistence diagrams through simulations as well as on a real dataset tracking human movement.

Related papers

• The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD [46.71175773861434]
  We propose a simple privacy analysis of noisy clipped gradient descent (DP-SGD) We show experimentally that our is predictive of the outcome of privacy auditing applied to various training procedures. We also empirically support our and show existing privacy auditing attacks are bounded by our analysis in both vision and language tasks.
  arXiv  Detail & Related papers  (2024-10-08T16:51:10Z)
• Locally Private Histograms in All Privacy Regimes [14.453502159917525]
  We investigate locally private histograms, and the very related distribution learning task, in a medium-to-low privacy regime. We obtain a protocol for histograms in the emphlocal model of differential privacy, with accuracy matching previous algorithms but significantly better message and communication complexity. Our theoretical findings emerge from a novel analysis, which appears to improve bounds across the board for the locally private histogram problem.
  arXiv  Detail & Related papers  (2024-08-09T06:22:45Z)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Using Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) to ensure Differential Privacy (DP) comes at the cost of model performance degradation. We propose a new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on R'enyi DP.
  arXiv  Detail & Related papers  (2023-11-24T17:56:44Z)
• Differentially Private Neural Tangent Kernels for Privacy-Preserving Data Generation [32.83436754714798]
  This work considers the using the features of $textitneural tangent kernels (NTKs)$, more precisely $textitempirical$ NTKs (e-NTKs) We find that, perhaps surprisingly, the expressiveness of the untrained e-NTK features is comparable to that of the features taken from pre-trained perceptual features using public data.
  arXiv  Detail & Related papers  (2023-03-03T03:00:49Z)
• 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)
• Differentially Private Learning Needs Hidden State (Or Much Faster Convergence) [9.429448411561541]
  We show that differentially private learning, with a tight bound, needs hidden state privacy analysis or a fast convergence. Our converging privacy analysis, thus, shows that differentially private learning, with a tight bound, needs hidden state privacy analysis or a fast convergence.
  arXiv  Detail & Related papers  (2022-03-10T13:31:08Z)
• Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning [74.73901662374921]
  A differentially private model degrades the utility drastically when the model comprises a large number of trainable parameters. We propose an algorithm emphGradient Embedding Perturbation (GEP) towards training differentially private deep models with decent accuracy.
  arXiv  Detail & Related papers  (2021-02-25T04:29:58Z)
• 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)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $tau_mathsfmix$. We propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate.
  arXiv  Detail & Related papers  (2020-06-16T04:26:50Z)
• Towards practical differentially private causal graph discovery [74.7791110594082]
  Causal graph discovery refers to the process of discovering causal relation graphs from purely observational data. We present a differentially private causal graph discovery algorithm, Priv-PC, which improves both utility and running time compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-15T18:30: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.