text:
\section{Introduction}

The line of work on {\em differential privacy}~\cite{DworkMcNiSm06} is aimed at
enabling useful statistical analyses on privacy-sensitive data while providing strong privacy protections for individual-level information.  Privacy is achieved in differentially private algorithms through randomization and the introduction of ``noise'' to obscure the effect of each individual, and thus differentially private algorithms can be less accurate than their non-private analogues.  Nevertheless,
by now a rich literature has shown that many data analysis tasks of interest are compatible with differential privacy, and generally the loss in accuracy vanishes as the number $n$ of individuals tends to infinity.  However, in many cases, there is still is a price of privacy hidden in these asymptotics --- in the rate at which the loss in accuracy vanishes, and in how large $n$ needs to be to start getting accurate results at all (the ``sample complexity'').

In this paper, we consider the price of privacy for three very basic types of computations involving threshold functions: query release, distribution learning with respect to Kolmogorov distance, and (proper) PAC learning.  In all cases, we show for the first time that accomplishing these tasks with differential privacy is {\em impossible} when the data universe is infinite (e.g. $\N$ or $[0,1]$) and in fact that the sample complexity must grow with the size $|X|$ of the data universe: $n=\Omega(\log^*|X|)$,
which is tantalizingly close to the previous upper bound of $n=2^{O(\log^*|X|)}$~\cite{BeimelNiSt13b}.  We also provide simpler and somewhat improved upper bounds for these problems, reductions between these problems and other natural problems, as well as additional techniques that allow us to prove
impossibility results for infinite domains even when the sample complexity does not need to grow with the domain size (e.g. for PAC learning of point functions with ``pure'' differential privacy).

\subsection{Differential Privacy}

We recall the definition of differential privacy.  We think of a dataset as consisting of $n$ rows from a data universe $X$, where each row corresponds to one individual.  Differential privacy requires that no individual's data has a significant effect on the distribution of what we output.

\begin{definition}
A randomized algorithm $M : X^n\rightarrow Y$ is $(\varepsilon,\delta)$ {\em differentially private} if for every two datasets $x,x'\in X^n$ that differ on one row, and every set $T\subseteq Y$, we have
$$\Pr[M(x)\in T]\leq e^{\varepsilon}\cdot \Pr[M(x')\in T]+\delta.$$
\end{definition}

The original definition from \cite{DworkMcNiSm06} had $\delta=0$, and is sometimes referred to as {\em pure} differential privacy.  However, a number of subsequent works have shown that allowing a small (but negligible) value of $\delta$, referred to as {\em approximate differential privacy}, can provide substantial gains over  pure differential privacy~\cite{DworkLe09,HardtTa10,DworkRoVa10,De12,BeimelNiSt13b}.

The common setting of parameters is to take $\varepsilon$ to be a small constant and $\delta$ to be negligible in $n$ (or a given security parameter).  To simplify the exposition, we fix $\varepsilon=0.1$ and $\delta=1/n^{\log n}$ throughout the introduction (but precise dependencies on these parameters are given in the main body).

\subsection{Private Query Release}

Given a set $Q$ of queries $q : X^n\rightarrow \R$, the {\em query release} problem for $Q$ is to output accurate answers  to all queries in $Q$.  That is, we want a differentially private algorithm $M : X^n\rightarrow \R^{|Q|}$ such that for every dataset $D\in X^n$, with high probability over $y\leftarrow M(D)$, we have $|y_q-q(D)|\leq \alpha$ for all $q\in Q$, for an error parameter $\alpha$.

A special case of interest is the case where $Q$ consists of {\em counting queries}.  In this case, we are given a set $Q$ of predicates $q : X\rightarrow \{0,1\}$ on individual rows, and then extend them to databases by averaging. That is, $q(D) = (1/n)\sum_{i=1}^D q(D_i)$ counts the fraction of the population that satisfies predicate $q$.

The query release problem for counting queries is one of the most widely studied problems in differential privacy.  Early work on differential privacy implies that for every family of counting queries $Q$, the query release problem for $Q$ has sample complexity at most $\tilde{O}(\sqrt{|Q|})$ \cite{DinurNi03, DworkNi04, BlumDwMcNi05, DworkMcNiSm06}. That is, there is an $n_0=\tilde{O}(\sqrt{|Q|})$ such that for all $n\geq n_0$,
there is a differentially private mechanism
$M : X^n\rightarrow \R^{Q}$ that solves the query release problem for $Q$ with
error at most $\alpha=0.01$.
(Again, we treat $\alpha$ as a small constant to avoid an extra parameter in the introduction.)

Remarkably, Blum, Ligett, and Roth~\cite{BlumLiRo08} showed that if the data universe $X$ is finite, then the sample complexity grows much more slowly with $|Q|$ --- indeed the query release problem for $Q$ has sample complexity at most $O((\log |X|)(\log |Q|))$.  Hardt and Rothblum~\cite{HardtRo10} improved this bound to $\tilde{O}(\log |Q|\cdot \sqrt{\log |X|})$, which was recently shown to be optimal for
some families $Q$~\cite{BUV14}.

However, for specific query families of interest, the sample complexity can be significantly smaller.  In particular, consider the family of {\em point functions} over $X$, which is the family $\{q_x\}_{x\in X}$ where $q_x(y)$ is 1 iff $y=x$, and the family of {\em threshold functions} over $X$, where $q_x(y)$ is 1 iff $y\leq x$ (where $X$ is a totally ordered set).  The query release problems for these families correspond to the very natural tasks of producing $\ell_\infty$ approximations to the histogram and to the cumulative distribution function of the empirical data distribution, respectively.
For point functions, Beimel, Nissim, and Stemmer~\cite{BeimelNiSt13b} showed that the sample complexity has no dependence on $|X|$ (or $|Q|$, since
$|Q|=|X|$ for these families).  In the case of threshold functions, they showed that it has at most a very mild dependence on $|X|=|Q|$, namely $2^{O(\log^* |X|)}$.

Thus, the following basic questions remained open:
Are there differentially private algorithms for releasing threshold functions over an infinite data universe (such as $\N$ or $[0,1]$)?
If not, does the sample complexity for releasing threshold functions grow with the size $|X|$ of the data universe?

We resolve these questions:
\begin{theorem}
The sample complexity  of releasing threshold functions over a data universe $X$ with differential privacy is at least $\Omega(\log^* |X|)$.  In particular, there is no differentially private algorithm for releasing threshold functions over an infinite data universe.
\end{theorem}

In addition, inspired by the ideas in our lower bound, we present a simplification of the algorithm of \cite{BeimelNiSt13b} and improve the sample complexity to $2^{(1+o(1))\log^* |X|}$ (from roughly $8^{\log^* |X|}$).  Closing the gap between the lower bound of $\approx \log^* |X|$ and the upper bound of $\approx 2^{\log^* |X|}$ remains an intriguing open problem.

We remark that in the case of pure differential privacy ($\delta=0$), a sample complexity lower bound of $n=\Omega(\log |X|)$ follows from a standard ``packing argument''~\cite{HardtTa10,BeimelKaNi10}.  For point functions, this is matched by the standard Laplace mechanism~\cite{DworkMcNiSm06}.  For threshold functions, a matching upper bound was recently obtained~\cite{ReingoldRo14}, building on a construction of \cite{DworkNaPiRo10}.  We note that these algorithms have a slightly better dependence on the accuracy parameter $\alpha$ than our algorithm (linear rather than nearly linear in $1/\alpha$). In general, while packing arguments often yield tight lower bounds for pure differential privacy, they fail badly for approximate differential privacy, for which much less is known.

There is also a beautiful line of work on characterizing the $\ell_2$-accuracy achievable for query release in terms of other measures of the ``complexity'' of the family $Q$ (such as ``hereditary discrepancy'')~\cite{HardtTa10,BhaskaraDaKrTa12,MuthukrishnanNi12,NikolovTaZh13}.  However, the characterizations given in these works are tight only up to factors of
$\mathop{\rm{poly}}\nolimits(\log |X|,\log |Q|)$ and thus do not give good estimates of the sample complexity (which is at most $(\log |X|)(\log |Q|)$ even for pure differential privacy, as mentioned above).

\subsection{Private Distribution Learning}

A fundamental problem in statistics is \emph{distribution learning}, which is the task of learning an unknown distribution $\mathcal{D}$ given i.i.d.\ samples from it. The query release problem for threshold functions is closely related to the problem of learning an arbitrary distribution $\mathcal{D}$ on $\R$ up to small error in Kolmogorov (or CDF) distance: Given $n$ i.i.d.\ samples $x_i \gets_{\mbox{\tiny R}} \mathcal{D}$, the goal of a distribution learner is to produce a CDF $F : X \to [0, 1]$ such that $|F(x) - F_{\mathcal{D}}(x)| \le \alpha$ for all $x \in X$, where $\alpha$ is an accuracy parameter. While closeness in Kolmogorov distance is a relatively weak measure of closeness for distributions, under various structural assumptions (e.g. the two distributions have probability mass functions that cross in a constant number of locations), it implies closeness in the much stronger notion of total variation distance. Other works have developed additional techniques that use weak hypotheses learned under Kolmogorov distance to test and learn distributions under total variation distance (e.g. \cite{DaskalakisDiSeVaVa13, DaskalakisDiSe14, DaskalakisKa14}).

The well-known Dvoretzky-Kiefer-Wolfowitz inequality \cite{DvoretzkyKiWo56} implies that without privacy, any distribution over $X$ can be learned to within constant error with $O(1)$ samples. On the other hand, we show that with approximate differential privacy, the task of releasing thresholds is essentially equivalent to distribution learning. As a consequence, with approximate differential privacy, distribution learning instead requires sample complexity that grows with the size of the domain.
\begin{theorem} \label{thm:dist-informal}
The sample complexity of learning arbitrary distributions on a domain $X$ with differential privacy is at least $\Omega(\log^*|X|)$.
\end{theorem}
We prove Theorem \ref{thm:dist-informal} by showing that the problem of distribution learning with respect to Kolmogorov distance with differential privacy is essentially equivalent to query release for threshold functions. Indeed, query release of threshold functions amounts to approximating the \emph{empirical distribution} of a dataset with respect to Kolmogorov distance. Approximating the empirical distribution is of course trivial without privacy (since we are given it as input), but with privacy, it turns out to have essentially the same sample complexity as the usual distribution learning problem from i.i.d.\ samples.  More generally, query release for a family $Q$ of counting queries is equivalent to distribution learning with respect to the distance measure $d_{Q}(\mathcal{D}, \mathcal{D}') = \sup_{q \in Q} |\operatorname*{\mathbb{E}}[q(\mathcal{D})] - \operatorname*{\mathbb{E}}[q(\mathcal{D}')]|$.

\subsection{Private PAC Learning}

Kasiviswanathan et al.~\cite{KasiviswanathanLeNiRaSm07} defined {\em private PAC learning} as a combination of probably approximately correct (PAC) learning~\cite{Valiant84} and differential privacy.
Recall that a PAC learning algorithm takes some $n$ labeled examples
$(x_i,c(x_i))\in X\times \{0,1\}$ where the $x_i$'s are i.i.d.\ samples of an arbitrary and unknown distribution on a data universe $X$ and $c : X\rightarrow \{0,1\}$ is an unknown {\em concept} from some concept class $C$.  The goal of the learning algorithm is
to output a {\em hypothesis} $h : X\rightarrow \{0,1\}$ that approximates $c$ well on the unknown distribution.   We are interested in PAC learning algorithms
$L : (X\times \{0,1\})^n\rightarrow H$ that are also differentially private.  Here
$H$ is the {\em hypothesis class}; if $H \subseteq C$, then $L$ is called a {\em proper} learner.

As with query release and distribution learning, a natural problem is to characterize the {\em sample complexity} --- the minimum number $n$ of samples in order to achieve differentially private PAC learning for a given concept class $C$.
Without privacy,  it is well-known that
the sample complexity of (proper) PAC learning is proportional to the Vapnik--Chervonenkis (VC) dimension of the class $C$~\cite{VC,BlumerEhHaWa89,EHKV}.  In the initial work on differentially private learning, Kasiviswanathan et al.~\cite{KasiviswanathanLeNiRaSm07} showed that $O(\log|C|)$ labeled examples suffice for privately learning any concept class $C$.\footnote{As with the query release discussion, we omit the dependency on all parameters except for $|C|$, $|X|$ and $\operatorname{\rm VC}(C)$.} The VC dimension of a concept class $C$ is always at most $\log|C|$, but is significantly lower for many interesting classes. Hence, the results of~\cite{KasiviswanathanLeNiRaSm07} left open the possibility that the sample complexity of private learning may be significantly higher than that of non-private learning.

In the case of {\em pure} differential privacy ($\delta=0$), this gap in the sample complexity was shown to be unavoidable in general.
Beimel, Kasiviswanathan, and Nissim~\cite{BeimelKaNi10}  considered the concept class $C$ of point functions over a data universe $X$, which have VC dimension 1 and hence can be (properly) learned without privacy with $O(1)$ samples. In contrast, they showed that proper PAC learning with pure differential privacy requires sample complexity $\Omega(\log |X|)=\Omega(\log |C|)$.
Feldman and Xiao~\cite{FX14} showed a similar separation even for improper learning --- the class $C$ of threshold functions over $X$ also has VC dimension 1, but PAC learning with pure differential privacy requires sample complexity $\Omega(\log |X|)=\Omega(\log |C|)$.

For approximate differential privacy ($\delta>0$), however, it was still open whether there is an asymptotic gap between the sample complexity of private learning and non-private learning.  Indeed, Beimel et al.~\cite{BeimelNiSt13b} showed that point functions
can be properly learned with approximate differential privacy using $O(1)$ samples (i.e. with no dependence on $|X|$).  For threshold functions, they exhibited a proper learner with sample complexity $2^{O(\log^* |X|)}$, but it was conceivable that the sample complexity could also be reduced to $O(1)$.

We prove that the sample complexity of proper PAC learning with approximate differential privacy can be asymptotically larger than the VC dimension:

\begin{theorem}
The sample complexity of properly learning threshold functions over a data universe $X$ with differential privacy is at least $\Omega(\log^* |X|)$.
\end{theorem}

This lower bound extends to the concept class of $\ell$-dimensional thresholds. An $\ell$-dimensional threshold function, defined over the domain $X^\ell$, is a conjunction of $\ell$ threshold functions, each defined on one component of the domain. This shows that our separation between the sample complexity of private and non-private learning applies to concept classes of every VC dimension.

\begin{theorem}
For every finite, totally ordered $X$ and $\ell\in \N$, the sample complexity of properly learning the class $C$ of $\ell$-dimensional threshold functions on $X^\ell$ with differential privacy is at least
$\Omega(\ell\cdot \log^*|X|) = \Omega(\operatorname{\rm VC}(C)\cdot \log^* |X|)$.
\end{theorem}

Based on these results, it would be interesting to fully characterize the difference between the sample complexity of proper non-private learners and of proper learners with (approximate) differential privacy. Furthermore, our results still leave open the possibility that {\em improper} PAC learning with (approximate) differential privacy has sample complexity $O(\operatorname{\rm VC}(C))$.  We consider this to be an important question for future work.

We also present a new result on improper learning of point functions with pure differential privacy over infinite countable domains.  Beimel et al.~\cite{BeimelKaNi10,BeimelNiSt13a} showed that for finite data universes $X$, the sample complexity of improperly learning point functions with pure differential
privacy does not grow with $|X|$.  They also gave a mechanism for learning point functions over infinite domains (e.g. $X=\N$), but the outputs of their mechanism do not have a finite description length (and hence cannot be implemented by an algorithm).  We prove that this is inherent:

\begin{theorem} \label{thm:pure-point-lb}
For every infinite domain $X$, countable hypothesis space $H$, and $n\in \N$, there is no (even improper) PAC learner $L : (X\times \{0,1\})^n\rightarrow
H$ for point functions over $X$ that satisfies pure differential privacy.
\end{theorem}

\subsection{Techniques}

Our results for query release and proper learning of threshold functions are obtained by analyzing the sample complexity of a related but simpler problem, which
we call the {\em interior-point problem}.  Here we want a mechanism $M : X^n\rightarrow X$ (for a totally ordered data universe $X$) such that for every database $D\in X^n$, with high probability we have
$\min_i D_i \leq M(D)\leq \max_i D_i$.  We give reductions showing that the sample complexity of this problem is equivalent to the other ones we study:
\begin{theorem}
Over every totally ordered data universe $X$, the following four problems have the same sample complexity (up to constant factors) under differential privacy:
\stocrm{
\begin{enumerate}
\item The interior-point problem.
\item Query release for threshold functions.
\item Distribution learning (with respect to Kolmogorov distance).
\item Proper PAC learning of threshold functions.
\end{enumerate}
}
\stoctext{
(1) The interior-point problem, (2) Query release for threshold functions, (3) Distribution learning with respect to Kolmogorov distance, and (4) Proper PAC learning of threshold functions.
}
\end{theorem}
Thus we obtain our lower bounds and our simplified and improved upper bounds  for query release and proper learning by proving such bounds  for the interior-point problem, such as:

\begin{theorem} \label{thm:range-lb-informal}
The sample complexity for solving the interior-point problem over a data universe $X$ with differential privacy is $\Omega(\log^* |X|)$.
\end{theorem}

Note that for every fixed distribution $\mathcal{D}$ over $X$ there exists a simple differentially private algorithm for solving the interior-point problem (w.h.p.) over databases sampled i.i.d.\ from $\mathcal{D}$ -- simply output a point $z$ s.t. $\Pr_{x\sim \mathcal{D}}[x\geq z]=1/2$. Hence, in order to prove Theorem~\ref{thm:range-lb-informal}, we show a (correlated) distribution $\mathcal{D}$ over {\em databases} of size $n \approx \log^* |X|$ on which privately solving the interior-point problem is impossible. The construction is recursive: we use a hard distribution over databases of size $(n-1)$ over a data universe of size logarithmic in $|X|$ to construct
the hard distribution over databases of size $n$ over $X$.

By another reduction to the interior-point problem, we show an impossibility result for the following \emph{undominated-point} problem:
\begin{theorem}
For every $n\in \N$, there does not exist a differentially private mechanism $M : \N^n\rightarrow \N$ with the property that
for every dataset $D\in \N^n$, with high probability $M(D)\geq \min_i D_i$.
\end{theorem}
Note that for the above problem, one cannot hope to construct a single distribution over databases that every private mechanism fails on. The reason is that for any such distribution $\mathcal{D}$, and any desired failure probability $\beta$, there is some number $K$ for which $\Pr_{D\sim\mathcal{D}}[\max{D} > K] \le \beta$, and hence that the mechanism that always outputs $K$ solves the problem.
Hence, given a mechanism $\mathcal{M}$ we must tailor a hard distribution $\mathcal{D}_\mathcal{M}$.
We use a similar mechanism-dependent approach to prove Theorem~\ref{thm:pure-point-lb}.

\iffalse
\stocrm{
\subsection{Other Related Works}
While sanitization is an extremely desirable goal, as was shown in~\cite{DworkNaReRoVa09,UllmanVa11,Ullman13}, it is not generally computationally feasible.
The first evidence for computational hardness in data sanitization was given by Dwork et al.~\cite{DworkNaReRoVa09}, who showed that there exists a concept class of size $2^{\widetilde{O}(\sqrt{n})}$ for which sanitization is possible in exponential time, but impossible in polynomial time. Following that, Ullman~\cite{Ullman13} showed that data sanitization can be hard even for $n^{2+o(1)}$ queries.
Dwork et al.~\cite{DworkNaReRoVa09} also showed that there is no general efficient {\em proper}-sanitizer\footnote{A proper-sanitizer is restricted to only output ``synthetic databases'' containing elements from the input domain.} for when either the universe
or the target concept class are of superpolynomial size (in a security parameter).
Their results were extended by Ullman and Vadhan~\cite{UllmanVa11} who showed that proper-sanitization is hard even for very simple concept classes.

Chaudhuri and Hsu~\cite{CH11} studied the sample complexity needed for private learning when the data is drawn from a continuous domain. They showed that under these settings there exists a simple
concept class for which any proper learner that uses a finite number of
examples and guarantees pure-privacy fails to satisfy accuracy
guarantee for at least one data distribution.

A characterization for the sample complexity of {\em pure-private} learners was given in~\cite{BeimelNiSt13a}, in terms of a new combinatorial measure -- the {\em Representation Dimension}. That is, given a class $C$, the number of samples that are necessary and sufficient for privately learning $C$ is $\Theta(\operatorname{\rm RepDim}(C))$. Subsequently, Feldman and Xiao~\cite{FX14} showed an equivalence between the representation dimension of a concept $C$ and the randomized one-way communication complexity of the evaluation problem for concepts from $C$. Using this equivalence they separated the sample complexity of pure-private learners from that of non-private ones.

Dwork et al.~\cite{DworkRoVa10} showed how to boost the accuracy of both private learners and sanitizers. \mnote{Note sure if we need to describe this body of work.}\knote{I tend to agree.} That is, given a ``weak sanitizer'' that only guarantees accurate answers to most (but not all) of the mass of a given query distribution, they produce a sanitizer that guarantees accurate answers to all of the queries in the class. In addition, they showed how a private learner with a large classification error can be transformed into a private learner with small error.
Other tools for private learning include, e.g., private SVM~\cite{RBHT09}, private logistic regression~\cite{CM08}, and private empirical risk minimization~\cite{CMS11}.
}
\fi

\stocrm{
\section{Preliminaries}

Throughout this work, we use the convention that $[n] = \{0, 1, \dots, n-1\}$ and write $\log$ for $\log_2$. We use $\operatorname*{\tt THRESH}_X$ to denote the set of all {\em threshold functions} over a totally ordered domain $X$. That is,
$$\operatorname*{\tt THRESH}\nolimits_X = \{c_x : x \in X\} \quad \text{where} \quad c_x(y) = 1 \text{ iff } y \le x.$$
\mnote{Didn't change this to $y \ge x$ (yet)}

\subsection{Differential Privacy} \label{sec:dp-prelim}

Our algorithms and reductions rely on a number of basic results about differential privacy. Early work on differential privacy showed how to solve the query release problem by adding independent Laplace noise to each exact query answer. A real-valued random variable is distributed as $\operatorname{\rm Lap}(b)$ if its probability density function is $f(x)=\frac{1}{2b}\exp(-\frac{|x|}{b})$. We say a function $f:X^n \rightarrow \R^m$ has {\em sensitivity $\Delta$} if for all neighboring $D,D'\in X^n$, it holds that $||f(D)-f(D')||_1\leq \Delta$.

\begin{theorem}[The Laplace Mechanism \cite{DworkMcNiSm06}]\label{thm:lap}
Let $f:X^n \rightarrow \R^n$ be a sensitivity $\Delta$ function. The mechanism $A$ that on input $D\in X^n$
adds independent noise with distribution $\operatorname{\rm Lap}(\Delta/\epsilon)$ to each coordinate of $f(D)$ preserves $\epsilon$-differential privacy.
\end{theorem}

We will present algorithms that access their input database using (several) differentially private mechanisms and use the following composition theorem to prove their overall privacy guarantee.

\begin{lemma}[Composition, e.g. \cite{DworkLe09}] \label{lem:composition}
Let $\mathcal{M}_1: X^n \to \mathcal{R}_1$ be $(\varepsilon_1, \delta_1)$-differentially private. Let $\mathcal{M}_2: X^n \times \mathcal{R}_1 \to \mathcal{R}_2$ be $(\varepsilon_2, \delta_2)$-differentially private for any fixed value of its second argument. Then the composition $M(D) = \mathcal{M}_2(D, \mathcal{M}_1(D))$ is $(\varepsilon_1 + \varepsilon_2, \delta_1 + \delta_2)$-differentially private.
\end{lemma}

}

\section{The Interior Point Problem}

\subsection{Definition}
In this work we exhibit a close connection between the problems of privately learning and releasing threshold queries, distribution learning, and solving the \emph{interior point problem} as defined below.

\begin{definition}
An algorithm $A:X^n \to X$ solves the \emph{interior point problem} on $X$ with error probability $\beta$ if for every $D \in X^n$,
\[\Pr[\min D \le A(D) \le \max D] \ge 1 - \beta,\]
where the probability is taken over the coins of $A$. The sample complexity of the algorithm $A$ is the database size $n$.
\end{definition}

We call a solution $x$ with $\min D \le x \le \max D$ an \emph{interior point} of $D$. Note that $x$ need not be a member of the database $D$.

\stocrm{\subsection{Lower Bound}}
\stoctext{\subsection{Lower and Upper Bounds}}
\label{sec:lowerBound}

We now prove our lower bound on the sample complexity of private algorithms for solving the interior point problem.

\begin{theorem} \label{thm:range-lb}
Fix any constant $0 < \varepsilon < 1/4$. Let $\delta(n) \le 1/(50 n^2)$. Then for every positive integer $n$, solving the interior point problem on $X$ with probability at least $3/4$ and with $(\varepsilon, \delta(n))$-differential privacy requires sample complexity $n \ge \Omega(\log^*|X|)$.
\end{theorem}

Our choice of $\delta = O( 1/n^2 )$ is unimportant; any monotonically non-increasing
convergent series will do. To prove the theorem, we inductively construct a sequence of database distributions $\{\mathcal{D}_n\}$ supported on data universes $[S(n)]$ (for $S(n+1) = 2^{\tilde{O}(S(n))}$) over which any differentially private mechanism using $n$ samples must fail to solve the interior point problem. Given a hard distribution $\mathcal{D}_n$ over $n$ elements $(x_1, x_2, \dots, x_n)$ from $[S(n)]$, we construct a hard distribution $\mathcal{D}_{n+1}$ over elements $(y_0, y_1, \dots, y_n)$ from $[S(n+1)]$ by setting $y_0$ to be a random number, and letting each other $y_i$ agree with $y_0$ on the $x_i$ most significant digits. We then show that if $y$ is the output of any differentially private interior point mechanism on $(y_0, \dots, y_n)$, then with high probability, $y$ agrees with $y_0$ on at least $\min x_i$ entries and at most $\max x_i$ entries. Thus, a private mechanism for solving the interior point problem on $\mathcal{D}_{n+1}$ can be used to construct a private mechanism for $\mathcal{D}_n$, and so $\mathcal{D}_{n+1}$ must also be a hard distribution.

The inductive lemma we prove depends on a number of parameters we now define. Fix $\frac{1}{4}>\varepsilon, \beta > 0$. Let $\delta(n)$ be any positive non-increasing
sequence for which
\[P_n \triangleq \frac{e^\varepsilon}{e^\varepsilon + 1} + (e^\varepsilon+1)\sum_{j=1}^{n} \delta(j) \le 1 - \beta \] for every $n$.
In particular, it suffices that
\[\sum_{n=1}^\infty \delta(n) \leq \frac{\frac{1}{3}-\beta}{e^\epsilon + 1}.\]
Let $b(n) = 1/\delta(n)$ and define the function $S$ recursively by
\[S(1) = 2 \quad \text{and} \quad S(n+1) = b(n)^{S(n)}.\]

\begin{lemma} \label{lem:range-lb-dist}
For every positive integer $n$, there exists a distribution $\mathcal{D}_n$ over databases $D \in [S(n)]^n = \{0, 1, \dots, S(n)-1\}^n$ such that for every $(\varepsilon, \delta(n))$-differentially private mechanism $\mathcal{M}$,
\[\Pr[\min D \le \mathcal{M}(D) \le \max D] \le P_n,\]
where the probability is taken over $D \gets_{\mbox{\tiny R}} \mathcal{D}_n$ and the coins of $\mathcal{M}$.
\end{lemma}

In this section, we give a direct proof of the lemma and in \stocrm{Appendix \ref{app:range-fpc}}\stoctext{the full version of this paper}, we show how the lemma follows from the construction of a new combinatorial object we call an ``interior point fingerprinting code.'' This is a variant on traditional fingerprinting codes, which have been used recently to show nearly optimal lower bounds for other problems in approximate differential privacy \cite{BUV14, DworkTaThZh14, BassilySmTh14}.

\begin{proof}
The proof is by induction on $n$. We first argue that the claim holds for $n = 1$ by letting $\mathcal{D}_1$ be uniform over the singleton databases $(0)$ and $(1)$. To that end let $x \gets_{\mbox{\tiny R}}\mathcal{D}_1$ and note that for any $(\varepsilon, \delta(1))$-differentially private mechanism $\mathcal{M}_0:\{0,1\}\rightarrow\{0,1\}$ it holds that
$$
\Pr[\mathcal{M}_0(x)=x]\leq e^\varepsilon \Pr[\mathcal{M}_0(\bar{x})=x]+\delta(1)=e^\varepsilon (1-\Pr[\mathcal{M}_0(x)=x])+\delta(1),
$$
giving the desired bound on $\Pr[\mathcal{M}_0(x)=x]$.

Now inductively suppose we have a distribution $\mathcal{D}_n$ that satisfies the claim. We construct a distribution $\mathcal{D}_{n+1}$ on databases $(y_0, y_1, \dots, y_n) \in [S(n+1)]^{n+1}$ that is sampled as follows:
\begin{itemize}
\item Sample $(x_1, \dots, x_n) \gets_{\mbox{\tiny R}} \mathcal{D}_n$.
\item Sample a uniformly random $y_0 \gets_{\mbox{\tiny R}} [S(n+1)]$. We write the base $b(n)$ representation of $y_0$ as $y_0^{(1)}y_0^{(2)}\dots y_0^{(S(n))}$.
\item For each $i = 1, \dots, n$ let $y_i$ be a base $b(n)$ number (written $y_i^{(1)}y_i^{(2)}\dots y_i^{(S(n))}$) that agrees with the base $b(n)$ representation of $y_0$ on the first $x_i$ digits and contains a random sample from $[b(n)]$ in every index thereafter.
\end{itemize}
Suppose for the sake of contradiction that there were an $(\varepsilon, \delta(n+1))$-differentially private mechanism $\hat{\mathcal{M}}$ that could solve the interior point problem on $\mathcal{D}_{n+1}$ with probability greater than $P_{n+1}$. We use $\hat{\mathcal{M}}$ to construct the following private mechanism $\mathcal{M}$ for solving the interior point problem on $\mathcal{D}_n$, giving the desired contradiction:

\begin{algorithm}[H]
\caption{$\mathcal{M}(D)$}
{\bf Input:} Database $D = (x_1, \dots, x_n) \in [S(n)]^n$
\begin{enumerate}
\item Construct $\hat{D} = (y_0, \dots, y_n)$ by sampling from $\mathcal{D}_{n+1}$, but starting with the database $D$. That is, sample $y_0$ uniformly at random and set every other $y_i$ to be a random base $b(n)$ string that agrees with $y_0$ on the first $x_i$ digits.
\item Compute $y \gets_{\mbox{\tiny R}} \hat{\mathcal{M}}(\hat{D})$.
\item Return the length of the longest prefix of $y$ (in base $b(n)$ notation) that agrees with $y_0$.
\end{enumerate}
\end{algorithm}

The mechanism $\mathcal{M}$ is also $(\varepsilon, \delta(n+1))$-differentially private, since for all pairs of adjacent databases $D\sim D'$ and every $T \subseteq [S(n)]$,

\begin{align*}
\Pr[\mathcal{M}(D) \in T] &= \operatorname*{\mathbb{E}}_{y_0 \gets_{\mbox{\tiny R}} [S(n+1)]} \Pr[\hat{\mathcal{M}}(\hat{D}) \in \hat{T} \mid y_0] \\
&\le \operatorname*{\mathbb{E}}_{y_0 \gets_{\mbox{\tiny R}} [S(n+1)]} (e^\varepsilon \Pr[\hat{\mathcal{M}}(\hat{D}') \in \hat{T} \mid y_0] + \delta) & \text{since $\hat{D} \sim \hat{D}'$ for fixed $y_0$}\\
& = e^{\varepsilon} \Pr[\mathcal{M}(D') \in T] + \delta,
\end{align*}
where $\hat{T}$ is the set of $y$ that agree with $y_0$ in exactly the first $x$ entries for some $x \in T$.

Now we argue that $\mathcal{M}$ solves the interior point problem on $\mathcal{D}_n$ with probability greater than $P_n$. First we show that $x \ge \min D$ with probability greater than $P_{n+1}$. Observe that by construction, all the elements of $\hat{D}$ agree in at least the first $\min D$ digits, and hence so does any interior point of $\hat{D}$. Therefore, if $\mathcal{M}'$ succeeds in outputting an interior point $y$ of $\hat{D}$, then $y$ must in particular agree with $y_0$ in at least $\min D$ digits, so $x \ge \min D$.

Now we use the privacy that $\hat{\mathcal{M}}$ provides to $y_0$ to show that $x \le \max D$ except with probability at most $e^{\varepsilon}/b(n)+ \delta(n+1)$. Fix a database $D$. Let $w = \max D$, and fix all the randomness of $\mathcal{M}$ but the $(w+1)$st entry of $y_0$ (note that since $w = \max D$, this fixes $y_1,\ldots,y_n$). Since the $(w+1)$st entry of $y_0$ is still a uniformly random element of $[b(n)]$, the privately produced entry $y^{w+1}$ should not be able to do much better than randomly guessing $y_0^{(w+1)}$. Formally, for each $z \in [b(n)]$, let $\hat{D}_z$ denote the database $\hat{D}$ with $y_0^{(w+1)}$ set to $z$ and everything else fixed as above. Then by the differential privacy of $\hat{\mathcal{M}}$,

\begin{align*}
\Pr_{z \in [b(n)]}[\hat{\mathcal{M}}(\hat{D}_z)^{w+1} = z] &= \frac{1}{b(n)} \sum_{z \in [b(n)]} \Pr[\hat{\mathcal{M}}(\hat{D}_z)^{w+1} = z] \\
&\le \frac{1}{b(n)} \sum_{z \in [b(n)]} \operatorname*{\mathbb{E}}_{z' \gets_{\mbox{\tiny R}} [b(n)]} \left[e^\varepsilon \Pr[\hat{\mathcal{M}}(\hat{D}_{z'})^{w+1} = z] +\delta(n+1)\right] \\
&\le \frac{e^{\varepsilon}}{b(n)} + \delta(n+1),
\end{align*}
where all probabilities are also taken over the coins of $\hat{\mathcal{M}}$. Thus $x \le \max D$ except with probability at most $e^{\varepsilon}/b(n)+ \delta(n+1)$. By a union bound, $\min D\le x \le \max D$ with probability greater than
\[P_{n+1} -\left( \frac{e^{\varepsilon}}{b(n)} + \delta(n+1)\right) \geq P_n.\]
This gives the desired contradiction.
\end{proof}

\stocrm{
We now prove Theorem \ref{thm:range-lb} by estimating the $S(n)$ guaranteed by Lemma \ref{lem:range-lb-dist}.

\begin{proof}[Proof of Theorem \ref{thm:range-lb}]
Let $S(n)$ be as in Lemma \ref{lem:range-lb-dist}. We introduce the following notation for iterated exponentials:
\[{\rm tower}^{(0)}(x) = x \quad \text{and} \quad  {\rm tower}^{(k)}(x) = 2^{{\rm tower}^{(k-1)}(x)}.\]
Observe that for $k \ge 1$, $x > 0$, and $M > 16$,
\begin{align*}
M^{{\rm tower}^{(k)}(x)} &= 2^{{\rm tower}^{(k)}(x) \log M} \\
&= {\rm tower}^{(2)}({\rm tower}^{(k-1)}(x) + \log\log M) \\
&\le {\rm tower}^{(2)}({\rm tower}^{(k-1)}(x + \log\log M)) \\
&= {\rm tower}^{(k+1)}(x + \log\log M).
\end{align*}
By induction on $n$ we get an upper bound of
\[S(n+1) \le {\rm tower}^{(n)}(2 + n\log\log (cn^2)) \le {\rm tower}^{(n + \log^*(cn^2))}(1).\]
This immediately shows that solving the interior point problem on $X=[S(n)]$ requires sample complexity
\begin{align*}
n &\ge \log^*S(n) - \log^*(cn^2)\\
 &\ge \log^*S(n) - O(\log^*\log^*S(n))\\
&= \log^*|X| - O(\log^*\log^*|X|).
\end{align*}
To get a lower bound for solving the interior point problem on $X$ when $|X|$ is not of the form $S(n)$, note that a mechanism for $X$ is also a mechanism for every $X'$ s.t.\ $|X'|\le |X|$. The lower bound follows by setting $|X'|=S(n)$ for the largest $n$ such that $S(n)\leq|X|$.
\end{proof}
}

\stoctext{The proof of Theorem \ref{thm:range-lb} follows by estimating the $S(n)$ guaranteed by Lemma \ref{lem:range-lb-dist}, and appears in the full version of this work. Using similar ideas, we also prove the following upper bound on the sample complexity of solving the interior point problem.

\begin{theorem}
Let $\beta,\epsilon,\delta > 0$ and let $X$ be a finite totally ordered domain.
There is an $(\epsilon,\delta)$-differentially private algorithm for solving the interior point problem on $X$ with failure probability $\beta$ and sample complexity $n=\frac{18500}{\epsilon} \cdot 2^{\log^*|X|} \cdot \log^*(|X|) \cdot \ln(\frac{4\log^*|X|}{\beta\epsilon\delta})$.
\end{theorem}
}

\iffalse
\stoctext{
We next state our upper bound for privately solving the interior point problem. Here we only present the main ideas of the construction. See the full version of this paper, included as an appendix, for full details.

\begin{theorem} \label{thm:range_queries_upperbound}
For every $\beta,\epsilon,\delta$ there exists an efficient $(\epsilon,\delta)$-differentially private algorithm for solving the interior point problem with error probability $\beta$ over $n$ elements from $X$, provided that $n\geq\frac{18480}{\epsilon}2^{\log^*|X|}\log^*(|X|)\ln(\frac{4\log^*|X|}{\beta\epsilon\delta})$.
\end{theorem}

\begin{proof}[Proof Idea]
Consider an input database $S=(x_1,\ldots,x_n)\in X^n$. Our goal is to design a private algorithm whose output is a point $x\in X$ between the minimal and the maximal points in $S$.
To that end, suppose we have paired {\em random} elements in $S$, and constructed a database $S'=(z_1,\ldots,z_{n/2})$ s.t. every $z_i$ is the length of the longest common prefix of one random pair $(x_j,x_{\ell})$.

Now assume that (by recursion) we have identified a number $z$ s.t.\
$\min\{z_i\}\leq z\leq\max\{z_i\}$. Moreover, let us assume that there are in fact {\em several} elements $z_i$ in $S'$ s.t.\ $z_i\geq z$. This could easily be achieved by, e.g., excluding the top elements from $S'$ when applying the recursion.
Therefore the number $z$ is s.t.
(1) there is at least one pair of input elements that agree on a prefix of length at most $z$; and
(2) there are several (say $k$) pairs that agree on a prefix of length at least $z$.

Although every one of those $k$ pairs may agree on a {\em different prefix} of length $z$,
it can be shown that because the pairing was random, w.h.p.\ there exists a prefix of length $(z+1)$ s.t.\ ``a lot'' of the inputs agree on it.
This prefix is ``stable'' in the scene that even if we were to change one of the input elements, there would still be ``enough'' $x_i$'s that agree on it.
Hence, (using the choosing mechanism, see Section~\ref{sec:dp-prelim}) we can privately identify a prefix $L$ of length $(z+1)$ which is the prefix of at least one input element, say $x_{i^*}$.

For $\sigma\in\{0,1\}$, let $L_{\sigma}\in X$ denote the prefix $L$ followed by appearances of $\sigma$ (e.g., $L_1=L\circ111\ldots1$). Note that $L_0\leq x_{i^*}\leq L_1$. Now recall that there are two input elements, say $x_{i_1}\leq x_{i_2}$, that agree on a prefix of length at most $z$. Hence, as $L$ is of length $z{+}1$, we have that either $x_{i_1}\leq L_0 \leq x_{i^*}$ or $x_{i^*}\leq L_1 \leq x_{i_2}$. At any case, we have privately identified two numbers ($L_0$ and $L_1$) s.t.\ at least one of them is a good output. Choosing one out of the two can be done privately using standard techniques.
\end{proof}
}
\fi

\def\mbox{\it RecPrefix}{\mbox{\it RecPrefix}}

\stocrm{
\subsection{Upper Bound}
We now present a recursive algorithm, $\mbox{\it RecPrefix}$, for privately solving the interior point problem.

\begin{theorem} \label{thm:range_queries_upperbound}
Let $\beta,\epsilon,\delta > 0$, let $X$ be a finite, totally ordered domain, and let $n \in \N$ with $n\geq\frac{18500}{\epsilon} \cdot 2^{\log^*|X|} \cdot \log^*(|X|) \cdot \ln(\frac{4\log^*|X|}{\beta\epsilon\delta})$. If $\mbox{\it RecPrefix}$ (defined below) is executed on a database $S \in X^n$ with parameters $\frac{\beta}{3\log^*|X|},\frac{\epsilon}{2\log^*|X|},\frac{\delta}{2\log^*|X|}$, then
\begin{enumerate}
	\item $\mbox{\it RecPrefix}$ is $(\epsilon,\delta)$-differentially private;
	\item With probability at least $(1-\beta)$, the output $x$ satisfies
	$\min\{x_i:x_i\in S\}\leq x\leq\max\{x_i:x_i\in S\}$.
\end{enumerate}
\end{theorem}

The idea of the algorithm is that on each level of recursion, $\mbox{\it RecPrefix}$ takes an input database $S$ over $X$ and constructs a database $S'$ over a smaller universe $X'$, where $|X'| = \log |X|$, in which every element is the length of the longest prefix of a pair of elements in $S$ (represented in binary). In a sense, this reverses the construction presented in Section~\ref{sec:lowerBound}.

\subsubsection{The exponential and choosing mechanisms}

Before formally presenting the algorithm $\mbox{\it RecPrefix}$, we introduce several additional algorithmic tools. One primitive we will use is the exponential mechanism of McSherry and Talwar~\cite{McSherryTa07}. Let $X^*$ denote the set of all finite databases over the universe $X$. A quality function  $q:X^*\times \mathcal{F} \rightarrow \N$ defines an {\em optimization problem} over the domain $X$ and a finite solution set $\mathcal{F}$:  Given a database $S \in X^*$, choose $f\in\mathcal F$ that (approximately) maximizes $q(S,f)$. The exponential mechanism solves such an optimization problem by choosing a random solution where the probability of outputting any solution $f$ increases exponentially with its quality $q(D,f)$. Specifically, it outputs each $f \in \mathcal{F}$ with probability $\propto \exp\left(\epsilon \cdot q(S,f) /2 \Delta q\right)$. Here, the sensitivity of a quality function, $\Delta q$, is the maximum over all $f\in\mathcal{F}$ of the sensitivity of the function $q(\cdot, f)$.

\begin{proposition}[Properties of the Exponential Mechanism] \label{prop:exp_mech}
\ \begin{enumerate}
\item The exponential mechanism is $\epsilon$-differentially private.
\item Let $q$ be a quality function with sensitivity at most $1$. Fix a database $S \in X^n$ and let $\operatorname{\rm OPT} = \max_{f\in \mathcal{F}}\{q(S,f)\}$. Let $t >0$. Then exponential mechanism outputs a solution $f$ with $q(S,f)\leq \operatorname{\rm OPT} - tn$ with probability at most $|\mathcal{F}| \cdot \exp(-\epsilon tn /2)$.
\end{enumerate}
\end{proposition}

We will also use an $(\varepsilon, \delta)$-differentially private variant of the exponential mechanism called the \emph{choosing mechanism}, introduced in \cite{BeimelNiSt13b}.

\iffalse
\stoctext{One building block in our algorithms is an $(\varepsilon, \delta)$-differentially private variant of the exponential mechanism \cite{McSherryTa07} called the \emph{choosing mechanism}, introduced in \cite{BeimelNiSt13b}.
The choosing mechanism is an $(\varepsilon, \delta)$-differentially private algorithm for approximately solving \emph{$k$-bounded-growth choice problems.} A quality function  $q:X^*\times \mathcal{F} \rightarrow \N$ defines an optimization problem over the domain $X$ and solution set $\mathcal{F}$:  Given a database $S \in X^*$, choose $f\in\mathcal F$ that (approximately) maximizes $q(S,f)$.}
\fi

A quality function with sensitivity at most $1$ is of {\em $k$-bounded-growth} if adding an element to a database can increase (by 1) the score of at most $k$ solutions,\mnote{We do mean ``adding an element'' here} without changing the scores of other solutions.
\stocrm{Specifically, it holds that
\begin{enumerate}
\item $q(\emptyset, f) = 0$ for all $f \in \mathcal{F}$,
\item If $S_2 = S_1 \cup \{x\}$, then $q(S_1, f) + 1 \ge q(S_2, f) \ge q(S_1, f)$ for all $f \in \mathcal{F}$, and
\item There are at most $k$ values of $f$ for which $q(S_2, f) = q(S_1, f) + 1$.
\end{enumerate}
}

\iffalse
\stoctext{When run on a $k$-bounded-growth quality function and a database $S$ of size $m$, with high probability, the choosing mechanism outputs a solution $f$ with $q(S,f) \ge \mathop{\rm{opt}}\nolimits_q(S) - O(\ln(km/\varepsilon\delta))$. See the full version of this paper for precise details.}
\fi

The choosing mechanism is a differentially private algorithm for approximately solving bounded-growth choice problems. Step~1 of the algorithm checks whether a good solution exists (otherwise any solution is approximately optimal) and Step~2 invokes the exponential mechanism, but with the {\em small} set $G(S)$ of good solutions instead of $\mathcal F$.

\begin{algorithm}
\caption{Choosing Mechanism}
\label{alg:choosing}
{\bf Input:} database $S$, quality function $q$, solution set $\mathcal F$, and parameters $\beta,\epsilon,\delta$ and $k$.
\begin{enumerate}[topsep=-1pt, rightmargin=10pt]
\item Set $\widetilde{\operatorname{\rm OPT}}=\operatorname{\rm OPT}+\operatorname{\rm Lap}(\frac{4}{\epsilon})$. If $\widetilde{\operatorname{\rm OPT}}<\frac{8}{\epsilon}\ln(\frac{4k}{\beta\epsilon\delta})$ then halt and return $\bot$.
\item Let $G(S)=\{f\in\mathcal F : q(S,f)\geq1\}$. Choose and return $f\in G(S)$ using the exponential mechanism with parameter $\frac{\epsilon}{2}$.\\
\end{enumerate}
\end{algorithm}

The following lemmas give the privacy and utility guarantees of the choosing mechanism. We give a slightly improved utility result over \cite{BeimelNiSt13b}, and the analysis is presented in Appendix \ref{app:choosing}.

\begin{lemma} \label{lem:CMprivacy}
Fix $\delta > 0$, and $0 < \epsilon\leq2$.
If $q$ is a $k$-bounded-growth quality function, then the choosing mechanism is $(\epsilon,\delta)$-differentially private.
\end{lemma}

\begin{lemma}\label{lem:CMscoreOne}
Let the choosing mechanism be executed on a $k$-bounded-growth quality function, and on a database $S$ s.t. there exists a solution $\hat{f}$ with quality $q(S,\hat{f})\geq\frac{16}{\epsilon}\ln(\frac{4k}{\beta\epsilon\delta})$.
With probability at least $(1-\beta)$, the choosing mechanism outputs a solution $f$ with quality
$q(S,f)\geq1$.
\end{lemma}

\begin{lemma}\label{lem:CMutility}
Let the choosing mechanism be executed on a $k$-bounded-growth quality function, and on a database $S$ containing $m$ elements.
With probability at least $(1-\beta)$, the choosing mechanism outputs a solution $f$ with quality
$q(S,f)\geq\operatorname{\rm OPT}-\frac{16}{\epsilon}\ln(\frac{4km}{\beta\epsilon\delta})$.
\end{lemma}

\subsubsection{The $\mbox{\it RecPrefix}$ algorithm}

We are now ready to present and analyze the algorithm $\mbox{\it RecPrefix}$.

\begin{algorithm}[H]
\caption{$\mbox{\it RecPrefix}$}
{\bf Input:} Database $S=(x_j)_{j=1}^n \in X^n$, parameters $\beta,\epsilon,\delta$.
\begin{enumerate}[rightmargin=10pt,itemsep=1pt]
\item If $|X|\leq32$, then use the exponential mechanism with privacy parameter $\epsilon$ and quality function $q(S, x)= \min\left\{ \#\{j : x_j \ge x\}, \#\{j : x_j \le x\}\right\} $ to choose and return a point $x\in X$.

\item Let $k= \lfloor \frac{386}{\epsilon}\ln(\frac{4}{\beta\epsilon\delta}) \rfloor$, and let $Y=(y_1,y_2,\ldots,y_{n-2k})$ be a random permutation of the smallest $(n{-}2k)$ elements in $S$.

\item For $j=1$ to $\frac{n-2k}{2}$, define $z_j$ as the length of the longest prefix for which $y_{2j-1}$ agrees with $y_{2j}$ (in base 2 notation).

\item Execute $\mbox{\it RecPrefix}$ recursively on $S'=(z_j)_{j=1}^{(n-2k)/2}\in (X')^{(n-2k)/2}$ with parameters $\beta,\epsilon,\delta$. Recall that $|X'| = \log |X|$. Denote the returned value by $z$.

\item Use the choosing mechanism to choose a prefix $L$ of length $(z+1)$ with a large number of agreements among elements in $S$.
Use parameters $\beta,\epsilon,\delta$, and the quality function
$q:X^* \times X^{z+1}\rightarrow\N$, where $q(S, I)$ is the number of agreements on $I$ among $x_1,\ldots,x_n$.

\item For $\sigma\in\{0,1\}$, define $L_{\sigma}\in X$ to be the prefix $L$ followed by $(\log|X|-z-1)$ appearances of $\sigma$.

\item Compute $\widehat{big}=\operatorname{\rm Lap}(\frac{1}{\epsilon})+ \#\{j : x_j\geq L_1\}$.

\item If $\widehat{big}\geq\frac{3k}{2}$ then return $L_1$. Otherwise return $L_0$.
\end{enumerate}
\end{algorithm}

We start the analysis of $\mbox{\it RecPrefix}$ with the following two simple observations.

\begin{observation}\label{obs:RecPrefixIterations}
There are at most $\log^*|X|$ recursive calls throughout the execution of $\mbox{\it RecPrefix}$ on a database $S\in X^*$.
\end{observation}

\begin{observation}\label{obs:databaseSize}
Let $\mbox{\it RecPrefix}$ be executed on a database $S\in X^n$, where $n\geq 2^{\log^*|X|} \cdot \frac{2312}{\epsilon} \cdot \ln(\frac{4}{\beta\epsilon\delta})$.
Every recursive call throughout the execution operates on a database containing at least $\frac{1540}{\epsilon} \cdot \ln(\frac{4}{\beta\epsilon\delta})$ elements.
\end{observation}

\begin{proof}
This follows from Observation~\ref{obs:RecPrefixIterations} and from the fact that the $i^\text{th}$ recursive call is executed on a database of size $n_i=\frac{n}{2^{i-1}}-k\sum_{\ell=0}^{i-2}(\frac{1}{2})^{\ell} \geq \frac{n}{2^i} - 2k$.
\end{proof}

We now analyze the utility guarantees of $\mbox{\it RecPrefix}$ by proving the following lemma.

\begin{lemma}\label{lem:RecPrefixUtility}
Let $\beta,\epsilon,\delta$, and $S\in X^n$ be inputs on which $\mbox{\it RecPrefix}$ performs at most $N$ recursive calls,
all of which are on databases of at least $\frac{1540}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$ elements.
With probability at least $(1-3\beta N)$, the output $x$ is s.t.
\begin{enumerate}
\item $\exists x_i\in S$ s.t. $x_i\leq x$;
\item $|\{i: x_i\geq x\}|\geq k\triangleq  \lfloor \frac{386}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta}) \rfloor$.
\end{enumerate}
\end{lemma}

Before proving the lemma, we make a combinatorial observation that motivates the random shuffling in Step~2 of $\mbox{\it RecPrefix}$. A pair of elements  $y,y'\in S$ is useful in Algorithm $\mbox{\it RecPrefix}$ if many of the values in $S$ lie between $y$ and $y'$ -- a prefix on which $y,y'$ agree is also a prefix of every element between $y$ and $y'$. A prefix common to a useful pair can hence be identified privately via stability-based techniques. Towards creating useful pairs, the set $S$ is shuffled randomly. We will use the following lemma:

\begin{claim}\label{claim:randomPermutation}
Let $(\Pi_1,\Pi_2,\ldots,\Pi_n)$ be a random permutation of $(1,2,\ldots,n)$. Then for all $r \ge 1$,
$$
\Pr\left[  \left| \left\{ i : \left| \Pi_{2i-1} - \Pi_{2i} \right| \leq \frac{r}{12} \right\} \right| \geq r  \right] \leq 2^{-r}
$$
\end{claim}

\begin{proof}
We need to show that w.h.p.\ there are at most $r$ ``bad'' pairs $(\Pi_{2i-1}, \Pi_{2i})$ within distance $\frac{r}{12}$. For each $i$, we call $\Pi_{2i-1}$ the left side of the pair, and $\Pi_{2i}$ the right side of the pair.
Let us first choose $r$ elements to be placed on the left side of $r$ bad pairs (there are ${n \choose r}$ such choices).
Once those are fixed, there are at most $(\frac{r}{6})^r$ choices for placing elements on the right side of those pairs.
Now we have $r$ pairs and $n-2r$ unpaired elements that can be shuffled in $(n-r)!$ ways.
Overall, the probability of having at least $r$ bad pairs is at most
$$
\frac{{n \choose r}(\frac{r}{6})^r(n-r)!}{n!}=\frac{(\frac{r}{6})^r}{r!}\leq\frac{(\frac{r}{6})^r}{\sqrt{r}r^r e^{-r}}=\frac{e^r}{\sqrt{r}6^r}\leq2^{-r},
$$
where we have used Stirling's approximation for the first inequality.
\end{proof}

Suppose we have paired random elements in our input database $S$, and constructed a database $S'$ containing lengths of the prefixes for those pairs.
Moreover, assume that by recursion we have identified a length $z$ which is the length at least $r$ random pairs.
Although those prefixes may be different for each pair, Claim~\ref{claim:randomPermutation} guarantees that (w.h.p.) at least one of these prefixes is the prefix of at least $\frac{r}{12}$ input elements.
This will help us in (privately) identifying such a prefix.

\begin{proof}[Proof of Lemma \ref{lem:RecPrefixUtility}]
The proof is by induction on the number of recursive calls, denoted as $t$.
For $t=1$ (i.e., $|X|\leq32$), the claim holds as long as the exponential mechanism outputs an $x$ with $q(S, x) \ge k$ except with probability at most $\beta$. By Proposition~\ref{prop:exp_mech}, it suffices to have $n\geq\frac{1540}{\epsilon} \cdot \ln(\frac{4}{\beta\epsilon\delta})$, since $32 \exp(-\varepsilon (n/2 - k) / 2) \le \beta$.

Assume that the stated lemma holds whenever $\mbox{\it RecPrefix}$ performs at most $t-1$ recursive calls.
Let $\beta,\epsilon,\delta$ and $S=(x_i)_{i=1}^n\in X^n$ be inputs on which algorithm $\mbox{\it RecPrefix}$ performs $t$ recursive calls, all of which are on databases containing at least $\frac{1540}{\epsilon} \cdot\ln(\frac{4}{\beta\epsilon\delta})$ elements.
Consider the first call in the execution on those inputs, and let $y_1,\ldots,y_{n-2k}$ be the random permutation chosen on Step~2.
We say that a pair $y_{2j-1},y_{2j}$ is {\em close} if $$\left|i :
\begin{array}{c}
	y_{2j-1}\leq y_i \leq y_{2j}\\
	\text{or}\\
	y_{2j}\leq y_i \leq y_{2j-1}
\end{array} \right|\leq\frac{k-1}{12}.$$
By Claim~\ref{claim:randomPermutation}, except with probability at most $2^{-(k-1)} < \beta$, there are at most
$(k-1)$ close pairs.
We continue the proof assuming that this is the case.

Let $S'=(z_i)_{i=1}^{(n-2k)/2}$ be the database constructed in Step~3.
By the inductive assumption, with probability at least $(1-3\beta(t-1))$, the value $z$ obtained in Step~4 is s.t.
(1) $\exists z_i\in S'$ s.t. $z_i\leq z$; and (2) $|\{z_i\in S' : z_i\geq z\}|\geq k$.
We proceed with the analysis assuming that this event happened.

By (2), there are at least $k$ pairs $y_{2j-1},y_{2j}$ that agree on a prefix of length at least $z$.
At least one of those pairs, say $y_{2j^*-1},y_{2j^*}$, is not {\em close}.
Note that every $y$ between $y_{2j^*-1}$ and $y_{2j^*}$ agrees on the same prefix of length $z$, and that there are at least $\frac{k-1}{12}$ such elements in $S$.
Moreover, as the next bit is either 0 or 1, at least half of those elements agree on a prefix of length $(z+1)$.
Thus, when using the choosing mechanism on Step~5 (to choose a prefix of length $(z+1)$), there exists at least one prefix with quality at least $\frac{k-1}{24}\ge\frac{16}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$. By Lemma \ref{lem:CMutility}, the choosing mechanism ensures, therefore, that with probability at least $(1-\beta)$, the chosen prefix $L$ is the prefix of at least one $y_{i'}\in S$, and, hence, this $y_{i'}$ satisfies $L_0\leq y_{i'}\leq L_1$ (defined in Step~6). We proceed with the analysis assuming that this is the case.

Let $z_{\hat{j}}\in S'$ be s.t. $z_{\hat{j}}\leq z$. By the definition of $z_{\hat{j}}$, this means that $y_{2\hat{j}-1}$ and $y_{2\hat{j}}$ agree on a prefix of length at most $z$. Hence, as $L$ is of length $z+1$, we have that either $\min\{ y_{2\hat{j}-1},y_{2\hat{j}}\}<L_0$ or $\max\{ y_{2\hat{j}-1},y_{2\hat{j}}\}>L_1$.
If $\min\{ y_{2\hat{j}-1},y_{2\hat{j}}\}<L_0$, then $L_0$ satisfies Condition~1 of being a good output. It also satisfies Condition~2 because $y_{i'} \ge L_0$ and $y_{i'} \in Y$, which we took to be the smallest $n-2k$ elements of $S$. Similarly, $L_1$ is a good output if $\max\{ y_{2\hat{j}-1},y_{2\hat{j}}\}>L_1$.
In any case, at least one out of $L_0,L_1$ is a good output.

If both $L_0$ and $L_1$ are good outputs, then Step~8 cannot fail.
We have already established the existence of $L_0\leq y_{i'}\leq L_1$. Hence, if $L_1$ is not a good output, then there are at most $(k{-}1)$ elements $x_i\in S$ s.t. $x_i\geq L_1$. Hence, the probability of $\widehat{big} \ge 3k/2$ and Step~8 failing is at most $\exp(-\frac{\epsilon k}{2})\leq\beta$. It remains to analyze the case where $L_0$ is not a good output (and $L_1$ is).

If $L_0$ is not a good output, then every $x_j\in S$ satisfies $x_j>L_0$.
In particular, $\min\{ y_{2\hat{j}-1},y_{2\hat{j}}\}>L_0$, and, hence, $\max\{ y_{2\hat{j}-1},y_{2\hat{j}}\}>L_1$.
Recall that there are at least $2k$ elements in $S$ which are bigger than $\max\{ y_{2\hat{j}-1},y_{2\hat{j}}\}$.
As $k\geq\frac{2}{\epsilon}\ln(\frac{1}{\beta})$, the probability that $\widehat{big} < 3k/2$ and $\mbox{\it RecPrefix}$ fails to return $L_1$ in this case is at most $\beta$.

All in all, $\mbox{\it RecPrefix}$ fails to return an appropriate $x$ with probability at most $3\beta t$.
\end{proof}

We now proceed with the privacy analysis.

\begin{lemma}\label{lem:RecPrefixPrivacy}
When executed for $N$ recursive calls, $\mbox{\it RecPrefix}$ is $(2\epsilon N,2\delta N)$-differentially private.
\end{lemma}

\begin{proof}
The proof is by induction on the number of recursive calls, denoted by $t$.
For $t=1$ (i.e., $|X|\leq32$), then by Proposition~\ref{prop:exp_mech} the exponential mechanism ensures that $\mbox{\it RecPrefix}$ is $(\epsilon,0)$-differentially private.
Assume that the stated lemma holds whenever $\mbox{\it RecPrefix}$ performs at most $t-1$ recursive calls, and let $S_1,S_2\in X^*$ be two neighboring databases on which $\mbox{\it RecPrefix}$ performs $t$ recursive calls.\footnote{The recursion depth is determined by $|X|$, which is identical in $S_1$ and in $S_2$.}
Let $\mathcal B$ denote an algorithm consisting of steps~1-4 of $\mbox{\it RecPrefix}$ (the output of $\mathcal B$ is the value $z$ from Step~4).
Consider the executions of $\mathcal B$ on $S_1$ and on $S_2$, and denote by $Y_1,S'_1$ and by $Y_2,S'_2$ the elements $Y,S'$ as they are in the executions on $S_1$ and on $S_2$.

We show that the distributions on the databases $S'_1$ and $S'_2$ are similar in the sense that for each database in one of the distributions
there exist a neighboring database in the other that have the same
probability. Thus, applying the recursion (which is differentially private by the inductive assumption) preserves privacy. We now make this argument formal.

First note that as $S_1,S_2$ differ in only one element,
there is a bijection between
orderings $\Pi$ and $\widehat{\Pi}$ of the smallest $(n-2k)$ elements of $S_1$ and of $S_2$ respectively s.t. $Y_1$ and $Y_2$ are neighboring databases. This is because there exists a permutation of the smallest $(n-2k)$ elements of $S_1$ that is a neighbor of the smallest $(n-2k)$ elements of $S_2$; composition with this fixed permutation yields the desired bijection.
Moreover, note that whenever $Y_1,Y_2$ are neighboring databases, the same is true for $S'_1$ and $S'_2$. Hence, for every set of outputs $F$ it holds that

\begin{eqnarray*}
\Pr[\mathcal B(S)\in F] &=& \sum_{\Pi}\Pr[\Pi]\cdot\Pr[\mbox{\it RecPrefix}(S'_1) \in F|\Pi]\\
&\leq& e^{2\epsilon(t-1)}\cdot\sum_{\Pi}\Pr[\Pi]\cdot\Pr[\mbox{\it RecPrefix}(S'_2) \in F|\widehat{\Pi}]+2\delta(t-1)\\
&=& e^{2\epsilon(t-1)}\cdot\sum_{\widehat{\Pi}}\Pr[\widehat{\Pi}]\cdot\Pr[\mbox{\it RecPrefix}(S'_2) \in F|\widehat{\Pi}]+2\delta(t-1)\\
&=& e^{2\epsilon(t-1)}\cdot\Pr[\mathcal B(S')\in F]+2\delta(t-1)\\
\end{eqnarray*}

So when executed for $t$ recursive calls, the sequence of Steps~1-4 of $\mbox{\it RecPrefix}$ is $(2\epsilon(t{-}1),2\delta(t{-}1))$-differentially private.
On Steps~5 and~7, algorithm $\mbox{\it RecPrefix}$ interacts with its database through the choosing mechanism and using the Laplace mechanism, each of which is $(\epsilon,\delta)$-differentially private. By composition (Lemma \ref{lem:composition}), we get that $\mbox{\it RecPrefix}$ is $(2t\epsilon,2t\delta)$-differentially private.
\end{proof}

Combining Lemma~\ref{lem:RecPrefixUtility} and Lemma~\ref{lem:RecPrefixPrivacy} we obtain Theorem~\ref{thm:range_queries_upperbound}.

\subsubsection{Informal Discussion and Open Questions}
An natural open problem is to close the gap between our (roughly) $2^{\log^* |X|}$ upper bound on the sample complexity of privately solving the interior point problem (Theorem \ref{thm:range_queries_upperbound}), and our $\log^* |X|$ lower bound (Theorem \ref{thm:range-lb}). Below we describe an idea for reducing the upper bound to $\mathop{\rm{poly}}\nolimits(\log^* |X|)$.

In our recursive construction for the lower bound, we took $n$ elements $(x_1,\ldots,x_n)$ and generated $n+1$ elements where $y_0$ is a random element (independent of the $x_i$'s), and every $x_i$ is the length of the longest common prefix of $y_0$ and $y_i$. Therefore, a change limited to one $x_i$ affects only one $y_i$ and privacy is preserved (assuming that our future manipulations on $(y_0,\ldots,y_n)$ preserve privacy). While the representation length of domain elements grows exponentially on every step, the database size grows by 1. This resulted in the $\Omega(\log^*|X|)$ lower bound.

In $\mbox{\it RecPrefix}$ on the other hand, every level of recursion shrank the database size by a factor of $\frac{1}{2}$, and hence, we required a sample of (roughly) $2^{\log^*|X|}$ elements. Specifically, in each level of recursion, two input elements $y_{2j-1},y_{2j}$ were paired and a new element $z_j$ was defined as the length of their longest common prefix. As with the lower bound, we wanted to ensure that a change limited to one of the inputs affects only one new element, and hence, every input element is paired only once, and the database size shrinks.

If we could pair input elements {\em twice} then the database size would only be reduced additively (which will hopefully result in a $\mathop{\rm{poly}}\nolimits(\log^*|X|)$ upper bound). However, this must be done carefully, as we are at risk of deteriorating the privacy parameter $\epsilon$ by a factor of $2$ and thus remaining with an exponential dependency in $\log^*|X|$.
Consider the following thought experiment for pairing elements.
\begin{center}
\noindent\fbox{
\parbox{0.95\textwidth}{
{\bf Input:} $(x_1,\ldots,x_n)\in X^n$.
\begin{enumerate}[topsep=-1pt, rightmargin=10pt]
\item Let $(y_1^0,\ldots,y_n^0)$ denote a random permutation of $(x_1,\ldots,x_n)$.
\item For $t=1$ to $\log^*|X|$:
\begin{enumerate}[label={}, topsep=-1pt, rightmargin=10pt]
	\item For $i=1$ to $(n{-}t)$, let $y_i^t$ be the length of the longest common prefix of $y_i^{t-1}$ and $y_{i+1}^{t-1}$.
\end{enumerate}
\end{enumerate}
}}
\end{center}

As (most of the) elements are paired twice on every step, the database size reduces additively. In addition, every input element $x_i$ affects at most $t+1$ elements at depth $t$, and the privacy loss is acceptable. However, this still does not solve the problem. Recall that every iteration of $\mbox{\it RecPrefix}$ begins by randomly shuffling the inputs. Specifically, we needed to ensure that (w.h.p.) the number of ``close'' pairs is limited. The reason was that if a ``not close'' pair agrees on a prefix $L$, then $L$ is the prefix ``a lot'' of other elements as well, and we could privately identify $L$.
In the above process we randomly shuffled only the elements at depth $0$. Thus we do not know if the number of ``close'' pairs is small at depth $t>0$. On the other hand, if we changed the pairing procedure to shuffle at every step, then each input element $x_i$ might affect $2^t$ elements at depth $t$, causing the privacy loss to deteriorate rapidly.
}

\stoctext{
\section{Equivalences with the Interior Point Problem}
We show that under $(\epsilon,\delta)$-differential privacy the interior point problem is equivalent with each of the following three problems: (1) Query release for threshold functions, (2) Distribution learning with respect to Kolmogorov distance, and (3) Proper PAC learning of threshold functions.
Hence, our bounds from Section~\ref{sec:lowerBound} translate to new bounds on the sample complexity of those three problems.
Here we only state the equivalences; see the full version of the paper for more details.
}

\stocrm{
\section{Query Release and Distribution Learning}

\subsection{Definitions}

Recall that a {\em counting query} $q$ is a predicate $q: X \to \{0, 1\}$. For a database $D = (x_1, \dots, x_n) \in X^n$, we write $q(D)$ to denote the average value of $q$ over the rows of $D$, i.e.
$q(D) = \frac{1}{n} \sum_{i = 1}^n q(x_i).$
In the query release problem, we seek differentially private algorithms that can output approximate answers to a family of counting queries $Q$ simultaneously.

\begin{definition}[Query Release]
Let $Q$ be a collection of counting queries on a data universe $X$, and let $\alpha, \beta > 0$ be parameters. For a database $D \in X^n$, a sequence of answers $\{a_q\}_{q \in Q}$ is \emph{$\alpha$-accurate} for $Q$ if $|a_q - q(D)| \le \alpha$ for every $q\in Q$. An algorithm $A: X^n \to \R^{|Q|}$ is \emph{$(\alpha, \beta)$-accurate for $Q$} if for every $D \in X^n$, the output $A(D)$ is $\alpha$-accurate for $Q$ with probability at least $1-\beta$ over the coins of $A$. The sample complexity of the algorithm $A$ is the database size $n$.
\end{definition}

We are interested in the query release problem for the class $\operatorname*{\tt THRESH}_X$ of \emph{threshold queries}, which we view as a class of counting queries.

We are also interested in the following \emph{distribution learning} problem, which is very closely related to the query release problem.

\begin{definition}[Distribution Learning with respect to $Q$]
Let $Q$ be a collection of counting queries on a data universe $X$. Algorithm $A$ is an $(\alpha, \beta)$-accurate \emph{distribution learner with respect to $Q$} with sample complexity $n$ if for all distributions $\mathcal{D}$ on $X$, given an input of $n$ samples $D = (x_1, \dots, x_n)$ where each $x_i$ is drawn i.i.d.\ from $\mathcal{D}$, algorithm $A$ outputs a distribution $\mathcal{D}'$ on $X$ (specified by its PMF) satisfying $d_{Q}(\mathcal{D}, \mathcal{D}') \triangleq \sup_{q \in Q}|\operatorname*{\mathbb{E}}_{x \sim \mathcal{D}}[q(x)]- \operatorname*{\mathbb{E}}_{x \sim \mathcal{D}'}[q(x)]| \le \alpha$ with probability at least $1 - \beta$.
\end{definition}

We highlight two important special cases of the distance measure $d_Q$ in the distribution learning problem. First, when $Q$ is the collection of \emph{all} counting queries on a domain $X$, the distance $d_{Q}$ is the \emph{total variation distance} between distributions, defined by
\[d_{\mathrm{TV}}(\mathcal{D}, \mathcal{D}') \triangleq \sup_{S \subseteq X} |\Pr_{x \sim \mathcal{D}}[x \in S]- \Pr_{x \sim \mathcal{D}'}[x \in S]|.\]
 Second, when $X$ is a totally ordered domain and $Q = \operatorname*{\tt THRESH}_X$, the distance $d_Q$ is the \emph{Kolmogorov }(or CDF) distance. A distribution learner in the latter case may as well output a CDF that approximates the target CDF in $\ell_\infty$ norm. Specifically, we define

\begin{definition}[Cumulative Distribution Function (CDF)]
Let $\mathcal{D}$ be a distribution over a totally ordered domain $X$. The CDF $F_{\mathcal{D}}$ of $\mathcal{D}$ is defined by $F_{\mathcal{D}}(t) = \Pr_{x \sim \mathcal{D}}[x \le t]$. If $X$ is finite, then any function $F: X \to [0, 1]$ that is non-decreasing with $F(\max X) = 1$ is a CDF.
\end{definition}

\begin{definition}[Distribution Learning with respect to Kolmogorov distance]
Algorithm $A$ is an $(\alpha, \beta)$-accurate \emph{distribution learner with respect to Kolmogorov distance} with sample complexity $n$ if for all distributions $\mathcal{D}$ on a totally ordered domain $X$, given an input of $n$ samples $D = (x_1, \dots, x_n)$ where each $x_i$ is drawn i.i.d.\ from $\mathcal{D}$, algorithm $A$ outputs a CDF $F$ with $\sup_{x \in X} |F(x) - F_{\mathcal{D}}(x)|$ with probability at least $1 - \beta$.
\end{definition}

The query release problem for a collection of counting queries $Q$ is very closely related to the distribution learning problem with respect to $Q$. In particular, solving the query release problem on a dataset $D$ amounts to learning the empirical distribution of $D$. Conversely, results in statistical learning theory show that one can solve the distribution learning problem by first solving the query release problem on a sufficiently large random sample, and then fitting a distribution to approximately agree with the released answers.
\stocrm{The requisite size of this sample (without privacy considerations) is characterized by a combinatorial measure of the class $Q$ called the VC dimension:
\begin{definition}
Let $Q$ be a collection of queries over domain $X$. A set $S = \{x_1, \dots, x_k\} \subseteq X$ is \emph{shattered} by $Q$ if for every $T \subseteq [k]$ there exists $q \in Q$ such that $T=\{i:q(x_i) = 1\}$. The \emph{Vapnik-Chervonenkis (VC) dimension} of $Q$, denoted $\operatorname{\rm VC}(Q)$, is the cardinality of the largest set $S \subseteq X$ that is shattered by $Q$.
\end{definition}

It is known \cite{AnthonyBa09} that solving the query release problem on $256 \operatorname{\rm VC}(Q) \ln(48/\alpha\beta) / \alpha^2$ random samples yields an $(\alpha, \beta)$-accurate distribution learner for a query class $Q$.
}

\subsection{Equivalences with the Interior Point Problem}
\subsubsection{Private Release of Thresholds vs. the Interior Point Problem}
}
\stoctext{\paragraph{Private Release of Thresholds vs. the Interior Point Problem.}}
We show that the problems of privately releasing thresholds and solving the interior point problem are equivalent.

\begin{theorem} \label{thm:sanitization-vs-range}
Let $X$ be a totally ordered domain. Then,
\begin{enumerate}
	\item If there exists an $(\varepsilon,\delta)$-differentially private algorithm that is able to release threshold queries on $X$ with $(\alpha,\beta)$-accuracy and sample complexity $n/(8\alpha)$, then there is an $(\varepsilon, \delta)$-differentially private algorithm that solves the interior point problem on $X$ with error $\beta$ and sample complexity $n$.

	\item If there exists an $(\varepsilon, \delta)$-differentially private algorithm solving the interior point problem on $X$ with error $\alpha\beta/24$ and sample complexity $m$, then there is a $(5\varepsilon, (1 + e^{\varepsilon})\delta)$-differentially private algorithm for releasing threshold queries with $(\alpha, \beta)$-accuracy and sample complexity
\[n = \max \left\{ \frac{6m}{\alpha},  \frac{25\log(24/\beta)\log^{2.5}(6/\alpha)}{\alpha\varepsilon} \right\}.\]
\end{enumerate}

\end{theorem}

For the first direction, observe that an algorithm for releasing thresholds could easily be used for solving the interior point problem. \stocrm{Formally,

\begin{proof}[Proof of Theorem~\ref{thm:sanitization-vs-range} item 1]
Suppose}\stoctext{More formally, suppose}
$\mathcal{A}$ is a private $(\alpha,\beta)$-accurate algorithm for releasing thresholds over $X$ for databases of size $\frac{n}{8\alpha}$. Define $\mathcal{A}'$ on databases of size $n$ to pad the database with an equal number of $\min\{X\}$ and $\max\{X\}$ entries, and run $\mathcal{A}$ on the result. We can now return any point $t$ for which the approximate answer to the query $c_t$ is $(\frac{1}{2}\pm\alpha)$ on the (padded) database.
\stocrm{\end{proof}}

\stocrm{We now show the converse, i.e., that the problem of releasing thresholds can be reduced to the interior point problem. Specifically, we reduce the problem to a combination of solving the interior point problem, and of releasing thresholds on a much smaller data universe.
The latter task is handled by the following algorithm.

\begin{lemma}[\cite{DworkNaPiRo10}] \label{lem:prefix-tree}
For every finite data universe $X$, and $n\in\N$, $\varepsilon,\beta>0$,
there is an $\varepsilon$-differentially private algorithm $A$ that releases all threshold queries on $X$ with $(\alpha,\beta)$-accuracy for
\[\alpha=\frac{4 \log(1/\beta)\log^{2.5}|X|}{\varepsilon n}.\]
\end{lemma}

}

\stoctext{For proving the second direction of the equivalence, we reduce the problem of releasing thresholds to a combination of solving the interior point problem, and of releasing thresholds on a much smaller data universe.}
The idea of the reduction is to create noisy partitions of the input database into $O(1/\alpha)$ blocks of size roughly $\alpha n / 3$. We then solve the interior point problem on each of these blocks, and think of the results as representatives for each block. By answering threshold queries on just the set of representatives, we can well-approximate all threshold queries. Moreover, since there are only $O(1/\alpha)$ representatives,
\stocrm{the base algorithm above gives only $\mathrm{polylog}(1/\alpha)$ error for these answers.}
\stoctext{we can use the results of~\cite{DworkNaPiRo10} in order to incur only $\mathrm{polylog}(1/\alpha)$ error for these answers.}

\stocrm{
In Appendix \ref{app:thresh-from-range2}, we describe another reduction that, up to constant factors, gives the same sample complexity.

\begin{proof}[Proof of Theorem~\ref{thm:sanitization-vs-range} item 2]
Let $R: X^* \to X$ be an $(\varepsilon, \delta)$-differentially private algorithm solving the interior point problem on $X$ with error $\alpha\beta/24$ and sample complexity $m$.
We may actually assume that $R$ is differentially private in the sense that if $D \in X^*$ and $D'$ differs from $D$ up to the addition or removal of a row, then for every $S \subseteq X$, $\Pr[R(D) \in S] \le e^{\varepsilon} \Pr[R(D') \in S] + \delta$, and that $R$ solves the interior point problem with probability at least $1-\alpha\beta/24$ whenever its input is of size at least $m$. This is because we can pad databases of size less than $m$ with an arbitrary fixed element, and subsample the first $m$ entries from any database with size greater than $m$.

Consider the following algorithm for answering thresholds on databases $D \in X^n$ for $n > m$:
\begin{algorithm}[H]
\caption{$Thresh(D)$}
\textbf{Input:} Database $D = (x_1, \dots, x_n) \in X^n$.
\begin{enumerate}
\item Sort $D$ in nondecreasing order $x_1 \le x_2 \le \dots \le x_n$.

\item Set $k = 6/\alpha$ and let $t_0 = 1, t_1 = t_0 + \alpha n / 3 + \nu_1, t_2 = t_1 + \alpha n / 3 + \nu_2 \dots, t_k = t_{k-1} + \alpha n / 3 + \nu_k$ where each $\nu_\ell \sim \operatorname{\rm Lap}(1/\varepsilon)$ independently.

\item Divide $D$ into blocks $D_1, \dots, D_k$, where $D_\ell = (x_{t_{\ell-1}}, \dots, x_{t_{\ell}-1})$ (setting $x_j = \max X$ if $j > n$; note some $D_\ell$ may be empty).

\item Let $r_0 = \min X$, $r_1 = R(D_1), \dots, r_k = R(D_k)$ and define $\hat{D}$ from $D$ by replacing each $x_j$ with the largest $r_\ell$ for which $r_\ell \le x_j$.

\item Run algorithm $A$ from Lemma~\ref{lem:prefix-tree} on $\hat{D}$ over the universe $\{r_0, r_1, \dots, r_k\}$ to obtain threshold query answers $a_{r_0}, a_{r_1}, \dots, a_{r_k}$. Use privacy parameter $\varepsilon$ and confidence parameter $\beta/4$.

\item Answer arbitrary threshold queries by interpolation, i.e. for $r_\ell \le t < r_{\ell+1}$, set $a_t = a_{r_\ell}$.

\item Output $(a_t)_{t\in X}$.
\end{enumerate}
\end{algorithm}

\paragraph{Privacy} Let $D = (x_1, \dots, x_n)$ where $x_1 \le x_2 \le \dots \le x_n$, and consider a neighboring database $D' = (x_1, \dots, x_i', \dots, x_n)$. Assume without loss of generality that $x_i' \ge x_{i+1}$, and suppose
\[x_1 \le \dots \le x_{i-1} \le x_{i+1} \le \dots \le x_{j} \le x_{i}' \le x_{j+1} \le \dots \le x_n.\]
We write vectors of noise values as $\nu = (\nu_1, \nu_2, \dots, \nu_k)$. There is a bijection between noise vectors $\nu$ and noise vectors $\nu'$ such that $D$ partitioned according to $\nu$ and $D'$ partitioned according to $\nu'$ differ on at most two blocks: namely, if $\ell, r$ are the indices for which $t_{\ell-1} \le i < t_{\ell}$ and $t_{r - 1} \le j < t_r$ (we may have $\ell=r$), then we can take $\nu'_{\ell} = \nu_\ell - 1$ and $\nu'_{r} = \nu_r + 1$ with $\nu' = \nu$ at every other index.
Note that $D$ partitioned into $(D_1,\ldots,D_k)$ according to $\nu$ differs from $D'$ partitioned into $(D'_1,\ldots,D'_k)$ according to $\nu'$
by a removal of an element from one block (namely $D_\ell$) and the addition of an element to another block (namely $D'_r$). Thus, for every set $S \subseteq X^m$,
\[\Pr[(R(D_1), \dots, R(D_k)) \in S \;  | \; \nu] \le e^{2\varepsilon} \Pr[(R(D'_1), \dots, R(D'_k)) \in S \; | \; \nu'] + (1+e^{\varepsilon})\delta.\]
Moreover, under the bijection we constructed between $\nu$ and $\nu'$, noise vector $\nu'$ is sampled with density at most $e^{2\varepsilon}$ times the density of $\nu$, so for every set $S \subseteq X^m$,
\begin{align*}
\Pr[(R(D_1), \dots, R(D_k)) \in S] &\le e^{2\varepsilon}(e^{2\varepsilon}\Pr[(R(D'_1), \dots, R(D'_k)) \in S]) + (1+e^{\varepsilon})\delta \\
&= e^{4\varepsilon} \Pr[(R(D'_1), \dots, R(D'_k)) \in S]  + (1 + e^{\varepsilon})\delta.
\end{align*}
Finally, the execution of $A$ at the end of the algorithm is $\varepsilon$-differentially private, so by composition (Lemma~\ref{lem:composition}), we obtain the asserted level of privacy.

\paragraph{Utility} We can produce $\alpha$-accurate answers to every threshold function as long as
\begin{enumerate}
\item The partitioning exhausts the database, i.e. every element of $D$ is in some $D_i$,
\item Every execution of $R$ succeeds at finding an interior point,
\item Every database $D_i$ has size at most $5\alpha n / 12$ (ensuring that we have error at most $5\alpha/6$ from interpolation),
\item The answers obtained from executing $A$ all have error at most $\alpha /6$.
\end{enumerate}
We now estimate the probabilities of each event. For each $i$ we have $\nu_i \ge -\alpha n /6$ with probability at least
\[1 - \exp(-\alpha n \varepsilon / 6) \ge 1 - \alpha\beta/24.\]
So by a union bound, every $\nu_i$ is at least $(-\alpha n /6)$ with probability at least $1 - \beta/4$. If this is the case, then item 1 holds because
$t_k = k\cdot\alpha n/3 + \nu_1 + \dots + \nu_k \geq (6/\alpha)(\alpha n/3) + (6/\alpha)(-\alpha n/6)\geq n$. Moreover, if every $\nu_i \ge -\alpha n / 6$, then item 2 also holds with probability at least $1 - \beta/4$. This is because every $|D_i| \ge \alpha n/3 - \alpha n/6 \ge m$, and hence every execution of $R$ on a subdatabase $D_i$ succeeds with probability $1 - \alpha\beta/24$.

By a similar argument, property 3 holds as long as each noise value $\nu_i$ is at most $\alpha n / 12$, which happens with probability at least $1 - \beta/4$. Finally, property 4 holds with probability at least $1-\beta/4$ since
\[\alpha n \ge \frac{24}{\varepsilon} \log (4/\beta) \log^{2.5}(1 + 6/\alpha).\]
A union bound over the four properties completes the proof.
\end{proof}

\subsubsection{Releasing Thresholds vs.\ Distribution Learning}
}

\stoctext{\paragraph{Releasing Thresholds vs.\ Distribution Learning.}}
Query release and distribution learning are very similar tasks: A distribution learner can be viewed as an algorithm for query release with small error w.r.t.\ the underlying distribution (rather than the fixed input database). We show that the two tasks are equivalent under differential privacy.

\begin{theorem}\label{thm:distlearning-release-reduction}
Let $Q$ be a collection of counting queries over a domain $X$.
\begin{enumerate}
	\item If there exists an $(\varepsilon,\delta)$-differentially private algorithm for releasing $Q$ with $(\alpha,\beta)$-accuracy and sample complexity $n\geq 256 \operatorname{\rm VC}(Q) \ln(48/\alpha\beta) / \alpha^2$, then there is an $(\varepsilon,\delta)$-differentially private $(3\alpha, 2\beta)$-accurate distribution learner w.r.t.\ $Q$ with sample complexity $n$.

	\item If there exists an $(\varepsilon, \delta)$-differentially private $(\alpha, \beta)$-accurate distribution learner w.r.t.\ $Q$ with sample complexity $n$, then there is an $(\varepsilon,\delta)$-differentially private query release algorithm for $Q$ with $(\alpha,\beta)$-accuracy and sample complexity $9n$.
\end{enumerate}

\end{theorem}

The first direction follows from a standard generalization bound, showing that if a given database $D$ contains (enough) i.i.d.\ samples from a distribution $\mathcal{D}$, then (w.h.p.) accuracy with respect to $D$ implies accuracy with respect to $\mathcal{D}$. We remark that the sample complexity lower bound on $n$ required to apply item 1 of Theorem~\ref{thm:distlearning-release-reduction} does not substantially restrict its applicability: It is known that an $(\varepsilon, \delta)$-differentially private algorithm for releasing $Q$ always requires sample complexity $\Omega(\operatorname{\rm VC}(Q)/\alpha\varepsilon)$ anyway \cite{BlumLiRo08}.

\stocrm{
\begin{proof}[Proof of Theorem~\ref{thm:distlearning-release-reduction}, item 1]
Suppose $\tilde{\mathcal{A}}$ is an $(\varepsilon,\delta)$-differentially private algorithm for releasing $Q$ with $(\alpha,\beta)$-accuracy and sample complexity $n\geq 256 \operatorname{\rm VC}(Q) \ln(48/\alpha\beta) / \alpha^2$.
Fix a distribution $\mathcal{D}$ over $X$ and consider a database $D$ containing $n$ i.i.d.\ samples from $\mathcal{D}$.
Define the algorithm $\mathcal{A}$ that on input $D$ runs $\tilde{\mathcal{A}}$ on $D$ to obtain answers $a_q$ for every query $q \in Q$. Afterwards, algorithm $\mathcal{A}$ uses linear programming \cite{DworkNaReRoVa09} to construct a distribution $\mathcal{D}'$ that such that $|a_q - q(\mathcal{D}')| \le \alpha$ for every $q \in Q$, where $q(\mathcal{D}') \triangleq \operatorname*{\mathbb{E}}_{x \sim \mathcal{D}'}[q(x)]$. This reconstruction always succeeds as long as the answers $\{a_q\}$ are $\alpha$-accurate, since the empirical distribution of $D$ is a feasible point for the linear program. Note that $\mathcal{A}$ is $(\varepsilon,\delta)$-differentially private (since it is obtained by post-processing $\tilde{\mathcal{A}}$).

We first argue that $q(\mathcal{D}')$ is close to $q(D)$ for every $q\in Q$, and then argue that $q(D)$ is close to $q(\mathcal{D})$. By the utility properties of $\tilde{\mathcal{A}}$, with all but probability $\beta$,
$$
|q(\mathcal{D}') - q(D)| \le |q(\mathcal{D}') - a_q| + |a_q - q(D)| \le 2\alpha.
$$
for every $q \in Q$.

We now use the following generalization theorem to show that (w.h.p.) $q(D)$ is close to $q(\mathcal{D})$ for every $q \in Q$.

\begin{theorem}[\cite{AnthonyBa09}] \label{thm:dist-generalization}
Let $Q$ be a collection of counting queries over a domain $X$. Let $D = (x_1, \dots, x_n)$ consist of i.i.d.\ samples from a distribution $\mathcal{D}$ over $X$. If $d = \operatorname{\rm VC}(Q)$, then
\[\Pr\left[\sup_{q \in Q} |q(D) - q(\mathcal{D})| > \alpha\right] \le 4 \left(\frac{2en}{d}\right)^d\exp\left(-\frac{\alpha^2n}{8}\right).\]
\end{theorem}

Using the above theorem, together with the fact that $n \ge 256 \operatorname{\rm VC}(Q) \ln(48/\alpha\beta) / \alpha^2$, we see that except with probability at least $1 - \beta$ we have that $|q(D) - q(\mathcal{D}))|\leq \alpha$ for every $q \in Q$. By a union bound (and the triangle inequality) we get that $\mathcal{A}$ is $(3\alpha,2\beta)$-accurate.
\end{proof}

In the special case where $Q = \operatorname*{\tt THRESH}_X$ for a totally ordered domain $X$, corresponding to distribution learning under Kolmogorov distance, the above theorem holds as long as $n \ge 2\ln(2/\beta)/\alpha^2$.
This follows from using the Dvoretzky-Kiefer-Wolfowitz inequality \cite{DvoretzkyKiWo56,massart1990} in place of Theorem \ref{thm:dist-generalization}.

\begin{theorem}
If there exists an $(\varepsilon,\delta)$-differentially private algorithm for releasing $\operatorname*{\tt THRESH}_X$ over a totally ordered domain $X$ with $(\alpha,\beta)$-accuracy and sample complexity $n\geq 2\ln(2/\beta)/\alpha^2$, then there is an $(\varepsilon,\delta)$-differentially private $(2\alpha, 2\beta)$-accurate distribution learner under Kolmogorov distance with sample complexity $n$.
\end{theorem}

We now show the other direction of the equivalence.

\begin{lemma}\label{lem:nonprivateSubsample}
Suppose $\mathcal{A}$ is an $(\varepsilon, \delta)$-differentially private and $(\alpha, \beta)$-accurate distribution learner w.r.t.\ a concept class $Q$ with sample complexity $n$. Then there is an $(\varepsilon, \delta)$-differentially private algorithm $\tilde{\mathcal{A}}$ for releasing $Q$ with $(\alpha,\beta)$-accuracy and sample complexity $9n$.
\end{lemma}
}

\stoctext{For the second direction of the equivalence,}
\stocrm{To construct the algorithm $\tilde{\mathcal{A}}$,}
we note that a distribution learner must perform well on the uniform distribution on the rows of any fixed database, and thus must be useful for releasing accurate answers for queries on such a database. Thus if we have a distribution learner $\mathcal{A}$, the mechanism $\tilde{\mathcal{A}}$ that samples $m$ rows (with replacement) from its input database $D \in (X \times \{0, 1\})^n$ and runs $\mathcal{A}$ on the result should output accurate answers for queries with respect to $D$. The random sampling has two competing effects on privacy. On one hand, the possibility that an individual is sampled multiple times incurs additional privacy loss. On the other hand, if $n > m$, then a ``secrecy-of-the-sample'' argument shows that random sampling actually improves privacy, since any individual is unlikely to have their data affect the computation at all. We show that if $n$ is only a constant factor larger than $m$, these two effects offset, and the resulting mechanism is still differentially private.

\stocrm{
\begin{proof}
Consider a database $D \in X^{9n}$. Let $\mathcal{D}$ denote the uniform distribution over the rows of $D$, and let $\mathcal{D}'$ be the distribution learned. Consider the algorithm $\tilde{\mathcal{A}}$ that subsamples (with replacement) $n$ rows from $D$ and runs $\mathcal{A}$ on it to obtain a distribution $\mathcal{D}'$. Afterwards, algorithm $\tilde{\mathcal{A}}$ answers every threshold query $q \in Q$ with $a_q = q(\mathcal{D}') \triangleq \operatorname*{\mathbb{E}}_{x \sim \mathcal{D}'}[q(x)]$.

Note that drawing $n$ i.i.d.\ samples from $\mathcal{D}$ is equivalent to subsampling $n$ rows of $D$ (with replacement).
Then with probability at least $1 - \beta$, the distribution $\mathcal{D}'$ returned by $\mathcal{A}$ is such that for every $x\in X$
$$
|q(\mathcal{D}')-q(D)| = |q(\mathcal{D}')-q(\mathcal{D})| \leq \alpha,
$$
showing that $\tilde{\mathcal{A}}$ is $(\alpha,\beta)$-accurate.
\end{proof}

We'll now use a secrecy-of-the-sample argument (refining an argument that appeared implicitly in \cite{KasiviswanathanLeNiRaSm07}), to show that $\tilde{\mathcal{A}}$ (from Lemma~\ref{lem:nonprivateSubsample}) is differentially private whenever $\mathcal{A}$ is differentially private.

\begin{lemma}\label{lem:secrecy-of-the-sample}
Fix $\epsilon\leq1$ and let $\mathcal{A}$ be an $(\varepsilon, \delta)$-differentially private algorithm operating on databases of size $m$.
For $n\geq2m$, construct an algorithm $\tilde{\mathcal{A}}$ that on input a database $D$ of size $n$ subsamples (with replacement) $m$ rows from $D$ and runs $\mathcal{A}$ on the result. Then $\tilde{\mathcal{A}}$ is $( \tilde{\varepsilon} , \tilde{\delta} )$-differentially private for
$$\tilde{\varepsilon}=6\varepsilon m /n \quad \text{and} \quad \tilde{\delta}= \exp(6\varepsilon m/n)\frac{4m}{n}\cdot\delta.$$
\end{lemma}

\begin{proof}
Let $D, D'$ be adjacent databases of size $n$, and suppose without loss of generality that they differ on the last row. Let $T$ be a random variable denoting the multiset of indices sampled by $\tilde{\mathcal{A}}$, and let $\ell(T)$ be the multiplicity of index $n$ in $T$. Fix a subset $S$ of the range of $\tilde{\mathcal{A}}$. For each $k = 0, 1, \dots, m$ let
\begin{align*}
p_k &= \Pr[\ell(T) = k] = {m \choose k} n^{-k} (1 - 1/n)^{m - k} = {m \choose k} (n-1)^{-k} (1 - 1/n)^m ,\\
q_k &= \Pr[\mathcal{A}(D|_T) \in S | \ell(T) = k], \\
q'_k &= \Pr[\mathcal{A}(D'|_T) \in S | \ell(T) = k].
\end{align*}
Here, $D|_T$ denotes the subsample of $D$ consisting of the indices in $T$, and similarly for $D'|_T$. Note that $q_0 = q'_0$, since $D|_T = D'|_T$ if index $n$ is not sampled. Our goal is to show that
\[\Pr[\tilde{\mathcal{A}}(D) \in S] = \sum_{k=0}^{m} p_k q_k \le e^{\tilde{\varepsilon}} \sum_{k=0}^{m} p_kq'_k + \tilde{\delta} = e^{\tilde{\varepsilon}} \Pr[\tilde{\mathcal{A}}(D') \in S] + \tilde{\delta}.\]

To do this, observe that by privacy,
$q_k \le e^{\varepsilon}q_{k-1} + \delta$, so
\[q_k \le e^{k\varepsilon} q_0 + \frac{e^{k\varepsilon} - 1}{e^{\varepsilon} - 1}\delta.\]

Hence,
\begin{eqnarray}
\Pr[\tilde{\mathcal{A}}(D) \in S] &=& \sum_{k=0}^{m} p_k q_k \nonumber \\
&\leq& \sum_{k=0}^{m}  {m \choose k} (n-1)^{-k} (1 - 1/n)^m \left(  e^{k\varepsilon} q_0 + \frac{e^{k\varepsilon} - 1}{e^{\varepsilon} - 1}\delta \right) \nonumber \\
&=& q_0 (1 - 1/n)^m \sum_{k=0}^{m} {m \choose k} \left(\frac{e^\varepsilon}{n-1}\right)^k
    + \frac{\delta}{e^{\varepsilon} - 1} (1 - 1/n)^m \sum_{k=0}^{m} {m \choose k} \left(\frac{e^\varepsilon}{n-1}\right)^k
    - \frac{\delta}{e^{\varepsilon} - 1} \nonumber \\
&=& q_0 (1 - 1/n)^m \left( 1 + \frac{e^\varepsilon}{n-1} \right)^m
    + \frac{\delta}{e^{\varepsilon} - 1} (1 - 1/n)^m \left( 1 + \frac{e^\varepsilon}{n-1} \right)^m
    - \frac{\delta}{e^{\varepsilon} - 1} \nonumber \\
&=& q_0 \left( 1-\frac{1}{n}+\frac{e^\varepsilon}{n} \right)^m + \frac{\left( 1-\frac{1}{n}+\frac{e^\varepsilon}{n} \right)^m -1}{e^\varepsilon -1}\delta. \label{eq:pkqk1}
\end{eqnarray}

Similarly, we also have that
\begin{eqnarray}
\Pr[\tilde{\mathcal{A}}(D') \in S] \geq q_0 \left( 1-\frac{1}{n}+\frac{e^{-\varepsilon}}{n} \right)^m - \frac{\left( 1-\frac{1}{n}+\frac{e^{-\varepsilon}}{n} \right)^m -1}{e^{-\varepsilon} -1}\delta.
\label{eq:pkqk2}
\end{eqnarray}

Combining inequalities~\ref{eq:pkqk1} and~\ref{eq:pkqk2} we get that
\begin{eqnarray*}
\Pr[\tilde{\mathcal{A}}(D) \in S] &\leq& \left(\frac{1-\frac{1}{n}+\frac{e^\varepsilon}{n}}{1-\frac{1}{n}+\frac{e^{-\varepsilon}}{n}}\right)^m
\cdot\left\{ \Pr[\tilde{\mathcal{A}}(D') \in S]  +\frac{1-\left(1-\frac{1}{n}+\frac{e^{-\varepsilon}}{n}\right)^m}{1-e^{-\varepsilon}}\delta \right\}
+\frac{\left(1-\frac{1}{n}+\frac{e^\varepsilon}{n}\right)^m -1}{e^\varepsilon -1}\delta,
\end{eqnarray*}
proving that $\mathcal{A}'$ is $(\tilde{\varepsilon},\tilde{\delta})$-differentially private for
\begin{eqnarray*}
\tilde{\varepsilon} &\leq& m\cdot\ln\left( \frac{1+\frac{e^\varepsilon -1}{n}}{1+\frac{e^{-\varepsilon}-1}{n}} \right)
\leq\frac{6\varepsilon m}{n}
\end{eqnarray*}
and
\begin{eqnarray*}
\tilde{\delta}&\leq& \exp(6\varepsilon m/n)\frac{1-\left(1+\frac{e^{-\varepsilon}-1}{n}\right)^m}{1-e^{-\varepsilon}}\cdot\delta + \frac{\left(1+\frac{e^{\varepsilon}-1}{n}\right)^m-1}{e^{\varepsilon}-1}\cdot\delta\\
&\leq& \exp(6\varepsilon m/n)\frac{1-\exp\left(2\frac{e^{-\varepsilon} -1}{n/m}\right)}{1-e^{-\varepsilon}}\cdot\delta + \frac{\exp\left(\frac{e^\varepsilon-1}{n/m}\right)-1}{e^{\varepsilon}-1}\cdot\delta\\
&\leq& \exp(6\varepsilon m/n)\frac{2m}{n}\cdot\delta + \frac{2m}{n}\cdot\delta\\
&\leq& \exp(6\varepsilon m/n)\frac{4m}{n}\cdot\delta.
\end{eqnarray*}

\end{proof}

\section{PAC Learning}

\subsection{Definitions}

A concept $c:X\rightarrow \{0,1\}$ is a predicate that labels {\em examples} taken from the domain $X$.  A \emph{concept class} $C$ over $X$ is a set of concepts over the domain $X$. A learner is given examples sampled from an unknown probability distribution $\mathcal{D}$ over $X$ that are labeled according to an unknown {\em target concept} $c\in C$ and outputs a hypothesis $h$ that approximates the target concept with respect to the distribution $\mathcal{D}$. More precisely,

\begin{definition}
The {\em generalization error} of a hypothesis $h:X\rightarrow\{0,1\}$ (with respect to a target concept $c$ and distribution $\mathcal{D}$) is defined by
${\rm error}_{\mathcal{D}}(c,h)=\Pr_{x \sim \mathcal{D}}[h(x)\neq c(x)].$
If ${\rm error}_{\mathcal{D}}(c,h)\leq\alpha$ we say that $h$ is an {\em $\alpha$-good} hypothesis for $c$ on $\mathcal{D}$.
\end{definition}

\begin{definition}[PAC Learning~\cite{Valiant84}]\label{def:PAC}
Algorithm $A$ is an {\em $(\alpha,\beta)$-accurate PAC learner} for a concept class $C$ over $X$ using hypothesis class $H$ with sample complexity $m$ if for all target concepts $c \in C$ and all distributions $\mathcal{D}$ on $X$, given an input of $m$ samples $D =((x_i, c(x_i)),\ldots,(x_m, c(x_m)))$, where each $x_i$ is drawn i.i.d.\ from $\mathcal{D}$, algorithm $A$ outputs a hypothesis $h\in H$ satisfying
$\Pr[{\rm error}_{\mathcal{D}}(c,h)  \leq \alpha] \geq 1-\beta.$

The probability is taken over the random choice of the examples in $D$ and the coin tosses of the learner $A$. If $H\subseteq C$ then $A$ is called {\em proper}, otherwise, it is called {\em improper}.
\end{definition}

\begin{definition}
The \emph{empirical error} of a hypothesis $h$ on a labeled sample $S=((x_1,\ell_1), \dots, (x_m, \ell_m))$ is ${\rm error}_S(h) = \frac{1}{m} |\{i : h(x_i) \neq \ell_i\}|.$
If ${\rm error}_{S}(h) \le \alpha$ we say $h$ is \emph{$\alpha$-consistent} with $S$.
\end{definition}

Classical results in statistical learning theory show that
a sample of size $\Theta(\operatorname{\rm VC}(C))$ is both necessary and sufficient for PAC learning a concept class $C$. \stocrm{That $O(\operatorname{\rm VC}(C))$ samples suffice follows from a ``generalization'' argument: for any concept $c$ and distribution $\mathcal{D}$, with probability at least $1-\beta$ over $m > O_{\alpha,\beta}(\operatorname{\rm VC}(C))$ random labeled examples, \emph{every} concept $h \in C$ that agrees with $c$ on the examples has error at most $\alpha$ on $\mathcal{D}$. Therefore, $C$ can be properly learned by finding any hypothesis $h \in C$ that agrees with the given examples.}

Recall the class of \emph{threshold functions}, which are concepts defined over a totally ordered domain $X$ by $\operatorname*{\tt THRESH}_X = \{c_x : x \in X\}$ where $c_x(y) = 1$ iff $y \le x$\mnote{Didn't change this to $y \ge x$ (yet)}. The class of threshold functions has VC dimension $\operatorname{\rm VC}(\operatorname*{\tt THRESH}_X) = 1$, and hence can be learned with $O_{\alpha, \beta}(1)$ samples.

A private learner is a PAC learner that is differentially private. Following \cite{KasiviswanathanLeNiRaSm07}, we consider algorithms $A: (X \times \{0, 1\})^m \to H$, where $H$ is a hypothesis class, and require that
\begin{enumerate}
\item $A$ is an $(\alpha, \beta)$-accurate PAC learner for a concept class $C$ with sample complexity $m$, and
\item $A$ is $(\varepsilon, \delta)$-differentially private.
\end{enumerate}

\stocrm{Note that while we require utility (PAC learning) to hold only when the database $D$ consists of random labeled examples from a distribution, the requirement of differential privacy applies to every pair of neighboring databases $D \sim D'$, including those that do not correspond to examples labeled by any concept.}

Recall the relationship between distribution learning and releasing thresholds, where accuracy is measured w.r.t.\ the underlying distribution in the former and w.r.t.\ the fixed input database in the later. Analogously, we now define the notion of an {\em empirical learner} which is similar to a PAC learner where accuracy is measured w.r.t.\ the fixed input database.

\begin{definition}[Empirical Learner]
Algorithm $A$ is an {\em $(\alpha,\beta)$-accurate empirical learner} for a concept class $C$ over $X$ using hypothesis class $H$ with sample complexity $m$ if for every $c\in C$ and for every database $D =((x_i, c(x_i)),\ldots,(x_m, c(x_m)))\in(X\times\{0,1\})^m$ algorithm $A$ outputs a hypothesis $h\in H$ satisfying
$\Pr[{\rm error}_{D}(c,h)  \leq \alpha] \geq 1-\beta.$

The probability is taken over the coin tosses of $A$.
\end{definition}

Note that without privacy (and ignoring computational efficiency) identifying a hypothesis with small empirical error is trivial for every concept class $C$ and for every database of size at least $1$. This is not the case with $(\varepsilon,\delta)$-differential privacy,\footnote{The lower bound in Theorem~\ref{thm:empiricalVC} also holds for {\em label private} empirical learners, that are only required to provide privacy for the labels in the database.} and the sample complexity of every empirical learner for a concept class $C$ is at least $\Omega(\operatorname{\rm VC}(C))$:

\begin{theorem}\label{thm:empiricalVC}
For every $\alpha,\beta\leq1/8$, every $\delta\leq\frac{1}{8n}$ and $\epsilon>0$,
if $\mathcal{A}$ is an $(\varepsilon,\delta)$-differentially private $(\alpha,\beta)$-accurate empirical learner for a class $C$ with sample complexity $n$, then
$n=\Omega\left(\frac{1}{\alpha\epsilon}\operatorname{\rm VC}(C)\right)$.
\end{theorem}

The proof of Theorem~\ref{thm:empiricalVC} is very similar the analysis of~\cite{BlumLiRo08} for lower bounding the sample complexity of releasing approximated answers for queries in the class $C$.
As we will see in the next section, at least in some cases (namely, for threshold functions) the sample complexity must also have some dependency in the size of the domain $X$.

\begin{proof}[Proof of Theorem~\ref{thm:empiricalVC}]
Fix $d<\operatorname{\rm VC}(C)$, let $x_0,x_1,x_2,\ldots,x_d$ be {\em shattered} by $C$, and denote $S=\{x_1,\ldots,x_d\}$.
Let $D$ denote a database containing $(1-8\alpha)n$ copies of $x_0$ and $8\alpha n/d$ copies of every $x_i\in S$.
For a concept $c$ we use $D_c$ to denote the database $D$ labeled by $c$.
We will consider concepts that label $x_0$ as 0, and label exactly half of the elements in $S$ as 1.
To that end, initiate $\tilde{C}=\emptyset$, and for every subset $S'\subseteq S$ of size $|S'|=|S|/2$, add to $\tilde{C}$ one concept $c\in C$ s.t.\ $c(x_0)=0$ and for every $x_i\in S$ it holds that $c(x_i)=1$ iff $x_i\in S'$ (such a concept exists since $S\cup\{x_0\}$ is shattered by $C$).

Now, let $c\in\tilde{C}$ be chosen uniformly at random, let $x\in S$ be a random element s.t.\ $c(x)=1$, and let $y\in S$ be a random element s.t.\ $c(y)=0$. Also let $c'\in\tilde{C}$ be s.t.\ $c'(x)=0$, $c'(y)=1$, and $c'(x_i)=c(x_i)$ for every $x_i\in S\setminus\{x,y\}$. Note that the marginal distributions on $c$ and on $c'$ are identical, and denote $h=\mathcal{A}(D_c)$ and $h'=\mathcal{A}(D_{c'})$.

Observe that $x$ is a random element of $S$ that is labeled as 1 in $D_c$, and that an $\alpha$-consistent hypothesis for $D_c$ must label at least $(1-\frac{1}{8})d$ such elements as 1. Hence, by the utility properties of $\mathcal{A}$, we have that
$$
\Pr[h(x)=1]\geq(1-\beta)(1-1/8)\geq3/4.
$$
Similarly, $x$ is a random elements of $S$ that is labeled as 0 in $D_{c'}$, and an $\alpha$-consistent hypothesis for $D_{c'}$ must not label more than $d/8$ such elements as 1. Hence,
$$
\Pr[h'(x)=1]\leq\beta+(1-\beta)\frac{1}{8}\leq1/4.
$$

Finally, as $D_c$ and $D_{c'}$ differ in at most $16\alpha n/d$ entries, differential privacy ensures that
$$
3/4\leq\Pr[h(x)=1]
\leq e^{16 \alpha \epsilon n/d}\cdot\Pr[h'(x)=1]+e^{16 \alpha \epsilon n/d}\cdot 16 \alpha n \delta/d
\leq e^{16 \alpha \epsilon n/d}\cdot1/2,
$$
showing that $n\geq\frac{d}{40\alpha\epsilon}$.
\end{proof}

\subsection{Private Learning of Thresholds vs.\ the Interior Point Problem}\label{sec:PPAC-vs-IPP}
}
\stoctext{\paragraph{Private Learning of Thresholds vs.\ the Interior Point Problem.}}

We show that with differential privacy, there is a $\Theta(1/\alpha)$ multiplicative relationship between the sample complexities of properly PAC learning thresholds with $(\alpha, \beta)$-accuracy and of solving the interior point problem with error probability $\Theta(\beta)$. Specifically, we show

\begin{theorem}\label{thm:learning-vs-range}
Let $X$ be a totally ordered domain. Then,
\begin{enumerate}
	\item If there exists an $(\varepsilon, \delta)$-differentially private algorithm solving the interior point problem on $X$ with error probability $\beta$ and sample complexity $n$, then there is a $(2\varepsilon, (1 + e^{\varepsilon})\delta)$-differentially private $(2\alpha, 2\beta)$-accurate proper PAC learner for
\stoctext{threshold functions over $X$}\stocrm{$\operatorname*{\tt THRESH}_X$}
with sample complexity $\max \left\{\frac{n}{2\alpha}, \frac{4 \log(2/\beta)}{\alpha}\right\}$.

	\item If there exists an $(\varepsilon,\delta)$-differentially private $(\alpha, \beta)$-accurate proper PAC learner for
\stoctext{thresholds over $X$}
\stocrm{$\operatorname*{\tt THRESH}_X$}
with sample complexity $n$, then there is a $(2\varepsilon, (1 + e^{\varepsilon})\delta)$-differentially private algorithm that solves the interior point problem on $X$ with error $\beta$ and sample complexity $27\alpha n$.
\end{enumerate}

\end{theorem}

We show this equivalence in two phases. In the first, we show a $\Theta(1/\alpha)$ relationship between the sample complexity of solving the interior point problem and the sample complexity of
\stoctext{identifying an $\alpha$-consistent hypothesis for every fixed input database.}
\stocrm{empirically learning thresholds.}
We then use generalization and resampling arguments to show that with privacy, this latter task is equivalent to learning with samples from a distribution.

\stocrm{
\begin{lemma}\label{lem:range-learning-reduction}
Let $X$ be a totally ordered domain. Then,
\begin{enumerate}
	\item If there exists an $(\varepsilon, \delta)$-differentially private algorithm solving the interior point problem on $X$ with error probability $\beta$ and sample complexity $n$, then there is a $(2\varepsilon, (1 + e^{\varepsilon})\delta)$-differentially private algorithm for properly and empirically learning thresholds with $(\alpha, \beta)$-accuracy and sample complexity $n / (2\alpha)$.

	\item If there exists an $(\varepsilon,\delta)$-differentially private algorithm that is able to properly and empirically learn thresholds on $X$ with $(\alpha,\beta)$-accuracy and sample complexity $n/(3\alpha)$, then there is a $(2\varepsilon, (1 + e^{\varepsilon})\delta)$-differentially private algorithm that solves the interior point problem on $X$ with error $\beta$ and sample complexity $n$.
\end{enumerate}

\end{lemma}

\begin{proof}
For the first direction, let $\mathcal{A}$ be a private algorithm for the interior point problem on databases of size $n$. Consider the algorithm $\mathcal{A}'$ that, on input a database $D$ of size $n/(2\alpha)$, runs $\mathcal{A}'$ on a database $D'$ consisting of the largest $n/2$ elements of $D$ that are labeled $1$ and the smallest $n/2$ elements of $D$ that are labeled $0$. If there are not enough of either such element, pad $D'$ with $\min\{X\}$'s or $\max\{X\}$'s respectively. Note that if $x$ is an interior point of $D'$ then $c_x$ is a threshold function with error at most $\frac{n/2}{n/(2\alpha)}$ on $D$, and is hence $\alpha$-consistent with $D$.
For privacy, note that changing one row of $D$ changes at most two rows of $D'$. Hence, applying algorithm $\mathcal{A}$ preserves $(2\varepsilon,(e^\varepsilon+1)\delta)$-differential privacy.

For the reverse direction, suppose $\mathcal{A}'$ privately finds an $\alpha$-consistent threshold functions for databases of size $n/(3\alpha)$. Define $\mathcal{A}$ on a database $D'\in X^n$ to label the smaller $n/2$ points 1 and the larger $n/2$ points 0 to obtain a labeled database $D\in(X\times\{0,1\})^n$, pad $D$ with an equal number of $(\min\{X\},1)$ and $(\max\{X\},0)$ entries to make it of size $n/(3\alpha)$, and run $\mathcal{A}'$ on the result. Note that if $c_x$ is a threshold function with error at most $\alpha$ on $D$ then $x$ is an interior point of $D'$, as otherwise $c_x$ has error at least $\frac{n/2}{n/(3\alpha)}>\alpha$ on $D$.
For privacy, note that changing one row of $D'$ changes at most two rows of $D$. Hence, applying algorithm $\mathcal{A}'$ preserves $(2\varepsilon,(e^\varepsilon+1)\delta)$-differential privacy.
\end{proof}

Now we show that the task of privately outputting an almost consistent hypothesis on any fixed database is essentially equivalent to the task of private (proper) PAC learning. One direction follows immediately from a standard generalization bound for learning thresholds:

\begin{lemma}
Any algorithm $\mathcal{A}$ for empirically learning $\operatorname*{\tt THRESH}_X$ with $(\alpha,\beta)$-accuracy is also a $(2\alpha, \beta + \beta')$-accurate PAC learner for $\operatorname*{\tt THRESH}_X$ when given at least $\max \{n, 4\ln (2/\beta')/\alpha\}$ samples.
\end{lemma}

\begin{proof}
Let $\mathcal{D}$ be a distribution over a totally ordered domain $X$ and fix a target concept $c=q_x \in \operatorname*{\tt THRESH}_X$. It suffices to show that for a sample $S=((x_i,c(x_i)), \dots (x_m, c(x_m)))$ where $m\geq4\ln (2/\beta')/\alpha$
and the $x_i$ are drawn i.i.d.\ from $\mathcal{D}$, it holds that
\[\Pr\left[\exists \; h\in C:\;\; {\rm error}_\mathcal{D}(h,c) > 2\alpha\ \land \  {\rm error}_S(h)\leq\alpha \right] \le \beta'.\]

Let $x^- \le x$ be the largest point with ${\rm error}_{\mathcal{D}}(q_{x^-}, c) \ge 2\alpha$. If some $y \le x$ has ${\rm error}_{\mathcal{D}}(q_{y}, c) \ge 2\alpha$ then $y \le x^{-}$, and hence for any sample $S$, ${\rm error}_S(q_{x^-}) \le {\rm error}_S(q_{y})$. Similarly let $x^+ \ge x$ be the smallest point with ${\rm error}_{\mathcal{D}}(q_{x^+}, c) \ge 2\alpha$. Let $c^- = q_{x^-}$ and $c^+ = q_{x^+}$. Then it suffices to show that
\[\Pr\left[{\rm error}_S(c^-)\leq\alpha \lor {\rm error}_S(c^+) \leq\alpha\right] \le \beta'.\]
Concentrating first on $c^-$, we define the error region $R^- = (x^-, x] \cap X$ as the interval where $c^-$ disagrees with $c$. By a Chernoff bound, the probability that after $m$ independent samples from $\mathcal{D}$, fewer than $\alpha m$ appear in $R^-$ is at most $\exp(-\alpha m / 4) \le \beta'/2$. The same argument holds for $c^+$, so the result follows by a union bound.
\end{proof}

In general, an algorithm that can output an $\alpha$-consistent hypothesis from concept class $\mathcal{C}$ can also be used to learn $\mathcal{C}$ using $\max \{n, 64\operatorname{\rm VC}(\mathcal{C}) \log (512/\alpha \beta')/\alpha\}$ samples \cite{BlumerEhHaWa89}. The concept class of thresholds has VC dimension $1$, so the generalization bound for thresholds saves an $O(\log(1/\alpha))$ factor over the generic statement.

For the other direction, we note that a distribution-free learner must perform well on the uniform distribution on the rows of any fixed database, and thus must be useful for outputting a consistent hypothesis on such a database.

\begin{lemma}
Suppose $\mathcal{A}$ is an $(\epsilon,\delta)$-differentially private $(\alpha, \beta)$-accurate PAC learner for a concept class $\mathcal{C}$ with sample complexity $m$. Then there is an $(\epsilon,\delta)$-differentially private $(\alpha, \beta)$-accurate empirical learner for $\mathcal{C}$ with sample complexity $n=9m$. Moreover, if $\mathcal{A}$ is proper, then so is the resulting empirical learner.
\end{lemma}

\begin{proof}
Consider a database $D = \{(x_i, y_i)\} \in (X \times \{0, 1\})^n$. Let $\mathcal{D}$ denote the uniform distribution over the rows of $D$. Then drawing $m$ i.i.d.\ samples from $\mathcal{D}$ is equivalent to subsampling $m$ rows of $D$ (with replacement). Consider the algorithm $\tilde{\mathcal{A}}$ that subsamples (with replacement) $m$ rows from $D$ and runs $\mathcal{A}$ on it. Then with probability at least $1 - \beta$, algorithm $\mathcal{A}$ outputs an $\alpha$-good hypothesis on $\mathcal{D}$, which is in turn an $\alpha$-consistent hypothesis for $D$. Moreover, by Lemma~\ref{lem:secrecy-of-the-sample} (secrecy-of-the-sample), algorithm $\mathcal{A}$ is $(\varepsilon,\delta)$-differentially private.
\end{proof}

}

\stocrm{
\section{Thresholds in High Dimension}

We next show that the bound of $\Omega(\log^*|X|)$ on the sample complexity of private proper-learners for $\operatorname*{\tt THRESH}_X$ extends to conjunctions of $\ell$ independent threshold functions in $\ell$ dimensions. As we will see, every private proper-learner for this class requires a sample of $\Omega(\ell \cdot \log^*|X|)$ elements. This also yields a similar lower bound for the task of query release, as in general an algorithm for query release can be used to construct a private learner.

The significance of this lower bound is twofold. First, for reasonable settings of parameters (e.g. $\delta$ is negligible and items in $X$ are of polynomial bit length in $n$), our $\Omega(\log^*|X|)$ lower bound for threshold functions is dominated by the dependence on $\log(1/\delta)$ in the upper bound. However, $\ell \cdot \log^*|X|$ can still be much larger than $\log(1/\delta)$, even when $\delta$ is negligible in the bit length of items in $X^\ell$. Second, the lower bound for threshold functions only yields a separation between the sample complexities of private and non-private learning for a class of VC dimension $1$. Since the concept class of $\ell$-dimensional thresholds has VC dimension of $\ell$, we obtain an $\omega(\operatorname{\rm VC}(C))$ lower bound for concept classes even with arbitrarily large VC dimension.

Consider the following extension of $\operatorname*{\tt THRESH}_X$ to $\ell$ dimensions.

\begin{definition}
For a totally ordered set $X$ and $\vec{a}=(a_1,\ldots,a_{\ell})\in X^{\ell}$ define the concept $c_{\vec{a}}:X^{\ell}\rightarrow\{0,1\}$ where $c_{\vec{a}}(\vec{x})=1$ if and only if for every $1\leq i\leq \ell$ it holds that $x_i\leq a_i$. Define the concept class of all thresholds over $X^{\ell}$ as $\operatorname*{\tt THRESH}_X^{\ell}=\{ c_{\vec{a}} \}_{\vec{a}\in X^{\ell}}$.
\end{definition}

Note that the VC dimension of $\operatorname*{\tt THRESH}_X^{\ell}$ is $\ell$. We obtain the following lower bound on the sample complexity of privately learning $\operatorname*{\tt THRESH}_X^{\ell}$.

\begin{theorem} \label{thm:lb-higher}
For every $n, \ell \in \N$, $\alpha > 0$, and $\delta \le \ell^2/(1500n^2)$, any $(\varepsilon = \frac{1}{2}, \delta)$-differentially private and $(\alpha, \beta = \frac{1}{8})$-accurate proper learner for $\operatorname*{\tt THRESH}_X^{\ell}$ requires sample complexity $n=\Omega(\frac{\ell}{\alpha}\log^*|X|)$.
\end{theorem}

This is the result of a general hardness amplification theorem for private proper learning. We show that if privately learning a concept class $C$ requires sample complexity $n$, then learning the class $C^\ell$ of conjunctions of $\ell$ different concepts from $C$ requires sample complexity $\Omega(\ell n)$.

\begin{definition}
For $\ell \in \N$, a data universe $X$ and a concept class $C$ over $X$, define a concept class $C^\ell$ over $X^\ell$ to consist of all $\vec{c} = (c_1, \dots, c_\ell)$, where $\vec{c}: X^\ell \to \{0, 1\}$ is defined by $\vec{c}(\vec{x}) = c_1(x_1) \land c_2(x_2) \land \dots \land c_{\ell}(x_{\ell})$.
\end{definition}

\begin{theorem} \label{thm:lb-higher-general}
Let $\alpha, \beta, \varepsilon, \delta > 0$. Let $C$ be a concept class over a data universe $X$, and assume there is a domain element $p_1\in X$ s.t.\ $c(p_1)=1$ for every $c\in C$. Let $\mathcal{D}$ be a distribution over databases containing $n$ examples from $X$ labeled by a concept in $C$, and suppose that every $(\varepsilon, \delta)$-differentially private algorithm fails to find an $(\alpha/\beta)$-consistent hypothesis $h \in C$ for $D \sim \mathcal{D}$ with probability at least $2\beta$. Then any $(\varepsilon, \delta)$-differentially private and $(\alpha, \beta)$-accurate proper learner for $C^\ell$ requires sample complexity $\Omega(\ell n)$.
\end{theorem}

Note that in the the above theorem we assumed the existence of a domain element $p_1\in X$ on which every concept in $C$ evaluates to 1. To justify the necessity of such an assumption, consider the class of {\em point functions} over a domain $X$ defined as $\operatorname{\tt POINT}_X=\{ c_x : x\in X \}$ where $c_x(y)=1$ iff $y=x$. As was shown in~\cite{BeimelNiSt13b}, this class can be privately learned using $O_{\alpha,\beta,\epsilon,\delta}(1)$ labeled examples (i.e., the sample complexity has no dependency in $|X|$). Observe that since there is no $x\in X$ on which every point concept evaluates to 1, we cannot use Theorem~\ref{thm:lb-higher-general} to lower bound the sample complexity of privately learning $\operatorname{\tt POINT}_X^{\ell}$. Indeed, the class $\operatorname{\tt POINT}_X^{\ell}$ is identical (up to renaming of domain elements) to the class $\operatorname{\tt POINT}_{X\ell}$, and can be privately learned using $O_{\alpha,\beta,\epsilon,\delta}(1)$ labeled examples.

\begin{remark}
Similarly to Theorem~\ref{thm:lb-higher-general} it can be shown that if privately learning a concept class $C$ requires sample complexity $n$, and if there exists a domain element $p_0\in X$ s.t.\ $c(p_0)=0$ for every $c\in C$, then learning the class of {\em disjunctions} of $\ell$ concepts from $C$ requires sample complexity $\ell n$.
\end{remark}

\begin{proof}[Proof of Theorem~\ref{thm:lb-higher-general}]
Assume toward a contradiction that there exists an $(\varepsilon, \delta)$-differentially private and $(\alpha, \beta)$-accurate proper learner $\mathcal{A}$ for $C^{\ell}$ using $\ell n / 9$ samples.
Recall that the task of privately outputting a good hypothesis on any fixed database is essentially equivalent to the task of private PAC learning (See Section~\ref{sec:PPAC-vs-IPP}).
We can assume, therefore, that $\mathcal{A}$ outputs an $\alpha$-consistent hypothesis for every fixed database of size at least $n' \triangleq \ell n$ with probability at least $1 - \beta$.

We construct an algorithm ${Solve}_{\mathcal{D}}$ which uses $\mathcal{A}$ in order to find an $(\alpha/\beta)$-consistent threshold function for databases of size $n$ from $\mathcal{D}$. Algorithm ${Solve}_{\mathcal{D}}$ takes as input a set of $n$ labeled examples in $X$ and applies $\mathcal{A}$ on a database containing $n'$ labeled examples in $X^{\ell}$.
The $n$ input points are embedded along one random axis, and random samples from $\mathcal{D}$ are placed on each of the other axes (with $n$ labeled points along each axis).

\begin{algorithm}[H]
\caption{${Solve}_{\mathcal{D}}$}
{\bf Input:} Database $D=(x_i,y_i)_{i=1}^{n} \in (X \times \{0,1\})^{n}$.
\begin{enumerate}[rightmargin=10pt,itemsep=1pt]

\item Initiate $S$ as an empty multiset.
\item Let $r$ be a (uniform) random element from $\{1,2,\ldots,\ell\}$.
\item For $i=1$ to $n$, let $\vec{z_i}\in X^{\ell}$ be the vector with $r^\text{th}$ coordinate $x_i$, and all other coordinates $p_1$ (recall that every concept in $C$ evaluates to 1 on $p_1$). Add to $S$ the labeled example $(\vec{z_i},y_i)$.
\item For every axis $t\neq r$:
\begin{enumerate}
	\item Let $D'=(x'_i,y'_i)_{i=1}^{n} \in (X \times \{0,1\})^{n}$ denote a (fresh) sample from $\mathcal{D}$.
	\item For $i=1$ to $n$, let $\vec{z'_i}\in X^{\ell}$ be the vector whose $t^\text{th}$ coordinate is $x'_i$, and its other coordinates are $p_1$. Add to $S$ the labeled example $(\vec{z'_i},y'_i)$.
\end{enumerate}
\item Let $(h_1,h_2,\ldots,h_{\ell})=\vec{h}\leftarrow\mathcal{A}(S)$.
\item Return $h_r$.
\end{enumerate}
\end{algorithm}

First observe that ${Solve}_{\mathcal{D}}$ is $(\varepsilon,\delta)$-differentially private. To see this, note that a change limited to one input entry affects only one entry of the multiset $S$. Hence, applying the $(\varepsilon,\delta)$-differentially private algorithm $\mathcal{A}$ on $S$ preserves privacy.

Consider the execution of ${Solve}_{\mathcal{D}}$ on a database $D$ of size $n$, sampled from $\mathcal{D}$.
We first argue that $\mathcal{A}$ is applied on a multiset $S$ correctly labeled by a concept from $C^{\ell}$.
For $1\leq t\leq\ell$ let $(x^t_i,y^t_i)_{i=1}^{n}$ be the sample from $\mathcal{D}$ generated for the axis $t$, let $(\vec{z^t_i},y^t_i)_{i=1}^{n}$ denote the corresponding elements that were added to $S$, and let $c_t$ be s.t.\ $c_t(x^t_i)=y^t_i$ for every $1\leq i \leq n$. Now observe that
$$
(c_1,c_2,\ldots,c_{\ell})(\vec{z^t_i})=c_1(p_1)\land c_2(p_1)\land \dots \land c_t(x^t_i)\land\dots\land c_{\ell}(p_1) = y^t_i,
$$
and hence $S$ is perfectly labeled by $(c_1,c_2,\ldots,c_{\ell})\in C^{\ell}$.

By the properties of $\mathcal{A}$, with probability at least $1-\beta$ we have that $\vec{h}$ (from Step~5) is an $\alpha$-consistent hypothesis for $S$.
Assuming that this is the case, there could be at most $\beta\ell$ ``bad'' axes on which $\vec{h}$ errs on more than $\alpha n / \beta$ points.
Moreover, as $r$ is a random axis, and as the points along the $r^\text{th}$ axis are distributed exactly like the points along the other axes, the probability that $r$ is a ``bad'' axis is at most $\frac{\beta\ell}{\ell}=\beta$.
Overall, ${Solve}_{\mathcal{D}}$ outputs an $(\alpha/\beta)$-consistent hypothesis with probability at least $(1-\beta)^2>1-2\beta$. This contradicts the hardness of the distribution $\mathcal{D}$.
\end{proof}

Now the proof of Theorem \ref{thm:lb-higher} follows from the lower bound on the sample complexity of privately finding an $\alpha$-consistent threshold function (see Section~\ref{sec:lowerBound}):

\begin{lemma}[Follows from Lemma~\ref{lem:range-lb-dist} and~\ref{lem:range-learning-reduction}]\label{lemma:lowerRestated}
There exists a constant $\lambda>0$ s.t.\ the following holds.
For every totally ordered data universe $X$ there exists a distribution $\mathcal{D}$ over databases containing at most $n=\frac{\lambda}{\alpha}\log^*|X|$ labeled examples from $X$ such that every $(\frac{1}{2}, \frac{1}{50 n^2})$-differentially private algorithm fails to find an $\alpha$-consistent threshold function for $D\sim\mathcal{D}$ with probability at least $\frac{1}{4}$.
\end{lemma}

We remark that, in general, an algorithm for query release can be used to construct a private learner with similar sample complexity. Hence, Theorem~\ref{thm:lb-higher} also yields the following lower bound on the sample complexity of releasing approximated answers to queries from $\operatorname*{\tt THRESH}_X^{\ell}$.

\begin{theorem}\label{thm:query-release-lower-bound}
For every $n, \ell \in \N$, $\alpha > 0$, and $\delta \le \ell^2/(7500n^2)$, any $(\frac{1}{150}, \delta)$-differentially private algorithm for releasing approximated answers for queries from $\operatorname*{\tt THRESH}_X^{\ell}$ with $(\alpha,\frac{1}{150})$-accuracy must have sample complexity $n=\Omega(\frac{\ell}{\alpha}\log^*|X|)$.
\end{theorem}

In order to prove the above theorem we use our lower bound on privately learning $\operatorname*{\tt THRESH}_X^{\ell}$ together with the following reduction from private learning to query release.

\begin{lemma}[\cite{GuptaHaRoUl11,BeimelNiSt13b}]\label{lem:sanitization-implies-PPAC}
Let $C$ be a class of predicates.
If there exists a $(\frac{1}{150},\delta)$-differentially private algorithm capable of releasing queries from $C$ with $(\frac{1}{150},\frac{1}{150})$-accuracy and sample complexity $n$, then there exists a $(\frac{1}{5},5\delta)$-differentially private $(\frac{1}{5},\frac{1}{5})$-accurate PAC learner for $C$ with sample complexity $O(n)$.
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{thm:query-release-lower-bound}]
Let $\delta\leq\ell^2/(7500n^2)$.
Combining our lower bound on the sample complexity of privately learning $\operatorname*{\tt THRESH}_X^{\ell}$ (Theorem~\ref{thm:lb-higher}) together with the reduction stated in Lemma~\ref{lem:sanitization-implies-PPAC}, we get a lower bound of $m\triangleq\Omega(\ell\cdot\log^*|X|)$ on the sample complexity of every $(\frac{1}{150},\delta)$-differentially private algorithm for releasing queries from $\operatorname*{\tt THRESH}_X^{\ell}$ with $(\frac{1}{150},\frac{1}{150})$-accuracy.

In order to refine this argument and get a bound that incorporates the approximation parameter, let $\alpha\leq1/150$, and assume towards contradiction that there exists a $(\frac{1}{150},\delta)$-differentially private algorithm $\tilde{\mathcal{A}}$ for releasing queries from $\operatorname*{\tt THRESH}_X^{\ell}$ with $(\alpha,\frac{1}{150})$-accuracy and sample complexity $n < m/(150\alpha)$.

We will derive a contradiction by using $\tilde{\mathcal{A}}$ in order to construct a $(\frac{1}{150},\frac{1}{150})$-accurate algorithm for releasing queries from $\operatorname*{\tt THRESH}_X^{\ell}$ with sample complexity less than $m$.
Consider the algorithm $\mathcal{A}$ that on input a database $D$ of size $150\alpha n$, applies $\tilde{\mathcal{A}}$ on a database $\tilde{D}$ containing the elements in $D$ together with $(1-150\alpha)n$ copies of $(\min X)$. Afterwards, algorithm $\mathcal{A}$ answers every query $c\in\operatorname*{\tt THRESH}_X^{\ell}$ with $a_c \triangleq \frac{1}{150\alpha}(\tilde{a_c} - 1 + 150\alpha)$, where $\{\tilde{a_c}\}$ are the answers received from $\tilde{\mathcal{A}}$.

Note that as $\tilde{\mathcal{A}}$ is $(\frac{1}{150},\delta)$-differentially private, so is $\mathcal{A}$.
We now show that $\mathcal{A}$'s output is $\frac{1}{150}$-accurate for $D$ whenever $\tilde{\mathcal{A}}$'s output is $\alpha$-accurate for $\tilde{D}$, which happens with all but probability $\frac{1}{150}$.
Fix a query $c\in\operatorname*{\tt THRESH}_X^{\ell}$ and assume that $c(D)=t/(150\alpha n)$. Note that $c(\min X)=1$, and hence, $c(\tilde{D})=t/n + (1 - 150\alpha)$. By the utility properties of $\tilde{\mathcal{A}}$,
\begin{eqnarray*}
a_c &=& \frac{1}{150\alpha}(\tilde{a_c} - 1 + 150\alpha) \\
&\leq& \frac{1}{150\alpha}(c(\tilde{D}) + \alpha - 1 + 150\alpha) \\
&=& \frac{1}{150\alpha}(t/n + \alpha)\\
&=& t/(150\alpha n) + 1/150\\
&=& c(D)+1/150.
\end{eqnarray*}
Similar arguments show that $a_c\geq c(D) - 1/150$, proving that $\mathcal{A}$ is $(1/150,1/150)$-accurate and contradicting the lower bound on the sample complexity of such algorithms.
\end{proof}

}

\stocrm{

\section{Mechanism-Dependent Lower Bounds}

\subsection{The Undominated Point Problem}

By a reduction to the interior point problem problem, we can prove an impossibility result for the problem of privately outputting something that is at least the minimum of a database on an unbounded domain. Specifically, we show

\begin{theorem} \label{thm:half-range}
For every (infinite) totally ordered domain $X$ with no maximum element (e.g., $X=\N$) and every $n\in\N$, there is no $(\varepsilon, \delta)$-differentially private mechanism
$M:X^n\rightarrow X$ such that for every $x=(x_1,\ldots,x_n)\in X^n$,
$$\Pr[M(x)\geq\min_i x_i]\geq2/3.$$
\end{theorem}

Besides being a natural relaxation of the interior point problem, this \emph{undominated point problem} is of interest because we require new techniques to obtain lower bounds against it. Note that if we ask for a mechanism that works over a bounded domain (e.g., $[0,1]$), then the problem is trivial. Moreover, this means that proving a lower bound on the problem when the domain is $\N$ cannot possibly go by way of constructing a single distribution that every differentially private mechanism fails on. The reason is that for any distribution $\mathcal{D}$ over $\N^n$, there is some number $K$ where $\Pr_{D \gets_{\mbox{\tiny R}} \mathcal{D}}[\max{D} > K] \le 2/3$, so the mechanism that always outputs $K$ solves the problem.

\begin{proof}
Without loss of generality we may take $X=\N$, since every totally ordered domain with no maximum element contains an infinite sequence $x_0<x_1<x_2<x_3<\dots$.
To prove our lower bound we need to take advantage of the fact that we only need to show that for each differentially private mechanism $M$ there exists a distribution, depending on $M$, over which $M$ fails. To this end, for an increasing function $T:\N \to \N$, we say that a mechanism $M:\N^n \to \N$ is ``$T$-bounded'' if $\Pr[M(x_1,\dots,x_n) \ge T(\max_i x_i)] < 1/8$. That is, $M$ is $T$-bounded if it is unlikely to output anything larger than $T$ applied to the max of its input. Note that any mechanism is $T$-bounded for some function $T$.

We can then reduce the impossibility of the undominated point problem for $T$-bounded mechanisms to our lower bound for the interior point problem. First, fix a function $T$. Suppose for the sake of contradiction that there were a $T$-bounded mechanism $M$ that solves the undominated point problem on $(x_1,\dots,x_n)$ with probability at least $7/8$. Then by a union bound, $M$ must output something in the interval $[\min_i x_i, T(\max_i x_i))$ with probability at least $3/4$. Now, for $d\in\N$, consider the data universe $X_d=\{ 1, T(1), T(T(1)), T(T(T(1))), \dots, T^{(d-1)}(1)  \}$ and the differentially private mechanism $M':X_d^n\rightarrow X_d$ that, on input a database $D$ runs $M(D)$ and rounds the answer down to the nearest $T^i(d)$. Then $M'$  solves the interior point problem on the domain $X_d$ with probability at least $3/4$. By our lower bound for the interior point problem we have $n = \Omega(\log^* d)$, which is a contradiction since $n$ is fixed and $d$ is arbitrary.

\end{proof}
}

\stocrm{
\subsection{Properly Learning Point Functions with Pure Differential Privacy}

Using similar ideas as in the above section, we revisit the problem of privately learning the concept class $\operatorname{\tt POINT}_{\N}$ of point functions over the natural numbers. Recall that a point function $c_x$ is defined by $c_x(y) = 1$ if $x = y$ and evaluates to $0$ otherwise. Beimel et al. \cite{BeimelKaNi10} used a packing argument to show that $\operatorname{\tt POINT}_{\N}$ cannot be properly learned with {\em pure} $\varepsilon$-differential privacy (i.e., $\delta{=}0$). However, more recent work of Beimel et al. \cite{BeimelNiSt13a} exhibited an $\varepsilon$-differentially private \emph{improper} learner for $\operatorname{\tt POINT}_{\N}$ with sample complexity $O(1)$. Their construction required an uncountable hypothesis class, with each concept being described by a real number. This left open the question of whether $\operatorname{\tt POINT}_{\N}$ could be learned with a countable hypothesis class, with each concept having a finite description length.

We resolve this question in the negative. Specifically, we show that it is impossible to learn (even improperly) point functions over an infinite domain with pure differential privacy using a countable hypothesis class.

\begin{theorem} \label{thm:points}
Let $X$ be an infinite domain, let $H$ be a countable collection of hypotheses $\{h : X \to \{0, 1\}\}$, and let $\varepsilon\geq 0$. Then there is no $\varepsilon$-differentially private $(1/3, 1/3)$-accurate PAC learner for points over $X$ using the hypothesis class $H$.
\end{theorem}

\begin{remark}
A learner implemented by an algorithm (i.e. a probabilistic Turing machine) must use a hypothesis class where each hypothesis has a finite description. Note that the standard proper learner for $\operatorname{\tt POINT}_X$ can be implemented by an algorithm. However, a consequence of our result is that there is no algorithm for privately learning $\operatorname{\tt POINT}_X$.
\end{remark}

\begin{proof}
For clarity, and without loss of generality, we assume that $X=\N$.
Suppose for the sake of contradiction that we had an $\varepsilon$-differentially private learner $M$ for point functions over $\N$ using hypothesis class $H$. Since $H$ is countable, there is a finite subset of hypotheses $H'$ such that $M((0, 1)^n) \in H'$ with probability at least $5/6$, where $(0, 1)^n$ is the dataset where all examples are the point $0$ with the label $1$. Indeed
$\sum_{h\in H}\Pr[M((0, 1)^n)=h]=1$, so some finite partial sum of this series is at least $5/6$.
Now to each point $x \in \N$ we will associate a distribution $\mathcal{D}_x$ on $\N$ and let $G_x \subseteq H'$ be the set of hypotheses $h$ \emph{in the finite set $H'$} for which
\[\Pr_{y \sim \mathcal{D}_x}[c_x(y) = h(y)] \ge 2/3.\]
We establish the following claim.
\begin{claim} \label{claim:disjoint-good-hyp}
There is an infinite sequence of points $x_1,x_2,x_3,\dots$ together with distributions $\mathcal{D}_i := \mathcal{D}_{x_i}$ such that the sets $G_i := G_{x_i}$ are all disjoint.
\end{claim}
Given the claim, the result follows by a packing argument \cite{HardtTa10, BeimelKaNi10}. By the utility of $M$, for each $\mathcal{D}_i$ there is a database $R_i \in (\N \times \{0, 1\})^n$ in the support of $\mathcal{D}_i^n$ such that $\Pr[M(R_i) \in G_i] \ge 2/3 - 1/6 = 1/2$. By changing the database $R_i$ to $(0, 1)^n$ one row at a time while applying the differential privacy constraint, we see that
\[\Pr[M((0, 1)^n) \in G_i] \ge \frac{1}{2}e^{-\varepsilon n}.\]
It is impossible for this to hold for infinitely many disjoint sets $G_i$.
\end{proof}

\begin{proof}[Proof of Claim \ref{claim:disjoint-good-hyp}]
We inductively construct the sequence $(x_i)$, starting with $x_1 = 0$. Now suppose we have constructed $x_1, \dots, x_i$ with corresponding good hypothesis sets $G_1, \dots, G_i$. Let $B = \cup_{j = 1}^i G_i$ be the set of hypotheses with wish to avoid. Note that $B$ is a finite set of hypotheses, so there are some $x, x' \in \N$ for which every $h \in B$ with $h(x) = 1$ also has $h(x') = 1$. Let $x_{i+1} = x$ and $\mathcal{D}_{i}$ be distributed uniformly over $x$ and $x'$. Then for every hypothesis $h \in B$,
\[\Pr_{y \sim D_i}[c_{x_{i+1}}(y) = h(y)] \le 1/2,\]
and hence $G_{i+1}$ is disjoint from the preceding $G_j$'s.
\end{proof}
}

\paragraph{Acknowledgments.} We thank Amos Beimel, Adam Smith, \stoctext{and} Jonathan Ullman\stocrm{, and anonymous reviewers} for helpful conversations and suggestions that helped guide our work. We also thank Gautam Kamath for pointing us to references on distribution learning.

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv