Optimal query complexity for private sequential learning against eavesdropping

Jiaming Xu, Kuang Xu, Dana Yang
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2296-2304, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-xu21f, title = { Optimal query complexity for private sequential learning against eavesdropping }, author = {Xu, Jiaming and Xu, Kuang and Yang, Dana}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2296--2304}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/xu21f/xu21f.pdf}, url = {https://proceedings.mlr.press/v130/xu21f.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Optimal query complexity for private sequential learning against eavesdropping %A Jiaming Xu %A Kuang Xu %A Dana Yang %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-xu21f %I PMLR %P 2296--2304 %U https://proceedings.mlr.press/v130/xu21f.html %V 130 %X 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.
APA
Xu, J., Xu, K. & Yang, D.. (2021). Optimal query complexity for private sequential learning against eavesdropping . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2296-2304 Available from https://proceedings.mlr.press/v130/xu21f.html.

Related Material