Fast-MWEM: Private Data Release in Sublinear Time

Themistoklis Haris, Steve Choi, Mutiraj Laksanawisit · 2026

Read Fast-MWEM: Private Data Release in Sublinear Time by Themistoklis Haris, Steve Choi, Mutiraj Laksanawisit (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-2602-03732.txt.

Description

Releasing statistics from private data without exposing individuals is the job of MWEM, a classic iterative algorithm with a scaling problem. Themistoklis Haris and 2 co-authors attack that bottleneck in a 2026 paper. Each MWEM iteration scans all queries to run its exponential mechanism, so the cost grows linearly with the number of queries.

Fast-MWEM replaces the exhaustive scan with lazy sampling of the noisy-max step, implemented with Gumbel noise and a nearest-neighbor data structure. The per-iteration cost drops to roughly the square root of the query count in expectation. The authors apply the accelerated framework to private linear query release and to solving linear programs under privacy constraints. Experiments confirm substantial runtime improvements over classic MWEM.

Catalog record

CREATORThemistoklis Haris, Steve Choi, Mutiraj Laksanawisit
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-03732

Browse the full library · About the Tower of Babel