Private Evaluation of High-Dimensional Functions

Mohammad Afzali; Hassan Ashtiani; Adam Smith

stat.MLOct 17, 2026

Private Evaluation of High-Dimensional Functions

Authors: Mohammad Afzali, Hassan Ashtiani, Adam Smith

Organizations: University of British Columbia. · McMaster University and the Vector Institute. · Boston University.

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.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

\displaystyle q(S,j)=\frac{1}{2}\max_{I\in\mathcal{I}_{j}}\left\{\min\left\{\min_{p\in I}\mathcal{Q}(S,p)-(r-\Delta),\quad r-\max_{p\in(I^{\otimes 3})^{C}}\mathcal{Q}(S,p)\right\}\right\}

Appendix

Algorithm 5 Private 1-dimensional Quasi-Concave Optimization

\displaystyle\mathcal{Q}_{i}(S,y):=\max_{(y_{i+1}^{*},\ldots,y_{d}^{*})\in\mathbb{R}^{d-i}}\mathcal{Q}\bigl(S,(\hat{y}_{1},\ldots,\hat{y}_{i-1},y,y_{i+1}^{*},\ldots,y_{d}^{*})\bigr).

Appendix

Algorithm 6 High-dimensional Quasi-Concave Optimization

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 274 papers

Nov 17, 2025

On the Gradient Complexity of Private Optimization with Private Oracles

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time

Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})

is necessary to achieve

α

excess risk on problems of dimension

d

when

d \geq 1/α^2

. Upper bounds via DP-SGD show these results are tight when

d>\tildeΩ(1/α^4)

. We further show our lower bound can be strengthened to

Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})

for algorithms which use minibatches of size at most

\bar{m} < \sqrt{d}

. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by

\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)

, where

n

is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most

Γ

-bits of information about the gradients in the minibatch, then

Ω\big(\min\{\frac{d}{α^2Γ}, \frac{d}{\log(1/α)}\}\big)

oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

Michael Menart, Aleksandar Nikolov

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto

Query Complexity Oracle Complexity Differentially Private Stochastic Gradient Descent Differential Privacy Gradient Quantization Nonsmooth Convex Optimization+1

Ask PDF

Feb 27, 2026

Challenges in Enabling Private Data Valuation

Data valuation methods quantify how individual training examples contribute to a model's behavior, and are increasingly used for dataset curation, auditing, and emerging data markets. As these techniques become operational, they raise serious privacy concerns: valuation scores can reveal whether a person's data was included in training, whether it was unusually influential, or what sensitive patterns exist in proprietary datasets. This motivates the study of privacy-preserving data valuation. However, privacy is fundamentally in tension with valuation utility under differential privacy (DP). DP requires outputs to be insensitive to any single record, while valuation methods are explicitly designed to measure per-record influence. As a result, naive privatization often destroys the fine-grained distinctions needed to rank or attribute value, particularly in heterogeneous datasets where rare examples exert outsized effects. In this work, we analyze the feasibility of DP-compatible data valuation. We identify the core algorithmic primitives across common valuation frameworks that induce prohibitive sensitivity, explaining why straightforward DP mechanisms fail. We further derive design principles for more privacy-amenable valuation procedures and empirically characterize how privacy constraints degrade ranking fidelity across representative methods and datasets. Our results clarify the limits of current approaches and provide a foundation for developing valuation methods that remain useful under rigorous privacy guarantees.

Yiwei Fu, Tianhao Wang, Varun Chandrasekaran

University of Illinois Urbana-Champaign · ∗University of Virginia

Data Valuation Privacy-Utility Tradeoff Differential Privacy

Ask PDF

May 13, 2026

Min-Max Optimization Requires Exponentially Many Queries

We study the query complexity of min-max optimization of a nonconvex-nonconcave function

f

over

[0,1]^d \times [0,1]^d

. We show that, given oracle access to

f

and to its gradient

\nabla f

, any algorithm that finds an

\varepsilon

-approximate stationary point must make a number of queries that is exponential in

1/\varepsilon

d

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

Bocconi University · Politecnico di Milano · University of Oxford

Query Complexity Oracle Complexity Min-Max Optimization Nonconvex Optimization

Ask PDF

Abstract

Differential Privacy

Explore similar work

On the Gradient Complexity of Private Optimization with Private Oracles

Challenges in Enabling Private Data Valuation

Min-Max Optimization Requires Exponentially Many Queries