Private methods for accurate high-dimensional function evaluation
Private Evaluation of High-Dimensional Functions
Cryptography and SecurityData Structures and AlgorithmsInformation TheoryMachine Learning
Summary
This paper addresses how to estimate complex functions from big datasets while keeping individual data private. The authors develop a way to ask the function about slightly smaller subsets of the data to produce a good overall estimate without revealing sensitive details. They guarantee the output stays within reasonable bounds based on the function’s behavior around the data, extending previous work from simple cases to high-dimensional ones. Their method also improves how some private optimization problems are solved by reducing the required data size.
What this means in practice
- •For data privacy engineers: Implement private evaluation of complex high-dimensional analytics without revealing individual data contributions by querying subsets of the original data.
- •For machine learning engineers: Improve private user-level optimization algorithms by reducing sample overhead when optimizing quasi-concave or convex objectives on sensitive datasets.
Authors
Mohammad Afzali, Hassan Ashtiani, Adam Smith
Abstract
We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and query access to a function $f$---whose sensitivity may be unknown or unbounded---the goal is to privately output an approximation to $f(S)$. The black-box evaluator can only query the value of $f$ over a down neighborhood of $S$ (i.e., those subsets of $S$ that are obtained by removing a bounded number of elements from $S$). We design generic black-box evaluators for both pure and approximate differential privacy through a reduction to high-dimensional private quasi-concave optimization (QCO). Our black-box evaluator enjoys a geometric notion of utility. Consider the vectors obtained by applying $f$ on sets in a down neighborhood of $S$. With high probability, the evaluator's output is guaranteed to be in the convex hull of these vectors. Our work generalizes the result of Linder et al. [LRSS25] for real-valued function evaluation to high dimensions. It also recovers the private center-point guarantees of Beimel et al. [BMNS19], with an explicit additive approximation to maximum Tukey depth. We also apply our evaluators to user-level quasi-concave and convex optimization, showing how they can improve upon the sample-and-aggregate baseline of Nissim et al. [NRS07] by replacing the multiplicative data overhead with an additive overhead. Finally, we show that our formulation of high dimensional black-box evaluation and high dimensional private QCO are equivalent up to a factor of the dimension: the hardest private evaluation instances already arise from the cases that $f$ is a (non-private) quasi-concave optimizer.