No-Regret Algorithms for Private Gaussian Process Bandit Optimization

Abstract

The widespread proliferation of data-driven decision-making has ushered in a recent interest in the design of privacy-preserving algorithms. In this paper, we consider the ubiquitous problem of gaussian process (GP) bandit optimization from the lens of privacy-preserving statistics. We propose a solution for differentially private GP bandit optimization that combines a uniform kernel approximator with random perturbations, providing a generic framework to create differentially-private (DP) Gaussian process bandit algorithms. For two specific DP settings - joint and local differential privacy, we provide algorithms based on efficient quadrature Fourier feature approximators, that are computationally efficient and provably no-regret for popular stationary kernel functions. Our algorithms maintain differential privacy throughout the optimization procedure and critically do not rely explicitly on the sample path for prediction, making the parameters straightforward to release as well.

arXiv commentAISTATS21 Camera Ready v1

References in corpus (11)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• RecoGym: A Reinforcement Learning Environment for the problem of Product Recommendation in Online Advertising
• Local Differential Privacy: a tutorial
• Quadrature-based features for kernel approximation
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Differentially Private Bayesian Optimization
• On Kernelized Multi-armed Bandits
• Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?
• Personalized Gaussian Processes for Future Prediction of Alzheimer's Disease Progression
• Differentially Private Gaussian Processes