Private Sequential Learning

We formulate a private learning model to study an intrinsic tradeoff between privacy and query complexity in sequential learning. Our model involves a learner who aims to determine a scalar value, v*, by sequentially querying an external database with binary responses. In the meantime, an adversary observes the learner's queries, though not the responses, and tries to infer from them the value of v*. The objective of the learner is to obtain an accurate estimate of v* using only a small number of queries, while simultaneously protecting her privacy by making v* provably difficult to learn for the adversary. Our main results provide tight upper and lower bounds on the learner's query complexity as a function of desired levels of privacy and estimation accuracy. We also construct explicit query strategies whose complexity is optimal up to an additive constant.