Differentially-private frugal estimation of quantiles

• URL: http://arxiv.org/abs/2502.20207v1
• Date: Thu, 27 Feb 2025 15:47:15 GMT
• Title: Differentially-private frugal estimation of quantiles
• Authors: Massimo Cafaro, Aneglo Coluccia, Italo Epicoco, Marco Pulimeno,
• Abstract summary: quantiles are robust indicators for the underlying distribution, compared to moment-based indicators such as mean and variance.<n>Stream items may arrive at a very high rate and must be processed as quickly as possible and discarded, being their storage usually unfeasible.<n>In this paper we present the following algorithms for frugal estimation of a quantile: DP-FRUGAL-1U-L, DP-FRUGAL-1U-G, DP-FRUGAL-1U-rho and DP-FRUGAL-2U-SA.
• Score: 2.934266338788597
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Fast and accurate estimation of quantiles on data streams coming from communication networks, Internet of Things (IoT), and alike, is at the heart of important data processing applications including statistical analysis, latency monitoring, query optimization for parallel database management systems, and more. Indeed, quantiles are more robust indicators for the underlying distribution, compared to moment-based indicators such as mean and variance. The streaming setting additionally constrains accurate tracking of quantiles, as stream items may arrive at a very high rate and must be processed as quickly as possible and discarded, being their storage usually unfeasible. Since an exact solution is only possible when data are fully stored, the goal in practical contexts is to provide an approximate solution with a provably guaranteed bound on the approximation error committed, while using a minimal amount of space. At the same time, with the increasing amount of personal and sensitive information exchanged, it is essential to design privacy protection techniques to ensure confidentiality and data integrity. In this paper we present the following differentially private streaming algorithms for frugal estimation of a quantile: DP-FRUGAL-1U-L, DP-FRUGAL-1U-G, DP-FRUGAL-1U-\r{ho} and DP-FRUGAL-2U-SA. Frugality refers to the ability of the algorithms to provide a good approximation to the sought quantile using a modest amount of space, either one or two units of memory. We provide a theoretical analysis and extensive experimental results, in which we also compare DP-FRUGAL-1U-L with LDPQ, a recent state of the art algorithm, and show that DP-FRUGAL-1U-L outperforms LDPQ in both accuracy and speed.

Related papers

• Dual Utilization of Perturbation for Stream Data Publication under Local Differential Privacy [10.07017446059039]
  Local differential privacy (LDP) has emerged as a promising standard. Applying LDP to stream data presents significant challenges, as stream data often involves a large or even infinite number of values. We introduce the Iterative Perturbation IPP method, which utilizes current perturbed results to calibrate the subsequent perturbation process. We prove that these three algorithms satisfy $w$-event differential privacy while significantly improving utility.
  arXiv  Detail & Related papers  (2025-04-21T09:51:18Z)
• Federated PCA and Estimation for Spiked Covariance Matrices: Optimal Rates and Efficient Algorithm [19.673557166734977]
  Federated Learning (FL) has gained significant recent attention in machine learning for its enhanced privacy and data security. This paper investigates federated PCA and estimation for spiked covariance matrices under distributed differential privacy constraints. We establish minimax rates of convergence, with a key finding that the central server's optimal rate is the harmonic mean of the local clients' minimax rates.
  arXiv  Detail & Related papers  (2024-11-23T21:57:50Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• DPZero: Private Fine-Tuning of Language Models without Backpropagation [49.365749361283704]
  We introduce DPZero, a novel private zeroth-order algorithm with nearly dimension-independent rates. The memory efficiency of DPZero is demonstrated in privately fine-tuning RoBERTa and OPT on several downstream tasks.
  arXiv  Detail & Related papers  (2023-10-14T18:42:56Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  We study the space complexity of the two related fields of differential privacy and adaptive data analysis. We show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy. The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries.
  arXiv  Detail & Related papers  (2023-02-11T14:45:31Z)
• 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)
• FedADMM: A Robust Federated Deep Learning Framework with Adaptivity to System Heterogeneity [4.2059108111562935]
  Federated Learning (FL) is an emerging framework for distributed processing of large data volumes by edge devices. In this paper, we introduce a new FLAD FedADMM based protocol. We show that FedADMM consistently outperforms all baseline methods in terms of communication efficiency.
  arXiv  Detail & Related papers  (2022-04-07T15:58:33Z)
• JUMBO: Scalable Multi-task Bayesian Optimization using Offline Data [86.8949732640035]
  We propose JUMBO, an MBO algorithm that sidesteps limitations by querying additional data. We show that it achieves no-regret under conditions analogous to GP-UCB. Empirically, we demonstrate significant performance improvements over existing approaches on two real-world optimization problems.
  arXiv  Detail & Related papers  (2021-06-02T05:03:38Z)
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times [51.61278695776151]
  Federated Learning (FL) is well known for its privacy protection when training machine learning models among distributed clients collaboratively. Recent studies have pointed out that the naive FL is susceptible to gradient leakage attacks. Differential Privacy (DP) emerges as a promising countermeasure to defend against gradient leakage attacks.
  arXiv  Detail & Related papers  (2021-01-11T19:43:12Z)
• APQ: Joint Search for Network Architecture, Pruning and Quantization Policy [49.3037538647714]
  We present APQ for efficient deep learning inference on resource-constrained hardware. Unlike previous methods that separately search the neural architecture, pruning policy, and quantization policy, we optimize them in a joint manner. With the same accuracy, APQ reduces the latency/energy by 2x/1.3x over MobileNetV2+HAQ.
  arXiv  Detail & Related papers  (2020-06-15T16:09:17Z)

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.