将隐私数据发布速度提升至亚线性时间，大幅加速私有分析
Fast-MWEM: Private Data Release in Sublinear Time
- 用懒惰采样结合高斯噪声与k近邻结构，避免每轮全量扫描
- 每轮运行时间从O(m)降至期望O(√m)，在真实数据集上提速超10倍
- 适合需快速处理海量查询的私有数据分析场景
多重加权指数机制（MWEM）是私有数据分析中的核心迭代框架，广泛用于回答m个线性查询或私有求解m个线性约束系统。然而，其可扩展性受制于每轮迭代中指数机制需耗时Θ(m)。本文提出一种改进框架，将每轮运行时间复杂度优化至期望Θ(√m)。该方法通过懒惰采样实现报告噪声最大值机制，利用Gumbel噪声与k-最近邻数据结构高效选取近似得分，避免了全量线性扫描。我们在私有线性查询发布和邻近约束下低敏感度假设的线性规划求解问题上应用该加速框架。实验表明，该方法相比经典MWEM实现显著的运行时间提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。