Fast-MWEM: Private Data Release in Sublinear Time
This work addresses efficiency issues in private data analysis for applications like query answering and linear programming, representing an incremental improvement over existing methods.
The paper tackles the scalability bottleneck of the Multiplicative Weights Exponential Mechanism (MWEM) for private data analysis by reducing its per-iteration runtime from Θ(m) to Θ(√m) in expectation, enabling faster private linear query release and solving Linear Programs under privacy constraints.
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 $Θ(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 $Θ(\sqrt{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.