Fixed-Parameter Tractability of Private Synthetic Data Generation

• URL: http://arxiv.org/abs/2606.11283v1
• Date: Tue, 09 Jun 2026 15:14:11 GMT
• Title: Fixed-Parameter Tractability of Private Synthetic Data Generation
• Abstract summary: We study the problem of generating synthetic data under differential privacy.<n>Our algorithms attain optimal error rates across all regimes and are realized by two different approaches.
• Score: 84.99100741615423
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SEED: Targeted Data Selection by Weighted Independent Set [76.68391670109433]
  We develop a robust and scalable data selection pipeline dubbed SEED.<n>SEED consistently outperforms state-of-the-art methods on instruction tuning, visual instruction tuning, and semantic segmentation.
  arXiv  Detail & Related papers  (2026-05-15T07:26:54Z)
• Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guarantees [13.571671030124604]
  Piecewise regularization (PAR) provides a flexible modelingization based on the statistical perspectives.<n>We show how to use the PAR method to solve problems using gradient, and Alternating Direction Multipliers.
  arXiv  Detail & Related papers  (2025-08-14T23:35:21Z)
• An Iterative Bayesian Approach for System Identification based on Linear Gaussian Models [70.75865595489691]
  We tackle the problem of system identification, where we select inputs, observe the corresponding outputs from the true system, and optimize the parameters of our model to best fit the data.<n>Our approach only requires input-output data from the system and first-order information of the model with respect to the parameters.
  arXiv  Detail & Related papers  (2025-01-28T01:57:51Z)
• Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition [1.283608820493284]
  Metric Differential Privacy (mDP) extends the concept of Differential Privacy (DP) to serve as a new paradigm of data. It is designed to protect secret data represented in general metric space, such as text data encoded as word embeddings or geo-location data on the road network or grid maps.
  arXiv  Detail & Related papers  (2024-05-07T14:19:09Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Joint Bayesian Inference of Graphical Structure and Parameters with a Single Generative Flow Network [59.79008107609297]
  We propose in this paper to approximate the joint posterior over the structure of a Bayesian Network. We use a single GFlowNet whose sampling policy follows a two-phase process. Since the parameters are included in the posterior distribution, this leaves more flexibility for the local probability models.
  arXiv  Detail & Related papers  (2023-05-30T19:16:44Z)
• Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
  clustering clusters (FedC) problem aims to accurately partition unlabeled data samples distributed over massive clients into finite clients under the orchestration of a server. We propose a novel FedC algorithm using differential privacy convergence technique, referred to as DP-Fed, in which partial participation and multiple clients are also considered. Various attributes of the proposed DP-Fed are obtained through theoretical analyses of privacy protection, especially for the case of non-identically and independently distributed (non-i.i.d.) data.
  arXiv  Detail & Related papers  (2023-01-03T05:38:43Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  One of the main queries on such models is to identify the SDPWCSP Function on Cost of a Posteri (MAP) Networks. We consider a traditional dualized constraint approach and a dedicated dedicated SDP/Monteiro style method based on row-by-row updates.
  arXiv  Detail & Related papers  (2021-11-24T13:38:34Z)
• A Method for Handling Multi-class Imbalanced Data by Geometry based Information Sampling and Class Prioritized Synthetic Data Generation (GICaPS) [15.433936272310952]
  This paper looks into the problem of handling imbalanced data in a multi-label classification problem. Two novel methods are proposed that exploit the geometric relationship between the feature vectors. The efficacy of the proposed methods is analyzed by solving a generic multi-class recognition problem.
  arXiv  Detail & Related papers  (2020-10-11T04:04:26Z)
• Sparse learning with CART [18.351254916713305]
  Decision trees with binary splits are popularly constructed using Classification and Regression Trees (CART) methodology. This paper aims to study the statistical properties of regression trees constructed with CART methodology.
  arXiv  Detail & Related papers  (2020-06-07T20:55:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.