lmath

$\displaystyle\BODY$ (1)

lmath*

$\displaystyle\BODY$

lm

# Local Differential Privacy for Bayesian Optimization

Xingyu Zhou
Department of ECE
The Ohio State University
<EMAIL_ADDRESS>This work was done during the internship of the first author
at Alibaba, USA. Jian Tan
Alibaba, USA
<EMAIL_ADDRESS>

###### Abstract

Motivated by the increasing concern about privacy in nowadays data-intensive
online learning systems, we consider a black-box optimization in the
nonparametric Gaussian process setting with local differential privacy (LDP)
guarantee. Specifically, the rewards from each user are further corrupted to
protect privacy and the learner only has access to the corrupted rewards to
minimize the regret. We first derive the regret lower bounds for any LDP
mechanism and any learning algorithm. Then, we present three almost optimal
algorithms based on the GP-UCB framework and Laplace DP mechanism. In this
process, we also propose a new Bayesian optimization (BO) method (called MoMA-
GP-UCB) based on median-of-means techniques and kernel approximations, which
complements previous BO algorithms for heavy-tailed payoffs with a reduced
complexity. Further, empirical comparisons of different algorithms on both
synthetic and real-world datasets highlight the superior performance of MoMA-
GP-UCB in both private and non-private scenarios.

##  1 Introduction

We consider the problem of maximizing an unknown function $f$ over a set
$\mathcal{D}$ via sequentially querying it and received only bandit feedback,
i.e., when we query at $x$, we observe a possibly noisy evaluation of $f(x)$.
This model has been a main focus in machine learning research, e.g., the
classic multi-armed bandit (MAB) setting [15], linear bandit setting [1] and
the general Bayesian optimization [21], with each one generalizing the
previous one. It also finds broad applications in many real-world systems,
including medical experiments, online shopping websites and recommender
systems [16]. These systems adaptively make a decision and receive rewards
(feedback) from the user to simultaneously learn insightful facts and maximize
the profit.

Recently, privacy has become a key issue in the above mentioned online
learning systems. Users have become increasingly concerned about directly
sharing their online information or activities to these systems, since these
activities may reveal their private information. For example, a customer of an
online shopping website is not willing to tell the website that he or she has
purchased medicines for mental issues. Another example is the medical
experiments in which the patient could reject to share the actual effects of
the treatment due to privacy concerns. This stimulates the need to have a
mechanism that further corrupts the feedbacks from each user to protect
privacy, which exactly fits the _locally differential private_ (LDP) model
[13, 9].

In contrast to the standard differential privacy model [11], in which the
learner collects the true data while releasing a private output to protect
privacy, in the LDP model, the learner only has access to corrupted input data
from the users. Hence, LDP often provides a much stronger privacy protection
for the user and is more appealing in real applications, especially for the
systems mentioned above [8]. To the best of our knowledge, in the setting of
online learning with bandit feedback, LDP model has only been studied
theoretically very recently. For example, in [12, 19], the authors investigate
MAB with LDP guarantee. [25] studies LDP in the linear (contextual) bandit
setting. However, LDP in the most general scenario, i.e., Bayesian
optimization (BO), remains an important open problem.

Motivated by this, in this paper, we investigate the locally differentially
private BO, in which the rewards are further corrupted to protect privacy.
Specifically, we consider a Gaussian process (GP) model for BO (also called
Gaussian process bandit setting), which directly generalizes both MAB and
linear bandit setting. The main contributions of this paper can be summarized
as follows.

Contributions. (i) We first derive the regret lower bounds for any LDP
mechanism and any learning algorithm. (ii) Then, we present three almost
optimal algorithms based on the GP-UCB framework and Laplace DP mechanism.
(iii) Our two new methods developed for handling LDP also contribute to BO
under heavy-tailed payoffs in general. In particular, one is a new truncation
method that can be applied to any sub-Weibull rewards. The other one, called
MoMA-GP-UCB, is based on median-of-means techniques and kernel approximations,
which complements previous BO algorithms for general heavy-tailed payoffs [7]
with a reduced complexity. (iv) We further conduct empirical comparisons of
different algorithms over both synthetic and real-world datasets, which
demonstrate the superior performance of our new MoMA-GP-UCB algorithm in both
private and non-private settings.

###  1.1 Related Work

In the traditional non-private case, a line of BO methods based on Gaussian
process (GP) and upper confidence bound (UCB) have been analyzed in both sub-
Gaussian [23, 6] and heavy-tailed scenarios [7]. Kernel approximation is
recently proposed to reduce complexity of GP-based BO algorithms [17, 5]. In
the private BO case, [14] studies how to privately release the BO outputs to
protect privacy (e.g., hyper-parameters of machine learning model), and hence
it belongs to the traditional DP perspective rather than LDP.

LDP model has been previously considered in MAB setting [12, 2, 19]. Recently,
it is generalized to linear contextual bandits in which both the rewards and
the contexts are corrupted for privacy [25]. There are also some other types
of DP considered in MAB and linear bandit setting (not comparable to our
work). Due to space limitations, we refer readers to [19, 25] and the
references therein.

##  2 Problem Statement and Preliminaries

We consider a sequential decision-making problem over a set $\mathcal{D}$. A
learning policy is adopted to select an action $x_{t}\in\mathcal{D}$ at each
discrete time slot $t=1,2,\ldots$ with the corresponding reward observation
$y_{t}=f(x_{t})+\eta_{t}$, i.e., $y_{t}$ could be a noisy version of
$f(x_{t})$. Then, the reward $y_{t}$ will be further corrupted to protect
privacy, and only the private response $\bar{y}_{t}$ is revealed to the
learning agent. The action $x_{t}$ is chosen based on the arms played and the
private rewards obtained until $t-1$, denoted by the history
$\mathcal{H}_{t-1}=\\{(x_{s},\bar{y}_{s}):s\in[t-1]\\}$111For any positive
integer, we define [m]:={1,2, …, m}. The objective is to simultaneously
preserve LDP and minimize the cumulative regret defined as

$\displaystyle R_{T}=\sum_{t=1}^{T}f(x^{*})-f(x_{t}),$ (2)

where $x^{*}=\arg\max_{x\in\mathcal{D}}f(x)$ (assuming the maximum is
attained).

######  Definition 1 ($(\epsilon,\delta)$-LDP).

A randomized mechanism $\mathcal{Q}:\mathcal{D}\to\mathcal{Z}$ is said to
protect $(\epsilon,\delta)$-LDP if for any $x,x^{\prime}\in\mathcal{D}$, and
any measurable subset $E\in\mathcal{Z}$, there is

$\displaystyle\mathbb{P}\\{M(x)\in E\\}\leq
e^{\epsilon}\mathbb{P}\\{M(x^{\prime})\in E\\}+\delta,$

for $\epsilon\geq 0$ and $\delta\geq 0$. Moreover, if $\delta=0$, we say it
protects $\epsilon$-LDP.

Note that, if not explicitly stated, LDP in this paper means $\epsilon$-LDP
(stronger than $(\epsilon,\delta)$-LDP).

Noise Assumptions. We assume that the noise $\eta_{t}$ has zero mean
conditioned on the history and is bounded by $R$ almost surely. We also
address the case of unbounded noise at the end of the paper.

Regularity Assumptions. Attaining a sub-linear regret is in general infeasible
for an arbitrary reward function $f$ over a very large space without any
assumptions on the structure of $f$. In this paper, we assume that
$\mathcal{D}$ is compact and $f$ has a bounded norm in the RKHS of functions
$\mathcal{D}\to\mathbb{R}$, corresponding a kernel function
$k:\mathcal{D}\times\mathcal{D}\to\mathbb{R}$. This RKHS denoted by
$\mathcal{H}_{k}(\mathcal{D})$ is completely determined by its kernel function
with an inner product $\langle\cdot,\cdot\rangle_{\mathcal{H}}$ that satisfies
the reproducing property: $f(x)=\langle f,k(x,\cdot)\rangle_{\mathcal{H}}$ for
all $f\in H_{k}(\mathcal{D})$. The norm for the RKHS is given by $\left\lVert
f\right\rVert_{\mathcal{H}}=\sqrt{\langle f,f\rangle_{\mathcal{H}}}$, which
measures the smoothness of $f$. We assume $\left\lVert
f\right\rVert_{\mathcal{H}}\leq B$ and $B<\infty$ is a known constant.
Moreover, we assume a bounded variance by restricting $k(x,x)\leq 1$. Note
that two commonly used kernels _Squared Exponential_ and _Matérn_ satisfy the
bounded variance assumption, defined as:

$\displaystyle k_{\text{SE}}(x,x^{\prime})$
$\displaystyle=\exp{(-s^{2}/2l^{2})}$ $\displaystyle
k_{\text{Mat\'{e}rn}}(x,x^{\prime})$
$\displaystyle=\frac{2^{1-\nu}}{\Gamma(\nu)}\left(\frac{s\sqrt{2\nu}}{l}\right)^{\nu}B_{\nu}\left(\frac{s\sqrt{2\nu}}{l}\right),$

where $l>0$ and $\nu>0$ are hyper-parameters, $s=\left\lVert
x-x^{\prime}\right\rVert_{2}$ specifies the similarity between two points, and
$B_{\nu}(\cdot)$ is the modified Bessel function.

Surrogate GP Model222The surrogate GP model described above (i.e., a GP prior
and a Gaussian likelihood) is only used for the algorithm design.. A Gaussian
process, denoted by $\mathcal{GP}(\mu(\cdot),k(\cdot,\cdot))$, is a collection
of (possibly infinitely many) random variables $f(x),x\in\mathcal{D}$, such
that every finite subset of random variables $\\{f(x_{i}),i\in[m]\\}$ is
jointly Gaussian with mean $\mathbb{E}\left[f(x_{i})\right]=\mu(x_{i})$ and
covariance
$\mathbb{E}\left[(f(x_{i})-\mu(x_{i}))(f(x_{j})-\mu(x_{j}))\right]=k(x_{i},x_{j})$,
where $i,j\in[m]$ and $m\in\mathbb{N}$. By conditioning GPs on available
observations, one can obtain a non-parametric surrogate Bayesian model over
the space of functions. In particular, we use $\mathcal{GP}(0,k(\cdot,\cdot))$
as an initial prior on the unknown black-box function $f$, and a Gaussian
likelihood with the noise variables $\eta_{t}$ drawn independently across $t$
from $\mathcal{N}(0,\lambda)$. Conditioned on a set of past observations
$\mathcal{H}_{t}=\\{(x_{s},{y}_{s}),s\in[t]\\}$, by the properties of GPs
[18], the posterior distribution over $f$ is
$\mathcal{GP}(\mu_{t}(\cdot),k_{t}(\cdot,\cdot))$, where

$\displaystyle\mu_{t}(x)$ $\displaystyle=k_{t}(x)^{T}(K_{t}+\lambda
I)^{-1}{y}_{1:t}$ (3) $\displaystyle k_{t}(x,x^{\prime})$
$\displaystyle=k(x,x^{\prime})-k_{t}(x)^{T}(K_{t}+\lambda
I)^{-1}k_{t}(x^{\prime})$ $\displaystyle\sigma_{t}^{2}(x)$
$\displaystyle=k_{t}(x,x).$ (4)

Therefore, for every $x\in\mathcal{D}$, the posterior distribution of $f(x)$,
given $\mathcal{H}_{t}$ is $\mathcal{N}(\mu_{t}(x),\sigma_{t}^{2}(x))$. The
following term often plays a key role in the regret bounds of GP based
algorithms.

$\displaystyle\gamma_{t}:=\gamma_{t}(k,\mathcal{D})=\max_{A\subset\mathcal{D}:|A|=t}\frac{1}{2}\ln|I_{t}+{\lambda}^{-1}K_{A}|,$

where $K_{A}=[k(x,x^{\prime})]_{x,x^{\prime}\in A}$. Roughly speaking,
$\gamma_{t}$ is the maximum mutual information that can be obtained about the
GP prior from $t$ samples corrupted by a Gaussian channel
$\mathcal{N}(0,\lambda)$. It is a function of the kernel $k$ and domain
$\mathcal{D}$. For instance, if $\mathcal{D}$ is compact and convex, then we
have $\gamma_{t}=O((\ln t)^{d+1})$ for $k_{\text{SE}}$,
$O(t^{\frac{d(d+1)}{2\nu+d(d+1)}}\ln t)$ for $k_{\text{Mat\'{e}rn}}$, and
$O(d\ln t)$ for a linear kernel [23].

##  3 Lower Bounds

In this section, we derive the lower bounds for both $k_{\text{SE}}$ and
$k_{\text{Mat\'{e}rn}}$ under any LDP mechanism and any learning algorithm, as
presented in the following theorem.

######  Theorem 1.

Let $\mathcal{D}=[0,1]^{d}$ for some $d\in\mathbb{N}$. Fix a kernel
$k\in\\{k_{\text{SE}},k_{\text{Mat\'{e}rn}}\\}$, $B>0$, $\epsilon>0$,
$T\in\mathbb{Z}$, $\delta\in(0,1)$, $\alpha\in(0,1]$ and $v>0$. Given any
learning algorithm, any $\epsilon$-LDP mechanism, there exists a function
$f\in\mathcal{H}_{k}(\mathcal{D})$ with $\left\lVert
f\right\rVert_{\mathcal{H}}\leq B$, and a reward distribution satisfying
$\mathbb{E}\left[|y_{t}|^{1+\alpha}|\mathcal{F}_{t-1}\right]\leq v$ for all
$t\in[T]$, such that the following hold, respectively

  * •

$\mathbb{E}\left[R_{T}\right]=\Omega\left(v^{\frac{1}{1+\alpha}}T^{\frac{1}{1+\alpha}}{\zeta^{\frac{-2\alpha}{1+\alpha}}}\left(\ln\frac{B^{(1+\alpha)/\alpha}T\zeta^{2}}{v^{1/\alpha}}\right)^{\frac{d\alpha}{2+2\alpha}}\right)$,
where $\zeta=e^{\epsilon}-1$, if $k=k_{\text{SE}}$

  * •

$\mathbb{E}\left[R_{T}\right]=\Omega\left(v^{\frac{\nu}{\nu(1+\alpha)+d\alpha}}T^{\frac{\nu+d\alpha}{\nu(1+\alpha)+d\alpha}}\tilde{\zeta}B^{\frac{d\alpha}{\nu(1+\alpha)+d\alpha}}\right)$,
where
$\tilde{\zeta}={\zeta^{\frac{-2\alpha}{1+\alpha}+{\frac{2d\alpha^{2}}{(1+\alpha)(\nu(1+\alpha)+d\alpha)}}}}$
and $\zeta=e^{\epsilon}-1$, if $k=k_{\text{Mat\'{e}rn}}$.

######  Remark 1.

For a small $\epsilon$ and $\alpha=1$, and hence $\zeta\approx\epsilon$, the
regret lower bounds in Theorem 1 have an additional factor of $1/\epsilon$ in
front of the lower bounds for non-private case in [7]333for
$k=k_{\text{Mat\'{e}rn}}$, it holds for a large $\nu$..

###### Proof Sketch of Theorem 1.

The proof follows the standard techniques in [20, 7], which provide lower
bounds for _non-private_ BO under $i.i.d$ Gaussian noise (or heavy-tailed
payoffs). The key challenge is handle the additional requirement of
$\epsilon$-LDP. To this end, we aim to relate the Kullback-Leibler (KL)
divergence between two distributions $P_{1}$ and $P_{2}$ to the KL divergence
between two new distributions $M_{1}$ and $M_{2}$, which are the distributions
transformed from $P_{1}$ and $P_{2}$ according to a given $\epsilon$-LDP
mechanism. Inspired by [2], we resort to Theorem 1 of [9] and Pinsker’s
inequality. More specifically, by Theorem 1 of [9], we have

$\displaystyle D_{kl}(M_{1}||M_{2})+D_{kl}(M_{2}||M_{1})$ $\displaystyle\leq
4(e^{\epsilon}-1)^{2}||P_{1}-P_{2}||^{2}_{TV}.$

Then, by Pinsker’s inequality, we have

$\displaystyle||P_{1}-P_{2}||^{2}_{TV}\leq 2D_{kl}(P_{1}||P_{2}).$

Thus, roughly speaking, there is an additional term $(e^{\epsilon}-1)^{2}$.
The full proof is in Appendix. ∎

##  4 Algorithms and Upper Bounds

In this section, we will present three algorithms that are able to achieve
nearly optimal regret while guaranteeing $\epsilon$-LDP. All the three
algorithms rely on adding additional Laplace noise on the reward (i.e.,
Laplace mechanism in DP) to provide privacy guarantee. Note that, due to the
additional Laplace noise, the rewards received by the learner are now no
longer sub-Gaussian, and hence standard algorithms will not work. As a result,
the three algorithms mainly differ in the way of handling the issue of non-
sub-Gaussian rewards.

###  4.1 Laplace Mechanism

A commonly used mechanism in the areas of DP is the Laplace mechanism, which
adds independent Laplace noise to the data point. For any $\mathcal{L}>0$, the
PDF of the Laplace($\mathcal{L}$) (i.e., mean is zero) is given by

$\displaystyle\text{Laplace}(\mathcal{L}):l(x\mid\mathcal{L})=(2\mathcal{L})^{-1}\exp(-|x|/\mathcal{L}).$

Thus, it is with mean $0$ and variance $2\mathcal{L}^{2}$. The Laplace
mechanism used in this paper is stated in Curator 1 and its theoretical
guarantee is given by Lemma 1.

Curator 1 Convert-to-Laplace (CTL($\epsilon$))

On receiving a reward observation $y_{t}$:

return $\bar{y}_{t}:=y_{t}+L$, where $L\sim$ Laplace$(\mathcal{L})$ and
$\mathcal{L}=\frac{2(B+R)}{\epsilon}$.

######  Lemma 1.

CTL($\epsilon$) guarantees $\epsilon$-LDP.

###### Proof.

See Appendix. ∎

###  4.2 Adaptively Truncated Approximate (ATA) Algorithm and Regret

One direct way of handling non-sub-Gaussian rewards in BO is to utilize the
recently developed technique for heavy-tailed payoffs [7]. In particular, the
authors show that when combining a good feature approximation (e.g., Nyström
approximation) and a feature adaptive truncation of rewards (e.g., TOFU in
[22]), one can obtain a regret bound roughly
$\tilde{O}(\gamma_{T}T^{\frac{1}{1+\alpha}})$, when the $(1+\alpha)$-th moment
of the reward is finite and $\alpha\in(0,1]$. Hence, when $\alpha=1$, it
recovers the regret bounds under sub-Gaussian rewards [6].

Thus, it is natural to adapt ATA-GP-UCB introduced in [7] to handle the non-
sub-Gaussian payoffs caused by the Laplace noise in the LDP setting, which
leads to the LDP-ATA-GP-UCB, as described in Algorithm 1.

Algorithm 1 LDP-ATA-GP-UCB

1:Input: Parameters $\lambda$, $B$, $R$, $\epsilon>0$, $\\{b_{t}\\}_{t\geq
1}$, $\\{\beta_{t}\\}_{t\geq 1}$, and $q$.

2:Set: $\tilde{\mu}_{0}(x)=0$ and $\tilde{\sigma}_{0}(x)=k(x,x)$ for all
$x\in\mathcal{D}$.

3:for $t=1,2,3,\ldots,T$ do

4: Play
$x_{t}=\operatorname*{arg\,max}_{x\in\mathcal{D}}\tilde{\mu}_{t-1}(x)+\beta_{t}(x)\tilde{\sigma}_{t-1}(x)$

5: Receive private response $\bar{y}_{t}$ from CTL($\epsilon$)

6: Set
$\tilde{\varphi}_{t}(x)=\text{Nystr\"{o}mEmbedding}(\\{(x_{i},\tilde{\sigma}_{t-1}(x_{i}))\\}_{i=1}^{t},q)$

7: Set $m_{t}$ as the dimension of $\tilde{\varphi}_{t}$

8: Set
$\tilde{\Phi}_{t}^{T}=[\tilde{\varphi}_{t}(x_{1}),\ldots,\tilde{\varphi}_{t}(x_{t})]$
and $\tilde{V}_{t}=\tilde{\Phi}_{t}^{T}\tilde{\Phi}_{t}+\lambda I_{m_{t}}$

9: Find the rows $u_{1}^{T}\ldots,u_{m_{t}}^{T}$ of
$\tilde{V}_{t}^{-1/2}\tilde{\Phi}_{t}^{T}$

10: Set
$\hat{r}_{i}=\sum_{\tau=1}^{t}u_{i,\tau}\bar{y}_{\tau}\mathbbm{1}_{|u_{i,\tau}\bar{y}_{\tau}|\leq
b_{\tau}}$ for $i\in[m_{t}]$

11: Set
$\tilde{\theta}_{t}=\tilde{V}_{t}^{-1/2}[\hat{r}_{1},\ldots,\hat{r}_{m_{t}}]^{T}$

12: Set $\tilde{\mu}_{t}(x)=\tilde{\varphi}_{t}(x)^{T}\tilde{\theta}_{t}$

13: Set
$\tilde{\sigma}_{t}^{2}(x)=k(x,x)-\tilde{\varphi}_{t}(x)^{T}\tilde{\varphi}_{t}(x)+\lambda\tilde{\varphi}_{t}(x)^{T}\tilde{V}_{t}^{-1}\tilde{\varphi}_{t}(x)$

14:end for

Further, by adapting the regret analysis of ATA-GP-UCB in [7], we have the
following theorem for the regret upper bound of LDP-ATA-GP-UCB.

######  Theorem 2.

Let $f\in\mathcal{H}_{k}(\mathcal{D})$ with $\left\lVert
f\right\rVert_{\mathcal{H}}\leq B$ for all $x\in\mathcal{D}$ and noise
$\eta_{t}$ is bounded by $R$. Fix $\epsilon>0$, $\varepsilon\in(0,1)$ and set
$\rho=\frac{1+\varepsilon}{1-\varepsilon}$, and
$v=B^{2}+R^{2}+8(B+R)^{2}/\epsilon^{2}$. Then, for any $\delta\in(0,1]$, LDP-
ATA-GP-UCB with parameters $q=6\rho\ln(4T/\delta)/\varepsilon^{2}$,
$b_{t}=\sqrt{v/\ln(4m_{t}T/\delta)}$ and
$\beta_{t+1}=B(1+\frac{1}{\sqrt{1-\varepsilon}})+4\sqrt{\ln(4m_{t}T/\delta)vm_{t}/\lambda}$,
with probability at least $1-\delta$, has regret bound

$\displaystyle
R_{T}=O\left(\hat{\rho}B\sqrt{T\gamma_{T}}+\frac{\rho}{\varepsilon^{2}}\gamma_{T}\sqrt{T}\sqrt{v\ln(T/\delta)\ln(\frac{\gamma_{T}T\ln(T/\delta)}{\delta})}\right)$

where $\hat{\rho}=\rho\left(1+\frac{1}{\sqrt{1-\varepsilon}}\right)$.

######  Remark 2.

Note that by substituting the value of $v$ into the regret bound, we obtain
that $R_{T}=\tilde{O}(\gamma_{T}\sqrt{T}/\epsilon)$. That is, it has a factor
of $1/\epsilon$ compared to the non-private case, which matches the same
scaling of $\epsilon$ in the lower bounds as shown in Theorem 1. Moreover,
LDP-ATA-GP-UCB enjoys the same scaling with respect to both $\gamma_{T}$ and
$T$ as in the state-of-the-art non-private sub-Gaussian case.

Although the LDP-ATA-GP-UCB algorithm achieves almost optimal regret bound, it
might be a ‘overkill’ for the LDP setting. In particular, the original setting
for the ATA-GP-UCB algorithm in [7] only assumes at most a finite variance.
However, in our LDP setting, the corrupted reward $\bar{y}$ has all the
moments being bounded and enjoys an exponential-type tail. In other words,
although the additional Laplace noise causes the corrupted reward to be no
longer sub-Gaussian, it still enjoys better properties compared to the general
conditions for the ATA-GP-UCB algorithm to work. Therefore, it seems that
there is some hope that we can design simple algorithm to achieve the same
regret bound. Another issue of ATA-GP-UCB is its computational complexity. As
pointed out by [22] in the linear bandit setting (ATA-GP-UCB reduces to TOFU),
for each round, it needs to truncate all the historical payoffs, which leads
to a high complexity.

Based on the discussions above, in the following, we will propose two novel
algorithms that are also able to achieve almost optimal regret while
substantially reducing the implementation and computational complexity of LDP-
ATA-GP-UCB.

###  4.3 Raw Reward Truncation Algorithm and Regret

In this section, instead of using the sophisticated truncation in the feature
space as in LDP-ATA-GP-UCB, we turn to adopt the simple truncation on the raw
rewards. In the general heavy-tail reward setting (with at most a finite
variance), [7] proposed TGP-UCB algorithm which truncates the reward to zero
if it is larger than a truncated point $b_{t}$ for round $t$. Specifically,
for a finite variance case, the truncated point $b_{t}$ is $\theta(t^{1/4})$
in TGP-UCB, which finally leads to an regret bound of $\tilde{O}(T^{3/4})$.
Hence, it has an additional factor $O(T^{1/4})$ when compared to the regret
bound for the sub-Gaussian case. This means that we cannot directly adopt TGP-
UCB to achieve the same regret bound as in LDP-ATA-GP-UCB of the last section.

However, as pointed before, the corrupted reward $\bar{y}$ has a nice
exponential tail property. This suggests that a truncated point of order
$O(\ln t)$ is enough, which will only in turn incurs an additional $O(\ln T)$
factor in the regret. Based on this idea, we propose the LDP-TGP-UCB
algorithm, as described in Algorithm 2.

Algorithm 2 LDP-TGP-UCB

1:Input: Parameters $B$, $R$, $\epsilon>0$, $\lambda$, $\delta$.

2:Set: $K=B^{2}+R^{2}+2\mathcal{L}^{2}$

3:for $t=1,2,3,\ldots,T$ do

4: Set $b_{t-1}=B+R+\mathcal{L}\ln(t-1)$

5: Set
$\beta_{t}=B+\frac{2\sqrt{2}}{\sqrt{\lambda}}b_{t-1}\sqrt{\gamma_{t-1}+\ln(1/\delta)}+\frac{1}{\sqrt{\lambda}}\sqrt{K(\ln(t-1)+1)}$

6: Play
$x_{t}=\arg\max_{x\in\mathcal{D}}\hat{\mu}_{t-1}(x)+\beta_{t}\sigma_{t-1}(x)$

7: Receive private response $\bar{y}_{t}$ from CTL($\epsilon$).

8: Set $\hat{y}_{t}=\bar{y}_{t}\mathbbm{1}_{|\bar{y}_{t}|\leq b_{t}}$ and
$\hat{Y}_{t}=[\hat{y}_{1},\ldots,\hat{y}_{t}]^{T}$

9: Set $\hat{\mu}_{t}(x)=k_{t}(x)^{T}(K_{t}+\lambda I)^{-1}\hat{Y}_{t}$

10: Set $\sigma_{t}^{2}(x)=k(x,x)-k_{t}(x)^{T}(K_{t}+\lambda I)^{-1}k_{t}(x)$

11:end for

Moreover, by refining the regret analysis of TGP-UCB in [7], we can obtain the
following theorem for the regret bound of LDP-TGP-UCB.

######  Theorem 3.

Fix $\epsilon>0$. Let $f\in\mathcal{H}_{k}(\mathcal{D})$ with $\left\lVert
f\right\rVert_{\mathcal{H}}\leq B$ for all $x\in\mathcal{D}$ and the noise
$\eta_{t}$ is bounded by $R$ for all $t$. Then, for any $\delta\in(0,1]$, LDP-
TGP-UCB achieves, with probability at least $1-\delta$, the regret bound

$\displaystyle R_{T}=O\left(\vartheta\sqrt{\ln
T\gamma_{T}T}+\vartheta\sqrt{T}\ln
T\sqrt{\gamma_{T}(\gamma_{T}+\ln(1/\delta))}\right),$

where $\vartheta=(B+R)/\epsilon$.

######  Remark 3.

As in LDP-ATA-GP-UCB, LDP-TGP-UCB is also able to achieve regret bound
$\tilde{O}(\gamma_{T}\sqrt{T}/\epsilon)$. The advantage of LDP-TGP-UCB is its
simple implementation in the sense that each reward is only trimmed once.

###### Proof Sketch of Theorem 3.

As in most GP-UCB like algorithms [6, 7], the key step boils down to
establishing a (high-probability) confidence interval bound, i.e., in our
setting,

$\displaystyle|f(x)-\hat{\mu}_{t}(x)|\leq\beta_{t+1}\sigma_{t}(x).$

To this end, with some linear algebra calculations, we have

$\displaystyle|f(x)-\hat{\mu}_{t}(x)|\leq\left(B+\lambda^{-1/2}\lVert\sum_{\tau=1}^{t}\hat{\eta}_{\tau}\varphi(x_{\tau})\rVert_{V_{t}^{-1}}\right)\sigma_{t}(x),$

where $\hat{\eta}_{t}=\hat{y}_{t}-f(x_{t})$, $\varphi(x):=k(x,\cdot)$, which
maps $x\in\mathbb{R}^{d}$ to RKHS $H$ associated with kernel function $k$ and
$V_{t}=\Phi_{t}^{T}\Phi_{t}+\lambda I_{\mathcal{H}}$,
$\Phi_{t}:=[\varphi(x_{1})^{T},\ldots,\varphi(x_{t})^{T}]^{T}$.

The key term is
$\lVert\sum_{\tau=1}^{t}\hat{\eta}_{\tau}\varphi(x_{\tau})\rVert_{V_{t}^{-1}}$,
which can be handled by the self-normalized inequality if $\hat{\eta}_{\tau}$
is sub-Gaussian. However, in our setting, it is not. To overcome this issue,
we will divide it into two parts. In particular, similar to [7], we define
$\xi_{t}=\hat{\eta}_{t}-\mathbb{E}\left[\hat{\eta}_{t}\mid\mathcal{F}_{t-1}\right]$.
Now, the key term can be written as

$\displaystyle\lVert\sum_{\tau=1}^{t}\hat{\eta}_{\tau}\varphi(x_{\tau})\rVert_{V_{t}^{-1}}=\underbrace{\lVert\sum_{\tau=1}^{t}{\xi}_{\tau}\phi(x_{\tau})\rVert_{V_{t}^{-1}}}_{\mathcal{T}_{1}}+\underbrace{\lVert\sum_{\tau=1}^{t}\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]\phi(x_{\tau})\rVert_{V_{t}^{-1}}.}_{\mathcal{T}_{2}}$
(5)

For $\mathcal{T}_{1}$, note that
$\xi_{t}=\hat{y}_{t}-\mathbb{E}\left[\hat{y}_{t}\mid\mathcal{F}_{t-1}\right]$,
which is bounded by $2b_{t}$, and hence sub-Gaussian. Thus, by the self-
normalized inequality for the RKHS-valued process in [10, 7], we can bound
$\mathcal{T}_{1}$ as follows

$\displaystyle\mathcal{T}_{1}\leq 2b_{t}\sqrt{2(\gamma_{t}+\ln(1/\delta))}.$

For $\mathcal{T}_{2}$, with some linear algebra, we can first bound it as
$\sqrt{\sum_{\tau=1}^{t}\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]^{2}}$.
Further, note that
$\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]=-\mathbb{E}\left[\bar{y}_{\tau}\mathbbm{1}_{|\tilde{y}_{\tau}|>b_{\tau}}|\mathcal{F}_{\tau-1}\right]$.
Hence, by Cauchy-Schwartz inequality with $b_{\tau}=B+R+\mathcal{L}\ln\tau$,
we have

$\displaystyle\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]^{2}\leq\mathbb{E}\left[\bar{y}_{\tau}^{2}|\mathcal{F}_{\tau-1}\right]\mathbbm{P}(|L|>\mathcal{L}\ln\tau)\leq
K\frac{1}{\tau},$

where $K:=B^{2}+R^{2}+2\mathcal{L}^{2}$. The last inequality holds since
$|L|\sim\text{Exp}(1/\mathcal{L})$. Therefore, by the property of Harmonic
sum, we have

$\displaystyle\mathcal{T}_{2}\leq\sqrt{K(\ln t+1)}.$

Hence, the (high-probability) confidence interval bound is obtained by setting

$\displaystyle\beta_{t+1}=B+\frac{2\sqrt{2}}{\sqrt{\lambda}}b_{t}\sqrt{\gamma_{t}+\ln(1/\delta)}+\frac{1}{\sqrt{\lambda}}\sqrt{K(\ln
t+1)}.$

The full proof is relegated to Appendix. ∎

It is worth pointing out the truncation trick used in LDP-TGP-UCB also sheds
light on the regret bounds for non-private BO under payoffs that are beyond
sub-Gaussian, e.g., sub-Weibull which includes sub-Gaussian and sub-
exponential as special cases [24]. More specifically, according to [24], a
random variable $X$ is said to be a sub-Weibull with tail parameter $\theta$,
i.e., $X\sim\text{subW}(\theta)$, if for some constants $a$ and $b$ such that

$\displaystyle\mathbb{P}(|X|\geq x)\leq a\exp(-bx^{1/\theta}),\quad\text{for
all }x>0.$ (6)

It can be seen that sub-Gaussian and sub-exponential distributions are special
cases of sub-Weibull with $\theta=1/2$ and $\theta=1$, respectively. Thus,
instead of choosing the truncation point $b_{t}=O(\ln t)$ as in LDP-TGP-UCB,
one turn to choose $b_{t}=O((\ln t)^{\theta})$, which in turn only incurs a
log factor in the regret bound. As a result, with this simple truncation, the
non-private BO under sub-Weibull noise is still
$\tilde{O}(\gamma_{T}\sqrt{T})$.

###  4.4 Median of Means Approximate (MoMA) Algorithm and Regret

In this section, we will introduce a new BO method that is able to achieve
almost optimal regret bounds under general heavy-tailed payoffs. Hence, the
LDP setting is just a special case. This new method is mainly inspired by the
MENU algorithm in [22], which is introduced to handle the heavy-tailed payoffs
in the linear bandit setting. Moreover, it has been shown to have a lower
complexity than TOFU (which is the core of ATA-GP-UCB). The key idea in MENU
is based on median of means techniques [3]. The main challenge in generalizing
MENU to the BO setting is to handle the possibly infinite feature dimension
associated with the kernel function. To this end, we will again use kernel
approximation techniques (i.e., Nyström approximation) developed in [5, 7].
However, instead of updating the approximations after every iteration as in
ATA-GP-UCB, in our new method the approximation is only updated after each
‘epoch’, which is composed of multiple iterations. This further reduces its
complexity.

This new algorithm is called MoMA-GP-UCB, which is presented in Algorithm 3.
With the aid of Fig. 1 (adapted from [22]), we can easily see that the total
number of $T$ iterations are divided into $N$ epochs, each consisted of $k$
iterations. The algorithm will loop over each $n=1,\ldots,N$ epoch. Within
each epoch $n$, a point $x_{n}$ is selected in a GP-UCB fashion, and the
selected point $x_{n}$ will be played $k$ times with corresponding rewards.
Then, the kernel approximation terms are updated, i.e.,
$\tilde{\varphi}_{n}$,$\tilde{\Phi}_{n}$ and $\tilde{V}_{n}$. Following this
update, it will calculate $k$ least-square-estimates (LSE), each is based on
the rewards along each row $j\in[k]$ (e.g., using the data in the pink row to
generate the pink LSE, and similarly green data for the green LSE). Next, it
applies median-of-means techniques to find the best LSE
$\tilde{\theta}_{n,k^{*}}$ for epoch $n$. Finally, the posterior mean and
variance are updated.

Now, we have the following theorem for the regret bound of MoMA-GP-UCB under
general heavy-tailed payoffs.

######  Theorem 4.

Let $f\in\mathcal{H}_{k}(\mathcal{D})$ with $\left\lVert
f\right\rVert_{\mathcal{H}}\leq B$ for all $x\in\mathcal{D}$. Assume that
$\mathbb{E}\left[|\eta_{t}|^{1+\alpha}\mid\mathcal{F}_{t-1}\right]\leq c$. Fix
$\varepsilon\in(0,1)$ and set $\rho=\frac{1+\varepsilon}{1-\varepsilon}$.
Then, for any $\delta\in(0,1]$, MoMA-GP-UCB with parameters
$q=6\rho\ln(4T/\delta)/\varepsilon^{2}$, $k=\lceil
24\ln\left(\frac{4eT}{\delta}\right)\rceil$, and
$\beta_{n+1}=B(1+\frac{1}{\sqrt{1-\varepsilon}})+3\left((9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}\right)$,
with probability at least $1-\delta$, has regret bound

$\displaystyle
R_{T}=O\left(\hat{B}\sqrt{\gamma_{T}T\ln\frac{T}{\delta}}+Z\ln\frac{T}{\delta}c^{\frac{1}{1+\alpha}}T^{\frac{1}{1+\alpha}}\gamma_{T}^{\frac{3+\alpha}{2(1+\alpha)}}\right),$

where $\hat{B}=\rho B(1+\frac{1}{\sqrt{1-\varepsilon}})$ and
$Z=\left(\frac{\rho^{3+\alpha}}{\varepsilon^{2}}\right)^{\frac{1}{1+\alpha}}$.

######  Remark 4.

Note that when $\alpha=1$, MoMA-GP-UCB recovers the same regret bound
$\tilde{O}(\gamma_{T}\sqrt{T})$ as in the sub-Gaussian case. Moreover, for the
special linear kernel case, substituting $\gamma_{T}=O(d\ln T)$, the bound in
Theorem 4 recovers the regret bound in [22] up to logarithmic factor.

Figure 1: Illustration of MoMA-GP-UCB

###### Proof Sketch of Theorem 4.

The proof is mainly inspired by [22, 7]. The key step is again a (high-
probability) confidence interval bound, i.e.,

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|\leq\beta_{n+1}\tilde{\sigma}_{n}(x).$
(7)

Assume that the kernel approximation is $\varepsilon$-accurate, the LHS of Eq.
(7) can be bounded by

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|$ $\displaystyle\leq
B(1+\frac{1}{\sqrt{1-\varepsilon}})\tilde{\sigma}_{n}(x)$ $\displaystyle+$
$\displaystyle\lambda^{-1/2}\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}\tilde{\sigma}_{n}(x),$
(8)

where $f_{n}=[f(x_{1}),\ldots,f(x_{n})]^{T}$, i.e., a vector containing $f$’s
evaluations up to epoch $n$. Now, we need to focus on the term
$\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}$.
To this end, we first establish the following result regarding the $k$ LSEs.
In particular, for $j\in[k]$, we have

$\displaystyle\mathbb{P}\left(\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,j}\rVert_{\tilde{V}_{n}}\leq\gamma\right)\geq\frac{3}{4},$

where
$\gamma:=(9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}$.
Based on this result, by the choice of $k^{*}$, we obtain that if $k=\lceil
24\ln\left(\frac{eT}{\delta}\right)\rceil$, then for all $n\in[N]$, with
probability at least $1-\delta$,

$\displaystyle\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}\leq
3\gamma.$ (9)

Combining Eqs. (9) and (8), yields that, under the event that the kernel
approximation is $\varepsilon$-accurate, with probability at least $1-\delta$,

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|$
$\displaystyle\leq\left(B(1+\frac{1}{\sqrt{1-\varepsilon}})+\lambda^{-1/2}3\gamma\right)\tilde{\sigma}_{n}(x)$

for all $n\in[N]$ when $k=\lceil 24\ln\left(\frac{eT}{\delta}\right)\rceil$.
Since for any $\delta$, the kernel approximation (under given parameters) is
$\varepsilon$-accurate with probability at least $1-\delta$, by the virtue of
union bound, we have that when $k=\lceil
24\ln\left(\frac{2eT}{\delta}\right)\rceil$,

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|$
$\displaystyle\leq\beta_{n+1}\tilde{\sigma}_{n}(x)$ (10)

for all $n\in[N]$, where
$\beta_{n+1}:=B(1+\frac{1}{\sqrt{1-\varepsilon}})+\lambda^{-1/2}3\gamma$.
Finally, by the nice properties of Nyström approximation, we can obtain that
with probability at least $1-\delta$, both
$m_{n}=O(\frac{\rho^{2}}{\varepsilon^{2}}\gamma_{n}\ln(T/\delta))$ and
$\tilde{\sigma}_{n-1}(x_{n})\leq\rho{\sigma}_{n-1}(x_{n})$. Then, the regret
bound follows from that
$R_{T}=2k\sum_{n=1}^{N}\beta_{n}\tilde{\sigma}_{n-1}(x)$ along with standard
GP-UCB analysis. The full proof is relegated to Appendix. ∎

Algorithm 3 MoMA-GP-UCB

1:Input: Parameters $\lambda$, $\delta$, $\\{\beta_{t}\\}_{t\geq 1}$, and $q$.

2:Set: $\tilde{\mu}_{0}(x)=0$ and $\tilde{\sigma}_{0}(x)=k(x,x)$ for all
$x\in\mathcal{D}$.

3:Set: $k=\lceil 24\ln\left(\frac{4eT}{\delta}\right)\rceil$ and
$N=\lfloor\frac{T}{k}\rfloor$.

4:for $n=1,2,3,\ldots,N$ do

5:
$x_{n}=\operatorname*{arg\,max}_{x\in\mathcal{D}}\tilde{\mu}_{n-1}(x)+\beta_{n}(x)\tilde{\sigma}_{n-1}(x)$

6: Play $x_{n}$ with $k$ times and observe rewards
$y_{n,1},y_{n,2},\ldots,y_{n,k}$.

7: Set
$\tilde{\varphi}_{n}(x)=\text{Nystr\"{o}mEmbedding}(\\{(x_{i},\tilde{\sigma}_{n-1}(x_{i}))\\}_{i=1}^{n},q)$

8: Set $m_{n}$ as the dimension of $\tilde{\varphi}_{n}$

9: Set
$\tilde{\Phi}_{n}^{T}=[\tilde{\varphi}_{n}(x_{1}),\ldots,\tilde{\varphi}_{n}(x_{n})]$
and $\tilde{V}_{n}=\tilde{\Phi}_{n}^{T}\tilde{\Phi}_{n}+\lambda I_{m_{n}}$

10: For $j\in[k]$,
$\tilde{\theta}_{n,j}=\tilde{V}_{n}^{-1}\sum_{i=1}^{n}y_{i,j}\tilde{\varphi}_{n}(x_{i})$

11: For $j\in[k]$, $r_{j}=$
median$(\\{\lVert\tilde{\theta}_{n,j}-\tilde{\theta}_{n,s}\rVert_{\tilde{V}_{n}}:s\in[k]\setminus
j\\})$

12: Set $k^{*}=\arg\min_{j\in[k]}r_{j}$

13: Set
$\tilde{\mu}_{n}(x)=\tilde{\varphi}_{n}(x)^{T}\tilde{\theta}_{n,k^{*}}$

14: Set
$\tilde{\sigma}_{n}^{2}(x)=k(x,x)-\tilde{\varphi}_{n}(x)^{T}\tilde{\varphi}_{n}(x)+\lambda\tilde{\varphi}_{n}(x)^{T}\tilde{V}_{n}^{-1}\tilde{\varphi}_{n}(x)$

15:end for

Now, we can easily design the private version of it, called LDP-MoMA-GP-UCB.
The only difference is line $6$, in which LDP-MoMA-GP-UCB received private
response from CTL($\epsilon$). Thus, we can directly obtain the regret bound
of LDP-MoMA-GP-UCB as a corollary of Theorem 4.

######  Corollary 1.

Let $f\in\mathcal{H}_{k}(\mathcal{D})$ with $\left\lVert
f\right\rVert_{\mathcal{H}}\leq B$ for all $x\in\mathcal{D}$ and noise
$\eta_{t}$ is bounded by $R$. Fix $\epsilon>0$, $\varepsilon\in(0,1)$ and set
$\rho=\frac{1+\varepsilon}{1-\varepsilon}$, and
$c=R^{2}+8(B+R)^{2}/\epsilon^{2}$. Then, for any $\delta\in(0,1]$, LDP-MoMA-
GP-UCB with parameters $q=6\rho\ln(4T/\delta)/\varepsilon^{2}$, $k=\lceil
24\ln\left(\frac{4eT}{\delta}\right)\rceil$ and
$\beta_{n+1}=B(1+\frac{1}{\sqrt{1-\varepsilon}})+3\left((9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}\right)$,
with probability at least $1-\delta$, has regret bound

$\displaystyle
R_{T}=O\left(\hat{B}\sqrt{\gamma_{T}T\ln\frac{T}{\delta}}+Z\ln\frac{T}{\delta}\frac{B+R}{\epsilon}\gamma_{T}\sqrt{T}\right),$

where $\hat{B}=\rho B(1+\frac{1}{\sqrt{1-\varepsilon}})$ and
$Z=\left(\frac{\rho^{3+\alpha}}{\varepsilon^{2}}\right)^{\frac{1}{1+\alpha}}$.

###  4.5 Unbounded Noise Case

In previous sections, we assume that $\eta_{t}$ is bounded by $R$. Hence, by
Laplace mechanism, we can achieve $\epsilon$-LDP. In the case of unbounded
noise, we show that Laplace mechanism can ensure $(\epsilon,\delta)$-LDP
(weaker than $\epsilon$-LDP) while still achieving almost optimal regret
bounds for a large class of noise. More specifically, consider the case
$\eta_{t}$ is $i.i.d$ and $\eta_{t}\sim\text{subW}(\theta)$ as defined in Eq.
(6). Then, it is easy to see that there exists a constant $K_{1}$ such that
$\mathbb{P}(\exists
t\in[T],|\eta_{T}|>K_{1}\ln(T/\delta)^{\theta})\leq\delta$. Thus, by letting
$R=K_{1}\ln(T/\delta)^{\theta}$ in the Laplace mechanism (i.e.,
CTL($\epsilon$)), the previous three private algorithms can protect
$(\epsilon,\delta)$-LDP while only incurring an additional logarithmic factor
in the regret bounds.

##  5 Experiments

We conduct experiments to compare the performance of the three private
algorithms (i.e., LDP-ATA-GP-UCB, LDP-TGP-UCB, LDP-MoMA-GP-UCB) and the
performance of three non-private BO methods for general heavy-tailed payoffs
(i.e., ATA-GP-UCB, TGP-UCB in [7] and MoMA-GP-UCB proposed in this paper). As
in [7], the parameters used for each algorithm are set order-wise similar to
those recommended by the theorems. We run each algorithm for $10$ independent
trials and plot the average of cumulative regret along with time evolution.

###  5.1 Datasets and Settings

Synthetic data. The domain $\mathcal{D}$ is generated by discretizing $[0,1]$
uniformly into $100$ points. The black-box function
$f=\sum_{i=1}^{p}a_{i}k(\cdot,x_{i})$ is generated by uniformly sampling
$a_{i}\in[-1,1]$ and support points $x_{i}\in\mathcal{D}$ with $p=100$. The
parameters for the kernel function are $l=0.2$ for $k_{\text{SE}}$ and
$l=0.2$, $\nu=2.5$ for $k_{\text{Mat\'{e}rn}}$. We set
$B=\max_{x\in\mathcal{D}}|f(x)|$ and $y(x)=f(x)+\eta$. For the LDP case, the
noise $\eta$ is uniformly sampled in $[-1,1]$ and hence $R=1$. For the non-
private heavy-tailed case, the noise $\eta$ are samples from the Student’s
$t$-distribution with $3$ degrees of freedom. Hence, $v=B^{2}+3$ and $c=3$.

Light sensor data. This data is collected in the CMU Intelligent Workplace in
Nov 2005, which is available online as Matlab
structure444http://www.cs.cmu.edu/~guestrin/Class/10708-F08/projects and
contains locations of 41 sensors, 601 train samples and 192 test samples. We
use it in the context of finding the maximum average reading of the sensors.
For fair comparison, the settings for this dataset follow from [7],which has
shown that the payoffs are heavy-tailed. In particular, $f$ is set as
empirical average of the test samples, with $B$ set as its maximum, and $k$ is
set as the empirical covariance of the normalized train samples. The noise is
estimated by taking the difference between the test samples and its empirical
mean (i.e., $f$), and $R$ is set as the maximum. Here, we consider $\alpha=1$,
set $v$ as the empirical mean of the squared readings of test samples, and $c$
is the empirical mean of the squared noise.

Stock market data. This dataset is the adjusted closing price of $29$ stocks
from January 4th, 2016 to April 10th, 2019. We use it in the context of
identifying the most profitable stock in a given pool of stocks. As verified
in [7], the rewards follows from heavy-tailed distribution. We take the
empirical mean of stock prices as our objective function $f$ and empirical
covariance of the normalized stock prices as our kernel function $k$. The
noise is estimated by taking the difference between the raw prices and its
empirical mean (i.e., $f$), with $R$ set as the maximum. Consider $\alpha=1$,
with $v$ set as the empirical mean of the squared prices and $c$ set as the
empirical mean of squared noise.

###  5.2 Results

From Figure 2, we can see that MoMA-GP-UCB (or LDP-MoMA-GP-UCB) tends to
empirically outperform the other two algorithms in both non-private and
private settings. We also conduct additional experiments (relegated to
Appendix), and similar observations are obtained. Note that similar to [7],
the high error bar in (d) is because a different $f$ is chosen for each trial.

(a) LDP, $\epsilon=1$, Synthetic data, $k_{\text{Mat\'{e}rn}}$

(b) LDP, $\epsilon=0.5$, Light sensor data

(c) LDP, $\epsilon=1$, Stock market data.

(d) Non-private, Synthetic data, $k_{\text{SE}}$

(e) Non-private, Light sensor data

(f) Non-private, Stock market data

Figure 2: (a)-(c) Cumulative regrets for three LDP algorithms; (d)-(f)
Cumulative regrets (and standard variance) for non-private versions on heavy-
tailed data.

##  6 Conclusion

We derived regret lower bounds for LDP BO and presented three almost optimal
algorithms. We also proposed MoMA-GP-UCB. It complements previous BO
algorithms for heavy-tailed payoffs and has superior performance with a
reduced complexity.

## References

  * [1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In Advances in Neural Information Processing Systems, pages 2312–2320, 2011.
  * [2] Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou.  Differential privacy for multi-armed bandits: What is it and what is its cost?  arXiv preprint arXiv:1905.12298, 2019.
  * [3] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi.  Bandits with heavy tail.  IEEE Transactions on Information Theory, 59(11):7711–7717, 2013\.
  * [4] Xu Cai and Jonathan Scarlett.  On lower bounds for standard and robust gaussian process bandit optimization.  arXiv preprint arXiv:2008.08757, 2020.
  * [5] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco.  Gaussian process optimization with adaptive sketching: Scalable and no regret.  arXiv preprint arXiv:1903.05594, 2019.
  * [6] Sayak Ray Chowdhury and Aditya Gopalan.  On kernelized multi-armed bandits.  arXiv preprint arXiv:1704.00445, 2017.
  * [7] Sayak Ray Chowdhury and Aditya Gopalan.  Bayesian optimization under heavy-tailed payoffs.  In Advances in Neural Information Processing Systems, pages 13790–13801, 2019.
  * [8] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang.  Privacy at scale: Local differential privacy in practice.  In Proceedings of the 2018 International Conference on Management of Data, pages 1655–1658, 2018.
  * [9] John C Duchi, Michael I Jordan, and Martin J Wainwright.  Local privacy and statistical minimax rates.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438. IEEE, 2013.
  * [10] Audrey Durand, Odalric-Ambrym Maillard, and Joelle Pineau.  Streaming kernel regression with provably adaptive mean, variance, and regularization.  The Journal of Machine Learning Research, 19(1):650–683, 2018.
  * [11] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  2014\.
  * [12] Pratik Gajane, Tanguy Urvoy, and Emilie Kaufmann.  Corrupt bandits for preserving local privacy.  In Algorithmic Learning Theory, pages 387–412. PMLR, 2018.
  * [13] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [14] Matt Kusner, Jacob Gardner, Roman Garnett, and Kilian Weinberger.  Differentially private bayesian optimization.  In International conference on machine learning, pages 918–927, 2015.
  * [15] Tze Leung Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  Advances in applied mathematics, 6(1):4–22, 1985.
  * [16] Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010.
  * [17] Mojmir Mutny and Andreas Krause.  Efficient high dimensional bayesian optimization with additivity and quadrature fourier features.  In Advances in Neural Information Processing Systems, pages 9005–9016, 2018.
  * [18] Carl Edward Rasmussen.  Gaussian processes in machine learning.  In Summer School on Machine Learning, pages 63–71. Springer, 2003\.
  * [19] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff.  Multi-armed bandits with local differential privacy.  arXiv preprint arXiv:2007.03121, 2020.
  * [20] Jonathan Scarlett, Ilijia Bogunovic, and Volkan Cevher.  Lower bounds on regret for noisy gaussian process bandit optimization.  arXiv preprint arXiv:1706.00090, 2017.
  * [21] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas.  Taking the human out of the loop: A review of bayesian optimization.  Proceedings of the IEEE, 104(1):148–175, 2015.
  * [22] Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu.  Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs.  In Advances in Neural Information Processing Systems, pages 8420–8429, 2018.
  * [23] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger.  Gaussian process optimization in the bandit setting: No regret and experimental design.  arXiv preprint arXiv:0912.3995, 2009.
  * [24] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel.  Sub-weibull distributions: generalizing sub-gaussian and sub-exponential properties to heavier-tailed distributions.  arXiv preprint arXiv:1905.04955, 2019.
  * [25] Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang.  Locally differentially private (contextual) bandits learning.  arXiv preprint arXiv:2006.00701, 2020.

##  Appendix A Proof of Theorem 1

In this section, we will provide the detailed proof for the lower bounds in
Theorem 1. As pointed out earlier, our analysis build on the lower bounds for
non-private BO in [7, 20], but with important differences to handle the
requirement of $\epsilon$-LDP under _any_ private mechanism. Roughly speaking,
we follow the same construction of a function class in [20] (with some slight
changes as noted in footnotes) and the reward construction in [7] for heavy-
tailed payoffs. To handle the LDP requirement, we take the strategy of
relating a non-private version KL divergence to a private version KL
divergence. It is worth noting that recently high probability (rather than
expected) regret lower bounds in the case of non-private BO with Gaussian
noise have also been derived [4]. By using the same method of handling LDP in
this proof, one can directly extend the results in [4] to establish private
high probability lower bounds.

In the following, to make our proof self-contained, we first briefly review
the necessary backgrounds and notations used in previous papers [7, 20, 4] for
establishing the lower bounds.

###  A.1 Construction of a function class

The high-level idea of this process is to construct a set of ‘difficult’
functions, i.e., $\mathcal{F}=\\{f_{1},\ldots,f_{M}\\}$, by shifting a common
function $g$ by different amount. By ‘difficult’, we mean that this function
class satisfies that any single point $x$ can only be $\Delta$-optimal for at
most one function in this set. Then, we take $f$ as a uniformly sampled
function from $\mathcal{F}$. The idea is that if we can lower bound the regret
averaged over the set, then there must exist a particular value of $m$ such
that the same lower bound applies to $f_{m}$. The details are as follows.

  * •

The common function $g$ is a function on $\mathbb{R}^{d}$ with the following
properties:

    1. 1.

$g$ is bounded in the RKHS norm, i.e., $\left\lVert
g\right\rVert_{\mathcal{H}}\leq B$.

    2. 2.

$g$ takes values in $[-2\Delta,2\Delta]$ with a peak value of $2\Delta$ at
$x=0$, for some $\Delta>0$ determined later.

    3. 3.

$g$ takes values strictly less than $\Delta$, i.e., $g(x)<\Delta$, whenever
$\left\lVert x\right\rVert_{\infty}>\frac{w}{2}$, for some $w$ to be chosen
later555Note that, in all previous papers [7, 20, 4], the condition is
$\left\lVert x\right\rVert_{\infty}>{w}$ for property 3. However, it turns out
to be insufficient to construct the ‘difficult’ function class, i.e., any
single point $x$ can only be $\Delta$-optimal for at most one function among
$M$ functions constructed by the shifting process..

  * •

The shifting process of $g$ on the domain $\mathcal{D}=[0,1]^{d}$ is as
follows. First, by taking a step size of $w$ in each dimension, we can
construct a grid of size $M=\lfloor\left(\frac{1}{w}\right)^{d}\rfloor$. Then,
each function $f_{j}$ is constructed by centering $g$ on the $j$th point of
the grid, and then cropping to $\mathcal{D}=[0,1]^{d}$. Hence, we obtain $M$
functions, i.e., $\mathcal{F}=\\{f_{1},\ldots,f_{M}\\}$. Moreover, by the
properties of $g$ mentioned above, we ensure that any $\Delta$-optimal point
for $f_{i}$ fails to be a $\Delta$-optimal point for any other function
$f_{j}$ where $j\neq i$.

Now, it only remains to choose $g$, $\Delta$, and $w$ (and hence $M$).

  * •

Choose $g(x)=\frac{2\Delta}{h(0)}h\left(\frac{2x\zeta}{w}\right)$, for some
absolute constant $\zeta>0$, where $h$ is the inverse Fourier transform of the
multi-dimensional bump function: $H(z)=e^{-\frac{1}{1-\left\lVert
z\right\rVert_{2}^{2}}}\mathbbm{1}\\{\left\lVert z\right\rVert_{2}^{2}\leq
1\\}$. Since $H$ is real and symmetric, we have the maximum of $h$ is attained
at $x=0$, and hence $g$ has its maximum at $x=0$ with value $2\Delta$.
Moreover, since $H$ has finite energy, $h(x)\to 0$ when $\left\lVert
x\right\rVert_{2}\to\infty$. Then, there exits a constant $\zeta>0$ such that
$h(x)<\frac{1}{2}h(0)$ when $\left\lVert x\right\rVert_{\infty}>\zeta$. Thus,
when $\left\lVert x\right\rVert_{\infty}>\frac{w}{2}$, $g(x)<\Delta$, as
required before666Note that, we choose $\frac{2x\zeta}{w}$ in $h$ rather than
$\frac{x\zeta}{w}$ as in previous papers, since we actually require that
$g(x)<\Delta$ for any $\left\lVert x\right\rVert_{\infty}>\frac{w}{2}$. Thus,
all $\zeta$ in previous papers should be replaced by $2\zeta$. However, it is
just a constant difference, and does not affect the final results in previous
papers..

  * •

Now, we turn to choose $\Delta$ and $w$. Note that both of them will affect
the norm of $g$. To guarantee $\left\lVert g\right\rVert_{{\mathcal{H}}}\leq
B$, it has been shown [20] that, when $\frac{\Delta}{B}$ is sufficient small,
one can choose $w=\frac{2\zeta\pi l}{\sqrt{\log\frac{B(2\pi
l^{2})^{d/4}h(0)}{2\Delta}}}$ for $k_{\text{SE}}$ and
$w=2\zeta\left(2\Delta\frac{(8\pi^{2})^{(\nu+d/2)/2}}{Bc^{-1/2}h(0)}\right)^{1/\nu}$
for $k_{\text{Mat\'{e}rn}}$, where $c$ is an absolute constant. Note that, we
will later consider $\Delta$ such that $\frac{\Delta}{B}$ is sufficient small.

  * •

From the above choices of $w$ and
$M=\lfloor\left(\frac{1}{w}\right)^{d}\rfloor$, we have

$\displaystyle
M=\Theta\left(\left(\ln\frac{B}{\Delta}\right)^{d/2}\right),\text{ for
}k_{\text{SE}},\text{ and
}M=\Theta\left(\left(\frac{B}{\Delta}\right)^{d/\nu}\right)\text{ for
}k_{\text{Mat\'{e}rn}}$ (11)

Since we choose a sufficient small $\frac{\Delta}{B}$, $M\gg 1$, i.e., there
is an enough number of functions in $\mathcal{F}$.

  * •

Finally, we choose $f$ as a uniformly sampled function from $\mathcal{F}$.

###  A.2 Construction of reward function

We consider the general case that the non-private reward (i.e., before passed
to Laplace mechanism) could be heavy-tailed. That is, the $(1+\alpha)$th
moment of the reward is bounded by some value $v$ for $\alpha\in(0,1]$. To
satisfy this condition, we consider the same reward function in [7], i.e.,

$\displaystyle
y(x)=\begin{cases*}sgn(f(x))\left(\frac{v}{2\Delta}\right)^{1/\alpha}&with
probability $\left(\frac{2\Delta}{v}\right)^{\frac{1}{\alpha}}|f(x)|$\\\
0&otherwise\end{cases*}$ (12)

Note that as long as $\Delta\leq\frac{1}{2}v^{\frac{1}{1+\alpha}}$, Eq. (12)
is a valid distribution.

###  A.3 Preliminary notations and lemmas

Now, let us introduce some necessary notations and results. In the following,
with a bit abuse of notations, we use $\tilde{P}$ (probability) (or
$\tilde{E}$, expectation) for the randomness with respect to non-private
rewards, and $P$ (or $E$) for the private rewards.

  * •

$y_{m}$ denotes the non-private reward (i.e., before the Laplace mechanism)
when the underlying ground function is $f_{m}$. Let $\bar{y}_{m}$ denote the
corresponding private reward. $f_{0}$ denotes the function which has value
zero everywhere, and $y_{0}$ (resp. $\bar{y}_{0}$) is the corresponding non-
private (private) reward. Let
$\bar{Y}_{T}=\\{\bar{y}_{1},\ldots,\bar{y}_{T}\\}$ be the sequence of private
rewards up to time $T$. Let $P_{m}$ (resp. $P_{0}$ ) be the probability
density function of the private reward sequence $\bar{Y}_{T}$ when the
underlying function is $f_{m}$ (resp. $f_{0}$). Similarly, $\tilde{P}_{m}$
(resp. $\tilde{P}_{0}$) for the non-private sequence $Y_{T}$. Further,
$P_{m}(\bar{y}\mid x)$ (resp. $P_{0}(\bar{y}\mid x)$) denotes the conditional
probability of the private reward $\bar{y}$ given the selected point $x$ when
the underlying function is $f_{m}$ (resp. $f_{0}$). Similarly,
$\tilde{P}_{m}({y}\mid x)$ (resp. $\tilde{P}_{0}({y}\mid x)$) for the non-
private reward $y$.

  * •

$\mathbb{E}_{m}$ (resp. $\mathbb{E}_{0}$) denotes expectation (with respect to
the noisy private rewards) when the underlying function is $f_{m}$ (resp.
$f_{0}$). $\mathbb{E}[\cdot]=\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}_{m}[\cdot]$
denotes the expectation averaged over a uniformly random function index.

  * •

$\\{\mathcal{R}_{m}\\}_{m=1}^{M}$ denote a partition of the domain into $M$
regions (i.e., the uniform grid) with $f_{m}$ taking its maximum in the center
of $\mathcal{R}_{m}$. Define the maximum absolute value of $f_{m}$ in the
region $\mathcal{R}_{j}$ as

$\displaystyle{v}_{m}^{j}:=\max_{x\in\mathcal{R}_{j}}|f_{m}(x)|.$ (13)

Define the maximum KL divergence between $P_{0}(\cdot|x)$ and $P_{m}(\cdot|x)$
within region $\mathcal{R}_{j}$ as

$\displaystyle
D_{m}^{j}:=\max_{x\in\mathcal{R}_{j}}D_{kl}(P_{0}(\cdot|x)||P_{m}(\cdot|x))$
(14)

  * •

$N_{j}=\sum_{t=1}^{T}\mathbbm{1}\\{x_{t}\in\mathcal{R}_{j}\\}$ denotes the
number of points within $\mathcal{R}_{j}$ that are selected up to time $T$.

Next, we provide some useful results for our LDP scenario. The first result is
directly from Lemma 5 of [20].

######  Lemma 2.

The function class $\mathcal{F}$ constructed in A.1 satisfies the following
properties:

  1. 1.

$\sum_{j=1}^{M}v_{m}^{j}=O(\Delta)$ for all $m\in[M]$.

  2. 2.

$\sum_{m=1}^{M}v_{m}^{j}=O(\Delta)$ for all $j\in[M]$.

######  Lemma 3.

Under the definitions above, we have
$\mathbb{E}_{m}(N_{j})\leq\mathbb{E}_{0}(N_{j})+T\sqrt{\sum_{j=1}^{M}\mathbb{E}_{0}[N_{j}]D_{m}^{j}}$

###### Proof.

First, by Lemma 3 of [20], which relates two expectations in terms of the
corresponding divergence of the probability distributions, we have

$\displaystyle\mathbb{E}_{m}\left[f(\bar{Y}_{T})\right]\leq\mathbb{E}_{0}\left[f(\bar{Y}_{T})\right]+A\sqrt{D_{kl}(P_{0}||P_{m})},$

for any function $f$ on $\bar{Y}_{T}$ with a bounded range $[0,A]$. Note that
compared to the non-private case in [20], here the randomness is with respect
to the private reward sequences. Then, following Lemma 4 in [20], we have

$\displaystyle
D_{kl}(P_{0}||P_{m})\leq\sum_{j=1}^{M}\mathbb{E}_{0}[N_{j}]D_{m}^{j}.$

Further, note that $\\{x_{t}\\}_{t=1}^{T}$ is a function of $\bar{Y}_{T}$.
Combing the two results above, yields the result. ∎

###  A.4 Analysis of expected cumulative regret

Note that $D_{m}^{j}$ is the key term in our analysis. In particular, in our
LDP setting, it is the KL divergence between two distributions on the
_private_ rewards, which is the key difference compared to previous works.
Nevertheless, as stated before, we can relate it to the non-private case.
Specifically, we have the following bound on it.

######  Lemma 4.

Under the definitions above, if
$\Delta\leq\frac{1}{2}\left(\frac{1}{2}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}$,
we have, for any $\epsilon$-LDP mechanism

$\displaystyle D_{m}^{j}\leq
8(e^{\epsilon}-1)^{2}2^{\frac{1+\alpha}{\alpha}}\left(\frac{\Delta}{v}\right)^{\frac{1}{\alpha}}v_{m}^{j}.$

###### Proof.

First, we have

$\displaystyle
D_{kl}(P_{0}(\cdot|x)||P_{m}(\cdot|x))+D_{kl}(P_{m}(\cdot|x)||P_{0}(\cdot|x))$
$\displaystyle\mathop{\leq}\limits^{(a)}4(e^{\epsilon}-1)^{2}||\tilde{P}_{0}(\cdot|x)-\tilde{P}_{m}(\cdot|x)||^{2}_{TV}$
$\displaystyle\mathop{\leq}\limits^{(b)}8(e^{\epsilon}-1)^{2}D_{kl}(\tilde{P}_{0}(\cdot|x)||\tilde{P}_{m}(\cdot|x)),$

where (a) follows from Theorem 1 of [9] and (b) is due to Pinsker’s
inequality. Then, according to the (non-private) reward distribution in Eq.
(12) and the analysis in [7] (cf., Eq. (17)), we have

$\displaystyle D_{kl}(\tilde{P}_{0}(\cdot|x)||\tilde{P}_{m}(\cdot|x))\leq
2\left(\frac{2\Delta}{v}\right)^{\frac{1}{\alpha}}|f(x)|$

for
$\Delta\leq\frac{1}{2}\left(\frac{1}{2}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}$.
Thus, combing the results above with the definitions of $D_{m}^{j}$ and
$v_{m}^{j}$ in Eqs. (14) and (13), yields the result. ∎

Now, we are well-prepared to analyze the lower bounds of the expected
cumulative regret in the LDP setting.

First, note that by the decomposition of expectation, we have
$\mathbb{E}_{m}[f(x_{t})]\leq\sum_{j=1}^{M}\mathbb{P}_{m}[x_{t}\in\mathcal{R}_{j}]v_{m}^{j}$.
Hence,

$\displaystyle\mathbb{E}_{m}\left[\sum_{t=1}^{T}f(x_{t})\right]\leq\sum_{j=1}^{M}v_{m}^{j}\mathbb{E}_{m}\left[N_{j}\right]\mathop{\leq}\limits^{(a)}\sum_{j=1}^{M}v_{m}^{j}\left(\mathbb{E}_{0}(N_{j})+T\sqrt{\sum_{j^{\prime}=1}^{M}\mathbb{E}_{0}[N_{j^{\prime}}]D_{m}^{j^{\prime}}}\right),$

where (a) directly follows from Lemma 3. Now, taking the average over
$m\in[M]$, yields

$\displaystyle\mathbb{E}\left[\sum_{j=1}^{T}f(x_{t})\right]\leq\frac{1}{M}\sum_{m=1}^{M}\sum_{j=1}^{M}v_{m}^{j}\left(\mathbb{E}_{0}(N_{j})+T\sqrt{\sum_{j^{\prime}=1}^{M}\mathbb{E}_{0}[N_{j^{\prime}}]D_{m}^{j^{\prime}}}\right)$
(15)

For the first term, we can bound it as follows:

$\displaystyle\frac{1}{M}\sum_{m=1}^{M}\sum_{j=1}^{M}v_{m}^{j}\mathbb{E}_{0}[N_{j}]=\frac{1}{M}\sum_{j=1}^{M}\sum_{m=1}^{M}v_{m}^{j}\mathbb{E}_{0}[N_{j}]\mathop{\leq}\limits^{(a)}O\left(\frac{\Delta}{M}\right)\sum_{j=1}^{M}\mathbb{E}_{0}\left[N_{j}\right]\mathop{=}\limits^{(b)}O\left(\frac{T\Delta}{M}\right),$
(16)

where (a) follows from the second part of Lemma 2, and (b) holds since
$\sum_{j=1}^{M}N_{j}=T$.

For the second term, we have when
$\Delta\leq\frac{1}{2}\left(\frac{1}{2}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}$

$\displaystyle\frac{1}{M}\sum_{m=1}^{M}\sum_{j=1}^{M}v_{m}^{j}T\sqrt{\sum_{j^{\prime}=1}^{M}\mathbb{E}_{0}[N_{j^{\prime}}]D_{m}^{j^{\prime}}}$
$\displaystyle\mathop{=}\limits^{(a)}O(T\Delta)\frac{1}{M}\sum_{m=1}^{M}\sqrt{\sum_{j^{\prime}=1}^{M}\mathbb{E}_{0}[N_{j^{\prime}}]D_{m}^{j^{\prime}}}$
$\displaystyle\mathop{\leq}\limits^{(b)}O(T\Delta)\sqrt{\frac{1}{M}\sum_{m=1}^{M}\sum_{j^{\prime}=1}^{M}\mathbb{E}_{0}[N_{j^{\prime}}]D_{m}^{j^{\prime}}}$
$\displaystyle\mathop{\leq}\limits^{(c)}O(T\Delta)(e^{\epsilon}-1)2^{\frac{1+\alpha}{2\alpha}}\left(\frac{\Delta}{v}\right)^{\frac{1}{2\alpha}}\sqrt{\frac{1}{M}\sum_{m=1}^{M}\sum_{j^{\prime}=1}^{M}\mathbb{E}_{0}[N_{j^{\prime}}]v_{m}^{j^{\prime}}}$
$\displaystyle\mathop{\leq}\limits^{(d)}O\left(T\Delta(e^{\epsilon}-1)\frac{(2\Delta)^{\frac{1+\alpha}{2\alpha}}}{v^{\frac{1}{2\alpha}}}\sqrt{\frac{T}{M}}\right),$
(17)

where (a) follows from the first part of Lemma 2; (b) follows from Jensen’s
inequality; (c) follows from Lemma 4; (d) holds by Eq. (16). Now, substituting
Eqs. (16) and (17) into Eq. (15), yields

$\displaystyle\mathbb{E}\left[\sum_{j=1}^{T}f(x_{t})\right]\leq
CT\Delta\left(\frac{1}{M}+(e^{\epsilon}-1)\frac{(2\Delta)^{\frac{1+\alpha}{2\alpha}}}{v^{\frac{1}{2\alpha}}}\sqrt{\frac{T}{M}}\right)$

for some constant $C$, when
$\Delta\leq\frac{1}{2}\left(\frac{1}{2}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}$.

Observe that $f(x^{*})=2\Delta$ by the construction process in A.1, then the
cumulative expected regret is given by

$\displaystyle\mathbb{E}\left[R_{T}\right]=Tf(x^{*})-\mathbb{E}\left[\sum_{j=1}^{T}f(x_{t})\right]\geq
T\Delta\left(2-\frac{C}{M}-C(e^{\epsilon}-1)\frac{(2\Delta)^{\frac{1+\alpha}{2\alpha}}}{v^{\frac{1}{2\alpha}}}\sqrt{\frac{T}{M}}\right),$

when
$\Delta\leq\frac{1}{2}\left(\frac{1}{2}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}$.
Recall that we always choose a sufficient $\frac{\Delta}{B}$, and hence by Eq.
(11), $M$ is sufficient large. Thus, $\frac{C}{M}\leq\frac{1}{2}$. As a
result, we have

$\displaystyle\mathbb{E}\left[R_{T}\right]$ $\displaystyle\geq
T\Delta\left(\frac{3}{2}-C(e^{\epsilon}-1)\frac{(2\Delta)^{\frac{1+\alpha}{2\alpha}}}{v^{\frac{1}{2\alpha}}}\sqrt{\frac{T}{M}}\right)$
$\displaystyle\geq T\Delta,\text{ for
}\Delta\leq\frac{1}{2}\left(\min\left\\{\frac{1}{2},\frac{M}{4C^{2}(e^{\epsilon}-1)^{2}T}\right\\}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}.$

Therefore, if $M\leq 2C^{2}(e^{\epsilon}-1)^{2}T$, then we have

$\displaystyle\mathbb{E}\left[R_{T}\right]=\Omega\left(v^{\frac{1}{1+\alpha}}T^{\frac{1}{1+\alpha}}M^{\frac{\alpha}{1+\alpha}}(e^{\epsilon}-1)^{-\frac{2\alpha}{1+\alpha}}\right)\text{
for
}\frac{1}{4}\left(\frac{M}{4C^{2}(e^{\epsilon}-1)^{2}T}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}\leq\Delta\leq\frac{1}{2}\left(\frac{M}{4C^{2}(e^{\epsilon}-1)^{2}T}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}$
(18)

Now, it only remains to combine $M$ (in Eq. (11)) and Eq. (18) to arrive at
the specific lower bound for $k_{\text{SE}}$ and $k_{\text{Mat\'{e}rn}}$,
respectively.

  * •

For $k_{\text{SE}}$, note that we choose
$M=\Theta\left(\left(\ln\frac{B}{\Delta}\right)^{d/2}\right)$ in Eq. (11).
Combing it with the upper and lower bounds on $\Delta$ in Eq. (18), yields
that
$\Delta=\Theta\left(\left(\frac{\left(\ln\frac{B}{\Delta}\right)^{d/2}}{(e^{\epsilon}-1)^{2}T}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}\right)$.
This, in turn, implies that

$\displaystyle\ln\frac{B}{\Delta}=\ln\frac{B\left(T(e^{\epsilon}-1)^{2}\right)^{\frac{\alpha}{1+\alpha}}}{v^{\frac{1}{1+\alpha}}}-\ln\left(\Theta(1)\left(\ln\frac{B}{\Delta}\right)^{\frac{d\alpha}{2(1+\alpha)}}\right).$

Since $d=O(1)$, and $\frac{\alpha}{1+\alpha}\in(0,1/2]$, the second term above
behaves like $\Theta(\ln\ln\frac{B}{\Delta})$, which is at most
$\frac{1}{2}\ln\frac{B}{\Delta}$ for sufficiently small $\frac{\Delta}{B}$.
Thus, we have
$\ln\frac{B}{\Delta}=\Theta\left(\ln\frac{B\left(T(e^{\epsilon}-1)^{2}\right)^{\frac{\alpha}{1+\alpha}}}{v^{\frac{1}{1+\alpha}}}\right)$,
which implies that

$\displaystyle
M=\Theta\left(\left(\ln\frac{B\left(T(e^{\epsilon}-1)^{2}\right)^{\frac{\alpha}{1+\alpha}}}{v^{\frac{1}{1+\alpha}}}\right)^{\frac{d}{2}}\right)$

and

$\displaystyle\Delta=\Theta\left(\left(\ln\frac{B\left(T(e^{\epsilon}-1)^{2}\right)^{\frac{\alpha}{1+\alpha}}}{v^{\frac{1}{1+\alpha}}}\right)^{\frac{d\alpha}{2(1+\alpha)}}T^{-\frac{\alpha}{1+\alpha}}(e^{\epsilon}-1)^{-\frac{2\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}\right).$

Note that the choice $M$ ensures that $M\leq 2C^{2}(e^{\epsilon}-1)^{2}T$ and
the choice of $\Delta$ guarantees that $\frac{\Delta}{B}$ is indeed
sufficiently small as long as $v^{\frac{1}{1+\alpha}}\leq
C_{1}B(T(e^{\epsilon}-1)^{2})^{\frac{\alpha}{1+\alpha}}$ for some sufficiently
small constant $C_{1}$. This can always hold since $B,v,\epsilon$ are all
constants that do not increase with $T$. Finally, substituting $M$ into Eq.
(18), yields

$\displaystyle\mathbb{E}\left[R_{T}\right]$
$\displaystyle=\Omega\left(\left(\ln\frac{B\left(T(e^{\epsilon}-1)^{2}\right)^{\frac{\alpha}{1+\alpha}}}{v^{\frac{1}{1+\alpha}}}\right)^{\frac{d\alpha}{2(1+\alpha)}}T^{\frac{1}{1+\alpha}}(e^{\epsilon}-1)^{-\frac{2\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}\right)$
$\displaystyle\mathop{=}\limits^{(a)}\Omega\left(\left(\ln\frac{B^{\frac{1+\alpha}{\alpha}}T(e^{\epsilon}-1)^{2}}{v^{\frac{1}{\alpha}}}\right)^{\frac{d\alpha}{2(1+\alpha)}}T^{\frac{1}{1+\alpha}}(e^{\epsilon}-1)^{-\frac{2\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}\right)$

where (a) holds due to $d=O(1)$ and
$\frac{\alpha}{1+\alpha}\in(0,\frac{1}{2}]$.

  * •

For $k_{\text{Mat\'{e}rn}}$, from Eq. (11), we have
$M=\Theta\left(\left(\frac{B}{\Delta}\right)^{d/\nu}\right)$. Plug it into the
upper and lower bounds on $\Delta$ in Eq. (18), we have
$\Delta=\Theta\left(\left(\frac{1}{T}\frac{1}{(e^{\epsilon}-1)^{2}}\left(\frac{B}{\Delta}\right)^{\frac{d}{\nu}}\right)^{\frac{\alpha}{1+\alpha}}v^{\frac{1}{1+\alpha}}\right)$.
This further implies that

$\displaystyle\Delta=\Theta\left(v^{\frac{\nu/(1+\alpha)}{\nu+d\alpha/(1+\alpha)}}B^{\frac{d\alpha/(1+\alpha)}{\nu+d\alpha/(1+\alpha)}}(T(e^{\epsilon}-1)^{2})^{-\frac{\nu\alpha/(1+\alpha)}{\nu+d\alpha/(1+\alpha)}}\right)$

and

$\displaystyle
M=\Theta\left(v^{-\frac{d/(1+\alpha)}{\nu+d\alpha/(1+\alpha)}}B^{\frac{d}{\nu+d\alpha/(1+\alpha)}}(T(e^{\epsilon}-1)^{2})^{\frac{d\alpha/(1+\alpha)}{\nu+d\alpha/(1+\alpha)}}\right)$

As before, the choice of $M$ and $\Delta$ above can guarantee our necessary
conditions. Finally, substituting $M$ into Eq. (18), yields

$\displaystyle\mathbb{E}\left[R_{T}\right]=\Omega\left(v^{\frac{\nu}{\nu(1+\alpha)+d\alpha}}T^{\frac{\nu+d\alpha}{\nu(1+\alpha)+d\alpha}}{(e^{\epsilon}-1)^{\frac{-2\alpha}{1+\alpha}}}(e^{\epsilon}-1)^{\frac{2d\alpha^{2}}{(1+\alpha)(\nu(1+\alpha)+d\alpha)}}B^{\frac{d\alpha}{\nu(1+\alpha)+d\alpha}}\right).$

∎

##  Appendix B Proof of Lemma 1

###### Proof.

By the reproducing property of RKHS, we have $f(x)=\langle
f,k(x,\cdot)\rangle_{\mathcal{H}}\leq\left\lVert
f\right\rVert_{\mathcal{H}}\sqrt{k(x,x)}\leq B$ for any $x\in\mathcal{D}$.
Combining this with the upper bound $R$ on the noise $\eta_{t}$, yields that
the sensitivity of information is at most $2(B+R)$. Thus, $\epsilon$-LDP
follows directly from the Laplace mechanism [11]. ∎

##  Appendix C Proof of Theorem 2

###### Proof.

Note that in our LDP setting with additional independent Laplace noise,
$\mathbb{E}\left[|\bar{y}_{t}|^{2}\mid\mathcal{F}_{t-1}\right]\leq
B^{2}+R^{2}+2\mathcal{L}^{2}$, where $\mathcal{L}=\frac{2(B+R)}{\epsilon}$.
Hence, Theorem 4 of [7] is satisfied with $\alpha=1$ and
$v=B^{2}+R^{2}+8(B+R)^{2}/\epsilon^{2}$, which directly leads to our results.
∎

##  Appendix D Proofs of Theorems 3 and 4

###  D.1 Preliminaries

In this section, we first present some common notations and useful results for
the proofs of the two theorems.

Similar to [7], we define $\varphi:\mathcal{D}\to\mathcal{H}_{k}(\mathcal{D})$
as the associated feature map of the kernel $k$ such that
$k(x,y)=\langle\varphi(x),\varphi(y)\rangle_{\mathcal{H}}$ for any
$x,y\in\mathcal{D}$ From the reproducing property, we have for any
$f\in\mathcal{H}_{k}(\mathcal{D})$, $f(x)=\langle
f,\varphi(x)\rangle_{\mathcal{H}}$. For a set $\\{x_{1},\ldots,x_{t}\\}$, we
define a operator $\Phi_{t}:\mathcal{H}_{k}(\mathcal{D})\to\mathbb{R}^{t}$
such that for any $f\in\mathcal{H}_{k}(\mathcal{D})$,
$\Phi_{t}f=[\langle\varphi(x_{1}),f\rangle_{\mathcal{H}},\ldots,\langle\varphi(x_{t}),f\rangle_{\mathcal{H}}]^{T}$,
which is also equal to $[f(x_{1}),\ldots,f(x_{t})]^{T}$ by the reproducing
property. Define the adjoint of $\Phi_{t}$ by
$\Phi_{t}^{T}:\mathbb{R}^{t}\to\mathcal{H}_{k}(\mathcal{D})$. For any
$\lambda>0$, define $V_{t}=\Phi_{t}^{T}\Phi_{t}+\lambda{I}_{\mathcal{H}}$,
where $I_{\mathcal{H}}$ denotes the identity operator. For a positive definite
operator $V:\mathcal{H}_{k}(\mathcal{D})\to\mathcal{H}_{k}(\mathcal{D})$, we
define the inner product
$\langle\cdot,\cdot\rangle_{V}:=\langle\cdot,V\cdot\rangle_{\mathcal{H}}$ with
the corresponding norm as $\left\lVert\cdot\right\rVert_{V}$.

Based on the definitions above, we have the following result, which is
directly from Eq.(13) of [6].

######  Lemma 5.

Under the definitions above, we have
$\sigma_{t}^{2}(x)=\lambda\left\lVert\varphi(x)\right\rVert_{V_{t}^{-1}}^{2}$.

The following lemma summarizes useful properties for linear operators, which
is from Lemma 3 of [7].

######  Lemma 6.

For any linear operator $A:\mathcal{H}_{k}(\mathcal{D})\to\mathbb{R}^{t}$ and
its adjoint $A^{T}:\mathbb{R}^{t}\to\mathcal{H}_{k}(\mathcal{D})$, for any
$\lambda>0$, we have

$\displaystyle(A^{T}A+\lambda I_{\mathcal{H}})^{-1}A^{T}=A^{T}(AA^{T}+\lambda
I_{t})^{-1}$ (19)

and

$\displaystyle I_{\mathcal{H}}-A^{T}(AA^{T}+\lambda
I_{t})A=\lambda(A^{T}A+\lambda I_{\mathcal{H}})^{-1}.$ (20)

The following result is a standard result in BO, which can be obtained from
Lemma 6 of [7] and Cauchy-Schwartz inequality.

######  Lemma 7.

If $k(x,x)\leq 1$, for any $x\in\mathcal{D}$, we have

$\displaystyle\sum_{t=1}^{T}\sigma_{t-1}(x)=O(\sqrt{\gamma_{T}T}).$

###  D.2 Proof of Theorem 3

###### Proof.

First, as pointed out in the proof sketch, we establish a bound on
$|f(x)-\hat{\mu}_{t}(x)|$, in which
$\hat{\mu}_{t}(x)=k_{t}(x)^{T}(K_{t}+\lambda I)^{-1}\hat{Y}_{t}$. Following
[7], we define $\hat{\eta}_{t}=\hat{y}_{t}-f(x_{t})$,
$\hat{N}_{t}=[\hat{\eta}_{1},\ldots,\hat{\eta}_{t}]^{T}$ and
$f_{t}=[f(x_{1}),\ldots,f(x_{t})]^{T}$. Hence,
$\hat{Y}_{t}=\hat{N}_{t}+f_{t}$. Define
$\alpha_{t}(x)=k_{t}(x)^{T}(K_{t}+\lambda I)^{-1}f_{t}$, then by the
preliminaries above, we have

$\displaystyle
f(x)-\alpha_{t}(x)=\langle\varphi(x),(I_{\mathcal{H}}-\Phi_{t}^{T}(\Phi_{t}\Phi_{t}^{T}+\lambda
I_{t})^{-1}\Phi_{t})f\rangle_{\mathcal{H}}\mathop{=}\limits^{(a)}\lambda\langle\varphi(x),f\rangle_{V_{t}^{-1}}$

where (a) holds by Eq. (20). Similarly, we have

$\displaystyle k_{t}(x)^{T}(K_{t}+\lambda
I)^{-1}\hat{N}_{t}=\langle\varphi(x),\Phi_{t}^{T}(\Phi_{t}\Phi_{t}^{T}+\lambda
I_{t})^{-1}\hat{N}_{t}\rangle_{\mathcal{H}}=\langle\varphi(x),\Phi_{t}^{T}\hat{N}_{t}\rangle_{V_{t}^{-1}},$

which holds by Eq. (19). Based on the results above, we have

$\displaystyle|f(x)-\hat{\mu}_{t}(x)|$
$\displaystyle\leq|\lambda\langle\varphi(x),f\rangle_{V_{t}^{-1}}|+|\langle\varphi(x),\Phi_{t}^{T}\hat{N}_{t}\rangle_{V_{t}^{-1}}|$
$\displaystyle\mathop{\leq}\limits^{(a)}\lambda\left\lVert\varphi(x)\right\rVert_{V_{t}^{-1}}\left\lVert
V_{t}^{-1/2}f\right\rVert_{\mathcal{H}}+\left\lVert\varphi(x)\right\rVert_{V_{t}^{-1}}\left\lVert\Phi_{t}^{T}\hat{N}_{t}\right\rVert_{V_{t}^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(b)}\lambda^{1/2}\left\lVert\varphi(x)\right\rVert_{V_{t}^{-1}}\left\lVert
f\right\rVert_{\mathcal{H}}+\left\lVert\varphi(x)\right\rVert_{V_{t}^{-1}}\left\lVert\Phi_{t}^{T}\hat{N}_{t}\right\rVert_{V_{t}^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(c)}\sigma_{t}(x)\left(B+\lambda^{-1/2}\left\lVert\Phi_{t}^{T}\hat{N}_{t}\right\rVert_{V_{t}^{-1}}\right)$

where (a) follows from Cauchy-Schwartz inequality; (b) is true since
$V_{t}^{-1}\preceq\lambda^{-1}I_{\mathcal{H}}$; (c) follows from the fact that
$\left\lVert f\right\rVert_{\mathcal{H}}\leq B$ and Lemma 5.

The key term is
$\left\lVert\Phi_{t}^{T}\hat{N}_{t}\right\rVert_{V_{t}^{-1}}=\lVert\sum_{\tau=1}^{t}\hat{\eta}_{\tau}\varphi(x_{\tau})\rVert_{V_{t}^{-1}}$,
which can be handled by the self-normalized inequality if $\hat{\eta}_{\tau}$
is sub-Gaussian. However, in our LDP setting, it is not due to Laplace noise.
To overcome this issue, we will divide it into two parts. In particular,
similar to [7], we define
$\xi_{t}=\hat{\eta}_{t}-\mathbb{E}\left[\hat{\eta}_{t}\mid\mathcal{F}_{t-1}\right]$.
Now, the key term can be written as

$\displaystyle\lVert\sum_{\tau=1}^{t}\hat{\eta}_{\tau}\varphi(x_{\tau})\rVert_{V_{t}^{-1}}=\underbrace{\lVert\sum_{\tau=1}^{t}{\xi}_{\tau}\phi(x_{\tau})\rVert_{V_{t}^{-1}}}_{\mathcal{T}_{1}}+\underbrace{\lVert\sum_{\tau=1}^{t}\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]\phi(x_{\tau})\rVert_{V_{t}^{-1}}.}_{\mathcal{T}_{2}}$

For $\mathcal{T}_{1}$, note that
$\xi_{t}=\hat{y}_{t}-\mathbb{E}\left[\hat{y}_{t}\mid\mathcal{F}_{t-1}\right]$
and $\hat{y}_{t}=\bar{y}_{t}\mathbbm{1}_{|\bar{y}_{t}|\leq b_{t}}$. This
implies that $\xi_{t}$ is bounded by $2b_{t}$, and hence sub-Gaussian. Thus,
by the self-normalized inequality for the RKHS-valued process in [10, 7], we
have for any $\delta\in(0,1]$, with probability at least $1-\delta$, we have
for all $t\in\mathbb{N}$

$\displaystyle\mathcal{T}_{1}\leq 2b_{t}\sqrt{2(\gamma_{t}+\ln(1/\delta))}.$

For $\mathcal{T}_{2}$, we can first bound it as
$\mathcal{T}_{2}\leq\sqrt{\sum_{\tau=1}^{t}\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]^{2}}$.
This is due to the following property. For any $a\in\mathbb{R}^{t}$,

$\displaystyle\left\lVert\sum_{\tau=1}^{t}a_{\tau}\varphi(x_{\tau})\right\rVert_{V_{t}^{-1}}^{2}=a^{T}\Phi_{t}(\Phi_{t}^{T}\Phi_{t}+\lambda
I_{\mathcal{H}})^{-1}\Phi_{t}^{T}a\mathop{=}\limits^{(a)}a^{T}\Phi_{t}\Phi_{t}^{T}(\Phi_{t}\Phi_{t}^{T}+\lambda
I_{t})^{-1}a\mathop{\leq}\limits^{(b)}\left\lVert a\right\rVert_{2}^{2},$

where (a) holds by Eq. (19); (b) is true since
$\Phi_{t}\Phi_{t}^{T}(\Phi_{t}\Phi_{t}^{T}+\lambda I_{t})^{-1}\preceq I_{t}$.

Further, note that
$\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]=-\mathbb{E}\left[\bar{y}_{\tau}\mathbbm{1}_{|\tilde{y}_{\tau}|>b_{\tau}}|\mathcal{F}_{\tau-1}\right]$.
Hence, by Cauchy-Schwartz inequality with $b_{\tau}=B+R+\mathcal{L}\ln\tau$,
we have

$\displaystyle\mathbb{E}\left[\hat{\eta}_{\tau}|\mathcal{F}_{\tau-1}\right]^{2}\leq\mathbb{E}\left[\bar{y}_{\tau}^{2}|\mathcal{F}_{\tau-1}\right]\mathbbm{P}(|L|>\mathcal{L}\ln\tau)\leq
K\frac{1}{\tau},$

where $K:=B^{2}+R^{2}+2\mathcal{L}^{2}$. The last inequality holds since
$|L|\sim\text{Exp}(1/\mathcal{L})$. Therefore, by the property of Harmonic
sum, we have

$\displaystyle\mathcal{T}_{2}\leq\sqrt{K(\ln t+1)}.$

Hence, by setting

$\displaystyle\beta_{t+1}=B+\frac{2\sqrt{2}}{\sqrt{\lambda}}b_{t}\sqrt{\gamma_{t}+\ln(1/\delta)}+\frac{1}{\sqrt{\lambda}}\sqrt{K(\ln
t+1)},$

we have for any $\delta\in(0,1]$, with probability at least $1-\delta$,
uniformly over all $t\geq 1$ and $x\in\mathcal{D}$,

$\displaystyle|f(x)-\hat{\mu}_{t}(x)|\leq\beta_{t+1}\sigma_{t}(x).$ (21)

Now, the following analysis is standard. First,

$\displaystyle r_{t}=f(x^{*})-f(x_{t})\leq 2\beta_{t}\sigma_{t-1}(x),$

which follows from Eq. (21) and the GP-UCB like algorithm. Hence, for any
$\delta\in(0,1]$, with probability at least $1-\delta$, the cumulative regret
is given by

$\displaystyle R_{T}=\sum_{t=1}^{T}r_{t}\leq
2\beta_{T}\sum_{t=1}^{T}\sigma_{t-1}(x)\mathop{=}\limits^{(a)}O(\beta_{T}\sqrt{\gamma_{T}T})=O\left(\vartheta\sqrt{\ln
T\gamma_{T}T}+\vartheta\sqrt{T}\ln
T\sqrt{\gamma_{T}(\gamma_{T}+\ln(1/\delta))}\right),$

where $\vartheta=(B+R)/\epsilon$ and (a) holds by Lemma 7. ∎

###  D.3 Proof of Theorem 4

Before the proof, we first present some useful results regarding Nyström
approximation based on [5, 7]. One key notation difference here is that in
MoMA-GP-UCB, the main index is $n$ (i.e., epoch) rather than $t$, since the
Nyström approximation is only updated every epoch, which consists of $k$
iterations.

First, we present the algorithm for NyströmEmbedding used in MoMA-GP-UCB based
on [7], as shown in Algorithm 4. The basic idea is to first sample a random
number $m_{n}$ of points from the set $\\{x_{1},\ldots,x_{n}\\}$ to construct
a dictionary $\mathcal{D}_{n}=\\{x_{i_{1}},\ldots,x_{i_{m_{n}}}\\}$,
$i_{j}\in[n]$. Each data point $x_{i}$, $i\in[n]$ is included with probability
$p_{n,i}=\min\\{q\tilde{\sigma}_{n-1}^{2}(x_{i})),1\\}$. Then, the finite
approximation of the feature map is computed in line $7$. Note that
$A^{\dagger}$ denotes the pseudo inverse of any matrix $A$.
$K_{\mathcal{D}_{n}}=[k(u,v)]_{u,v\in\mathcal{D}_{n}}$ and
$k_{\mathcal{D}_{n}}(x)=[k(x_{i_{1}},x),\ldots,k(x_{i_{m_{n}}},x)]^{T}$.

Algorithm 4 NyströmEmbedding

1:Input: $\\{(x_{i},\tilde{\sigma}_{t-1}(x_{i}))\\}_{i=1}^{t}$, $q$

2:Set: $\mathcal{D}_{0}=\emptyset$

3:for $t=1,2,3,\ldots,t$ do

4: Sample
$z_{t,i}\sim\text{Bern}(\min\\{q\tilde{\sigma}_{t-1}^{2}(x_{i})),1\\})$

5: If $z_{t,i}=1$, then set $\mathcal{D}_{t}=\mathcal{D}_{t}\cup\\{x_{i}\\}$

6:end for

7:Return
$\tilde{\varphi}_{t}(x)=\left(K_{\mathcal{D}_{t}}^{1/2}\right)^{\dagger}k_{\mathcal{D}_{t}}(x)$

The following result states one equivalent definition of an
$\epsilon$-accurate dictionary $\mathcal{D}_{n}$, based on Lemma 16 of [7].

######  Definition 2 ($\varepsilon$-accurate).

For any $\varepsilon\in(0,1)$, a dictionary
$\mathcal{D}_{n}\subseteq\\{x_{1},\ldots,x_{n}\\}$ is said to be
$\varepsilon$-accurate if
$V_{\mathcal{D}_{n}}:=\Phi_{n}^{T}S_{n}^{2}\Phi_{n}+\lambda I_{\mathcal{H}}$
satisfies

$\displaystyle(1-\epsilon)V_{n}\preceq
V_{\mathcal{D}_{n}}\preceq(1+\epsilon)V_{n}$

where $\mathcal{S}_{n}$ is the selection matrix associated with the dictionary
$\mathcal{D}_{n}$ such that $[S_{n}]_{i,i}=1/\sqrt{p_{n,i}}$ if
$x_{i}\in\mathcal{D}_{n}$ and $0$, elsewhere.

The following results states the key properties of NyströmEmbedding, which is
directly adapted from Lemma 17 of [7].

######  Lemma 8.

For any $\varepsilon\in(0,1)$ and $\delta\in(0,1]$, set
$\rho=\frac{1+\varepsilon}{1-\varepsilon}$ and
$q=\frac{6\rho\ln(2T/\delta)}{\varepsilon^{2}}$. Let $E_{1,n}$ denote the
event that $\mathcal{D}_{n}$ is $\varepsilon$-accurate, and $E_{2,n}$ denote
the event that $m_{n}\leq 6\rho\left(1+\frac{1}{\lambda}\right)q\gamma_{t}$.
Then, with probability at least $1-\delta$, uniformly over all $n\in[N]$, both
$E_{1,n}$ and $E_{2,n}$ are true, i.e., $\mathbb{P}[\cap_{n=1}^{N}(E_{1,n}\cup
E_{2,n})]\geq 1-\delta$.

We also let
$\mathcal{G}_{n}=\sigma\left(\\{x_{i},(z_{i,j})_{j=1}^{i}\\}_{i=1}^{n}\right)$,
$n\geq 1$ denote the $\sigma$-algebra generated by the arms played and the
outcomes of the NyströmEmbedding algorithm up to time $t$. Note that
$(\mathcal{G}_{n})_{n\geq 1}$ defines a filtration and both $E_{1,n}$ and
$E_{2,n}$ are $(\mathcal{G}_{n})_{n\geq 1}$ measurable.

Based on the definitions above, we have the following results, which are
useful for establishing the high probability confidence bound. The first
result is adapted from the proof of Lemma 20 in [7] (cf. Eq.(25) and (26)),
and the second one directly follows from Lemma 19 of [7].

######  Lemma 9.

Given a filtration $(\mathcal{G}_{n})_{n\geq 1}$ such that $E_{1,n}$ is true
(i.e., $\varepsilon$-accurate), we have

  1. 1.

$|f(x)-\tilde{\mu}_{n}(x)|\leq
B\left(1+\frac{1}{\sqrt{1-\varepsilon}}\right)\tilde{\sigma}_{n}(x)+\lambda^{-1/2}\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}\tilde{\sigma}_{n}(x).$

  2. 2.

$\tilde{\sigma}_{n}(x)\leq\rho\sigma_{n}(x)$, where
$\rho=\frac{1+\varepsilon}{1-\varepsilon}$.

The following two lemmas state the key properties of the least-square-
estimators (LSEs) constructed in MoMA-GP-UCB, which are mainly inspired from
[22].

######  Lemma 10.

Let $\gamma:=(9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}$,
for any $j\in[k]$, we have

$\displaystyle\mathbb{P}\left(\left\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,j}\right\rVert_{\tilde{V}_{n}}\leq\gamma\right)\geq\frac{3}{4}.$

###### Proof.

Recall that in MoMA-GP-UCB,
$\tilde{\theta}_{n,j}=\tilde{V}_{n}^{-1}\sum_{i=1}^{n}y_{i,j}\tilde{\varphi}_{n}(x_{i})=\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}Y_{n}$,
where $Y_{n}=[y_{1,j},y_{2,j},\ldots,y_{n,j}]^{T}$. Hence, we have

$\displaystyle\left\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,j}\right\rVert_{\tilde{V}_{n}}=\left\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}Y_{n}\right\rVert_{\tilde{V}_{n}}=\left\lVert\tilde{V}_{n}^{-\frac{1}{2}}\tilde{\Phi}_{n}^{T}(Y_{n}-f_{n})\right\rVert_{2}=\sqrt{\sum_{i=1}^{m_{n}}(u_{i}^{T}(Y_{n}-f_{n}))^{2}},$

where $u_{i}^{T}$, $i\in[m_{n}]$ are the rows of
$\tilde{V}_{n}^{-\frac{1}{2}}\tilde{\Phi}_{n}^{T}$. By Lemma 12 in [7], we can
bound the $(1+\alpha)$th norm. Specifically, we have $\left\lVert
u_{i}\right\rVert_{1+\alpha}\leq n^{\frac{1-\alpha}{2(1+\alpha)}}$. In the
following, we let $\eta_{l,j}=y_{l,j}-f(x_{l})$.

Then, we will follow a similar analysis as in [22] (cf. Lemma 2). First, we
bound the following probability

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{m_{n}}\left(\sum_{\tau=1}^{n}u_{i,\tau}\eta_{\tau,j}\right)^{2}>\gamma^{2}\right)\leq\underbrace{\mathbb{P}\left(\exists
i,\tau,|u_{i,\tau}\eta_{\tau,j}|>\gamma\right)}_{\mathcal{T}_{1}}+\underbrace{\mathbb{P}\left(\sum_{i=1}^{m_{n}}\left(\sum_{\tau=1}^{n}u_{i,\tau}\eta_{\tau,j}\mathbbm{1}_{|u_{i,\tau}\eta_{\tau,j}|\leq\gamma}\right)^{2}>\gamma^{2}\right)}_{\mathcal{T}_{2}}.$

For $\mathcal{T}_{1}$, by using union bound and Markov’s inequality along with
the norm bound on $u_{i}$, we have

$\displaystyle\mathcal{T}_{1}\leq\frac{\sum_{i=1}^{m_{n}}\sum_{\tau=1}^{n}\mathbb{E}\left[|u_{i,\tau}\eta_{\tau,j}|^{1+\alpha}\right]}{\gamma^{1+\alpha}}\leq\frac{\sum_{i=1}^{m_{n}}\sum_{\tau=1}^{n}|u_{i,\tau}|^{1+\alpha}c}{\gamma^{1+\alpha}}\leq\frac{m_{n}cn^{\frac{1-\alpha}{2}}}{\gamma^{1+\alpha}}.$

For $\mathcal{T}_{2}$, by using Markov’s inequality and the fact that
$\mathbb{E}\left[u_{i,\tau}\eta_{\tau,j}\mathbbm{1}_{|u_{i,\tau}\eta_{\tau,j}|\leq\gamma}\mid\mathcal{F}_{\tau-1}\right]=-\mathbb{E}\left[u_{i,\tau}\eta_{\tau,j}\mathbbm{1}_{|u_{i,\tau}\eta_{\tau,j}|>\gamma}\mid\mathcal{F}_{\tau-1}\right]$,
we have

$\displaystyle\mathcal{T}_{2}\leq\sum_{i=1}^{m_{n}}\left(\frac{\sum_{\tau=1}^{n}|u_{i,\tau}|^{1+\alpha}c}{\gamma^{1+\alpha}}+\left(\frac{\sum_{\tau=1}^{n}|u_{i,\tau}|^{1+\alpha}c}{\gamma^{1+\alpha}}\right)^{2}\right)\leq\frac{m_{n}cn^{\frac{1-\alpha}{2}}}{\gamma^{1+\alpha}}+m_{n}\left(\frac{cn^{\frac{1-\alpha}{2}}}{\gamma^{1+\alpha}}\right)^{2}.$

The final result is obtained by substituting the value of $\gamma$, i.e.,
$(9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}$. ∎

######  Lemma 11.

If $\gamma=(9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}$,
$k=\lceil 24\ln\left(\frac{eT}{\delta}\right)\rceil$ and $\delta\in(0,1]$,
then with probability at least $1-\delta$, uniformly over $n\in[N]$

$\displaystyle\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}\leq
3\gamma.$

where $k^{*}$ is chosen based on the line $12$ of MoMA-GP-UCB algorithm.

###### Proof.

This result can be proved by adapting the proof of Lemma 3 in [22]. We define
$b_{j}:=\mathbbm{1}_{\left\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,j}\right\rVert_{\tilde{V}_{n}}>\gamma}$,
$p_{j}:=\mathbb{P}(b_{j}=1)$ and
$B_{\tilde{V}_{n}}(\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n},\gamma):=\\{\theta:\left\lVert\theta-\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}\right\rVert_{\tilde{V}_{n}}\leq\gamma\\}$.

First, by Lemma 10, we have $p_{j}<\frac{1}{4}$. Then, by Hoeffding’s
inequality, we have

$\displaystyle\mathbb{P}\left(\sum_{j=1}^{k}b_{j}\geq\frac{k}{3}\right)<\mathbb{P}\left(\sum_{j=1}^{k}b_{j}-p_{j}\geq\frac{k}{12}\right)\leq
e^{-\frac{k}{24}}.$

This means that with probability at least $1-e^{-\frac{k}{24}}$ more than
$\frac{2}{3}$ of $\\{\tilde{\theta}_{n,1},\ldots,\tilde{\theta}_{n,k}\\}$ are
within
$B_{\tilde{V}_{n}}(\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n},\gamma)$. When
this is true, by the nature of $k^{*}$, we can directly have with probability
at least $1-e^{-\frac{k}{24}}$,
$\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}\leq
3\gamma$. Therefore, by letting $k=\lceil
24\ln\left(\frac{eT}{\delta}\right)\rceil$, we have the desired result by
union bound and $N=\lfloor T/k\rfloor$. ∎

Now, we are well-prepared to present the regret analysis of MoMA-GP-UCB.

###### Proof.

As pointed out before, the key is again a high probability confidence bound,
which is now on $|f(x)-\tilde{\mu}_{n}(x)|$, uniformly over $n\in[N]$ and
$x\in\mathcal{D}$. By Lemma 9, we have when $E_{1,n}$ is true (i.e.,
$\varepsilon$-accurate), for any $x\in\mathcal{D}$,

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|$ $\displaystyle\leq
B\left(1+\frac{1}{\sqrt{1-\varepsilon}}\right)\tilde{\sigma}_{n}(x)+\lambda^{-1/2}\lVert\tilde{V}_{n}^{-1}\tilde{\Phi}_{n}^{T}f_{n}-\tilde{\theta}_{n,k^{*}}\rVert_{\tilde{V}_{n}}\tilde{\sigma}_{n}(x).$

Then, combined with Lemma 11, we have that when the event $E_{1,n}$ is true,
for any $\delta\in(0,1]$, when $k=\lceil
24\ln\left(\frac{eT}{\delta}\right)\rceil$, then with probability at least
$1-\delta$, uniformly over $n\in[N]$ and $x\in\mathcal{D}$, we have

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|$
$\displaystyle\leq\left(B(1+\frac{1}{\sqrt{1-\varepsilon}})+\lambda^{-1/2}3\gamma\right)\tilde{\sigma}_{n}(x),$

where $\gamma=(9m_{n}c)^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}$.
Since the event $E_{1,n}$ is true for all $n\in[N]$ with probability at least
$1-\delta$ from Lemma 8, by using a union bound, we obtain that for any
$\delta\in(0,1]$, if we choose $k=\lceil
24\ln\left(\frac{2eT}{\delta}\right)\rceil$, then with probability at least
$1-\delta$, uniformly over all $n\in[N]$ and $x\in\mathcal{D}$,

$\displaystyle|f(x)-\tilde{\mu}_{n}(x)|$
$\displaystyle\leq\beta_{n+1}\tilde{\sigma}_{n}(x),$ (22)

where
$\beta_{n+1}:=B(1+\frac{1}{\sqrt{1-\varepsilon}})+\lambda^{-1/2}3\gamma$.

Now, by the result above and the choice of MoMA-GP-UCB, we have for any
$\delta\in(0,1]$, when $k=\lceil 24\ln\left(\frac{2eT}{\delta}\right)\rceil$

$\displaystyle r_{n}=f(x^{*})-f(x_{n})\leq 2\beta_{n}\tilde{\sigma}_{n}(x)$

holds with probability at least $1-\delta$. Then, we first bound the term
$\beta_{n}$. From Lemma 8, given a $(\mathcal{G}_{n})_{n\geq 1}$ such that the
event $E_{2,n}$ is true for all $n\in[N]$, we have $m_{n}\leq
6\rho\left(1+\frac{1}{\lambda}\right)q\gamma_{t}$. This implies that

$\displaystyle\beta_{n}=O\left(B(1+\frac{1}{\sqrt{1-\varepsilon}})+\left(\frac{\rho^{2}}{\varepsilon^{2}}\ln\frac{T}{\delta}\right)^{\frac{1}{1+\alpha}}\gamma_{n}^{\frac{1}{1+\alpha}}c^{\frac{1}{1+\alpha}}n^{\frac{1-\alpha}{2(1+\alpha)}}\right).$

Next, we can bound the $\sum_{n=1}^{N}\tilde{\sigma}_{n}(x)$ as follows given
that the event $E_{1,t}$ is true for $n\in[N]$.

$\displaystyle\sum_{n=1}^{N}\tilde{\sigma}_{n}(x)\mathop{\leq}\limits^{(a)}\rho\sum_{n=1}^{N}{\sigma}_{n}(x)\mathop{=}\limits^{(b)}O(\rho\sqrt{N\gamma_{N}}),$

where (a) holds by the second part of Lemma 9; (b) holds by Lemma 7. Recall
that by Lemma 8, with probability at least $1-\delta$, both $E_{1,n}$ and
$E_{2,n}$ are true for all $n\in[N]$. With the use of the union bound, we have
for any $\delta\in(0,1]$, when $k=\lceil
24\ln\left(\frac{4eT}{\delta}\right)\rceil$, with probability at least
$1-\delta$, the cumulative regret is given by

$\displaystyle R_{T}=k\sum_{n=1}^{N}r_{n}\leq
k\sum_{n=1}^{N}2\beta_{n}\tilde{\sigma}_{n}(x)=O\left(\hat{B}\sqrt{\gamma_{T}T\ln\frac{T}{\delta}}+Z\ln\frac{T}{\delta}c^{\frac{1}{1+\alpha}}T^{\frac{1}{1+\alpha}}\gamma_{T}^{\frac{3+\alpha}{2(1+\alpha)}}\right),$

where $\hat{B}=\rho B(1+\frac{1}{\sqrt{1-\varepsilon}})$ and
$Z=\left(\frac{\rho^{3+\alpha}}{\varepsilon^{2}}\right)^{\frac{1}{1+\alpha}}$.
∎

##  Appendix E Additional Experiment Results

In this section, we conduct additional experiments to compare the performance
of three LDP algorithms under different scenarios. For the synthetic case, we
use $k_{\text{SE}}$ in this section. For the two real-world datasets, we use
different values of $\epsilon$. From Fig. 3, we can see that LDP-MoMA-GP-UCB
has better or competitive performance across different scenarios.

(a) LDP, $\epsilon=1$, Synthetic data, $k_{\text{SE}}$

(b) LDP, $\epsilon=1$, Light sensor data

(c) LDP, $\epsilon=0.5$, Stock market data.

Figure 3: Cumulative regrets for three LDP algorithms under three new
scenarios