  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.
