Differentially Private High Dimensional Bandits
Apurv Shukla
We consider a high-dimensional stochastic contextual linear bandit problem
when the parameter vector is $s_{0}$-sparse and the decision maker is subject
to privacy constraints under both central and local models of differential
privacy. We present PrivateLASSO, a differentially private LASSO bandit
algorithm. PrivateLASSO is based on two sub-routines: (i) a sparse
hard-thresholding-based privacy mechanism and (ii) an episodic thresholding
rule for identifying the support of the parameter $\theta$. We prove minimax
private lower bounds and establish privacy and utility guarantees for
PrivateLASSO for the central model under standard assumptions.