The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches

• URL: http://arxiv.org/abs/2505.24603v2
• Date: Wed, 04 Jun 2025 16:02:22 GMT
• Title: The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches
• Authors: Omri Lev, Vishwak Srinivasan, Moshe Shenfeld, Katrina Ligett, Ayush Sekhari, Ashia C. Wilson,
• Abstract summary: In this work, we revisit this operation through the lens of Renyi Differential Privacy (RDP)<n>We demonstrate how this improved analysis leads to performance improvement in different linear regression settings.<n> Empirically, our methods improve performance across multiple datasets and, in several cases, reduce runtime.
• Score: 13.972860872034525
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian sketching, which consists of pre-multiplying the data with a random Gaussian matrix, is a widely used technique for multiple problems in data science and machine learning, with applications spanning computationally efficient optimization, coded computing, and federated learning. This operation also provides differential privacy guarantees due to its inherent randomness. In this work, we revisit this operation through the lens of Renyi Differential Privacy (RDP), providing a refined privacy analysis that yields significantly tighter bounds than prior results. We then demonstrate how this improved analysis leads to performance improvement in different linear regression settings, establishing theoretical utility guarantees. Empirically, our methods improve performance across multiple datasets and, in several cases, reduce runtime.

Related papers

• Shortening the Trajectories: Identity-Aware Gaussian Approximation for Efficient 3D Molecular Generation [2.631060597686179]
  Probabilistic Generative Models (GPGMs) generate data by reversing a process that corrupts samples with Gaussian noise.<n>These models have achieved state-of-the-art performance across diverse domains, but their practical deployment remains constrained by the high computational cost.<n>We introduce a theoretically grounded and empirically validated framework that improves generation efficiency without sacrificing training granularity or inference fidelity.
  arXiv  Detail & Related papers  (2025-07-11T21:39:32Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD.<n>We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy [17.81999485513265]
  We study gradient descent under linearly correlated noise. We use our results to develop new, effective matrix factorizations for differentially private optimization.
  arXiv  Detail & Related papers  (2023-02-02T23:32:24Z)
• 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)
• An automatic differentiation system for the age of differential privacy [65.35244647521989]
  Tritium is an automatic differentiation-based sensitivity analysis framework for differentially private (DP) machine learning (ML) We introduce Tritium, an automatic differentiation-based sensitivity analysis framework for differentially private (DP) machine learning (ML)
  arXiv  Detail & Related papers  (2021-09-22T08:07:42Z)
• Differentially Private Federated Learning with Laplacian Smoothing [72.85272874099644]
  Federated learning aims to protect data privacy by collaboratively learning a model without sharing private data among users. An adversary may still be able to infer the private training data by attacking the released model. Differential privacy provides a statistical protection against such attacks at the price of significantly degrading the accuracy or utility of the trained models.
  arXiv  Detail & Related papers  (2020-05-01T04:28:38Z)

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.