# Fast-MWEM: Private Data Release in Sublinear Time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 3 Feb 2026.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [Efficient, Noise-Tolerant, and Private Learning via Boosting](https://mlsanity.com/paper/2002.01100/) (2020)
- [Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search](https://mlsanity.com/paper/1707.03372/) (2017)
- [Privately Solving Linear Programs](https://mlsanity.com/paper/1402.3631/) (2014)
- [On Differentially Private Linear Algebra](https://mlsanity.com/paper/2411.03087/) (2024)
- [Solving Linear Programs with Differential Privacy](https://mlsanity.com/paper/2507.10946/) (2025)

## Abstract (arXiv)

The Multiplicative Weights Exponential Mechanism (MWEM) is a fundamental iterative framework for private data analysis, with broad applications such as answering m linear queries, or privately solving systems of m linear constraints. However, a critical bottleneck hindering its scalability is the Theta(m) time complexity required to execute the exponential mechanism in each iteration. We introduce a modification to the MWEM framework that improves the per-iteration runtime dependency to Theta(√m) in expectation. This is done via a lazy sampling approach to the Report-Noisy-Max mechanism, which we implement efficiently using Gumbel noise and a k-Nearest Neighbor data structure. This allows for the rapid selection of the approximate score in the exponential mechanism without an exhaustive linear scan. We apply our accelerated framework to the problems of private linear query release and solving Linear Programs (LPs) under neighboring constraint conditions and low-sensitivity assumptions. Experimental evaluation confirms that our method provides a substantial runtime improvement over classic MWEM.