List and Certificate Complexities in Replicable Learning

Let $\mathcal{P}$ be a $(d+1,\frac{1}{2d})$-secluded partition from Theorem 3.2 and $f:\mathbb{R}^{d}\to\mathbb{R}^{d}$ the associated deterministic rounding function due to Observation 3.4 The partition $\mathcal{P}$ consists of translates of the unit cube $[0,1)^{d}$ with the property that for any point $\vec{p}\in\mathbb{R}^{d}$ the closed cube of side length $1/d$ centered at $\vec{p}$ (i.e. $\overline{B}_{1/2d}^{\infty}(\vec{p})$) intersects at most $d+1$ members/cubes in $\mathcal{P}$. The associated rounding function $f:\mathbb{R}^{d}\to\mathbb{R}^{d}$ maps each point of $\mathbb{R}^{d}$ to the center point of the unique cube in $\mathcal{P}$ which contains it. This means $f$ has the following two properties (which are closely connected to the two properties we want of $f_{\epsilon}$): (1) for every $a\in\mathbb{R}^{d}$, $\lVert f(a)-a\rVert_{\infty}\leq\frac{1}{2}$ (because every point is mapped to the center of its containing unit cube) and (2) for any point $p\in\mathbb{R}^{d}$, the set $\left\{f(a)\colon a\in\overline{B}_{1/2d}^{\infty}(p)\right\}$ has cardinality at most $d+1$ (because $\overline{B}_{1/2d}^{\infty}(p)$ intersects at most $d+1$ members of $\mathcal{P}$). Define $f_{\epsilon}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ by $f_{\epsilon}(a)=\epsilon\cdot f(\frac{1}{\epsilon}a)$. The efficient computability of $f_{\epsilon}$ comes from the efficient computability of $f$ (i.e. the ability to efficiently compute the center of the unit cube in $\mathcal{P}$ which contains a given point).

To see that $f_{\epsilon}$ has property (1), let $x\in\mathbb{R}^{d}$ and $\hat{x}\in\overline{B}_{\epsilon_{0}}^{\infty}(x)$. Then we have the following (justifications will follow):

The first line is by the definition of $f_{\epsilon}$, the second is the triangle inequality, the third is scaling of norms, the fourth uses the property of $f$ that points are not mapped a distance more than $\frac{1}{2}$ along with the hypothesis that $\hat{x}\in\overline{B}_{\epsilon_{0}}^{\infty}(x)$, the fifth uses the definition of $\epsilon_{0}$, and the sixth uses the fact that $d\geq 1$.

Scaling both sides by $\epsilon$ and using the scaling of norms, the above gives us $\left\lVert f_{\epsilon}(\hat{x})-x\right\rVert_{\infty}\leq\epsilon$ which proves property (1) of the lemma.

To see that $f_{\epsilon}$ has property (2), let $x\in\mathbb{R}^{d}$. We have the following set of equalities:

The first line is from the definition of $f_{\epsilon}$, the second is from re-scaling, and the third is from the definition of $\epsilon_{0}$.

Because $f$ takes on at most $d+1$ distinct values on $\overline{B}_{\tfrac{1}{2d}}^{\infty}(x)$, the set has cardinality at most $d+1$ which proves property (2) of the lemma. ∎

Partition each coordinate of $\mathbb{R}^{d}$ into $2\varepsilon_{0}$-width intervals. The algorithm computing the function $f$ does the following simple randomized rounding:

The function $f:$ Choose a random integer $r\in\{1\dots 2^{\ell}\}$. Note that $r$ can be represented using $\ell$ bits. Consider the $i^{th}$ coordinate of ${\hat{x}}$ denoted by ${\hat{x}[i]}$. Round $\hat{x}[i]$ to the nearest $k*(2\varepsilon_{0})$ such that $k\mod 2^{\ell}\equiv r$.

Now we will prove that $f$ satisfies the required properties.

First, we prove the approximation guarantee. Let ${x^{\prime}}$ denote the point in $\mathbb{R}^{d}$ obtained after rounding each coordinate of $\hat{x}$. The $k$s satisfying $k\mod 2^{\ell}\equiv r$ are $2^{\ell}\cdot 2\varepsilon_{0}$ apart. Therefore, ${x^{\prime}}[i]$ is rounded by at most $2^{\ell}\epsilon_{0}$. That is, $|{x^{\prime}}[i]-\hat{x}[i]|\leq 2^{\ell}\epsilon_{0}={\varepsilon_{0}d\over\delta}$ for every $i$, $1\leq i\leq d$. Since $\hat{x}$ is an $\varepsilon_{0}$-approximation (i.e. each coordinate $\hat{x}[i]$ is within $\varepsilon_{0}$ of the true value $x[i]$), then each coordinate of ${x^{\prime}}$ is within $(2^{\ell}+1)\varepsilon_{0}$ of $x[i]$. Therefore ${x^{\prime}}$ is a $(2^{\ell}+1)\varepsilon_{0}$-approximation of $x[i]$. Thus $x^{\prime}\in\overline{B}_{\varepsilon}^{\infty}(x)$ for any choice of $r$.

Now we establish that for $\geq 1-\delta$ fraction of $r\in\{1\ldots 2^{\ell}\}$, there exists $x^{*}$ such every $\hat{x}\in\overline{B}_{\varepsilon_{0}}^{\infty}(x)$ is rounded $x^{*}$. We argue this with respect to each coordinate and apply the union bound. Fix an $x$ and a coordinate $i$. For $x[i]$, consider the $\varepsilon_{0}$ interval around it.

Consider $r$ from $\{1\ldots 2^{\ell}\}$. When this $r$ is chosen, then we round $\hat{x}[i]$ to the closest $k*(2\varepsilon_{0})$ such that $k\mod 2^{\ell}\equiv r$. Let $p^{r}_{1},p^{r}_{2},\ldots p^{r}_{j}\ldots$ be the set of such points: more precisely $p_{j}=(j2^{l}+r)*2\varepsilon_{0}$. Note that $\hat{x}[i]$ is rounded to an $p_{j}$ to some $j$. Let $m^{r}_{j}$ denote the midpoint between $p^{r}_{j}$ and $p^{r}_{j+1}$. I.e, $m^{r}=(p^{r}_{j}+p^{r}_{j+1})/2$ We call $r$ ‘bad’ for $x[i]$ if $x[i]$ is close to some $m^{r}_{j}$. That is, $r$ is ‘bad’ if $|x[i]-m^{r}_{j}|<\varepsilon_{0}$. Note that for a bad $r$ there exists $\hat{x_{1}}$ and $\hat{x_{2}}$ in $\overline{B}_{\varepsilon_{0}}^{\infty}(x)$ so that their $i^{th}$ coordinates are round to $p^{r}_{j}$ and $p^{r}_{j+1}$ respectively. The crucial point is that if $r$ is ‘not bad’ for $x[i]$, then for every $x^{\prime}\in\overline{B}_{\varepsilon_{0}}^{\infty}(x)$, there exists a canonical $p^{*}$ such that $x^{\prime}[i]$ is rounded to $p^{*}$. We call $r$ bad for $x$, if $r$ is bad for $x$, if there exists at least one $i$, $1\leq i\leq d$ such that $r$ is bad for $x[i]$. With this, it follows that if $r$ is not bad for $x$, then there exists a canonical $x^{*}$ such that every $x^{\prime}\in\overline{B}_{\varepsilon_{0}}^{\infty}(x)$ is rounded to $x^{*}$.

With this, the goal is to bound the probability that a randomly chosen $r$ is bad for $x$. For this, we first bound the probability that $r$ is bad for $x[i]$. We will argue that there exists almost one bad $r$ for $x[i]$. Suppose that there exist two numbers $r_{1}$ and $r_{2}$ that are both bad for $x[i]$. This means that $|x[i]-m^{r_{1}}_{j_{1}}|<\varepsilon_{0}$ and $|x[i]-m^{r_{2}}_{j_{2}}|<\varepsilon_{0}$ for some $j_{1}$ and $j_{2}$. Thus by triangle inequality $|m^{r_{1}}_{j_{1}}-m^{r_{2}}_{j_{2}}|<2\varepsilon_{0}$. However, note that $|p^{r_{1}}_{j_{1}}-p^{r_{2}}_{j_{2}}|$ is $|(j_{1}-j_{2})2^{\ell}+(r_{1}-r_{2})|2\epsilon_{0}$. Since $r_{1}\neq r_{2}$, this value is at least $2\varepsilon_{0}$. This implies that the absolute value of difference between $m^{r_{1}}_{j_{1}}$ and $m^{r_{2}}_{j_{2}}$ is at least $2\varepsilon$ leading to a contradiction.

Thus the probability that $r$ is bad for $x[i]$ is atmost $\frac{1}{2^{\ell}}$ and by the union bound the probability that $r$ is bad for $x$ is atmost $\frac{d}{2^{\ell}}\leq\delta$. This completes the proof. ∎

Note that when $\varepsilon\geq 1/2$, a trivial algorithm that outputs a vector with $1/2$ in each component works. Thus the most interesting case is when $\varepsilon<1/2$. Our list replicable algorithm is described in Algorithm 1.

So we will prove its correctness by giving for each possible bias $\vec{b}\in[0,1]^{d}$, a set $L_{\vec{b}}$ with the three necessary properties: (1) $\lvert L_{\vec{b}}\rvert\leq d+1$, (2) $L_{\vec{b}}\subseteq\overline{B}_{\epsilon}^{\infty}(\vec{b})$ (and also the problem specific restriction that $L_{\vec{b}}\subseteq[0,1]^{d}$), and (3) when given access to coins of biases $\vec{b}$, with probability at least $1-\delta$ the algorithm returns a value in $L_{\vec{b}}$.

Assume notation from Algorithm 1. Let $L_{\vec{b}}=\left\{g(f_{\epsilon}(\vec{x}))\colon\vec{x}\in\overline{B}_{\epsilon_{0}}^{\infty}(\vec{b})\right\}$. By 3.5, $f_{\epsilon}$ takes on at most $d+1$ values on $\overline{B}_{\epsilon_{0}}^{\infty}(\vec{b})$ (which means $g\circ f_{\epsilon}$ also takes on at most $d+1$ values on this ball) which proves that $\lvert L_{\vec{b}}\rvert\leq d+1$. This proves property (1).

NExt we state the following ibservation which says that the coordinate restriction function $g$ of Algorithm 1 does not reduce approximation quality. The proof is relatively straightforward, but tedious.

We can view the model as algorithm $A$ having access to a single draw from a distribution. The distribution giving one sample flip of each coin in a collection with bias $\vec{b}$ is the $d$-fold product of Bernoulli distributions $\prod_{i=1}^{d}\operatorname{Bern}(b_{i})$ (which for notational brevity we denote as $\operatorname{Bern}(\vec{b}$), so the distribution which gives $n$ independent flips of each coin is the $n$-fold product of this (using notation of [Can15] written as $\operatorname{Bern}(\vec{b})^{\otimes n}$).

Comparing the distributions of $n$ independent flips of the $d$ coins for bias $\vec{b}$ as compared to bias $\vec{a}$, we have for each $i\in[d]$ that

so by C.1.2 and C.1.3 of [Can15] we have

and

Because $A$ is a randomized function of one draw of this distribution, by D.1.2 of [Can15] we have that $A$ cannot serve to increase the total variation distance, so

which completes the proof. ∎

Fix any $d\in\mathbb{N}$, and choose $\epsilon$ and $\delta$ as $\epsilon<\frac{1}{2}$ and $\delta\leq\frac{1}{d+2}$.

Suppose for contradiction that such an algorithm $A$ does exists for some $k<d+1$. This means that for each possible threshold $\vec{t}\in[0,1]^{d}$, there exists some set $L_{\vec{t}}\subseteq\mathcal{H}$ of hypotheses with three properties: (1) each element of $L_{\vec{t}}$ is an $\epsilon$-approximation to $h_{\vec{t}}$, (2) $\lvert L_{\vec{t}}\rvert\leq k$, and (3) with probability at least $1-\delta$, $A$ returns an element of $L_{\vec{t}}$.

Suppose for contradiction that such an algorithm does exist for some $k<d+1$. This means that for each possible bias $\vec{b}\in[0,1]^{d}$, there exists some set $L_{\vec{b}}\subseteq\overline{B}_{\epsilon}^{\infty}(\vec{b})$ (not necessarily unique, but consider some fixed one) with $\lvert L_{\vec{b}}\rvert\leq k$ such that with probability at least least $\frac{1}{k}\cdot(1-\delta)\geq\frac{1}{k}\cdot(1-\frac{1}{d+2})=\frac{1}{k}\cdot\frac{d+1}{d+2}\geq\frac{1}{k}\cdot\frac{k+1}{k+2}$, $A$ returns an element of $L_{\vec{b}}$. By the trivial averaging argument, this means that there exists at least one element in $L_{\vec{b}}$ which is returned by $A$ with probability at least $\frac{1}{k}\cdot\frac{k+1}{k+2}$. Let $f\colon[0,1]^{d}\to[0,1]^{d}$ be a function which maps each bias $\vec{b}$ to such an element of $L_{\vec{b}}$.

Since $\frac{1}{k}\cdot\frac{k+1}{k+2}>\frac{1}{k+1}$, let $\eta$ be such that $0<\eta<\frac{1}{k}\cdot\frac{k+1}{k+2}-\frac{1}{k+1}$.

The function $f$ induces a partition $\mathcal{P}$ of $[0,1]^{d}$ where the members of $\mathcal{P}$ are the fibers of $f$ (i.e. $\mathcal{P}=\left\{f^{-1}(\vec{y})\colon\vec{y}\in\operatorname{range}(f)\right\}$). By definition, for any member $X\in\mathcal{P}$ there exists some $\vec{y}\in\operatorname{range}{f}$ such that for all $\vec{b}\in X$, $f(\vec{b})=\vec{y}$. By definition of $k$-pseudodeterministic $\epsilon$-approximation, we have $f(\vec{b})\in L_{\vec{b}}\subseteq\overline{B}_{\epsilon}^{\infty}(\vec{b})$ showing that $\vec{y}\in\overline{B}_{\epsilon}^{\infty}(\vec{b})$ and by symmetry $\vec{b}\in\overline{B}_{\epsilon}^{\infty}(\vec{y})$. This shows that $X\subseteq\overline{B}_{\epsilon}^{\infty}(\vec{y})$, so $\operatorname{diam}_{\infty}(X)\leq 2\epsilon<1$.

Let $r=\frac{\eta\cdot d}{n}$. Since every member of $\mathcal{P}$ has $\ell_{\infty}$ diameter less than $1$, by 3.7 there exists a point $\vec{p}\in[0,1]^{d}$ such that $\overline{B}_{r}^{\infty}(\vec{p})$ intersects at least $d+1>k$ members of $\mathcal{P}$. Let $\vec{b}^{(1)},\ldots,\vec{b}^{(d+1)}$ be points belonging to distinct members of $\mathcal{P}$ that all belong to $\overline{B}_{r}^{\infty}(\vec{p})$. By definition of $\mathcal{P}$, this means for distinct $j,j^{\prime}\in[d+1]$ that $f(\vec{b}^{(j)})\not=f(\vec{b}^{(j^{\prime})})$.