私有合成数据生成的固定参数可解性

核心结论

差分隐私下合成数据生成问题首次被严格证明具备固定参数可解性（Fixed-Parameter Tractability, FPT），关键参数为查询族（query family）关联图的树宽（treewidth）——该结构参数刻画了查询间依赖关系的稀疏性。

算法设计与理论贡献

• LP 对偶分离问题的 FPT 解法：将合成数据生成建模为线性规划（LP），其对偶问题的分离（separation）可在 treewidth 为参数时实现 FPT 求解，从而导出整体 FPT 算法；
• 子采样私有乘性权重法（subsampled private multiplicative weights）：改进经典 Multiplicative Weights Mechanism，其中 Gibbs 分布采样步骤被证明在 treewidth 参数下具备 FPT 复杂度；
• 统一框架：两种路径均依托于同一动态规划（dynamic programming）范式，运行于查询族关联图的树分解（tree decomposition）之上，凸显结构化先验对隐私计算效率的根本性提升。

实践意义

该工作为高维、结构化查询（如 join-rich SQL 工作负载或图模式查询）下的高效私有合成提供了首个理论可行路径，避免了传统方法在维度灾难下的指数级开销；树宽作为可计算图参数，亦为实际系统中自动识别‘易处理’查询子集提供了可部署的判据。