# Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-
Composition Regime

Wael Alghamdi , Shahab Asoodeh , Flavio P. Calmon†,
Oliver Kosut , Lalitha Sankar§, and Fei Wei§ Corresponding author, remaining
authors in alphabetical order.W. Alghamdi and F. P. Calmon are with the School
of Engineering and Applied Science, Harvard University (emails:
<EMAIL_ADDRESS>flavio@seas.harvard.edu)S. Asoodeh is with the
Department of Computing and Software, McMaster University (email:
asoodehs@mcmaster.ca)O. Kosut, L. Sankar, and F. Wei are with the School of
Electrical, Computer, and Energy Engineering, Arizona State University
(emails<EMAIL_ADDRESS>
###### Abstract

Most differential privacy mechanisms are applied (i.e., composed) numerous
times on sensitive data. We study the design of optimal differential privacy
mechanisms in the limit of a large number of compositions. As a consequence of
the law of large numbers, in this regime the best privacy mechanism is the one
that minimizes the Kullback-Leibler divergence between the conditional output
distributions of the mechanism given two different inputs. We formulate an
optimization problem to minimize this divergence subject to a cost constraint
on the noise. We first prove that additive mechanisms are optimal. Since the
optimization problem is infinite dimensional, it cannot be solved directly;
nevertheless, we quantize the problem to derive near-optimal additive
mechanisms that we call “cactus mechanisms” due to their shape. We show that
our quantization approach can be arbitrarily close to an optimal mechanism.
Surprisingly, for quadratic cost, the Gaussian mechanism is strictly sub-
optimal compared to this cactus mechanism. Finally, we provide numerical
results which indicate that cactus mechanism outperforms the Gaussian
mechanism for a finite number of compositions.

00footnotetext: This material is based upon work supported by the National
Science Foundation under Grant Nos. CAREER-1845852, CIF-1900750, CIF-1815361,
CIF-1901243, CIF-1908725, CIF-2007688, and SaTC 2031799. The authors also
thank Oracle Research for a gift that supported this work.

This paper is Part I in a pair of papers, where Part II is [1].

##  1 Introduction

Likelihood ratios are at the heart of most privacy metrics. Consider the
problem of quantifying the privacy loss suffered by a sensitive variable $X$
given an observation of a disclosed variable $Y$. For example, $X$ may
represent a dataset and $Y$ a randomized function computed over $X$. Privacy
can be measured in terms of properties of the _privacy loss random variable_ ,
defined as

$L_{x,x^{\prime}}\coloneqq\log\frac{dP_{Y|X=x}}{dP_{Y|X=x^{\prime}}}(Y),$ (1)

where $Y\sim P_{Y|X=x}$ and
$x,x^{\prime}\in\mathcal{X}\coloneqq\mathsf{supp}(X).$ The channel $P_{Y|X}$
is often referred to as a _privacy mechanism_.

Today, the most popular privacy definition (including, in practice [2, 3, 4])
is _differential privacy_ (DP), which quantifies privacy in terms of
$L_{x,x^{\prime}}$ when $x,x^{\prime}$ are close or “neighboring.” Thus, given
a metric $d:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$, $P_{Y|X}$ is said to
be $(\varepsilon,\delta)$-differentially private ($(\varepsilon,\delta)$-DP)
[5] if

$\sup_{d(x,x^{\prime})\leq s}\
\sup_{A\subset\mathcal{Y}}\left[P_{Y|X=x}(A)-e^{\varepsilon}P_{Y|X=x^{\prime}}(A)\right]\leq\delta,$
(2)

where $s$ determines when inputs $x$ and $x^{\prime}$ are neighboring, and
$\mathcal{Y}:=\mathsf{supp}(Y)$. Intuitively, if a mechanism is
$(\varepsilon,\delta)$-differentially private for sufficiently small
$\varepsilon$ and $\delta$, then an adversary observing $Y$ cannot accurately
distinguish between small changes in $X$.

Most privacy mechanisms are applied several times on sensitive data.
Quantifying privacy guarantees under multiple _compositions_ of a mechanism is
a challenging problem. In the simple case where the same mechanism $P_{Y|X}$
is independently applied $n$ times on data $X$ generating output $Y^{n}$,
i.e., $P_{Y^{n}|X}=\prod_{i=1}^{n}P_{Y_{i}|X}$, the privacy loss random
variable is given by

$L_{x,x^{\prime}}^{n}\coloneqq\sum_{i=1}^{n}\log\frac{dP_{Y_{i}|X=x}}{dP_{Y_{i}|X=x^{\prime}}}(Y_{i}),$
(3)

where $Y_{i}\sim P_{Y_{i}|X=x}.$ Differential privacy can be cast in terms of
the privacy loss random variable. The reader can directly verify that $n$
independent applications of a mechanism $P_{Y|X}$ is $(\varepsilon,\delta)$-DP
if

$\sup_{d(x,x^{\prime})\leq
s}\mathbb{E}\left[\left(1-e^{-(L_{x,x^{\prime}}^{n}-\varepsilon)}\right)^{+}\right]\leq\delta.$
(4)

From the law of large numbers, the distribution of $L_{x,x^{\prime}}^{n}/n$
will concentrate around its mean, the KL-divergence, as

$\frac{1}{n}\mathbb{E}\left[L_{x,x^{\prime}}^{n}\right]=D\left(P_{Y|X=x}\|P_{Y|X=x^{\prime}}\right).$
(5)

Since the function $f(u)\coloneqq(1-e^{-nu+\varepsilon})^{+}$ is non-
decreasing, in the limit of large compositions, privacy mechanisms with lower
values of $D(P_{Y|X=x}\|P_{Y|X=x^{\prime}})$ will enjoy stronger
$(\varepsilon,\delta)$-DP guarantees. Thus, regardless of the exact
distribution of the privacy loss random variable, its mean (5) plays a central
role in the privacy guarantees offered after many compositions. In
applications such as privacy-ensuring machine learning, the number of
compositions frequently exceeds $n=10^{3}$.

We study the design of privacy mechanisms with favorable
$(\varepsilon,\delta)$-DP guarantees under a large number of compositions. Our
approach departs from previous work in that we focus on the large-composition
regime instead of optimizing (2). Since after many compositions, privacy will
be mostly determined by the mean of the privacy loss random variable (5), we
solve the optimization problem

$\begin{array}[]{ll}\displaystyle\inf_{P_{Y|X}\in\mathscr{R}}&\displaystyle\displaystyle\sup_{|x-x^{\prime}|\leq
s}D(P_{Y|X=x}\|P_{Y|X=x^{\prime}})\\\\[8.61108pt] \text{subject
to}&\displaystyle\sup_{x\in\mathbb{R}}~{}\mathbb{E}[c(Y-x)\mid X=x]\leq
C,\end{array}$ (6)

where $c:\mathbb{R}\to[0,\infty)$ is a pre-specified cost function, $s,C>0$
are constants, and $\mathscr{R}$ is the set of all Markov kernels on
$\mathbb{R}$. Note that the cost function is critical: without the constraint,
(6) can be trivially solved by any mechanism that is independent of $X$.

Our main contributions are as follows:

  1. 1.

We show (Thm. 1) that additive mechanisms—i.e., where $Y=X+Z$ for a noise
variable $Z$ independent of $X$—suffice to minimize (6).

  2. 2.

Even restricting to additive mechanisms, (6) is an infinite-dimensional
optimization problem, so it cannot be solved directly. Instead, we formulate
an approximate problem that is finite dimensional and can be solved
efficiently. We prove (Thm. 3) that this approximate problem can get arbitrary
close to optimal.

  3. 3.

We solve the approximate problem to derive (near) optimal mechanisms for the
quadratic cost function, i.e., $c(x)=x^{2}$. We dub the resulting mechanism
the “cactus mechanism” due to the shape of the distribution (see Fig. 1).
Surprisingly, the Gaussian distribution is strictly sub-optimal for (6), as
the cactus mechanism achieves a smaller KL divergence for the same variance.

  4. 4.

We bound the $(\varepsilon,\delta)$-DP for the cactus mechanism in the context
of sub-sampled stochastic gradient descent using the moments accountant
method. Compared to the same analysis applied to a Gaussian mechanism, our
approach does better for a reasonable number of compositions.

###  1.1 Related Work

Identifying optimal mechanisms is a fundamental and challenging problem in the
domain of differential privacy. There have been several works in the
literature that have attempted to address this problem. For instance, within
the class of additive noise mechanisms and under the single shot setting
(i.e., no composition), Ghosh et al. [6] showed that the geometric mechanism
is universally optimal for $(\varepsilon,0)$-DP in a Bayesian framework, and
Gupte and Sundararajan [7] derived the optimal noise distribution in a minimax
cost framework. For a rather general cost function, the optimal noise
distribution was shown to have a staircase-shaped density function [8, 9, 10].

Geng and Viswanath [11] showed that for $(\varepsilon,\delta)$-DP and integer-
valued query functions, in the single-shot setting, the discrete uniform noise
distribution and the discrete Laplacian noise distribution are asymptotically
optimal (for $L^{1}$ and $L^{2}$ costs) within a constant multiplicative gap
in the high privacy regime (i.e., both $\varepsilon$ and $\delta$ approach
zero). Geng et al. [12] studied the same setting except for real-valued query
functions and identified truncated Laplace distribution is asymptotically
optimal in various high privacy regimes. Finally, Geng et al. [13] showed that
the optimal noise distribution for real-valued query and $(0,\delta)$-DP is
uniform with probability mass at the origin. Our work differs from these works
in that we focus on the optimal mechanisms under a large number of
compositions, rather than the single shot setting.

When considering a composition of $n$ mechanisms, an important line of
research has been to derive tighter composition results: relationships between
the DP parameters of the composed mechanism and the parameters of each
constituent mechanism. There are several composition results in the
literature, such as [14, 15, 16, 17, 18, 19]. More recently, Dong et al. [20]
have proposed a composition result for large $n$ and for a new variant of DP,
called Gaussian-DP, that leverages the central limit theorem. These results
can be sub-optimal (see, for example, [21, Fig. 1]). Consequently, numerical
composition results have gained increasing traction as they lead to easier,
yet powerful, methods for accounting the privacy loss in composition [22, 21,
23, 24]. In particular, Koskela et al. [22] obtained a numerical composition
result based on a numerical approximation of an integral that gives the DP
parameters of the composed mechanism. The approximation is carried out by
discretizing the integral and by evaluating discrete convolutions via the fast
Fourier transform algorithm. The running time and memory needed for this
approximation were subsequently improved [21]. While our work shares the focus
on the large composition regime, we are primarily interested in synthesizing
optimal mechanisms rather than analyzing existing mechanisms.

###  1.2 Notation

The Lebesgue measure on $\mathbb{R}$ is denoted by $\lambda$. We denote by
$\mathscr{R}$ the set of all Markov kernels111It is true that any conditional
distribution from $\mathbb{R}$ into $\mathbb{R}$ has a version that is a
Markov kernel [25, Chapter 4, Theorem 2.10]. on $\mathbb{R}$, i.e.,
conditional distributions $P_{Y|X}$ for $\mathbb{R}$-valued $X$ and $Y$ such
that $x\mapsto P_{Y|X=x}(B)$ is a Borel function for all Borel sets
$B\subset\mathbb{R}$. The set $\mathscr{B}$ denotes all Borel probability
measures on $\mathbb{R}$. We fix a real-valued random variable $X$ throughout,
and let $P_{X}\in\mathscr{B}$ be its induced Borel probability measure. The
KL-divergence is denoted by $D(P\|Q)$, and also by $D(p\|q)$ if
$P,Q\ll\lambda$ with densities $p$ and $q$. The expectation is denoted by
$\mathbb{E}_{P}[f]:=\int_{\mathbb{R}}f\,dP$, and also by $\mathbb{E}_{p}[f]$
if $P\ll\lambda$ has probability density function (PDF) $p$. We let $T_{a}$
denote the shift operator, i.e., for a function $f$ of a real variable the
function $T_{a}f$ is defined as $(T_{a}f)(x):=f(x-a)$, and for a measure $P$
the measure $T_{a}P$ is defined by $(T_{a}P)(B):=P(B-a)$.

##  2 Optimality of Additive Continuous Channels

We start by deriving characterizations of solutions to the optimization
problem (6). The difficulty of this problem lies in the fact that we are
optimizing over all conditional distributions. This not only makes the problem
infinite-dimensional, but it also renders direct approaches ineffective. The
main result of this section, shown in Theorem 1, is that it suffices to
consider continuous additive channels. In other words, the optimization in (6)
may be restricted to conditional distributions of the form $P_{Y|X=x}=T_{x}P$
for some Borel probability measure $P$ on $\mathbb{R}$ that is absolutely
continuous with respect to the Lebesgue measure. Equipped with this reduction,
we build in the next section an explicit family of finitely-parametrized
distributions that are also optimal in (6).

###  2.1 Assumptions and Definitions

Throughout the paper, we require the cost function to satisfy the following
properties.

######  Assumption 1.

The cost function $c:\mathbb{R}\to\mathbb{R}$ satisfies:

  * •

_Positivity:_ $c(x)\geq 0$ for all $x\in\mathbb{R},$ and $c(0)=0.$

  * •

_Symmetry:_ $c(x)=c(-x)$ for all $x\in\mathbb{R}$.

  * •

_Monotonicity:_ $c(x)\leq c(x^{\prime})$ if $|x|\leq|x^{\prime}|$.

  * •

_Continuity:_ $c$ is continuous over $\mathbb{R}.$

  * •

_Tail regularity:_ There exist $\alpha,\beta>0$ such that $c(x)\sim\beta
x^{\alpha}$ as $x\to\infty.$

A natural choice of cost function is the quadratic cost $c(x)=x^{2}$, but we
allow $c(x)$ to be any function that satisfies the above assumptions. For
example, $c(x)=|x|^{\alpha}$ for any positive $\alpha$ is a natural family of
cost functions.

Let $\mathscr{P}\subset\mathscr{R}$ be the set of conditional distributions
$P_{Y|X}$ satisfying the cost constraint in (6), i.e., set

$\mathscr{P}:=\left\\{P_{Y|X}\in\mathscr{R}~{};~{}\sup_{x\in\mathbb{R}}~{}\mathbb{E}[c(Y-x)\mid
X=x]\leq C\right\\}.$ (7)

The infimal value in (6) is then

$\text{KL}^{\star}:=\inf_{P_{Y|X}\in\mathscr{P}}\
\sup_{x,x^{\prime}\in\mathbb{R}:|x-x^{\prime}|\leq s}\
D(P_{Y|X=x}\|P_{Y|X=x^{\prime}}).$ (8)

We are interested in computing $\text{KL}^{\star},$ as well as mechanisms
$P_{Y|X}$ that approach this optimal value. Note that, for clarity of
presentation, we suppress the dependence on $(s,c,C)$ in the notations
$\mathscr{P}$ and $\text{KL}^{\star}.$

In the main problem (6), we allow $P_{Y|X}$ to be any mechanism that produces
$Y$ given $X$. A more restrictive but natural and easy-to-implement class of
mechanisms is the _additive_ mechanism class. An additive mechanism is given
by $P_{Y|X=x}(B)=T_{x}P(B)$ where $P$ is a Borel probability measure on
$\mathbb{R}$. In other words, an additive mechanism $P_{Y|X}$ has $Y$ of the
form $Y=X+Z$ for some noise random variable $Z\sim P\in\mathscr{B}$ that is
independent of the input $X.$ Let $\mathscr{P}_{\text{add}}\subset\mathscr{B}$
be the set of additive mechanisms satisfying the cost constraint in (6),

$\mathscr{P}_{\text{add}}:=\left\\{P\in\mathscr{B}~{};~{}\mathbb{E}_{P}[c]\leq
C\right\\}.$ (9)

Since the KL-divergence is shift-invariant, restricting the optimization (6)
to additive mechanisms amounts to considering the simplified optimization
problem

$\text{KL}_{\text{add}}^{\star}:=\inf_{P\in\mathscr{P}_{\text{add}}}\
\sup_{a\in\mathbb{R}:|a|\leq s}\ D(P\|T_{a}P).$ (10)

Of course, it is immediate that
$\text{KL}^{\star}\leq\text{KL}_{\text{add}}^{\star}$. In fact, we will show
below that these quantities are the same, meaning that there is no loss in
restricting to additive mechanisms.

###  2.2 Optimality of Continuous Additive Mechanisms

The optimization problem in (6) is a convex problem, but the fact that the
feasible set $\mathscr{P}$ is of infinite dimension means it cannot be solved
directly, nor do the tractable properties one expects of a convex optimization
problem necessarily follow. For example, in any finite dimensional convex
optimization problem, a symmetry in the problem leads to the same symmetry in
the solution. In this problem, one can see that shifting the mechanism—i.e.,
given $P_{Y|X}$, construct $Q_{Y|X=x}(B)=P_{Y|X=x+z}(B+z)$ for some $z$—does
not change the cost constraint nor the objective value in (6). Thus, one might
be inclined to conclude that the optimal mechanism is invariant to a shift
(i.e., is an additive mechanism). Unfortunately, the infinite-dimensional
nature of the problem means that this conclusion is not immediate. We resolve
this issue in the following theorem which states that additive mechanisms are
in fact optimal in (6).

######  Theorem 1.

We have that

$\textup{KL}^{\star}=\textup{KL}_{\textup{add}}^{\star},$ (11)

and there exists a $P^{\star}\in\mathscr{P}_{\textup{add}}$ achieving this
value. Further, any such $P^{\star}$ is necessarily absolutely continuous.

###### Proof sketch.

The proof is given in Appendix A. We give here only a high level description
of the approach. Let $P_{Y|X}^{(k)}$ be a sequence achieving
$\text{KL}^{\star}$. We make these mechanisms increasingly closer to being
additive, while sacrificing neither feasibility nor utility, by considering
the convex combinations

$\overline{P}_{Y|X=x}^{(k)}(B):=\mathbb{E}\left[P_{Y|X=x+Z_{k}}^{(k)}(B+Z_{k})\right]$
(12)

where $Z_{k}\sim\mathrm{Unif}([-k,k])$. Specifically, one can invoke
Prokhorov’s theorem on the $\overline{P}_{Y|X}^{(k)}$, thereby extracting a
probability measure $P^{\star}$ such that $\overline{P}_{Y|X=x}^{(k)}\to
T_{x}P^{\star}$ weakly for each fixed $x$. Finally, we show that the mechanism
$P^{\star}$ is optimal by invoking joint convexity and lower-semicontinuity of
the KL-divergence. ∎

######  Remark 1.

The proof of $P^{\star}\ll\lambda$ only relies on the property that
$P^{\star}\ll T_{a}P^{\star}$ for every $|a|\leq s$, which holds in view of
$\text{KL}^{\star}<\infty$. Therefore, any _feasible_ additive mechanism must
be absolutely continuous with respect to the Lebesgue measure, i.e., if
$\mu\in\mathscr{B}$ satisfies $\sup_{|a|\leq s}D(\mu\|T_{a}\mu)<\infty$ then
we necessarily have $\mu\ll\lambda$.

##  3 Numerical Approximation: The Cactus Distribution

The optimization problem over additive mechanisms in (10) is infinite-
dimensional, so it cannot be solved numerically as-is, and it appears to have
no closed-form solution for non-trivial cost functions. The lack of closed-
form solution is true even for the simple case of $c(x)=x^{2}$: to our
surprise, as will be illustrated later, the Gaussian mechanism is not
optimal!222Of course, simply because Gaussian is not optimal does not imply
that there is no closed-form solution. It is possible to write a set of KKT
conditions for (10), which we have omitted from this paper in the interest of
space. This set of KKT conditions cannot be solved in closed-form. In our
companion paper [1], we explore the regime where $s\to 0^{+}$; in this limit,
we show that the optimal distribution can be determined exactly, and in fact
for quadratic cost the limiting optimal distribution _is_ Gaussian—although
for other costs the optimal distribution is much more surprising.

In the regime of fixed positive $s$, to find practically achievable near-
optimal mechanisms, we resort to numerical approximation of (10). In this
section, we fix $s=1$. We can do this without loss of generality simply by
scaling: that is, the optimization problem in (10) with sensitivity $s$ and
cost function $c(x)$ is equivalent to the same problem with sensitivity $1$
and cost function $c(sx)$.

To approximate (10) by a numerically tractable problem, we (i) quantize the
distribution, and (ii) only explicitly parameterize the distribution in a
certain interval. Specifically, we construct a mapping from finite-length
vectors to continuous distributions as follows.

######  Definition 1.

Fix two positive integers $n$ and $N$, and a constant $r\in(0,1)$. Consider
the partition of $\mathbb{R}$ by intervals
$\\{\mathcal{J}_{n,i}\\}_{i\in\mathbb{Z}}$ defined by:
$\mathcal{J}_{n,0}:=[-1/(2n),1/(2n)]$ and

$\mathcal{J}_{n,i}:=\left\\{\begin{array}[]{cl}\left(\frac{i-1/2}{n},\frac{i+1/2}{n}\right],&\text{if
}i>0,\vspace{1mm}\\\ \left[\frac{i-1/2}{n},\frac{i+1/2}{n}\right),&\text{if
}i<0.\end{array}\right.$ (13)

We associate to each vector $\bm{p}=(p_{0},p_{1},\ldots,p_{N})\in[0,1]^{N+1}$
a piecewise constant function that is defined by

$f_{n,r,\bm{p}}(x)=\begin{cases}np_{|i|},&\text{if
}x\in\mathcal{J}_{n,i},\text{with }|i|<N,\\\ np_{N}r^{|i|-N},&\text{if
}x\in\mathcal{J}_{n,i},\text{with }|i|\geq N.\end{cases}$ (14)

We also associate with $f_{n,r,\bm{p}}$ the Borel measure $P_{n,r,\bm{p}}$,
where

$P_{n,r,\bm{p}}(B):=\int_{B}f_{n,r,\bm{p}}(x)\,dx.$ (15)

######  Remark 2.

Note that

$\int_{\mathbb{R}}f_{n,r,\bm{p}}(x)\,dx=p_{0}+\sum_{i=1}^{N-1}2p_{i}+\frac{2p_{N}}{1-r}=:S_{r,\bm{p}}.$
(16)

If $S_{r,\bm{p}}=1,$ then $P_{n,r,\bm{p}}$ is a probability measure with
density $f_{n,r,\bm{p}}$. This distribution is symmetric around the origin,
i.e., $f_{n,r,\bm{p}}(x)=f_{n,r,\bm{p}}(-x)$. Further, its tails decay almost
geometrically: for $(N+1/2)/n<x_{1}<x_{2}$ one has
$f_{n,r,\bm{p}}(x_{2})=r^{nk}\cdot f_{n,r,\bm{p}}(x_{1})$ where
$k=\left(\lceil nx_{2}-1/2\rceil-\lceil nx_{1}-1/2\rceil\right)/n\approx
x_{2}-x_{1}$.

The main results of this section are: we show that the distribution family
introduced in Definition 1 is optimal for (6), and we show that the optimal
distribution _within_ this family (which we will call the _cactus
distribution_) is obtainable via a tractable finite-dimensional convex
optimization problem.

We use the following notation. Consider the restriction of (10) to the
mechanisms constructible by Definition 1. For a fixed triplet
$(n,N,r)\in\mathbb{N}^{2}\times(0,1)$, consider the set of mechanisms
$\mathscr{C}_{n,N,r}\subset\mathscr{B}$,

$\mathscr{C}_{n,N,r}:=\left\\{P_{n,r,\bm{p}}~{};~{}\bm{p}\in[0,1]^{N+1},S_{r,\bm{p}}=1\right\\}.$
(17)

(Recall the definition of $S_{r,\bm{p}}$ from (16).) Denote the optimal value
achievable by the class $\mathscr{C}_{n,N,r}$ by

$\text{KL}^{\star}_{n,N,r}(C):=\inf_{\begin{subarray}{c}P\in\mathscr{C}_{n,N,r}\\\
\mathbb{E}_{P}[c]\leq C\end{subarray}}~{}\sup_{|a|\leq 1}D(P\|T_{a}P).$ (18)

We show next that we may restrict the shift $a$ in (18) to take values over
the finite set $\\{1/n,2/n,\cdots,1\\}$ (rather than varying over the whole
interval $[-1,1]$), thereby rendering (18) a finite-dimensional optimization
problem amenable to standard numerical convex-programming methods.

For each $i\in\mathbb{Z},$ we denote the constants

$c_{n,i}:=\int_{\mathcal{J}_{n,i}}nc(x)\,dx.$ (19)

######  Theorem 2.

Fix $r\in(0,1)$, and positive integers $n<N$. The minimization (18) can be
recast as the following convex program over the variable
$\bm{p}=(p_{0},\cdots,p_{N})\in\mathbb{R}^{N+1}$

$\displaystyle\underset{\bm{p}}{\textup{minimize}}$
$\displaystyle\displaystyle\max_{k\in\\{1,\ldots,n\\}}\
\frac{1}{2}\sum_{i=-N+1}^{N-k-1}(p_{|i|}-p_{|i+k|})\log\frac{p_{|i|}}{p_{|i+k|}}+\sum_{i=N-k}^{N-1}(p_{i}-p_{N}r^{i+k-N})\log\frac{p_{i}}{p_{N}r^{i+k-N}}$
$\displaystyle\displaystyle\qquad+p_{N}\frac{1-r^{k}}{1-r}k\log r^{-1}$
subject to $\displaystyle\displaystyle
p_{0}c_{n,0}+\sum_{i=1}^{N-1}2p_{i}c_{n,i}+2p_{N}\sum_{i=N}^{\infty}c_{n,i}r^{i-N}\leq
C,$ $\displaystyle\displaystyle
p_{0}+\sum_{i=1}^{N-1}2p_{i}+\frac{2p_{N}}{1-r}=1,$
$\displaystyle\displaystyle p_{i}\geq 0\textup{ for all
}i\in\\{0,\ldots,N\\}.$ (20)

###### Proof.

See Appendix B. ∎

Figure 1 shows an example of the distribution that results from the finite-
dimensional optimization problem in (20) with a quadratic cost. The shape of
this distribution333In addition to the state of Arizona being home of several
of the authors. has inspired the name the “cactus distribution.” The following
result shows that cactus mechanisms derived from the optimization problem (20)
are in fact globally optimal for the main optimization problem (6).

######  Theorem 3.

Denote the optimal value a cactus distribution can achieve by

$\textup{KL}_{\textup{Cactus}}^{\star}:=\lim_{\varepsilon\to
0^{+}}\inf_{(n,N,r)\in\mathbb{N}^{2}\times(0,1)}\textup{KL}_{n,N,r}^{\star}(C+\varepsilon).$
(21)

We have that $\textup{KL}^{\star}=\textup{KL}_{\textup{Cactus}}^{\star}$.

###### Proof.

See Appendix C. ∎

######  Remark 3.

The proof of Theorem 3 gives some guidelines for choosing the parameters
$(n,N,r)$. For example, optimal cactus distributions can be obtained by
restricting the ratio $N/n$ (chosen sufficiently large), and choosing
$r=1-\Theta_{\alpha}(N^{-1})$.

Fig. 1: The optimal distribution $p(z)$, found by solving (20) (and dubbed the
_cactus distribution_), plotted on a semi-log scale. The cost function is
$c(z)=z^{2}$, and the parameters are: $s=1$, $C=0.25$, $n=200$, $N=1600$, and
$r=0.9$.

##  4 Numerical Results

We solve the optimization problem (20) using an interior-point method. An
example of the cactus distribution for quadratic cost is shown in Figure 1.
Figure 2 compares the maximal KL-divergence achieved by the cactus to that of
Gaussian distributions for fixed sensitivity $s=1$ and various $\sigma$. As
noted above, varying $\sigma$ with fixed $s$ is equivalent to varying $s$ with
fixed $\sigma$. The KL-divergence for cactus is computed numerically, and for
Gaussian mechanisms the KL-divergence is exactly $\frac{1}{2\sigma^{2}}$. The
cactus distribution outperforms the Gaussian distribution in terms of KL-
divergence for all values of $\sigma$, although the difference decreases as
$\sigma$ grows such that for larger values of $\sigma$ it is difficult to
discern any gap between the curves in Figure 2. (Our companion paper [1] gives
a theoretical explanation for why Gaussian is so close to optimal as
$s/\sigma$ decreases.) To illustrate that this improvement in KL-divergence
leads to an improvement in $(\varepsilon,\delta)$-DP, we compute the achieved
privacy via moments accountant [17] for each mechanism. Figure 3 shows the
resulting $\varepsilon$ value as a function of the number of compositions, for
fixed $\delta=10^{-3}$. Indeed, the cactus mechanism does better than
Gaussian.

To give a reasonable comparison in the context of machine learning, we
modified the tutorial code in TensorFlow-Privacy [26], which implements the
DP-stochastic gradient descent (SGD) algorithm with a Gaussian mechanism on a
convolutional neural network (CNN) model. We use the training results from the
original tutorial as a benchmark, then replace the Gaussian mechanism with our
cactus mechanism, and train the model using the renewed setting. We select a
noise level $\sigma=\sqrt{0.1}$. We test the original and modified model on a
popular image dataset, MNIST, which is of size $60000$. We choose a batch-size
$250$, such that each epoch consists of $240$ iterations (i.e., compositions)
and the sub-sampling rate444The cactus mechanism is not optimized for
subsampling. Nevertheless, we observe numerical performance of the cactus
mechanism in the subsampling setting outperforming that of the Gaussian
mechanism. is $q=250/60000\approx 0.00417$. Figure 4 shows the achieved
$(\varepsilon,\delta)$-DP as computed by the moments account in this setting.
Fixing $\delta=10^{-5}$, Figure 5 shows the tradeoff between privacy
$\varepsilon$ and accuracy of the resulting CNN as the number of training
iterations increases. One can see that for a fixed privacy budget (i.e., fixed
$\varepsilon$ and $\delta$), the cactus mechanism allows more training
iterations and, thus, better accuracy.

Fig. 2: Achieved maximal KL-divergence $\sup_{|a|\leq s}D(p\|T_{a}p)$ versus
$\sigma$, the (quadratic) cost constraint is of the form
$\mathbb{E}[Z^{2}]\leq\sigma^{2}=C$ with fixed sensitivity $s=1$. Fig. 3:
Privacy parameter $\varepsilon$ versus the number of compositions, computed
via the moments accountant, where $\delta=10^{-3}$, and quadratic cost $C=0.1$
with fixed sensitivity $s=1$. Fig. 4: Privacy parameter $\varepsilon$ versus
the number of compositions, computed via the moments accountant, where
$\delta=10^{-5}$, subsampling rate $q\approx 0.00417$, and quadratic cost
$C=0.1$ with fixed sensitivity $s=1$. Fig. 5: Model accuracy versus privacy
parameter $\varepsilon$. The settings are the same as in Figure 4 and
experiment details are given in Section 4.

##  Appendix A Proof of Theorem 1: Optimality of Additive Continuous Channels

Let $F:\mathscr{R}\to[0,\infty]$ denote the objective function in (6), i.e.,

$F(P_{Y|X}):=\sup_{|u-v|\leq s}~{}D(P_{Y|X=u}\|P_{Y|X=v}).$ (22)

Thus,

$\text{KL}^{\star}=\inf_{P_{Y|X}\in\mathscr{P}}~{}F(P_{Y|X}).$ (23)

Fix a sequence of conditional distributions

$\left\\{P_{Y|X}^{(k)}\right\\}_{k\in\mathbb{N}}\subset\mathscr{P}$ (24)

satisfying

$\text{KL}^{\star}=\lim_{k\to\infty}F\left(P_{Y|X}^{(k)}\right).$ (25)

Recall that by assumption, the version of each conditional distribution
$P_{Y|X}^{(k)}$ we choose is regular, i.e., $x\mapsto P_{Y|X=x}^{(k)}(B)$ is a
Borel function for each Borel set $B\subset\mathbb{R}$. Note that
$\text{KL}^{\star}<\infty$ since, e.g., the Gaussian mechanism is feasible.
Throwing away the first few elements in the sequence, we assume that
$F\left(P_{Y|X}^{(k)}\right)<\infty$ for each $k\in\mathbb{N}$.

We break the proof down into several steps:

  1. 1.

Introduce Markov kernels $\overline{P}_{Y|X}^{(k)}$ as “continuous” convex
combinations of the $P_{Y|X}^{(k)}$.

  2. 2.

The $\overline{P}_{Y|X}^{(k)}$ also satisfy the cost constraint.

  3. 3.

The $\overline{P}_{Y|X}^{(k)}$ asymptotically achieve $\text{KL}^{\star}$.

  4. 4.

The $\overline{P}_{Y|X=x}^{(k)}$ are asymptotically shifted versions
$T_{x}P^{\star}$ of a fixed $P^{\star}\in\mathscr{B}$.

  5. 5.

$P^{\star}$ achieves $\text{KL}^{\star}$.

$\bullet$ _Step 1_ : Averaging the $P_{Y|X}^{(k)}$.

For $k\in\mathbb{N}$, we will define the Markov kernel
$\overline{P}_{Y|X}^{(k)}\in\mathscr{R}$ by

$\overline{P}_{Y|X=x}^{(k)}(B):=\frac{1}{2k}\int_{-k}^{k}P^{(k)}_{Y|X=x+z}(B+z)\,dz.$
(26)

Of course, we need to check that (26) indeed yields a Markov kernel
$\overline{P}_{Y|X}^{(k)}$. In view of Fubini’s theorem, it suffices to check
that the map $(x,z)\mapsto P^{(k)}_{Y|X=x+z}(B+z)$ is jointly Borel (for every
fixed Borel set $B\subset\mathbb{R}$). This joint measurability is not self-
evident, so we check next that it indeed holds.

Let the transition probability kernel
$L^{(k)}:\mathbb{R}^{2}\times\mathcal{B}(\mathbb{R})\to[0,1]$ be defined by

$L^{(k)}((x,z),A):=P_{Y|X=x+z}^{(k)}(A).$ (27)

Let $N^{(k)}:\mathbb{R}^{2}\times\mathcal{B}(\mathbb{R})\to[0,1]$ denote the
map

$N^{(k)}((x,z),B):=P^{(k)}_{Y|X=x+z}(B+z).$ (28)

For each $(x,z)\in\mathbb{R}^{2}$ and Borel set $B\subset\mathbb{R}$, we may
write $N^{(k)}((x,z),B)$ as the integral of a nonnegative Borel function
against $L((x,z),dy)$, namely,

$N^{(k)}((x,z),B)=\int_{\mathbb{R}}1_{B}(y-z)\,L((x,z),dy).$ (29)

Hence (see, e.g., [25, Chapter 1, Proposition 6.9]) $(x,z)\mapsto
N^{(k)}((x,z),B)$ is a Borel function. Hence, $\overline{P}_{Y|X}^{(k)}$ as
given by (26) is indeed a well-defined Markov kernel on $\mathbb{R}$.

For the next steps, we will use the following notation

$\displaystyle R^{(k,x)}_{Y|X=z}(B)$ $\displaystyle:=P_{Y|X=x+z}^{(k)}(B+z),$
(30) $\displaystyle P^{(k,x)}(B)$
$\displaystyle:=\overline{P}_{Y|X=x}^{(k)}(B),$ (31) $\displaystyle
U^{(k)}(B)$ $\displaystyle:=\frac{1}{2k}\cdot\lambda(B\cap[-k,k]).$ (32)

Note that $R^{(k,x)}_{Y|X}\in\mathscr{R}$ and $P^{(k,x)}\in\mathscr{B}$ for
each fixed $(k,x)\in\mathbb{N}\times\mathbb{R}$, and (26) may be rewritten as

$P^{(k,x)}=R_{Y|X}^{(k,x)}\circ U^{(k)}.$ (33)

$\bullet$ _Step 2_ : The $\overline{P}_{Y|X}^{(k)}$ satisfy the cost
constraint.

Fix $k\in\mathbb{N}$, and we will show next that
$\overline{P}_{Y|X}^{(k)}\in\mathscr{P}$, i.e., that
$\overline{P}_{Y|X}^{(k)}$ satisfies the cost constraint. Recall that a Markov
kernel $P_{Y|X}\in\mathscr{R}$ belongs to $\mathscr{P}$ if and only if it
satisfies

$\sup_{x\in\mathbb{R}}~{}\mathbb{E}_{P_{Y|X=x}}\left[T_{x}c\right]\leq C.$
(34)

By the assumption that $P_{Y|X}^{(k)}\in\mathscr{P}$, we have that

$\mathbb{E}_{P_{Y|X=x}^{(k)}}\left[T_{x}c\right]\leq C$ (35)

for every $x\in\mathbb{R}$. Shifting the variable of integration in (35) by a
fixed constant $-z$, we obtain that

$\mathbb{E}_{T_{-z}P_{Y|X=x}^{(k)}}\left[T_{x-z}c\right]\leq C$ (36)

for every $(x,z)\in\mathbb{R}^{2}$. Replacing $x$ by $x+z$ in (36), we
conclude that (see (30))

$\mathbb{E}_{R^{(k,x)}_{Y|X=z}}\left[T_{x}c\right]\leq C$ (37)

for every $(x,z)\in\mathbb{R}^{2}$. We proceed via the following standard
approximation by simple functions argument.

Fix $x\in\mathbb{R}$, and let $\sum_{j}a_{j}1_{B_{j}}(y)$ be a nonnegative
simple function upper bounded by $(T_{x}c)(y)$. Integrating against
$R^{(k,x)}_{Y|X=z}(dy)$ we deduce from (37) that

$\sum_{j}a_{j}R^{(k,x)}_{Y|X=z}(B_{j})\leq C$ (38)

for every $z\in\mathbb{R}$. Integrating (38) against $U^{(k)}(dz)$, and noting
that $P^{(k,x)}=R^{(k,x)}_{Y|X}\circ U^{(k)}$ (see (33)), we deduce that

$\sum_{j}a_{j}P^{(k,x)}(B_{j})\leq C.$ (39)

Now, as (39) holds for all nonnegative simple functions below $T_{x}c$, taking
an increasing sequence of nonnegative simple function converging pointwise to
$T_{x}c$ we conclude that

$\mathbb{E}_{P^{(k,x)}}[T_{x}c]\leq C.$ (40)

In other words (see (31)),

$\mathbb{E}_{\overline{P}_{Y|X=x}^{(k)}}[T_{x}c]\leq C.$ (41)

As (41) holds for all $x\in\mathbb{R}$, we have shown that
$\overline{P}_{Y|X}^{(k)}\in\mathscr{P}$.

$\bullet$ _Step 3_ : The $\overline{P}_{Y|X}^{(k)}$ are asymptotically
optimal.

Next, we use monotonicity of the KL-divergence under conditioning (see Lemma
1) to show the limit

$\text{KL}^{\star}=\lim_{k\to\infty}F\left(\overline{P}_{Y|X}^{(k)}\right).$
(42)

Shift-invariance of the KL-divergence implies that, for each
$x,x^{\prime},z\in\mathbb{R}$,

$D\left(R_{Y|X=z}^{(k,x)}\|R_{Y|X=z}^{(k,x^{\prime})}\right)=D\left(P_{Y|X=x+z}^{(k)}\|P_{Y|X=x^{\prime}+z}^{(k)}\right).$
(43)

Thus, as $(x+z)-(x^{\prime}+z)=x-x^{\prime}$, we conclude that

$\sup_{\begin{subarray}{c}|x-x^{\prime}|\leq s\\\
z\in\mathbb{R}\end{subarray}}D\left(R_{Y|X=z}^{(k,x)}\|R_{Y|X=z}^{(k,x^{\prime})}\right)=F\left(P_{Y|X}^{(k)}\right)$
(44)

By assumption of optimality of the $P_{Y|X}^{(k)}$ (see (25)), there exists a
$k_{0}$ such that for all $k\geq k_{0}$,

$\sup_{\begin{subarray}{c}|x-x^{\prime}|\leq s\\\
z\in\mathbb{R}\end{subarray}}D\left(R_{Y|X=z}^{(k,x)}\|R_{Y|X=z}^{(k,x^{\prime})}\right)\leq\text{KL}^{\star}+\delta.$
(45)

By definition of KL-divergence, we infer $R_{Y|X=z}^{(k,x)}\ll
R_{Y|X=z}^{(k,x^{\prime})}$ for all $z\in\mathbb{R}$ and $|x-x^{\prime}|\leq
s$. Also, (45) shows in particular that

$\sup_{|x-x^{\prime}|\leq s}\mathbb{E}_{\xi\sim
U^{(k)}}\left[D\left(R_{Y|X=\xi}^{(k,x)}\|R_{Y|X=\xi}^{(k,x^{\prime})}\right)\right]\leq\text{KL}^{\star}+\delta.$
(46)

Using (33), Lemma 1 yields that

$\sup_{|x-x^{\prime}|\leq
s}D\left(P^{(k,x)}\|P^{(k,x^{\prime})}\right)\leq\text{KL}^{\star}+\delta.$
(47)

Taking $\delta\to 0^{+}$, we see that (42) holds.

$\bullet$ _Step 4_ : $P^{(k,x)}$ is asymptotically $T_{x}P^{\star}$ for a
fixed $P^{\star}$.

Next, we show that there is a measure $P^{\star}\in\mathscr{B}$ such that, for
every $x\in\mathbb{R}$, we have the weak convergence

$P^{(k,x)}\to T_{x}P^{\star}$ (48)

as $k\to\infty$.

First, for each fixed $x\in\mathbb{R}$, we establish the total-variation
distance convergence

$\lim_{k\to\infty}\left\|P^{(k,x)}-T_{x}P^{(k,0)}\right\|_{\text{TV}}=0.$ (49)

We may write

$\left(T_{x}P^{(k,0)}\right)(B)=\frac{1}{2k}\int_{-k-x}^{k-x}R_{Y|X=z}^{(k,x)}(B)\,dz.$
(50)

Therefore, for any Borel set $B\subset\mathbb{R}$ we have that

$\displaystyle\left|P^{(k,x)}(B)-T_{x}P^{(k,0)}(B)\right|\leq\frac{1}{2k}\int_{[-k,k]\Delta[-k-x,k-x]}R_{Y|X=z}^{(k,x)}(B)\,dz\leq\frac{|x|}{k},$
(51)

where $\Delta$ denotes the symmetric difference. As the bound (51) is uniform
in $B$, we conclude that the total-variation limit in (49) holds.

The next ingredient we need is that the set
$\\{P^{(k,0)}\\}_{k\in\mathbb{N}}\subset\mathscr{B}$ is tight, i.e., that for
any $\varepsilon>0$ there exists an $n>0$ such that

$\sup_{k\in\mathbb{N}}~{}P^{(k,0)}(\mathbb{R}\setminus[-n,n])\leq\varepsilon.$
(52)

Fix $\varepsilon>0$. By the assumption that $c(x)\sim\beta|x|^{\alpha}$ where
$\alpha,\beta>0$, we have $\lim_{|x|\to\infty}c(x)=\infty$. Thus there exists
an integer $n$ such that $c(x)\geq C/\varepsilon$ whenever $|x|\geq n.$ Then,
for each $(z,k)\in\mathbb{R}\times\mathbb{N}$,

$\displaystyle R_{Y|X=z}^{(k,0)}\left(\mathbb{R}\setminus[-n,n]\right)$
$\displaystyle=P_{Y|X=z}^{(k)}\left(\mathbb{R}\setminus[-n+z,n+z]\right)$ (53)
$\displaystyle\leq\int_{\mathbb{R}\setminus[-n+z,n+z]}\frac{c(y-z)}{c(n)}\,dP_{Y|X=z}^{(k)}(y)$
(54) $\displaystyle\leq c(n)^{-1}\mathbb{E}_{P_{Y|X=z}^{(k)}}[T_{z}c]$ (55)
$\displaystyle\leq c(n)^{-1}\cdot C$ (56) $\displaystyle\leq\varepsilon,$ (57)

where (54) follows by monotonicity of $c$, (55) by nonnegativity of $c$, and
(56) since $P_{Y|X}^{(k)}\in\mathscr{P}$. Hence,

$\sup_{(z,k)\in\mathbb{R}\times\mathbb{N}}~{}R_{Y|X=z}^{(k,0)}\left(\mathbb{R}\setminus[-n,n]\right)\leq\varepsilon.$
(58)

Averaging over $z$, we deduce that (52) holds, i.e., that
$\\{P^{(k,0)}\\}_{k\in\mathbb{N}}$ is tight.

By tightness of $\\{P^{(k,0)}\\}_{k\in\mathbb{N}}$, we conclude via
Prokhorov’s theorem [25, Chapter 3, Theorem 5.13] after passing to a
subsequence that there is a $P^{\star}\in\mathscr{B}$ such that $P^{(k,0)}\to
P^{\star}$ weakly as $k\to\infty$, i.e., for every continuous and bounded
function $f:\mathbb{R}\to\mathbb{R}$ we have

$\lim_{k\to\infty}\mathbb{E}_{P^{(k,0)}}[f]=\mathbb{E}_{P^{\star}}[f].$ (59)

This immediately implies that, for each $x\in\mathbb{R}$, we also have

$T_{x}P^{(k,0)}\to T_{x}P^{\star}$ (60)

weakly as $k\to\infty$. As convergence in total variation is stronger than
weak convergence, we conclude from (49) and (60) that for every
$x\in\mathbb{R}$

$P^{(k,x)}\to T_{x}P^{\star}$ (61)

weakly as $k\to\infty$.

$\bullet$ _Step 5_ : The additive mechanism $P^{\star}$ is optimal.

The final step is showing that $P^{\star}$ attains $\text{KL}^{\star}$ and
satisfies the cost constraint. By joint lower-semicontinuity of the KL-
divergence [27, Theorem 1], we deduce from (61) that for each $x\in\mathbb{R}$

$D(P^{\star}\|T_{x}P^{\star})\leq\liminf_{k\to\infty}D\left(P^{(k,0)}\|P^{(k,x)}\right).$
(62)

But we also have

$\sup_{|x|\leq s}D\left(P^{(k,0)}\|P^{(k,x)}\right)\leq
F\left(\overline{P}_{Y|X}^{(k)}\right).$ (63)

Therefore, taking the supremum over $|x|\leq s$ in (62), we infer from (42)
that

$\sup_{|x|\leq s}D(P^{\star}\|T_{x}P^{\star})\leq\text{KL}^{\star}.$ (64)

Hence, it only remains to check that $P^{\star}\in\mathscr{P}_{\text{add}}$
for us to conclude that equality holds in (64).

For every $A>0$ and $x\in\mathbb{R}$, the function $1_{[-A,A]}\cdot T_{x}c$ is
continuous and bounded. Hence, the weak convergence $P^{(k,x)}\to
T_{x}P^{\star}$ yields

$\mathbb{E}_{T_{x}P^{\star}}\left[1_{[-A,A]}\cdot
T_{x}c\right]=\lim_{k\to\infty}\mathbb{E}_{P^{(k,x)}}\left[1_{[-A,A]}\cdot
T_{x}c\right].$ (65)

As $\overline{P}_{Y|X}^{(k)}\in\mathscr{P}$, nonnegativity of $c$ implies in
view of (65) that

$\mathbb{E}_{T_{x}P^{\star}}\left[1_{[-A,A]}\cdot T_{x}c\right]\leq C.$ (66)

By the monotone convergence theorem, taking $A\to\infty$ yields

$\mathbb{E}_{T_{x}P^{\star}}\left[T_{x}c\right]\leq C,$ (67)

In other words, $P^{\star}\in\mathscr{P}_{\text{add}}$. Therefore, we must
have

$\text{KL}^{\star}\leq\text{KL}_{\text{add}}^{\star}\leq\sup_{|x|\leq
s}~{}D(P^{\star}\|T_{x}P^{\star}).$ (68)

Combining this inequality with (64), we conclude that

$\text{KL}^{\star}=\text{KL}_{\text{add}}^{\star}=\sup_{|x|\leq
s}~{}D(P^{\star}\|T_{x}P^{\star}).$ (69)

This completes the proof of the first statement of the theorem.

For the last statement of the theorem, we show that the relation $\mu\ll
T_{x}\mu$ for every $|x|\leq s$ (which holds for $P^{\star}$ by (69) and
$\text{KL}^{\star}<\infty$) is enough to conclude that $\mu\ll\lambda$. Fix a
Borel set $B\subset\mathbb{R}$ such that $\lambda(B)=0$, and we will show that
$\mu(B)=0$. Note that the function $x\mapsto(T_{x}\mu)(B)$ is Borel as it is
given by the convolution $1_{B}\ast\eta$ where $\eta(A):=\mu(-A)$. Then, by
Tonelli’s theorem and translation-invariance of the Lebesgue measure,

$\displaystyle\int_{\mathbb{R}}(T_{x}\mu)(B)\,d\lambda(x)$
$\displaystyle=\int_{\mathbb{R}^{2}}1_{B-x}(b)\,d\mu(b)\,d\lambda(x)$ (70)
$\displaystyle=\int_{\mathbb{R}^{2}}1_{B-x}(b)\,d\lambda(x)\,d\mu(b)$ (71)
$\displaystyle=\int_{\mathbb{R}^{2}}1_{B-b}(x)\,d\lambda(x)\,d\mu(b)$ (72)
$\displaystyle=\int_{\mathbb{R}}(T_{b}\lambda)(B)\,d\mu(b)$ (73)
$\displaystyle=\int_{\mathbb{R}}\lambda(B)\,d\mu(b)=0.$ (74)

Thus, $(T_{x}\mu)(B)=0$ for $\lambda$-almost every $x$. In particular,
$(T_{x}\mu)(B)=0$ for at least one $x\in[-s,s]$. Thus, $\mu\ll T_{x}\mu$
implies $\mu(B)=0$, and the proof is complete.

######  Remark 4.

The lemma stated below, showing that conditioning increases divergence, is a
well-known fact. It is shown in the literature under various assumptions on
the underlying distributions (see, e.g., [28, Theorem 2.2 and Section 2.6]).
We use it in the proof of Theorem 1 in the specific situation where one of the
conditional distributions is absolutely continuous with respect to the other
for each individual input. As in [28, Remark 2.4], Doob’s version of the
Radon-Nikodym theorem can be used to derive that conditioning increases
divergence in our case. For completeness, we add a proof of this lemma here.

######  Lemma 1 (Conditioning increases divergence).

Let $P_{Y|X},P_{Y|X}^{\prime}$ be Markov kernels on $\mathbb{R}$ such that
$P_{Y|X=x}\ll P_{Y|X=x}^{\prime}$ for every $x\in\mathbb{R}$. Then, denoting
the marginalizations of $P_{X,Y}:=P_{Y|X}\otimes
P_{X},P_{X,Y}^{\prime}:=P_{Y|X}^{\prime}\otimes P_{X}$ in the second
coordinate by $P_{Y},P_{Y}^{\prime}$, we have that

$D\left(P_{Y}\|P_{Y}^{\prime}\right)\leq\mathbb{E}_{\xi\sim
P_{X}}\left[D\left(P_{Y|X=\xi}\|P_{Y|X=\xi}^{\prime}\right)\right].$ (75)

###### Proof.

Since by assumption $P_{Y|X=x}\ll P_{Y|X=x}^{\prime}$ for every
$x\in\mathbb{R}$, a generalization of the Radon-Nikodym theorem by Doob (see
[25, Chapter 5, Theorem 4.44]) yields the existence of a version of the Radon-
Nikodym derivatives $dP_{Y|X=x}/dP_{Y|X=x}^{\prime}$ such that the function

$(x,y)\mapsto\frac{dP_{Y|X=x}}{dP_{Y|X=x}^{\prime}}(y)$ (76)

is jointly measurable. We show that this function is a version of
$dP_{X,Y}/dP_{X,Y}^{\prime}$. First, note that $P_{X,Y}\ll P_{X,Y}^{\prime}$
are equivalent. Indeed, for any Borel set $E\subset\mathbb{R}$, denoting the
sections by $E_{x}:=\\{y\in\mathbb{R}~{};~{}(x,y)\in E\\}$, we have that
$P_{X,Y}(E)=0$ if and only if $P_{Y|X=x}(E_{x})=0$ for $P_{X}$-a.e. $x$, and a
similar statement holds for $P_{X,Y}^{\prime}$. By assumption, $P_{Y|X=x}\ll
P_{Y|X=x}^{\prime}$ for each $x$, so we obtain $P_{X,Y}\ll P_{X,Y}^{\prime}$.
By joint measurability and nonnegativity, using the disintegration theorem
(see, e.g., [25, Chapter 1, Theorem 6.11]) we obtain that for any Borel
$E\subset\mathbb{R}^{2}$

$\displaystyle\int_{E}\frac{dP_{Y|X=x}}{dP_{Y|X=x}^{\prime}}(y)\,dP_{X,Y}^{\prime}(x,y)$
$\displaystyle=\int_{\mathbb{R}}\int_{E_{x}}\frac{dP_{Y|X=x}}{dP_{Y|X=x}^{\prime}}(y)\,dP_{Y|X=x}^{\prime}(y)\,dP_{X}(x)$
(77) $\displaystyle=\int_{\mathbb{R}}\int_{E_{x}}dP_{Y|X=x}(y)\,dP_{X}(x)$
(78) $\displaystyle=P_{X,Y}(E).$ (79)

Thus, we have the equality

$\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}(x,y)=\frac{dP_{Y|X=x}}{dP_{Y|X=x}^{\prime}}(y)$
(80)

for $P_{X,Y}^{\prime}$-a.e. $(x,y)$.

Define $f:[0,\infty)\to[-1/e,\infty)$ by $f(0)=0$ and $f(t)=t\log t$ for
$t>0$. By the disintegration theorem and (80), we have the equality

$\displaystyle D\left(P_{X,Y}\|P_{X,Y}^{\prime}\right)$
$\displaystyle=\int_{\mathbb{R}^{2}}f\left(\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}\right)\,dP_{X,Y}^{\prime}$
(81)
$\displaystyle=\int_{\mathbb{R}}\int_{\mathbb{R}}f\left(\frac{dP_{Y|X=x}}{dP_{Y|X=x}^{\prime}}(y)\right)\,dP_{Y|X=x}^{\prime}\,dP_{X}(x)$
(82) $\displaystyle=\mathbb{E}_{\xi\sim
P_{X}}\left[D\left(P_{Y|X=\xi}\|P_{Y|X=\xi}^{\prime}\right)\right].$ (83)

On the other hand, disintegration with respect to $Y$ yields the following
bound. Denote by $P_{X|Y},P_{X|Y}^{\prime}$ the disintegrations of
$P_{X,Y},P_{X,Y}^{\prime}$ with respect to $P_{Y},P_{Y}^{\prime}$. In
particular, $P_{X|Y}$ and $P_{X|Y}^{\prime}$ are Markov kernels on
$\mathbb{R}$. By the disintegration theorem and Jensen’s inequality,

$\displaystyle D\left(P_{X,Y}\|P_{X,Y}^{\prime}\right)$
$\displaystyle=\int_{\mathbb{R}^{2}}f\left(\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}\right)\,dP_{X,Y}^{\prime}$
(84)
$\displaystyle=\int_{\mathbb{R}}\int_{\mathbb{R}}f\left(\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}(x,y)\right)\,dP_{X|Y=x}^{\prime}(x)\,dP_{Y}^{\prime}(y)$
(85)
$\displaystyle\geq\int_{\mathbb{R}}f\left(g(y)\right)\,dP_{Y}^{\prime}(y)$
(86)

where

$g(y):=\int_{\mathbb{R}}\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}(x,y)\,dP_{X|Y=x}^{\prime}(x).$
(87)

For this application of Jensen’s inequality, we use the fact, shown next, that
$g$ is finite $P_{Y}^{\prime}$-a.e. In fact, we show that $g$ is a version of
$dP_{Y}/dP_{Y}^{\prime}$. Note that $P_{X,Y}\ll P_{X,Y}^{\prime}$ implies that
$P_{Y}\ll P_{Y}^{\prime}$. Now, for any Borel $B\subset\mathbb{R}$, the
disintegration theorem yields that

$\displaystyle\int_{B}g\,dP_{Y}^{\prime}$
$\displaystyle=\int_{B}\int_{\mathbb{R}}\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}(x,y)\,dP_{X|Y=x}^{\prime}(x)\,dP_{Y}^{\prime}(y)$
(88) $\displaystyle=\int_{\mathbb{R}\times
B}\frac{dP_{X,Y}}{dP_{X,Y}^{\prime}}\,dP_{X,Y}^{\prime}$ (89)
$\displaystyle=P_{X,Y}(\mathbb{R}\times B)=P_{Y}(B).$ (90)

Thus, we have that

$g(y)=\frac{dP_{Y}}{dP_{Y}^{\prime}}(y).$ (91)

for $P_{Y}^{\prime}$-a.e. $y$. Hence, we obtain from inequality (86) that

$D\left(P_{X,Y}\|P_{X,Y}^{\prime}\right)\geq
D\left(P_{Y}\|P_{Y}^{\prime}\right).$ (92)

Combining inequality (92) and equation (83) we obtain the desired inequality
(75). ∎

##  Appendix B Proof of Theorem 2: Finite-Dimensionality

Note that the vector $\bm{p}$ only includes $p_{i}$ for $0\leq i\leq N$. We
will simplify our analysis by defining $p_{i}$ for all integers $i$.
Specifically, for $i\in\mathbb{Z}\setminus\\{0,\cdots,N\\}$, we denote

$p_{i}:=\left\\{\begin{array}[]{cl}p_{|i|},&\text{if }-N\leq
i\leq-1,\vspace{2mm}\\\ p_{N}r^{|i|-N},&\text{if }|i|>N.\end{array}\right.$
(93)

Thus we may rewrite the formula for $f_{n,r,\bm{p}}$ in (14) as

$f_{n,r,\bm{p}}(x)=np_{i}\quad\text{ if }x\in\mathcal{J}_{n,i}.$ (94)

We show first that

$\sup_{a\in\mathbb{R}:|a|\leq
1}D(P_{n,r,\bm{p}}\|T_{a}P_{n,r,\bm{p}})=\max_{k\in\mathbb{Z}:|k|\leq
n}\sum_{i\in\mathbb{Z}}p_{i}\log\frac{p_{i}}{p_{i+k}},$ (95)

then we show that this formula is equal to the objective function in (20). For
convenience, we drop the subscripts on $f_{n,r,\bm{p}}$ and $P_{n,r,\bm{p}}$
throughout this proof. We may assume $\bm{p}>\mathbf{0}$, since any vector
$\bm{p}$ with some zero coordinate will be infeasible in both optimization
problems (18) and (20).

Fix $a\in[-1,1]$. For each $i\in\mathbb{Z}$, let
$\mathcal{J}_{n,i}^{\circ}=\left(\frac{i-1/2}{n},\frac{i+1/2}{n}\right)$
denote the interior of $\mathcal{J}_{n,i}$. We start by showing that the
function

$F_{a}:=f\log\frac{f}{T_{-a}f}$ (96)

is integrable, which would allow us to use countable additivity of the
Lebesgue integral to split $D(P\|T_{-a}P)$ into a sum of integrals over the
$\mathcal{J}_{n,i}^{\circ}$. Let $k\in\mathbb{Z}$ be the unique integer such
that $a+\frac{1}{2n}\in\mathcal{J}_{n,k}$, and denote $\Delta:=k-an$. From

$\frac{k-1/2}{n}\leq a+\frac{1}{2n}\leq\frac{k+1/2}{n},$ (97)

we conclude that $0\leq\Delta\leq 1$. Consider an integer $i$ and a real
$x\in\mathcal{J}_{n,i}^{\circ}$. If $x<(i-1/2+\Delta)/n$, then

$x+a=x+\frac{k-\Delta}{n}<\frac{i+k-1/2}{n}=\frac{(i+k-1)+1/2}{n}$ (98)

and, since $\Delta\leq 1$,

$x+a=x+\frac{k-\Delta}{n}>\frac{i-1/2}{n}+\frac{k-1}{n}=\frac{(i+k-1)-1/2}{n}.$
(99)

Inequalities (98) and (99) together imply that
$x+a\in\mathcal{J}_{n,i+k-1}^{\circ}$. Similarly, if $x>(i-1/2+\Delta)/n$ then
$x+a\in\mathcal{J}_{n,i+k}^{\circ}$. We may ignore the countably many cases
$x=(i-1/2+\Delta)/n$ (as $i$ varies over $\mathbb{Z}$) for the sake of
integrating $F_{a}$. We conclude that for every $x\in\mathbb{R}$ such that
$nx-\Delta+\frac{1}{2}$ is not an integer,

$F_{a}(x)=\left\\{\begin{array}[]{cl}np_{i}\log\frac{p_{i}}{p_{i+k-1}},&\text{if
}~{}x\in\mathcal{J}_{n,i},~{}~{}x<\frac{i-1/2+\Delta}{n},\\\
np_{i}\log\frac{p_{i}}{p_{i+k}},&\text{if
}~{}x\in\mathcal{J}_{n,i},~{}~{}x>\frac{i-1/2+\Delta}{n}.\end{array}\right.$
(100)

Since
$\int_{\mathbb{R}}|F_{a}|=\sum_{i\in\mathbb{Z}}\int_{\mathcal{J}_{n,i}^{\circ}}|F_{a}|$,
we obtain

$\int_{\mathbb{R}}|F_{a}|=\sum_{i\in\mathbb{Z}}p_{i}\left(\Delta\left|\log\frac{p_{i}}{p_{i+k-1}}\right|+(1-\Delta)\left|\log\frac{p_{i}}{p_{i+k}}\right|\right).$
(101)

Now, we may conclude that $F_{a}\in L^{1}(\mathbb{R})$ by comparison with a
geometric series. Indeed, we show the convergence of the series

$S_{\ell}:=\sum_{i\in\mathbb{Z}}p_{i}\left|\log\frac{p_{i}}{p_{i+\ell}}\right|$
(102)

for each fixed $\ell\in\mathbb{Z}$. Consider the set of indices

$I=\mathbb{Z}\setminus\\{-N-|\ell|,\cdots,N+|\ell|\\},$ (103)

and note that for each $i\in I$ we have $p_{i+j}=p_{N}r^{|i+j|-N}$ for both
values $j\in\\{0,\ell\\}$. In particular, for $i\in I$ we have that

$\left|\log\frac{p_{i}}{p_{i+\ell}}\right|=\left||i|-|i+\ell|\right|\cdot\log\frac{1}{r}\leq|\ell|\cdot\log\frac{1}{r}.$
(104)

Therefore, we obtain the bound

$S_{\ell}\leq\frac{|\ell|p_{N}\log\frac{1}{r}}{r^{N}}\cdot\frac{1+r}{1-r}+\sum_{|i|\leq
N+|\ell|}p_{i}\left|\log\frac{p_{i}}{p_{i+\ell}}\right|<\infty.$ (105)

As $S_{k}$ and $S_{k-1}$ are both finite, we conclude from (101) that
$F_{a}\in L^{1}(\mathbb{R})$. Therefore, by countable additivity,

$D(P\|T_{-a}P)=\sum_{i\in\mathbb{Z}}\int_{\mathcal{J}_{n,i}^{\circ}}F_{a},$
(106)

i.e.,

$D(P\|T_{-a}P)=\sum_{i\in\mathbb{Z}}p_{i}\left(\Delta\log\frac{p_{i}}{p_{i+k-1}}+(1-\Delta)\log\frac{p_{i}}{p_{i+k}}\right).$
(107)

Let $B_{\ell}$ denote the same sum as $S_{\ell}$ but without the absolute
value sign,

$B_{\ell}:=\sum_{i\in\mathbb{Z}}p_{i}\log\frac{p_{i}}{p_{i+\ell}}.$ (108)

Finiteness of the $S_{\ell}$ yields from (107) that

$D(P\|T_{-a}P)=\Delta B_{k-1}+(1-\Delta)B_{k}.$ (109)

Also, the relation we are aiming to prove (95) can be restated as

$\sup_{|d|\leq 1}D(P\|T_{d}P)=\max_{|\ell|\leq n}B_{\ell}.$ (110)

We deduce from $k=an+\Delta$, $|a|\leq 1$, and $0\leq\Delta\leq 1$ that we
must have $-n\leq k\leq n+1$. If it holds that $-n+1\leq k\leq n$, then what
we have shown in (109) implies, in view of $0\leq\Delta\leq 1$, that

$D(P\|T_{-a}P)\leq\max_{|\ell|\leq n}B_{\ell}.$ (111)

We treat the remaining two extreme cases $k\in\\{-n,n+1\\}$ separately. First,
if $k=-n$ then $\Delta=0$, in which case

$D(P\|T_{-a}P)=B_{-n}\leq\max_{|\ell|\leq n}B_{\ell}.$ (112)

Second, if $k=n+1$ then $\Delta=1$, in which case

$D(P\|T_{-a}P)=B_{n}\leq\max_{|\ell|\leq n}B_{\ell}.$ (113)

Combining all cases, we conclude that

$\sup_{|d|\leq 1}D(P\|T_{d}P)\leq\max_{|\ell|\leq n}B_{\ell}.$ (114)

We establish now that the reverse inequality in (114) also holds. Let
$\ell\in\\{0,\cdots,n\\}$. The shift $a_{\ell}:=\ell/n$ satisfies
$|a_{\ell}|\leq 1$ and $a_{\ell}+\frac{1}{2n}\in\mathcal{J}_{n,\ell}$. Also,
$\Delta_{\ell}:=\ell-a_{\ell}n=0$. Therefore, we conclude from (109) that

$D(P\|T_{-a_{\ell}}P)=B_{\ell}.$ (115)

This shows that

$\sup_{|d|\leq 1}D(P\|T_{d}P)\geq\max_{0\leq\ell\leq n}B_{\ell}.$ (116)

In addition, consider $\ell\in\\{-n,\cdots,-1\\}$ and the shift
$a_{\ell}^{\prime}:=\ell/n$. Then, in this case
$a_{\ell}^{\prime}+\frac{1}{2n}\in\mathcal{J}_{n,\ell+1}$. Also,
$\Delta_{\ell}^{\prime}:=(\ell+1)-a_{\ell}^{\prime}n=1$. Thus, by (109), we
have that

$D(P\|T_{-a_{\ell}^{\prime}}P)=B_{(\ell+1)-1}=B_{\ell}.$ (117)

Therefore,

$\sup_{|d|\leq 1}D(P\|T_{-d}P)\geq\max_{-n\leq\ell\leq-1}B_{\ell}.$ (118)

Combining (116) and (118), we conclude that

$\sup_{|d|\leq 1}D(P\|T_{-d}P)\geq\max_{|\ell|\leq n}B_{\ell}.$ (119)

Inequality (119) together with the reverse inequality (114) yield that the
desired equation (95) holds, i.e.,

$\sup_{|a|\leq 1}~{}D(P\|T_{a}P)=\max_{|k|\leq
n}~{}\sum_{i\in\mathbb{Z}}p_{i}\log\frac{p_{i}}{p_{i+k}}.$ (120)

Next, we show that the expression

$\max_{|k|\leq n}~{}\sum_{i\in\mathbb{Z}}p_{i}\log\frac{p_{i}}{p_{i+k}}$ (121)

reduces to the form given in the statement of the theorem. By construction,
$p_{i}=p_{-i}$ for each $i\in\mathbb{Z}$. Thus, we have for each
$k\in\mathbb{Z}$

$\displaystyle B_{k}$
$\displaystyle=\sum_{i\in\mathbb{Z}}p_{i}\log\frac{p_{i}}{p_{i+k}}=\sum_{j\in\mathbb{Z}}p_{-j}\log\frac{p_{-j}}{p_{-j+k}}=\sum_{j\in\mathbb{Z}}p_{j}\log\frac{p_{j}}{p_{j-k}}=B_{-k}.$
(122)

Therefore, $B_{k}=(B_{k}+B_{-k})/2$ for every $k\in\mathbb{Z}$. Note that this
is a symmetric expression in $k$. As $B_{0}=0$, the KL-divergence is
nonnegative, and $B_{k}\geq 0$ for every $|k|\leq n$ (see (115) and (117)), we
conclude that

$\sup_{|a|\leq 1}~{}D(P\|T_{a}P)=\max_{1\leq k\leq
n}~{}\frac{1}{2}(B_{k}+B_{-k}).$ (123)

We now rewrite (123) in terms of $p_{i}$ for only $0\leq i\leq N$, by taking
advantage of (93). Fix $k\in\\{1,\cdots,n\\}$. We may write

$B_{-k}=\sum_{j\in\mathbb{Z}}p_{j}\log\frac{p_{j}}{p_{j-k}}=\sum_{i\in\mathbb{Z}}p_{i+k}\log\frac{p_{i+k}}{p_{i}},$
(124)

so

$B_{k}+B_{-k}=\sum_{i\in\mathbb{Z}}(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}.$
(125)

We split this sum at the points $-N,N-k,$ and $N$. For any
$k\in\\{1,\ldots,n\\}$, using the assumption that $n<N$, we may write

$\sum_{i\in\mathbb{Z}}(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}=\sum_{i=-N+1}^{N-k-1}(p_{|i|}-p_{|i+k|})\log\frac{p_{|i|}}{p_{|i+k|}}\\\
+\sum_{i=N-k}^{\infty}(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}+\sum_{i=-\infty}^{-N}(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}.$
(126)

In fact, the third term in (126) is identical to the second. This is proved by

$\displaystyle\sum_{i=-\infty}^{-N}(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}$
$\displaystyle=\sum_{i=N}^{\infty}(p_{-i}-p_{-i+k})\log\frac{p_{-i}}{p_{-i+k}}$
(127)
$\displaystyle=\sum_{i=N}^{\infty}(p_{i}-p_{i-k})\log\frac{p_{i}}{p_{i-k}}$
(128)
$\displaystyle=\sum_{i=N-k}^{\infty}(p_{i+k}-p_{i})\log\frac{p_{i+k}}{p_{i}}$
(129)
$\displaystyle=\sum_{i=N-k}^{\infty}(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}.$
(130)

Moreover, we may rewrite this expression as

$\displaystyle\sum_{i=N-k}^{\infty}$
$\displaystyle(p_{i}-p_{i+k})\log\frac{p_{i}}{p_{i+k}}$
$\displaystyle=\sum_{i=N-k}^{N-1}(p_{i}-p_{N}r^{i+k-N})\log\frac{p_{i}}{p_{N}r^{i+k-N}}+\sum_{i=N}^{\infty}(p_{N}r^{i-N}-p_{N}r^{i+k-N})\log\frac{p_{N}r^{i-N}}{p_{N}r^{i+k-N}}$
(131)
$\displaystyle=\sum_{i=N-k}^{N-1}(p_{i}-p_{N}r^{i+k-N})\log\frac{p_{i}}{p_{N}r^{i+k-N}}+p_{N}\sum_{i=N}^{\infty}r^{i-N}(1-r^{k})\log
r^{-k}$ (132)
$\displaystyle=\sum_{i=N-k}^{N-1}(p_{i}-p_{N}r^{i+k-N})\log\frac{p_{i}}{p_{N}r^{i+k-N}}+p_{N}\frac{1-r^{k}}{1-r}k\log
r^{-1}.$ (133)

Putting all of the above together shows that (123) is exactly equal to the
objective function in (20).

Finally, we show that the cost constraint

$\mathbb{E}_{P}[c]\leq C$ (134)

is equivalent to the one given in (20). By nonnegativity of $c$, we have that

$\displaystyle\mathbb{E}_{P}[c]$
$\displaystyle=\int_{\mathbb{R}}fc=\sum_{i\in\mathbb{Z}}\int_{\mathcal{J}_{n,i}}np_{i}c=\sum_{i\in\mathbb{Z}}p_{i}c_{n,i}=p_{0}c_{n,0}+2\sum_{i=1}^{N-1}p_{i}c_{n,i}+2p_{N}\sum_{i=N}^{\infty}c_{n,i}r^{i-N},$
(135)

and the proof is complete.

##  Appendix C Proof of Theorem 3: Optimality of Cactus

We will use the integration shorthand

$\int_{A}f:=\int_{A}f(x)\,dx.$ (136)

Define

$\gamma:=\left\\{\begin{array}[]{cl}1/2&\text{ if }\alpha>1,\\\
\alpha/2&\text{ otherwise.}\end{array}\right.$ (137)

Note that $\gamma\in(0,1/2]$ and $\gamma<\alpha$. Define the PDF

$\psi(x):=\mathrm{exp}\left(-|x|^{\gamma}\right)\cdot\chi^{-1},$ (138)

where

$\chi:=\int_{\mathbb{R}}\mathrm{exp}\left(-|x|^{\gamma}\right)\,dx$ (139)

is the normalization constant. As $\gamma\in(0,1]$, the function
$z\mapsto|z|^{\gamma}$ is subadditive. Hence, for any $x,y\in\mathbb{R}$ we
have the inequality

$\frac{\psi(x+y)}{\psi(x)}\leq\mathrm{exp}\left(|y|^{\gamma}\right).$ (140)

For each $\sigma>0,$ denote the dilated PDF

$\psi^{\sigma}(x):=\frac{1}{\sigma}\psi\left(\frac{x}{\sigma}\right).$ (141)

We denote the result of convolving a PDF $q$ with $\psi^{\sigma}$ by
$q_{\sigma}$,

$q_{\sigma}:=q\ast\psi^{\sigma}.$ (142)

For any $a\in\mathbb{R}$, it is easy to see that

$T_{a}(q_{\sigma})=\left(T_{a}q\right)_{\sigma},$ (143)

so we denote this common quantity by $T_{a}q_{\sigma}.$

Due to the length of the proof, we break down some of the initial steps into
the following five auxiliary lemmas. The proof resumes in the subsequent
subsection.

###  C.1 Auxiliary Lemmas

The first lemma helps reduce the problem to considering only continuous PDFs.
Specifically, it shows that a convolution $q_{\sigma}$ can perform arbitrarily
close to how the original PDF $q$ does.

######  Lemma 2.

For any PDF $q$ and constant $\eta>0$, there is a constant
$\sigma_{0}\in(0,1)$ such that $\sigma\in(0,\sigma_{0}]$ implies the
inequalities

$\displaystyle D(q_{\sigma}\|T_{a}q_{\sigma})$ $\displaystyle\leq
D(q\|T_{a}q),\quad\text{for all }a\in\mathbb{R},$ (144)
$\displaystyle\mathbb{E}_{q_{\sigma}}[c]$
$\displaystyle\leq\mathbb{E}_{q}[c]+\eta.$ (145)

###### Proof.

First, by the data-processing inequality, for any $a\in\mathbb{R}$ and
$\sigma>0$,

$D(q_{\sigma}\|T_{a}q_{\sigma})\leq D(q\|T_{a}q).$ (146)

Thus, (144) always holds. We may assume that $\mathbb{E}_{q}[c]<\infty$, for
otherwise (145) trivially holds. Now, we will establish (145) for all small
$\sigma$ by proving the limit

$\lim_{\sigma\to 0^{+}}\mathbb{E}_{q_{\sigma}}[c]=\mathbb{E}_{q}[c].$ (147)

Let $(\Omega,\mathcal{F},P)$ be a probability space and
$Z,V:\Omega\to\mathbb{R}$ be independent random variables with PDFs $q$ and
$\psi$, respectively, with respect to $\lambda$, i.e., with
$P_{Z}(B):=P(Z^{-1}(B))$ and $P_{V}(B):=P(V^{-1}(B))$ we have

$\frac{dP_{Z}}{d\lambda}=q,\qquad\frac{dP_{V}}{d\lambda}=\psi.$ (148)

Then, for any $\sigma>0$, the random variable $Z_{\sigma}:=Z+\sigma V$ has PDF
$q_{\sigma}$ (see equations (137)–(142)). Denote integration against $P$ by
$\mathbb{E}$; in particular,

$\mathbb{E}[f(Z,V)]:=\int_{\Omega}f(Z(\omega),V(\omega))\,dP(\omega)$ (149)

for any Borel function $f:\mathbb{R}^{2}\to\mathbb{R}$.

By Slutsky’s theorem, we have that $Z_{\sigma}\to Z$ in distribution. By the
continuous mapping theorem, we also have that $c(Z_{\sigma})\to c(Z)$ in
distribution. Thus, by the Lebesgue-Vitali theorem [29, Theorem 4.5.4], to
conclude that (147) holds, it suffices to show uniform integrability of
$\\{c(Z_{\sigma})\\}_{0<\sigma\leq 1}$, i.e., it suffices to show that

$\lim_{K\to\infty}\,\sup_{0<\sigma\leq 1}\mathbb{E}\left[c(Z_{\sigma})\cdot
1_{(K,\infty)}(c(Z_{\sigma}))\right]=0.$ (150)

To establish (150), it suffices to uniformly upper bound the $c(Z_{\sigma})$
(for $\sigma\in(0,1]$) by an integrable random variable. To see this, note
that if

$\sup_{0<\sigma\leq 1}c(Z_{\sigma})\leq U$ (151)

for some random variable $U:\Omega\to\mathbb{R}$ with $\mathbb{E}[U]<\infty$,
then we have the inequality

$\displaystyle\sup_{0<\sigma\leq 1}\mathbb{E}\left[c(Z_{\sigma})\cdot
1_{(K,\infty)}(c(Z_{\sigma}))\right]$ $\displaystyle\leq\mathbb{E}\left[U\cdot
1_{(K,\infty)}(U)\right],$ (152)

and the limit

$\lim_{K\to\infty}\mathbb{E}\left[U\cdot 1_{(K,\infty)}(U)\right]=0$ (153)

follows by absolute continuity of the Lebesgue integral in view of
$\mathbb{E}[U]<\infty$.

Now, we show that a uniform bound as in (151) holds. Recall that for any
$(u,v)\in\mathbb{R}^{2}$ and $0<s<t$, denoting
$\|(u,v)\|_{s}:=(|u|^{s}+|v|^{s})^{1/s}$, one has from Hölder’s inequality
that

$\|(u,v)\|_{t}\leq\|(u,v)\|_{s}\leq 2^{\frac{1}{s}-\frac{1}{t}}\|(u,v)\|_{t}.$
(154)

In particular, for any $r>0$, denoting $\ell_{r}:=\max(1,2^{r-1})$, one has
that

$(|u|+|v|)^{r}\leq\ell_{r}(|u|^{r}+|v|^{r}).$ (155)

In addition, by the tail-regularity assumption on $c$, there is a constant
$\beta_{1}>0$ such that

$c(x)\leq\beta_{1}\left(1+|x|^{\alpha}\right)$ (156)

for every $x\in\mathbb{R}$. Then, for any $u,v\in\mathbb{R}$, we have that

$c(u+v)\leq\beta_{1}\left(1+\ell_{\alpha}\left(|u|^{\alpha}+|v|^{\alpha}\right)\right).$
(157)

In particular, for every $\sigma\in(0,1]$,

$c(Z_{\sigma})\leq\beta_{1}\left(1+\ell_{\alpha}\left(|Z|^{\alpha}+|V|^{\alpha}\right)\right)=:U.$
(158)

Now, we have that $\mathbb{E}[|V|^{\alpha}]<\infty$ by definition of $\psi$.
Further, by assumption on $c$, there are $A,\beta_{2}>0$ such that $|x|>A$
implies

$\beta_{2}|x|^{\alpha}\leq c(x).$ (159)

Then, as

$\displaystyle|Z|^{\alpha}$ $\displaystyle\leq A^{\alpha}+|Z|^{\alpha}\cdot
1_{\mathbb{R}\setminus[-A,A]}(Z)\leq A^{\alpha}+c(Z)/\beta_{2}$ (160)

and $\mathbb{E}[c(Z)]=\mathbb{E}_{q}[c]<\infty$ by assumption, we also have
that $\mathbb{E}[|Z|^{\alpha}]<\infty$. Thus, $\mathbb{E}[U]<\infty$. Hence,
by absolute continuity of the Lebesgue integral, the uniform bound in (158)
implies the uniform integrability of the set
$\\{c(Z_{\sigma})\\}_{0<\sigma\leq 1}$, so (147) follows by the Lebesgue-
Vitali theorem, and the proof is complete. ∎

The following lemma shows that the integrands when computing
$D(q_{\sigma}\|T_{a}q_{\sigma})$ have equi-small tails as $a$ varies over
$[-1,1]$. This will allow us to focus on approximating $q_{\sigma}$ by a
cactus distribution only in a bounded interval.

######  Lemma 3.

If the PDF $q$ satisfies

$\sup_{|a|\leq 1}D(q\|T_{a}q)<\infty$ (161)

then for any $\sigma>0$

$\lim_{z\to\infty}\sup_{|a|\leq
1}\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|=0.$
(162)

###### Proof.

Assume that $q$ satisfies (161). By the data processing inequality, we also
have

$\sup_{|a|\leq 1}D(q_{\sigma}\|T_{a}q_{\sigma})<\infty.$ (163)

Suppose, for the sake of contradiction, that (162) does not hold. That is,
suppose there exists $\varepsilon>0$ where

$\limsup_{z\to\infty}\sup_{|a|\leq
1}\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|=\varepsilon.$
(164)

This implies that there exists a sequence
$\\{(z_{n},a_{n})\\}_{n\in\mathbb{N}}$, where $z_{n}\nearrow\infty$ and
$\sup_{n\in\mathbb{N}}|a_{n}|\leq 1$, such that for all $n$

$\int_{\mathbb{R}\setminus[-z_{n},z_{n}]}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a_{n}}q_{\sigma}}\right|\geq\varepsilon/2.$
(165)

Since $[-1,1]$ is a compact set, there exists a convergent subsequence
$\\{a_{n_{k}}\\}_{k\in\mathbb{N}}$, say $a_{n_{k}}\to a$ where $a\in[-1,1]$.
Moreover, for any $z>0$, for sufficiently large $k$ we have $z_{n_{k}}\geq z$,
which implies

$\limsup_{k\to\infty}\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a_{n_{k}}}q_{\sigma}}\right|\geq\varepsilon/2.$
(166)

Recall that $\psi$ is as defined in (138) and that, as shown in (140), it
satisfies the inequality

$\frac{\psi(x+y)}{\psi(x)}\leq\mathrm{exp}\left(|y|^{\gamma}\right)$ (167)

for every $x,y\in\mathbb{R}$. Thus, for any $a,b,z\in\mathbb{R}$,

$\displaystyle(T_{a}q_{\sigma})(z)$ $\displaystyle=q_{\sigma}(z-a)$ (168)
$\displaystyle=\int_{\mathbb{R}}q(x)\frac{1}{\sigma}\psi\left(\frac{z-a-x}{\sigma}\right)dx$
(169) $\displaystyle\leq
e^{|a-b|^{\gamma}/\sigma^{\gamma}}\int_{\mathbb{R}}q(x)\frac{1}{\sigma}\psi\left(\frac{z-b-x}{\sigma}\right)dx$
(170) $\displaystyle=e^{|a-b|^{\gamma}/\sigma^{\gamma}}(T_{b}q_{\sigma})(z).$
(171)

Thus, for any $a,b\in\mathbb{R}$, we have the uniform bound

$\left\|\log\frac{T_{a}q_{\sigma}}{T_{b}q_{\sigma}}\right\|_{L^{\infty}(\mathbb{R})}\leq\left(\frac{|a-b|}{\sigma}\right)^{\gamma}.$
(172)

Applying this bound to the integral in (166) gives

$\displaystyle\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\cdot\left|\log\frac{q_{\sigma}}{T_{a_{n_{k}}}q_{\sigma}}\right|$
$\displaystyle=\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\cdot\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}+\log\frac{T_{a}q_{\sigma}}{T_{a_{n_{k}}}q_{\sigma}}\right|$
(173)
$\displaystyle\leq\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\cdot\left(\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|+\left(\frac{|a_{n_{k}}-a|}{\sigma}\right)^{\gamma}\right)$
(174)
$\displaystyle\leq\left(\frac{|a_{n_{k}}-a|}{\sigma}\right)^{\gamma}+\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\cdot\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|.$
(175)

Recalling inequality (166) and that $a_{n_{k}}\to a$ as $k\to\infty$, we have,
for any $z>0$,

$\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|\geq\varepsilon/2.$
(176)

Finally, note that by finiteness of the KL-divergence
$D(q_{\sigma}\|T_{a}q_{\sigma})$ (see (163)), we also have that

$\int_{\mathbb{R}}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|<\infty.$
(177)

Indeed, the function $f(t):=t\log t$ over $(0,\infty)$ is lower bounded by
$-1/e$, so dividing the integration region over the two regions where $f$ is
positive or negative we obtain

$\displaystyle\int_{\mathbb{R}}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|$
$\displaystyle=\mathbb{E}_{T_{a}q_{\sigma}}\left[\left|f\circ\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|\right]\leq
D\left(q_{\sigma}\|T_{a}q_{\sigma}\right)+\frac{2}{e}<\infty.$ (178)

Thus, by the monotone convergence theorem, we must have

$\lim_{z\to\infty}\int_{\mathbb{R}\setminus[-z,z]}q_{\sigma}\left|\log\frac{q_{\sigma}}{T_{a}q_{\sigma}}\right|=0.$
(179)

As this contradicts (176), the lemma is proved. ∎

The following lemma gives an $\mathrm{exp}(-O(w^{\gamma}))$ lower bound on the
minimum value of $q_{\sigma}$ over $[-w,w]$ and on the probability that
$Z_{\sigma}\sim q_{\sigma}$ exceeds $w$, both as $w\to\infty$.

######  Lemma 4.

For a PDF $q$ and a constant $\sigma>0$, we have that

$\int_{[w,\infty)}q_{\sigma}=\mathrm{exp}\left(-O(w^{\gamma})\right)$ (180)

and

$\min_{|x|\leq w}q_{\sigma}(x)=\mathrm{exp}\left(-O(w^{\gamma})\right),$ (181)

both as $w\to\infty$.

###### Proof.

First, we show that there is a bounded Borel set $B$ with $\lambda(B)>0$ such
that

$\mu:=\inf_{x\in B}q(x)>0.$ (182)

Note that we may remove the boundedness condition on $B$. Indeed, if the Borel
set $B$ satisfies $\lambda(B)>0$ and $\inf_{x\in B}q(x)>0$, then the bounded
Borel sets $A_{m}:=B\cap[-m,m]$ also satisfy $\lambda(A_{m})>0$ and
$\inf_{x\in A_{m}}q(x)>0$ for all large $m$ by continuity of $\lambda$ and the
definition of the infimum. Now, to see that such a $B$ exists, consider the
Borel sets $B_{n}:=q^{-1}([1/n,\infty))$ for integers $n\geq 1$. For each
$n\geq 1$, we have that $\inf_{x\in B_{n}}q(x)\geq 1/n$. Suppose, for the sake
of contradiction, that $\lambda(B_{n})=0$ for each $n$. Then we would have

$\displaystyle\lambda(q^{-1}((0,\infty)))$
$\displaystyle=\lambda\left(q^{-1}\left(\bigcup_{n\geq
1}[1/n,\infty)\right)\right)=\lambda\left(\bigcup_{n\geq 1}B_{n}\right)=0.$
(183)

Hence, $q=0$ a.e. However, this would contradict that $q$ is a PDF. Thus, we
conclude that $\lambda(B_{n})>0$ for some $n$. In short, there must exist a
bounded Borel set $B$ with $\lambda(B)>0$ and $\inf_{x\in B}q(x)>0$. Fix such
a $B$, and let $x_{0}>0$ be such that $B\subset[-x_{0},x_{0}]$.

Recall that we define $q_{\sigma}=q\ast\psi^{\sigma}$ (see equations
(137)–(142)). For each $w\in\mathbb{R}$, Tonelli’s theorem implies that

$\int_{[w,\infty)}q_{\sigma}=\int_{\mathbb{R}}q(x)\int_{w}^{\infty}\psi\left(\frac{y-x}{\sigma}\right)\frac{1}{\sigma}\,dy\,dx.$
(184)

Performing a change of variable, we have for every $x,w\in\mathbb{R}$

$\int_{w}^{\infty}\psi\left(\frac{y-x}{\sigma}\right)\frac{1}{\sigma}\,dy=\int_{[(w-x)/\sigma,\infty)}\psi.$
(185)

Further, for any $z\geq 0$, by definition of $\psi$, we have the bound

$\int_{[z,\infty)}\psi\geq\int_{[z,z+1]}\psi\geq\mathrm{exp}\left(-\left(z+1\right)^{\gamma}\right)\cdot\chi^{-1},$
(186)

where $\chi=\int_{\mathbb{R}}\mathrm{exp}(-|u|^{\gamma})\,du$ is the
normalization constant for $\psi$. Therefore, whenever $w\geq x$ we have

$\int_{[(w-x)/\sigma,\infty)}\psi\geq\mathrm{exp}\left(-\left(\frac{w-x+\sigma}{\sigma}\right)^{\gamma}\right)\cdot\chi^{-1}.$
(187)

Now, combining (184) and (185), nonnegativity of the PDFs $q$ and $\psi$
implies the bound

$\int_{[w,\infty)}q_{\sigma}\geq\int_{B}q(x)\int_{[(w-x)/\sigma,\infty)}\psi(u)\,du\,dx.$
(188)

Since $B\subset[-x_{0},x_{0}]$, we conclude from (187) that for every $w\geq
x_{0}$

$\displaystyle\int_{[w,\infty)}q_{\sigma}$
$\displaystyle\geq\int_{B}\mu\cdot\mathrm{exp}\left(-\left(\frac{w-x+\sigma}{\sigma}\right)^{\gamma}\right)\cdot\chi^{-1}\,dx$
(189)
$\displaystyle\geq\lambda(B)\mu\chi^{-1}\cdot\mathrm{exp}\left(-\left(\frac{w+x_{0}+\sigma}{\sigma}\right)^{\gamma}\right).$
(190)

The estimate in (180) follows by taking $w\to\infty$.

Finally, we show that (181) holds. Let $w_{0}>0$ be such that
$\int_{[-w,w]}q\geq 1/2$ for every $w\geq w_{0}$. Then, for any $w\geq w_{0}$
and $x\in[-w,w]$,

$\displaystyle q_{\sigma}(x)$
$\displaystyle=\int_{\mathbb{R}}q(u)\psi^{\sigma}(x-u)\,du$ (191)
$\displaystyle=(\sigma\chi)^{-1}\int_{\mathbb{R}}q(u)~{}\mathrm{exp}\left(-|x-u|^{\gamma}/\sigma^{\gamma}\right)\,du$
(192)
$\displaystyle\geq(\sigma\chi)^{-1}\int_{-w}^{w}q(u)~{}\mathrm{exp}\left(-|x-u|^{\gamma}/\sigma^{\gamma}\right)\,du$
(193)
$\displaystyle\geq(\sigma\chi)^{-1}~{}\mathrm{exp}\left(-(2/\sigma^{\gamma})w^{\gamma}\right)\int_{[-w,w]}q$
(194)
$\displaystyle\geq(2\sigma\chi)^{-1}~{}\mathrm{exp}\left(-(2/\sigma^{\gamma})w^{\gamma}\right).$
(195)

The estimate (181) follows by taking $w\to\infty$. ∎

Conversely, the following lemma gives an upper bound on the tail of any
distribution that satisfies the cost constraint.

######  Lemma 5.

For any $P\in\mathscr{B}$, if $\mathbb{E}_{P}[c]<\infty$ then

$P(\mathbb{R}\setminus[-x,x])=o\left(c(x)^{-1}\right)$ (196)

as $x\to\infty.$

###### Proof.

We start by showing that

$\lim_{t\to\infty}P\left(\left\\{c>t\right\\}\right)\cdot t=0.$ (197)

Denote $f(t):=P\left(\left\\{c>t\right\\}\right)$ for $t>0$. Note that $f$ is
a decreasing nonnegative function over $(0,\infty)$. Further, $f$ is
integrable by nonnegativity of $c$ and by the assumption in the lemma since

$\int_{0}^{\infty}P\left(\left\\{c>t\right\\}\right)\,dt=\mathbb{E}_{P}[c]<\infty.$
(198)

We show that these three properties of $f$ yield that $f(t)=o(t^{-1})$.

Suppose, for the sake of contradiction, that there is an $\varepsilon>0$ and
an increasing sequence $t_{n}\nearrow\infty$ of strictly positive numbers such
that

$f(t_{n})\geq\frac{\varepsilon}{t_{n}}$ (199)

for every $n\in\mathbb{N}$. Since $f$ is decreasing, we infer from (199) that

$f(t)\geq\sum_{n\in\mathbb{N}}\frac{\varepsilon}{t_{n+1}}\cdot
1_{(t_{n},t_{n+1}]}(t)$ (200)

for every $t>t_{1}$. Integrating both sides in (200), integrability of $f$
implies that

$\infty>\int_{(t_{1},\infty)}f\geq\sum_{n\in\mathbb{N}}\varepsilon\left(1-\frac{t_{n}}{t_{n+1}}\right).$
(201)

By convergence of the series in (201), we conclude that $t_{n}/t_{n+1}\sim 1$
as $n\to\infty$. In particular, the constant

$\tau:=\inf_{n\in\mathbb{N}}\frac{t_{n}}{t_{n+1}}$ (202)

satisfies $\tau\in(0,1)$. Set $\delta=\varepsilon\tau$, and note that
$\delta>0$. Then, from (200) we obtain

$\displaystyle f(t)\cdot 1_{(t_{1},\infty)}(t)$
$\displaystyle\geq\sum_{n\in\mathbb{N}}\frac{\delta}{\tau\cdot t_{n+1}}\cdot
1_{(t_{n},t_{n+1}]}(t)$ (203)
$\displaystyle\geq\sum_{n\in\mathbb{N}}\frac{\delta}{t_{n}}\cdot
1_{(t_{n},t_{n+1}]}(t)$ (204)
$\displaystyle\geq\sum_{n\in\mathbb{N}}\frac{\delta}{t}\cdot
1_{(t_{n},t_{n+1}]}(t)=\frac{\delta}{t}\cdot 1_{(t_{1},\infty)}(t).$ (205)

However, (205) contradicts the integrability of $f$. Thus, we conclude that it
must be the case that

$f(t)=o\left(t^{-1}\right)$ (206)

as $t\to\infty$.

To finish the proof of the lemma, recall by the tail-regularity assumption on
$c$ that we have

$\lim_{|x|\to\infty}\frac{c(x)}{|x|^{\alpha}}=\beta$ (207)

for some $\alpha,\beta>0$. Thus there are $0<\beta_{1}<\beta<\beta_{2}$ such
that for sufficiently large $|x|$, $\beta_{1}|x|^{\alpha}\leq
c(x)\leq\beta_{2}|x|^{\alpha}$. Then, for all large enough $t$, we have that

$\displaystyle P\left(\left\\{c>t\right\\}\right)$ $\displaystyle\geq
P\left(\mathbb{R}\setminus\left[-(t/\beta_{1})^{1/\alpha},(t/\beta_{1})^{1/\alpha}\right]\right).$
(208)

Writing $x=(t/\beta_{1})^{1/\alpha}$, we conclude that for all large $x$

$\displaystyle c(x)P\left(\mathbb{R}\setminus[-x,x]\right)$
$\displaystyle\leq\beta_{2}x^{\alpha}P\left(\mathbb{R}\setminus[-x,x]\right)$
(209)
$\displaystyle=\frac{\beta_{2}}{\beta_{1}}tP\left(\mathbb{R}\setminus\left[-(t/\beta_{1})^{1/\alpha},(t/\beta_{1})^{1/\alpha}\right]\right)$
(210)
$\displaystyle\leq\frac{\beta_{2}}{\beta_{1}}tP\left(\left\\{c>t\right\\}\right).$
(211)

Taking $t\to\infty$, we obtain from (206) that

$c(x)P\left(\mathbb{R}\setminus[-x,x]\right)\to 0,$ (212)

as desired. ∎

The final auxiliary lemma gives an upper bound on the tail of the cost
constraint incurred by a cactus distribution.

######  Lemma 6.

Fix $r\in(0,1)$ and integers $N>n\geq 1$, and set $w=(N-1/2)/n$. Assume that
$c(x)\leq\beta_{1}x^{\alpha}$ for $x\geq w$. Then, we have the bound

$\sum_{i\geq
N}c_{n,i}r^{i-N}\leq\beta_{1}\ell_{\alpha}\left(\frac{w^{\alpha}}{1-r}+\frac{2\left(\frac{\alpha}{e}\right)^{\alpha}\log\frac{1}{r}+\Gamma(\alpha+1)}{rn^{\alpha}\left(\log\frac{1}{r}\right)^{\alpha+1}}\right),$
(213)

where $\ell_{\alpha}:=\max(1,2^{\alpha-1})$.

###### Proof.

By monotonicity of $c$,

$\displaystyle\sum_{i\geq N}c_{n,i}r^{i-N}$ $\displaystyle=\sum_{i\geq
N}\int_{(i-1/2)/n}^{(i+1/2)/n}ncr^{i-N}$ (214) $\displaystyle\leq\sum_{i\geq
N}\beta_{1}\left(\frac{i+1/2}{n}\right)^{\alpha}r^{i-N}$ (215)
$\displaystyle=\beta_{1}\sum_{i\geq
0}\left(w+\frac{i+1}{n}\right)^{\alpha}r^{i}$ (216)
$\displaystyle\leq\beta_{1}\ell_{\alpha}\left(\frac{w^{\alpha}}{1-r}+\frac{\text{Li}_{-\alpha}(r)}{rn^{\alpha}}\right),$
(217)

where

$\text{Li}_{-\alpha}(r):=\sum_{k\geq 1}k^{\alpha}r^{k}$ (218)

is the polylogarithm function. To finish the proof of the lemma, we show next
that

$\text{Li}_{-\alpha}(r)\leq
2\left(\frac{\alpha}{e\log\frac{1}{r}}\right)^{\alpha}+\frac{\Gamma(\alpha+1)}{\left(\log\frac{1}{r}\right)^{\alpha+1}}.$
(219)

Now, consider the function $g:(0,\infty)\to(0,\infty)$ defined by

$g(x):=x^{\alpha}r^{x}.$ (220)

We have that

$g^{\prime}(x)=\left(\alpha+x\log r\right)x^{\alpha-1}r^{x}.$ (221)

Thus, $g$ increases until it reaches a maximum at
$x_{0}=\alpha/\log\frac{1}{r}$ then it decreases. Thus,

$\text{Li}_{-\alpha}(r)\leq g(\lfloor x_{0}\rfloor)+g(\lceil
x_{0}\rceil)+\int_{(0,\infty)}g.$ (222)

We have

$g(\lfloor x_{0}\rfloor)+g(\lceil x_{0}\rceil)\leq
2g(x_{0})=2\left(\frac{\alpha}{e\log\frac{1}{r}}\right)^{\alpha},$ (223)

and

$\int_{(0,\infty)}g=\frac{\Gamma(\alpha+1)}{\left(\log\frac{1}{r}\right)^{\alpha+1}}.$
(224)

The proof is thus complete. ∎

###  C.2 Proof of Theorem 3

By Theorem 1, there is a PDF $q^{\star}$ that satisfies both

$\displaystyle\sup_{|a|\leq 1}D(q^{\star}\|T_{a}q^{\star})$
$\displaystyle=\text{KL}^{\star},$ (225)
$\displaystyle\mathbb{E}_{q^{\star}}[c]$ $\displaystyle\leq C.$ (226)

We may assume that $q^{\star}$ is even; indeed, we may replace $q^{\star}$
with the even PDF $(q^{\star}(x)+q^{\star}(-x))/2$, which satisfies the cost
constraint by evenness of $c$, and which also has a better KL-divergence than
that of $q^{\star}$ by joint convexity of the KL-divergence. Fix arbitrary
constants $\delta,\eta>0$, and we will find a cactus distribution that attains
the KL-divergence (225) to within $\delta$ and the cost (226) to within
$\eta$.

By Lemma 2, there is a $\sigma>0$ such that the PDF $q_{\sigma}^{\star}$
satisfies the bounds

$\displaystyle\sup_{|a|\leq 1}D(q_{\sigma}^{\star}\|T_{a}q_{\sigma}^{\star})$
$\displaystyle\leq\text{KL}^{\star},$ (227)
$\displaystyle\mathbb{E}_{q_{\sigma}^{\star}}[c]$ $\displaystyle\leq
C+\frac{\eta}{2}.$ (228)

Throughout the proof, we will denote

$q:=q_{\sigma}^{\star}$ (229)

for short. Let

$Q(B):=\int_{B}q$ (230)

be the probability measure induced by $q$. We will construct a cactus
distribution that approximates $q$.

We first note a few properties of $q$. Note that $q$ is an even PDF. Further,
it is uniformly continuous, and strictly positive over $\mathbb{R}$. Thus, $q$
is locally bounded away from zero. For each $z\geq 0$, denote the minimum

$\mu_{z}:=\min_{|x|\leq z}q(x),$ (231)

so $\mu_{z}>0$ for every $z$. In addition, $q$ is upper bounded: by Young’s
inequality, we have that

$\displaystyle\|q\|_{L^{\infty}(\mathbb{R})}$
$\displaystyle=\|q^{\star}\ast\psi^{\sigma}\|_{L^{\infty}(\mathbb{R})}\leq\|q^{\star}\|_{L^{1}(\mathbb{R})}\cdot\|\psi^{\sigma}\|_{L^{\infty}(\mathbb{R})}=(\sigma\chi)^{-1}=:M.$
(232)

In fact, $q$ satisfies a property resembling local $\gamma$-Hölder continuity.
Specifically, as in the proof of Lemma 3 (see (167)–(171)), we have that

$q(x)\leq e^{|x-y|^{\gamma}/\sigma^{\gamma}}q(y)$ (233)

for every $x,y\in\mathbb{R}$. Therefore, for some $|t_{x,y}|\leq 1$ we have

$\displaystyle|q(x)-q(y)|$
$\displaystyle=q(y)\left|e^{t_{x,y}|x-y|^{\gamma}/\sigma^{\gamma}}-1\right|\leq\frac{2M}{\sigma^{\gamma}}|x-y|^{\gamma},$
(234)

where the latter inequality follows whenever $|x-y|\leq\sigma$. In particular,
for all $\varepsilon\in(0,2M)$, we have that

$|q(x)-q(y)|\leq\varepsilon\quad\text{whenever}\quad|x-y|\leq\sigma\cdot\left(\frac{\varepsilon}{2M}\right)^{1/\gamma}.$
(235)

Before constructing the parameters $(n,N,r)$ of the cactus distribution, we
note a fundamental lower bound on $n$. For the cost constraint to be
satisfied, we need $c_{n,0}<C$ to hold. Nevertheless, by continuity of $c$,
every real number is a Lebesgue point of $c$. In particular, as $0$ is a
Lebesgue point of $c$, we obtain

$c_{n,0}=\frac{\int_{[-1/(2n),1/(2n)]}c}{1/n}\to c(0)=0$ (236)

as $n\to\infty$. Let $n_{\min}$ be the least positive integer such that

$c_{n,0}<C$ (237)

for every $n\geq n_{\min}$. Note that $n_{\min}$ depends only on $c$ and $C$.

Now, we choose the integers $n$ and $N$. Denote the constants

$\displaystyle\theta_{\alpha}$
$\displaystyle:=4\left(\frac{\alpha}{e}\right)^{\alpha}+2\Gamma(\alpha+1)$
(238) $\displaystyle\theta_{\alpha}^{\prime}$
$\displaystyle:=(2\theta_{\alpha})^{1/\alpha}$ (239)
$\displaystyle\gamma^{\prime}$
$\displaystyle:=\frac{\gamma+\alpha}{2}\in(\gamma,\alpha)$ (240)
$\displaystyle\varepsilon_{\min}$
$\displaystyle:=2M\cdot\min\left(\frac{2}{\sigma
n_{\min}},\frac{1}{\theta_{\alpha}^{\prime}\sigma}\right)^{\gamma}$ (241)
$\displaystyle z_{\min,0}$
$\displaystyle:=\left(\log\left(\frac{4}{\sigma}\cdot\left(\frac{2M}{\varepsilon_{\min}}\right)^{1/\gamma}\right)\right)^{1/\gamma^{\prime}}$
(242) $\displaystyle z_{\min,1}$
$\displaystyle:=\left(\frac{\eta}{\delta}\cdot\frac{2e\theta_{\alpha}^{\prime}}{\beta_{1}\ell_{\alpha}}\right)^{1/(\alpha+1)}$
(243) $\displaystyle z_{\min,2}$
$\displaystyle:=\left(\frac{2^{\alpha+1}}{\beta_{1}\ell_{\alpha}}\right)^{1/(\alpha-\gamma^{\prime})}$
(244) $\displaystyle z_{\min}$
$\displaystyle:=\max\left(z_{\min,0},z_{\min,1},z_{\min,2},\frac{\delta}{12M}\right).$
(245)

Since $q=q_{\sigma}^{\star}$ (see (229)), Lemma 3 yields the existence of a
constant $z_{0}>0$ such that $z\geq z_{0}$ implies the uniform bound

$\sup_{|a|\leq
1}\int_{\mathbb{R}\setminus[-z,z]}q\left|\log\frac{q}{T_{a}q}\right|\leq\frac{\delta}{3}.$
(246)

In addition, Lemma 4 yields the existence of constants $\tau,z_{1}>0$ such
that $z\geq z_{1}$ implies (see (230) and (231))

$\min\left(\mu_{z},Q([z,\infty))\right)\geq\mathrm{exp}\left(-\tau
z^{\gamma}\right).$ (247)

By the tail-regularity assumption on $c$, there are constants
$\beta_{1},\beta_{2},z_{2}>0$ such that

$\beta_{2}z^{\alpha}\leq c(z)\leq\beta_{1}z^{\alpha}$ (248)

for every $z\geq z_{2}$. By Lemma 5, we have that (see (230))

$\lim_{z\to\infty}Q(\mathbb{R}\setminus[-z,z])c(z)=0.$ (249)

Let $z_{3}>0$ be large enough that $z\geq z_{3}$ implies

$Q\left(\mathbb{R}\setminus[-z,z]\right)c(z)\leq\frac{\beta_{2}}{\beta_{1}\ell_{\alpha}}\cdot\frac{\eta}{6}.$
(250)

If $z\geq\max(z_{2},z_{3})$, then by (248) and (250) we may bound the tail of
$Q$ also by

$Q\left(\mathbb{R}\setminus[-z,z]\right)\leq\frac{1}{\beta_{1}\ell_{\alpha}z^{\alpha}}\cdot\frac{\eta}{6}.$
(251)

Let $z_{4}>0$ be the smallest number such that both inequalities

$\displaystyle e^{\tau z^{\gamma}}$
$\displaystyle\geq\frac{\delta\beta_{1}\ell_{\alpha}}{2M\eta}\cdot z^{\alpha}$
(252) $\displaystyle e^{\gamma z^{\gamma^{\prime}}}$
$\displaystyle\geq\left(\frac{4}{\sigma}\right)^{\gamma}\cdot\frac{48M^{2}}{\delta}\cdot
ze^{\tau z^{\gamma}}$ (253)

hold for all $z\geq z_{4}$. Fix a rational number

$z>\max(z_{\min},z_{0},z_{1},z_{2},z_{3},z_{4},2\theta_{\alpha}^{\prime})$
(254)

that is a ratio of an odd integer by an even integer, and set

$w:=z+1.$ (255)

We choose $z$ (hence also $w$) here to belong in $\mathbb{N}+\frac{1}{2}$ for
simplicity, but we note that any other choice (of denominator) is also valid
provided that $w$ is increased so that the subsequent choices in (260) below
can be made. Set

$\varepsilon:=\frac{2^{2\gamma+1}M}{\sigma^{\gamma}}\cdot e^{-\gamma
w^{\gamma^{\prime}}}.$ (256)

Denote

$n_{0}:=\frac{2}{\sigma}\cdot\left(\frac{2M}{\varepsilon}\right)^{1/\gamma},$
(257)

By the uniform continuity of $q$ shown in (235), we have that

$|q(x)-q(y)|\leq\varepsilon\quad\text{whenever}\quad|x-y|\leq\frac{2}{n_{0}}.$
(258)

Note that $n_{\min}<n_{0}$ since $\varepsilon<\varepsilon_{\min}$, which in
turn follows because $w>z_{\min,0}$. We note also that
$\varepsilon<\varepsilon_{\min}$ implies $2\theta_{\alpha}^{\prime}<n_{0}$.
Set

$n_{1}:=e^{w^{\gamma^{\prime}}}.$ (259)

By construction, we have that $n_{1}=2n_{0}$. Thus, we may choose integers
$n\in[n_{0},n_{1}]$ and $N>n$ such that

$w=\frac{2N-1}{2n}$ (260)

Next, we choose the parameter $r$, thereby completing the cactus distribution
construction. Define, for $i\in\\{0,\cdots,N-1\\}$,

$p_{i}:=\inf_{x\in\mathcal{J}_{n,i}}\frac{q(x)}{n}.$ (261)

By evenness, continuity, and strict positivity of $q$, we have that

$p_{0}+\sum_{i=1}^{N-1}2p_{i}=\int_{[-w,w]}\sum_{|i|\leq N-1}np_{|i|}\cdot
1_{\mathcal{J}_{n,i}}\leq\int_{[-w,w]}q<1.$ (262)

Thus, for any $r\in(0,1),$ setting

$p_{N}:=\frac{1-r}{2}\left(1-\left(p_{0}+\sum_{i=1}^{N-1}2p_{i}\right)\right),$
(263)

we infer from (262) that the vector $\bm{p}=(p_{0},\cdots,p_{N})$ belongs to
$(0,1]^{N+1}$, and by construction it satisfies $S_{r,\bm{p}}=1$. We will
choose $r$ as

$r:=1-\frac{\theta_{\alpha}^{\prime}}{wn},$ (264)

and define $p_{N}$ as in (263) for this choice of $r$.

Therefore, $f_{n,r,\bm{p}}$ is a valid cactus distribution. By uniform
continuity of $q$ (see (258)) and by definition of the $p_{i}$ (see (261)), we
have that $f_{n,r,\bm{p}}$ uniformly approximates $q$ from below over
$[-w,w]$: for every $x\in[-w,w]$ we have that

$0\leq q(x)-f_{n,r,\bm{p}}(x)\leq\varepsilon.$ (265)

We will deduce from the uniform bound (265) that $f_{n,r,\bm{p}}$ approximates
$q$ in the two senses:

$\mathbb{E}_{f_{n,r,\bm{p}}}[c]\leq\mathbb{E}_{q}[c]+\frac{\eta}{2}$ (266)

and

$\sup_{|a|\leq 1}D(f_{n,r,\bm{p}}\|T_{a}f_{n,r,\bm{p}})\leq\sup_{|a|\leq
1}D(q\|T_{a}q)+\delta.$ (267)

Combined with (227)–(228), we would conclude from (266)–(267) that

$\mathbb{E}_{f_{n,r,\bm{p}}}[c]\leq C+\eta$ (268)

and

$\sup_{|a|\leq
1}D(f_{n,r,\bm{p}}\|T_{a}f_{n,r,\bm{p}})\leq\text{KL}^{\star}+\delta.$ (269)

Now, we show that $f_{n,r,\bm{p}}$ satisfies the cost constraint (268). Since
$f_{n,r,\bm{p}}|_{[-w,w]}\leq q|_{[-w,w]}$, we have that

$\mathbb{E}_{f_{n,r,\bm{p}}}[c\cdot 1_{[-w,w]}]\leq\mathbb{E}_{q}[c]\leq
C+\frac{\eta}{2}.$ (270)

We show next that

$\mathbb{E}_{f_{n,r,\bm{p}}}[c\cdot
1_{\mathbb{R}\setminus[-w,w]}]\leq\frac{\eta}{2}.$ (271)

By construction of $f_{n,r,\bm{p}}$, and since $w=(N-1/2)/n$ (see (260)), we
have the expression

$\mathbb{E}_{f_{n,r,\bm{p}}}[c\cdot
1_{\mathbb{R}\setminus[-w,w]}]=2p_{N}\sum_{i\geq N}c_{n,i}r^{i-N}.$ (272)

We bound the terms $2p_{N}$ and $\sum_{i\geq N}c_{n,i}r^{i-N}$ separately. By
Lemma 6, we have the bound

$\sum_{i\geq
N}c_{n,i}r^{i-N}\leq\beta_{1}\ell_{\alpha}\left(\frac{w^{\alpha}}{1-r}+\frac{2\left(\frac{\alpha}{e}\right)^{\alpha}\log\frac{1}{r}+\Gamma(\alpha+1)}{rn^{\alpha}\left(\log\frac{1}{r}\right)^{\alpha+1}}\right).$
(273)

By definition of $r$ (see (264)), and since $w\geq 1$ and $n\geq
2\theta_{\alpha}^{\prime}$, we have that $r\geq 1/2>1/e$. Thus, we deduce from
(273) that

$\sum_{i\geq
N}c_{n,i}r^{i-N}\leq\beta_{1}\ell_{\alpha}\left(\frac{w^{\alpha}}{1-r}+\frac{\theta_{\alpha}}{n^{\alpha}\left(\log\frac{1}{r}\right)^{\alpha+1}}\right),$
(274)

where $\theta_{\alpha}$ is as defined in (238). In addition, we have that
(recall that we denote by $P_{n,r,\bm{p}}$ the probability measure associated
with $f_{n,r,\bm{p}}$)

$\frac{2p_{N}}{1-r}=P_{n,r,\bm{p}}\left(\mathbb{R}\setminus[-w,w]\right)=1-P_{n,r,\bm{p}}\left([-w,w]\right).$
(275)

As $f_{n,r,\bm{p}}$ uniformly approximates $q$ from below over $[-w,w]$ to
within $\varepsilon$ (see (265)), we have that

$P_{n,r,\bm{p}}\left([-w,w]\right)\geq Q\left([-w,w]\right)-2\varepsilon w.$
(276)

Thus, by the bound on the tail of $Q$ in (251)

$\displaystyle\frac{2p_{N}}{1-r}$ $\displaystyle\leq
Q\left(\mathbb{R}\setminus[-w,w]\right)+2\varepsilon
w\leq\frac{1}{\beta_{1}\ell_{\alpha}w^{\alpha}}\cdot\frac{\eta}{6}+2\varepsilon
w.$ (277)

Further, combining inequalities (252)–(253) and using the definition of
$\varepsilon$ in (256), we obtain

$\varepsilon\leq\frac{\eta}{12\beta_{1}\ell_{\alpha}w^{\alpha+1}}.$ (278)

Thus, we deduce

$2p_{N}\leq\frac{\eta\cdot(1-r)}{3\beta_{1}\ell_{\alpha}w^{\alpha}}.$ (279)

From the expression in (272), multiplying inequalities (274) and (279) and
noting that $1-r\leq\log\frac{1}{r}$, we obtain

$\mathbb{E}_{f_{n,r,\bm{p}}}[c\cdot
1_{\mathbb{R}\setminus[-w,w]}]\leq\frac{\eta}{3}\left(1+\frac{\theta_{\alpha}}{\left(wn\log\frac{1}{r}\right)^{\alpha}}\right).$
(280)

By definition of $r$, we have that

$\log\frac{1}{r}\geq 1-r=\frac{\theta_{\alpha}^{\prime}}{wn}.$ (281)

Using inequality (281) in (280), we obtain

$\mathbb{E}_{f_{n,r,\bm{p}}}[c\cdot
1_{\mathbb{R}\setminus[-w,w]}]\leq\frac{\eta}{3}\cdot\frac{3}{2}=\frac{\eta}{2},$
(282)

which is inequality (271). Combining (270)–(271), we deduce (268), i.e.,

$\mathbb{E}_{f_{n,r,\bm{p}}}[c]\leq C+\eta.$ (283)

Next, we show that $f_{n,r,\bm{p}}$ satisfies the KL bound (269). We begin by
splitting the integration at the points $\pm z$. By finiteness of the
considered KL-divergences, we have for each $|a|\leq 1$

$\displaystyle D(f_{n,r,\bm{p}}\|T_{-a}f_{n,r,\bm{p}})-D(q\|T_{-a}q)$
$\displaystyle\leq\int_{[-z,z]}\left(f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}-q\log\frac{q}{T_{-a}q}\right)$
$\displaystyle\hskip
41.25641pt+\int_{\mathbb{R}\setminus[-z,z]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}$
$\displaystyle\hskip
41.25641pt+\int_{\mathbb{R}\setminus[-z,z]}q\log\frac{q}{T_{-a}q}.$ (284)

We already have a uniform bound for the last integral in (284): since $z\geq
z_{0}$, the estimate in (246) holds and we obtain

$\sup_{|a|\leq
1}\int_{\mathbb{R}\setminus[-z,z]}q\log\frac{q}{T_{a}q}\leq\frac{\delta}{3}.$
(285)

We proceed to bounding the first integral in (284) uniformly by

$\sup_{|a|\leq
1}\int_{[-z,z]}\left(f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}-q\log\frac{q}{T_{-a}q}\right)\leq\frac{\delta}{3}.$
(286)

We do this via deriving an upper bound on the integrand that is uniform in
both $a$ and the variable of integration. From $w\geq\delta/(12M)$ (245),
$\mu_{w}\geq e^{-\tau w^{\gamma}}$ (247), and (253), we have that

$\varepsilon\leq\frac{\mu_{w}}{2}\cdot\min\left(1,\frac{\delta}{12Mw}\right).$
(287)

Define the function $g:[-w,w]\to[0,\varepsilon]$ by

$g:=q-f_{n,r,\bm{p}}.$ (288)

That the range of $g$ is contained within $[0,\varepsilon]$ follows since
$f_{n,r,\bm{p}}$ approximates $q$ from below uniformly over $[-w,w]$ to within
$\varepsilon$. Thus, $z=w-1$ yields

$\sup_{|a|\leq 1}\|T_{a}g\|_{L^{\infty}([-z,z])}\leq\varepsilon.$ (289)

We note that, over $[-z,z]$, the inequality

$\displaystyle
f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}-q\log\frac{q}{T_{-a}q}\leq-q\log\left(1-T_{-a}\frac{g}{q}\right)-g\log\left(1-\frac{g}{q}\right)+g\log\frac{T_{-a}q}{q}$
(290)

holds; that all the logarithms are well defined follows since $g\leq q$ over
$[-w,w]$. Indeed, subtracting the left hand side from the right hand side in
(290), we get the function

$-q\log\left(1-\frac{g}{q}\right)-g\log\left(1-T_{-a}\frac{g}{q}\right),$
(291)

which is nonnegative over $[-z,z]$ since $g$ is nonnegative over $[-w,w]$.
Now, we bound each of the terms in (290). It is easy to see that for $0\leq
t\leq 1/2$ one has

$-\log(1-t)\leq 2t.$ (292)

Now, we show that $g/q\leq 1/2$ over $[-w,w]$. Indeed, this is equivalent to
$q\leq 2f_{n,r,\bm{p}}$ over $[-w,w]$. But $q-\varepsilon\leq f_{n,r,\bm{p}}$
over $[-w,w]$, which implies in view of $\varepsilon\leq\mu_{w}/2\leq q/2$
(over $[-w,w]$) that $q\leq 2f_{n,r,\bm{p}}$, as desired. Thus, we obtain that
over $[-z,z]$

$-q\log\left(1-T_{-a}\frac{g}{q}\right)\leq
2qT_{-a}\frac{g}{q}\leq\frac{2M\varepsilon}{\mu_{w}},$ (293)

and

$-g\log\left(1-\frac{g}{q}\right)\leq\frac{2g^{2}}{q}\leq\frac{2\varepsilon^{2}}{\mu_{w}}\leq\varepsilon.$
(294)

It is also clear that over $[-z,z]$

$g\log\frac{T_{-a}q}{q}\leq\varepsilon\log\frac{M}{\mu_{w}}\leq\varepsilon\left(\frac{M}{\mu_{w}}-1\right).$
(295)

Plugging in inequalities (293)–(295) into (290), we obtain the uniform bound

$f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}-q\log\frac{q}{T_{-a}q}\leq\frac{3M\varepsilon}{\mu_{w}}$
(296)

over $[-z,z]$. Integrating, we deduce

$\displaystyle\int_{[-z,z]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}-q\log\frac{q}{T_{-a}q}$
$\displaystyle\leq\frac{6zM\varepsilon}{\mu_{w}}<\frac{\delta}{3},$ (297)

where the last inequality follows by (287).

It remains to upper bound the middle integral in (290), for which we also
derive a uniform upper bound

$\sup_{|a|\leq
1}\int_{\mathbb{R}\setminus[-z,z]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}\leq\frac{\delta}{3}.$
(298)

We will further split the integration at the points $\pm(w+1)$. By evenness of
$f_{n,r,\bm{p}}$, we have that this integral depends only on $|a|$, i.e., for
each $a\in[-1,1]$

$\int_{\mathbb{R}\setminus[-z,z]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}=\int_{\mathbb{R}\setminus[-z,z]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{a}f_{n,r,\bm{p}}}.$
(299)

Thus, it suffices for (298) to show that

$\sup_{0<a\leq
1}\int_{\mathbb{R}\setminus[-z,z]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}\leq\frac{\delta}{3}.$
(300)

Consider first the integral

$\int_{\mathbb{R}\setminus[-(w+1),w+1]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}$
(301)

for fixed $a\in(0,1]$. From the proof of Theorem 2, we can write the integrand
in (301) as follows. Extend the definition of $p_{i}$ to all $i\in\mathbb{Z}$
by

$p_{i}:=\left\\{\begin{array}[]{cl}p_{|i|},&\text{if }-N\leq
i\leq-1,\vspace{2mm}\\\ p_{N}r^{|i|-N},&\text{if }|i|>N.\end{array}\right.$
(302)

For each $i\in\mathbb{Z}$, there is an integer $j$ with $|j|\leq n$, such that
we have

$f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}=np_{i}\log\frac{p_{i}}{p_{i+j}}$
(303)

over $\mathcal{J}_{n,i}$ except possibly at a single point. By definition of
$w$, we have that

$\mathbb{R}\setminus[-(w+1),w+1]=\bigcup_{|i|\geq N+n}\mathcal{J}_{n,i}.$
(304)

Further, if $|i|\leq N+n$ and $|j|\leq n$, then $|i+j|\geq N$. Hence, from
(303) we have that over $\mathcal{J}_{n,i}$ with $|i|\geq N+n$

$\displaystyle f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}$
$\displaystyle=np_{N}r^{|i|-N}(|i|-|i+j|)\log r\leq
n^{2}p_{N}r^{|i|-N}\log\frac{1}{r}.$ (305)

Summing over $|i|\geq N+n$, we obtain

$\displaystyle\int_{\mathbb{R}\setminus[-(w+1),w+1]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}$
$\displaystyle=\sum_{|i|\geq
N+n}\int_{\mathcal{J}_{n,i}}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}$
(306) $\displaystyle\leq np_{N}\log\frac{1}{r}\sum_{|i|\geq
n}r^{|i|}=\frac{2np_{N}r^{n}\log\frac{1}{r}}{1-r}.$ (307)

Using the upper bound on $p_{N}$ in (279), we obtain that

$\int_{\mathbb{R}\setminus[-(w+1),w+1]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}\leq\frac{\eta
nr^{n}\log\frac{1}{r}}{3\beta_{1}\ell_{\alpha}w^{\alpha}}.$ (308)

As $1/e\leq r\leq 1$ and $\log\frac{1}{r}\leq\frac{1}{r}-1$, using the
definition of $r$ given in (264) and $w\geq z_{4}$ (see (245)), we have the
bound

$\frac{\eta
nr^{n}\log\frac{1}{r}}{3\beta_{1}\ell_{\alpha}w^{\alpha}}\leq\frac{e\eta
n(1-r)}{3\beta_{1}\ell_{\alpha}w^{\alpha}}\leq\frac{e\eta\theta_{\alpha}^{\prime}}{3\beta_{1}\ell_{\alpha}w^{\alpha+1}}\leq\frac{\delta}{6}.$
(309)

Thus, we have shown that

$\sup_{a\in(0,1]}\int_{\mathbb{R}\setminus[-(w+1),w+1]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}}{T_{-a}f_{n,r,\bm{p}}}\leq\frac{\delta}{6}.$
(310)

The final integral bound we need is the following:

$\sup_{0<a\leq 1}\int_{w-1<|x|\leq
w+1}f_{n,r,\bm{p}}(x)\log\frac{f_{n,r,\bm{p}}(x)}{T_{-a}f_{n,r,\bm{p}}(x)}\,dx\leq\frac{\delta}{6}.$
(311)

By evenness of $f_{n,r,\bm{p}}$, we have that

$\displaystyle\int_{w-1<|x|\leq
w+1}f_{n,r,\bm{p}}(x)\log\frac{f_{n,r,\bm{p}}(x)}{T_{-a}f_{n,r,\bm{p}}(x)}\,dx=\int_{(w-1,w+1]}f_{n,r,\bm{p}}\log\frac{f_{n,r,\bm{p}}^{2}}{(T_{-a}f_{n,r,\bm{p}})\cdot(T_{a}f_{n,r,\bm{p}})}.$
(312)

Consider the function inside the logarithm in the integrand:

$\rho(x;a):=\frac{f_{n,r,\bm{p}}(x)^{2}}{f_{n,r,\bm{p}}(x+a)f_{n,r,\bm{p}}(x-a)}.$
(313)

We will prove the uniform upper bound

$\sup_{\begin{subarray}{c}x\in(w-1,w+1]\\\
a\in(0,1]\end{subarray}}\,\rho(x;a)\leq\mathrm{exp}\left(2w^{\gamma^{\prime}}\right),$
(314)

where $\gamma^{\prime}:=(\gamma+\alpha)/2\in(\gamma,\alpha)$ is as defined in
(240). Note that

$(w-1,w+1]=\bigcup_{i=N-n}^{N+n}\mathcal{J}_{n,i}.$ (315)

For each $a\in(0,1]$ and $x\in(w-1,w+1]$, there are integers $N-n\leq i\leq
N+n$ and $0\leq j,k\leq n$ such that

$\rho(x;a)=\frac{p_{i}^{2}}{p_{i+j}p_{i-k}}.$ (316)

Thus, it suffices to show that $\mathrm{exp}(w^{\gamma^{\prime}})$ is an upper
bound on each of the terms

$\frac{p_{i}}{p_{j}},~{}\frac{p_{k}}{p_{N}r^{n}},~{}\frac{p_{N}}{p_{k}},~{}\frac{1}{r^{n}}$
(317)

for $0\leq i,j,k\leq N-1$ with $|i-j|\leq n$. First, for $1/r^{n}$, denoting
$m=nw/(2\theta_{\alpha})^{1/\alpha}\geq 2$, we have the bound

$r^{n}=\left(\left(1-\frac{1}{m}\right)^{m}\right)^{(2\theta_{\alpha})^{1/\alpha}/w}\geq
4^{-(2\theta_{\alpha})^{1/\alpha}/w}\geq\frac{1}{2}.$ (318)

Hence,

$\frac{1}{r^{n}}\leq 2\leq e^{w^{\gamma^{\prime}}}.$ (319)

For $p_{k}/p_{N}$ with $0\leq k\leq N-1$, we have the bound

$\displaystyle\frac{p_{k}}{p_{N}}$
$\displaystyle\leq\frac{M}{np_{N}}=\frac{2M/(1-r)}{n\cdot(2p_{N}/(1-r))}=\frac{2M/(1-r)}{nP_{n,r,\bm{p}}(\mathbb{R}\setminus[-w,w])}$
(320)
$\displaystyle\leq\frac{2M/(1-r)}{nQ(\mathbb{R}\setminus[-w,w])}\leq\frac{M/(1-r)}{ne^{-\tau
w^{\gamma}}}=\frac{Mwe^{\tau w^{\gamma}}}{\theta_{\alpha}^{\prime}}.$ (321)

Hence,

$\frac{p_{k}}{p_{N}r^{n}}\leq\frac{2Mwe^{\tau
w^{\gamma}}}{\theta_{\alpha}^{\prime}}\leq e^{w^{\gamma^{\prime}}},$ (322)

where the last inequality follows from (253) for all small $\delta$, e.g., for

$\delta\leq 3\cdot 2^{2\gamma+2}\cdot\theta_{\alpha}^{\prime}\cdot\chi^{-1}$
(323)

(alternatively, we may increase the size of $w$ at the outset). Consider next
$p_{i}/p_{j}$ for $0\leq i,j\leq N-1$ with $|i-j|\leq n$. By definition of the
$p_{k}$ and uniform continuity of $q$, we have for $0\leq k\leq N-2$

$|p_{k}-p_{k+1}|\leq\frac{\varepsilon}{n}.$ (324)

By the triangle inequality, we deduce

$\left|p_{i}-p_{j}\right|\leq\frac{|i-j|\varepsilon}{n}\leq\varepsilon.$ (325)

Thus,

$\frac{p_{i}}{p_{j}}\leq 1+\frac{\varepsilon}{p_{j}}\leq
1+\frac{n\varepsilon}{\mu_{w}}\leq 1+\frac{n}{2}\leq e^{w^{\gamma^{\prime}}}.$
(326)

The last term $p_{N}/p_{k}$ can be bounded using (279) to obtain

$\displaystyle\frac{p_{N}}{p_{k}}$
$\displaystyle\leq\frac{\eta\cdot(1-r)/(6\beta_{1}\ell_{\alpha}w^{\alpha})}{\mu_{w}/n}=\frac{\eta\theta_{\alpha}^{\prime}}{6\beta_{1}\ell_{\alpha}\mu_{w}w^{\alpha+1}}\leq\frac{\eta\theta_{\alpha}^{\prime}}{6\beta_{1}\ell_{\alpha}}\cdot
e^{\tau w^{\gamma}}\leq e^{w^{\gamma^{\prime}}},$ (327)

where the last inequality follows from (253) for all small $\eta$, e.g., for

$\eta\leq
24\beta_{1}\ell_{\alpha}\cdot\chi^{-1}\cdot(\theta_{\alpha}^{\prime})^{-2}$
(328)

(alternatively, we may increase the size of $w$ at the outset). Collecting
(319), (322), (326), and (327), we obtain the following upper bound on the
integral in (312):

$P_{n,r,\bm{p}}((w-1,w+1])\cdot 2w^{\gamma^{\prime}}.$ (329)

Further,

$\displaystyle P_{n,r,\bm{p}}((w-1,w+1])]$ $\displaystyle\leq
P_{n,r,\bm{p}}((w-1,w])+P_{n,r,\bm{p}}((w,\infty))$ (330) $\displaystyle\leq
Q((w-1,w])+\frac{1}{2}-P_{n,r,\bm{p}}([0,w])$ (331) $\displaystyle\leq
Q((w-1,w])+\frac{1}{2}-\left(Q([0,w])-\varepsilon w\right)$ (332)
$\displaystyle=\varepsilon w+Q((z,\infty))$ (333)
$\displaystyle\leq\varepsilon
w+\frac{\eta}{12\beta_{1}\ell_{\alpha}z^{\alpha}}$ (334)
$\displaystyle\leq\frac{\eta}{6\beta_{1}\ell_{\alpha}z^{\alpha}},$ (335)

where the last inequality follows by (278). Hence, the integral in (312) is
upper bounded by

$\frac{2^{\alpha}}{3\beta_{1}\ell_{\alpha}w^{\alpha-\gamma^{\prime}}}\cdot\eta\leq\frac{\eta}{6},$
(336)

where the last inequality follows since $w\geq z_{\min}$ (see (245)). Thus, we
have shown that (311) holds, which when combined with (310) gives (298).

Combining (285), (286), and (298) gives, in view of (284), the desired
inequality (269):

$\sup_{|a|\leq
1}D(f_{n,r,\bm{p}}\|T_{a}f_{n,r,\bm{p}})\leq\text{KL}^{\star}+\delta.$ (337)

Recall that we showed in (268) that

$\mathbb{E}_{f_{n,r,\bm{p}}}[c]\leq C+\eta.$ (338)

To sum up, we make the dependence on $C$ explicit in the optimal values, i.e.,
we write $\textup{KL}^{\star}(C)$, $\textup{KL}_{n,N,r}^{\star}(C)$, and
$\textup{KL}_{\text{Cactus}}^{\star}(C)$. What we have shown above yields that

$\textup{KL}_{n,N,r}^{\star}(C+\eta)\leq\textup{KL}^{\star}(C)+\delta.$ (339)

Consider the values

$\textup{KL}_{\textup{Cactus}}^{\circ}(C):=\inf_{(n,N,r)\in\mathbb{N}^{2}\times(0,1)}\textup{KL}_{n,N,r}^{\star}(C),$
(340)

so (as defined by (21) in the statement of the theorem)
$\textup{KL}_{\text{Cactus}}^{\star}(C)=\lim_{\eta\to
0^{+}}\textup{KL}_{\text{Cactus}}^{\circ}(C+\eta)$. We conclude that

$\textup{KL}^{\star}(C+\eta)\leq\textup{KL}_{\textup{Cactus}}^{\circ}(C+\eta)\leq\textup{KL}^{\star}(C)+\delta.$
(341)

Taking $\delta\to 0^{+}$, we have

$\textup{KL}^{\star}(C+\eta)\leq\textup{KL}_{\text{Cactus}}^{\circ}(C+\eta)\leq\textup{KL}^{\star}(C).$
(342)

Finally, being the infimum of a jointly convex function over a convex set, the
function $C\mapsto\textup{KL}^{\star}(C)$ is convex. Since it is also finite,
we see that $\textup{KL}^{\star}(C)$ is continuous over $(0,\infty)$. Thus,
taking $\eta\to 0^{+}$, we see that

$\textup{KL}_{\text{Cactus}}^{\star}(C)=\textup{KL}^{\star}(C),$ (343)

completing the proof of the theorem.

## References

  * [1] W. Alghamdi, S. Asoodeh, F. Calmon, O. Kosut, L. Sankar, and F. Wei, “Schrödinger mechanisms: Optimal differential privacy mechanisms for small sensitivity,” 2022. [Online]. Available: https://github.com/WaelAlghamdi/DP-Schrodinger
  * [2] Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_. ACM, 2014, pp. 1054–1067.
  * [3] Differential privacy team Apple, “Learning with privacy at scale,” 2017.
  * [4] D. Kifer, S. Messing, A. Roth, A. Thakurta, and D. Zhang, “Guidelines for implementing and auditing differentially private systems,” _ArXiv_ , vol. abs/2002.04049, 2020.
  * [5] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Proc. Theory of Cryptography (TCC)_ , Berlin, Heidelberg, 2006, pp. 265–284.
  * [6] A. Ghosh, T. Roughgarden, and M. Sundararajan, “Universally utility-maximizing privacy mechanisms,” _SIAM Journal on Computing_ , vol. 41, no. 6, pp. 1673–1693, 2012.
  * [7] M. Gupte and M. Sundararajan, “Universally optimal privacy mechanisms for minimax agents,” in _Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems_ , 2010, p. 135–146.
  * [8] Q. Geng and P. Viswanath, “The optimal noise-adding mechanism in differential privacy,” _IEEE Transactions on Information Theory_ , vol. 62, no. 2, pp. 925–951, 2015.
  * [9] Q. Geng, P. Kairouz, S. Oh, and P. Viswanath, “The staircase mechanism in differential privacy,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 9, no. 7, pp. 1176–1184, 2015.
  * [10] J. Soria-Comas and J. Domingo-Ferrer, “Optimal data-independent noise for differential privacy,” _Information Sciences_ , vol. 250, no. Complete, pp. 200–214, 2013.
  * [11] Q. Geng and P. Viswanath, “Optimal noise adding mechanisms for approximate differential privacy,” _IEEE Transactions on Information Theory_ , vol. 62, no. 2, pp. 952–969, 2016.
  * [12] Q. Geng, W. Ding, R. Guo, and S. Kumar, “Tight analysis of privacy and utility tradeoff in approximate differential privacy,” in _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, S. Chiappa and R. Calandra, Eds., vol. 108, 2020, pp. 89–99.
  * [13] ——, “Optimal noise-adding mechanism in additive differential privacy,” in _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and M. Sugiyama, Eds., vol. 89. PMLR, 16–18 Apr 2019, pp. 11–20. [Online]. Available: https://proceedings.mlr.press/v89/geng19a.html
  * [14] C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in _51st Annual Symposium on Foundations of Computer Science_. IEEE, 2010, pp. 51–60.
  * [15] J. Murtagh and S. Vadhan, “The complexity of computing the optimal composition of differential privacy,” in _Proc. Int. Conf. Theory of Cryptography_ , 2016, pp. 157–175.
  * [16] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” in _Proceedings of the 32nd International Conference on Machine Learning_ , F. Bach and D. Blei, Eds., vol. 37, 2015, pp. 1376–1385.
  * [17] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016, pp. 308–318.
  * [18] S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar, “Three variants of differential privacy: Lossless conversion and applications,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 208–222, 2021.
  * [19] S. Meiser and E. Mohammadi, “Tight on budget? tight bounds for r-fold approximate differential privacy,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’18, 2018, p. 247–264.
  * [20] J. Dong, A. Roth, and W. J. Su, “Gaussian differential privacy,” _arXiv preprint arXiv:1905.02383_ , 2019.
  * [21] S. Gopi, Y. T. Lee, and L. Wutschitz, “Numerical composition of differential privacy,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * [22] A. Koskela, J. Jälkö, and A. Honkela, “Computing tight differential privacy guarantees using fft,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 2560–2569.
  * [23] A. Koskela, J. Jälkö, L. Prediger, and A. Honkela, “Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft,” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Banerjee and K. Fukumizu, Eds., vol. 130. PMLR, 13–15 Apr 2021, pp. 3358–3366. [Online]. Available: https://proceedings.mlr.press/v130/koskela21a.html
  * [24] Y. Zhu, J. Dong, and Y.-X. Wang, “Optimal accounting of differential privacy via characteristic function,” _arXiv preprint arXiv:2106.08567_ , 2021.
  * [25] E. Çınlar, _Probability and Stochastics_. New York, NY: Springer, 2011.
  * [26] TensorFlow-Privacy tutorial, https://github.com/tensorflow/privacy.git/.
  * [27] E. Posner, “Random coding strategies for minimum entropy,” _IEEE Transactions on Information Theory_ , vol. 21, no. 4, pp. 388–391, 1975.
  * [28] Y. Polyanskiy, “Lecture notes on information theory,” 2019. [Online]. Available: http://people.lids.mit.edu/yp/homepage/data/itlectures_v5.pdf
  * [29] V. I. Bogachev, _Measure theory_. Berlin: Springer, 2007.