Private Sequential Learning

John Tsitsiklis, Kuang Xu, Zhi Xu
Proceedings of the 31st Conference On Learning Theory, PMLR 75:721-727, 2018.

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, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-tsitsiklis18a, title = {Private Sequential Learning}, author = {Tsitsiklis, John and Xu, Kuang and Xu, Zhi}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {721--727}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/tsitsiklis18a/tsitsiklis18a.pdf}, url = {https://proceedings.mlr.press/v75/tsitsiklis18a.html}, 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, 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.} }
Endnote
%0 Conference Paper %T Private Sequential Learning %A John Tsitsiklis %A Kuang Xu %A Zhi Xu %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-tsitsiklis18a %I PMLR %P 721--727 %U https://proceedings.mlr.press/v75/tsitsiklis18a.html %V 75 %X 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, 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.
APA
Tsitsiklis, J., Xu, K. & Xu, Z.. (2018). Private Sequential Learning. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:721-727 Available from https://proceedings.mlr.press/v75/tsitsiklis18a.html.

Related Material