Skip to yearly menu bar Skip to main content


Optimal query complexity for private sequential learning against eavesdropping

Jiaming Xu · Kuang Xu · Dana Yang

Keywords: [ Ethics and Safety ] [ Privacy-preserving Statistics and Machine Learning ]


We study the query complexity of a learner-private sequential learning problem, motivated by the privacy and security concerns due to eavesdropping that arise in practical applications such as pricing and Federated Learning. A learner tries to estimate an unknown scalar value, by sequentially querying an external database and receiving binary responses; meanwhile, a third-party adversary observes the learner's queries but not the responses. The learner's goal is to design a querying strategy with the minimum number of queries (optimal query complexity) so that she can accurately estimate the true value, while the eavesdropping adversary even with the complete knowledge of her querying strategy cannot.

Chat is not available.