The Fast Mixing Mechanism for Differential Privacy
2026
Read The Fast Mixing Mechanism for Differential Privacy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30600.txt.
Description
Lev and colleagues present a fast differential-privacy sketching mechanism based on fast transforms. Random sketching compresses large tuning problems while preserving accuracy, and structured matrices like Hadamard apply efficiently. Gaussian sketching has served private linear regression, but usually without runtime gains over old approaches. It matches old fast sketching runtime in certain cases, with privacy guarantees matching Gaussian sketch guarantees up to a constant factor. Combined with sketch-based methods for private linear regression, it yields the first fast method for private ordinary least squares.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 182737 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.30600