Private Sequential Learning

John N. Tsitsiklis (), Kuang Xu () and Zhi Xu ()
Additional contact information
John N. Tsitsiklis: Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Kuang Xu: Graduate School of Business, Stanford University, Stanford, California 94305
Zhi Xu: Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2021, vol. 69, issue 5, 1575-1590

Abstract: 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 and receiving binary responses. In the meantime, an adversary observes the learner’s queries, although 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 his or 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.

Keywords: decision analysis: sequential; statistics: estimation; probability: stochastic model applications; Stochastic Models; sequential learning; privacy; bisection algorithm (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2021 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:5:p:1575-1590

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().