# The Fast Mixing Mechanism for Differential Privacy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 28 May 2026.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [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)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization](https://mlsanity.com/paper/2007.01327/) (2020)
- [Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing](https://mlsanity.com/paper/1410.2470/) (2014)
- [Optimal Shrinkage for Distributed Second-Order Optimization](https://mlsanity.com/paper/2402.01956/) (2024)
- [The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches](https://mlsanity.com/paper/2505.24603/) (2025)
- [Sketched Gaussian Mechanism for Private Federated Learning](https://mlsanity.com/paper/2509.08195/) (2025)
- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)

## Abstract (arXiv)

Randomized sketching is a central tool for compressing large-scale optimization problems while preserving accuracy. In particular, sketches that are based on structured matrices, such as the Hadamard matrix, can be applied efficiently and often yield solutions that approximate those of the original problem at much lower computational cost. In differential privacy (DP), Gaussian sketching has been used to solve DP linear regression, beginning with citetsheffet2017differentially, sheffet2019old and later refined by citetlev2025gaussianmix, lev2026near. However, although these methods achieve strong utility guarantees, they usually do not improve runtime over classical DP approaches. In this work, we introduce a new DP sketching mechanism based on fast transforms, which, in certain cases, matches the runtime of classical fast sketching methods. We prove state-of-the-art privacy guarantees for this mechanism and show that, in favorable regimes, they match those of the Gaussian sketch up to a constant factor. As an application, we combine this mechanism with recent sketch-based methods for DP linear regression to obtain a new algorithm with strong utility and improved runtime. We establish privacy and accuracy guarantees for this algorithm, yielding, to the best of our knowledge, the first fast method for DP ordinary least squares.