Optimal query complexity for private sequential learning against eavesdropping
arXiv:1909.09836
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. We develop new querying strategies and analytical techniques and use them to prove tight upper and lower bounds on the optimal query complexity. The bounds almost match across the entire parameter range, substantially improving upon existing results. We thus obtain a complete picture of the optimal query complexity as a function of the estimation accuracy and the desired levels of privacy. We also extend the results to sequential learning models in higher dimensions, and where the binary responses are noisy. Our analysis leverages a crucial insight into the nature of private learning problem, which suggests that the query trajectory of an optimal learner can be divided into distinct phases that focus on pure learning versus learning and obfuscation, respectively.
References in corpus (15)
- Deep Learning with Differential Privacy
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Learning: Strategies for Improving Communication Efficiency
- Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning
- How To Backdoor Federated Learning
- Learning Differentially Private Recurrent Language Models
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Differentially Private Federated Learning: A Client Level Perspective
- Generalized Byzantine-tolerant SGD
- Byzantine Stochastic Gradient Descent
- Prediction Poisoning: Towards Defenses Against DNN Model Stealing Attacks
- Infection Spreading and Source Identification: A Hide and Seek Game
- Distance-based and continuum Fano inequalities with applications to statistical estimation
- Query Complexity of Bayesian Private Learning