Query Complexity of Bayesian Private Learning
This addresses privacy-preserving learning in adversarial settings, providing tight bounds for query complexity, though it is incremental as it builds on existing methods like Fano's inequality.
The paper tackles the problem of Bayesian private learning, where a learner aims to locate a random target within an interval using queries while concealing it from an adversary, and shows that the query complexity is on the order of L log(1/ε) to estimate within error ε with privacy parameter L.
We study the query complexity of Bayesian Private Learning: a learner wishes to locate a random target within an interval by submitting queries, in the presence of an adversary who observes all of her queries but not the responses. How many queries are necessary and sufficient in order for the learner to accurately estimate the target, while simultaneously concealing the target from the adversary? Our main result is a query complexity lower bound that is tight up to the first order. We show that if the learner wants to estimate the target within an error of $\varepsilon$, while ensuring that no adversary estimator can achieve a constant additive error with probability greater than $1/L$, then the query complexity is on the order of $L\log(1/\varepsilon)$, as $\varepsilon \to 0$. Our result demonstrates that increased privacy, as captured by $L$, comes at the expense of a {multiplicative} increase in query complexity. Our proof method builds on Fano's inequality and a family of proportional-sampling estimators. As an illustration of the method's wider applicability, we generalize the complexity lower bound to settings involving high-dimensional linear query learning and partial adversary observation.