Differentially Private Stochastic Linear Bandits: (Almost) for Free

2022/07/07 by Osama A. Hanna, Antonious M. Girgis, Hanna, Osama A. +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2207.03445

openalex publication_date 2022/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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)+\frac1ε) matching the known lower bound for private linear bandits, while the best previously known algorithm achieves O(\frac1ε√(T)). In the local case, we achieve a regret of O(\frac1ε√(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)+\frac1ε) %for small ε as in the central case, while the best previously known algorithm suffers a regret of O(\frac1εT^3/5). Our numerical evaluation validates our theoretical results.

Cited by

• Beyond ATE: Multi-Criteria Design for A/B Testing

Related

• Robust and differentially private stochastic linear bandits
• Faster Rates for Private Adversarial Bandits
• Differentially Private High Dimensional Bandits
• Differentially Private Contextual Linear Bandits
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits