基于树宽的高效私有数据生成，误差最优且方法统一。
Fixed-Parameter Tractability of Private Synthetic Data Generation
- 以查询图的树宽为参数，设计可固定参数可解的私有合成数据算法。
- 两种方法均达到各场景下的最优误差率，分别基于线性规划与采样权重。
- 适用于低树宽查询族，适合隐私保护数据生成研究者使用。
我们研究了在差分隐私约束下生成合成数据的问题。通过将查询族的关联图的树宽作为参数，建立了该问题的固定参数可解性（FPT）。所提出的算法在所有场景下均实现最优误差率，其核心思想来自两种不同方法：第一种基于线性规划（LP）及其对偶问题分离的FPT求解；第二种基于子采样私有乘法权重机制，并首次实现了吉布斯分布采样的FPT。两种方法统一于树分解上的动态规划框架中，显著提升了私有数据生成的效率与精度。
原文摘要 · Abstract (English)
We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth of the query family's incidence graph. Our algorithms attain optimal error rates across all regimes and are realized by two different approaches: the first is based on linear programming (LP) and the FPT of the separation problem for the LP dual; the second is based on a subsampled private multiplicative weights method, where we obtain FPT for sampling from Gibbs distributions. Both approaches are unified by a dynamic programming framework over a tree decomposition.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。