%% Theory of Computing
%% File: v014a008.tex
%% Publication date: June 2, 2018
%% Authors: Jack Murtagh and Salil Vadhan
%
%
%
%

%

%

\documentclass{toc}
\usepackage{mathtools}
\usepackage{tikz}
\usetikzlibrary{automata,arrows,positioning,calc}
\usepackage{subcaption}
\usepackage{graphicx}
\usepackage{floatpag}%
\usepackage{algorithmic}
\usepackage{algorithm}

\newtheoremstyle{named}{}{}{\itshape}{}{\bfseries}{.}{.5em}{\thmnote{#3}}
\theoremstyle{named}
\newtheorem{namedtheorem}{Theorem}[section]
\newenvironment{claim_proof}[1][Proof of Claim]
  {\proof[#1]\leftskip=1cm\rightskip=1cm}
  {\endproof}

%
%
%
\newcommand{\ebar}{\overline{\epsilon}}

%
%
\tocdetails{%
volume=14, number=8, year=2018, firstpage=1,
%
%
%
%
received={Month 1, 2012},
revised={July 29, 2017},
published={June 2, 2018},
%
%
doi={10.4086/toc.2018.v014a008},
title={The Complexity of Computing the Optimal Composition of Differential Privacy},
author={Jack Murtagh and Salil Vadhan},
plaintextauthor={Jack Murtagh, Salil Vadhan},
acmclassification={F.2},
amsclassification={68Q17, 68W25, 68Q25},
keywords={complexity theory, approximation algorithms, differential privacy, composition}
}
%

\begin{document}

\begin{frontmatter}
%
\title{The Complexity of Computing the Optimal Composition of Differential Privacy\titlefootnote{A conference version of this paper appeared in the Proceedings of the 13th IACR
Theory  of  Cryptography  Conference  (TCC), 2016-A~\cite{MV16}.}}

%
%
%
\author[murtagh]{Jack Murtagh\thanks{Supported by NSF grant CNS-1237235 and a grant from the Sloan Foundation.}}
\author[vadhan]{Salil Vadhan\thanks{Supported by NSF grant CNS-1237235, a grant from the Sloan Foundation, and a Simons Investigator Award.}}

%
%
%
%

%
\begin{abstract}
In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC'06)) bound the degradation of privacy when composing several differentially private algorithms. Kairouz, Oh, and Viswanath (ICML'15) showed how to compute the optimal bound for composing $k$ arbitrary $(\epsilon,\delta)$-differentially private algorithms. We characterize the optimal composition for the more general case of $k$ arbitrary $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$-differentially private algorithms where the privacy parameters may differ for each algorithm in the composition. We show that computing the optimal composition in general is \cclass{\#P}-complete. Since computing optimal composition exactly is infeasible (unless $\cclass{FP} = \cclass{\#P}$), we give an approximation algorithm that computes the composition to arbitrary accuracy in polynomial time. The algorithm is a modification of Dyer's dynamic programming approach to approximately counting solutions to knapsack problems (STOC'03).
\end{abstract}

\iffalse %
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\tocarxivcategory{cs.CC}

\fi %

\end{frontmatter}


%
%
\begin{section}{Introduction}
  Differential privacy is a framework that allows statistical analysis of private databases while minimizing the risks to individuals in the databases. The idea is that an individual should be relatively unaffected whether he or she decides to join or opt out of a research dataset. More specifically, the probability distribution of outputs of a statistical analysis of a database should be nearly identical to the distribution of outputs on the same database with a single person's data removed. Here the probability space is over the coin flips of the randomized differentially private algorithm that handles the queries. To formalize this, we call two databases $D_{0}, D_{1}$ with $n$ rows each $\textit{neighboring}$ if they are identical on at least $n-1$ rows, and define differential
privacy as follows. %

\begin{definition}[Differential Privacy~\cite{DMNS06, DKMMN06}]
A randomized algorithm $M$ is \emph{$(\epsilon,\delta)$-differentially private} for $\epsilon,\delta \geq 0$ if for all pairs of neighboring databases $D_{0}$ and $D_{1}$ and all output sets $S\subseteq \mathrm{Range}(M)$
\[
\Pr[M(D_{0})\in S] \leq \eee^{\epsilon}\Pr[M(D_{1})\in S] + \delta
\]
where the probabilities are over the coin flips of the algorithm $M$. 
\end{definition}

In the practice of differential privacy, we generally think of $\epsilon$ as a small, non-negligible, constant (\eg, $\epsilon=.1$). We view $\delta$ as a ``security parameter'' that is cryptographically small (\eg, $\delta=2^{-30}$). One of the important properties of differential privacy is that if we run multiple distinct differentially private algorithms on the same database, the resulting composed algorithm is also differentially private, albeit with some degradation in the privacy parameters $(\epsilon,\delta)$. In this paper, we are interested in quantifying the degradation of privacy under composition. We will denote the composition of $k$ differentially private algorithms $M_{1},M_{2},\ldots,M_{k}$ as $(M_{1},M_{2},\ldots,M_{k})$ where
\[
(M_{1},M_{2},\ldots,M_{k})(x)=(M_{1}(x),M_{2}(x),\ldots,M_{k}(x))\,.
\]
A handful of composition theorems already exist in the literature. The first basic result
%
is the following.  %

\begin{theorem}[Basic Composition~\cite{DKMMN06}]
\label{thm:basiccomp}
For every $\epsilon \geq 0$, $\delta \in [0,1]$, and $(\epsilon,\delta)$-differentially private algorithms $M_{1},M_{2},\ldots,M_{k}$, the composition $(M_{1},M_{2},\ldots,M_{k})$ satisfies $(k\epsilon,k\delta)$-differential privacy.
\end{theorem}

This tells us that under composition, the privacy parameters of the individual algorithms ``sum up,'' so to speak. We care about understanding composition because in practice we rarely want to release only a single statistic about a dataset. Releasing many statistics may require running multiple differentially private algorithms on the same database. Composition is also a very useful tool in algorithm design. Often, new differentially private algorithms are created by combining several simpler algorithms. Composition theorems help us analyze the privacy properties of algorithms designed in this way.

\expref{Theorem}{thm:basiccomp} shows a linear degradation in global privacy as the number of algorithms in the composition $(k)$ grows and it is of interest to improve on this bound. If we can prove that privacy degrades more slowly under composition, we can get more utility out of our algorithms under the same global privacy guarantees. Dwork, Rothblum, and Vadhan gave the following improvement on the basic summing composition above~\cite{DRV10}.

\begin{theorem}[Advanced Composition~\cite{DRV10}]
\label{thm:advancedcomp}
For every $\epsilon>0, \delta, \delta'>0,$ $k\in \mathbb{N},$ and $(\epsilon,\delta)$-differentially private algorithms $M_{1},M_{2},\ldots,M_{k}$, the composition $(M_{1},M_{2},\ldots,M_{k})$ satisfies $(\epsilon_{g},k\delta+\delta')$-differential privacy for
\[
\epsilon_{g} = \sqrt{2k\ln(1/\delta')}\cdot\epsilon + k\cdot\epsilon\cdot(\eee^{\epsilon}-1)\,.
\]
\end{theorem}

\expref{Theorem}{thm:advancedcomp} shows that privacy under composition degrades by a function of $O(\sqrt{k\ln(1/\delta')})$ which is an improvement if $\delta'=2^{-O(k)}$. It can be shown that a degradation function of $\Omega(\sqrt{k\ln(1/\delta)})$ is necessary even for the simplest differentially private algorithms, such as randomized response~\cite{War65}.

Despite giving an asymptotically correct upper bound for the global privacy parameter, $\epsilon_{g}$, \expref{Theorem}{thm:advancedcomp} is not exact. We want an exact characterization because, beyond being theoretically interesting, constant factors in composition theorems can make a substantial difference in the practice of differential privacy. Furthermore, \expref{Theorem}{thm:advancedcomp} only applies to ``homogeneous'' composition where each individual algorithm has the same pair of privacy parameters, $(\epsilon,\delta)$. In practice we often want to analyze the more general case where some individual algorithms in the composition may offer more or less privacy than others. That is, given algorithms $M_{1},M_{2},\ldots,M_{k}$, we want to compute the best achievable privacy parameters for $(M_{1},M_{2},\ldots,M_{k})$. Formally, we want to compute the
%
following function. %
\[
\mathrm{OptComp}(M_{1},M_{2},\ldots,M_{k},\delta_{g}) = \inf\{\epsilon_{g}\geq 0\colon(M_{1},M_{2},\ldots,M_{k}) \;\textrm{is}\; (\epsilon_{g},\delta_{g})\textsc{-DP}\}\,.
\]

It is convenient for us to view $\delta_{g}$ as given and then compute the best $\epsilon_{g}$, but the dual formulation, viewing $\epsilon_{g}$ as given, is equivalent (by binary search). Actually, we want a function that depends only on the privacy parameters of the individual algorithms,
\begin{multline}
\mathrm{OptComp}((\epsilon_{1},\delta_{1}),(\epsilon_{2},\delta_{2}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})\\ = \sup\{\mathrm{OptComp}(M_{1},M_{2},\ldots,M_{k},\delta_{g})\colon M_{i} \;\textrm{is}\; (\epsilon_{i},\delta_{i})\textsc{-DP}\;\forall i\in [k]\}.
\end{multline}

In other words we want $\mathrm{OptComp}$ to give us the minimum possible $\epsilon_{g}$ that maintains privacy for every sequence of algorithms with the given privacy parameters $(\epsilon_{i},\delta_{i})$. A result from Kairouz, Oh, and Viswanath~\cite{KOV15} characterizes $\mathrm{OptComp}$ for the homogeneous case.

\begin{theorem}[Optimal Homogeneous Composition~\cite{KOV15}\footnote{The phrasing of \expref{Theorem}{thm:homogeneouscomp} is not exactly how it is presented in~\cite{KOV15} (which only refers to $\epsilon_{g}$ of the form $(k-2i)\epsilon$ for integer $i$), but this version can be deduced from the original.}]
\label{thm:homogeneouscomp}
For every $\epsilon \geq 0$ and $\delta \in [0,1)$,
\[
  \mathrm{OptComp}(\underbrace{(\epsilon,\delta),(\epsilon,\delta),\ldots,(\epsilon,\delta)}_{k}, \delta_{g})
\]
equals the least value of $\epsilon_{g}\geq 0$ such that
\[
\frac{1}{(1+\eee^{\epsilon})^{k}}\sum\limits^{k}_{\ell=\left\lceil{\frac{\epsilon_{g}+k\epsilon}{2\epsilon}}\right\rceil}\binom{k}{\ell}\left(\eee^{\ell\epsilon}-\eee^{\epsilon_{g}}\eee^{(k-\ell)\epsilon}\right)\leq 1-\frac{1-\delta_{g}}{(1-\delta)^{k}}\,.
\]
\end{theorem}

 Empirically (see \expref{Section}{sect:fig}), this optimal bound provides a 30-40$\%$ savings in $\epsilon_{g}$ compared to \expref{Theorem}{thm:advancedcomp} (and a $20\%$ savings compared to an improved asymptotic bound from~\cite{KOV15}). The problem remains to find the optimal composition behavior for the more general heterogeneous case. Kairouz, Oh, and Viswanath also provide an upper bound for heterogeneous composition that generalizes the $O(\sqrt{k\ln(1/\delta')})$ degradation found in \expref{Theorem}{thm:advancedcomp} for homogeneous composition but do not comment on how close it is to optimal. 
\end{section}

\begin{subsection}{Our results}

We begin by extending the results of Kairouz, Oh, and Viswanath~\cite{KOV15} to the general heterogeneous case.

\begin{theorem}[Optimal Heterogeneous Composition]
\label{thm:optcomp}
For all $\epsilon_{1},\ldots,\epsilon_{k} \geq 0$ and $\delta_{1},\ldots,\delta_{k},\delta_{g}\in [0,1)$, $\mathrm{OptComp}((\epsilon_{1},\delta_{1}),(\epsilon_{2},\delta_{2}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})$ equals the least value of $\epsilon_{g}\geq 0$ such that
\begin{equation}
\label{eq:1}
\frac{1}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} \leq 1-\frac{1-\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\,.
\end{equation}
\end{theorem}

\expref{Theorem}{thm:optcomp} exactly characterizes the optimal composition behavior for any arbitrary set of differentially private algorithms. It also shows that optimal composition can be computed in time exponential in $k$ by computing the sum over $S\subseteq \{1,\ldots,k\}$ by brute force. Of course in practice an exponential-time algorithm is not satisfactory for large $k$. Our next result shows that this exponential complexity is
necessary. %

\begin{theorem}
\label{thm:hardness}
Computing $\mathrm{OptComp}$ is \cclass{\#P}-complete, even on instances where $\delta_{1}=\delta_{2}=\cdots=\delta_{k}=0$ and $\sum_{i\in [k]}\epsilon_{i}\leq \epsilon$ for any desired constant $\epsilon>0$.
\end{theorem}

Recall that \cclass{\#P} is the class of counting problems associated with decision problems in \cclass{NP}. So being \cclass{\#P}-complete means that there is no polynomial-time algorithm for $\mathrm{OptComp}$ unless there is a polynomial-time algorithm for counting the number of satisfying assignments of Boolean formulas (or equivalently for counting the number of solutions of all \cclass{NP} problems). So there is almost certainly no efficient algorithm for $\mathrm{OptComp}$ and therefore no analytic solution. Despite the intractability of exact computation, we show that $\mathrm{OptComp}$ can be approximated efficiently.

\begin{theorem}
\label{thm:approx}
There is a polynomial-time algorithm that given rational $\epsilon_{1},\ldots,\epsilon_{k}\geq 0, \delta_{1},\ldots \delta_{k}, \delta_{g} \in [0,1),$ and $\eta\in (0,1)$, outputs $\epsilon^{*}$ satisfying 
\[
  \mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})\leq \epsilon^{*}\leq\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \eee^{-\eta/2}\cdot\delta_{g})+\eta\,.
\]
The algorithm runs in time
\[
  O\left(\frac{k^{3}\cdot\ebar\cdot(1+\ebar)}{\eta}\cdot \log\left(\frac{k^{2}\cdot\ebar\cdot(1+\ebar)}{\eta}\right)\right)
\]
 where $\ebar=\sum_{i\in [k]}\epsilon_{i}/k$, assuming constant-time arithmetic operations.
\end{theorem}

Note that we incur a relative error of $\eta$ in approximating $\delta_{g}$ \emph{and} an additive error of $\eta$ in approximating $\epsilon_{g}$. Since we always take $\epsilon_{g}$ to be non-negligible or even constant, we get a very good approximation when $\eta$ is polynomially small or even a constant. Thus, it is acceptable that the running time is polynomial in $1/\eta$. 

In addition to the results listed above, our proof of \expref{Theorem}{thm:optcomp} also provides a somewhat simpler proof of the Kairouz-Oh-Viswanath homogeneous composition theorem (\expref{Theorem}{thm:homogeneouscomp} \cite{KOV15}). The proof in~\cite{KOV15} introduces a view of differential privacy through the lens of hypothesis testing and uses geometric arguments. Our proof relies only on elementary techniques commonly found in the differential privacy literature.

\paragraph{Practical application.} 
The theoretical results presented here were motivated by our work on an applied project called ``Privacy Tools for Sharing Research Data''\footnote{\url{https://privacytools.seas.harvard.edu/}} \cite{GHKMNUV16}. We are building a system that will allow researchers with sensitive datasets to make differentially private statistics about their data available through data repositories using the Dataverse\footnote{\url{https://dataverse.org/}} platform~\cite{Cro11, Kin07}. Part of this system is a tool that helps both data depositors and data analysts distribute a global privacy budget across many statistics. Users select which statistics they would like to compute and are given estimates of how accurately each statistic can be computed. They can also redistribute their privacy budget according to which statistics they think are most valuable in their dataset. We implemented the approximation algorithm from \expref{Theorem}{thm:approx} and integrated it with this tool to ensure that users get the most utility out of their privacy budget. 

\paragraph{Utility-theoretic interpretation.} As suggested to us by an anonymous referee, another natural perspective on composition is to maximize the ``utility'' $u(M_1,\ldots,M_k)$ provided by $k$ differentially private algorithms for a particular set of analysts subject to a global privacy constraint, OptComp$(M_1,\ldots,M_k,\delta_g)\leq \epsilon_g$. Our results can be interpreted as studying this problem in the special case where $u(M_1,\ldots,M_k)=1$ if and only if for every $i\in[k]$, $M_i$ is a ``randomized response'' algorithm (see \expref{Definition}{def:randresponse}) with privacy parameters \emph{at least} $\epsilon_i,\delta_i$ (recall that larger privacy parameters generally yield greater accuracy and hence greater utility). Following~\cite{KOV15}, we show in \expref{Lemma}{lem:sim} that randomized response achieves the worst-case bound OptComp$((\epsilon_1, \delta_1),\ldots, (\epsilon_k,\delta_k),\delta_g)$ over all sequences of algorithms $M_i$ that are $(\epsilon_i,\delta_i)$-DP\@. Studying this utility maximization problem in greater generality is an interesting direction for future work. (See~\cite{BN10,GRS08} for a general study of utility maximization under one-shot differential privacy, without composition.)

\end{subsection}
\begin{section}{Technical preliminaries}
\label{sect:tech}
A useful notation for thinking about differential privacy is defined below.
\begin{definition}
  For two discrete random variables $Y$ and $Z$ taking values in the same output space $S$, the \emph{$\delta$-approximate max-divergence} of $Y$ and $Z$
%
is defined as follows. %
\[
D_{\infty}^{\delta}(Y\|Z)\equiv \max_{S}\left[\ln\frac{\Pr[Y\in S]-\delta}{\Pr[Z\in S]}\right].
\]
\end{definition}

Notice that an algorithm $M$ is $(\epsilon,\delta)$ differentially private if and only if for all pairs of neighboring databases, $D_{0},D_{1}$, we have $D_{\infty}^{\delta}(M(D_{0})\|M(D_{1}))\leq\epsilon$. The standard fact that differential privacy is closed under ``post processing''~\cite{DMNS06, DR13} now can be formulated
%
as follows.  %
\begin{fact}
\label{fact:postproc}
If $f\colon S\to R$ is any randomized function, then 
\[
D_{\infty}^{\delta}(f(Y)\|f(Z))\leq D_{\infty}^{\delta}(Y\|Z)\,.
\]
\end{fact}

\paragraph{Adaptive composition.} The composition results in our paper actually hold for a more general model of composition than the one described in the introduction. The model is called adaptive composition and was formalized in~\cite{DRV10}. We generalize their formulation to the heterogeneous setting where privacy parameters may differ across different algorithms in the composition.

The idea is that instead of running $k$ differentially private algorithms chosen all at once on a single database, we can imagine an adversary adaptively engaging in a ``composition game.'' The game takes as input a bit $b\in\{0,1\}$ and privacy parameters $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$. A randomized adversary $A$, tries to learn $b$ through $k$ rounds of interaction as follows. On the $i$-th round of the game, $A$ chooses an $(\epsilon_{i},\delta_{i})$-differentially private algorithm $M_{i}$ and two neighboring databases $D_{(i,0)},D_{(i,1)}$. $A$ then receives an output $y_{i}=M_{i}(D_{(i,b)})$ where the internal randomness of $M_{i}$ is independent of the internal randomness of $M_{1},\ldots,M_{i-1}$. The choices of $M_{i}, D_{(i,0)},$ and $D_{(i,1)}$ may depend on $y_{0},\ldots,y_{i-1}$ as well as the adversary's own randomness.

The outcome of this game is called the \emph{view of the adversary}, $V^{b}$ which is defined to be $(y_{1},\ldots,y_{k})$ along with $A$'s coin tosses. The algorithms $M_{i}$ and databases $D_{(i,0)},D_{(i,1)}$ from each round can be reconstructed from $V^{b}$. Now we can formally define privacy guarantees under adaptive composition.

\begin{definition}
  We say that the sequences of privacy parameters $\epsilon_{1},\ldots,\epsilon_{k}\geq 0$, $\delta_{1},\ldots,\delta_{k}\in [0,1)$ satisfy \emph{$(\epsilon_{g},\delta_{g})$-differential privacy under adaptive composition} if for every adversary $A$ we have
  \[
    D_{\infty}^{\delta_{g}}(V^{0}\|V^{1})\leq\epsilon_{g}\,,
  \]
  where $V^{b}$ represents the view of $A$ in composition game $b$
  with privacy parameter inputs
  \[
    (\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})\,.
  \]
\end{definition}

\paragraph{Computing real-valued functions.} Many of the computations we discuss involve irrational numbers and we need to be explicit about how we model such computations on finite, discrete machines. Namely when we talk about computing a function $f:\{0,1\}^{*}\to\mathbb{R}$, what we really mean is computing $f$ to any desired number $q$ bits of precision. More precisely, given $x,q$, the task is to compute a number $y\in\mathbb{Q}$ such that $\left|f(x)-y\right|\leq {1}/{2^{q}}$. We measure the complexity of algorithms for this task as a function of $|x|+q$. In order to reason about the complexity of OptComp, we will also require that the inputs be rational. So when we talk about computing OptComp exactly, we actually mean given $\epsilon_{1},\ldots,\epsilon_{k}\geq 0, \delta_{1},\ldots,\delta_{k}, \delta_{g}\in [0,1)$ all rational and an integer $q$, compute $\epsilon^{*}$ such
that %
\[
\left|\epsilon_{g}-\epsilon^{*}\right|\leq\frac{1}{2^{q}}
\]
where $\epsilon_{g}$ is the true optimal parameter with full precision.
\end{section}

\begin{section}{Characterization of OptComp}

Following~\cite{KOV15}, we show that to analyze the composition of arbitrary $(\epsilon_{i},\delta_{i})$-DP algorithms, it suffices to analyze the composition of the following simple variant of randomized response~\cite{War65}. 

\begin{definition}[\cite{KOV15}]
\label{def:randresponse}
Define a randomized algorithm $\tilde{M}_{(\epsilon,\delta)}\colon\{0,1\} \to \{0,1,2,3\}$ as follows,
%
setting $\alpha=1-\delta$.
\begin{center}
\begin{tabular}{ll} 
$\Pr[\tilde{M}_{(\epsilon,\delta)}(0)=0]=\delta$\,, & $\Pr[\tilde{M}_{(\epsilon,\delta)}(1)=0]=0$\,,  \\
$\Pr[\tilde{M}_{(\epsilon,\delta)}(0)=1]=\alpha\cdot\frac{\eee^{\epsilon}}{1 + \eee^{\epsilon}}$\,, & $\Pr[\tilde{M}_{(\epsilon,\delta)}(1)=1]=\alpha\cdot\frac{1}{1 + \eee^{\epsilon}}$\,,\\
$\Pr[\tilde{M}_{(\epsilon,\delta)}(0)=2]=\alpha\cdot\frac{1}{1 + \eee^{\epsilon}}$\,, & $\Pr[\tilde{M}_{(\epsilon,\delta)}(1)=2]=\alpha\cdot\frac{\eee^{\epsilon}}{1 + \eee^{\epsilon}}$\,,\\
$\Pr[\tilde{M}_{(\epsilon,\delta)}(0)=3]=0$\,, & $\Pr[\tilde{M}_{(\epsilon,\delta)}(1)=3]=\delta$\,.
\end{tabular}
\end{center}
\end{definition}
Note that $\tilde{M}_{(\epsilon,\delta)}$ is in fact $(\epsilon,\delta)$-DP\@. Kairouz, Oh, and Viswanath showed that $\tilde{M}_{(\epsilon,\delta)}$ can be used to simulate the output of every $(\epsilon,\delta)$-DP algorithm on adjacent databases. 

\begin{lemma}[\cite{KOV15}]
\label{lem:sim}
For every $(\epsilon,\delta)$-DP algorithm $M$ and neighboring databases $D_{0},D_{1}$, there exists a randomized algorithm $T$ such that $T(\tilde{M}_{(\epsilon,\delta)}(b))$ is identically distributed to $M(D_{b})$ for $b=0$ and $b=1$.
\end{lemma}

For the sake of completeness, we show how this lemma can be deduced from a recent characterization, due to Bun and Steinke~\cite{BunSt16}, of approximate max-divergence as equivalent to exact max-divergence conditioned on events of probability $1-\delta$.  
%

%

\begin{lemma}[\cite{BunSt16}]
\label{lem:events}
Let $X$ and $Y$ be random variables. The following are
equivalent. %
\begin{enumerate}
\item $D^{\delta}_{\infty}(X\| Y)\leq \epsilon$ and $D^{\delta}_{\infty}(Y\| X)\leq \epsilon$.  
\item There are probabilistic events $E=E(X)$ and $F=F(Y)$ such that
  \[
    \Pr[E]=\Pr[F]=1-\delta\quad\text{and}\quad D_{\infty}^{0}(X|_E~\|~Y|_F)\leq \epsilon\quad\text{and}\quad D_{\infty}^{0}(Y|_F~\|~X|_E)\leq \epsilon\,.
    \]
  \item There are probabilistic events $E=E(X)$ and $F=F(Y)$ such that
    \[
      \Pr[E]=\Pr[F]\geq 1-\delta\quad\text{and}\quad D_{\infty}^{0}(X|_E~\|~Y|_F)\leq \epsilon\quad\text{and}\quad D_{\infty}^{0}(Y|_F~\|~X|_E)\leq \epsilon\,.
      \]
\end{enumerate}

\end{lemma}
Bun and Steinke originally proved \expref{Lemma}{lem:events} using \expref{Lemma}{lem:sim}, but we give a direct proof here
that is in a similar spirit to the proof of an alternate characterization of approximate max-divergence from
\cite{DRV10} (which uses statistical distance rather than conditioning on high-probability events).  
%
%
%
This avoids the need for the hypothesis testing and geometric arguments used in~\cite{KOV15} to establish their optimal composition theorem.  In an earlier version of our paper, we included a direct proof of
\expref{Lemma}{lem:sim}, without going through \expref{Lemma}{lem:events}, but that proof was rather long and tedious, although using similar ideas to the proofs below.
\begin{proof}[Proof of \expref{Lemma}{lem:events}]
It is immediate that statement 2 implies statement 3. To see that statement 3 implies statement 1, note that assuming statement 3, for every set $S$ we have %
\begin{align*}
\Pr[X\in S] \leq \Pr[X\in S|E]\cdot \Pr[E]+\Pr[\lnot E]
\leq \left(\eee^{\epsilon}\cdot\Pr[Y\in S|F]\right)\cdot\Pr[F]+\Pr[\lnot F]
\leq \eee^{\epsilon}\cdot\Pr[Y\in S]+\delta\,.
\end{align*}
Thus we have $D^{\delta}_{\infty}(X\| Y)\leq \epsilon$ and by symmetry we also have $D^{\delta}_{\infty}(Y\| X)\leq \epsilon$. 

It remains to show that statement 1 implies statement 2, so assume that statement 1 holds. Finding events $E$ and $F$ as in statement 2 is equivalent to finding functions $e$ and $f$ such
%
that the following hold.  %
\begin{enumerate}
\item For all $x$, $0\leq e(x) \leq \Pr[X=x]$ and $0\leq f(x) \leq \Pr[Y=x]$.
\item For all $x$, $e(x)\leq \eee^{\epsilon}\cdot f(x)$ and $f(x)\leq \eee^{\epsilon}\cdot e(x)$.
\item $\sum_x e(x) = \sum_x f(x) = 1-\delta$.
\end{enumerate}
Indeed, the corresponding events $E$ and $F$ are defined by
\[
  \Pr[E \mid X=x]=e(x)/\Pr[X=x]\qquad\text{and}\qquad \Pr[F\mid Y=x] =
  f(x)/\Pr[Y=x]\,.
\]
Then by Bayes' Rule, the conditions above imply that
  $$\Pr[X=x | E] = \frac{\Pr[E|X=x]\cdot \Pr[X=x]}{\Pr[E]} =
  \frac{e(x)}{\sum_{y} e(y)} \leq \frac{\eee^{\epsilon}\cdot
    f(x)}{\sum_y f(y)} = \eee^{\epsilon}\cdot \Pr[Y=x | F]\,.$$ Thus we
  have $D_\infty^0(X|_E~\|~Y|_F)\leq \epsilon$ and by symmetry we also
  have $D_\infty^0(Y|_F~\|~X|_E)\leq \epsilon$.

We now proceed to defining the functions $e$ and $f$. Define the following disjoint subsets of the domain. %
\begin{eqnarray*}
S &=& \{ x : \Pr[X=x] > \eee^{\epsilon}\cdot \Pr[Y=x]\}\,,\\
%
%
%
T &=& \{ x : \Pr[Y=x] > \eee^{\epsilon}\cdot \Pr[X=x]\}\,.
\end{eqnarray*}
Let
\[
  \alpha = \Pr[X\in S] - \eee^{\epsilon}\cdot \Pr[Y\in S] \geq 0 \quad\text{and}\quad \beta = \Pr[Y\in T]-\eee^{\epsilon}\cdot \Pr[X\in T] \geq 0\,.
  \]
%
We know that $\alpha,\beta \leq \delta$, because
$D^\delta_\infty(X \| Y)\leq \epsilon$ and $D^\delta_\infty(Y \| X )\leq \epsilon$. We start by trying to define the functions $e$ and $f$ as
follows. %
\begin{enumerate}
\item For $x\in S$, $e(x) = \eee^{\epsilon}\cdot \Pr[Y=x]$ and for $x\notin S$, $e(x)=\Pr[X=x]$.
\item For $x\in T$, $f(x) = \eee^{\epsilon}\cdot \Pr[X=x]$ and for $x\notin T$, $f(x)=\Pr[Y=x]$.
\end{enumerate}
\expref{Figure}{fig:BSlem} shows the functions $e$ and $f$ as defined above as well as the sets $S$ and $T$ and regions whose areas are $\alpha$ and $\beta$. Notice that we have satisfied the conditions
\begin{align*}
  0 \leq e(x) &\leq \Pr[X=x]\,,\\
  0 \leq f(x) &\leq \Pr[Y=x]\,,\\
  e(x) &\leq \eee^{\epsilon}\cdot f(x)\,,\qquad \text{and}\\
  f(x) &\leq \eee^{\epsilon}\cdot e(x)\,.
\end{align*}
It is also clear from the figure that $\sum_x e(x)=1-\alpha$ and
$\sum_x f(x)=1-\beta$.
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=.7]{BSlemma_figure}
\end{center}
\caption{Depiction of the functions $e(x)$ (red) and $f(x)$ (green). The solid black curves are the probability mass functions of $X$ and $Y$ and the dashed curves are the solid curves scaled by a factor of $\eee^\epsilon$. The regions with areas $\alpha$ and $\beta$ are shaded with vertical lines and the region above $e(x)$ and below $f(x)$ is shaded with horizontal lines. The sets $S$, $T$, and $T'$ from the proof are also depicted.}
\label{fig:BSlem}
\end{figure}
Indeed, when we sum $e(x)$ and $f(x)$ over
%
all $x$, we obtain the following.   %
\begin{eqnarray*}
\sum_x e(x) &=& \sum_{x\in S} e(x) + \sum_{x\notin S} e(x)\\
&=& \sum_{x\in S} \eee^{\epsilon}\cdot \Pr[Y=x] + \sum_{x\notin S} \Pr[X=x]\\
&=& \eee^{\epsilon}\cdot \Pr[Y\in S] + \Pr[X\notin S]\\
&=& \Pr[X\in S]-\alpha + \Pr[X\notin S]\\
&=& 1-\alpha\,.
\end{eqnarray*}
Similarly, we have
$$\sum_x f(x) = 1-\beta.$$
If $\alpha=\beta=\delta$, then we're done. Otherwise, we will modify $e$ and $f$ to ensure that $\alpha=\beta$ and then we will modify them again to achieve $\alpha=\beta=\delta$. Suppose without loss of generality that $\alpha > \beta$.
Then we will reduce the function $f$ on the set $T' = \{ x : \Pr[Y=x] > \Pr[X=x]\}\supseteq T$ (see \expref{Figure}{fig:BSlem}) to reduce the sum 
$\sum_x f(x)$ by $\alpha-\beta$ (while maintaining
all the other conditions).   The only condition that might be violated if we reduce the function $f$ is the one that $e(x) \leq \eee^{\epsilon}\cdot f(x)$. So we just need to confirm that
\[
  \sum_{x\in T'} (f(x) - \eee^{-\epsilon}\cdot e(x))
\]
is at least $\alpha-\beta$ to be able to reduce $f$ as much as we
need.  We have
$$\sum_{x\in T'} (f(x) - \eee^{-\epsilon}\cdot e(x)) \geq \sum_{x\in T'} (f(x) - e(x))\,,$$
so it suffices to show that the area of the region that is above $e(x)$ and below $f(x)$ is at least $\alpha-\beta$.  To see this,
we make the following observations.
\begin{enumerate}
\item The area of the region that is above $\Pr[X=x]$ and below $\Pr[Y=x]$ equals the area of the region that is above $\Pr[Y=x]$ and below $\Pr[X=x]$.
\begin{eqnarray*}
\sum_{x\in T'} \left(\Pr[Y=x]-\Pr[X=x]\right)
&=& \Pr[Y\in T']-\Pr[X\in T']\\[-1ex]
&=& (1-\Pr[Y\notin T'])-(1-\Pr[X\notin T'])\\[1ex]
&=& \sum_{x\notin T'} \left(\Pr[X=x]-\Pr[Y=x]\right).
\end{eqnarray*}
(This quantity is simply the total variation distance between
$X$ and $Y$.)
\item The area of the region that is above $\Pr[X=x]$ and below $\Pr[Y=x]$ equals $\beta$ plus the area of the region that is above $e(x)$ and below $f(x)$.
\begin{eqnarray*}
\sum_{x\in T'} \left(\Pr[Y=x]-\Pr[X=x]\right)
&=& \sum_{x\in T'} (\Pr[Y=x] - f(x)) + \sum_{x\in T'} (f(x) - \Pr[X=x])\\
&=& \sum_{x\in T} (\Pr[Y=x]-f(x)) + \sum_{x\in T'} (f(x) - e(x))\\
&=& \beta+\sum_{x\in T'} (f(x) - e(x))\,.
\end{eqnarray*}
\item The area of the region that is above $\Pr[Y=x]$ and below
$\Pr[X=x]$ is at least $\alpha$.
\begin{eqnarray*}
\sum_{x\notin T'} \left(\Pr[X=x]-\Pr[Y=x]\right)
&\geq& \sum_{x\in S} (\Pr[X=x] - \eee^\epsilon\cdot \Pr[Y=x]\\
&=& \alpha\,.
\end{eqnarray*}
\end{enumerate}
Putting it all together, we have
\begin{eqnarray*}
\sum_{x\in T'} (f(x) - \eee^{-\epsilon}\cdot e(x)) 
&\geq& \sum_{x\in T'} (f(x) - e(x))\\
&=& \sum_{x\in T'} \left(\Pr[Y=x]-\Pr[X=x]\right) - \beta\\
&\geq& \alpha-\beta\,.
\end{eqnarray*}
\iffalse
+ \sum_{x\in T'} (f(x) - \Pr[X=x])\\
&=& \sum_{x\in T} (\Pr[Y=x]-f(x)) + \sum_{x\in T'} (f(x) - e(x))\\
&=& \beta+\sum_{x\in T'} (f(x) - e(x)).
&=& \sum_{x\in T'} (\Pr[Y=x] - e(x)) + \sum_{x\in T'} (f(x) - \Pr[Y=x])\\
&=& \Pr[Y\in T']-\Pr[X\in T'] + \sum_{x\in T} (\eee^{\epsilon}\cdot \Pr[X=x] - \Pr[Y=x])\\
&=& \Pr[X\notin T']-\Pr[Y\notin T'] + \eee^{\epsilon}\cdot \Pr[X\in T]-\Pr[Y\in T]\\
&\geq& \Pr[X\in S]- \Pr[Y\in S] - \beta\\
&\geq& \Pr[X\in S]-\eee^{\epsilon}\cdot \Pr[Y\in S]-\beta\\
&=& \alpha-\beta.
\end{eqnarray*}
\fi
So we can afford to reduce the sum over all $x$ of $f(x)$ by $\alpha-\beta$ without violating the other conditions and thus have found two functions $e$ and $f$ such that 
\begin{enumerate}
\item for all $x$, $0\leq e(x) \leq \Pr[X=x]$ and $0\leq f(x) \leq \Pr[Y=x]$;
\item for all $x$, $e(x)\leq \eee^{\epsilon}\cdot f(x)$ and $f(x)\leq \eee^{\epsilon}\cdot e(x)$;
\item $\sum_x e(x) = \sum_x f(x) \geq 1-\delta$.
\end{enumerate}
Suppose $\sum_x e(x) = \sum_x f(x)=1-\delta_0 > 1-\delta$. Then we can scale them both by a multiplicative factor of $(1-\delta_0)/(1-\delta)$ and achieve all the desired conditions.
\end{proof}
Now we can prove \expref{Lemma}{lem:sim} using \expref{Lemma}{lem:events}.

\begin{proof}[Proof of \expref{Lemma}{lem:sim}]
  Let $M$ be an $(\epsilon,\delta)$-DP algorithm and let $D_0,D_1$ be neighboring databases. Let $X\sim M(D_0)$ and $Y\sim M(D_1)$ be random variables and note that
  \[
    D_{\infty}^{\delta}(X\| Y)\leq \epsilon\qquad\text{and}\qquad D_{\infty}^{\delta}(Y\| X)\leq \epsilon
  \]
  because $M$ is $(\epsilon,\delta)$-DP. \expref{Lemma}{lem:events} says that there exist events $E, F$ such that
  \[
    D_{\infty}^{0}(X|_E~\|~Y|_F)\leq \epsilon\,,\qquad D_{\infty}^{0}(Y|_F~\|~X|_E)\leq \epsilon\,, \qquad\text{and}\qquad \Pr[E]=\Pr[F]= 1-\delta\,.
  \]
  Let $R$ be the output space of $M$ and fix $r\in R$. We define the simulating mechanism $T\colon\{0,1,2,3\}\rightarrow R$ as follows.
  \begin{align*}
    \Pr[T(0)=r]&=\Pr[M(D_0)=r|\lnot E]\,,\\[1ex] 
   \Pr[T(1)=r] &= \frac{1}{\eee^{\epsilon}-1}\cdot\left(\eee^{\epsilon}\Pr[M(D_0)=r|E]-\Pr[M(D_1)=r|F]\right)\,,\\
    \Pr[T(2)=r] &= \frac{1}{\eee^{\epsilon}-1}\cdot \left(\eee^{\epsilon}\Pr[M(D_1)=r|F]-\Pr[M(D_0)=r|E]\right)\,,\\[1ex]
    \Pr[T(3)=r]&=\Pr[M(D_1)=r|\lnot F]\,.
  \end{align*}
  Note that for each input to $T$, the probabilities of the outputs sum to 1 and are all non-negative because
  \[
    D_{\infty}^{0}(X|_E~\|~Y|_F)\leq \epsilon \qquad\text{and}\qquad D_{\infty}^{0}(Y|_F~\|~X|_E)\leq \epsilon\,.
  \]
  So the outputs of $T$ form a valid probability distribution.

  We now show that for all $r\in R$,
  \[
    \Pr[T(\tilde{M}_{(\epsilon,\delta)}(0))=r]=\Pr[M(D_0)=r]\,.
  \]
  It follows that
  \[
    T(\tilde{M}_{(\epsilon,\delta)}(0))\sim M(D_0)
  \]
  and
  by symmetry that
  \[
    T(\tilde{M}_{(\epsilon,\delta)}(1))\sim M(D_1)\,,
    \]
    which will complete the proof. We use the shorthand
    $P_{b}(r|H)=\Pr[M(D_b)=r|H]$ for $b\in\{0,1\}$ and any event
    $H$. Fix $r\in R$.
\begin{align*}
  \Pr[T(&\tilde{M}_{(\epsilon,\delta)}(0))=r] \\ =\;&\delta\cdot  \Pr[T(0)=r]+\frac{(1-\delta)\eee^{\epsilon}}{1+\eee^{\epsilon}}\cdot\Pr[T(1)=r]+\frac{(1-\delta)}{1+\eee^{\epsilon}}\cdot\Pr[T(2)=r]+0\\
  =\;&\delta\cdot P_{0}(r|\lnot E)+\frac{(1-\delta)\eee^{\epsilon}}{\eee^{2\epsilon}-1}\cdot\left(\eee^{\epsilon}P_{0}(r|E)-P_{1}(r|F)\right)+\frac{(1-\delta)}{\eee^{2\epsilon}-1}\cdot\left(\eee^{\epsilon}P_{1}(r|F)-P_{0}(r|E)\right)\\
  =\;&\delta\cdot P_{0}(r|\lnot E)+\frac{(1-\delta)\eee^{\epsilon}}{\eee^{2\epsilon}-1}\cdot \eee^{\epsilon}\cdot P_{0}(r|E)-\frac{(1-\delta)}{\eee^{2\epsilon}-1}\cdot P_{0}(r|E)\\[1ex]
  =\;&\delta\cdot P_{0}(r|\lnot E)+(1-\delta)\cdot P_{0}(r|E)\\[1ex]
  =\;& \Pr[\lnot E]\cdot P_{0}(r|\lnot E)+\Pr[E]\cdot P_{0}(r|E)\\[1ex]
  =\;&\Pr[M(D_0)=r]\,.\qedhere
\end{align*}
\end{proof}

So $\tilde{M}_{(\epsilon,\delta)}$ can simulate any $(\epsilon,\delta)$ differentially private algorithm. Since it is known that post-processing preserves differential privacy (\expref{Fact}{fact:postproc}), it follows that to analyze the composition of arbitrary differentially private algorithms, it suffices to analyze the composition of
%
algorithms $\tilde{M}_{(\epsilon_{i},\delta_{i})}$. %

\begin{lemma}
\label{lem:optism}
For all $\epsilon_{1},\ldots,\epsilon_{k}\geq 0$, $\delta_{1},\ldots,\delta_{k}$, $\delta_{g}\in [0,1)$,
\[
\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})= \mathrm{OptComp}(\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})},\delta_{g})\,.
\]
\end{lemma}
\begin{proof}
Since $\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}$ are $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$-differentially private, we have
\begin{align*}
\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})&=\sup\{\mathrm{OptComp}(M_{1},\ldots,M_{k},\delta_{g})\colon M_{i} \;\textrm{is}\;(\epsilon_{i},\delta_{i})\textsc{-DP}\;\forall i\in [k]\}\\
&\geq \mathrm{OptComp}(\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})},\delta_{g})\,.
\end{align*}

For the other direction, it suffices to show that for every $M_{1},\ldots,M_{k}$ that are $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$-differentially private, we have 
\[\mathrm{OptComp}(M_{1},\ldots,M_{k},\delta_{g})\leq\mathrm{OptComp}(\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})},\delta_g)\,.\]
That is, 
\[
\inf\{\epsilon_{g}\geq0\colon(M_{1},\ldots,M_{k}) \;\textrm{is}\; (\epsilon_{g},\delta_{g})\textsc{-DP}\}\leq\inf\{\epsilon_{g}\geq 0\colon(\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}) \;\textrm{is}\; (\epsilon_{g},\delta_{g})\textsc{-DP}\}\,.
\]
So suppose $(\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})})$ is $(\epsilon_{g},\delta_{g})$-DP\@. We will show that $(M_{1},\ldots,M_{k})$ is also $(\epsilon_{g},\delta_{g})$-DP\@. Taking the infimum over $\epsilon_{g}$ then completes the proof.

We know from \expref{Lemma}{lem:sim} that for every pair of neighboring databases $D_{0},D_{1}$, there must exist randomized algorithms $T_{1},\ldots,T_{k}$ such that $T_{i}(\tilde{M}_{(\epsilon_{i},\delta_{i})}(b))$ is identically distributed to $M_{i}(D_{b})$ for all $i\in \{1,\ldots,k\}$. By hypothesis we have 
\[D_{\infty}^{\delta_{g}}\left((\tilde{M}_{(\epsilon_{1},\delta_{1})}(0),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(0))\|(\tilde{M}_{(\epsilon_{1},\delta_{1})}(1),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(1))\right)\leq\epsilon_{g}\,.
\] 
Thus by \expref{Fact}{fact:postproc} we have
\begin{multline*}
D_{\infty}^{\delta_{g}}\big((M_{1}(D_{0}),\ldots,M_{k}(D_{0}))\|(M_{1}(D_{1}),\ldots,M_{k}(D_{1}))\big)\\
{} ={}D_{\infty}^{\delta_{g}}\left((T_{1}(\tilde{M}_{(\epsilon_{1},\delta_{1})}(0)),\ldots,T_{k}(\tilde{M}_{(\epsilon_{k},\delta_{k})}(0)))\|(T_{1}(\tilde{M}_{(\epsilon_{1},\delta_{1})}(1)),\ldots,T_{k}(\tilde{M}_{(\epsilon_{k},\delta_{k})}(1)))\right)\leq\epsilon_{g}\,.\qedhere
\end{multline*}
\end{proof}

Now we are ready to characterize $\mathrm{OptComp}$ for an arbitrary set of differentially private algorithms. 

\begin{namedtheorem}[\expref{Theorem}{thm:optcomp} (restated)]
  For all $\epsilon_{1},\ldots,\epsilon_{k} \geq 0$ and $\delta_{1},\ldots,\delta_{k},\delta_{g}\in [0,1)$,
  \[
    \mathrm{OptComp}((\epsilon_{1},\delta_{1}),(\epsilon_{2},\delta_{2}),\ldots,(\epsilon_{k},\delta_{k}),
    \delta_{g})
  \]
  equals the least value of $\epsilon_{g}\geq 0$ such that
\[
\frac{1}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} \leq 1-\frac{1-\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\,.
\]
\end{namedtheorem}

\begin{proof}[Proof of \expref{Theorem}{thm:optcomp}] 
  Given $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$ and $\delta_{g}$, let $\tilde{M}^{k}(b)$ denote the composition
  \[
    (\tilde{M}_{(\epsilon_{1},\delta_{1})}(b),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(b))
  \]
  and let $\tilde{P}_{b}^{k}(x)$ be the probability mass function of
  $\tilde{M}^{k}(b)$, for $b=0$ and $b=1$. By
  \expref{Lemma}{lem:optism},
  \[ \mathrm{OptComp((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})}
    \]
    is the smallest value of $\epsilon_{g}$ such that

\[
\delta_{g} \geq \max_{Q\subseteq\{0,1,2,3\}^{k}}\left\{\tilde{P}_{0}^{k}(Q)-\eee^{\epsilon_{g}}\cdot\tilde{P}_{1}^{k}(Q), \tilde{P}_{1}^{k}(Q)-\eee^{\epsilon_{g}}\cdot\tilde{P}_{0}^{k}(Q)\right\}.
\]
Since $\tilde{M}$ is symmetric, we can instead consider the smallest value of $\epsilon_{g}$ such that

\begin{equation}
\label{eq:char1}
\delta_{g} \geq \max_{Q\subseteq\{0,1,2,3\}^{k}}\left\{\tilde{P}_{0}^{k}(Q)-\eee^{\epsilon_{g}}\cdot\tilde{P}_{1}^{k}(Q)\right\},
\end{equation}
without loss of generality. Given $\epsilon_{g}$, the set $S\subseteq \{0,1,2,3\}^{k}$ that maximizes the right-hand side is
\[
S=S(\epsilon_{g})=\left\{x\in\{0,1,2,3\}^{k}\;\middle|\; \tilde{P}_{0}^{k}(x)\geq \eee^{\epsilon_{g}}\cdot\tilde{P}_{1}^{k}(x)\right\}.
\]
We can further split $S(\epsilon_{g})$ into $S(\epsilon_{g}) = S_{0}(\epsilon_{g})\cup S_{1}(\epsilon_{g})$ with
\begin{align*}
S_{0}(\epsilon_{g}) &= \left\{x\in \{0,1,2,3\}^{k} \;\middle|\; \tilde{P}_{1}^{k}(x) = 0\right\}, \\
S_{1}(\epsilon_{g}) &= \left\{x\in \{0,1,2,3\}^{k} \;\middle|\; \tilde{P}_{0}^{k}(x) \geq \eee^{\epsilon_{g}}\cdot\tilde{P}_{1}^{k}(x), \;\textrm{and}\; \tilde{P}_{1}^{k}(x) > 0\right\}.
\end{align*}
Note that $S_{0}(\epsilon_{g})\cap S_{1}(\epsilon_{g})=\emptyset$. We have
\[
  \tilde{P}_{1}^{k}(S_{0}(\epsilon_{g}))=0\qquad\text{and}\qquad \tilde{P}_{0}^{k}(S_{0}(\epsilon_{g})) = 1-\Pr[\tilde{M}^{k}(0)\in \{1,2,3\}^{k}] = 1-\prod_{i=1}^{k}(1-\delta_{i})\,.
\]
So
\begin{align}
\tilde{P}_{0}^{k}(S(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S(\epsilon_{g})) &=  \tilde{P}_{0}^{k}(S_{0}(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S_{0}(\epsilon_{g})) + \tilde{P}_{0}^{k}(S_{1}(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S_{1}(\epsilon_{g})) \notag \\
&= 1-\prod_{i=1}^{k}(1-\delta_{i}) + \tilde{P}_{0}^{k}(S_{1}(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S_{1}(\epsilon_{g}))\,. \label{eq:char2}
\end{align}

Now we just need to analyze
\[
  \tilde{P}_{0}^{k}(S_{1}(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S_{1}(\epsilon_{g}))\,.
\]
Notice that $S_{1}(\epsilon_{g})\subseteq \{1,2\}^{k}$ because for all
$x\in S_{1}(\epsilon_{g})$, we have
$\tilde{P}_{0}(x)>\tilde{P}_{1}(x)>0$. So we can write
\begin{eqnarray}
\lefteqn{\tilde{P}_{0}^{k}(S_{1}(\epsilon_{g}))-\eee^{\epsilon_{g}}\cdot\tilde{P}_{1}^{k}(S_{1}(\epsilon_{g}))} \notag \\
&=& \sum_{y\in \{1,2\}^{k}}\max\left\{\prod_{i\colon y_{i}=1}\frac{(1-\delta_{i})\eee^{\epsilon_{i}}}{1+\eee^{\epsilon_{i}}}\cdot\prod_{i\colon y_{i}=2}\frac{(1-\delta_{i})}{1+\eee^{\epsilon_{i}}} - \eee^{\epsilon_{g}}\prod_{i\colon y_{i}=1}\frac{(1-\delta_{i})}{1+\eee^{\epsilon_{i}}}\cdot\prod_{i\colon y_{i}=2}\frac{(1-\delta_{i})\eee^{\epsilon_{i}}}{1+\eee^{\epsilon_{i}}},0\right\}\notag \\
&=&\prod_{i=1}^{k}\frac{1-\delta_{i}}{1+\eee^{\epsilon_{i}}}\sum_{y\in\{0,1\}^{k}}\max\left\{\frac{\eee^{\sum_{i=1}^{k}{{\epsilon_{i}}}}}
{\eee^{\sum_{i=1}^{k}y_{i}\epsilon_{i}}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum_{i=1}^{k}y_{i}\epsilon_{i}}, 0\right\}.\label{eq:char3}
\end{eqnarray}
Combining Equations~\eqref{eq:char1}, \eqref{eq:char2}, and \eqref{eq:char3} together yields
\begin{align*}
\delta_{g} &\geq \tilde{P}_{0}^{k}(S_{0}(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S_{0}(\epsilon_{g})) + \tilde{P}_{0}^{k}(S_{1}(\epsilon_{g})) - \eee^{\epsilon_{g}}\tilde{P}_{1}^{k}(S_{1}(\epsilon_{g})) \\
&= 1-\prod_{i=1}^{k}(1-\delta_{i}) + \frac{\prod_{i=1}^{k}(1-\delta_{i})}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\}.\qedhere
\end{align*}
\end{proof}

We have characterized the optimal composition for an arbitrary set of differentially private algorithms $(M_{1},\ldots,M_{k})$ under the assumption that the algorithms are chosen in advance and all run on the same database. Next we show that $\mathrm{OptComp}$ under this restrictive model of composition is actually equivalent under the more general adaptive composition discussed in \expref{Section}{sect:tech}.

\begin{theorem}
\label{thm:optadaptive}
The privacy parameters $\epsilon_{1},\ldots,\epsilon_{k}\geq 0$, $\delta_{1},\ldots,\delta_{k}\in [0,1)$, satisfy $(\epsilon_{g},\delta_{g})$-differential privacy under adaptive composition for $\epsilon_{g},\delta_{g}\geq 0$ if and only if \[\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})\leq\epsilon_{g}.\]
\end{theorem}
\begin{proof}
First suppose the privacy parameters $\epsilon_{1},\ldots,\epsilon_{k},\delta_{1},\ldots,\delta_{k}$ satisfy $(\epsilon_{g},\delta_{g})$-differential privacy under adaptive composition. Then $\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})\leq \epsilon_{g}$ because adaptive composition is more general than the composition defining $\mathrm{OptComp}$.

Conversely, suppose $\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})\leq\epsilon_{g}$. In particular, this means
\[
  \mathrm{OptComp}(\tilde{M}_{(\epsilon_{1},\delta_{1})},\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})},\delta_{g})\leq\epsilon_{g}\,.
\]
To complete the proof, we must show that the privacy parameters
$\epsilon_{1},\ldots,\epsilon_{k},\delta_{1},\ldots,\delta_{k}$
satisfy $(\epsilon_{g},\delta_{g})$-differential privacy under
adaptive composition.

Fix an adversary $A$. On each round $i$, $A$ uses its coin tosses $r$ and the previous outputs $y_{1},\ldots,y_{i-1}$ to select an $(\epsilon_{i},\delta_{i})$-differentially private algorithm $M_{i}=M_{i}^{r,y_{1},\ldots,y_{i-1}}$ and neighboring databases
\[
  D_{0}=D_{0}^{r,y_{1},\ldots,y_{i-1}}\,,\qquad D_{1}=D_{1}^{r,y_{1},\ldots,y_{i-1}}\,.
\]
Let $V^{b}$ be the view of $A$ with the given privacy parameters under
composition game $b$ for $b=0$ and $b=1$.

\expref{Lemma}{lem:sim} tells us that there exists an algorithm $T_{i}=T_{i}^{r,y_{1},\ldots,y_{i-1}}$ such that
\[
  T_{i}(\tilde{M}_{(\epsilon_{i},\delta_{i})}(b))
\]
is identically distributed to $M_{i}(D_{b})$ for both $b=0,1$ for all
$i\in [k]$. Define $\hat{T}(z_{1},\ldots,z_{k})$ for
$z_{1},\ldots,z_{k}\in\{0,1,2,3\}$ as follows.
\begin{enumerate}
\item Randomly choose coins $r$ for $A$.
\item For $i=1,\ldots,k,$ let $y_{i}\leftarrow T_{i}^{r,y_{1},\ldots,y_{i-1}}(z_{i})$.
\item Output $(r,y_{1},\ldots,y_{k})$.
\end{enumerate}

Notice that \[\hat{T}(\tilde{M}_{(\epsilon_{1},\delta_{1})}(b),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(b))\] is identically distributed to $V^{b}$ for both $b=0,1$. By hypothesis we have 
\[D_{\infty}^{\delta_{g}}\left((\tilde{M}_{(\epsilon_{1},\delta_{1})}(0),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(0))\|(\tilde{M}_{(\epsilon_{1},\delta_{1})}(1),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(1))\right)\leq\epsilon_{g}\,.
\] 
Thus by \expref{Fact}{fact:postproc} we have
\[
D_{\infty}^{\delta_{g}}\big(V^{0}\|V^{1}\big)=D_{\infty}^{\delta_{g}}\left(\hat{T}(\tilde{M}_{(\epsilon_{1},\delta_{1})}(0),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(0))\|\hat{T}(\tilde{M}_{(\epsilon_{1},\delta_{1})}(1),\ldots,\tilde{M}_{(\epsilon_{k},\delta_{k})}(1))\right)\leq\epsilon_{g}\,.\qedhere
\]
\end{proof}
\end{section}

\begin{section}{Hardness of OptComp}

\cclass{\#P} is the class of all counting problems associated with decision
problems in \cclass{NP}. It is a set of functions that count the
%
solutions to some \cclass{NP} problem. More formally,

\begin{definition}
A function $f\colon \{0,1\}^{*}\to\mathbb{N}$ is in the class \cclass{\#P} if there exists a polynomial $p\colon \mathbb{N}\to\mathbb{N}$ and a polynomial time algorithm $M$ such that for every $x\in\{0,1\}^{*}$,
\[
f(x)=\left|\left\{y\in\{0,1\}^{p(|x|)}\colon M(x,y)=1\right\}\right|.
\]
\end{definition}

\begin{definition}
  For functions $f,g\in \cclass{\#P}$, we say that \emph{$f$ reduces
    to $g$} (written $f\leq g$) if there exists a polynomial time
  algorithm $M$ such that for all $x\in\{0,1\}^{*}$, $M(x)=f(x)$ when
  $M$ is given oracle access to $g$.  That is, evaluations of $g$ can
  be done in one time step.
\end{definition}

\begin{definition}
A function $g$ is called \cclass{\#P}\emph{-hard} if every function $f\in \cclass{\#P}$ can be computed in polynomial time given oracle access to $g$. That is, evaluations of $g$ can be done in one time step.
\end{definition}

If a function is \cclass{\#P}-hard, then there is no polynomial-time algorithm for computing it unless there is a polynomial-time algorithm for counting the
%
solutions of all \cclass{NP} problems.

\begin{definition}
A function $f$ is called \cclass{\#P}\emph{-easy} if there is some function $g\in \cclass{\#P}$ such that $f$ can be computed in polynomial time given oracle access to $g$.
\end{definition}

If a function is both \cclass{\#P}-hard and \cclass{\#P}-easy, we say it is \cclass{\#P}-complete. In this section we prove \expref{Theorem}{thm:hardness}.
\begin{namedtheorem}[\expref{Theorem}{thm:hardness} (restated)]
Computing $\mathrm{OptComp}$ is \cclass{\#P}-complete, even on instances where $\delta_{1}=\delta_{2}=\ldots=\delta_{k}=0$ and $\sum_{i\in [k]}\epsilon_{i}\leq \epsilon$ for any desired constant $\epsilon>0$.
\end{namedtheorem}

Proving that computing $\textrm{OptComp}$ is \cclass{\#P}-complete can be broken into two steps: showing that it is \cclass{\#P}-easy and showing that it is \cclass{\#P}-hard. 

\begin{lemma}
Computing $\textrm{OptComp}$ is \cclass{\#P}-easy.
\end{lemma}
\begin{proof}
For convenience we will view rational $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$ and $\epsilon_{g}$ as given arguments to $\textrm{OptComp}$ and compute $\delta_{g}$. Recall that the two versions of $\textrm{OptComp}$, viewing $\epsilon_{g}$ as given and computing $\delta_{g}$ and vice versa, are equivalent up to a polynomial factor (just run binary search over values of $\delta_{g}$ computing polynomially many bits of precision). So the formulation we choose for the proof will not affect whether $\textrm{OptComp}$ is in \cclass{\#P} or not.  Recall that in our model of computing real valued functions, we will take another input $q$ and we will output an approximation of $\delta_{g}$ to $q$ bits of precision in polynomial time using a \cclass{\#P} oracle where $\delta_{g}$ satisfies the following.
\[
\frac{1}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} = 1-\frac{1-\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\,. 
\]
 Notice that the only part of the expression above that cannot be computed in polynomial time is the summation over subsets of $\{1,\ldots,k\}$. If we knew the sum, computing $\delta_{g}$ would be easy given our inputs. We show how to compute the sum in polynomial time using a \cclass{\#P} oracle and it follows that computing $\delta_{g}$ is \cclass{\#P}-easy.

 Define $f\colon 2^{[k]}\to \mathbb{R}$ as
 \[
   f(S)= \max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\}\,.
 \]
 $f$ is computable in polynomial time (to any desired precision). Let
 $\hat{f}$ be a function computable in polynomial time where
 $\left|\hat{f}(S)-f(S)\right|< {1}/{2^{q+k}}$ for all $S$. Set
 $m=10^{q}$. Now define the function
 $g\colon 2^{[k]}\times\mathbb{N} \to \{0,1\}$ as follows.
\[
g(S,n) = \begin{dcases}
1 & \mathrm{if}~m\cdot \hat{f}(S)\geq n, \\
0 & \mathrm{otherwise}.
\end{dcases}
\]

We can now phrase a decision problem in \cclass{NP}: Does there exist a pair $(S,n)$ such that $g(S,n)=1$? This is in \cclass{NP} because given a witness $(S,n)$, we can compute $m\cdot \hat{f}(S)$ and compare the output to $n$, thereby verifying the solution, in polynomial time. Since this is an \cclass{NP} problem, a \cclass{\#P} oracle can count the
%
solutions to it in one time step. Notice that for every set $S$, the number of solutions (pairs of the form $(S,n)$ satisfying $g(S,n)=1$) is exactly $m\cdot \hat{f}(S)$ because $g$ will output $1$ for $g(S,1), g(S,2), \ldots, g(S,m\cdot \hat{f}(S))$. So over all possible sets $S$, the number of solutions as counted by the \cclass{\#P} oracle equals $m\cdot\sum_{S\subseteq [k]}\hat{f}(S)$. Dividing this by $m$ gives us the sum up to an additive error of ${2^{k}}/{2^{q+k}} = {1}/{2^{q}}$, which can be used to compute $\delta_{g}$ to $q$ bits of precision in polynomial time. This only required one call to a \cclass{\#P} oracle. So computing $\textrm{OptComp}$ is \cclass{\#P}-easy.
\end{proof}

Next we show that computing $\textrm{OptComp}$ is also \cclass{\#P}-hard through a series of reductions. We start with a multiplicative version of the partition problem that is known to be \cclass{\#P}-complete by Ehrgott~\cite{Ehr00}. The problems in the chain of reductions are defined below. 

\begin{definition}
$\#\textsc{INT-PARTITION}$ is the following problem. Given a set
$Z = \{z_{1}, z_{2}, \ldots, z_{k}\}$ of positive integers, count the
%
partitions $P\subseteq [k]$ such that
\[\prod_{i\in P}z_{i} - \prod_{i\not\in P}z_{i} = 0\,.\]
\end{definition}

All of the remaining problems in our chain of reductions take inputs $\{w_{1},\ldots,w_{k}\}$ where $1\leq w_{i}\leq e$ is the $D$-th root of a positive integer $z_{i}$ for all $i\in [k]$ and some positive integer $D$. All of the reductions we present actually hold for every positive integer $D$, including $D=1$ (in which case the inputs are integers). However, we will constrain $D$ to be large enough so that our inputs are in the range $[1,e]$. This is because in the final reduction to $\textrm{OptComp}$, $\epsilon_{i}$ values in the proof are set to $\ln(w_{i})$. We want to show that our reductions hold for reasonable values of
%
the $\epsilon_i$  %
in a differential privacy setting so throughout the proofs we use
%
the $w_{i}\in [1,e]$   %
to correspond to
%
the $\epsilon_{i}\in [0,1]$   %
in the final reduction. In fact, we will later state our reductions as applying to instances where $\prod_{i}w_{i}\leq \eee^{\epsilon}$ (and hence $\sum_{i}\epsilon_{i}\leq \epsilon$) for any desired $\epsilon>0$. 

\begin{definition}   %
$\#\textsc{PARTITION}$ is the following problem. Given a
%
%
positive integer  %
$D\in\mathbb{N}$ and a set $W = \{w_{1}, w_{2}, \ldots, w_{k}\}$ of real numbers where $1\leq w_{1},\ldots,w_{k}\leq e$ are $D$-th roots of positive integers $z_{1},\dots z_{k}$,
%
count the
%
partitions $P\subseteq [k]$ such that
\[\prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i} = 0\,.\]
(The real numbers $w_{1},\ldots, w_{k}$ are specified in the input by $z_{1},\ldots,z_{k}$ and $D$ with the input size being the combined bit-length of these integers in binary.)
\end{definition}

\begin{definition}    %
  $\#\textsc{T-PARTITION}$ is the following problem. Given a
%
positive integer   %
  $D\in\mathbb{N}$, a set
  $W = \{w_{1}, w_2 \ldots, w_{k}\}$ of real numbers
and a \emph{positive} real number $T$,
where $1\leq w_{1},\ldots,w_{k}\leq e$ are $D$-th roots of
positive integers $z_{1},\dots z_{k}$,
%
and $T=\sqrt[2D]{t}-\sqrt[2D]{t'}$ for two integers $t,t'$, count the
%
partitions $P\subseteq [k]$ such that
\[\prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i} = T.\]
(The real numbers $w_{1},\ldots, w_{k}$ and $T$ are specified in the input by $z_{1},\ldots,z_{k},t,t'$ and $D$ with the input size being the combined bit-length of these integers in binary.)
\end{definition}

\begin{definition}  %
  $\textsc{SUM-PARTITION}$ is the following problem. Given a 
%
%
positive integer  %
$D\in\mathbb{N}$ and a set $W = \{w_{1}, w_{2}, \ldots, w_{k}\}$ of real numbers where $1\leq w_{1},\ldots,w_{k}\leq e$ are $D$-th roots of positive integers $z_{1},\dots z_{k}$,
%
and a rational number $r>1$, find
\[
\sum_{P\subseteq [k]}\max\left\{\prod_{i\in P}w_{i} - r\cdot\prod_{i\not\in P}w_{i},0\right\}.
\]
(The real numbers $w_{1},\ldots, w_{k}$ are specified in the input by $z_{1},\ldots,z_{k}$ and $D$ with the input size being the combined bit-length of these integers and the numerator and denominator of $r$ in binary.)
\end{definition}
Since the output of SUM-PARTITION is irrational, the actual computational problem is defined according to our convention in \expref{Section}{sect:tech} for computing real-valued functions. That is, given an additional input $q$, compute a number $y$ such that
\[
\left|y-\sum_{P\subseteq [k]}\max\left\{\prod_{i\in P}w_{i} - r\cdot\prod_{i\not\in P}w_{i},0\right\}\right|<\frac{1}{2^{q}}.
\]
We prove that computing $\textrm{OptComp}$ is \cclass{\#P}-hard by the following series of reductions.
\[
\#\textsc{INT-PARTITION} \leq \#\textsc{PARTITION} \leq \#\textsc{T-PARTITION} \leq \textsc{SUM-PARTITION} \leq \mathrm{OptComp}\,.
\]
Since $\#\textsc{INT-PARTITION}$ is known to be \cclass{\#P}-complete~\cite{Ehr00}, the chain of reductions will prove that $\mathrm{OptComp}$ is \cclass{\#P}-hard.   

\begin{lemma}
For every constant $c>1$, $\#\textsc{PARTITION}$ is \cclass{\#P}-hard, even on instances where $\prod_{i}w_{i}\leq c$.
\end{lemma}
\begin{proof}
Given an instance of $\#\textsc{INT-PARTITION}$, $\{z_{1},\ldots,z_{k}\}$, we show how to find the solution in polynomial time using a $\#\textsc{PARTITION}$ oracle. Set $D=\lceil{\log_{c}(\prod_{i}z_{i})}\rceil$ and $w_{i}=\sqrt[D]{z_{i}} \;\forall i\in [k]$. Note that $\prod_{i}w_{i}=\left(\prod_{i}z_{i}\right)^{1/D}\leq c$.
Let $P\subseteq [k]$.
\begin{align*}
\prod_{i\in P}w_{i} = \prod_{i\not\in P}w_{i}  &\iff \left(\prod_{i\in P}w_{i}\right)^{D} = \left(\prod_{i\not\in P}w_{i}\right)^{D} \\
&\iff \prod_{i\in P}z_{i} = \prod_{i\not\in P}z_{i}\,.
\end{align*}
There is a one-to-one correspondence between solutions to the $\#\textsc{PARTITION}$ problem and solutions to the given $\#\textsc{INT-PARTITION}$ instance. We can solve $\#\textsc{INT-PARTITION}$ in polynomial time with a $\#\textsc{PARTITION}$ oracle. Therefore $\#\textsc{PARTITION}$ is \cclass{\#P}-hard.
\end{proof}

\begin{lemma}
For every constant $c>1$, $\#\textsc{T-PARTITION}$ is \cclass{\#P}-hard, even on instances where $\prod_{i}w_{i}\leq c$.
\end{lemma}
 
\begin{proof}
  Let $c>1$ be a constant. We will reduce from $\#\textsc{PARTITION}$, so consider an instance of the $\#\textsc{PARTITION}$ problem, $W = \{w_{1}, w_{2}, \ldots, w_{k}\}$ of $D$-th roots of integers $z_{1},\ldots,z_{k}$.
%
%
We may assume $\prod_{i}w_{i}\leq \sqrt{c}$ since $\sqrt{c}$ is also a constant greater than $1$.

Set $W'=W\cup\{w_{k+1}\}$, where $w_{k+1}=\prod_{i=1}^{k}w_{i}$. Notice that
\[
  \prod_{i=1}^{k+1}w_{i}\leq (\sqrt{c})^{2}=c\,.
\]
Set $T = \sqrt{w_{k+1}}\left(w_{k+1}-1\right)$. Notice that
$w_{k+1}=\left(\prod_{i=1}^{k}z_{i}\right)^{\frac{1}{D}}$ so by
setting integers
\[
  t=\left(\prod_{i=1}^{k}z_{i}\right)^{3}\qquad\text{and}\qquad
  t'=\prod_{i=1}^{k}z_{i}
\]
we get that
\[
T=\sqrt[2D]{t}-\sqrt[2D]{t'}
\]
which meets the input requirement for $\#\textsc{T-PARTITION}$. So we can use a $\#\textsc{T-PARTITION}$ oracle to count
%
partitions $Q\subseteq \{1,\ldots,k+1\}$ such that
\[\prod_{i\in Q}w_{i} - \prod_{i\not\in Q}w_{i} = T.\]

Let $P=Q\cap\{1,\ldots,k\}$. We will argue that $\prod_{i\in Q}w_{i}-\prod_{i\not\in Q}w_{i}=T$ if and only if $\prod_{i\in P}w_{i}=\prod_{i\not\in P}w_{i}$, which completes the proof. There are two cases to consider: $w_{k+1}\in Q$ and $w_{k+1}\not\in Q$.

$\textbf{Case 1:}$ $w_{k+1}\in Q$. In this case, we have
\begin{align*}
&w_{k+1}\cdot\left(\prod_{i\in P}w_{i}\right) - \prod_{i\not\in P}w_{i} = \prod_{i\in Q}w_{i}-\prod_{i\not\in Q}w_{i}= T = \sqrt{w_{k+1}}\left(w_{k+1}-1\right) \\
  &\iff \left(\prod_{i\in[k]}w_{i}\right)\left(\prod_{i\in P}w_{i}\right)^{2} - \prod_{i\in[k]}w_{i}=\sqrt{\prod_{i\in[k]}w_{i}}\left(\prod_{i\in[k]}w_{i}-1\right)\left(\prod_{i\in P}w_{i}\right)  &&\text{multiplied
%
by} \prod\limits_{i\in P}w_{i}\\
&\iff \left(\prod_{i\in P}w_{i}-\sqrt{\prod_{i\in[k]}w_{i}}\right)\left(\prod_{i\in[k]}w_{i}\prod_{i\in P}w_{i} + \sqrt{\prod_{i\in[k]}w_{i}}\right)=0 &&\text{factored quadratic in} \prod\limits_{i\in P}w_{i} \\
&\iff \prod_{i\in P}w_{i}=\sqrt{\prod_{i\in[k]}w_{i}}\\
&\iff \prod_{i\not\in P}w_{i}=\prod_{i\in P}w_{i}.
\end{align*}

So there is a one-to-one correspondence between solutions to the $\#\textsc{T-PARTITION}$ instance $W'$ where $w_{k+1}\in Q$ and solutions to the original $\#\textsc{PARTITION}$ instance $W$.

\vspace*{\baselineskip}
$\textbf{Case 2:}$ $w_{k+1}\not\in Q$. Solutions now look like

\[
\prod_{i\in P}w_{i} - \prod_{i\in[k]}w_{i}\prod_{i\not\in P}w_{i} = \sqrt{\prod_{i\in[k]}w_{i}}\left(\prod_{i\in[k]}w_{i}-1\right).
\]

One way this can be true is if $w_{i}=1$ for all $i\in[k]$.  We can check ahead of time if our input set $W$ contains all ones. If it does, then there are $2^{k}-2$ partitions that yield equal products (all except $P=[k]$ and $P=\emptyset$) so we can just output $2^{k}-2$ as the solution and not even use our oracle. The only other way to satisfy the above expression is for
\[
  \prod_{i\in P}w_{i} > \prod_{i\in [k]}w_{i}
\]
which cannot happen because $P\subseteq [k]$. So there are no
solutions in the case that $w_{k+1}\not\in Q$.

Therefore the output of the $\#\textsc{T-PARTITION}$ oracle on $W'$ is the solution to the $\#\textsc{PARTITION}$ problem. So $\#\textsc{T-PARTITION}$ is \cclass{\#P}-hard.
\end{proof}

For the next two proofs we will make use of the following fact to bound the amount of precision needed when approximating irrational numbers by rational ones in our reductions.

\begin{fact}
\label{mvt}
For all real numbers $y>x$ and functions $f$ that are differentiable on the interval $[x,y]$,
\[
f(y)-f(x)\geq (y-x)\cdot \min_{z\in(x,y)}f'(z)\,.
\]
\end{fact}


\begin{lemma}
  For every constant $c>1$, $\textsc{SUM-PARTITION}$ is \cclass{\#P}-hard even on instances where $\prod_{i}w_{i}\leq c$ and where there are no partitions $S$ such that
  \[
    \prod_{i\in S}w_{i}=r\cdot\prod_{i\not\in S}w_{i}\,.
  \]
\end{lemma}

\begin{proof}
  We will use a $\textsc{SUM-PARTITION}$ oracle to solve $\#\textsc{T-PARTITION}$ given a set $W=\{w_{1}, \ldots, w_{k}\}$ of $D$-th roots of positive integers $z_{1},\ldots,z_{k}$,
%
%
%
and a positive real number $T=\sqrt[2D]{t}-\sqrt[2D]{t'}$ for integers $t,t'$ given in the input. Notice that for every $x>0$,
\begin{align*}
\prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i}=x &\implies \prod_{i\in P}w_{i} - \frac{\prod_{i\in[k]}w_{i}}{\prod_{i\in P}w_{i}} = x \\
&\implies \exists\; j\in\mathbb{Z}^{+} \mathrm{such~that} \sqrt[D]{j}-\frac{\prod_{i\in[k]}w_{i}}{\sqrt[D]{j}}=x\,.
\end{align*}

Above, $j$ must be a positive integer greater than $\left(\prod_{i=1}^{k}z_{i}\right)^{1/2}$, which tells us that the gap in products from every partition must take a particular form. This means that for a given $D$ and $W$, $\#\textsc{x-PARTITION}$ can only be non-zero on a discrete set of possible values of $x$. So given our $\#$T-PARTITION instance we can find a $T'>T$ such that the above has no solutions for $x$ in the interval $(T,T')$. Specifically, solve the above quadratic for $\sqrt[D]{j}$. If $j$ is not an integer, then we know the answer to the $\#$T-PARTITION instance is 0, so assume $j$ is an integer and set $T'=\sqrt[D]{j+1}-\prod_{i}w_{i}/\sqrt[D]{j+1}$. We can also find an interval $(T'',T)$ just below $T$ where no value of $x$ in the interval can yield a solution above by setting $T''=\sqrt[D]{j-1}-\prod_{i}w_{i}/\sqrt[D]{j-1}$. We use these discreteness properties twice in the proof. Also notice that these intervals are not too small.
\begin{claim}
\label{claim1}
$T'-T\geq 2^{-\text{poly}(n)}$ and $T-T''\geq 2^{-\text{poly}(n)}$ where $n$ is the input length (\ie, the bit-lengths of the integers $z_{1},\ldots,z_{k}, t, t'$).
\end{claim}

\begin{claim_proof}[Proof of Claim]
\begin{align*}
T'-T&=\sqrt[D]{j+1}-\frac{\prod_{i\in[k]}w_{i}}{\sqrt[D]{j+1}}-\sqrt[D]{j}+\frac{\prod_{i\in[k]}w_{i}}{\sqrt[D]{j}} \geq \sqrt[D]{j+1}-\sqrt[D]{j} \geq \frac{1}{D(j+1)}\,,
\end{align*}
where the last inequality follows from \expref{Fact}{mvt}. This final value is only exponentially small because $j$ is upper bounded by $\prod_{i=1}^{k}z_{i}$, which is at most exponentially large in the bit-length of the
%
$z_{i}$.   %
A very similar proof shows that $(T'',T)$ is only exponentially small.
\end{claim_proof}

This means that we can always find $\hat{T}\in (T,T')$ such that $\hat{T}$ is rational and can be fully specified with a bit-length that is polynomial in the input length. Fix such a quantity $\hat{T}$. For all $y>0$, define
\[
  P^{y} \equiv \left\{P\subseteq [k] \;\middle|\; \prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i} \geq y\right\}\,.
\]
Then, since $x$-PARTITION has no solutions for $x\in (T,T')$,
\begin{align*}
\left|\left\{P\subseteq [k] \;\middle|\; \prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i} = T\right\}\right| &= \left|P^{T}\backslash P^{\hat{T}}\right| \\
&= \frac{1}{T}\left(\sum_{P\in P^{T}\backslash P^{\hat{T}}}\left(\prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i}\right)\right)\\
&= \label{8} \frac{1}{T}\left(\sum_{P\in P^{T}}\left(\prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i}\right) - \sum_{P\in P^{\hat{T}}}\left(\prod_{i\in P}w_{i} - \prod_{i\not\in P}w_{i}\right)\right).
\end{align*}

We now show how to compute the two sums in the final term using the $\textsc{SUM-PARTITION}$ oracle. We will give the procedure for computing
\[
  \sum\limits_{P\in P^{T}}\left(\prod\limits_{i\in P}w_{i} - \prod\limits_{i\not\in P}w_{i}\right)
\]
and the case with $\hat{T}$ will follow by symmetry. The oracle returns a real number, so by our model of computing real valued functions, we will also give the oracle an additional input that specifies the number of bits of precision in its output. Ultimately we only need to approximate each sum to within $\pm T/4$. This will give an approximation to the $\#\textsc{T-PARTITION}$ problem to within $\pm 1/2$, thereby solving it by rounding the approximation because the solution will be an integer. We want to set the input $r$ to the $\textsc{SUM-PARTITION}$ oracle to be $r=r_{T}$ such that for all $P\subseteq [k]$, we have
\begin{equation}
\label{r}
\prod\limits_{i\in P}w_{i}-r_{T}\cdot\prod\limits_{i\not\in P}w_{i}\geq 0 \iff \prod\limits_{i\in P}w_{i}-\prod\limits_{i\not\in P}w_{i}\geq T.
\end{equation}

Taking $w=\prod_{i\in [k]}w_{i}$ and thinking of $v=\prod_{i\in P}w_{i}$, it suffices that all positive solutions to each of the following two inequalities are the same.
\[
v-r_{T}\frac{w}{v}\geq 0\qquad\text{and}\qquad v-\frac{w}{v}\geq T.
\]
The positive solutions to the left one are $v\geq \sqrt{r_{T}w}$, and to the right one are $v\geq (T+\sqrt{T^{2}+4w})/2$. Setting the right-hand sides equal gives 
\begin{equation}
\label{requation}
r_{T}=\frac{\left(T+\sqrt{T^{2}+4w}\right)^{2}}{4w}\,.
\end{equation}

Since $r_{T}$ might be irrational and SUM-PARTITION takes as input rational values of $r$, we need to find a rational $r$ that approximates $r_{T}$ and preserves the set of solutions $P^{T}$. Recall from \expref{Claim}{claim1} that there is an (only) exponentially small interval $(T'',T)$ below $T$ such that for all $\bar{T}\in (T'',T)$, $P^{T}=P^{\bar{T}}$. This translates to a corresponding interval $(r_{T''},r_{T})$ such that for all $r\in (r_{T''},r_{T})$, Equivalence~\eqref{r} holds. Furthermore, this interval is also only exponentially small.

\begin{claim}
\label{claim2}
$r_{T}-r_{T''}\geq 2^{-\text{poly}(n)}$ where $n$ is the input length (\ie, the bit-lengths of the integers $z_{1},\ldots,z_{k}, t, t'$).
\end{claim}
\begin{claim_proof}
To see this, view $r_{T}$ from Equation~\eqref{requation} as a function $r(T)$ of $T$, and calculate the derivative.

\[
r'(T)=\frac{\left(T+\sqrt{T^{2}+4w}\right)^{2}}{2w\cdot \sqrt{T^{2}+4w}}\,.
\]
\expref{Fact}{mvt} says that
\[
r_{T}-r_{T''}=r(T)-r(T'')
\geq \left(\min_{z\in(T'',T)}r'(z)\right)\cdot(T-T'')
\geq (T-T'')\cdot\text{poly}(T)\,.
\]
(Recall that $1\leq w=\prod_{i}w_{i}\leq c$). This is only exponentially small in the input length by \expref{Claim}{claim1}.
\end{claim_proof}

So we can choose a rational $r\in (r_{T''},r_{T})$ that can be specified with a number of bits that is polynomial in the input length and preserves
\[
  P^{T} = \left\{P\subseteq [k]\;\middle|\; \prod_{i\in P}w_{i}-r\cdot\prod_{i\not\in P}w_{i}\geq 0\right\}\,.
\]
However the SUM-PARTITION oracle gives us
\[
\sum_{P\subseteq [k]}\max\left\{\prod_{i\in P}w_{i} - r\cdot\prod_{i\not\in P}w_{i},0\right\}=\sum_{P\in P^{T}}\left(\prod_{i\in P}w_{i}-r\cdot\prod_{i\not\in P}w_{i}\right)\,,
\]
whereas we want to compute the right-hand side without the $r$ coefficient. To get this we just pick another rational $r'\in (r_{T''},r_{T})$ such that $r'-r\geq 2^{-\text{poly}(n)}$. If precision were not an issue, we could run our $\textsc{SUM-PARTITION}$ oracle for $r$ and $r'$ and receive the output
\begin{align*}
&S_{1}=\sum_{P\in P^{T}}\left(\prod_{i\in P}w_{i}-r\cdot\prod_{i\not\in P}w_{i}\right), \\
&S_{2}=\sum_{P\in P^{T}}\left(\prod_{i\in P}w_{i}-r'\cdot\prod_{i\not\in P}w_{i}\right).
\end{align*}

Then the following linear combination of $S_{1}$ and $S_{2}$ gives us what we want.
\[
\frac{r'-1}{r'-r}\cdot S_{1}-\frac{r-1}{r'-r}\cdot S_{2}=\sum_{P\in P^{T}}\left(\prod_{i\in P}w_{i}-\prod_{i\not\in P}w_{i}\right).
\]

\begin{claim}
  Computing $S_{1}$ and $S_{2}$ to within $\pm 2^{-\text{poly}(n)}$ yields an approximation of
  \[
    \sum_{P\in P^{T}}\left(\prod_{i\in P}w_{i}-\prod_{i\not\in P}w_{i}\right)
  \]
  to within $\pm T/4$.
\end{claim}
\begin{claim_proof}
  We just need to approximate $S_{1}$ and $S_{2}$ to within
  \[
    \pm \frac{T}{8}\cdot \frac{r'-r}{r'-1}
  \]
  to get the desired precision. This additive error is only
  exponentially small by \expref{Claim}{claim2}.
\end{claim_proof}

Running this whole procedure again for $\hat{T}\in (T,T')$, which we fixed above gives us all the information we need to count the
%
solutions to the $\#\textsc{T-PARTITION}$ instance we were given. We can solve $\#\textsc{T-PARTITION}$ in polynomial time with four calls to a $\textsc{SUM-PARTITION}$ oracle. Therefore $\textsc{SUM-PARTITION}$ is \cclass{\#P}-hard. 
\end{proof}


\noindent Now we prove that computing $\textrm{OptComp}$ is \cclass{\#P}-complete. 

\begin{proof}[Proof of \expref{Theorem}{thm:hardness}]
We have already shown that computing $\textrm{OptComp}$ is \cclass{\#P}-easy. Here we prove that it is also \cclass{\#P}-hard, thereby proving \cclass{\#P}-completeness.

We are given an instance $D$, $W=\{w_{1},\ldots,w_{k}\}, r\in\mathbb{Q},$ and $q$ of $\textsc{SUM-PARTITION}$, where $\forall i\in[k]$, $w_{i}$ is the $D$-th root of a corresponding integer $z_{i}$, $\prod_{i}w_{i}\leq c$, and $q$ specifies the desired number of bits of precision in the output. If we disregard precision, we would like to set $\epsilon_{i}=\ln(w_{i})\; \forall i\in [k]$, $\delta_{1}=\delta_{2}=\ldots \delta_{k}=0$ and $\epsilon_{g}=\ln(r)$. Note that $\sum_{i}\epsilon_{i}=\ln\left(\prod_{i}w_{i}\right)\leq \ln(c)$. Since we can take $c$ to be an arbitrary constant greater than $1$, we can ensure that $\sum_{i}\epsilon_{i}\leq\epsilon$ for an arbitrary $\epsilon>0$.

Again we will use the version of $\mathrm{OptComp}$ that takes $\epsilon_{g}$ as input and outputs $\delta_{g}$. After using an $\mathrm{OptComp}$ oracle to find $\delta_{g}$ we know the optimal composition Equation~\eqref{eq:1} from \expref{Theorem}{thm:optcomp} is satisfied.
\[
\frac{1}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} = 1-\frac{1-\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}=\delta_{g}.
\]
Thus we can compute
\begin{align*}
\delta_{g}\cdot\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}&=\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\}\\
&= \sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\prod_{i\in S}w_{i} - r\cdot \prod_{i\not\in S}w_{i}, 0\right\}.
\end{align*}

This last expression is exactly the solution to the instance of $\textsc{SUM-PARTITION}$ we were given. Taking precision into account, the input $\textsc{SUM-PARTITION}$ instance has an additional input $q$ that specifies the desired number of bits of precision in the output and we can only pass OptComp rational values so we will have to approximate $\epsilon_{i}=\ln(w_{i})$ for all $i$ and $\epsilon_{g}=\ln(r)$. Again there is a worry that when we approximate these values the set of partitions $S$ that make
\[
  \prod_{i\in S}w_{i}-r\cdot\prod_{i\not\in S}w_{i}>0
\]
might change. We want to get enough precision in our inputs so that
the set of partitions over which we sum does not change and enough
precision so that the output is accurate to $q$ bits. We will
calculate the approximations required for each of these two goals
separately and the final precision that we use will just be the
maximum of the two. We prove that we can achieve both of these goals
with the next two claims.

\begin{claim}
\label{sameset}
There exists a polynomial $p(n)$ in the length $n$ of the input (the bit-lengths of $z_{1},\ldots,z_{k}, q$, and the numerator and denominator of $r$) such that if $|w_{i}-w'_{i}|\leq 2^{-p(n)}$ for each $i$, then the set of partitions $S$ satisfying 
\[\prod_{i\in S}w_{i}-r\cdot\prod_{i\not\in S}w_{i}>0\]
is the same as the set of partitions satisfying
\[\prod_{i\in S}w'_{i}-r\cdot\prod_{i\not\in S}w'_{i}>0\,.\]
\end{claim}
\begin{claim_proof}
  Recall that SUM-PARTITION is \cclass{\#P}-hard even on instances where there are no partitions $S$ such that
  \[
    \prod_{i\in S}w_{i}=r\cdot\prod_{i\not\in S}w_{i}
  \]
  so we may assume our input instance of SUM-PARTITION has no such
  partitions and still prove the hardness of OptComp. So to ensure
  that we have enough precision such that the set over which we sum
  does not change, we must make the error smaller than the minimum
  possible (in absolute value) nonzero outcome of
  \[
    \prod_{i\in S}w_{i}-r\cdot\prod_{i\not\in S}w_{i}\,.
  \]
  We now bound this quantity. Let
\[
\mathcal{S}=\left\{S\subseteq [k] \;\middle|\; \prod_{i\in S}w_{i}\not=\prod_{i\not \in S}w_{i}\right\}.
\]
Since $r$ is rational, $r=a/b$ for two integers $a$ and $b$. Let $a'=a^{D}$ and $b'=b^{D}$. 
\begin{align*}
    \min_{S\in \mathcal{S}}\left\{\left|\prod_{i\in S}w_{i}-r\cdot\prod_{i\not\in S}w_{i}\right|\right\}
     &= \min_{S\in \mathcal{S}}\left\{\left|\left(\prod_{i\in S}z_{i}\right)^{\frac{1}{D}}-\left(\frac{a'}{b'}\prod_{i\not\in S}z_{i}\right)^{\frac{1}{D}}\right|\right\}\\
    &\geq \min_{S\in \mathcal{S}}\left\{\left|\prod_{i\in S}z_{i}-\frac{a'}{b'}\prod_{i\not\in S}z_{i}\right|\cdot\frac{1}{D\left(\prod_{i\in [k]}z_{i}\right)^{(D-1)/D}}\right\}.
\end{align*}
Where the last line follows from \expref{Fact}{mvt} applied to the function $f(x)=x^{1/D}$.
\[
  1/\left(\prod_{i\in [k]}z_{i}\right)^{(D-1)/D}
\]
is only exponentially small because $\prod_{i\in [k]}z_{i}$ is at most
exponentially large in the bit-length of the integers
$z_{1},\ldots,z_{k}$. We claim that
\[
  \left|\prod_{i\in S}z_{i}-\frac{a'}{b'}\prod_{i\not\in
      S}z_{i}\right|
\]
is at least $1/b'$ for all $S\in\mathcal{S}$. Fix $S\in \mathcal{S}$.
\begin{align*}
   \left| \prod_{i\in S}z_{i}-\frac{a'}{b'}\prod_{i\not\in S}z_{i}\right|=h &\implies  \left|b'\cdot\prod_{i\in S}z_{i}-a'\cdot\prod_{i\not\in S}z_{i}\right|=h\cdot b'\\
    &\implies h\geq 1/b'.
\end{align*}
Where the last implication follows because
\[
  b'\cdot\prod_{i\in S}z_{i}-a'\cdot\prod_{i\not\in S}z_{i}
\]
is just a difference of integers so the closest nonzero value it can
take on is $\pm 1$.
\end{claim_proof}

\begin{claim}
There exists a polynomial $p(n)$ in the length $n$ of the input (the bit-lengths of $z_{1},\ldots,z_{k}, q$, and the numerator and denominator of $r$) such that if $|w_{i}-w'_{i}|\leq 2^{-p(n)}$ for each $i$, then
\[
\left|\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\prod_{i\in S}w'_{i} - r\cdot \prod_{i\not\in S}w'_{i}, 0\right\}-\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\prod_{i\in S}w_{i} - r\cdot \prod_{i\not\in S}w_{i}, 0\right\}\right| \leq 2^{-q}.
\]
\end{claim}
\begin{claim_proof}
 We will choose $p(n)=p_{1}(n)+p_{2}(n)$ where $p_{1}(n)$ is the polynomial that exists from \expref{Claim}{sameset} and $p_{2}(n)$ will be determined later. Define
\[
S^{+}=\left\{S\subseteq [k] \mid \prod_{i\in S}w_{i}-r\cdot\prod_{i\not\in S}w_{i}>0 \right\}.
\]
\expref{Claim}{sameset} says that
\[
S^{+}=\left\{S\subseteq [k] \mid \prod_{i\in S}w'_{i}-r\cdot\prod_{i\not\in S}w'_{i}>0 \right\}.
\]

Now we can write 
\begin{align*}
   & \left|\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\prod_{i\in S}w'_{i} - r\cdot \prod_{i\not\in S}w'_{i}, 0\right\}-\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\prod_{i\in S}w_{i} - r\cdot \prod_{i\not\in S}w_{i}, 0\right\}\right| =\\
   &\left|\sum_{S\in S^{+}}\left(\prod_{i\in S}w'_{i} - r\cdot \prod_{i\not\in S}w'_{i}\right)-\sum_{S\in S^{+}}\left(\prod_{i\in S}w_{i} - r\cdot \prod_{i\not\in S}w_{i}\right)\right| = \\
   &\left|\sum_{S\in S^{+}}\left(\prod_{i\in S}w'_{i}-\prod_{i\in S}w_{i}\right)-\sum_{S\in S^{+}}r\cdot\left(\prod_{i\not\in S}w'_{i}-\prod_{i\not\in S}w_{i}\right)\right|\leq\\
   &\left|\sum_{S\in S^{+}}\left(\prod_{i\in S}w'_{i}-\prod_{i\in S}w_{i}\right)\right|+\left|\sum_{S\in S^{+}}r\cdot\left(\prod_{i\not\in S}w'_{i}-\prod_{i\not\in S}w_{i}\right)\right|.
\end{align*}
Bounding each term in the final expression above by $2^{-(q+1)}$ then gives us the accuracy we want. We will show directly how to bound the second term and the argument for the first term follows symmetrically. By hypothesis we have that for all $S\subseteq[k]$,
\begin{align*}
\prod_{i\not\in S}w_{i}' \leq \prod_{i\not\in S}\left(w_{i}+2^{-p(n)}\right)
\leq \prod_{i\not\in S}\left(1+2^{-p(n)}\right)w_{i} 
\leq \left(1+2^{-p(n)}\right)^{k}\cdot\prod_{i\not\in S}w_{i}
\end{align*}
and similarly 
\[
\prod_{i\not\in S}w_{i}'\geq \left(1-2^{-p(n)}\right)^{k}\cdot\prod_{i\not\in S}w_{i}\,.
\]
It follows that for all $S\subseteq[k]$,
\[
\left(\left(1-2^{-p(n)}\right)^{k}-1\right)\cdot \prod_{i\not\in S}w_{i}\leq \left(\prod_{i\not\in S}w'_{i}-\prod_{i\not\in S}w_{i}\right)\leq \left(\left(1+2^{-p(n)}\right)^{k}-1\right)\cdot \prod_{i\not\in S}w_{i}\,.
\]
Since $|S^{+}|\leq 2^{k}$ and $1\leq \prod_{i\not\in S}w_{i}\leq c$ for all $S$ we get
\[
2^{k}\cdot r\cdot\left(\left(1-2^{-p(n)}\right)^{k}-1\right)\cdot\leq \sum_{S\in S^{+}}r\cdot\left(\prod_{i\not\in S}w'_{i}-\prod_{i\not\in S}w_{i}\right)\leq 2^{k}\cdot r\cdot\left(\left(1+2^{-p(n)}\right)^{k}-1\right)\cdot c\,.
\]
Picking $p_{2}(n)$ such that $p(n)=p_{1}(n)+p_{2}(n)> 2k+\log (rc)+q+1$ then suffices to bound the absolute value of the sum by $2^{-(q+1)}$. Repeating the same calculation for
\[
  \sum_{S\in S^{+}}\left(\prod_{i\in S}w'_{i}-\prod_{i\in S}w_{i}\right)
\]
will yield the same approximation except without the factor of $r$. So
we can bound both terms by $2^{-(q+1)}$ (and therefore their sum by
$2^{-q}$) by approximating each $w_{i}$ to a precision that is
polynomial in $n$, which proves the claim.
\end{claim_proof}

 So by the two claims above we can get an approximation of the $\textsc{SUM-PARTITION}$ instance to $q$ bits of precision in polynomial time with access to an $\mathrm{OptComp}$ oracle. Therefore computing $\mathrm{OptComp}$ is \cclass{\#P}-hard.
\end{proof}
\end{section}


\begin{section}{Approximation of OptComp}
Although we cannot hope to efficiently compute the optimal composition for a general set of differentially private algorithms (assuming $\cclass{P} \not= \cclass{NP}$ or even $\cclass{FP} \not= \cclass{\#P}$), we show in this section that we can approximate $\mathrm{OptComp}$ to arbitrary precision in polynomial time.

\begin{namedtheorem}[\expref{Theorem}{thm:approx} (restated)]
There is a polynomial-time algorithm that given rational $\epsilon_{1},\ldots,\epsilon_{k}\geq 0$, \break $\delta_{1},\ldots, \delta_{k}, \delta_{g} \in [0,1),$ and $\eta\in (0,1)$, outputs $\epsilon^{*}$ satisfying 
\[\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})\leq \epsilon^{*}\leq\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \eee^{-\eta/2}\cdot\delta_{g})+\eta.\]
The algorithm runs in time \[O\left(\frac{k^{3}\cdot\ebar\cdot(1+\ebar)}{\eta}\cdot \log\left(\frac{k^{2}\cdot\ebar\cdot(1+\ebar)}{\eta}\right)\right)\]
 where $\ebar=\sum_{i\in [k]}\epsilon_{i}/k$, assuming constant-time arithmetic operations.
\end{namedtheorem}
We prove \expref{Theorem}{thm:approx} using the following three lemmas:

\begin{lemma}
\label{lem:pseudo}
Given non-negative integers $a_{1},\ldots,a_{k}$, $B$ and weights $w_{1},\ldots,w_{k}\in\mathbb{Q}$, one can compute 
\[\sum_{\substack {S\subseteq [k]~\mathrm{s.t.}\\
\sum\limits_{i\in S}a_{i}\leq B\;\;\;}}\prod_{i\in S}w_{i}\] 
in time $O(Bk)$.
\end{lemma}
Notice that the constraint in \expref{Lemma}{lem:pseudo} is the same one that characterizes knapsack problems. Indeed, the algorithm we give for computing $\sum_{S\subseteq [k]}\prod_{i\in S}w_{i}$ is a slight modification of the known pseudo-polynomial time algorithm for counting knapsack solutions, which uses dynamic programming. Next we show that we can use this algorithm to approximate $\mathrm{OptComp}$. 

\begin{lemma}
\label{lem:dyer}
Given a rational $\eee^{\epsilon_{0}}$ with $\epsilon_{0}\geq 0$ and $\epsilon_{1}=a_{1}\cdot\epsilon_{0},\ldots,\epsilon_{k}=a_{k}\cdot\epsilon_{0},\epsilon^{*}=a^{*}\cdot\epsilon_{0}$ for positive integers $a_{1},\ldots,a_{k},a^{*}$ (given as input), and rational $\delta_{1},\ldots \delta_{k}, \delta_{g} \in [0,1)$, there is an algorithm that determines whether or not $\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g}) \leq \epsilon^{*}$ and runs in time
\[
  O\left(k\cdot\sum_{i=1}^{k}a_{i}\right)
\]
assuming constant-time arithmetic operations.
\end{lemma}

In other words, if the $\epsilon$ values we are given are all integer multiples of some $\epsilon_{0}$ where $\eee^{\epsilon_{0}}$ is rational, we can determine whether or not the composition of those privacy parameters is $(a^{*}\cdot\epsilon_{0},\delta_{g})$-DP in pseudo-polynomial time, for every positive integer $a^{*}$. Running binary search over integers $a^{*}$, we can find the minimum such integer. When $\epsilon_{0}$ is small, this gives us a good overestimate of the optimal composition of the discrete input privacy parameters. This means that given any inputs $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g}$ to OptComp, we can discretize and polynomially bound the $\epsilon_{i}$ values to new values $\epsilon_{i}'$ for all $i\in[k]$ and use \expref{Lemma}{lem:dyer} to approximate OptComp$((\epsilon_{1}',\delta_{1}),\ldots,(\epsilon_{k}',\delta_{k}),\delta_{g})$. The next lemma tells us that this is also a good approximation of OptComp$((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})$. 

\begin{lemma}
\label{lem:goodapprox}
For all $\epsilon_{1},\ldots,\epsilon_{k}, c_{1},\ldots, c_{k}\geq0$ and $\delta_{1},\ldots,\delta_{k},\delta_{g}\in [0,1)$,
\[
\mathrm{OptComp}((\epsilon_{1}+c_{1},\delta_{1}),\ldots,(\epsilon_{k}+c_{k},\delta_{k}),\delta_{g})\leq
\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\eee^{-c/2}\cdot\delta_{g})+c
\]
where $c=\sum_{i=1}^{k}c_{i}$.
\end{lemma}


\noindent Next we prove the three lemmas and then show that \expref{Theorem}{thm:approx} follows.

\begin{proof}[Proof of \expref{Lemma}{lem:pseudo}]
We modify Dyer's algorithm for approximately counting solutions to knapsack problems~\cite{Dye03}. The algorithm uses dynamic programming. Given non-negative integers $a_{1},\ldots,a_{k}$, $B$, and weights $w_{1},\ldots,w_{k}\in\mathbb{Q}$, define 
\[F(r,s) = \sum_{\substack {S\subseteq [r]~\mathrm{s.t.}\\
\sum\limits_{i\in S}a_{i}\leq s\;\;\;}}\prod_{i\in S}w_{i}\,.\]

We want to compute $F(k,B)$, which we can do by tabulating $F(r,s)$ for $(0\leq r\leq k,\; 0\leq s\leq B)$ using the following recursion.
\[
F(r,s)=
\begin{dcases}
1 &\text{if $r=0$,}\\
F(r-1,s) + w_{r}F(r-1, s-a_{r}) &\text{if $r>0$ and $a_{r}\leq s$,}\\
F(r-1,s) &\text{if $r>0$ and $a_{r}>s$.}
\end{dcases}
\]

Each cell $F(r,s)$ in the table can be computed in constant time given earlier cells $F(r',s')$ where $r'<r$. Thus filling the entire table takes time $O(Bk)$. 
\end{proof}

\begin{proof}[Proof of \expref{Lemma}{lem:dyer}]
Given a rational $\eee^{\epsilon_{0}}\geq 0$ and $\epsilon_{1}=a_{1}\cdot\epsilon_{0},\ldots,\epsilon_{k}=a_{k}\cdot\epsilon_{0}, \epsilon^{*}=a^{*}\cdot\epsilon_{0}$ for positive integers $a_{1},\ldots,a_{k}, a^{*}$ and rational $\delta_{1},\ldots \delta_{k}, \delta_{g} \in [0,1)$ \expref{Theorem}{thm:optcomp} tells us that answering whether or not
\[\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g}) \leq \epsilon^{*}\]
is equivalent to answering whether or not the following inequality holds.
\begin{equation}
\label{q}
\frac{1}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon^{*}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} \leq 1-\frac{1-\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\,. 
\end{equation}
The right-hand side and $\prod_{i=1}^{k}(1+\eee^{\epsilon_{i}})$ are easy to compute given the inputs (note that $\eee^{\epsilon_{i}}$ is rational for all $i\in [k]$ because each is an integer power of $\eee^{\epsilon_{0}}$). So in order to check the inequality, we will show how to compute the sum. Define 
\begin{align*}
K&=\left\{T\subseteq[k] \mid \sum\limits_{i\not\in T}\epsilon_{i}\geq \epsilon^{*}+\sum\limits_{i\in T}\epsilon_{i}\right\}\\
&=\left\{T\subseteq[k] \mid \sum\limits_{i\in T}\epsilon_{i}\leq \left(\sum\limits_{i=1}^{k}\epsilon_{i}-\epsilon^{*}\right)/2\right\}\\
&=\left\{T\subseteq[k] \mid \sum\limits_{i\in T}a_{i}\leq B\right\}~\mathrm{for}~B=\left\lfloor{\left(\sum\limits_{i=1}^{k}a_{i}-a^{*}\right)/2}\right\rfloor
\end{align*}
and observe that by setting $T=S^{\mathsf{c}}$, we have
\[
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon^{*}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} = \sum_{T\in K}\left(\left(\prod_{i=1}^{k}\eee^{\epsilon_{i}}\cdot\prod\limits_{i\in T}\eee^{-\epsilon_{i}}\right)-\left(\eee^{\epsilon^{*}}\cdot\prod\limits_{i\in T}\eee^{\epsilon_{i}}\right)\right). 
\]

We can now use \expref{Lemma}{lem:pseudo} to compute each term separately since $K$ is a set of knapsack solutions. Specifically, setting $w_{i}=\eee^{-\epsilon_{i}}~\forall i\in [k]$, \expref{Lemma}{lem:pseudo} tells us that we can compute $\sum_{T\subseteq [k]}\prod_{i\in T}w_{i}$ subject to $\sum_{i\in T}a_{i}\leq B$, which is equivalent to
\[
  \sum_{T\in K}\prod_{i\in T}\eee^{-\epsilon_{i}}\,.
\]
To compute $\sum_{T\in K}\prod_{i\in T}\eee^{\epsilon_{i}}$, we
instead set $w_{i}=\eee^{\epsilon_{i}}$ and run the same
procedure. (Note that
$\eee^{\epsilon^{*}}=(\eee^{\epsilon_{0}})^{a^{*}}$, which is
rational.) So we can determine whether or not Inequality~\eqref{q}
holds. We used the algorithm from \expref{Lemma}{lem:pseudo} so the
running time is
\[
  O(Bk)=O\left(k\cdot\sum_{i=1}^{k}a_{i}\right)\,.\qedhere
\]
\end{proof}

\begin{proof}[Proof of \expref{Lemma}{lem:goodapprox}]
Fix $\epsilon_{1},\ldots,\epsilon_{k}, c_{1},\ldots, c_{k}\geq0$ and $\delta_{1},\ldots,\delta_{k},\delta_{g}\in [0,1)$ and let $c=\sum_{i\in [k]}c_{i}$. Let $\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\eee^{-c/2}\cdot\delta_{g})=\epsilon_{g}$. {}From Equation~\eqref{eq:1} in \expref{Theorem}{thm:optcomp} we know
\[
\frac{1}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} \leq 1-\frac{1-\eee^{-c/2}\cdot\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\,. 
\]
Multiplying both sides by $\eee^{c/2}$ gives
\begin{align*}
\frac{\eee^{c/2}}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\} &\leq \eee^{c/2}\cdot\left(1-\frac{1-\eee^{-c/2}\cdot\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\right) \\
&\leq 1-\frac{1-\delta_{g}}{\prod_{i=1}^{k}{(1-\delta_{i})}}\,.
\end{align*}
The above inequality together with \expref{Theorem}{thm:optcomp} means that showing the following will complete the proof. 
\begin{align*}
\sum_{S\subseteq \{1,\ldots,k\}}\max&\left\{\eee^{\sum\limits_{i\in S}(\epsilon_{i}+c_{i})} - \eee^{\epsilon_{g}+c}\cdot \eee^{\sum\limits_{i\not\in S}(\epsilon_{i}+c_{i})}, 0\right\} \leq \\ & \frac{\eee^{c/2}\cdot\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}+c_{i}})}}{\prod_{i=1}^{k}{(1+\eee^{\epsilon_{i}})}}
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\}.
\end{align*}
Since $(1+\eee^{\epsilon_{i}+c_{i}})/(1+\eee^{\epsilon_{i}})\geq \eee^{c_{i}/2}$ for every $\epsilon_{i}, c_{i}>0$, it suffices to show
\[
\sum_{S\subseteq \{1,\ldots,k\}}\max\left\{\eee^{\sum\limits_{i\in S}(\epsilon_{i}+c_{i})} - \eee^{\epsilon_{g}+c}\cdot \eee^{\sum\limits_{i\not\in S}(\epsilon_{i}+c_{i})}, 0\right\}\leq \sum_{S\subseteq \{1,\ldots,k\}}\eee^{c}\cdot\max\left\{\eee^{\sum\limits_{i\in S}\epsilon_{i}} - \eee^{\epsilon_{g}}\cdot \eee^{\sum\limits_{i\not\in S}\epsilon_{i}}, 0\right\}.
\]
This inequality holds term by term. If a right-hand term is zero
\[
  \left(\sum_{i\in S}\epsilon_{i}\leq\epsilon_{g}+\sum_{i\not\in S}\epsilon_{i}\right)\,,
\]
then so is the corresponding left-hand term
\[
  \left(\sum_{i\in
    S}(\epsilon_{i}+c_{i})\leq\epsilon_{g}+c+\sum_{i\not\in
    S}(\epsilon_{i}+c_{i})\right)\,.
\]
For the nonzero terms, the factor
of $\eee^{c}$ ensures that the right-hand terms are larger than the
left-hand terms.
\end{proof}
\end{section}


\begin{proof}[Proof of \expref{Theorem}{thm:approx}]
\expref{Lemma}{lem:dyer} tells us that we can determine whether a set of privacy parameters satisfies some $(\epsilon_{g},\delta_{g})$ differential privacy guarantee if the $\epsilon_{i}$ values and $\epsilon_{g}$ are all positive integer multiples of some $\epsilon_{0}$ where $\eee^{\epsilon_{0}}$ is rational. We are given rational $\epsilon_{1},\ldots,\epsilon_{k}\geq 0, \delta_{1},\ldots \delta_{k}, \delta_{g} \in [0,1),$ and $\eta\in (0,1)$. Let $\ebar=\sum_{i\in[k]}\epsilon_{i}/k$ be the arithmetic mean of the $\epsilon_{i}$ values. Let $\beta=\eta/(k\cdot(1+\ebar)+1)$, set $\epsilon_{0}=\ln(1+\beta)$, and for all $i\in [k]$ set $a_{i}=\lceil{\epsilon_{i}\cdot(1/\beta+1)}\rceil$ and $\epsilon_{i}'=\epsilon_{0}\cdot a_{i}$. We will use the following bounds on $\epsilon_{0}$ in the proof.
\[
\frac{\beta}{2}\leq\frac{\beta}{1+\beta}\leq \epsilon_{0}\leq \beta.
\]

With these settings, the
%
$a_{i}$     %
are non-negative integers, the $\epsilon_{i}'$ values are all integer multiples of $\epsilon_{0}$ and $\eee^{\epsilon_{0}}$ is rational. So for every positive integer $a$ we can apply \expref{Lemma}{lem:dyer} to determine whether or not OptComp$((\epsilon_{1}',\delta_{1}),\ldots,(\epsilon_{k}',\delta_{k}),\delta_{g})\leq a\cdot \epsilon_{0}$ in time $O\left(k\cdot \sum_{i\in [k]}a_{i}\right)$. Running binary search over integers $a$, we can find the minimum such integer, which we will call $a^{*}$. The algorithm's estimate of OptComp$((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})$ will be $a^{*}\cdot\epsilon_{0}$. However since this number is irrational, we will use the Taylor approximation of the natural logarithm to output $\epsilon^{*}$ satisfying $a^{*}\cdot\epsilon_{0}\leq \epsilon^{*}\leq a^{*}\cdot\epsilon_{0}+\beta-\epsilon_{0}$. Since we only need to calculate a few terms of the Taylor expansion of $\ln(1+\beta)$ to achieve this approximation, this step will not affect our running time. The pseudocode for this procedure is below.
%
\medskip
\begin{algorithm}
\begin{algorithmic}
\STATE \textbf{Input:} $\epsilon_1,\ldots,\epsilon_k\geq 0$, $\delta_1,\ldots,\delta_k,\delta_g\in[0,1)$, $\eta\in (0,1)$
\STATE \textbf{Output:} Approximation of  $\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}), \delta_{g})$
\STATE $\ebar\leftarrow \sum_{i\in[k]}\epsilon_{i}/k$
\STATE $\beta\leftarrow\eta/(k\cdot(1+\ebar)+1)$
\STATE $\epsilon_0 \leftarrow \ln(1+\beta)$
\FOR{$i\in[k]$}
\STATE{$a_{i}\leftarrow \lceil{\epsilon_{i}\cdot(1/\beta+1)}\rceil$}
\STATE{$\epsilon_{i}'\leftarrow \epsilon_{0}\cdot a_{i}$}
\ENDFOR
\STATE {Use binary search and \expref{Lemma}{lem:dyer} to find minimum integer $a^{*}$ such that \[
    \text{OptComp}((\epsilon_{1}',\delta_{1}),\ldots,(\epsilon_{k}',\delta_{k}),\delta_{g})\leq a^{*}\cdot \epsilon_{0}\]}
\RETURN{Taylor approximation to $a^{*}\cdot\epsilon_0$}
\end{algorithmic}
\end{algorithm}

Since we choose $a^{*}$ to be the minimum integer satisfying composition we have
\[
  \epsilon^{*}-\beta\leq(a^{*}-1)\cdot\epsilon_{0}\leq \mathrm{OptComp}((\epsilon_{1}',\delta_{1}),\ldots,(\epsilon_{k}',\delta_{k}),\delta_{g}) \leq a^{*}\cdot\epsilon_{0}\leq\epsilon^{*}\,.
\]
$a^{*}$ can range from $0$ to $\sum_{i\in [k]}a_{i}$ so the binary search can be done in
\[
  \log\left(\sum_{i\in[k]}a_{i}\right)=\log O\left(k^{2}\cdot\ebar\cdot(1+\ebar)/\eta\right)
\]
iterations. This gives us a total running time of
\[O\left(\frac{k^{3}\cdot\ebar\cdot(1+\ebar)}{\eta}\cdot \log\left(\frac{k^{2}\cdot\ebar\cdot(1+\ebar)}{\eta}\right)\right).\]

Now we argue that $\epsilon^{*}$ is a good approximation of OptComp$((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})$. For all $i\in [k]$ we have
\[
   \epsilon'_{i}=\epsilon_{0}\cdot a_{i}
   \geq \frac{\beta}{1+\beta}\cdot\left\lceil{\epsilon_{i}\cdot\left(\frac{1}{\beta}+1\right)}\right\rceil
   \geq \epsilon_{i}\,.
\]
So all of the $\epsilon_{i}'$ values are overestimates of their corresponding $\epsilon_{i}$ values and therefore
\[
\mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\delta_{g})\leq \mathrm{OptComp}((\epsilon_{1}',\delta_{1}),\ldots,(\epsilon_{k}',\delta_{k}),\delta_{g}) \leq \epsilon^{*}
\] 
satisfying one of the inequalities in the theorem. We also have for all $i\in [k]$
\[
    \epsilon'_{i} =\epsilon_{0}\cdot\left\lceil{\epsilon_{i}\cdot\left(\frac{1}{\beta}+1\right)}\right\rceil
    \leq \beta\cdot\left(\epsilon_{i}\cdot\left(\frac{1}{\beta}+1\right)+1\right)
    =\epsilon_{i}+\beta\cdot(\epsilon_{i}+1)\,.
\]
Let $c_{i}=\beta\cdot(\epsilon_{i}+1)$ for all $i\in [k]$ and let $c=\sum_{i\in[k]}c_{i}=\beta\cdot k\cdot(1+\ebar)$. Now we get
\begin{align*}
\epsilon^{*}-\beta&\leq \mathrm{OptComp}((\epsilon_{1}',\delta_{1}),\ldots,(\epsilon_{k}',\delta_{k}),\delta_{g})\\
&\leq \mathrm{OptComp}((\epsilon_{1}+c_{1},\delta_{1}),\ldots,(\epsilon_{k}+c_{k},\delta_{k}),\delta_{g})\\
&\leq \mathrm{OptComp}((\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k}),\eee^{-\beta\cdot k\cdot(1+\ebar)/2}\cdot\delta_{g})+\beta\cdot k\cdot(1+\ebar)
\end{align*}
by \expref{Lemma}{lem:goodapprox}. Noting that $\beta\cdot k\cdot(1+\ebar)$ and $\beta\cdot k\cdot(1+\ebar)+\beta$ are both at most $\eta$ completes the proof.
\end{proof}
\section{Comparison of composition theorems} \label{sect:fig}
The plots in \expref{Figure}{fig:compplots} below compare the performances of four homogeneous composition theorems. In all figures, ``Summing'' refers to basic composition---\expref{Theorem}{thm:basiccomp} \cite{DKMMN06}, ``DRV'' refers to advanced composition---\expref{Theorem}{thm:advancedcomp} \cite{DRV10}, ``KOV Bound'' refers to the bound below~\cite{KOV15} that is a closed form approximation of the optimal composition theorem, and ``Optimal'' refers to the optimal composition theorem---\expref{Theorem}{thm:homogeneouscomp} \cite{KOV15}. 
\begin{theorem}[KOV Bound~\cite{KOV15}]
For every $\epsilon \geq 0$, $\delta, \tilde{\delta} \in [0,1]$, and  $(\epsilon,\delta)$-differentially private algorithms $M_1,M_2,\ldots,M_k$, the composition $(M_1,M_2,\ldots,M_k)$ satisfies $(\epsilon_g,1-(1-\delta)^k(1-\tilde{\delta}))$-DP for
\[
\epsilon_g = \min\left\{k\epsilon, \frac{(\eee^{\epsilon}-1)\epsilon k}{\eee^{\epsilon}+1}+\epsilon\sqrt{2k\log\left(e+\frac{\sqrt{k\epsilon^2}}{\tilde{\delta}}\right)},\frac{(\eee^{\epsilon}-1)\epsilon k}{\eee^{\epsilon}+1}+\epsilon\sqrt{2k\log\left(\frac{1}{\tilde{\delta}}\right)}\right\}.
\]
\end{theorem}

Here we are composing $k$ mechanisms that are $(\epsilon,\delta)$ differentially private to obtain an $(\epsilon_{g},\delta_{g})$ differentially private mechanism as guaranteed by one of the composition theorems. Note that DRV as typically formulated is the only one of the bounds that does not have simple summing as a special case. For that reason the DRV bound actually performs worse than summing for small values of $k$ before the asymptotic improvement kicks in. 


%
\captionsetup[subfigure]{labelformat=empty}
\begin{figure}
  \thisfloatpagestyle{empty}
  \centering
\begin{subfigure}{0.48\textwidth}
\includegraphics[width=\textwidth]{shrt_700} 
\end{subfigure}
\begin{subfigure}{0.48\textwidth}
\includegraphics[width=\textwidth]{shrt_100}
\end{subfigure}

\begin{subfigure}{0.48\textwidth}
\includegraphics[width=\textwidth]{shrt_delchange} 
\end{subfigure}
\begin{subfigure}{0.48\textwidth}
\includegraphics[width=\textwidth]{shrt_ratios}
\end{subfigure}
\caption{(Top Left) $\epsilon_{g}$ given by four composition theorems for varying values of $\epsilon$ as $k$ grows. Parameters $\delta=0$ and $\delta_{g}=2^{-25}$. (Top Right) Same as Top Left zoomed in on the $k<100$ regime. We see that optimal composition gives substantial savings in $\epsilon_{g}$, even for moderate values of $k$. (Bottom Left) $\epsilon_{g}$ given by four composition theorems for varying values of $\delta_{g}$ as $k$ grows, with parameters $\delta=0$ and $\epsilon=.005$ for the individual mechanisms. $\delta_{g}$ does not affect $\epsilon_{g}$ in basic composition. (Bottom Right) Performance of composition theorems measured relative to optimal composition. Depicts every curve in Figure 1 divided by the optimal composition curve. We see that relative performances of the KOV bound and DRV seem to converge to a constant. The $\epsilon_{g}$ values given by the KOV bound are about $20\%$ larger than optimal and the values given by advanced composition are about 30-40$\%$ larger than optimal.}
\label{fig:compplots}
\end{figure}

\section*{Acknowledgements}
We thank Mark Bun, Cynthia Dwork, and Thomas Steinke for helpful comments, particularly regarding our proof of \expref{Lemma}{lem:sim}.

\bibliographystyle{tocplain}   %
%
%
%
%
\bibliography{v014a008}

%
%
%
%
\begin{tocauthors}
\begin{tocinfo}[murtagh]
 Jack Murtagh\\
 Graduate student\\
 Harvard University, Cambridge, MA\\
 jmurtagh\tocat{}g\tocdot{}harvard\tocdot{}edu \\
 \url{https://scholar.harvard.edu/jmurtagh}
\end{tocinfo}
\begin{tocinfo}[vadhan]
  Salil Vadhan\\
  Vicky Joseph Professor of\\
  Computer Science and Applied Mathematics\\
  Harvard University, Cambridge, MA\\
%
  salil\_vadhan\tocat{}harvard\tocdot{}edu \\
  \url{http://people.seas.harvard.edu/~salil/}
\end{tocinfo}
\end{tocauthors}

%

\begin{tocaboutauthors}
\begin{tocabout}[murtagh]
\textsc{\href{https://scholar.harvard.edu/jmurtagh}{Jack Murtagh}} is a graduate student at \href{https://toc.seas.harvard.edu/}{Harvard University} where he is advised by \href{http://people.seas.harvard.edu/~salil/}{Salil Vadhan.} As an undergraduate, Jack studied \href{http://math.tufts.edu/}{mathematics} at \href{https://www.tufts.edu/}{Tufts University}. Jack is broadly interested in complexity theory and currently works on derandomization and \href{https://privacytools.seas.harvard.edu/}{data privacy.} 
\end{tocabout}
\begin{tocabout}[vadhan]
  \textsc{\href{http://people.seas.harvard.edu/~salil/}{Salil Vadhan}} is the Vicky Joseph Professor of \href{https://www.seas.harvard.edu/computer-science}{Computer Science} and \href{https://www.seas.harvard.edu/applied-mathematics}{Applied Mathematics} at the \href{http://www.seas.harvard.edu/}{Harvard John A.\ Paulson School of Engineering} \& Applied Sciences. He received his
  \phd\ under the supervision of \href{http://people.csail.mit.edu/shafi/}{Shafi Goldwasser} at \href{http://web.mit.edu/}{MIT} in 1999;
%
the title of his dissertation was  %
\href{http://people.seas.harvard.edu/~salil/research/phdthesis-abs.html}{``A Study of Statistical Zero-Knowledge Proofs.''} Other research interests include the theory of \href{http://people.seas.harvard.edu/~salil/pseudorandomness/}{pseudorandomness} the \href{https://privacytools.seas.harvard.edu/}{theory and practice of data privacy.} He enjoys spending leisure time with his wife and two daughters, as well as learning to surf in the cold waters of New England.
\end{tocabout}
\end{tocaboutauthors}

\end{document}
