Source-linked AI summary
Differential Privacy for Functions and Functional Data
Rob Hall, Alessandro Rinaldo, Larry Wasserman
TL;DR
Existing differential-privacy methods considered finite-dimensional vector outputs, while many data summaries and analyses are functions. This paper adds a Gaussian process calibrated by RKHS sensitivity to release functions privately, demonstrating applications including kernel density estimation and supervised learning.
Problem
Differential-privacy methods primarily addressed finite-dimensional vector outputs, although data and statistical analyses can naturally involve functions.
Method
The paper adds a Gaussian process to the target function, calibrating its noise level to the function's sensitivity measured in an RKHS norm.
Results
The developed theory yields a private kernel density estimator and applies to regression and classification functions.
Takeaways & Limitations
The method provides a way to add random noise to functions while preserving differential privacy across functional-data applications.
Takeaways & Limitations
Bandwidth selection is not addressed when the bandwidth is data-dependent; it requires a differentially private bandwidth and differential-privacy composition.
Abstract
from arXiv · showhide
Differential privacy is a framework for privately releasing summaries of a database. Previous work has focused mainly on methods for which the output is a finite dimensional vector, or an element of some discrete set. We develop methods for releasing functions while preserving differential privacy. Specifically, we show that adding an appropriate Gaussian process to the function of interest yields differential privacy. When the functions lie in the same RKHS as the Gaussian process, then the correct noise level is established by measuring the "sensitivity" of the function in the RKHS norm. As examples we consider kernel density estimation, kernel support vector machines, and functions in reproducing kernel Hilbert spaces.
1 Introduction
The paper extends differential privacy from finite-dimensional or discrete outputs to function-valued data. It calibrates Gaussian-process noise using RKHS sensitivity and applies the framework to density estimation, SVM learning, and other function outputs.
- Differential privacy releases database summaries while limiting how strongly the output distribution depends on any single individual.
- Previous differential-privacy algorithms primarily treated real-valued vectors, whereas this paper addresses outputs and possibly inputs consisting of functions.
- Adding Gaussian-process noise calibrated to RKHS sensitivity provides differential privacy for function outputs.
- Function-valued data arise naturally in growth curves, temperature profiles, and economic indicators, and also as statistical summaries such as density estimates.
- A private density estimator can support release of a differentially private sample for subsequent exploratory analysis and model fitting.
- The framework produces private kernel density estimators and applies to regression, classification, kernel SVM learning, and broader classes of functions.
2 Differential Privacy
This section formalizes differential privacy for randomized database algorithms and develops finite-dimensional Gaussian-noise arguments that support later function-valued releases. It also emphasizes measurable-space details and derives testing implications of approximate privacy.
- Databases contain individual rows, and neighboring databases have the same size but differ in one element.
- Randomized algorithms are represented by output distributions indexed by databases, with outputs taking values in a measurable space.
- Approximate differential privacy requires the neighboring-database inequality for all measurable output events, with parameters α and β.
- For function-valued outputs, the choice of σ-field matters because using the finest available σ-field makes the privacy definition strongest.
- 2.1 Differential Privacy of Finite Dimensional Vectors: The vector-valued mechanism calibrates Gaussian noise to sensitivity measured in a Mahalanobis distance, extending the usual Euclidean sensitivity setting.
- 2.1 Differential Privacy of Finite Dimensional Vectors: The Gaussian-measure proof bounds density ratios on suitable sets and uses the resulting inequalities to establish approximate differential privacy.
- 2.1 Differential Privacy of Finite Dimensional Vectors: The vector result applies when the output is a real vector whose dimension does not depend on the database, including examples such as mean vectors.
- 2.2 The Implications of Approximate Differential Privacy: Under (α, β)-differential privacy, any level-γ test distinguishing one database from another has power at most γe^α + β.
3 Approximate Differential Privacy for Functions
The paper extends approximate differential privacy from finite-dimensional outputs to function spaces by analyzing finite and countable evaluations. It proposes Gaussian-process releases and connects privacy calibration to RKHS structure.
- Function-space privacy: Function-valued privacy is formulated through probability measures on function spaces, with practical algorithms evaluating released functions on finite or countable point sets.The construction uses cylinder sets generated by function evaluations and extends finite-dimensional guarantees to the generated sigma-field.
- Function-space privacy: Privacy on the field of cylinder sets implies (α, β)-differential privacy for every finite, a-priori chosen evaluation vector.The result applies to releases of (f̃_D(x1), . . . , f̃_D(xn)) at any finite set of points.
- Function-space privacy: For continuous released functions on C[0, 1], privacy over the cylinder-generated sigma-field extends to the Borel sigma-field under the uniform norm.This extension relies on the correspondence between the restricted sigma-field and the Borel sigma-field induced by ∥f∥∞.
- Alternative mechanism: The exponential mechanism can release a function by sampling from a finite approximating set, but utility may require a very large set and costly normalization.Computing probabilities for every candidate function can be extremely time consuming, especially when maintaining utility matters.
- Gaussian-process mechanism: The proposed alternative uses Gaussian-process measures over functions, transferring finite-dimensional Gaussian privacy arguments to function-space releases.The Gaussian process is characterized by finite-dimensional Gaussian projections, while the main privacy result applies to releases formed from a database-indexed function family and Gaussian-process sample paths.
- Gaussian-process mechanism: For functions in the RKHS associated with the Gaussian-process covariance kernel, privacy is established using an RKHS-based bound for the function family.The relevant proposition applies to any finite sequence of distinct evaluation points and the RKHS corresponding to kernel K.
4 Examples
The paper applies Gaussian-process privacy mechanisms to kernel density estimation, RKHS functions, and kernel SVMs. These examples show a trade-off between generality and noise level, while private bandwidth selection remains an additional requirement.
- Non-Isotropic Kernels: For non-isotropic Gaussian kernels, a fixed positive definite bandwidth matrix H can be used while preserving the Gaussian-process privacy construction.Different coordinates may use different bandwidths when H is fixed a-priori.
- Kernel Density Estimation: The private kernel density estimator preserves the original estimator’s gross features, including its two peaks.The example uses n = 100, h = 0.1, α = 1, and β = 0.1.
- Private Choice of Bandwidth: Data-dependent bandwidth selection is not covered by the fixed-bandwidth analysis and requires a private version of the bandwidth estimator plus differential-privacy composition.The paper discusses private cross-validation and private interquartile-range methods as possible approaches.
- RKHS Functions and Kernel SVMs: The proposed methods extend private function release from kernel density estimation to Sobolev-space functions and kernel support vector machines.The paper also describes RKHS constructions based on Sobolev spaces and applies its theory to classification functions.
- Functions in a Sobolev Space: The more general Sobolev-space technique requires a noise level that grows at a higher rate as dimension d increases.The authors contrast this cost with the higher generality of the technique.
5 Algorithms
The paper describes batch and online procedures for releasing private function evaluations. Batch release samples a multivariate Gaussian, whereas online release samples conditionally on prior evaluations, with computational costs that can grow with the number of requests.
- Batch Release: Batch release returns private evaluations at a designated finite collection of points by sampling the Gaussian process’s multivariate Gaussian distribution.The released output is a vector of function evaluations.
- Online Release: Online release answers repeated evaluation requests by sampling the Gaussian process conditioned on previously released values.The procedure maintains the prior evaluation points and released function values.
- Computational Considerations: Online computation generally becomes more expensive as the number of requests increases, with constructing V_i requiring time proportional to i.The paper identifies this growth as potentially problematic in practice.
- Computational Considerations: For the covariance kernel used in Section 4.2, the conditional vector V_i lies in the span of at most two rows, enabling a more efficient online calculation.The relevant rows correspond to the closest previous points on the left and right, when applicable.
- Online Release: The conditional noise at each requested point is Gaussian with mean and variance determined by previously evaluated points and the covariance kernel.The points are sorted to identify the relevant prior evaluations for the conditional calculation.
6 Conclusion
The paper shows how to add random noise to functions while preserving differential privacy, and identifies unresolved lower-bound questions about the necessary noise level.
- The method adds random noise to a function while preserving differential privacy.
- The paper leaves the least necessary noise for privately releasing a function as an open lower-bound question.The authors note that existing lower-bound techniques do not directly extend to their β > 0 setting.
- Determining lower bounds is complicated when β > 0 because the family {P_D} is no longer mutually absolutely continuous and quantities such as KL divergence may be unbounded.
7 Appendix
The appendix analyzes an operator associated with kernel evaluations, establishing its algebraic and symmetry properties and identifying the theorem's quantity as a squared RKHS norm on a restricted subspace.
- Invertibility of the matrix is assumed based on Mercer's theorem.
- The operator P is idempotent, satisfying P = P^2.
- The operator P is self-adjoint because the matrix M is symmetric.
- The appendix derives an RKHS norm decomposition that yields the inequality ⟨f, Pf⟩_H ≥ ⟨Pf, Pf⟩_H.
- The theorem's quantity is the squared RKHS norm after restricting H to the subspace spanned by the functions Kx_i.