Abstract | ||
---|---|---|
We study a learner-private sequential learning problem, motivated by the privacy and security concerns due to eavesdropping attacks. 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. We develop new querying strategies and analytical techniques and use them to prove almost-matching upper and lower bounds on the optimal query complexity, obtaining a complete characterization of the optimal query complexity as a function of the estimation accuracy and the desired levels of privacy. |
Year | Venue | DocType |
---|---|---|
2021 | 24TH INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS (AISTATS) | Conference |
Volume | ISSN | Citations |
130 | 2640-3498 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xu, Jiaming | 1 | 25 | 2.38 |
Kuang Xu | 2 | 137 | 17.59 |
Dana Yang | 3 | 0 | 1.01 |