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
| CREATOR | Themistoklis Haris, Steve Choi, Mutiraj Laksanawisit |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-03732