Research map / Federated learning and privacy / Differential privacy
Bounding the Excess Risk for Linear Models Trained on Marginal-Preserving, Differentially-Private, Synthetic Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives upper and lower bounds on the excess empirical risk of linear models trained on marginal-preserving DP synthetic data, and experiments with AIM synthetic data on six tabular datasets.
Problem
Understanding whether training linear models on DP synthetic data that preserves low-order marginals yields provably low excess empirical risk relative to training on real data.
Approach
Bounds the risk gap between models trained on real and marginal-preserving synthetic data by Bernstein polynomial approximation of the loss, so that each monomial's average is determined by a marginal and the l1 marginal error controls the risk difference; also proves a matching lower bound via non-adaptive statistical queries.
Key results
- With epsilon=2, models trained on AIM synthetic data lose less than 1% accuracy versus real data on five of six datasets; Heart drops 2.2%.
- Excess empirical risk below 0.02 on most datasets at epsilon=2 (Heart: 0.032).
- Lower bound Omega(1/ln^3 n) nearly matches upper bound O(sqrt(ln ln n / ln n)) for worst-case distributions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train logistic regression on AIM synthetic data rather than real data at ε=2 | Logistic regression · Public datasets other than Heart | accuracy: less than 1% | Hurt |
| Train logistic regression on AIM synthetic data rather than real data at ε=2 | Logistic regression · Public datasets other than Heart | excess empirical risk: less than 0.02 | Hurt |
| Train logistic regression on AIM synthetic data rather than real data at ε=2 | Logistic regression · Heart | accuracy: 2.2% | Hurt |
| Train logistic regression on AIM synthetic data rather than real data at ε=2 | Logistic regression · Heart | excess empirical risk: 0.032 | Hurt |
| Increase the privacy budget ε (ablation) | AIM synthetic data and downstream logistic regression · Six public datasets | accuracy | Helped |
| Increase the privacy budget ε (ablation) | AIM synthetic data and downstream logistic regression · Six public datasets | excess empirical risk | Helped |
| Increase the privacy budget ε (ablation) | AIM synthetic data · Six public datasets | normalized-ℓ1 marginal error | Helped |
| Use the 9-iteration Bernstein approximation instead of the minimax approximation (ablation) | Degree-4 approximation of log(sigmoid(x)) on [-5, 5] · Approximation error | approximation error: 0.061 -> 0.057 | Helped |
| Increase Bernstein approximation iterations from 1 to 4 to 9 (ablation) | Degree-4 approximation of log(sigmoid(x)) on [-5, 5] · Approximation error | approximation error: 0.545 -> 0.100 -> 0.057 | Helped |
| Increase polynomial degree (ablation) | Minimax and iterated Bernstein approximations · Approximation error | approximation error | Helped |
Surprising findings
- Experimental excess risk is well below the worst-case lower bound, suggesting real-world data is easier than the adversarial construction.
Limitations
- Theoretical synthetic data mechanism is computationally inefficient (brute-force search over datasets).
- Analysis restricted to discrete attributes with linear models and convex Lipschitz losses.
- Lower bound is for a worst-case distribution and does not capture real datasets.
Experimental setup
Datasets: Adult Compas Churn Dutch Law Heart
Benchmarks: Adult Compas Churn Dutch Law Heart
Metrics: accuracy ROC-AUC excess empirical risk normalized l1 marginal error
Baselines: DP-SGD PATE real-data training
Builds on: AIM Private-PGM Bernstein polynomial approximation DP-SGD PATE
Closest papers by meaning
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.89)
- Privacy Amplification Through Synthetic Data: Insights from Linear Regression (ICML 2025 · similarity 0.88)
- Does Training with Synthetic Data Truly Protect Privacy? (ICLR 2025 · similarity 0.87)
- It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.86)
- Analysis of Differentially Private Synthetic Data: A Measurement Error Approach (AAAI 2024 · similarity 0.86)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.