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

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE182737
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30600

Browse the full library · About the Tower of Babel