Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2637-2637, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-ghazi26b, title = {Fixed-Parameter Tractability of Private Synthetic Data Generation}, author = {Ghazi, Badih and Guzm{\'a}n, Crist{\'o}bal and Kamath, Pritish and Knop, Alexander and Kumar, Ravi and Manurangsi, Pasin}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2637--2637}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/ghazi26b/ghazi26b.pdf}, url = {https://proceedings.mlr.press/v336/ghazi26b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Fixed-Parameter Tractability of Private Synthetic Data Generation %A Badih Ghazi %A Cristóbal Guzmán %A Pritish Kamath %A Alexander Knop %A Ravi Kumar %A Pasin Manurangsi %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-ghazi26b %I PMLR %P 2637--2637 %U https://proceedings.mlr.press/v336/ghazi26b.html %V 336 %X 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.
APA
Ghazi, B., Guzmán, C., Kamath, P., Knop, A., Kumar, R. & Manurangsi, P.. (2026). Fixed-Parameter Tractability of Private Synthetic Data Generation. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2637-2637 Available from https://proceedings.mlr.press/v336/ghazi26b.html.

Related Material