Fast-MWEM: Private Data Release in Sublinear Time
Not on the map. Why?
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.
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
9 of 19 references.
References · 9
- 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
- 2021Iterative Methods for Private Synthetic Data: Unifying Framework and New Methodscited by 59
- 2018Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighborscited by 37
- 2014On Symmetric and Asymmetric LSHs for Inner Product Searchcited by 23
- 2020Efficient, Noise-Tolerant, and Private Learning via Boostingcited by 15
- 2017Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Searchcited by 8
- 2014Privately Solving Linear Programscited by 7
- 2024On Differentially Private Linear Algebracited by 4
- 2025Solving Linear Programs with Differential Privacycited by 1
Built on by
Not cited yet.