\appendix

\section{Technical appendices}

\subsection{Proof of Lemma~\ref{lemma:nice-families-l1-differentiable}}
\label{sec:proof-nice-families-l1-differentiable}

By the triangle inequality, we have
\begin{align}
  &\int |p_{\theta_0 + h} - p_{\theta_0} - 
  h^T \dot{\ell}_{\theta_0} p_{\theta_0}|d\mu \nonumber \\
  &\leq \underbrace{\int \left|p_{\theta_0 + h} - p_{\theta_0} - 
    \half h^T \dot{\ell}_{\theta_0} \sqrt{p_{\theta_0}}
    ({\sqrt{p_{\theta_0 + h}} + \sqrt{p_{\theta_0}}})\right|
    d\mu}_{\defeq I_1(h; \theta_0)}
  + \underbrace{\int \left| \half h^T \dot{\ell}_{\theta_0} 
    \sqrt{p_{\theta_0}} (\sqrt{p_{\theta_0 + h}} - \sqrt{p_{\theta_0}})\right|
    d\mu}_{\defeq I_2(h; \theta_0)}.
  \nonumber 
\end{align}
We show that each of the integral terms $I_1$ and $I_2$ are both
$o(\norm{h})$ as $h \to 0$.
By algebraic 
manipulation and the Cauchy--Schwarz inequality,
\begin{align*}
  I_1(h; \theta_0) &= \int |\sqrt{p_{\theta_0 + h}} + 
  \sqrt{p_{\theta_0}}| \cdot \left|\sqrt{p_{\theta_0 + h}} - 
  \sqrt{p_{\theta_0}} - \half h^T \dot{\ell}_{\theta_0} 
  \sqrt{p_{\theta_0}}\right| d\mu \nonumber \\
  &\leq \left(\int |\sqrt{p_{\theta_0 + h}} + \sqrt{p_{\theta_0}}|^2 
  d\mu \right)^\half  \cdot \left(\int \left|\sqrt{p_{\theta_0 + h}} - 
  \sqrt{p_{\theta_0}} - \half h^T \dot{\ell}_{\theta_0} 
  \sqrt{p_{\theta_0}}\right|^2 d\mu\right)^\half
\end{align*}
Jensen's inequality gives
$\int |\sqrt{p_{\theta_0 + h}} + \sqrt{p_{\theta_0}}|^2 d\mu
\leq 2 \int (p_{\theta_0 + h} + p_{\theta_0}) d\mu = 2$.
The assumption
that $\mc{P}$ is QMD at $\theta_0$ immediately yields
$I_1(h; \theta_0) = o(\norm{h})$.
To bound $I_2$, we again apply the Cauchy--Schwarz inequality, obtaining
\begin{equation*}
  2 I_2 (h; \theta_0) \leq \left(\int |h^T \dot{\ell}_{\theta_0}
  \sqrt{p_{\theta_0}} |^2 d\mu \right)^\half 
  \cdot  \left(\int |\sqrt{p_{\theta_0 + h}} - 
  \sqrt{p_{\theta_0}}|^2 d\mu \right)^\half
\end{equation*}
Since $\mc{P}$ is QMD at $\theta_0$, we have $\int |\sqrt{p_{\theta_0 + h}}
- \sqrt{p_{\theta_0}}|^2 d\mu = \int |\half h^T \dot{\ell}_{\theta_0}
\sqrt{p_{\theta_0}} |^2 d\mu + o(\norm{h}^2) = O(\norm{h}^2)$
(see~\cite[Ch.~7.2]{VanDerVaart98}).  Thus $I_2(h; \theta_0) = O(\norm{h}^2)$,
givin the lemma.

\subsection{Proof of Proposition~\ref{proposition:achievable}}
\label{sec:proof-achievable}

Let $P_0$ and $P_1$ be distributions on $\mc{X}$, each with
densities $p_0,p_1$ according to some base measure $\mu$.
Let $\theta_a = \theta(P_a)$, and consider the problem of privately
collecting observations and deciding whether $\theta = \theta_0$ or $\theta
= \theta_1$. We define a randomized-response based estimator
for this problem using a simple hypothesis test.

Define the ``acceptance'' set
\begin{equation*}
  A \defeq \left\{x \in \mc{X} \mid p_0(x) > p_1(x) \right\}.
\end{equation*}
Then we have $P_0(A) - P_1(A) = \tvnorm{P_0 - P_1}$ by a
calculation.


Now, consider the following estimator:
for each $X_i$, define
\begin{equation*}
  T_i = \indic{X_i \in A}
  ~~ \mbox{and} ~~
  Z_i \mid \{T_i = t\}
  = \begin{cases}
    1 & \mbox{with~probability~}
   (e^\diffp + 1)^{-1}\left(e^{\diffp} t + 1-t\right) \\
    0 & \mbox{with~probability~}
   (e^{-\diffp} + 1)^{-1}\left(e^{-\diffp} t + 1-t\right)
  \end{cases}
\end{equation*}
Then the channel $\channel(\cdot \mid X_i)$ for $Z_i \mid X_i$ is
$\diffp$-differentially-private by inspection, and
setting $\delta_\diffp = \frac{e^\diffp}{1 + e^\diffp} - \half$,
we have
\begin{equation*}
  \E_0[Z_i]
  = \frac{1 + \delta_\diffp}{2} P_0(A)
  + \frac{1 - \delta_\diffp}{2} P_0(A^c)
  = \frac{1- \delta_\diffp}{2} + \delta_\diffp P_0(A)
  ~~ \mbox{and} ~~
  \E_1[Z_i]
  = \frac{1- \delta_\diffp}{2} + \delta_\diffp P_1(A)


\end{equation*}
while $Z_i \in \{0, 1\}$.
Now, define the statistic
\begin{equation*}
  K_n \defeq \frac{1}{\delta_\diffp}
  \left(\frac{1}{n} \sum_{i = 1}^n Z_i - \frac{1-\delta_\diffp}{2}\right),
\end{equation*}
so that $\E_0[K_n] = P_0(A)$ and $\E_1[K_n] = P_1(A)$.
We define our estimator to be
\begin{equation*}
  \what{\theta} \defeq \begin{cases}
    \theta_0 & \mbox{if~} K_n \ge \frac{P_0(A) + P_1(A)}{2} \\
    \theta_1 & \mbox{if~} K_n < \frac{P_0(A) + P_1(A)}{2}. \end{cases}
\end{equation*}

We now analyze the performance of our randomized choice $\what{\theta}$.  By
construction of the acceptance set $A$, note that
\begin{equation*}
  \frac{P_0(A) + P_1(A)}{2}
  = P_0(A) + \frac{P_1(A) - P_0(A)}{2}
  = P_0(A) - \half \tvnorm{P_1 - P_0}
  = P_1(A) + \half \tvnorm{P_1 - P_0}.
\end{equation*}
By Hoeffding's inequality, we thus have
\begin{equation*}
  \max\left\{P_0\left(K_n \le \frac{P_0(A) + P_1(A)}{2}
  \right),
  P_1\left(K_n \ge \frac{P_0(A) + P_1(A)}{2}\right)
  \right\}
  \le \exp\left(- \frac{n \delta_\diffp^2 \tvnorm{P_0 - P_1}^2}{2}\right).
\end{equation*}
In particular, we have
\begin{equation*}
  \E_0[\loss(\what{\theta}, P_0)]
  + \E_1[\loss(\what{\theta}, P_1)]
  \le \left[\loss(\theta_1, P_0)
    + \loss(\theta_0, P_1)\right]
  \exp\left(-\frac{n \delta_\diffp^2 \tvnorm{P_0 - P_1}^2}{2}\right).
\end{equation*}
Using the reverse triangle condition~\ref{cond:reverse-triangle} on the
distance function's growth, we obtain
\begin{align}
  \nonumber
  \E_0[\loss(\what{\theta}, P_0)]
  + \E_1[\loss(\what{\theta}, P_1)]
  & \le
  \Creverse \lossdist(P_0, P_1)
  \exp\left(-\frac{n \delta_\diffp^2 \tvnorm{P_0 - P_1}^2}{2}
  \right) \\
  & \le \Creverse \sup_{P_1 \in \mc{P}}
  \lossdist(P_0, P_1)
  \exp\left(-\frac{n \delta_\diffp^2 \tvnorm{P_0 - P_1}^2}{2}
  \right) \nonumber \\
  & = \Creverse \sup_{r \ge 0}
  \left\{\modcont(r; P_0)
  \exp\left(-\frac{n \delta_\diffp^2 r^2}{2}\right)\right\}.
  \label{eqn:minimax-upper-exponential}
\end{align}

The bound~\eqref{eqn:minimax-upper-exponential} is the key inequality.
Let us substitute $\tau^2 = \frac{n r^2 \delta_\diffp^2}{2}$,
or $r = \frac{\sqrt{2} \tau}{\delta_\diffp \sqrt{n}}$ in the expression,
which yields
\begin{equation*}
  \E_0[\loss(\what{\theta}, P_0)]
  + \E_1[\loss(\what{\theta}, P_1)]
  \le \Creverse \sup_{\tau \ge 0}
  \left\{ \modcont\left(\frac{\sqrt{2} \tau}{\delta_\diffp \sqrt{n}};
  P_0\right) e^{-\tau^2}\right\}.
\end{equation*}
For all $\tau \le 1$, this gives the result; otherwise, we use
the growth condition on the modulus of continuity to obtain
\begin{equation*}
  \E_0[\loss(\what{\theta}, P_0)]
  + \E_1[\loss(\what{\theta}, P_1)]
  \le \Creverse \modcont\left(\frac{\sqrt{2}}{
    \delta_\diffp \sqrt{n}}; P_0\right)
  \Cgrow^\alpha \sup_{\tau \ge 1}
  \tau^\alpha e^{-\tau^2}
\end{equation*}
Noting that $\sup_{\tau \ge 0}
\tau^\alpha e^{-\tau^2} = (\alpha/2)^{\alpha/2} e^{-\alpha/2}$ gives
the result.


\subsection{Proof of
  Proposition~\ref{proposition:uniform-achievability-one-dim-exp}}
\label{sec:proof-uniform-achievability-one-dim-exp}


We require one additional piece of notation before we begin the proof.
Let $W_i = Z_i - V_i$ be the error in the private version of the
quantity $V_i$, so that $\E[W_i \mid V_i] = 0$, and
\begin{equation*}
  W_i = \begin{cases}
    \frac{2}{e^\diffp - 1} V_i
    - \frac{1}{e^\diffp - 1}
    & \mbox{w.p.}~ \frac{e^\diffp}{e^\diffp + 1} \\
    \frac{-2 e^\diffp}{e^\diffp - 1} V_i
    + \frac{e^\diffp}{e^\diffp - 1}
    & \mbox{w.p.}~ \frac{1}{e^\diffp + 1}.
  \end{cases}
\end{equation*}
Recall our definitions of $V_i = \indics{T(X_i) \ge \what{T}_n}$ and $Z_i$ as
the privatized version of $V_i$. Letting $\wb{Z}_n = \frac{1}{n} \sum_{i =
  1}^n Z_i$, and similarly for $\wb{V}_n$ and $\wb{W}_n$, recall also the
definition of the random variable $G_n \defeq \Psi(\what{T}_n, \theta_0) =
P_{\theta_0}(T(X) \ge \what{T}_n)$.
By mimicking the delta method, we will show that
\begin{equation}
  \sqrt{n}(\what{\theta}_n - \theta_0)
  = 2 \information[\theta_0]^{-1}
  \cdot \sqrt{n} \left(\wb{V}_n - G_n + \wb{W}_n \right) + o_P(1).
  \label{eqn:delta-method-expfam}
\end{equation}
Deferring the proof of the expansion~\eqref{eqn:delta-method-expfam},
let us show how it implies the proposition.


First, with our definition of the $W_i$, we have
\begin{equation*}
  \var(W_i \mid V_i) =
  \E[W_i^2 \mid V_i]
  = \frac{e^\diffp }{(e^\diffp - 1)^2}
  = \delta_\diffp^{-2},
\end{equation*}
so that $\wb{W}_n = \frac{1}{n} \sum_{i = 1}^n W_i$ satisfies $\sqrt{n}
\wb{W}_n \cd \normal(0, \delta_\diffp^{-2})$ by the Lindeberg CLT.  Thus,
assuming the expansion~\eqref{eqn:delta-method-expfam}, it remains to show
the weak convergence result
\begin{equation}
  \label{eqn:asymp-Z-n}
  \frac{\sqrt{n}\left(\wb{V}_n - G_n\right)}{G_n(1-G_n)} \cd \normal(0, 1).
\end{equation}
where $G_n = \Psi(\what{T}_n, \theta_0)$.

By definition, the $\{X_i\}_{i=1}^n$ are independent of $\what{T}_n$, and
hence
\begin{equation*}
  \E [V_i \mid \what{T}_n]= \Psi(\what{T}_n, \theta_0)  = G_n~~\text{and}~~ 
  \var(V_i \mid \what{T}_n) = 
  \Psi(\what{T}_n, \theta_0)(1-\Psi(\what{T}_n, \theta_0))
  = G_n(1-G_n).
\end{equation*}
The third central moments of the $V_i$ conditional on $\what{T}_n$
have the bound
\begin{equation*}
  \E \left[ \left|V_i - \E [V_i \mid \what{T}_n]\right|^3 \mid \what{T}_n \right]
  \leq  \Psi(\what{T}_n, \theta_0)(1-\Psi(\what{T}_n, \theta_0))
  = G_n(1-G_n).
\end{equation*}
Thus, we may apply the Berry-Esseen Theorem 
\cite[Thm 11.2.7]{LehmannRo05} to obtain
\begin{equation*}
  \sup_{t\in \R} 
  \left|\P\left(\frac{\sqrt{n}\left(\wb{V}_n - G_n\right)}{G_n(1- G_n)}
  \leq t \mid \what{T}_n\right)
  - \Phi(t) \right|
  \leq U_n \defeq \frac{1}{\sqrt{n G_n(1- G_n)}} \wedge 2.
\end{equation*}
Jensens's inequality then implies
\begin{equation*}
  \sup_{t \in \R}
  \left|\P\left(\frac{\sqrt{n}\left(\wb{V}_n - G_n\right)}{G_n(1- G_n)}
  \leq t\right) - \Phi(t)\right|
  \leq 
  \E\left[\sup_{t \in \R} \left|
    \P\left(\frac{\sqrt{n}\left(\wb{V}_n - G_n\right)}{G_n(1- G_n)} \leq t \mid \what{T}_n\right)
    - \Phi(t) \right|\right]
  \leq \E [U_n]
\end{equation*}


To show the convergence~\eqref{eqn:asymp-Z-n}, it is thus sufficient to show
that $\E [U_n] \to 0$ as $n \uparrow \infty$. To that end, the
following lemma on the behavior of $\Psi(t, \theta)
= P_\theta(T(X) \ge t)$ is useful.
\begin{lemma}
  \label{lemma:overlap-nonzero-lemma}
  Let $t_0 = \E_{\theta_0}[T(X)]$ and
  assume that $\var_{\theta_0} (T(X)) > 0$. Then there exist
  $\epsilon > 0$ and $c \in (0, \half)$ such that
  if $t \in [t_0 \pm \epsilon]$ and
  $\theta \in [\theta_0 \pm \epsilon]$, then
  $\Psi(t, \theta) \in [c, 1-c]$.
\end{lemma}
\begin{proof}
  By the dominated convergence theorem
  and our assumption that
  $\var_{\theta_0}(T(X)) > 0$,
  where $t_0 = \E_{\theta_0}[T(X)]$,
  we have
  \begin{equation*}
    \liminf_{t \uparrow t_0}
    \Psi(t, \theta_0)
    = P_{\theta_0}(T(X) \ge t_0) \in (0, 1)
    ~~ \mbox{and} ~~
    \limsup_{t \downarrow t_0}
    \Psi(t, \theta_0)
    = P_{\theta_0}(T(X) > t_0) \in (0, 1).
  \end{equation*}
  The fact that
  $t \mapsto \Psi(t, \theta_0)$ is non-increasing implies
  that for some $\epsilon_1 > 0, c \in (0, \frac{1}{4})$,
  we have
  $\Psi(t, \theta_0) \in [2c, 1-2c]$ for
  $t \in [t_0 - \epsilon_1, t_0 + \epsilon_1]$.
  Fix this $\epsilon_1$ and $c$.
  By~\cite[Thm 2.7.1]{LehmannRo05}, 
  we know that any $t \in \R$,
  the function $\theta \mapsto \Psi(t, \theta)$ is continuous and
  non-decreasing. Thus for any
  $\epsilon_2 > 0$, we have
  \begin{equation*}
    \Psi(t_0 + \epsilon_1, \theta_0 - \epsilon_2)
    \le \Psi(t, \theta)
    \le \Psi(t_0 - \epsilon_1, \theta_0 + \epsilon_2)
    ~~ \mbox{for}~~
    (t, \theta) \in [t_0 \pm \epsilon_1] \times [\theta_0 \pm \epsilon_2].
  \end{equation*}
  Using the continuity of $\theta \mapsto \Psi(t, \theta)$, we may
  choose $\epsilon_2 > 0$ small enough that
  \begin{equation*}
    \Psi(t, \theta) \in [ c, 1- c]~~\mbox{for}~~
    (t, \theta) \in \{t_0 - \epsilon_1, t_0 + \epsilon_1\}
    \times \{\theta_0 - \epsilon_2, \theta_0 + \epsilon_2\}.
  \end{equation*}
  The lemma 
  follows by taking $\epsilon = \epsilon_1 \wedge \epsilon_2$. 
\end{proof}

As $\var_{\theta_0} (T(X)) > 0$ by assumption,
Lemma~\ref{lemma:overlap-nonzero-lemma} and the
fact that $\what{T}_n \cp t_0$ imply
\begin{equation}
  \label{eqn:range-of-G-n}
  G_n \defeq \Psi(\what{T}_n, \theta_0)
  = P_{\theta_0}(T(X) \ge \what{T}_n)\in [c+o_P(1), 1-c + o_P(1)].
\end{equation} 
The bounds~\eqref{eqn:range-of-G-n} imply
that $G_n(1-G_n) \geq c(1-c) + o_P(1)$, so
$U_n \cp 0$.
By construction $|U_n| \leq 2$ for all $n$,
so the bounded convergence theorem implies $\E [U_n] \rightarrow 0$,
which was what we required to show the weak convergence
result~\eqref{eqn:asymp-Z-n}. 
The joint convergence in the proposition follows because
$\wb{W}_n$ and $\wb{V}_n - G_n$ are conditionally uncorollated.


\paragraph{The delta method expansion}
We now return to demonstrate the claim~\eqref{eqn:delta-method-expfam}.  For
$p \in [0, 1]$, recall the
definition~\eqref{eqn:private-expfam-estimator}
of the function $H$, and define
\begin{equation}
  \label{eqn:def-H-n}
  H_n(p)
  \defeq H(p, \what{T}_n)
  = \inf \left\{\theta\in \R \mid P_\theta(T(X) \ge \what{T}_n) \ge p\right\},
\end{equation}
where the value is $-\infty$ or $+\infty$ for $p$ below or above the range
of $\theta \mapsto P_\theta(T(X) \ge \what{T}_n)$, respectively.  Then
$\what{\theta}_n = H_n(\wb{Z}_n)$ by
construction~\eqref{eqn:private-expfam-estimator}.  We would like to apply
Taylor's theorem and the inverse function theorem to $\what{\theta}_n -
\theta_0 = H_n(\wb{Z}_n) - \theta_0$, but this requires a few additional
steps.

By the inverse function theorem, $p \mapsto H_n(p)$ is
$\mc{C}^\infty$ on the interval $(\inf_\theta \Psi(\what{T}_n, \theta),
\sup_\theta \Psi(\what{T}_n, \theta))$, and letting
\begin{equation*}
  \dot{\Psi}_\theta(t, \theta) = \frac{\partial}{\partial \theta}
  \Psi(t, \theta)
  = \E_\theta[\indic{T(X) \ge t} (T(X) - A'(\theta))]
\end{equation*}
be the derivative of $P_\theta(T(X) \ge t)$ with respect to $\theta$, we
have $H_n'(p) = \dot{\Psi}_\theta(\what{T}_n, H_n(p))^{-1}$ whenever $p$ is
interior to the range of $\theta \mapsto P_\theta(T(X) \ge \what{T}_n)$.  To
show that $\wb{Z}_n$ is (typically) in this range, we require a bit of
analysis on $\dot{\Psi}_\theta$.
\begin{lemma}
  \label{lemma:continuity-expfam}
  The function $(t, \theta) \mapsto \dot{\Psi}_\theta(t, \theta)
  = \E_{\theta}[\indic{T(X) \ge t} (T(X) - A'(\theta))]$
  is continuous at $(t_0, \theta_0)$, where $t_0 =
  \E_{\theta_0}[T(X)] = A'(\theta_0)$.
\end{lemma}
\noindent
To avoid disrupting the flow, we defer the proof to
Section~\ref{sec:proof-continuity-expfam}.

Now, we have that $\dot{\Psi}_{\theta}(t_0, \theta_0) = \half
\E_{\theta_0}[|T(X) - t_0|] > 0$, so Lemma~\ref{lemma:continuity-expfam}
implies there exists $\epsilon > 0$ such that
\begin{equation}
  \label{eqn:positive-expfam-deriv}
  \inf_{|t - t_0| \le \epsilon
    ,|\theta - \theta_0| \le \epsilon}
  \dot{\Psi}_{\theta}(t, \theta) \ge c > 0
\end{equation}
for some constant $c$. Thus, we obtain that
\begin{align}
  \nonumber
  \P\left(\wb{Z}_n \not \in \range(\Psi(\what{T}_n, \cdot))\right)
  & \le \P\left(\wb{Z}_n \not \in \range(\Psi(\what{T}_n, \cdot)),
  \what{T}_n \in [t_0 \pm \epsilon] \right)
  + \P\left(\what{T}_n \not \in [t_0 \pm \epsilon]\right) \\
  & \stackrel{(i)}{\le} \P\left(\wb{Z}_n \not \in
  [\Psi(\what{T}_n, \theta_0)
    \pm c \epsilon] \right)
  + o(1)
  \to 0,
  \label{eqn:z-in-range}
\end{align}
where inequality~$(i)$ follows because
$\range(\Psi(t, \cdot)) \supset [\Psi(t, \theta_0) \pm c \epsilon]$
for all $t$ such that $|t - t_0| \le \epsilon$
by condition~\eqref{eqn:positive-expfam-deriv}, and the
final convergence because $\wb{Z}_n - \Psi(\what{T}_n, \theta_0)
\cp 0$ and $\what{T}_n$ is consistent for $t_0$.

We recall also that for
any fixed $t$, $\theta \mapsto \Psi(t, \theta)$ is analytic on the interior
of the natural parameter space and strictly increasing at all $\theta$ for
which $\Psi(t, \theta) \in (0, 1)$ (cf.~\cite[Thm.~2.7.1,
  Thm.~3.4.1]{LehmannRo05}). Thus,
\begin{equation*}
  H_n(\Psi(\what{T}_n, \theta)) = \theta
  ~~ \mbox{whenever} ~~
  \Psi(\what{T}_n, \theta) \in (0, 1).
\end{equation*}
As $G_n = \Psi(\what{T}_n, \theta_0)
\in [c + o_P(1), 1- c+o_P(1)]$ by definition~\eqref{eqn:range-of-G-n} of
$G_n$, we obtain
\begin{equation*}
  \P \left(H_n(\Psi(\what{T}_n, \theta_0)) \neq \theta_0\right) \to 0. 
\end{equation*}
Now, by the differentiability of $H_n$ on the interior of its
domain (i.e.\ the range of $\Psi(\what{T}_n, \cdot)$), we use 
the convergence~\eqref{eqn:z-in-range}
and Taylor's intermediate value theorem to obtain that for
some $p_n$ between $\wb{Z}_n$ and $\Psi(\what{T}_n, \theta_0)$, we have
\begin{align}
  \nonumber \sqrt{n}(\what{\theta}_n - \theta_0)
  & = \sqrt{n} (\what{\theta}_n - H_n(\Psi(\what{T}_n, \theta_0)))
  + o_P(1) \\
  & = H_n'(p_n) \sqrt{n} \left(\wb{Z}_n - \Psi(\what{T}_n, \theta_0)
  \right) + o_P(1) \nonumber \\
  & = \dot{\Psi}_\theta(\what{T}_n, H_n(p_n))^{-1}
  \sqrt{n} \left(\wb{Z}_n - \Psi(\what{T}_n, \theta_0)
  \right) + o_P(1)
  \label{eqn:expfam-almost-done}
\end{align}
as $p_n \in \interior \dom H_n$ with high probability
by~\eqref{eqn:z-in-range}.

It remains to show that $H_n(p_n) \cp \theta_0$. To see this,
note that whenever $\what{T}_n \in [t_0 \pm \epsilon]$, 
the growth condition~\eqref{eqn:positive-expfam-deriv} implies
that
\begin{align*}
  \Psi(\what{T}_n,
  \theta_0 + \epsilon)
  = P_{\theta_0 + \epsilon}(T(X) \ge \what{T}_n)
  & \ge P_{\theta_0}(T(X) \ge \what{T}_n)
  + c \epsilon
  = \Psi(\what{T}_n, \theta_0) + c \epsilon \\
  \Psi(\what{T}_n,
  \theta_0 - \epsilon)
  = P_{\theta_0 - \epsilon}(T(X) \ge \what{T}_n)
  & \le P_{\theta_0}(T(X) \ge \what{T}_n)
  - c \epsilon
  = \Psi(\what{T}_n, \theta_0) - c \epsilon,
\end{align*}
and thus 
\begin{equation*}
  \P(|H_n(p_n) - \theta_0| \ge \epsilon)
  \le \P(|\wb{Z}_n - \Psi(\what{T}_n, \theta_0)| \ge c \epsilon)
  + \P(|\what{T}_n - t_0| \ge \epsilon)
  \to 0.
\end{equation*}
We have the convergence $\dot{\Psi}_\theta(\what{T}_n, H_n(p_n)) \cp \half
\E_{\theta_0}[|T(X) - A'(\theta_0)|] = \half \information[\theta_0]$ by the
continuous mapping theorem, and Slutsky's theorem applied to
Eq.~\eqref{eqn:expfam-almost-done} gives the delta-method
expansion~\eqref{eqn:delta-method-expfam}.

\subsubsection{Proof of Lemma~\ref{lemma:continuity-expfam}}
\label{sec:proof-continuity-expfam}

We have
\begin{align*}
  \dot{\Psi}_\theta(t_0, \theta_0)
  - \dot{\Psi}_\theta(t, \theta)
  & = \E_{\theta_0}[\indic{T(X) \ge t_0}
    (T(X) - A'(\theta_0))]
  - \E_\theta[\indic{T(X) \ge t}
    (T(X) - A'(\theta))] \\
  & \stackrel{(i)}{=} \E_{\theta_0}\left[
    \hinge{T(X) - t_0}\right]
  - \E_\theta[\indic{T(X) \ge t}
    (T(X) - t + t - A'(\theta))] \\
  & = \E_{\theta_0}\left[\hinge{T(X) - t_0}\right]
  - \E_\theta\left[\hinge{T(X) - t}\right]
  + P_\theta(T(X) \ge t) (t - A'(\theta)) \\
  & \stackrel{(ii)}{\in} \E_{\theta_0}\left[\hinge{T(X) - t_0}\right]
  - \E_\theta\left[\hinge{T(X) - t_0}\right]
  \pm |t - t_0| \pm |t - A'(\theta)|,
\end{align*}
where step~$(i)$ follows because $t_0 = A'(\theta_0) = \E_{\theta_0}[T(X)]$,
while the inclusion~$(ii)$ is a consequence of the 1-Lipschitz continuity of
$t \mapsto \hinge{t}$.  Now we use the standard
facts that $A(\theta)$ is analytic in $\theta$
and that $\theta \mapsto \E_\theta[f(X)]$ is continuous for any $f$
(cf.~\cite[Thm.~2.7.1]{LehmannRo05}) to see that for
any $\epsilon > 0$, we can choose $\delta > 0$ such that
$|t - t_0| \le \delta$ and $|\theta - \theta_0| \le \delta$ imply
\begin{equation*}
  |t - t_0| \le \epsilon, ~~
  |t - A'(\theta)| \le \epsilon, ~~ \mbox{and} ~~
  \left|
  \E_{\theta_0}\left[\hinge{T(X) - t_0}\right]
  - \E_\theta\left[\hinge{T(X) - t_0}\right]\right| \le \epsilon.
\end{equation*}
This gives the result.

\subsection{Proof of Lemma~\ref{lemma:mis-expfam-growth}}
\label{sec:proof-mis-expfam-growth}

Indeed, for $P \in \mc{P}$ let
$\mu(P) = \E_P[X]$
and
$\mu_0 = \E_{P_0}[X]$, and define the diameter
$D \defeq \diam (\xdomain)
= \sup\{\ltwo{x_1-x_2} \mid x_1, x_2 \in \xdomain\}$. 
As $A$ and $A^*$ are $\mc{C}^\infty$,
if we define the remainder
$\res(\mu; \mu') = \grad A^*(\mu) - \grad A^*(\mu')
- \grad^2 A^*(\mu') (\mu - \mu')$, then
there exists $G < \infty$ such that
\begin{equation*}
  |\res(\mu; \mu')|
  \le \half G \ltwo{\mu - \mu'}^2
  ~~ \mbox{for~all~} \mu, \mu' \in \xdomain.
\end{equation*}


Now, define the constant
\begin{equation*}
  K \defeq \sup_{x \in \mc{X}} \ltwo{\nabla^2 A^*(\mu_0)(x - \mu_0)},
\end{equation*}
which is positive whenever $\mc{X}$ has at least two elements, as
$\nabla^2 A^* \succ 0$ (recall Eq.~\eqref{eqn:inverse-hessian-conjugate}).
If $K = 0$ then the example becomes trivial as $\card(\xdomain) \le 1$.
We claim that
\begin{equation}
  \delta K - 2 G^2 D^2 \delta^2
  \le \modltwo(\delta) \le
  2 \delta K
  + 2 G^2 D^2 \delta^2
  \label{eqn:modltwo-exp-mean}
\end{equation}
A Taylor approximation is useful for this result.
Define the linearized modulus
\begin{equation*}
  \modltwolin(\delta) = 
  \sup_{P \in \mc{P}} \left\{\ltwo{\grad^2 A^*(\mu_0)(\mu(P) - \mu_0)}: 
  \tvnorm{P - P_0} \le \delta\right\}
\end{equation*}
Then the remainder guarantee $\res(\mu, \mu') \le
\half G \ltwo{\mu - \mu'}^2$ implies
\begin{equation*}
  \left|\modltwo(\delta) - \modltwolin(\delta)\right|
  \le \half G \cdot \{\ltwo{\mu - \mu_0}^2 \mid \tvnorm{P-P_0}
  \le \delta\} 
  \stackrel{(i)}{\le} 2G \delta^2 K^2. 
\end{equation*}
where inequality~$(i)$ follows from Eq.~\eqref{eqn:modltwo-mean}.  The
bounds on $\delta K \le \modltwolin(\delta) \le 2 \delta K$ are immediate
consequences of inequality~\eqref{eqn:modltwo-mean}, yielding
the bounds~\eqref{eqn:modltwo-exp-mean}.

We now show how inequalities~\eqref{eqn:modltwo-exp-mean}
imply the polynomial growth condition~\ref{cond:polynomial-growth}
on $\modltwo$, that
is, that for some constant $\beta < \infty$,
\begin{equation}
  \label{eqn:goal-of-example-two}
  \sup_{c\ge 1, \delta > 0}
  \frac{\modltwo(c\delta)}{c \cdot \modltwo(\delta)}
  \le \beta.
\end{equation}
Define $\delta_0 = \frac{K}{4 G^2 D^2}$.
We consider three cases. In the first, when $\delta \ge \delta_0$,
we have for $c \ge 1$ that
\begin{equation*}
  \frac{\modltwo(c\delta)}{c \cdot \modltwo(\delta)}
  \le \frac{\modltwo(1)}{\modltwo(\delta_0)}
  \le \frac{2K + 2G^2 D^2}{\delta_0 K - 2 G^2 D^2 \delta_0^2}
  = 32 (K + G^2 D^2) \frac{G^2 D^2}{K^2}.
\end{equation*}
In the case that $\delta \le \delta_0$ and
$c\delta \le 1$, we have
$\delta K - 2 G^2 D^2 \delta^2 \ge \delta K / 2$, and
\begin{equation*}
  \frac{\modltwo(c\delta)}{c \cdot \modltwo(\delta)}
  \le \frac{2 c \delta K + 2G^2 D^2 (c\delta)^2}{c \delta K
    - 2 c G^2 D^2 \delta^2}
  \le 4 \frac{c \delta K + G^2 D^2 (c\delta)^2}{c \delta K}
  \le 4 + 4 \frac{G^2 D^2}{K},
\end{equation*}
and in the final case that $c\delta \ge 1$, we have
$\frac{1}{c} \le \delta$ and so
\begin{equation*}
  \frac{\modltwo(c\delta)}{c \cdot \modltwo(\delta)}
  \le \frac{\delta \modltwo(1)}{\modltwo(\delta)}
  \le \delta \frac{2K + 2 G^2 D^2 }{ \delta K / 2}
  = 4 + 4 \frac{G^2 D^2}{K}.
\end{equation*}
These cases combined yield
inequality~\eqref{eqn:goal-of-example-two} for large enough $\beta$,
and thus Condition~\ref{cond:polynomial-growth} holds.

\subsection{Proof of Lemma~\ref{lemma:le-cam-method}}
\label{sec:proof-le-cam-method}

Let us define the minimal loss function
\begin{equation*}
  L_{i,*}(\theta)
  \defeq \inf_{P \in \mc{P}_i} L(\theta, P).
\end{equation*}
Then by the definition of the quantity $\lossdist$ and assumption that
$\lossdist(P_0, P_1) \ge \delta$ for all $P_0 \in \mc{P}_0, P_1 \in
\mc{P}_1$, we immediately see that $L_{0,*}(\theta) + L_{1,*}(\theta) \ge
\delta$ for all $\theta$.  For any measure $\pi$ on $\mc{P}$, define $P_\pi
= \int P d\pi(P)$ to be the mixture distribution according to $\pi$.  Then
for any measures $\pi_0$ on $\mc{P}_0$ and $\pi_1$ on $\mc{P}_1$, we have
\begin{align*}
  2 \sup_{P \in \mc{P}}
  \E_P[L(\what{\theta}, P)]
  & \ge
  \int \E_P[\loss(\what{\theta}, P)] d\pi_0(P)
  + \int \E_P[\loss(\what{\theta}, P)] d\pi_1(P) \\
  & \ge \int \E_P[L_{0,*}(\what{\theta})] d\pi_0(P)
  + \int \E_P[\loss_{1,*}(\what{\theta})] d\pi_1(P) \\
  & = \E_{P_{\pi_0}}[L_{0,*}(\what{\theta})]
  + \E_{P_{\pi_1}}[L_{1,*}(\what{\theta})].
\end{align*}
Using the standard variational equality $1 - \tvnorm{P_0 - P_1} = \inf_{f
  \ge 1} \int f (dP_0 + dP_1)$,
the fact othat $L_{0,*} + L_{1,*} \ge \delta$ implies
\begin{equation*}
  2 \sup_{P \in \mc{P}}
  \E_P[L(\what{\theta}, P)]
  \ge \delta \inf_{f \ge 1}
  \left\{\E_{P_{\pi_0}}[f]
  + \E_{P_{\pi_1}}[f] \right\}
  = \delta \left(1 - \tvnorm{P_{\pi_0} - P_{\pi_1}}\right),
\end{equation*}
which is the desired result.

\subsection{Proof of Theorem~\ref{theorem:big-tensor}}
\label{sec:proof-big-tensor}

We begin with the arguments common to each result, then specializing
to prove the two inequalities claimed in the theorem.
By the convexity and tensorization properties of the KL-divergence, respectively,
we have
\begin{align}
  \nonumber
  \dkl{\marginprob_0^n}{\meanmarginprob^n}
  & \le \frac{1}{|\packset|}
  \sum_{\packval \in \packset} \dkl{\marginprob_0^n}{\marginprob_\packval^n}
  \\
  & = \frac{1}{|\packset|} \sum_{\packval \in \packset}
  \sum_{i = 1}^n \int \dkl{\marginprob_0^{(i)}(\cdot \mid z_{1:i-1})}{
    \marginprob^{(i)}_\packval(\cdot \mid z_{1:i-1})}
  d\marginprob_0(z_{1:i-1}) \nonumber \\
  & = \sum_{i = 1}^n
  \left[\frac{1}{|\packset|} \sum_{\packval \in \packset}
    \dkl{\marginprob_0^{(i)}(\cdot \mid z_{1:i-1})}{
    \marginprob^{(i)}_\packval(\cdot \mid z_{1:i-1})}
    \right]
  d\marginprob_0(z_{1:i-1}),
  \label{eqn:easy-kl-tensorize}
\end{align}
where $\marginprob^{(i)}$ denotes the distribution over $Z_i$.
We consider 
Without loss of generality, we may assume that the $Z_i$ are finitely
supported (as all $f$-divergences can be approximated by
finitely supported distributions~\cite{CoverTh06}),
and we let $\margindens$ and $\channeldens$ denote the p.m.f.s of
$\marginprob$ and $\channel$, respectively.
Then, as $X_i$ is independent of $Z_{1:i-1}$ for all $i \in \N$, we 
obtain that
\begin{equation*}
  \margindens_\packval(z_i \mid z_{1:i-1})
  = \int \channeldens(z_i \mid x_i, z_{1:i-1}) dP_\packval(x_i
  \mid z_{1:i-1})
  = \int \channeldens(z_i \mid x_i, z_{1:i-1}) dP_\packval(x_i).
\end{equation*}

Returning to expression~\eqref{eqn:easy-kl-tensorize}
and using that $\dkl{P}{Q} \le \log(1 + \dchis{P}{Q})$ for any
$P$ and $Q$ (see~\cite[Lemma 2.7]{Tsybakov09}), we obtain
\begin{align*}
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \dkl{\marginprob_0^{(i)}(\cdot \mid z_{1:i-1})}{
    \marginprob_\packval^{(i)}(\cdot \mid z_{1:i-1})}
  & \le 
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \dchis{\marginprob_0^{(i)}(\cdot \mid z_{1:i-1})}{
    \marginprob_\packval^{(i)}(\cdot \mid z_{1:i-1})}.
\end{align*}
Thus, abstracting the entire history as $\what{z}$, the theorem
reduces to proving upper bounds on the quantity
\begin{align}
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \dchis{\marginprob_0^{(i)}(\cdot \mid z_{1:i-1})}{
    \marginprob_\packval^{(i)}(\cdot \mid z_{1:i-1})}
  & = \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \sum_z \frac{(\margindens_0(z \mid \what{z})
    - \margindens_\packval(z \mid \what{z}))^2}{
    \margindens_\packval(z \mid \what{z})} \nonumber \\
  & = \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \sum_z \frac{(\int \channeldens(z \mid x, \what{z})
    (dP_0(x) - dP_\packval(x)))^2}{
    \int \channeldens(z \mid x, \what{z}) dP_\packval(x)}.
  \label{eqn:chi-square-to-bound}
\end{align}
We provide upper bounds for the quantity~\eqref{eqn:chi-square-to-bound}
in the two cases of the theorem, that is, when the channel
$\channel$ is $\diffp$-differentially private and when it is
$\diffp^2$-$\chi^2$-private. 

\paragraph{The differentially private case}
We begin with the case in which $\channeldens(z \mid x, \what{z})
/ \channeldens(z \mid x', \what{z}) \le e^\diffp$ for all
$x, x', z$, and $\what{z}$. Let
$P$ be any distribution on $\xdomain$, which we are free to choose,
and define $\margindens(z \mid \what{z})
= \int \channeldens(z \mid x, \what{z}) dP(x)$. In this case, we note that
$\int \margindens(z \mid \what{z})
(dP_0 - dP_\packval)(x) = 0$ for any $\packval \in \packset$, so that
the quantity~\eqref{eqn:chi-square-to-bound}
is equal to
\begin{align*}
  \lefteqn{\frac{1}{|\packset|}
    \sum_{\packval \in \packset}
    \sum_z \left(
    \int\frac{\channeldens(z \mid x, \what{z})
      - \margindens(z \mid \what{z})}{
      \margindens_\packval(z \mid \what{z})}
    (dP_0(x) - dP_\packval(x))
    \right)^2
    \margindens_\packval(z \mid \what{z})} \\
  & = 
  \sum_z 
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \left(
  \int\frac{\channeldens(z \mid x, \what{z})
    - \margindens(z \mid \what{z})}{
    \margindens(z \mid \what{z})}
  (dP_0(x) - dP_\packval(x))
  \right)^2
  \frac{\margindens(z \mid \what{z})}{
    \margindens_\packval(z \mid \what{z})}
  \margindens(z \mid \what{z}) \\
  & \le
  \bigg[\sum_z 
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \left(
  \int\frac{\channeldens(z \mid x, \what{z})
    - \margindens(z \mid \what{z})}{
    \margindens(z \mid \what{z})}
  (dP_0(x) - dP_\packval(x))
  \right)^2
  \margindens(z \mid \what{z})
  \bigg]
  \cdot
  \max_{\packval', z'} \frac{\margindens(z' \mid \what{z})}{
    \margindens_{\packval'}(z' \mid \what{z})}.
\end{align*}
Let $C = \max_{z,\packval} \frac{\margindens_0(z \mid \what{z})}{
  \margindens_{\packval}(z \mid \what{z})}$, which is evidently bounded by
$e^\diffp$. For any $z, \what{z}$, and $x$, we have
\begin{equation*}
  \frac{\channeldens(z \mid x, \what{z})
    - \margindens(z \mid \what{z})}{
    \margindens(z \mid \what{z})}
  \in \left[e^{-\diffp} - 1, e^\diffp - 1 \right],
\end{equation*}
so we may choose the constant $c_\diffp = \half (e^{\diffp} + e^{-\diffp}) -
1$ to see that inequality~\eqref{eqn:chi-square-to-bound} has the further
upper bound
\begin{align*}
  C \cdot \sum_z &
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \left(
  \int\left(\frac{\channeldens(z \mid x, \what{z})
    - \margindens(z \mid \what{z})}{
    \margindens(z \mid \what{z})} - c_\diffp \right)
  (dP_0(x) - dP_\packval(x))
  \right)^2
  \margindens(z \mid \what{z})
  \nonumber \\
  & \le
  \frac{C}{4} (e^{\diffp/2} - e^{-\diffp/2})^2
  \sum_z \sup_{\linf{f} \le 1}
  \frac{1}{|\packset|} \sum_{\packval \in \packset}
  \left(\int f(x) (dP_0(x) - dP_\packval(x))\right)^2
  \margindens(z \mid \what{z}) \nonumber \\
  & = \frac{C}{4} (e^{\diffp/2} - e^{-\diffp/2})^2
  \complexity_\infty(\{P_\packval\}_{\packval \in \packset}).
\end{align*}
Recalling that for our choice of $C = \max_{\packval, z}
\frac{\margindens(z \mid \what{z})}{ \margindens_\packval(z \mid
  \what{z})}$, we have $C \le e^\diffp$ and $C \le \max_\packval \sup_x
\frac{dP(x)}{dP_\packval(x)}$, we obtain the desired
result~\eqref{eqn:diffp-big-le-cam-tensor} for the differentially private
case.

\paragraph{The $\chi^2$-private case}
In the second case, when the channel is $\chi^2$-private, we require
a slightly different argument.
We begin by using the convexity of the function
$t \mapsto 1 / t$ and, as in the proof of the differentially private case,
that $\int c (dP_0 - dP_\packval) = 0$, to obtain
\begin{align*}
  \frac{(\margindens_\packval(z \mid \what{z})
    - \margindens_0(z \mid \what{z}))^2}{
    \margindens_\packval(z \mid \what{z})}
  & =
  \frac{\inf_{x_0} (\int (\channeldens(z \mid x, \what{z})
    - \channeldens(z \mid x_0, \what{z}))
    (dP_0(x) - dP_\packval(x)))^2}{
    \int \channeldens(z \mid x', \what{z})
    dP_\packval(x')} \\
  & \le
  \int \frac{\inf_{x_0} (\int (\channeldens(z \mid x, \what{z})
    - \channeldens(z \mid x_0, \what{z}))
    (dP_0(x) - dP_\packval(x)))^2}{
    \int \channeldens(z \mid x', \what{z})}
  dP_\packval(x') \\
  & \le
  \int \frac{(\int (\channeldens(z \mid x, \what{z})
    - \channeldens(z \mid x', \what{z}))
    (dP_0(x) - dP_\packval(x)))^2}{
    \int \channeldens(z \mid x', \what{z})}
  dP_\packval(x').
\end{align*}
Now, let $P$ be an arbitrary distribution on $\xdomain$.
As a consequence of the preceding
display, we may upper bound the average~\eqref{eqn:chi-square-to-bound},
using the shorthand $\what{z} = z_{1:i-1}$ for the history
$z_{1:i-1}$,
by
\begin{align}
  \lefteqn{\frac{1}{|\packset|}
    \sum_{\packval \in \packset}
    \dchis{\marginprob_0(\cdot \mid \what{z})}{
      \marginprob_\packval(\cdot \mid \what{z})}} \nonumber \\
  & \le
  \sum_z
  \int \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \frac{(\int (\channeldens(z \mid x, \what{z})
    - \channeldens(z \mid x', \what{z}))(dP_0(x) - dP_\packval(x)))^2}{
    \channeldens(z \mid x', \what{z})}
  dP_\packval(x') \nonumber \\
  & \le \sup_{\packval, x}
  \frac{dP_\packval(x)}{dP(x)}
  \cdot \bigg[
    \int \sum_z
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \frac{(\int (\channeldens(z \mid x, \what{z})
    - \channeldens(z \mid x', \what{z}))(dP_0(x) - dP_\packval(x)))^2}{
    \channeldens(z \mid x', \what{z})}
  dP(x')\bigg]. \nonumber
\end{align}
Rearranging, the final expression is equal to
\begin{align}
  \lefteqn{ \max_{\packval} \linf{\frac{dP_\packval}{dP}}
  \cdot \bigg[
    \int \sum_z
    \frac{1}{|\packset|}
    \sum_{\packval \in \packset}
    \left(\int \frac{\channeldens(z \mid x, \what{z})
      - \channeldens(z \mid x', \what{z})}{
      \channeldens(z \mid x', \what{z})}
    (dP_0(x) - dP_\packval(x))\right)^2
    \channeldens(z \mid x', \what{z})
    dP(x')\bigg]} \nonumber \\
  & = \max_{\packval} \linf{\frac{dP_\packval}{dP}}
  \cdot \bigg[
    \int \sum_z
    \frac{1}{|\packset|}
    \sum_{\packval \in \packset}
    \left(\int \Delta(z \mid x, x', \what{z})
    (dP_0(x) - dP_\packval(x))\right)^2
    \channeldens(z \mid x', \what{z})
    dP(x')\bigg],
  \label{eqn:get-to-something-to-square}
\end{align}
where in the equality~\eqref{eqn:get-to-something-to-square}
we defined the quantity
\begin{equation*}
  \Delta(z \mid x, x', \what{z})
  \defeq \frac{\channeldens(z \mid x, \what{z})}{
    \channeldens(z \mid x', \what{z})} - 1.
\end{equation*}

For any distribution $P^*$ supported on $\xdomain$, we can further upper
bound the innermost summation over $\packval \in \packset$ in
expression~\eqref{eqn:get-to-something-to-square} by
\begin{align*}
  \lefteqn{\frac{1}{|\packset|}
    \sum_{\packval \in \packset}
    \left(\int \Delta(z \mid x, x', \what{z})
    (dP_0(x) - dP_\packval(x))\right)^2} \\
  & \le \sup_{f : \mc{X} \to \R} \left\{
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \left(\int f(x) (dP_0(x) - dP_\packval(x))\right)^2
  \mid
  \int f(x)^2 dP^*(x)
  \le \int \Delta(z \mid x, x', \what{z})^2 dP^*(x)
  \right\}.
\end{align*}
Recall the definition~\eqref{eqn:chi-square-complexity}
of $\complexity_2$, and assume without loss of generality that
the supremum in the quantity is attained by $P^*$. In this case,
we then obtain
\begin{align*}
  \frac{1}{|\packset|}
  \sum_{\packval \in \packset}
  \left(\int \Delta(z \mid x, x', \what{z})
  (dP_0(x) - dP_\packval(x))\right)^2
  & \le \complexity_2(\{P_\packval\}_{\packval \in \packset})
  \cdot \int \Delta(z \mid x, x', \what{z})^2 dP^*(x).
\end{align*}
Substituting this into the upper bound~\eqref{eqn:get-to-something-to-square}
and applying Fubini's theorem, we obtain
\begin{align}
  \lefteqn{\frac{1}{|\packset|}
    \sum_{\packval \in \packset}
    \dchis{\marginprob_0(\cdot \mid \what{z})}{
      \marginprob_\packval(\cdot \mid \what{z})}} \nonumber \\
  & \le \max_\packval
  \linf{\frac{dP_\packval}{dP}}
  \complexity_2(\{P_\packval\}_{\packval \in \packset})
  \int \int
  \bigg[\sum_z \Delta(z \mid x, x', \what{z})^2
    \channeldens(z \mid x', \what{z})\bigg]
  dP(x') dP^*(x) \nonumber \\
  & = 
  \max_\packval
  \linf{\frac{dP_\packval}{dP}}
  \complexity_2(\{P_\packval\}_{\packval \in \packset})
  \int \int
  \dchis{\channel(\cdot \mid x, \what{z})}{
    \channel(\cdot \mid x', \what{z})}
  dP(x') dP^*(x).
  \nonumber
\end{align}
Of course, by assumption we know that $\dchis{\channel(\cdot \mid
  x,\what{z})}{\channel(\cdot \mid x', \what{z})} \le \diffp^2$, which gives
the result~\eqref{eqn:chi-square-big-le-cam-tensor} by
way of equality~\eqref{eqn:chi-square-to-bound}.


\subsection{Proof of Proposition~\ref{proposition:sparse-logistic-regression}}
\label{sec:proof-sparse-logistic-regression}

As in our proof of Proposition~\ref{proposition:highdim-mean-hard}
(Section~\ref{sec:proof-highdim-mean-hard}) we construct distributions for
which the parameters are well-separated but for which the complexity measure
$\complexity_2$ is reasonably small. With this in mind, let $\theta_0 \ge 0$
without loss of generality, and consider the base distribution $P_0$ defined
by the conditional p.m.f.
\begin{equation*}
  p_0(y \mid x) = \frac{1}{1 + \exp(-y\theta_0)}
\end{equation*}
where we assume $X \sim \uniform(\{-1, 1\}^d)$. Now we construct the
well-separated packing set by, as in the proof of
Proposition~\ref{proposition:highdim-mean-hard}, setting $\packset = \{\pm
e_j\}_{j = 1}^d$ and for a parameter $\delta \in [0, 1]$ to be chosen, we
set
\begin{equation*}
  p_\packval(y \mid x)
  = \frac{1}{1 + \exp(-y (\theta_0 + \delta \packval^T x))},
\end{equation*}
letting $X \sim \uniform(\{-1, 1\}^d)$ as in the case of $P_0$.  With this
setting, we have $\theta_\packval = \theta(P_\packval) = \delta \packval$.

Our starting point is the following lemma, which controls the
complexity measure $\complexity_2$ for this class.
(See Appendix~\ref{sec:proof-highdim-logreg-complexity} for a proof.)
\begin{lemma}
  \label{lemma:highdim-logreg-complexity}
  Let $P_0$ and $P_\packval$ be as above, and
  define
  \begin{equation}
    \label{eqn:funny-quantities-for-logreg}
    \alpha = \frac{e^{\theta_0}}{e^{\theta_0} + 1} - \frac{e^{\theta_0}}{
      e^{\theta_0} + e^{-\delta}}
    ~~ \mbox{and} ~~
    \beta = \frac{e^{\theta_0}}{e^{\theta_0} + 1} - \frac{e^{\theta_0}}{
      e^{\theta_0} + e^{\delta}}.
  \end{equation}
  Then
  \begin{equation*}
    \complexity_2(\{P_\packval\}_{\packval \in \packset})
    \le 2 \max\left\{\frac{(\alpha - \beta)^2}{d},
    (\alpha + \beta)^2 \right\}.
  \end{equation*}
\end{lemma}
Inspecting this quantity, we obtain that
for $\theta_0 \ge 0$, we have
\begin{equation*}
  0 \le \alpha + \beta
  = \frac{e^{\theta_0} (e^{\theta_0} - 1)
    (e^\delta + e^{-\delta} - 2)}{
    1 + e^{\theta_0 - \delta}
    + e^{\theta_0} + e^{\theta_0 + \delta}
    + e^{2 \theta_0 - \delta}
    + e^{2\theta_0} + e^{2 \theta_0 + \delta}
    + e^{3 \theta_0}}
  \le e^{-\theta_0} \frac{e^{\theta_0} - 1}{e^{\theta_0}}
  (e^\delta + e^{-\delta} - 2),

\end{equation*}
while
\begin{equation*}
  0 \le \beta - \alpha
  = \frac{e^{\theta_0} (e^\delta - e^{-\delta})}{
    e^{\theta_0 - \delta} + e^{\theta_0} + e^{\theta_0 + \delta}
    + e^{2 \theta_0}}
  \le e^{-\theta_0} (e^\delta - e^{-\delta}).
\end{equation*}
For $0 \le \delta \le 1$, we thus obtain that
$0 \le \alpha + \beta \le 2 e^{-\theta_0} (1 - e^{-\theta_0}) \delta^2$
and $0 \le \beta - \alpha \le 2 e^{-\theta_0} \delta$, so that
in this regime, we have the complexity bound
\begin{equation}
  \label{eqn:highdim-logreg-complexity}
  \complexity_2(\{P_\packval\}_{\packval \in \packset})
  \le \frac{8\delta^2}{e^{2 \theta_0}}
  \max\left\{d^{-1}, (1 - e^{-\theta_0})^2 \delta^2 \right\}.
\end{equation}

Using the upper bound~\eqref{eqn:highdim-logreg-complexity}, we can
substitute into Theorem~\ref{theorem:big-tensor}, choosing $P = P_0$ in the
theorem so that $\linf{dP_\packval / dP_0} \le 1 + e^\delta \le 4$ for
$\delta \le 1$; we thus obtain
\begin{equation*}
  \tvnorm{\marginprob_0^n - \meanmarginprob^n}^2
  \le \half \dkl{\marginprob_0^n}{\meanmarginprob^n}
  \le \frac{16 n \diffp^2}{e^{2 \theta_0}}
  \max\left\{d^{-1}, (1 - e^{-\theta_0})^2 \delta^2\right\} \delta^2.
\end{equation*}
If we solve for $\delta^2$ to obtain
$\tvnorms{\marginprob_0^n - \meanmarginprob^n} \le \half$,
we see that the choice
\begin{equation*}
  \delta_n^2
  \defeq \min\left\{
  \frac{d e^{2 \theta_0}}{64 n \diffp^2},
  \frac{e^{\theta_0}}{8 (1 - e^{-\theta_0})^2 \sqrt{n \diffp^2}},
  1
  \right\}
\end{equation*}
is sufficient to guarantee that $\tvnorms{\marginprob_0^n -
  \meanmarginprob^n} \le \half$.  Using
Lemma~\ref{lemma:private-general-le-cam} and the separation lower
bound~\eqref{eqn:loss-sep-highdim-mean}, we obtain the minimax lower bound
\begin{equation*}
  \minimax_n
  \ge \min_{\packval \in \packset}
  \half \Phi(\delta_n \psi(\packval) / 2)
  =
  \min_{j = 1, \ldots, d}
  \half \Phi\left(
  \delta_{n} \psi(e_j) \right).
\end{equation*}

\subsubsection{Proof of Lemma~\ref{lemma:highdim-logreg-complexity}}
\label{sec:proof-highdim-logreg-complexity}

We take $P^*$ in the definition~\eqref{eqn:chi-square-complexity} to be
uniform on $(x, y) \in \{-1, 1\}^d \times \{-1, 1\}$.  We then have
\begin{align}
  \complexity_2(\{P_\packval\})
  & \le \sup_{f : P^* f^2 \le 1}
  \frac{1}{4^d \cdot 2d} \sum_{\packval \in \packset}
  \left(
  \sum_{x \in \{\pm 1\}^d}
  \sum_{y \in \{\pm 1\}}
  f(x, y) (p_0(y \mid x) - p_\packval(y \mid x))\right)^2 \nonumber \\
  & \le \sup_{f : P^*f^2 \le 1}
  \frac{1}{4^d \cdot d}
  \sum_{\packval \in \packset}
  \left(
  \sum_{x \in \{\pm 1\}^d}
  f(x) (p_0(1 \mid x) - p_\packval(1 \mid x))\right)^2 + \cdots \nonumber \\
  & ~~~~~
  \sup_{f : P^*f^2 \le 1}
  \frac{1}{4^d \cdot d}
  \sum_{\packval \in \packset}
  \left(
  \sum_{x \in \{\pm 1\}^d}
  f(x) (p_0(-1 \mid x) - p_\packval(-1 \mid x))\right)^2,
  \label{eqn:complexity-logreg-big}
\end{align}
where we have used that $(a + b)^2 \le 2 a^2 + 2b^2$. Fixing $f$
temporarily, we consider the terms inside the squares, recalling that
$\packval \in \{\pm e_j\}_{j=1}^d$. For a fixed $\packval \in \{\pm e_j\}$,
because $x$ is uniform, we have
\begin{align*}
  \lefteqn{\sum_{x \in \{\pm 1\}^d} f(x) (p_0(1 \mid x)
    - p_\packval(1 \mid x))} \\
  & = \sum_{x : \packval_j x_j = 1}
  f(x) \left[\frac{e^{\theta_0}}{1 + e^{\theta_0}}
    - \frac{e^{\theta_0}}{e^{\theta_0} + e^{-\delta}}\right]
  + \sum_{x : \packval_j x_j = -1}
  f(x) \left[\frac{e^{\theta_0}}{1 + e^{\theta_0}}
    - \frac{e^{\theta_0}}{e^{\theta_0} + e^{\delta}}\right] \\
  & = \sum_{x : \packval_j x_j = 1} f(x) \alpha
  + \sum_{x : \packval_j x_j = -1} f(x) \beta
  = \sum_x f(x) \frac{\packval^T x}{2}(\alpha - \beta)
  + \sum_x f(x) \frac{\alpha + \beta}{2},
\end{align*}
where $\alpha$ and $\beta$ are as defined in
expression~\eqref{eqn:funny-quantities-for-logreg}.
A similar calculation yields that
\begin{align*}
  \sum_x
  f(x) \left(p_0(-1 \mid x) - p_\packval(-1 \mid x)\right)
  & = -\sum_{x :  \packval_j x_j = 1}
  f(x) \alpha - \sum_{x : \packval_j x_j = -1} f(x) \beta \\
  & =
  \sum_x f(x) \frac{\packval^T x}{2} (\beta - \alpha)
  - \sum_x f(x) \frac{\alpha + \beta}{2}.
\end{align*}

Returning to expression~\eqref{eqn:complexity-logreg-big},
we thus obtain
\begin{align*}
  \complexity_2(\{P_\packval\})
  & \le
  \sup_{f : \E[f(X)^2] \le 1}
  \frac{1}{2 \cdot 4^d \cdot d}
  \sum_{\packval \in \packset}
  \left(\sum_x f(x)  \packval^T x (\alpha - \beta)
  + \sum_x f(x) (\beta + \alpha) \right)^2 \\
  & \le
  \sup_{f : \E[f(X)^2] \le 1}
  \frac{1}{d}
  \left(\sum_{\packval \in \packset}
  (\alpha - \beta)^2 \E[f(X) X^T \packval]^2
    + (\alpha + \beta)^2 \E[f(X)]^2 \right)
\end{align*}
where $X \sim \uniform(\{-1, 1\}^d)$. Finally, we use that
$\sum_{\packval \in \packset} \packval\packval^T = 2 I_{d \times d}$ to
obtain that
\begin{align*}
  \complexity_2(\{P_\packval\})
  & \le \frac{2}{d} \sup_{f : \E[f(X)^2] \le 1}
  \left((\alpha - \beta)^2 \ltwo{\E[f(X) X]}^2
  + d (\alpha + \beta)^2 \E[f(X)]^2 \right).
\end{align*}
As the final step, we apply an argument analogous to that in
the proof of Proposition~\ref{proposition:highdim-mean-hard}
to bound the expectations involving $f(X)$. Indeed,
for any $a, b \ge 0$ and $\E[f(X)^2] = 1$, we have
\begin{align*}
  \lefteqn{a^2 \ltwo{\E[f(X) X]}^2
    + b^2 \E[f(X)]^2
    = \sup_{\ltwo{w} \le 1}
    \E\left[f(X) \left[\begin{matrix} a X \\ b \end{matrix}
        \right]^T w\right]^2} \\
  & ~~~~~ \le
  \E[f(X)^2]
  \sup_{\ltwo{w} \le 1} \E[\<(aX ~ b), w\>^2]
  = \sup_{\ltwo{w} \le 1}
  w^T \left[\begin{matrix} a^2 I & 0 \\ 0 & b^2 \end{matrix}
    \right] w = \max\{a^2, b^2\}.
\end{align*}
Returning to the preceding bound on $\complexity_2$, we find that
\begin{align*}
  \complexity_2(\{P_\packval\})
  & \le 
  2 \max\left\{\frac{(\alpha - \beta)^2}{d}, (\alpha + \beta)^2\right\}.
\end{align*}
{"config": "arxiv", "file": "1806.05756/appendices.tex"}