Research map / Federated learning and privacy / Differential privacy
Distributed Differentially Private Data Analytics via Secure Sketching
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 the linear-transformation model, an intermediate distributed DP model where clients noise their data locally and a trusted public linear sketch (computed via secret sharing MPC) is applied, and derives low-rank approximation and ridge regression mechanisms with error independent of the number of clients.
Problem
Distributed differentially private data analysis that avoids both a single trusted server (central model) and the high noise of the local model, for problems like low-rank approximation and ridge regression.
Approach
Clients add local noise to their data, then a public linear transformation (oblivious sparse JL/OSNAP sketch) is computed securely across multiple servers via linear secret sharing; the noise from many clients aggregates through the linear sketch, reducing per-client noise and yielding error independent of the number of clients.
Key results
- Low-rank approximation LTM mechanism achieves multiplicative error (1+alpha) with additive error about O~(k d^{3/2} alpha^{-3} eps^{-1} log(1/delta)), compared with O(k sqrt(d)/eps) for central model.
- Ridge regression LTM mechanism achieves error (1+o(1)) times optimal objective plus poly(1/eps, d, log(1/delta)) under lambda >= poly(1/eps, d, log 1/delta).
- Frequency moment estimation in the LTM achieves additive error depending only on Delta, eps, delta, whereas local model incurs error of order sqrt(n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LTM instead of the local model | Frequency estimation · Frequency estimation | error: \tilde{O}(\sqrt{n}) -> \tilde{O}(\varepsilon^{-1}) | Helped |
| Use LTM instead of the local model | Low-rank approximation · Low-rank approximation | additive error: (O(k^2nd)) -> \tilde{O}(\frac{kd^{3/2}}{\alpha_\mathbf{S}^3} \varepsilon^{-1} ) | Helped |
| Use LTM instead of the central model | Low-rank approximation · Low-rank approximation | additive error: \tilde{O}(\frac{kd^{3/2}}{\alpha_\mathbf{S}^3} \varepsilon^{-1} ) vs. \tilde{\Theta}(k\sqrt{d}\varepsilon^{-1}) | Mixed |
| Use LTM instead of the central model | Frequency estimation · Frequency estimation | error: \tilde{O}(\varepsilon^{-1}) vs. \tilde{\Theta}(\varepsilon^{-1}) | No clear effect |
Surprising findings
- Existing shuffle-model DP definitions can be satisfied by mechanisms where a single client adds all the noise, motivating a stronger definition tolerating corrupt clients.
Limitations
- Requires lambda at least poly(1/eps, d, log 1/delta) for ridge regression guarantees
- Utility analysis uses specific OSNAP parameter trade-offs; results change by log factors with others
- Assumes at least one honest server and honest-majority style client assumptions for corrupted clients up to t' < n/2
Experimental setup
Metrics: multiplicative error additive error
Baselines: central model low-rank approximation (exponential mechanism) local model low-rank approximation shuffle model frequency estimation local model frequency estimation
Builds on: OSNAP shuffle model multi-central model Gaussian mechanism Laplace mechanism
Closest papers by meaning
- An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (NeurIPS 2019 · similarity 0.89)
- Privacy Amplification Through Synthetic Data: Insights from Linear Regression (ICML 2025 · similarity 0.87)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.86)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.86)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.86)
- The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches (NeurIPS 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.