Pure Differential Privacy for Functional Summaries with a Laplace-like Process

1. Problem Statement

The paper addresses the challenge of achieving Pure Differential Privacy ($\epsilon$-DP) for infinite-dimensional functional summaries (e.g., mean functions, density curves) in a separable Hilbert space.

• Limitations of Existing Methods: Current approaches typically embed infinite-dimensional functional data into finite-dimensional subspaces (using basis expansions like Fourier or polynomials) and apply standard multivariate DP mechanisms (e.g., adding i.i.d. Laplace noise to coefficients).
  • Trade-off Issues: These methods require a predetermined dimension $M$, creating a rigid trade-off between utility (bias) and privacy.
  • Uniform Noise Injection: They treat all dimensions equally, failing to account for the varying importance of coefficients across different dimensions, often injecting excessive noise into "important" components.
  • Impossibility of Pure DP: Theoretical results show that adding elliptical distributions (like Gaussian processes) to infinite-dimensional spaces generally only achieves $(\epsilon, \delta)$-DP, not pure $\epsilon$-DP.

2. Methodology: The ICLP Mechanism

The authors propose the Independent Component Laplace Process (ICLP) mechanism, which treats functional summaries and noise as truly infinite-dimensional objects without finite-dimensional truncation.

Core Concept

The mechanism releases a privatized summary $\tilde{f}_D = f_D + \sigma Z$, where $Z$ is an ICLP noise process.

• Definition of ICLP: $Z$ is defined via a Karhunen-Loève expansion:
  $$Z = \sum_{j=1}^{\infty} \sqrt{\lambda_j} Z_j \phi_j$$
  where $\{\lambda_j, \phi_j\}$ are the eigenvalues and eigenfunctions of a covariance operator $C$, and $Z_j$ are independent Laplace random variables with mean 0 and variance 1.
• Feasibility Conditions:
  • Unlike Gaussian mechanisms where the difference between adjacent datasets must lie in the Cameron-Martin space ($H_C$), the ICLP mechanism requires the difference $f_D - f_{D'}$ to lie in a stricter subspace, $H_{1,C}$.
  • $H_{1,C}$ is defined by the norm $\|h\|_{1,C} = \sum_{j=1}^\infty \frac{|\langle h, \phi_j \rangle|}{\sqrt{\lambda_j}} < \infty$.
  • Theorem: If $f_D - f_{D'} \in H_{1,C}$, there exists a finite scaling factor $\sigma = \Delta/\epsilon$ (where $\Delta$ is the global sensitivity in the $\|\cdot\|_{1,C}$ norm) such that the mechanism satisfies $\epsilon$-DP.

Constructing Qualified Summaries

To ensure the functional summary $f_D$ satisfies the $H_{1,C}$ condition, the authors propose using Regularized Empirical Risk Minimization (ERM):

1. ICLP-AR (Absolute Regularization): Uses an $\ell_1$-type penalty $\|f\|_{1,C_\eta}$. While theoretically sound, it introduces soft-thresholding bias.
2. ICLP-QR (Quadratic Regularization): Uses a squared $\ell_2$-type penalty $\|f\|_{C_\eta}^2$ where $\eta > 1$. This maps the solution into a power space $H_{C_\eta}$, which is a subset of $H_{1,C}$, ensuring feasibility while maintaining smoothness.

Parameter Selection (PSS)

To avoid privacy leakage from data-driven tuning (like Cross-Validation), the authors propose Privacy-Safe Selection (PSS). This method selects regularization parameters based solely on the sample size, privacy budget, and the covariance structure of the noise, rather than the data itself.

3. Key Contributions

1. Novel Mechanism: Introduction of the ICLP mechanism, the first additive noise mechanism to achieve pure $\epsilon$-DP for infinite-dimensional functional objects without finite-dimensional embedding.
2. Theoretical Feasibility: Proved that $\epsilon$-DP is achievable if the sensitivity of the summary lies in the specific subspace $H_{1,C}$. This contrasts with Gaussian mechanisms which are limited to $(\epsilon, \delta)$-DP in infinite dimensions.
3. Utility-Privacy Trade-off Analysis:
   • Demonstrated that by oversmoothing the non-private summary (choosing $\eta > 1$ in ICLP-QR), the privacy error can be made asymptotically negligible ($o(n^{-1})$) compared to the estimation error.
   • This leads to a "free privacy" phenomenon where the private estimator achieves the same optimal convergence rate as the non-private estimator.
4. General Applicability: The framework is extended beyond mean estimation to Kernel Density Estimation (KDE) and general regularized learning problems (e.g., non-parametric regression).
5. Continuous Function Extension: Extended the mechanism to the space of continuous functions $C(T)$, allowing for the release of point-wise evaluations, which are not measurable in $L^2$.

4. Experimental Results

The authors evaluated ICLP against Finite-Dimensional Representation-wise Laplace (FRL), Bernstein mechanisms, and Gaussian Process-based $(\epsilon, \delta)$-DP (GP-ADP).

• Synthetic Mean Function Protection:
  • ICLP-QR consistently outperformed FRL and Bernstein mechanisms, especially as the complexity of the mean function increased.
  • FRL suffered from high estimation error due to truncation bias, while ICLP-QR captured local details effectively.
  • ICLP-QR achieved lower privacy-estimation error than GP-ADP in many scenarios, despite GP-ADP having a relaxed privacy guarantee ($\delta > 0$).
• Kernel Density Estimation:
  • In univariate and multivariate settings, ICLP-QR produced privatized density curves/surfaces that closely matched non-private estimates, even with complex multimodal distributions.
  • Bernstein mechanisms struggled with tail behavior and required high lattice numbers to capture peaks, leading to "messy" outputs.
• Real-World Applications:
  • Medical (DTI) & Energy Data: ICLP-QR provided privatized mean functions that preserved the shape and local details of the original data significantly better than FRL.
  • Human Mortality Data: The mechanism successfully privatized age-at-death distributions across various global regions, handling both unimodal (developed regions) and multimodal (developing regions) distributions effectively.

5. Significance and Conclusion

This paper represents a significant theoretical and practical advancement in functional data privacy.

• Theoretical Breakthrough: It resolves the impossibility of pure $\epsilon$-DP for infinite-dimensional objects by introducing a non-elliptical noise process (ICLP) and identifying the precise subspace ($H_{1,C}$) required for feasibility.
• Practical Utility: By leveraging regularization to "oversmooth" data, the method achieves free privacy, meaning the cost of privacy does not degrade the statistical convergence rate.
• Future Directions: The authors note that the current implementation relies on Karhunen-Loève expansions, which can be computationally expensive ($O(n^3)$). Future work should focus on developing computationally efficient approximations that do not require full eigen-decomposition.

In summary, the ICLP mechanism offers a robust, theoretically grounded, and highly effective solution for releasing private functional summaries, overcoming the limitations of dimensionality reduction and uniform noise injection inherent in previous approaches.