Research map / Federated learning and privacy / Differential privacy
Credit Attribution and Stable Compression
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.
Introduces counterfactual credit attribution and sample DP-compression, relaxations of differential privacy that let k credited datapoints be used non-stably, and characterizes PAC learnability under these notions.
Problem
Formalizing credit attribution for machine learning algorithms: learners should be allowed to use a designated subset of training points non-stably if those points are credited, while all other points should have no significant influence on the output.
Approach
Define (eps,delta)-counterfactual credit attribution (CCA), where non-credited points must have near-zero influence via an omission-based DP-style guarantee, and sample DP-compression schemes where the compression index selection is DP. These generalize DP, semi-DP with public data, and stable sample compression, and are analyzed within PAC learning.
Key results
- PAC learning with credit attribution equals PAC learning: any VC-dimension d class is learnable with (0,0)-CCA using k=O(d log n) credited examples via randomized AdaBoost compression.
- Dichotomy for sample DP-compression: either the class is DP-learnable, or any sample DP-compression scheme requires k=Omega(1/alpha) credited points.
- Expected fraction of credited points from an event E is bounded between p e^{-eps} and p e^{eps} (up to delta n terms), showing exp(eps) factor is asymptotically optimal.
Surprising findings
- Sample DP-compression offers no expressivity advantage over semi-DP learners in the PAC setting.
Experimental setup
Metrics: sample complexity compression size
Builds on: differential privacy stable sample compression semi-private learning randomized sample compression (Moran et al.)
Closest papers by meaning
- It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.84)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.84)
- CPR: Retrieval Augmented Generation for Copyright Protection (CVPR 2024 · similarity 0.84)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.83)
- Blameless Users in a Clean Room: Defining Copyright Protection for Generative Models (NeurIPS 2025 · similarity 0.83)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.82)
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.