Research map / Federated learning and privacy / Differential privacy
Privately Learning Smooth Distributions on the Hypercube by Projections
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 a centrally zCDP estimator for Sobolev-smooth densities on the hypercube via noisy Fourier projections, extended to real smoothness and arbitrary dimension, with a privacy-aware Lepskii method for adaptivity to unknown smoothness.
Problem
Estimating a density on [0,1]^d under central zero-concentrated differential privacy when the smoothness level beta is unknown and may be non-integer, with the privacy-utility trade-off made explicit.
Approach
Private projection (Fourier) estimators with Gaussian noise on coefficients are analyzed in general dimension and for real Sobolev smoothness via Hölder remainders; adaptivity is obtained by a Lepskii-style selection whose penalization includes a privacy-variance term, with composition over a finite grid of models.
Key results
- Private projection estimator with noise calibrated to rho-zCDP achieves E||f - f_hat||^2 <= C (M+1)^(-2beta) with M chosen as a min of sampling and privacy cutoffs, matching the lower bound max{n^(-2beta/(2beta+d)), (n sqrt(rho))^(-2beta/(beta+d))} up to constants.
- Adaptive Lepskii-based selection with privacy-aware penalization attains the minimax rate up to a log factor in the privacy term without knowing beta, using a grid of about log^2 n candidate smoothness values.
- Results extend from integer to real smoothness beta>0 and arbitrary dimension d, with the dimension entering the rate exponents.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Tune the Fourier projection rank using the known smoothness β | Private projection estimator · Sobolev-smooth densities on [0, 1]^d | expected squared L2 error: r_{n,\rho}(\beta) := \max \left\{ n^{-\frac{2 \beta}{2 \beta + d}}, (n \sqrt{\rho})^{- \frac{2 \beta}{\beta+d}} \right\} | Helped |
| Adaptively select the projection rank with the privacy-aware Lepskii rule, without prior knowledge of β | Private projection estimator · Sobolev-smooth densities on [0, 1]^d | expected L2 error: 2 \sqrt{ r_{n,\rho_n'}(\beta)^* } \exp\left( \frac{\varepsilon}{\beta+ d}\right) | Helped |
| Use estimated-bias penalization to select the projection rank | Private projection estimator · Sobolev-smooth densities on [0, 1]^d | expected squared L2 error: C_1 \max \Bigg\{ n^{-\frac{2 \beta}{2 \beta + d}} , \p{\frac{n \sqrt{\rho}}{\sqrt{\log_2\p{n}}}}^{- \frac{2 \beta}{\beta | Helped |
Limitations
- Adaptive oracle result requires an assumption on the sup norm of f (||f||_inf) that appears to be a technical artifact.
- Adaptive selection incurs polylogarithmic degradation in the privacy term.
- Main text presents integer smoothness; real-smoothness results rely on appendix technical details.
Experimental setup
Metrics: expected squared L2 error minimax rate
Baselines: Lalanne et al. 2023 Lipschitz density estimator under pure DP non-private projection estimator
Builds on: Lalanne et al. 2023 one-dimensional private density estimation Lepskii method zero-concentrated differential privacy Assouad's lemma
Closest papers by meaning
- On Differentially Private Sampling from Gaussian and Product Distributions (NeurIPS 2023 · similarity 0.89)
- Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions (NeurIPS 2022 · similarity 0.87)
- On Differentially Private U Statistics (NeurIPS 2024 · similarity 0.86)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.86)
- Dimension-free Private Mean Estimation for Anisotropic Distributions (NeurIPS 2024 · similarity 0.85)
- Sample-Efficient Private Learning of Mixtures of Gaussians (NeurIPS 2024 · similarity 0.85)
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.