Nebula: Efficient, Private and Accurate Histogram Estimation

• URL: http://arxiv.org/abs/2409.09676v2
• Date: Thu, 03 Jul 2025 14:13:44 GMT
• Title: Nebula: Efficient, Private and Accurate Histogram Estimation
• Abstract summary: textitNebula is a system for differentially private histogram estimation on data distributed among clients.<n>textitNebula allows clients to independently decide whether to participate in the system.<n>Clients submit their data in just 0.0036 seconds and 0.0016 MB (textbfefficient), under strong $(varepsilon=1,delta=10-8)$ differential privacy guarantees.
• Score: 21.514019328704926
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present \textit{Nebula}, a system for differentially private histogram estimation on data distributed among clients. \textit{Nebula} allows clients to independently decide whether to participate in the system, and locally encode their data so that an untrusted server only learns data values whose multiplicity exceeds a predefined aggregation threshold, with $(\varepsilon,\delta)$ differential privacy guarantees. Compared to existing systems, \textit{Nebula} uniquely achieves: \textit{i)} a strict upper bound on client privacy leakage; \textit{ii)} significantly higher utility than standard local differential privacy systems; and \textit{iii)} no requirement for trusted third-parties, multi-party computation, or trusted hardware. We provide a formal evaluation of \textit{Nebula}'s privacy, utility and efficiency guarantees, along with an empirical assessment on three real-world datasets. On the United States Census dataset, clients can submit their data in just 0.0036 seconds and 0.0016 MB (\textbf{efficient}), under strong $(\varepsilon=1,\delta=10^{-8})$ differential privacy guarantees (\textbf{private}), enabling \textit{Nebula}'s untrusted aggregation server to estimate histograms with over 88\% better utility than existing local differential privacy deployments (\textbf{accurate}). Additionally, we describe a variant that allows clients to submit multi-dimensional data, with similar privacy, utility, and performance. Finally, we provide an implementation of \textit{Nebula}.

Related papers

• Privacy-Utility Tradeoffs in Quantum Information Processing [13.088625380700933]
  We study optimal tradeoffs for both generic and application-specific utility metrics when privacy is quantified by $(varepsilon,)$-quantum local differential privacy.<n>We derive a lower bound on the number of samples required to achieve a fixed accuracy guarantee with high probability.<n>We conclude by initiating the study of private classical shadows, which promise useful applications for private learning tasks.
  arXiv  Detail & Related papers  (2026-02-11T04:21:45Z)
• PrivTune: Efficient and Privacy-Preserving Fine-Tuning of Large Language Models via Device-Cloud Collaboration [17.909232830653618]
  We propose PrivTune, an efficient and privacy-preserving fine-tuning framework via Split Learning (SL)<n>The key idea of PrivTune is to inject crafted noise into token representations from the SL bottom model, making each token resemble the $n$-hop indirect neighbors.<n>Experiments show that, using RoBERTa on the Stanford Sentiment Treebank dataset, PrivTune reduces the attack success rate to 10% with only a 3.33% drop in utility performance.
  arXiv  Detail & Related papers  (2025-12-09T17:03:59Z)
• Private Model Personalization Revisited [13.4143747448136]
  We study model personalization under user-level differential privacy (DP) in the shared representation framework.<n>Our goal is to privately recover the shared embedding and the local low-dimensional representations with small excess risk.<n>We present an information-theoretic construction to privately learn the shared embedding and derive a margin-based accuracy guarantee.
  arXiv  Detail & Related papers  (2025-06-24T00:57:17Z)
• Enhanced Privacy Bound for Shuffle Model with Personalized Privacy [32.08637708405314]
  Differential Privacy (DP) is an enhanced privacy protocol which introduces an intermediate trusted server between local users and a central data curator. It significantly amplifies the central DP guarantee by anonymizing and shuffling the local randomized data. This work focuses on deriving the central privacy bound for a more practical setting where personalized local privacy is required by each user.
  arXiv  Detail & Related papers  (2024-07-25T16:11:56Z)
• Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learning [21.27813247914949]
  We propose Robust-HDP, which efficiently estimates the true noise level in clients model updates. It improves utility and convergence speed, while being safe to the clients that may maliciously send falsified privacy parameter to server.
  arXiv  Detail & Related papers  (2024-06-05T17:41:42Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Clients Collaborate: Flexible Differentially Private Federated Learning with Guaranteed Improvement of Utility-Privacy Trade-off [34.2117116062642]
  We introduce a novel federated learning framework with rigorous privacy guarantees, named FedCEO, to strike a trade-off between model utility and user privacy. We show that our FedCEO can effectively recover the disrupted semantic information by smoothing the global semantic space. It observes significant performance improvements and strict privacy guarantees under different privacy settings.
  arXiv  Detail & Related papers  (2024-02-10T17:39:34Z)
• Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learning [47.042811490685324]
  Mitigating the risk of this information leakage, using state of the art differentially private algorithms, also does not come for free. In this paper, we consider a representation learning objective that various parties collaboratively refine on a federated model, with differential privacy guarantees. We observe a significant performance improvement over the prior work under the same small privacy budget.
  arXiv  Detail & Related papers  (2023-09-11T14:46:55Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• 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)
• FedAUXfdp: Differentially Private One-Shot Federated Distillation [11.28272643576878]
  FedAUX is an augmentation of federated distillation with robust results on even highly heterogeneous client data. In experiments with deep networks on large-scale image datasets, FedAUXfdp with strong differential privacy guarantees performs significantly better than other SOTA baselines.
  arXiv  Detail & Related papers  (2022-05-30T09:57:33Z)
• Mixed Differential Privacy in Computer Vision [133.68363478737058]
  AdaMix is an adaptive differentially private algorithm for training deep neural network classifiers using both private and public image data. A few-shot or even zero-shot learning baseline that ignores private data can outperform fine-tuning on a large private dataset.
  arXiv  Detail & Related papers  (2022-03-22T06:15:43Z)
• Syfer: Neural Obfuscation for Private Data Release [58.490998583666276]
  We develop Syfer, a neural obfuscation method to protect against re-identification attacks. Syfer composes trained layers with random neural networks to encode the original data. It maintains the ability to predict diagnoses from the encoded data.
  arXiv  Detail & Related papers  (2022-01-28T20:32:04Z)
• Scotch: An Efficient Secure Computation Framework for Secure Aggregation [0.0]
  Federated learning enables multiple data owners to jointly train a machine learning model without revealing their private datasets. A malicious aggregation server might use the model parameters to derive sensitive information about the training dataset used. We propose textscScotch, a decentralized textitm-party secure-computation framework for federated aggregation.
  arXiv  Detail & Related papers  (2022-01-19T17:16:35Z)
• 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)
• CryptoSPN: Privacy-preserving Sum-Product Network Inference [84.88362774693914]
  We present a framework for privacy-preserving inference of sum-product networks (SPNs) CryptoSPN achieves highly efficient and accurate inference in the order of seconds for medium-sized SPNs.
  arXiv  Detail & Related papers  (2020-02-03T14:49:18Z)

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.