# The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches

arXiv: https://arxiv.org/abs/2505.24603 · HTML: https://mlsanity.com/paper/2505.24603/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 30 May 2025.

## Builds on (most cited first, 25 of 25)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Differential Privacy as a Mutual Information Constraint](https://mlsanity.com/paper/1608.03677/) (2016)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks](https://mlsanity.com/paper/2011.06223/) (2020)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise](https://mlsanity.com/paper/1902.04688/) (2019)
- [PASS-GLM: polynomial approximate sufficient statistics for scalable Bayesian GLM inference](https://mlsanity.com/paper/1709.09216/) (2017)
- [Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation](https://mlsanity.com/paper/2402.13531/) (2024)
- [Stochastic Coded Federated Learning with Convergence and Privacy Guarantees](https://mlsanity.com/paper/2201.10092/) (2022)
- [Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression](https://mlsanity.com/paper/1507.00056/) (2015)
- [Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds](https://mlsanity.com/paper/2203.09755/) (2022)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)

## Built on by (most cited first, 2 of 2)

- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)
- [The Fast Mixing Mechanism for Differential Privacy](https://mlsanity.com/paper/2605.30600/) (2026)

## Abstract (arXiv)

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.