Differentially Private Stochastic Linear Bandits:(Almost) for Free

Differentially Private Stochastic Linear Bandits:(Almost) for Free. Hanna, O. A, Girgis, A. M, Fragouli, C., & Diggavi, S. arXiv preprint arXiv:2207.03445, 2022.

Arxiv abstract bibtex 11 downloads

In this paper, we propose differentially private algorithms for the problem of stochastic linear bandits in the central, local and shuffled models. In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In particular, we achieve a regret of Õ(T‾‾√+1ϵ) matching the known lower bound for private linear bandits, while the best previously known algorithm achieves Õ(1ϵT‾‾√). In the local case, we achieve a regret of Õ(1ϵT‾‾√) which matches the non-private regret for constant ϵ, but suffers a regret penalty when ϵ is small. In the shuffled model, we also achieve regret of Õ(T‾‾√+1ϵ) %for small ϵ as in the central case, while the best previously known algorithm suffers a regret of Õ(1ϵT3/5). Our numerical evaluation validates our theoretical results.

@article{hanna2022differentially,
  title={Differentially Private Stochastic Linear Bandits:(Almost) for Free},
  author={Hanna, Osama A and Girgis, Antonious M and Fragouli, Christina and Diggavi, Suhas},
  journal={arXiv preprint arXiv:2207.03445},
  year={2022},
  tags={journalSub,DML,PDL},
  type={1},
  url_arxiv={https://arxiv.org/abs/2207.03445},
  abstract={In this paper, we propose differentially private algorithms for the problem of stochastic linear bandits in the central, local and shuffled models. In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In particular, we achieve a regret of Õ(T‾‾√+1ϵ) matching the known lower bound for private linear bandits, while the best previously known algorithm achieves Õ(1ϵT‾‾√). In the local case, we achieve a regret of Õ(1ϵT‾‾√) which matches the non-private regret for constant ϵ, but suffers a regret penalty when ϵ is small. In the shuffled model, we also achieve regret of Õ(T‾‾√+1ϵ) %for small ϵ as in the central case, while the best previously known algorithm suffers a regret of Õ(1ϵT3/5). Our numerical evaluation validates our theoretical results.},
}

Downloads: 11

{"_id":"QNtuJeeuvJyW9mnti","bibbaseid":"hanna-girgis-fragouli-diggavi-differentiallyprivatestochasticlinearbanditsalmostforfree-2022","author_short":["Hanna, O. A","Girgis, A. M","Fragouli, C.","Diggavi, S."],"bibdata":{"bibtype":"article","type":"1","title":"Differentially Private Stochastic Linear Bandits:(Almost) for Free","author":[{"propositions":[],"lastnames":["Hanna"],"firstnames":["Osama","A"],"suffixes":[]},{"propositions":[],"lastnames":["Girgis"],"firstnames":["Antonious","M"],"suffixes":[]},{"propositions":[],"lastnames":["Fragouli"],"firstnames":["Christina"],"suffixes":[]},{"propositions":[],"lastnames":["Diggavi"],"firstnames":["Suhas"],"suffixes":[]}],"journal":"arXiv preprint arXiv:2207.03445","year":"2022","tags":"journalSub,DML,PDL","url_arxiv":"https://arxiv.org/abs/2207.03445","abstract":"In this paper, we propose differentially private algorithms for the problem of stochastic linear bandits in the central, local and shuffled models. In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In particular, we achieve a regret of Õ(T‾‾√+1ϵ) matching the known lower bound for private linear bandits, while the best previously known algorithm achieves Õ(1ϵT‾‾√). In the local case, we achieve a regret of Õ(1ϵT‾‾√) which matches the non-private regret for constant ϵ, but suffers a regret penalty when ϵ is small. In the shuffled model, we also achieve regret of Õ(T‾‾√+1ϵ) %for small ϵ as in the central case, while the best previously known algorithm suffers a regret of Õ(1ϵT3/5). Our numerical evaluation validates our theoretical results.","bibtex":"@article{hanna2022differentially,\n title={Differentially Private Stochastic Linear Bandits:(Almost) for Free},\n author={Hanna, Osama A and Girgis, Antonious M and Fragouli, Christina and Diggavi, Suhas},\n journal={arXiv preprint arXiv:2207.03445},\n year={2022},\n tags={journalSub,DML,PDL},\n type={1},\n url_arxiv={https://arxiv.org/abs/2207.03445},\n abstract={In this paper, we propose differentially private algorithms for the problem of stochastic linear bandits in the central, local and shuffled models. In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In particular, we achieve a regret of Õ(T‾‾√+1ϵ) matching the known lower bound for private linear bandits, while the best previously known algorithm achieves Õ(1ϵT‾‾√). In the local case, we achieve a regret of Õ(1ϵT‾‾√) which matches the non-private regret for constant ϵ, but suffers a regret penalty when ϵ is small. In the shuffled model, we also achieve regret of Õ(T‾‾√+1ϵ) %for small ϵ as in the central case, while the best previously known algorithm suffers a regret of Õ(1ϵT3/5). Our numerical evaluation validates our theoretical results.},\n}\n\n","author_short":["Hanna, O. A","Girgis, A. M","Fragouli, C.","Diggavi, S."],"key":"hanna2022differentially","id":"hanna2022differentially","bibbaseid":"hanna-girgis-fragouli-diggavi-differentiallyprivatestochasticlinearbanditsalmostforfree-2022","role":"author","urls":{" arxiv":"https://arxiv.org/abs/2207.03445"},"metadata":{"authorlinks":{}},"downloads":11},"bibtype":"article","biburl":"https://bibbase.org/network/files/e2kjGxYgtBo8SWSbC","dataSources":["jxCYzXXYRqw2fiEXQ","wCByFFrQMyRwfzrJ6","yuqM5ah4HMsTyDrMa","YaM87hGQiepg5qijZ","n9wmfkt5w8CPqCepg","soj2cS6PgG8NPmWGr","FaDBDiyFAJY5pL28h","ycfdiwWPzC2rE6H77","2BHqTGHtDg7BjRAJQ","XpqzCLvCgsYBqbTpK","QNNZyNQzfeETJyTbL","Z6bBhKezwKd3pPWRc"],"keywords":[],"search_terms":["differentially","private","stochastic","linear","bandits","free","hanna","girgis","fragouli","diggavi"],"title":"Differentially Private Stochastic Linear Bandits:(Almost) for Free","year":2022,"downloads":11}