# Differentially private online Bayesian estimation
with adaptive truncation

Sinan Yıldırım<EMAIL_ADDRESS>Center of Excellence in Data
Analytics (VERİM), Sabancı University, İstanbul, Turkey

###### Abstract

We propose a novel online and adaptive truncation method for differentially
private Bayesian online estimation of a static parameter regarding a
population. We assume that sensitive information from individuals is collected
sequentially and the inferential aim is to estimate, on-the-fly, a static
parameter regarding the population to which those individuals belong. We
propose sequential Monte Carlo to perform online Bayesian estimation. When
individuals provide sensitive information in response to a query, it is
necessary to perturb it with privacy-preserving noise to ensure the privacy of
those individuals. The amount of perturbation is proportional to the
sensitivity of the query, which is determined usually by the range of the
queried information. The truncation technique we propose adapts to the
previously collected observations to adjust the query range for the next
individual. The idea is that, based on previous observations, we can carefully
arrange the interval into which the next individual’s information is to be
truncated before being perturbed with privacy-preserving noise. In this way,
we aim to design predictive queries with small sensitivity, hence small
privacy-preserving noise, enabling more accurate estimation while maintaining
the same level of privacy. To decide on the location and the width of the
interval, we use an exploration-exploitation approach _a la_ Thompson sampling
with an objective function based on the Fisher information of the generated
observation. We show the merits of our methodology with numerical examples.

Keywords: Differential privacy, Bayesian statistics, Sequential Monte Carlo,
online learning, Thompson sampling, adaptive truncation

## 1 Introduction

During the past couple of decades, there has been a rapid increase in the
amount of collected data as well as concerns about individuals’ privacy. This
has made privacy-preserving data analysis a popular and important subject in
data science. Along the way, _differential privacy_ has become a popular
framework for privacy-preserving data sharing algorithms (Dwork, , 2006; Dwork
and Roth, , 2013).

There are two conflicting interests in privacy-preserving data analysis: (i)
The individuals of a population who contribute to a data set with their
sensitive information want to protect their privacy against all possible
adversaries. (ii) Conflicting with that, it is desired to be able to estimate
a common quantity of interest regarding the population based on sensitive data
with reasonable accuracy. To put the conflict in a statistical context, we let
$X_{t}\sim\mathcal{P}_{\theta}$ be the sensitive information of $t$’th
individual of a sample randomly chosen from a large population with a
population distribution $\mathcal{P}_{\theta}$. We want to estimate $\theta$
while also protecting the privacy of the individuals contributing to the
sample, i.e., without revealing ‘much’ information about $X_{t}$s
individually.

In this paper, we are particularly interested in online Bayesian estimation of
$\theta$ as we continually collect $Y_{1},Y_{2},\ldots$, which are the
_perturbed_ versions of $X_{1},X_{2},\ldots$ respectively. The cases where
individuals contribute to a data set continually are not rare: Imagine web
users registering to a web application after entering their information,
patients being admitted to a hospital, customers applying for a bank loan,
etc. We address two interrelated questions:

  * •

How can we improve the estimate of $\theta$ as we collect $Y_{1},Y_{2},\ldots$
continually?

  * •

As we estimate $\theta$, how can we continually adjust the privacy-preserving
mechanism that generates $Y_{t}$ from $X_{t}$ so that the estimation
performance is improved as $t$ increases?

Differentially private Bayesian inference of $\theta$ has been the subject of
several recent studies, with Monte Carlo being the main methodological tool
for inference. Stochastic gradient MCMC algorithms were proposed in Wang et
al.,  (2015); Li et al.,  (2019), while reversible MCMC algorithms were
proposed in Heikkilä et al.,  (2019); Yıldırım and Ermiş,  (2019); Räisä et
al.,  (2021). Those algorithms require as many interactions with sensitive
data as the number of iterations they run for. An alternative scheme to that
is called input perturbation, where the sensitive data are perturbed and
shared once and for all, and all the subsequent Bayesian inference is
performed on the perturbed data without further interaction with the sensitive
data (Foulds et al., , 2016; Williams and Mcsherry, , 2010; Karwa et al., ,
2014; Bernstein and Sheldon, , 2018; Park et al., , 2021; Gong, , 2022;
Alparslan and Yıldırım, , 2022; Ju et al., , 2022).

All the cited works above consider differentially private Bayesian inference
conditional on a batch (static) data set. Unlike those works, in this paper,
we consider the case with continual observations, where data from the
individuals are collected _sequentially_ in a privacy-preserving way. This
scenario enables two methodological opportunities and/or challenges:

  1. 1.

One can (and/or should) estimate the static parameter on-the-fly, that is,
update the estimate as data are being received. Differentially private
estimation under continual observation has been the subject of several works
that are initiated by Dwork et al.,  (2010); other important contributions
include Chan et al.,  (2011); Cao et al.,  (2017). However, those works are
usually applied to online tracking of dynamic summaries of data, such as the
count of a certain property, rather than estimating a static parameter of the
population from which the sensitive data are being received. In particular,
they do not consider Bayesian estimation.

  2. 2.

As we estimate the parameter, we can adaptively adjust the query for the next
individual’s information to make the response as _informative_ as possible.
For example, if, based on the noisy income values collected so far from 100
individuals, we have estimated that the mean income of the population is
around $\hat{\mu}$, we can ask the $101$’th individual to provide their income
information after _truncating_ it to an interval around $\hat{\mu}$, such as
$[\hat{\mu}-\Delta,\hat{\mu}+\Delta]$, and _then_ privatising it by adding
noise to the (possibly) truncated value.

The motivation behind pursuing such an adaptive truncation technique is to
improve the estimation performance with less noisy data while maintaining a
given level of privacy. The standard deviation of the privacy-preserving noise
added to the outcome of a query is proportional to the sensitivity of the
query. By default, the queried information may be unbounded or have very large
ranges, resulting in low utility. Continuing with the income example above,
assume that the natural limits of an income are $[x_{\min},X_{\max}]$ so that
a query that directly asks for income information has a sensitivity of
$X_{\max}-x_{\min}$, which is expectedly large. If adaptive truncation were
used, instead, referring to the above example, the query interval for $101$’th
individual would be $[\hat{\mu}-\Delta,\hat{\mu}+\Delta]$ with sensitivity
$2\Delta$.

Truncation is considered in many works as a natural way to have finite
sensitivity, see Heikkilä et al.,  (2017); Ju et al.,  (2022) for examples of
differentially private Bayesian estimation based on truncated data. Those
works regard estimation based on batch data; adaptive truncation during online
Bayesian learning, as done in this paper, is not considered.

This paper contributes to the literature on differential privacy by addressing
the two challenges described above with a novel methodology. For the first
challenge, that is, online Bayesian estimation of $\theta$, we propose a
sequential Monte Carlo (SMC) method for static parameter estimation as studied
in Gilks and Berzuini,  (2001); Chopin,  (2002). For the second challenge, we
propose a novel adaptive truncation method that employs an _exploration-
exploitation_ heuristic to maximise the aggregate ‘information’ in the
sequence of observations $Y_{1},Y_{2},\ldots$ about $\theta$. To measure the
amount of ‘information’, we choose the Fisher information as suggested in
Alparslan and Yıldırım,  (2022). As we show in Section 5, the _exploration_
part of the proposed approach can be seen as an instance of Thompson sampling
(Russo et al., , 2018) from reinforcement learning. The _exploitation_ part
consists of finding the truncation points that make the resulting observations
most informative in terms of Fisher information. Finally, for the
_exploitation_ step, we pay special attention to _location-scale_ families and
show that the maximisation task can be performed for all time steps once and
for all. To the best of our knowledge, this is the first work that tackles the
problem of online differentially private Bayesian estimation with adaptive
queries.

The paper is organised as follows. In Section 2, we introduce the basic
concepts of differential privacy. In Section 3, we discuss the problem of
online parameter estimation using privatised noisy statistics of the sensitive
data and present our methodology in general. In Sections 4 and 5, we describe
the details of our methodology. In Section 6 we present the results of some
numerical experiments. Finally, we give our concluding remarks in Section 7.
This paper has an Appendix section for some deferred details.

## 2 Differential Privacy

Let $\mathcal{X}$ be a set of individual data values and
$\mathscr{X}=\bigcup_{n=1}^{\infty}\mathcal{X}^{n}$ be the set of all possible
data sets. Define the Hamming distance between the data sets
$\bm{x},\bm{x}^{\prime}\in\mathscr{X}$ as the number of different elements
between those data sets, denoted by $h(\bm{x},\bm{x}^{\prime})$. We call two
data sets $\bm{x},\bm{x}^{\prime}\in\mathscr{X}$ neighbours if
$h(\bm{x},\bm{x}^{\prime})=1$. A _randomised algorithm_ can be defined as a
couple $\mathcal{A}=(A,\mu)$, where
$A:\mathscr{X}\times\mathcal{E}\mapsto\mathcal{Y}$ is a function and $\mu$ is
a probability distribution on $\mathcal{E}$, which represents the randomness
intrinsic to $\mathcal{A}$. Upon taking an input $\bm{x}\in\mathscr{X}$, the
randomised algorithm $\mathcal{A}$ generates random numbers
$\omega\sim\mu(\cdot)$ in $\mathcal{E}$ and outputs $A(\bm{x},\omega)$.
Differential privacy (Dwork, , 2006) quantifies a certain sense of similarity
between random outputs $A(\bm{x},\omega)$ and $A(\bm{x}^{\prime},\omega)$ when
$\bm{x}$ and $\bm{x}^{\prime}$ are neighbours.

######  Definition 1 (Differential privacy (DP)).

A randomised algorithm $\mathcal{A}=(A,\mu)$ is $(\epsilon,\delta)$-DP if

$\mathbb{P}\left[A(\bm{x},\omega)\in S\right]\leq
e^{\epsilon}\mathbb{P}\left[\mathcal{A}(\bm{x}^{\prime},\omega)\in
S\right]+\delta,\quad\forall\bm{x},\bm{x}^{\prime}\in\mathscr{X}s.t.\
h(\bm{x},\bm{x}^{\prime})=1,\quad\forall S\subseteq\mathcal{Y},$

where the randomness is with respect to $\omega\sim\mu(\cdot)$. We say
$\mathcal{A}$ is $\epsilon$-DP when $\delta=0$.

As far as privacy is concerned, both privacy parameters $(\epsilon,\delta)$
are desired to be as small as possible. The following theorem states that
$(\epsilon,\delta)$-DP is maintained by post-processing the output of an
$(\epsilon,\delta)$-DP algorithm.

######  Theorem 1 (Post-processing).

Define functions
$A_{1}:\mathscr{X}\times\mathcal{E}_{1}\mapsto\mathcal{Y}_{1}$ and
$A_{2}:\mathcal{Y}_{1}\times\mathcal{E}_{2}\mapsto\mathcal{Y}_{2}$; and
probability distributions $\mu_{1}$, $\mu_{2}$ on $\mathcal{E}_{1}$,
$\mathcal{E}_{2}$, respectively. Furthermore, let
$A:\mathscr{X}\times\mathcal{E}_{1}\times\mathcal{E}_{2}\mapsto\mathcal{Y}_{2}$
be defined by
$A(\bm{x},\omega_{1},\omega_{2})=A_{2}(A_{1}(\bm{x},\omega_{1}),\omega_{2})$,
and $\mu=\mu_{1}\otimes\mu_{2}$. Then, if $\mathcal{A}_{1}=(A_{1},\mu_{1})$ is
$(\epsilon,\delta)$-DP, $\mathcal{A}=(A,\mu)$ is $(\epsilon,\delta)$-DP, too.

Let $\varphi:\mathscr{X}\mapsto\mathbb{R}$ be a function and assume that
$\varphi(\bm{x})$ is queried. One common way of achieving differential
privacy, in this case, is the _Laplace mechanism_ (Dwork, , 2008), which
relies on the _$L_{1}$ -sensitivity_ of $\varphi$, given by

$\Delta\varphi=\sup_{\begin{subarray}{c}\bm{x},\bm{x}^{\prime}\in\mathscr{X}:\\\
h(\bm{x},\bm{x}^{\prime})=1\end{subarray}}|\varphi(\bm{x})-\varphi(\bm{x}^{\prime})|.$
(1)

######  Theorem 2 (Laplace mechanism).

The algorithm that returns $\varphi(\bm{x})+\Delta\varphi V$ given the input
$\bm{x}\in\mathscr{X}$, where $V\sim\textup{Laplace}(1/\epsilon)$, is
$\epsilon$-DP.

Other useful definitions of data privacy have close relations to differential
privacy. Some important examples are Gaussian differential privacy (Dong et
al., , 2022) and zero-concentrated differential privacy (Bun and Steinke, ,
2016), both of which promote the _Gaussian mechanism_ (Dwork and Roth, , 2013)
(where $V$ in Theorem 2 has a normal distribution) as its primary mechanism
for providing privacy. The Gaussian mechanism can also provide
$(\epsilon,\delta)$-DP for $\delta>0$ if the variance is modified to depend on
$\delta$ also.

For the rest of the paper, we will consider the Laplace mechanism to provide
$\epsilon$-DP for sake of simplicity. We remark, however, that other additive
mechanisms to provide privacy in other senses also fit into our methodology
with minor changes. In particular, our methodology applies to the Gaussian
mechanism in an almost identical manner.

## 3 Differentially private parameter estimation with adaptive queries

Assume a sequence of i.i.d. data points

$X_{t}\overset{\textup{i.i.d.}}{\sim}\mathcal{P}_{\theta},\quad t\geq 1,$

where $X_{t}$ is some sensitive information that belongs to the $t$’th
individual sampled from a population. We want to estimate the unknown
parameter $\theta$ of the population distribution $\mathcal{P}_{\theta}$.
However, we are not allowed to access to $X_{t}$’s directly; instead,
individuals share their information through a function
$s_{t}:\mathcal{X}\mapsto\mathbb{R}$ and with privacy-preserving noise as

$Y_{t}=s_{t}(X_{t})+\Delta s_{t}V_{t},\quad
V_{t}\overset{\textup{i.i.d.}}{\sim}\textup{Laplace}(1/\epsilon),\quad t\geq
1,$ (2)

where $\Delta s_{t}$ is the sensitivity defined as in (1), that is,

$\Delta s_{t}=\sup_{x,x^{\prime}\in\mathcal{X}}|s_{t}(x)-s(x^{\prime})|.$

We consider online estimation of $\theta$ when $\\{Y_{t}\\}_{t\geq 1}$ are
observed sequentially in time. The recursion that corresponds to a sequential
estimation procedure can be written down generically as

$\Theta_{t}=G(\Theta_{t-1},Y_{1:t},s_{1:t}).$

The update function $G$ produces $\Theta_{t}$ using all the information up to
time $t$, which includes $\Theta_{t-1}$, the functions $s_{1:t}$, and the
observations $Y_{1:t}$. Generally, $\Theta_{t}$ is not necessarily a point
estimate but a collection of variables needed to construct the estimation of
$\theta$ at time $t$. For example, in SMC for Bayesian estimation,
$\Theta_{t}$ can correspond to the particle system at time $t$. Details of
such an algorithm will be provided in Section 4.

This paper focuses on the question of whether it is possible to choose $s_{t}$
_adaptively_ so that $\theta$ is estimated with improved accuracy relative to
its non-adaptive counterpart. The choice of $s_{t}$ is important because
$s_{t}$ determines how much information is contained in $Y_{t}$ about $\theta$
in two ways (Alparslan and Yıldırım, , 2022):

  * •

The first way is related to the sufficiency or informativeness of $s_{t}$ in
the classical sense. For example, let
$\mathcal{P}_{\theta}=\mathcal{N}(\theta,1)$ with an unknown mean $\theta$.
Then, discarding the privacy-preserving noise, $s_{t}(x_{t})=x_{t}$ would be a
better choice than $s_{t}(x_{t})=|x_{t}|$ since $|x_{t}|$ masks the
information that is contained in $x_{t}$ about $\theta$.

  * •

Secondly, the standard deviation of the privacy-preserving noise is
proportional to the sensitivity $\Delta s_{t}$. A mild truncation results in a
large $\Delta s_{t}$, which necessitates too much privacy-preserving noise.
(As an extreme case, think of an unbounded $s_{t}$). On the flip side, making
$\Delta s_{t}$ too small could result in a small amount of information in
$s_{t}(X_{t})$ about $\theta$. (Imagine a constant $s_{t}(\cdot)$, which has
$\Delta s_{t}=0$ but carries no information about $\theta$.) Therefore,
truncation and sensitivity establish a trade-off. Below, we exemplify the
trade-off when $s_{t}$ is a truncation function.

######  Example 1.

Assume that our goal is to learn the average income $\theta$ of the
individuals in a given population, with a population distribution
$\mathcal{N}(\theta,\sigma^{2})$, where $\sigma^{2}$ is known. Assume that
data is collected from (some of) the individuals in this population in a
sequential way. However, since the income information is sensitive, each
individual’s income is recorded (or shared by the individual) with privacy-
preserving noise as in (2). Consider the specific choice

$Y_{t}=\min\\{\max\\{X_{t},l\\},r\\}+(r-l)V_{t},\quad
V_{t}\sim\textup{Laplace}\left(1/\epsilon\right).$

If the interval $[l,r]$ is wide, true income $X_{t}$ is not likely to be
truncated but $Y_{t}$ suffers a large noise for ensuring the given level of
privacy. On the other hand, if $[l,r]$ is small, $X_{t}$ is likely to be
truncated but $Y_{t}$ is less noisy. This makes a trade-off between truncation
and privacy-preserving noise, the two undesired components in terms of
statistical inference.

It would therefore be reasonable to carefully adjust the interval adaptively
as we collect data, where the interval for receiving the $t$’th individual’s
data is denoted by $[l_{t},r_{t}]$. Intuitively, we would aim to set
$[l_{t},r_{t}]$ in such a way that it will likely contain the true value and
it is small so that the required privacy-preserving noise has a small
variance. If $\theta$ is a location parameter, we could do that by positioning
$[l_{t},r_{t}]$ around the most recent estimate of $\theta$.

The general online estimation method with adaptive functions $s_{t}$ is given
in Algorithm 1. The algorithm outlines the general idea in this paper: We gain
knowledge about $\theta$ as we observe $Y_{t}$’s; which we use to adapt the
statistic $s_{t+1}$ such that the new observation $Y_{t+1}$ carries more
information about $\theta$ than it would with an arbitrary choice of
$s_{t+1}$.

Algorithm 1 is $\epsilon$-DP. Each observation $Y_{t}$ belongs to an
individual and is shared with $\epsilon$-DP. Furthermore, all the updates in
Algorithm 1 are performed using the shared data $\\{Y_{t}\\}_{t\geq 1}$ and
_not_ the private data $\\{X_{t}\\}_{t\geq 1}$. Therefore, by Theorem 1, those
updates do not introduce any further privacy leaks. A more formal statement in
Proposition 1, a proof can be found in Appendix A.

1 Initialise the estimation system $\Theta_{0}$ and $s_{1}(\cdot)$.

2

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

4 The function $s_{t}$ is revealed to individual $t$, which shares his/her
data $X_{t}$ as  $Y_{t}=s_{t}(X_{t})+\Delta s_{t}V_{t},\quad
V_{t}\sim\textup{Laplace}\left(1/\epsilon\right).$

5 Update the estimation system $\Theta_{t}$ as
$\Theta_{t}=G(\Theta_{t-1},Y_{1:t},s_{1:t}).$ (3)

6 Update the new function  $s_{t+1}=H(\Theta_{t}).$ (4)

Algorithm 1 Differentially private online learning - general scheme

######  Proposition 1.

Algorithm 1 is $\epsilon$-DP.

In Sections 4 and 5, we describe the methods for the updates in (3) and in
(4).

## 4 Sequential Monte Carlo for online Bayesian estimation

In this section, we focus on $G$ in (3) in Algorithm 1, which stands for the
parameter estimation update upon receiving a new observation. We consider the
functions $s_{t}$ given and present an SMC method for online Bayesian
estimation of $\theta$. SMC is a popular numerical method for online Bayesian
inference; see Gilks and Berzuini,  (2001); Chopin,  (2002) for some pioneer
works. Let $p_{\theta}(\cdot)$ be the probability density (or mass) function
(pdf or pmf) of $\mathcal{P}_{\theta}$. With a prior distribution
$\eta(\theta)$ on $\theta$, the following sequence of posterior distributions
is targeted sequentially with SMC.

$\displaystyle p_{s_{1:t}}^{\epsilon}(\theta,x_{1:t}|y_{1:t})$
$\displaystyle\propto p_{s_{1:t}}^{\epsilon}(\theta,x_{1:t},y_{1:t})$ (5)
$\displaystyle=\eta(\theta)\prod_{k=1}^{t}p_{\theta}(x_{k})\textup{Laplace}\left(y_{k}-s_{k}(x_{k}),\Delta
s_{k}/\epsilon\right),\quad t=1,\ldots,n,$

where we used $\textup{Laplace}(\cdot;b)$ to denote the pdf of
$\textup{Laplace}(b)$. A Monte Carlo approximation is necessary for those
posterior distributions since they are intractable having no closed form. At
time $t$, SMC approximates the posterior distribution in (5) with a discrete
probability distribution having $N>1$ particles (points of mass)
$\\{(\theta^{(i)},x_{1:t}^{(i)});i=1,\ldots,N\\}$ with particle weights
$\\{w_{t}^{(i)};i=1,\ldots,N\\}$ as

$p^{\epsilon,N}_{s_{1:t}}(\mathrm{d}(\theta,x_{1:t})|y_{1:t})=\sum_{i=1}^{N}w_{t}^{(i)}\delta_{(\theta^{(i)},x_{1:t}^{(i)})}(\mathrm{d}(\theta,x_{1:t})).$

By marginalising out the $x_{1:t}$ component in the above approximation, we
can also obtain the particle approximation of the marginal posterior
distribution of $\theta$ given the observations.

$p^{\epsilon,N}_{s_{1:t}}(\mathrm{d}\theta|y_{1:t})=\sum_{i=1}^{N}w_{t}^{(i)}\delta_{\theta^{(i)}}(\mathrm{d}\theta).$
(6)

At time-step $t$, the particles and their weights from time $t-1$ are updated
after the _resampling_ , _rejuvenation_ , _propagation_ , and _weighting_
steps. The propagation and weighting steps are necessary to track the evolving
posterior distributions, while the rejuvenation and resampling steps prevent
the particle approximation from collapsing to a single point. The update at a
single time-step of SMC is detailed in Algorithm 2 (time indices of particles
are omitted for ease of exposition). The algorithm is an instance of the
resample-move algorithm of Gilks and Berzuini,  (2001), specified for the
sequence of posteriors in (5). The most common resampling step is multinomial
sampling, where the $N$ new particles are sampled independently according to
their weights. For the rejuvenation step, one common type of MCMC move
consists of (i) an update of $x_{k}$, $k=1,\ldots,t$, with a Metropolis-
Hastings (MH) move with invariant distribution
$p_{\theta,s_{k}}(x_{k}|y_{k})=p_{\theta}(x_{k})p_{s_{k}}^{\epsilon}(y_{k}|x_{k})$,
which is followed by (ii) an update of $\theta$ using an MH move with
invariant distribution
$p(\theta|x_{1:t})\propto\eta(\theta)\prod_{k=1}^{t}p_{\theta}(x)$. One such
MCMC move is shown in Algorithm 3 in Appendix C.

The computational cost of SMC for processing $n$ observations is
$\mathcal{O}(Nn^{2})$ in general, since an $\mathcal{O}(tN)$ operation is
needed to rejuvenate the particles at time $t$. The cost may be reduced in
some cases: The cost for updating $x_{1:t}$ can be reduced by updating a
random subset, of a fixed size, of $x_{k}$’s at each time step $t$. The cost
for updating $\theta$ may be reduced depending on the model specifics, for
example by using a Gibbs move for $\theta$ if the posterior distribution
$p(\theta|x_{1:t})$ is tractable.

Input: Particles at time $t-1$, $(\theta_{t-1}^{(1:N)},x_{1:t-1}^{(1:N)})$,
particle weights $w_{t}^{(i)}$ observation $y_{t}$, function $s_{t}$, DP
parameter $\epsilon$

Output: The particle system at time $t$

1 Resampling: Resample particles according to their weights:
$(\theta^{(1:N)},x_{1:t-1}^{(1:N)})\leftarrow\textup{Resample}((\theta^{(1:N)},x_{1:t-1}^{(1:N)});w_{t-1}^{(1:N)}).$
for  _$i=1,\ldots,N$_ do

2 Rejuvenation: Update $(\theta^{(i)},x_{1:t-1}^{(i)})$ using an MCMC move
that targets $p_{s_{1:t-1}}^{\epsilon}(\theta,x_{1:t-1}|y_{1:t-1})$.

3 Propagation: Sample $x_{t}^{(i)}\sim\mathcal{P}_{\theta^{(i)}}$ and append
particle $i$ as
$(\theta^{(i)},x_{1:t}^{(i)})=(\theta^{(i)},(x_{1:t-1}^{(i)},x_{t}^{(i)}))$.

Weighting: Calculate
$w_{t}^{(i)}\propto\textup{Laplace}\left(y_{t}-s_{t}(x^{(i)}),\Delta
s_{t}/\epsilon\right)$ for $i=1,\ldots,N$ s.t. $\sum_{i=1}^{N}w_{t}^{(i)}=1$.

Algorithm 2 SMC update at time $t$

## 5 Adaptive truncation for the transformation

In this section, we focus on $H$ in (4) in Algorithm 1 and describe a method
to determine the function $s_{t}$ adaptively so that the estimation
performance of SMC is better over a version where an arbitrary $s_{t}$ is
used. We confine to $s_{t}$ that corresponds to truncating $x_{t}$ into an
interval $[l_{t},r_{t}]$,

$s_{t}(x)=T_{l_{t}}^{r_{t}}(x):=\min\\{\max\\{x,l_{t}\\},r_{t}\\},$

so that the sensitivity is $\Delta s_{t}=r_{t}-l_{t}$. We assume $X_{t}$ is
univariate; for multivariate $X_{t}$ the truncation approach can be applied to
each component.

How should we choose the truncation points $l_{t},r_{t}$? Recall the trade-off
mentioned earlier: A larger $r_{t}-l_{t}$ renders truncation less likely but
leads to a larger noise in $Y_{t}$; whereas a smaller $r_{t}-l_{t}$ renders
truncation more likely but leads to a smaller noise in $Y_{t}$. Another
critical factor is the location of $l_{t},r_{t}$ relative to $\theta$. For
example, when $\theta$ is a location parameter, an interval $(l_{t},r_{t})$
around $\theta$ may be preferred.

Heikkilä et al.,  (2017) propose a way to optimise the truncation points for
batch estimation; however, their method spends a part of the privacy budget
and it is not straightforward to extend their method to online estimation.
Following Alparslan and Yıldırım,  (2022), we use the Fisher information as
the amount of information that an observation carries about the population
parameter. The Fisher information associated to $Y=T_{l}^{r}(X)+(r-l)V$ when
$X\sim\mathcal{P}_{\theta}$ and $V\sim\text{Laplace}(1/\epsilon)$ can be
expressed as

$\displaystyle F_{l,r}^{\epsilon}(\theta)$
$\displaystyle=\mathbb{E}\left[\nabla_{\theta}\log
p^{\epsilon}_{l,r}(Y|\theta)\nabla_{\theta}\log
p^{\epsilon}_{l,r}(Y|\theta)^{T}\right],$ (7)

where $p_{l,r}^{\epsilon}(y|\theta)$ is the pdf of the marginal distribution
of a single observation $Y_{t}=y$ given $\theta$ and $s_{t}=[l_{t},r_{t}]$.
According to this approach, we set the truncation points $l_{t},r_{t}$ to
those $l,r$ values that jointly maximise $F_{l,r}^{\epsilon}(\theta)$.

$F_{l,r}^{\epsilon}(\theta)$ is smaller for a smaller $\epsilon$, due to more
noisy observations. However, it is not obvious how
$F_{l,r}^{\epsilon}(\theta)$ behaves with $l,r$. The exact calculation of
$F_{l,r}^{\epsilon}(\theta)$ is not possible in general as the truncation of
$X$ between $l,r$, if nothing else, introduces an intractability in the
calculations. That is why we numerically approximate the Fisher information
using Monte Carlo

$F_{l,r}^{\epsilon}(\theta)\approx\frac{1}{M}\sum_{j=1}^{M}\widetilde{\nabla_{\theta}\log
p_{l,r}^{\epsilon}(y^{(j)}|\theta)}\widetilde{\nabla_{\theta}\log
p_{l,r}^{\epsilon}(y^{(j)}|\theta)^{T}},\quad
y^{(1)},\ldots,y^{(M)}\overset{\textup{i.i.d}}{\sim}p_{l,r}^{\epsilon}(y|\theta),$
(8)

where each gradient term in the sum is calculated using Algorithm 4 in
Appendix C.

When $\theta$ is multidimensional, an overall score function
$\text{sc}(\cdot)$ can be used to order the Fisher information matrices.
Examples of such a score function are the trace and a weighted sum of the
diagonals.

### 5.1 Exploration-exploitation for interval selection

We adjust the interval $[l,r]$ to better estimate $\theta$, yet the adjustment
is based on $F(\theta)$, which depends on $\theta$. Therefore, we are adapting
the intervals based on something that requires the knowledge of $\theta$ which
we want to estimate in the first place. This situation necessitates an
_exploration-exploitation_ approach. When we have little knowledge about
$\theta$, we should let our adaptive algorithm have more freedom to locate the
truncation interval; but as we learn $\theta$ by receiving more and more
observations, the location of the interval should be chosen with less variety.
Our exploration-exploitation approach consists of two steps. Given
$\Theta_{t}$,

  1. Step 1

Draw $\vartheta_{t}\sim p^{\epsilon,N}_{s_{1:t}}(\mathrm{d}\theta|y_{1:t})$,
the SMC approximation of the posterior distribution at time $t$, i.e.,

$\text{choose }\vartheta_{t}=\theta^{(i)}\text{ with probability
}w_{t}^{(i)},\quad i=1,\ldots,N.$

  2. Step 2

Determine the interval for the next observation as

$l_{t+1},r_{t+1}=\arg\max_{l,r}\text{sc}(F_{l,r}^{\epsilon}(\vartheta_{t})).$
(9)

After determining $[l_{t+1},r_{t+1}]$, the next data point $X_{t+1}$ is shared
as

$Y_{t+1}=T_{l_{t+1}}^{r_{t+1}}(X_{t+1})+(r_{t+1}-l_{t+1})V_{t+1},\quad
V_{t+1}\sim\textup{Laplace}(1/\epsilon).$ (10)

The exploration size is decreased as $t$ increases, that is, as more data are
observed. Remarkably, this is automatically handled by Step 1 above, since
posterior distribution is spread over a wide region for small $t$ but gets
more concentrated as more data are received.

#### Thompson sampling.

Steps 1 and 2 above can be seen as an instance of _Thompson sampling_ in
reinforcement learning (see e.g. Russo et al.,  (2018)): Using the terminology
from reinforcement learning, in our case, the ‘action’ is the choice of the
interval $[l_{t},r_{t}]$, ‘state’ is $Y_{t}$, the ‘model parameter’ is
$\theta$, the ‘past observations’ at time $t$ are the states
$Y_{1},\ldots,Y_{t}$, and the ‘objective function’ is $F_{l,r}(\theta)$. If
the maximiser $\arg\max_{l,r}F_{l,r}(\theta)$ is unique for every $\theta$,
then Thompson sampling corresponds to first sampling $\vartheta_{t}\sim
p^{\epsilon}_{l_{1:t},r_{1:t}}(\mathrm{d}\theta|Y_{1:t})$ and then setting
$l_{t+1},r_{t+1}=\arg\max F_{l,r}(\vartheta_{t})$, which corresponds to the
exploration-exploitation approach described above. The exact implementation of
Thompson sampling requires sampling from
$p_{l_{1:t},r_{1:t}}(\mathrm{d}\theta|Y_{1:t})$. As often done in practice, we
approximate that step sample from the particle approximation
$p_{l_{1:t},r_{1:t}}^{N}(\mathrm{d}\theta|Y_{1:t})$.

### 5.2 Location and scale parameters and truncation

In principle, the maximisation step in (9) can be applied to any population
distribution $\mathcal{P}_{\theta}$ for sensitive data. However, location-
scale distribution families deserve particular interest due to their common
use and certain desirable properties. It is intuitive to suppose that the best
truncation points for a location-scale distribution can be obtained simply by
scaling and shifting the best truncation points calculated for some _base_
distribution. We show here that this is indeed the case. For a general
population distribution $\mathcal{P}_{\theta}$, the maximisation (9) needs to
be performed afresh for each $\vartheta_{t}$. For location-scale families,
however, the computationally intensive part of (9) can be done once for some
base distribution and its result can easily be applied for all $\vartheta_{t}$
by scaling and shifting. Below we explain how that is possible.

######  Definition 2.

A distribution family $\\{f(\cdot;m,c):(m,c)\in\mathbb{R}\times(0,\infty)\\}$
is a location-scale family with a base distribution $g(x)$ if for all
$(m,c)\in\mathbb{R}\times(0,\infty)$ we have $f(x;m,c)=\frac{1}{c}g((x-m)/c)$
for all $x\in\mathcal{X}$. In particular, $f(x;0,1)=g(x)$.

Assume that $\mathcal{P}_{\theta}$ is a member of a location-scale family,
e.g. a normal distribution with $\theta$ being the vector of the mean and the
standard deviation. When $\vartheta_{t}=(m,c)$ is sampled in Step 1 above,
consider formalising the truncation points as

$l_{t+1}=ac+m,\quad r_{t+1}=bc+m,$ (11)

where $a$ and $b$ are the free parameters. Then, the problem in (9) reduces to
choosing the best $a,b$ that maximises
$\text{sc}(F_{ac+m,bc+m}^{\epsilon}(m,c))$, where
$F_{ac+m,bc+m}^{\epsilon}(m,c)$ is the Fisher information associated to the
random variable

$Y=T_{ac+m}^{bc+m}(X)+c(b-a)V,\quad V\sim\textup{Laplace}(1/\epsilon),\quad
X\sim\mathcal{P}_{(m,c)}.$ (12)

We show that for location-scale families, a _uniformly best pair_ $a,b$ over
all possible values $(m,c)$ exists.

######  Theorem 3.

For any $a,b\in\mathbb{R}$, $\epsilon>0$ and
$(m,c)\in\mathbb{R}\times[0,\infty)$, let $\textup{sc}:\mathbb{R}^{2\times
2}\mapsto\mathbb{R}$ be a score for information matrices. Then, for all pairs
$a,b$ and $a^{\prime},b^{\prime}$, either one of the three holds

$\displaystyle\textup{sc}(F^{\epsilon}_{ac+m,bc+m}(m,c))$
$\displaystyle>\textup{sc}(F^{\epsilon}_{a^{\prime}c+m,b^{\prime}c+m}(m,c)),\quad\forall(m,c)\in\mathbb{R}\times(0,\infty);$
$\displaystyle\textup{sc}(F^{\epsilon}_{ac+m,bc+m}(m,c))$
$\displaystyle<\textup{sc}(F^{\epsilon}_{a^{\prime}c+m,b^{\prime}c+m}(m,c)),\quad\forall(m,c)\in\mathbb{R}\times(0,\infty);$
$\displaystyle\textup{sc}(F^{\epsilon}_{ac+m,bc+m}(m,c))$
$\displaystyle=\textup{sc}(F^{\epsilon}_{a^{\prime}c+m,b^{\prime}c+m}(m,c)),\quad\forall(m,c)\in\mathbb{R}\times(0,\infty).$

A proof of Theorem 3 is given in Appendix B. Theorem 3 implies that it
suffices to find

$(a^{\ast},b^{\ast})=\arg\max_{a,b}\textup{sc}(F_{a,b}^{\epsilon}(0,1)),$ (13)

the best $a,b$ for the base distribution, i.e., for $(m,c)=(0,1)$. Then, it is
guaranteed that those $a^{\ast},b^{\ast}$ are the best choices for all $(m,c)$
values when the intervals are chosen according to (11). Therefore,
maximisation for interval selection needs to be done only once, implying
significant computational savings.

## 6 Numerical results

In our experiments111The code for the experiments can be found at
https://github.com/sinanyildirim/SMC_DP_adaTr, we take
$\mathcal{N}(\mu,\sigma^{2})$ as the population distribution, so that
$\theta=(\mu,\sigma)$, and aim to estimate both $\mu$ and $\sigma$. Sensitive
data $X_{1},\ldots,X_{n}$ of length $n=1000$ are generated from $\mu=50$ and
$\sigma^{2}=10$. The parameters are taken _a priori_ independent with
$\mu\sim\mathcal{N}(0,10^{4})$ and $\sigma^{2}\sim\mathcal{IG}(1,1)$, where
$\mathcal{IG}(\alpha,\beta)$ is the inverse gamma distribution with shape
$\alpha$ and scale $\beta$. Algorithm 1 is implemented for online learning of
$\theta$ by combining the SMC method in Section 4 with the exploration-
exploitation strategy described in Section 5 for the choice of the truncation
points.

Note that $\mathcal{N}(\mu,\sigma^{2})$ is a location-scale distribution with
$\mu$ and $\sigma$ being the location and scale parameters. Therefore, we
apply (12) to generate the noisy observations, where $a$, $b$ are the optimal
truncation points corresponding to the $\mathcal{N}(0,1)$. The Fisher
information matrix is a $2\times 2$ matrix, corresponding to the bivariate
parameter $\mu,\sigma$. For the example’s sake, we consider that the primary
goal is to estimate $\mu$ while $\sigma$ is of secondary importance. Thus, we
chose the score function as the first entry of the Fisher information matrix,
that is, $\text{sc}(F_{a,b}^{\epsilon}(0,1))=F_{a,b}^{\epsilon}(0,1)[1,1]$.
The maximisation in (13) is performed by Monte Carlo estimation of
$F_{a,b}^{\epsilon}(0,1)$ on the $50\times 50$ grid spanning
$[-3,3]\times[3,3]$ of $(a,b)$ points. The Monte Carlo estimation is performed
as in (8) with $M=1000$, where the gradient terms in (8) are approximated
using Algorithm 4 with samples of size $10000$. The best $[a,b]$ intervals
were numerically found as $[-0.06,0.06]$, $[-0.12,0.12]$, $[-0.54,0.54]$, and
$[-0.96,0.96]$ for $\epsilon=1,2,5,10$ respectively.

Figure 1 summarises the entire course of one run of SMC with adaptive
truncation, which we call “SMC-adaptive”. For each of $\epsilon=1,2,5,10$, we
repeat this experiment $30$ times independently.

• First, find $a,b$ that maximises $\text{sc}(F_{a,b}^{\epsilon}(0,1))$ the
score of the Fisher information matrix of $Y=T_{a}^{b}(X)+(b-a)V$, when
$X\sim\mathcal{N}(0,1)$, $V\sim\text{Laplace}(1/\epsilon)$. • Start with,
$l_{1},r_{1}$. For $t=1,\ldots,n$, – generate
$Y_{t}=T_{l_{t}}^{r_{t}}(X_{t})+(r_{t}-l_{r})V_{t}$, where
$X_{t}\sim\mathcal{N}(\mu,\sigma^{2})$ and
$V_{t}\sim\text{Laplace}(1/\epsilon)$. – Update the particle system of SMC
using Algorithm 2 with $N=1000$ particles to construct the SMC approximation
of the posterior $p^{\epsilon}_{l_{1:t},r_{1:t}}(\theta|Y_{1:t})$. – sample
$\vartheta_{t}=(m,c)$ from the SMC approximation
$p^{\epsilon,N}_{l_{1:t},r_{1:t}}(\theta|y_{1:t})$. – determine the new
truncation points $l_{t+1}=m+ca$, $r_{t+1}=m+cb$.

Figure 1: The entire course of one run of the SMC method with adaptive
truncation

We compared SMC-adaptive to two non-adaptive algorithms. The first one is the
same SMC method in Algorithm 2, but with constant truncation points,
$l_{c}=\mu-10\sigma$ and $r_{c}=\mu+10\sigma$ for all $t$. We call this
algorithm “SMC-non-adaptive”. The second method is an MCMC sampling method
that targets the conditional distribution of $\theta$ given the entire batch
of the observations at once, $p^{\epsilon}_{l_{c},r_{c}}(\theta|Y_{1:n})$,
where the observations are generated using the same truncation points for all
$X_{t}$ as in SMC-non-adaptive as

$Y_{t}=T_{l_{c}}^{r_{c}}(X_{t})+(r_{c}-l_{c})V_{t},\quad
V_{t}\overset{\textup{i.i.d.}}{\sim}\text{Laplace}(1/\epsilon),\quad
t=1,\ldots,n.$

The model for the random variables $\\{\theta,X_{1:n},Y_{1:n}\\}$ is a latent
variable model for independent observations. That is why, as the MCMC method,
we chose the MHAAR algorithm proposed in (Andrieu et al., , 2020, Section 3),
which is well suited to such latent variable models and also proposed for
privacy applications in Alparslan and Yıldırım,  (2022). The interval
$[l_{c},r_{c}]$, chosen for the non-adaptive methods, represents the situation
in many practical applications where there is not much strong _a priori_
knowledge available about $\theta$. The comparison with the non-adaptive
version of the SMC aims to show the merit of adaptive truncation. Moreover, by
comparing with the MCMC method, we aim to show the advantage of adaptation
even when online estimation is not required.

Figure 2 displays the performance of the two SMC methods for a single run and
each $\epsilon$. The scatter plots of the particles (after resampling so that
they have equal weights) at every 20th time step, as well as the mean
estimates, are shown. Further, the truncation points are also shown in the
plots for the location parameter $\mu$. Observe the decreasing amount of
spread of the particles as $t$. Also, as expected, accuracy increases with
$\epsilon$. We also observe the clear benefit of the adaptive truncation
method relative to its non-adaptive counterpart when we compare the particle
distributions: the particles of the SMC algorithm with adaptive truncation get
more concentrated around the true values and do that much more quickly than
those of the non-adaptive version. The posterior means, shown with red lines,
also demonstrate the advantage of the truncation method.

While Figure 2 shows results by the SMC methods from a single run, Figure 3
shows the box plots of the mean posterior estimates of $\theta$, obtained from
$30$ independent runs, of all the three methods under comparison, namely SMC-
adaptive, SMC-non-adaptive and the MCMC methods. The box plots clearly show
that the adaptive truncation approach is beneficial in terms of estimation
accuracy as our method beats the other two methods for both parameters and all
the tried $\epsilon$ values.

$\epsilon=1$$\epsilon=2$$\epsilon=5$$\epsilon=10$

Figure 2: The particle distribution of SMC (every 20th time-step shown) (blue
points) and the estimate of the posterior means (red line) versus time. Black
lines indicate the true values. In plots for $\mu$, truncation points are also
shown.

$\epsilon=1$ $\epsilon=2$ $\epsilon=5$ $\epsilon=10$

Figure 3: Box-plots of the posterior means, obtained from 30 runs

## 7 Conclusion

This paper presents a novel methodology for differentially private online
Bayesian estimation with adaptive truncation. The proposed methodology is a
working example of the general idea that, as we gain knowledge about the
process that generates sensitive data, we can modify our ‘query’ about
sensitive data to get more utility while maintaining the same level of
privacy. The proposed method demonstrated its merits in the numerical
experiments involving the normal distribution, one of the most commonly used
distributions for modelling univariate i.i.d. data. It would be interesting to
see the extension of the work to other distributions, especially multivariate
distributions.

Although we considered the Laplace mechanism throughout, the methodology can
be modified straightforwardly for other privacy mechanisms, such as the
Gaussian mechanism, that provide different senses of privacy. All that changes
throughout is the conditional distribution of $Y_{t}$ given
$x_{t},\theta,s_{t},\epsilon$.

We considered Bayesian inference in this work. Bayesian inference fits ideally
into the exploration-exploitation framework by providing a proper sense of
uncertainty about $\theta$ via the posterior distribution. However, its
computational cost that grows quadratically with data size can be concerning
when $n$ is very large. We mentioned some possible ways to reduce the
computational load. A viable alternative is to use an online gradient method
for online point estimation of $\theta$, where the gradients can be calculated
approximately using Monte Carlo as in Algorithm 4. The online gradient method
can be advantageous in terms of computational load but it would be more
challenging to tune the exploration-exploitation heuristic since a posterior
distribution of $\theta$ would not be available.

One limitation of this work is the requirement of considering a parametric
distribution family for the population distribution. Estimation of
characteristics regarding non-parametric distributions, such the as mean and
quantiles, is also a fundamental problem for data streaming applications
(Dwork and Lei, , 2009; Alabi et al., , 2022). A useful extension of this work
would be an online estimation methodology of (characteristics) non-parametric
distributions. Non-parametric methods like conformal prediction (Shafer and
Vovk, , 2008) can be considered for the adaptive query selection.

## Acknowledgment

This study was funded by the Scientific and Technological Research Council of
Turkey (TÜBİTAK) ARDEB Grant No 120E534. The author is supported by the grant.

## References

  * Alabi et al., (2022) Alabi, D., Ben-Eliezer, O., and Chaturvedi, A. (2022).  Bounded Space Differentially Private Quantiles.  arXiv e-prints, page arXiv:2201.03380.
  * Alparslan and Yıldırım, (2022) Alparslan, B. and Yıldırım, S. (2022).  Statistic selection and mcmc for differentially private bayesian estimation.  Statistics and Computing, 32(5):66.
  * Andrieu et al., (2020) Andrieu, C., Yıldırım, S., Doucet, A., and Chopin, N. (2020).  Metropolis-Hastings with averaged acceptance ratios.  arXiv:2101.01253.
  * Bernstein and Sheldon, (2018) Bernstein, G. and Sheldon, D. (2018).  Differentially private Bayesian inference for exponential families.  In NeurIPS.
  * Bun and Steinke, (2016) Bun, M. and Steinke, T. (2016).  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985, pages 635–658, New York, NY, USA. Springer-Verlag New York, Inc.
  * Cao et al., (2017) Cao, Y., Yoshikawa, M., Xiao, Y., and Xiong, L. (2017).  Quantifying differential privacy under temporal correlations.  In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 821–832.
  * Chan et al., (2011) Chan, T.-H. H., Shi, E., and Song, D. (2011).  Private and continual release of statistics.  ACM Trans. Inf. Syst. Secur., 14(3).
  * Chopin, (2002) Chopin, N. (2002).  A sequential particle filter method for static models.  Biometrika, 89(3):539–551.
  * Dong et al., (2022) Dong, J., Roth, A., and Su, W. J. (2022).  Gaussian differential privacy.  Journal of the Royal Statistical Society Series B, 84(1):3–37.
  * Dwork, (2006) Dwork, C. (2006).  Differential privacy.  In Bugliesi, M., Preneel, B., Sassone, V., and Wegener, I., editors, Automata, Languages and Programming, pages 1–12, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Dwork, (2008) Dwork, C. (2008).  Differential privacy: A survey of results.  In Agrawal, M., Du, D., Duan, Z., and Li, A., editors, Theory and Applications of Models of Computation, pages 1–19, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Dwork and Lei, (2009) Dwork, C. and Lei, J. (2009).  Differential privacy and robust statistics.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 371–380, New York, NY, USA. Association for Computing Machinery.
  * Dwork et al., (2010) Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010).  Differential privacy under continual observation.  In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, pages 715–724, New York, NY, USA. Association for Computing Machinery.
  * Dwork and Roth, (2013) Dwork, C. and Roth, A. (2013).  The algorithmic foundations of differential privacy.  Theoretical Computer Science, 9(3-4):211–407.
  * Foulds et al., (2016) Foulds, J., Geumlek, J., and an Kamalika Chaudhuri, M. W. (2016).  On the theory and practice of privacy-preserving Bayesian data analysis.  Technical report, arxiv:1603.07294.
  * Geweke, (1989) Geweke, J. (1989).  Bayesian inference in econometric models using Monte Carlo integration.  Econometrica, 57(6):1317–1339.
  * Gilks and Berzuini, (2001) Gilks, W. R. and Berzuini, C. (2001).  Following a moving target-Monte Carlo inference for dynamic Bayesian models.  J. R. Stat. Soc. B, 63(1):127–146.
  * Gong, (2022) Gong, R. (2022).  Exact inference with approximate computation for differentially private data via perturbations.  Journal of Privacy and Confidentiality, 12(2).
  * Heikkilä et al., (2017) Heikkilä, M., Lagerspetz, E., Kaski, S., Shimizu, K., Tarkoma, S., and Honkela, A. (2017).  Differentially private bayesian learning on distributed data.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
  * Heikkilä et al., (2019) Heikkilä, M. A., Jälkö, J., Dikmen, O., and Honkela, A. (2019).  Differentially private Markov chain Monte Carlo.  In NeurIPS.
  * Jones and Noufaily, (2015) Jones, M. C. and Noufaily, A. (2015).  Log-location-scale-log-concave distributions for survival and reliability analysis.  Electronic Journal of Statistics, 9(2):2732 – 2750.
  * Ju et al., (2022) Ju, N., Awan, J., Gong, R., and Rao, V. (2022).  Data augmentation MCMC for bayesian inference from privatized data.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems.
  * Karwa et al., (2014) Karwa, V., Slavković, A. B., and Krivitsky, P. (2014).  Differentially private exponential random graphs.  In Domingo-Ferrer, J., editor, Privacy in Statistical Databases, pages 143–155, Cham. Springer International Publishing.
  * Li et al., (2019) Li, B., Chen, C., Liu, H., and Carin, L. (2019).  On connecting stochastic gradient MCMC and differential privacy.  In Chaudhuri, K. and Sugiyama, M., editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 557–566. PMLR.
  * Park et al., (2021) Park, M., Vinaroz, M., and Jitkrittum, W. (2021).  ABCDP: Approximate Bayesian computation with differential privacy.  Entropy, 23(8).
  * Räisä et al., (2021) Räisä, O., Koskela, A., and Honkela, A. (2021).  Differentially private Hamiltonian Monte Carlo.
  * Russo et al., (2018) Russo, D. J., Roy, B. V., Kazerouni, A., Osband, I., and Wen, Z. (2018).  A tutorial on thompson sampling.  Foundations and Trends in Machine Learning, 11(1):1–96.
  * Shafer and Vovk, (2008) Shafer, G. and Vovk, V. (2008).  A tutorial on conformal prediction.  J. Mach. Learn. Res., 9:371–421.
  * Wang et al., (2015) Wang, Y.-X., Fienberg, S., and Smola, A. (2015).  Privacy for free: Posterior sampling and stochastic gradient Monte Carlo.  In Blei, D. and Bach, F., editors, Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pages 2493–2502. JMLR Workshop and Conference Proceedings.
  * Williams and Mcsherry, (2010) Williams, O. and Mcsherry, F. (2010).  Probabilistic inference and differential privacy.  In Lafferty, J., Williams, C., Shawe-Taylor, J., Zemel, R., and Culotta, A., editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc.
  * Yıldırım and Ermiş, (2019) Yıldırım, S. and Ermiş, B. (2019).  Exact MCMC with differentially private moves.  Statistics and Computing, 29(5):947–963.

##  Appendix A Proof of Proposition 1

###### Proof.

(Proposition 1) Let $R_{n}$ be the set of all revealed outputs of Algorithm 1.
For any $n\geq 1$, its conditional distribution given $X_{1:n}=x_{1:n}$ at
$R_{n}=(y_{1:n},s_{1:n},\theta_{1:n})$ is given by

$P(\mathrm{d}R_{n}|X_{1:n}=x_{1:n})=\prod_{t=1}^{n}\textup{Laplace}(y_{t}-s_{t}(x_{t}),\Delta
s_{t}/\epsilon)\mathrm{d}y_{t}\prod_{t=1}^{n}P(\mathrm{d}s_{t}|\theta_{t})p(\mathrm{d}\theta_{t}|\theta_{1:t-1},y_{1:t},s_{1:t})$

The ratio between the conditional distributions with $x_{1:n}$ and
$x^{\prime}_{1:n}$ for any neighbour pair $x_{1:n},x^{\prime}_{1:n}$ differing
by some $k$’th element is given by

$e^{-\epsilon}<\frac{P(\mathrm{d}R_{n}|X_{1:n}=x_{1:n})}{P(\mathrm{d}R_{n}|X_{1:n}=x^{\prime}_{1:n})}=\frac{\prod_{t=1}^{n}\textup{Laplace}(y_{t}-s_{t}(x_{t}),\Delta
s_{t}/\epsilon)}{\prod_{t=1}^{n}\textup{Laplace}(y_{t}-s_{t}(x^{\prime}_{t}),\Delta
s_{t}/\epsilon)}=\frac{\textup{Laplace}(y_{k}-s_{k}(x_{k}),\Delta
s_{k}/\epsilon)}{\textup{Laplace}(y_{k}-s_{k}(x^{\prime}_{k}),\Delta
s_{k}/\epsilon)}<e^{\epsilon}$

where the first equality is because the other factors do not depend on
$x_{1:n}$ (or $x^{\prime}_{1:n}$), the second equality is because $x_{1:n}$
and $x^{\prime}_{1:n}$ differ by the $k$’th element only. ∎

##  Appendix B Proof of Theorem 3

We prove the theorem by first showing that the distribution of $Y$ in (12)
belongs to a location-scale family. Lemmas 1 and 2 are used for establishing
that. Given a distribution with density $f$ on $\mathbb{R}$ and an interval
$[l,r]$, we define $f_{[l,r]}$ to be $f$ truncated to $[l,r]$, that is
$f_{[l,r]}(x)\propto f(x)\mathbb{I}\\{x\in[l,r]\\}$. Lemma 1 states that the
truncated version of a location-scale distribution is also a location-scale
distribution.

######  Lemma 1.

Let $\\{f(x;m,c);m\in\mathbb{R}\\}$ be a location-scale family of
distributions with location parameter $m$, scale parameter $c$ and base
distribution $g$. For any $a,b$; the family of truncated distributions
$\\{f_{[ca+m,cb+m]}(x;m,c):(m,c)\in\mathbb{R}\times[0,\infty)\\}$ is a
location-scale family with location parameter $m$, scale parameter $c$, and
base distribution $g_{[a,b]}$.

###### Proof.

(Lemma 1) For all $x\in\mathcal{X}$, $a,b\in\mathbb{R}$,
$(m,c)\in\mathbb{R}\times[0,\infty)$, we have

$\displaystyle f_{[ca+m,cb+m]}(x;m,c)$
$\displaystyle=\frac{f(x;m,c)\mathbb{I}\\{x\in[ca+m,cb+m]\\}}{\int_{ca+m}^{cb+m}f(u;m,c)du}$

Using $f(x;m,c)=g((x-m)/c)/c$,
$\mathbb{I}\\{x\in[ca+m,cb+m]\\}=\mathbb{I}\\{(x-m)/c\in[a,b]\\}$, and
$\int_{ca+m}^{cb+m}\frac{1}{c}g((u-m)/c)du=\int_{a}^{b}g(u)du$ by change of
variables, we end up with

$\displaystyle f_{[ca+m,cb+m]}(x;m,c)$
$\displaystyle=\frac{g((x-m)/c)/c\mathbb{I}\\{(x-m)/c\in[a,b]\\}}{\int_{a}^{b}g(u)du}=\frac{1}{c}g_{[a,b]}((x-m)/c).$

Hence, $f_{[ca+m,cb+m]}(x;m,c)$ is a location-scale distribution with location
$m$, scale $c$, base distribution $g_{[a,b]}$. ∎

Let $f^{\epsilon}_{[ca+m,cb+m]}(x;m,c)$ be the distribution of $Y$ defined in
(12). Let $g^{\epsilon}_{a,b}$ be the distribution of $X_{0}+(b-a)V_{0}$ where
$X_{0}\sim g_{[a,b]}$, $V_{0}\sim\text{Laplace}(1/\epsilon)$, and $X_{0}$ and
$V_{0}$ are independent.

######  Lemma 2.

Given $a,b\in\mathbb{R}$ and $\epsilon\in(0,\infty)$, the distribution family
$\\{f^{\epsilon}_{[ca+m,cb+m]}(x;m,c):m\in\mathbb{R},c\in[0,\infty)\\}$ is a
location-scale family with location $m$, scale $c$ and base distribution
$g_{a,b}^{\epsilon}$.

###### Proof.

(Lemma 2) By Lemma 1, the distribution of $T_{ac+m}^{bc+m}(X)$ is a location-
scale distribution with location $m$, scale $c$, and base distribution
$g_{a,b}$. For $Y$ in (12), it can be checked that $Y=cY_{0}+m$ where
$Y_{0}=X_{0}+(b-a)V_{0}$, where $X_{0}=(T_{ac+m}^{bc+m}(X)-m)/c\sim g_{a,b}$,
$V_{0}\sim\textup{Laplace}(1/\epsilon)$ and $X_{0}$ and $V_{0}$ are
independent. Then, $Y_{0}\sim g^{\epsilon}_{a,b}$, which does not depend on
$m$ and $c$. Hence we conclude. ∎

Finally, we proceed to the proof of Theorem 3.

###### Proof.

(Theorem 3) Since the distribution of $Y$ is a location-scale distribution by
Lemma 2, the Fisher information associated to it is given by
$F^{\epsilon}_{ac+m,bc+m}(m,c)=\frac{1}{c^{2}}F^{\epsilon}_{a,b}(0,1)$, where
$F^{\epsilon}_{a,b}(0,1)$ is the Fisher information matrix associated with the
base distribution $g_{a,b}^{\epsilon}(x)$ (for explicit formulae, see, e.g.
Jones and Noufaily,  (2015)), and depends on $a$, $b$, and $\epsilon$, but not
on $m$ and $c$. Therefore, if
$\text{sc}(F_{a,b}^{\epsilon}(0,1))>\text{sc}(F_{a^{\prime},b^{\prime}}^{\epsilon}(0,1))$
(resp. $<$, $=$), then
$\text{sc}(F_{a,b}^{\epsilon}(m,c))>\text{sc}(F_{a^{\prime},b^{\prime}}^{\epsilon}(m,c))$
(resp. $<$, $=$) for any other $(m,c)\in\mathbb{R}\times(0,\infty)$. ∎

##  Appendix C Supplementary algorithms

Algorithm 3 presents an MCMC move for the rejuvenation step of SMC at time
$t$.

Input: The current sample $(x_{1:t},\theta)$, proposal distributions
$q(x^{\prime}|x)$ and $q(\theta^{\prime}|\theta)$, $\epsilon$

Output: The new sample

1 MH update for $x_{1:t}$:

2 for  _$k=1:t$_ do

3 Sample $x^{\prime}_{k}\sim q(x_{k}^{\prime}|x_{k})$ and return
$x^{\prime}_{k}$ as the new sample w.p.
$\min\left\\{1,\frac{p_{\theta}(x^{\prime}_{k})\textup{Laplace}(y_{k}-s_{k}(x^{\prime}_{k}),\Delta
s_{k}/\epsilon)q(x_{k}|x_{k}^{\prime})}{p_{\theta}(x_{k})\textup{Laplace}(y_{k}-s_{k}(x_{k}),\Delta
s_{k}/\epsilon)q(x^{\prime}_{k}|x_{k})}\right\\};$ otherwise return $x_{k}$ as
the new sample.

MH update for $\theta$: Sample $\theta^{\prime}\sim q(\theta^{\prime}|\theta)$
and return $\theta^{\prime}$ as the new sample w.p.
$\min\left\\{1,\frac{q(\theta|\theta^{\prime})\eta(\theta^{\prime})\prod_{k=1}^{t}p_{\theta^{\prime}}(x_{k})}{q(\theta^{\prime}|\theta)\eta(\theta)\prod_{k=1}^{t}p_{\theta}(x_{k})}\right\\};$
otherwise, return $\theta$ as the new sample.

Algorithm 3 MCMC for $p^{\epsilon}_{s_{1:t}}(\theta,x_{1:t}|y_{1:t})$ \- a
single update

Algorithm 4 approximates Fisher’s identity for the score vector,

$\nabla_{\theta}\log p_{\theta,s}^{\epsilon}(y)=\int\nabla\log
p_{\theta}(x)p_{\theta,s}^{\epsilon}(x|y)\mathrm{d}x,$

using self-normalised importance sampling (Geweke, , 1989) with a sample of
size $N$ from $\mathcal{P}_{\theta}$.

Input: Parameter $\theta$, observation $y$, DP parameter $\epsilon$,
truncation points $l,r$

Output: Gradient vector $\widetilde{\nabla_{\theta}\log
p_{l,r}^{\epsilon}(y|\theta)}$

1 for  _$i=1,\ldots,N$_ do

2 Sample $x^{(i)}\sim\mathcal{P}_{\theta}$,

3 Calculate $w^{(i)}=\textup{Laplace}(y_{k}-T_{l}^{r}(x^{(i)}),\Delta
s_{k}/\epsilon)$.

Calculate the (approximate) gradient as  $\widetilde{\nabla_{\theta}\log
p_{l,r}^{\epsilon}(y|\theta)}=\frac{\sum_{i=1}^{N}w^{(i)}\nabla_{\theta}\log
p_{\theta}(x^{(i)})}{\sum_{i=1}^{N}w^{(i)}}.$

Algorithm 4 Monte Carlo calculation of the gradient


# Norm bounds for self-adjoint Toeplitz operators with non-radial symbols on
the Fock space

Yi C. Huang  Yunnan Key Laboratory of Modern Analytical Mathematics and
Applications, Yunnan Normal University, Kunming 650500, People’s Republic of
China  Department of Mathematical Sciences, Tsinghua University, Beijing
100084, People’s Republic of China  School of Mathematical Sciences, Nanjing
Normal University, Nanjing 210023, People’s Republic of China
<EMAIL_ADDRESS>https://orcid.org/0000-0002-1297-7674 and  Jian-
Yang Zhang  School of Mathematical Sciences, Nanjing Normal University,
Nanjing 210023, People’s Republic of China<EMAIL_ADDRESS>
###### Abstract.

In this paper we extend Galbis’ elegant norm bounds for self-adjoint Toeplitz
operators on the Fock space to bounded and integrable symbols which are non-
radial. The main ingredients are a transplantation of the remarkable Nicola-
Tilli isoperimetric inequality to the realm of Fock-Toeplitz operator theory
and a two-dimensional adaption of Galbis’ integration and approximation
arguments.

###### Key words and phrases:

Toeplitz operators, Fock space, Gaussian isoperimetric inequalities, operator
norm bounds, extremal problems

###### 1991 Mathematics Subject Classification:

Primary 47B35; Secondary 30H20

Research of the authors is partially supported by the National NSF grant of
China (no. 11801274), the Visiting Scholar Program from the Department of
Mathematical Sciences of Tsinghua University, and the Open Project from Yunnan
Normal University (no. YNNUMA2403). YCH thanks Shunlong Luo, Congwen Liu and
Youjiang Lin for helpful communications.

##  1\. Introduction

Using the Hermite expansion, Galbis obtained in [2] inspiring norm bounds for
self-adjoint Toeplitz operators with radial, bounded and integrable symbols on
the Fock space defined on the complex plane. See also Grudsky and Vasilevski
[4] for a related result. In this paper we extend Galbis’ norm bounds to the
non-radial case. The main ingredient is a Gaussian isoperimetric inequality
established recently by Nicola and Tilli in [6], and for readers’ convenience
we recall it as follows.

######  Theorem 1 (Nicola-Tilli, [6]).

For every $f\in{\mathcal{F}}^{2}({\mathbb{C}})$ with $||f||_{{\mathcal{F}}}=1$
and every measurable set $\Omega\subset\mathbb{C}$ of finite measure, there
holds

$\int_{\Omega}|f(z)|^{2}e^{-\pi|z|^{2}}\,dA(z)\leq 1-e^{-|\Omega|},$

where $|\Omega|$ is the Lebesgue measure of $\Omega$.

######  Remark 2.

For more recent progresses following this remarkable result (in different
background geometry or its stability), we mention for example Kulikov [5],
Frank [1], and Gómez-Guerra-Ramos-Tilli [3] (and the references therein).

In the statement of Theorem 1, the Fock (or Bargmann-Fock) space
${\mathcal{F}}^{2}({\mathbb{C}})$ is the Hilbert space consisting of those
entire functions $f$ such that

$\|f\|_{{\mathcal{F}}}^{2}=\int_{{\mathbb{C}}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)<+\infty,$

where $dA(z)$ denotes the Lebesgue measure. It is well known that
${\mathcal{F}}^{2}({\mathbb{C}})$ admits a reproducing kernel
$K(z,w)=e^{\pi\overline{w}z},$ which means that

$f(w)=\int_{{\mathbb{C}}}f(z)\overline{K(z,w)}e^{-\pi|z|^{2}}\ dA(z),\ \
f\in{\mathcal{F}}^{2}({\mathbb{C}}).$

For simplicity we denote $d\lambda(z)=e^{-\pi|z|^{2}}dA(z),$ so
${\mathcal{F}}^{2}({\mathbb{C}})$ is a closed subspace of
$L^{2}({\mathbb{C}},d\lambda).$ The induced orthogonal projection

$\mathbb{P}:L^{2}({\mathbb{C}},d\lambda)\to{\mathcal{F}}^{2}({\mathbb{C}})$

is the integral operator

$\left(\mathbb{P}f\right)(z)=\int_{{\mathbb{C}}}f(w)\overline{K(w,z)}\
d\lambda(w).$

For a measurable and bounded function $\varphi$ on ${\mathbb{C}}$, the
Toeplitz operator associated with symbol $\varphi$ is defined as

$T_{\varphi}(f)(z)=\mathbb{P}(\varphi
f)(z)=\int_{{\mathbb{C}}}\varphi(w)f(w)\overline{K(w,z)}\ d\lambda(w).$

It is obvious that

$T_{\varphi}:{\mathcal{F}}^{2}({\mathbb{C}})\to{\mathcal{F}}^{2}({\mathbb{C}})$

is a bounded operator and

$\|T_{\varphi}(f)\|_{\mathcal{F}}\leq\|\varphi
f\|_{L^{2}({\mathbb{C}},d\lambda)}\leq\|\varphi\|_{\infty}\cdot\|f\|_{\mathcal{F}}.$

The Toeplitz operator defined by a real valued symbol $\varphi$ is self-
adjoint. This can be seen via the following pairing identity

$\langle
T_{\varphi}(f),g\rangle=\int_{{\mathbb{C}}}\varphi(z)f(z)\overline{g(z)}d\lambda(z)$

for all $f,g\in{\mathcal{F}}^{2}({\mathbb{C}}).$ In this case we have

$\|T_{\varphi}\|=\sup_{\|f\|_{\mathcal{F}}=1}\left|\langle
T_{\varphi}(f),f\rangle\right|\leq\sup_{\|f\|_{\mathcal{F}}=1}\int_{{\mathbb{C}}}|\varphi(z)|\cdot|f(z)|^{2}d\lambda(z).$
(1)

In order to estimate $||T_{\varphi}||$, we only need to estimate

$\int_{{\mathbb{C}}}|\varphi(z)|\cdot|f(z)|^{2}d\lambda(z),$

where $f\in\mathcal{F}^{2}(\mathbb{C})$ such that $||f||_{\mathcal{F}}=1$.
Using Theorem 1 of Nicola and Tilli, and adapting [2, Lemma 2] of Galbis, we
obtain the following result.

######  Theorem 3.

Let $\varphi\in L^{1}({\mathbb{C}})\cap L^{\infty}({\mathbb{C}})$ be a real-
valued symbol. Then

$\|T_{\varphi}\|\leq\|\varphi\|_{\infty}\left(1-\exp\left(-\frac{\|\varphi\|_{1}}{\|\varphi\|_{\infty}}\right)\right).$
(2)

######  Remark 4.

Examing the statements in Nicola and Tilli [6], it is also transparent that
the equality in (2) is attained by choosing $\varphi$ as the indicator
function of a disc with measure $\|\varphi\|_{1}$ and the operator norm in (1)
is saturated by $f(z)=K(z,w_{0})/K(w_{0},w_{0})$ with $w_{0}$ being the center
of that disc.

##  2\. Proof of Theorem 1

First, we prove the following simple but very useful integration lemma which
is a two-dimensional adaption of [2, Lemma 2].

######  Lemma 5.

Let $(\Omega_{k})_{k=1}^{N}$ be disjoint sets contained in $\mathbb{C}$ with
finite measure and $0\leq\varepsilon_{k}\leq 1$ for every $1\leq k\leq N.$
Then, for every $f\in{\mathcal{F}}^{2}(\mathbb{C})$ such that
$||f||_{{\mathcal{F}}}=1$ we have

$\sum_{k=1}^{N}\varepsilon_{k}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)\leq 1-\exp\left(-\sum_{k=1}^{N}\varepsilon_{k}|\Omega_{k}|\right).$

###### Proof.

We denote by $n$ the number of indices $k$ such that $0<\varepsilon_{k}<1$ and
we proceed by induction on $n.$ For $n=0$, by Theorem 1 we have

$\sum_{k=1}^{N}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\ dA(z)\leq
1-\exp\left(-\sum_{k=1}^{N}|\Omega_{k}|\right).$

Let us now assume $n=1.$ Let $1\leq j\leq N$ be the coordinate with the
property that $0<\varepsilon_{j}<1$ and define function $\psi$ by:

$\displaystyle\psi(\varepsilon):=$ $\displaystyle\sum_{k\neq
j}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)+\varepsilon\int_{\Omega_{j}}|f(z)|^{2}e^{-\pi|z|^{2}}\ dA(z)$
$\displaystyle+\exp\left(-\sum_{k\neq
j}|\Omega_{k}|-\varepsilon|\Omega_{j}|\right),\,\,\qquad 0\leq\varepsilon\leq
1.$

We aim to prove $\psi(\varepsilon)\leq 1$. In fact, $\psi(0)\leq 1$ and
$\psi(1)\leq 1$ follow from Theorem 1. Moreover, the critical point
$\varepsilon_{0}$ of $\psi$ satisfies

$\int_{\Omega_{j}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)=|\Omega_{j}|\exp\left(-\sum_{k\neq
j}|\Omega_{k}|-\varepsilon_{0}|\Omega_{j}|\right).$

Hence

$\displaystyle\psi(\varepsilon_{0})$ $\displaystyle=\sum_{k\neq
j}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)+\varepsilon_{0}|\Omega_{j}|\exp\left(-\sum_{k\neq
j}|\Omega_{k}|-\varepsilon_{0}|\Omega_{j}|\right)$
$\displaystyle\qquad+\exp\left(-\sum_{k\neq
j}|\Omega_{k}|-\varepsilon_{0}|\Omega_{j}|\right)$ $\displaystyle=\sum_{k\neq
j}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)+\left(1+\varepsilon_{0}|\Omega_{j}|\right)\exp\left(-\sum_{k\neq
j}|\Omega_{k}|-\varepsilon_{0}|\Omega_{j}|\right).$

Since

$1+\varepsilon_{0}|\Omega_{j}|\leq\exp\left(\varepsilon_{0}|\Omega_{j}|\right)$

we conclude

$\psi(\varepsilon_{0})\leq\sum_{k\neq
j}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\ dA(z)+\exp\left(-\sum_{k\neq
j}|\Omega_{k}|\right)\leq 1.$

Let us assume that the lemma holds for $n=\ell$ ($0\leq\ell<N$). Then we
consider $n=\ell+1$ and the function $\psi:[0,1]^{\ell+1}\to{\mathbb{R}}$
defined by

$\displaystyle\psi({\bm{\varepsilon}}):=$
$\displaystyle\sum_{k=1}^{\ell+1}\varepsilon_{k}\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)+\sum_{j}\int_{\Omega_{j}}|f(z)|^{2}e^{-\pi|z|^{2}}\ dA(z)$
$\displaystyle\qquad+\exp\left(-\sum_{k}\varepsilon_{k}|\Omega_{k}|-\sum_{j}|\Omega_{j}|\right)$

for ${\bm{\varepsilon}}=(\varepsilon_{1},\ldots,\varepsilon_{\ell+1}).$ The
induction hypothesis means that $\psi({\bm{\varepsilon}})\leq 1$ whenever
${\bm{\varepsilon}}$ is in the boundary of $[0,1]^{\ell+1}.$ The lemma is
proved after checking $\psi({\bm{\varepsilon}}_{0})\leq 1,$ where
${\bm{\varepsilon}_{0}}$ is a critical point of $\psi.$ Proceeding as before,

$\begin{array}[]{*2{>{\displaystyle}l}}\psi({\bm{\varepsilon}}_{0})&=\left(\sum_{k=1}^{\ell+1}\varepsilon_{k}|\Omega_{k}|+1\right)e^{-\sum_{k}\varepsilon_{k}|\Omega_{k}|}e^{-\sum_{j}|\Omega_{j}|}+\sum_{j}\int_{\Omega_{j}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)\\\ &\\\
&\leq\exp\left(-\sum_{j}|\Omega_{j}|\right)+\sum_{j}\int_{\Omega_{j}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)\leq 1.\end{array}$

By induction, we finish the proof of Lemma 5.∎

Next we give a proof of Theorem 3.

###### Proof.

After replacing $\varphi$ by $\frac{\varphi}{\|\varphi\|_{\infty}}$ if
necessary we can assume that $\|\varphi\|_{\infty}=1.$ According to (1), we
aim to prove that

$\int_{\mathbb{C}}|\varphi(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\ dA(z)\leq
1-\exp(-||\varphi||_{1})$

for every entire function $f\in\mathcal{F}^{2}(\mathbb{C})$ such that
$||f||_{\mathcal{F}}=1.$ Let us first assume

$\varphi=\sum_{k=1}^{N}\varepsilon_{k}\chi_{\Omega_{k}},\
\left|\varepsilon_{k}\right|\leq 1,$ (3)

where $(\Omega_{k})_{k=1}^{N}$ are disjoint measurable sets in $\mathbb{C}$
with finite measure. Then, Lemma 5 gives

$\begin{array}[]{*2{>{\displaystyle}l}}\int_{\mathbb{C}}|\varphi(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\
dA(z)&=\sum^{N}_{k=1}|\varepsilon_{k}|\int_{\Omega_{k}}|f(z)|^{2}e^{-\pi|z|^{2}}\
dA(z)\\\ &\\\ &\leq
1-\exp\left(-\sum_{k=1}^{N}|\varepsilon_{k}||\Omega_{k}|\right)\\\ &\\\
&=1-\exp\left(-\|\varphi\|_{1}\right).\end{array}$

Theorem 3 is proved for $\varphi$ as in (3). Let us now assume that
$\|\varphi\|_{\infty}=1$ and $\varphi\in L^{1}({\mathbb{C}}).$ Since
$\varphi\in L^{1}(\mathbb{C})$, there is a sequence $(\varphi_{n})_{n}$ of
simple functions as in (3) such that

$\lim_{n\to\infty}\int_{\mathbb{C}}|\varphi_{n}(z)-\varphi(z)|\ dA(z)=0.$

By triangle inequality, we have

$\displaystyle\int_{\mathbb{C}}|\varphi(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\
dA(z)$
$\displaystyle\leq\int_{\mathbb{C}}|\varphi_{n}(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\
dA(z)$
$\displaystyle\qquad+\int_{\mathbb{C}}|\varphi(z)-\varphi_{n}(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\
dA(z)$ $\displaystyle\leq 1-\exp\left(-\|\varphi_{n}\|_{1}\right)$
$\displaystyle\qquad+\int_{\mathbb{C}}|\varphi(z)-\varphi_{n}(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\
dA(z).$

Because for a function $f\in\mathcal{F}^{2}$ such that
$||f||_{\mathcal{F}}=1$, we have

$|f(z)|^{2}e^{-\pi|z|^{2}}\leq 1,$

see for example [7, Theorem 2.7] or [6, Proposition 2.1]. So

$\int_{\mathbb{C}}|\varphi(z)-\varphi_{n}(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\
dA(z)\leq\int_{\mathbb{C}}|\varphi_{n}(z)-\varphi(z)|\ dA(z).$

Hence we obtain

$\int_{\mathbb{C}}|\varphi(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\ dA(z)\leq
1-\exp\left(-\|\varphi_{n}\|_{1}\right)+\int_{\mathbb{C}}|\varphi_{n}(z)-\varphi(z)|\
dA(z).$

Letting $n\rightarrow\infty$, we have

$\int_{\mathbb{C}}|\varphi(z)|\left|f(z)\right|^{2}e^{-\pi|z|^{2}}\ dA(z)\leq
1-\exp\left(-\|\varphi\|_{1}\right).$

According to (1), this implies

$\|T_{\varphi}\|\leq 1-\exp\left(-\|\varphi\|_{1}\right).$

Thus the proof of Theorem 3 is finished. ∎

## Compliance with ethical standards

Conflict of interest The authors have no known competing financial interests
or personal relationships that could have appeared to influence this reported
work.

Availability of data and material Not applicable.

## References

  * [1] R. L. Frank.  Sharp inequalities for coherent states and their optimizers.  Advanced Nonlinear Studies, 23(1):20220050, 2023.
  * [2] A. Galbis.  Norm estimates for selfadjoint Toeplitz operators on the Fock space.  Complex Analysis and Operator Theory, 16(1):15, 2022.
  * [3] J. Gómez, A. Guerra, J. P. G. Ramos, and P. Tilli.  Stability of the Faber-Krahn inequality for the short-time Fourier transform.  Inventiones Mathematicae, 236(2):779–836, 2024.
  * [4] S. M. Grudsky and N. L. Vasilevski.  Toeplitz operators on the Fock space: radial component effects.  Integral Equations and Operator Theory, 44(1):10–37, 2002.
  * [5] A. Kulikov.  Functionals with extrema at reproducing kernels.  Geometric and Functional Analysis, 32(4):938–949, 2022.
  * [6] F. Nicola and P. Tilli.  The Faber–Krahn inequality for the short-time Fourier transform.  Inventiones Mathematicae, 230(1):1–30, 2022.
  * [7] K. Zhu.  Analysis on Fock spaces, volume 263 of Graduate Texts in Mathematics.  Springer, 2012.