Concentration inequalities for sampling without replacement

Introduction

Few results exist on the concentration properties of sampling without replacement from a finite population $\mathcal{X}$. However, potential applications are numerous, from historical applications such as opinion surveys (Kish ) and ecological counting procedures (Bailey ), to more recent approximate Monte Carlo Markov chain algorithms that use subsampled likelihoods (Bardenet, Doucet and Holmes ). In a fundamental paper on sampling without replacement, Serfling introduced an efficient Hoeffding bound, that is, one which is a function of the range of the population. Bernstein bounds are typically tighter when the variance of the random variable under consideration is small, as their leading term is linear in the standard deviation of $\mathcal{X}$, while the range only influences higher-order terms. This paper is devoted to Hoeffding and Bernstein bounds for sampling without replacement.

Let $\mathcal{X}=(x_{1},\dots,x_{N})$ be a finite population of $N$ real points. We use capital letters to denote random variables on $\mathcal{X}$, and lower-case letters for their possible values. Sampling without replacement a list $(X_{1},\dots,X_{n})$ of size $n$ from $\mathcal{X}$ can be described sequentially as follows: let first $\mathcal{I}_{1}=\{1,\dots,n\}$, sample an integer $I_{1}$ uniformly on $\mathcal{I}_{1}$, and set $X_{1}$ to be $x_{I_{1}}$. Then, for each $i=2,\dots,n$, sample $I_{i}$ uniformly on the remaining indices $\mathcal{I}_{i}=\mathcal{I}_{i-1}\setminus\{I_{i-1}\}$. Hereafter, we assume that $N\geq 2$.

Previous work

There have been a few papers on concentration properties of sampling without replacement; see, for instance, Hoeffding , Serfling , Horvitz and Thompson , McDiarmid . One notable contribution is the following reduction result in Hoeffding’s seminal paper (Hoeffding , Theorem 4):

Lemma 1.1 implies that the concentration results known for sampling with replacement as Chernoff bounds (Boucheron, Lugosi and Massart ) can be transferred to the case of sampling without replacement. In particular, Proposition 1.2, due to Hoeffding , holds for the setting without replacement.

Let $\mathcal{X}=(x_{1},\ldots,x_{N})$ be a finite population of $N$ points and $X_{1},\ldots,X_{n}$ be a random sample drawn without replacement from $\mathcal{X}$. Let

where $\mu=\frac{1}{N}\sum_{i=1}^{N}x_{i}$ is the mean of $\mathcal{X}$.

The proof of Proposition 1.2 (see, e.g., Boucheron, Lugosi and Massart ) relies on a classical bound on the moment-generating function of a random variable, which we restate here as Lemma 1.3 for further reference.

When the variance of $\mathcal{X}$ is small compared to the range $b-a$, another Chernoff bound, known as Bernstein’s bound (Boucheron, Lugosi and Massart ), is usually tighter than Proposition 1.2.

With the notations of Proposition 1.2, let

be the variance of $\mathcal{X}$. Then, for all $\varepsilon>0$,

Although these are interesting results, it appears that the bounds in Propositions 1.2 and 1.4 are actually very conservative, especially when $n$ is large, say, $n\geq N/2$. Indeed, Serfling proved that the term $n$ in the RHS of (1) can be replaced by $\frac{n}{1-(n-1)/N}$; see Theorem 2.4 below, where the result of Serfling is restated in our notation and slightly improved. As $n$ approaches $N$, the bound of Serfling improves dramatically, which corresponds to the intuition that when sampling without replacement, the sample mean becomes a very accurate estimate of $\mu$ as $n$ approaches $N$.

Contributions and outline

In Section 2, we slightly modify Serfling’s result, yielding a Hoeffding–Serfling bound in Theorem 2.4 that dramatically improves on Hoeffding’s in Proposition 1.2. In Section 3, we contribute in Theorem 3.5 a similar improvement on Proposition 1.4, which we call a Bernstein–Serfling bound. To allow practical applications of our Bernstein–Serfling bound, we finally provide an empirical Bernstein–Serfling bound in Section 4, in the spirit of Maurer and Pontil , which does not require the variance of $\mathcal{X}$ to be known beforehand. In Section 5, we discuss direct applications and potential further improvements of our results.

Illustration

A reminder of Serfling’s fundamental result

In this section, we recall an initial result and proof by Serfling , and slightly improve on his final bound.

We start by identifying the following martingales structures. Let us introduce, for $1\leq k\leq N$,

Note that by definition $Z_{N}=0$, so that the $\sigma$-algebra $\sigma(Z_{k+1},\ldots,Z_{N})$ is equal to $\sigma(Z_{k+1},\ldots,\allowbreak Z_{N-1})$.

The following forward martingale structure holds for $\{Z_{k}^{\star}\}_{k\leq N}$:

Similarly, the following reverse martingale structure holds for $\{Z_{k}\}_{k\leq N}$:

We first prove (3). Let $1\leq k\leq N$. We start by noting that

Since $X_{k}$ is uniformly distributed on the remaining elements of $\mathcal{X}$ after $X_{1},\ldots,X_{k-1}$ have been drawn, its conditional expectation given $X_{1},\ldots,X_{k-1}$ is the average of the $N-k+1$ remaining points in $\mathcal{X}$. Since points in $\mathcal{X}$ add up to $N\mu$, we obtain

We now turn to proving (4). First, let $1\leq k\leq N$. Since

$\sigma(Z_{k+1},\ldots,Z_{N-1})$ is equal to $\sigma(X_{k+2},\ldots,X_{N})$. Now, let us remark that the indices of $(X_{1},\ldots,X_{N})$ are uniformly distributed on the permutations of $\{1,\ldots,N\}$, so that $(X_{1},\ldots,\allowbreak X_{N-k})$ and $(X_{k+1},\ldots,X_{N})$ have the same marginal distribution. Consequently,

where we introduced the sum $S_{k+1}=\sum_{t=1}^{k+1}X_{t}$. Finally, we prove (4) along the same lines as (3):

Let us now state the main result of Serfling . This is a key result to derive a concentration inequality, a maximal concentration inequality and a self-normalized concentration inequality, as explained in Serfling .

Let us denote $a=\min_{1\leq i\leq N}x_{i}$, and $b=\max_{1\leq i\leq N}x_{i}$. Then, for any $\lambda>0$, it holds that

Moreover, for any $\lambda>0$, it also holds that

First, (2) yields that for all $\lambda^{\prime}>0$,

Furthermore, we know from (2) that $-Z_{k-1}^{\star}$ is the conditional expectation of $X_{k}-\mu$ given $X_{1},\ldots,X_{k-1}$. Thus, since $X_{k}-\mu\in[a-\mu,b-\mu]$, Lemma 1.3 applies and we get that, for all $2\leq k\leq n$,

Similarly, we can apply Lemma 1.3 to $Z_{1}^{\star}=(X_{1}-\mu)/(N-1)$ to obtain

Upon noting that $Z_{n}=\frac{N-n}{n}Z_{n}^{\star}$, and combining (8) and (9) together with the decomposition (7), we eventually obtain the bound

In particular, for $\lambda$ such that $\lambda^{\prime}=(N-n)\lambda$, the RHS of this equation contains the quantity

where we used in the second line the following approximation from (Serfling , Lemma 2.1): for $1\leq j\leq m$, it holds

This concludes the proof of the first result of Proposition 2.2. The second result follows from applying Doob’s maximal inequality for martingales combined with the previous derivation. ∎

The result of Proposition 2.2 reveals a powerful feature of the no replacement setting: the factor $n(1-\frac{n-1}{N})$ in the exponent, as opposed to $n$ in the case of sampling with replacement. This leads to a dramatic improvement of the bound when $n$ is large, as can be seen on Figure 1. Serfling mentioned that a factor $1-\frac{n}{N}$ would be intuitively more natural, as indeed when $n=N$ the mean $\mu$ is known exactly, so that $Z_{N}$ is deterministically zero.

Serfling did not publish any result with $1-\frac{n}{N}$. However, it appears that a careful examination of the previous proof and of the use of equation (4), in lieu of (3), allows us to get such an improvement. We detail this in the following proposition. More than a simple cosmetic modification, it is actually a slight improvement on Serfling’s original result when $n>N/2$.

Let $(Z_{k})$ be defined by (2). For any $\lambda>0$, it holds that

Moreover, for any $\lambda>0$, it also holds that

Let us introduce the notation $Y_{k}=Z_{N-k}$ for $1\leq k\leq N-1$. From (4), it comes

By a change of variables, this can be rewritten as

Now we remark that the following decomposition holds:

Since $Y_{k-1}$ is the conditional mean of $X_{N-k+1}-\mu\in[a-\mu,b-\mu]$, Lemma 1.3 yields that, for all $2\leq k\leq n$,

On the other hand it holds by definition of $Y_{1}$ that

Along the lines of the proof of Proposition 2.2, we obtain

Combining equations (12) and (13) with the decomposition (2), it comes

where in the last line we made use of (2). Rewriting this inequality in terms of $Z$, we obtain that, for all $1\leq n\leq N-1$,

that is, by resorting to a new change of variable,

The second part of the proposition follows from applying Doob’s maximal inequality for martingales to $Y_{n}$, similarly to Proposition 2.2. ∎

Let $\mathcal{X}=(x_{1},\ldots,x_{N})$ be a finite population of $N>1$ real points, and $(X_{1},\ldots,X_{n})$ be a list of size $n<N$ sampled without replacement from $\mathcal{X}$. Then for all $\varepsilon>0$, the following concentration bounds hold

where $a=\min_{1\leq i\leq N}x_{i}$ and $b=\max_{1\leq i\leq N}x_{i}$.

Applying Proposition 2.3 together with Markov’s inequality, we obtain that, for all $\lambda>0$,

We now optimize the previous bound in $\lambda$. The optimal value is given by

This gives the first inequality of Theorem 2.4. The proof of the second inequality follows the very same lines. ∎

Inverting the result of Theorem 2.4 for $n<N$ and remarking that the resulting bound still holds for $n=N$, we straightforwardly obtain the following result.

For all $n\leq N$, for all $\delta\in$, with probability higher than $1-\delta$, it holds

A Bernstein–Serfling inequality

In this section, we consider $\sigma^{2}=N^{-1}\sum_{i=1}^{N}(x_{i}-\mu)^{2}$ is known, and extend Theorem 2.4 to that situation.

Similarly to Lemma 2.1, the following structural lemma will be useful:

where the $Z_{i}$’s are defined in (2). Similarly, it holds

We simply remark again that, conditionally on $X_{1},\ldots,X_{k-1}$, the variable $X_{k}$ is distributed uniformly over the remaining points in $\mathcal{X}$, so that

The second equality of Lemma 3.1 follows from the same argument, as in the proof of Lemma 2.1. ∎

Let us now introduce the following notations:

We are now ready to state Proposition 3.2, which is a Bernstein version of Proposition 2.2.

The key point is to replace equations (8) and (9) in the proof of Proposition 2.2, which make use of the range of $\mathcal{X}$, by equivalent ones that involve the variance. We only detail the proof of the first inequality, the proof of the three others follows the same steps.

A standard result from the proof of Bennett’s inequality (see Lugosi , page 11, or Boucheron, Lugosi and Massart , proof of Theorem 2.9) applied to the random variable $X_{N-k+1}-\mu$, with conditional mean $\mu_{<,N-k+1}$ and conditional variance $\sigma_{<,N-k+1}^{2}$, yields

where we used the notation $Y_{k}=Z_{N-k}$ of Proposition 2.3, and the function $\varphi$ defined in the statement of the proposition

where $\sigma_{<,N}^{2}=\sigma^{2}$ is deterministic.

Thus, combining (3) and (16) together with the decomposition (2), we eventually get the bound

Using the result of Proposition 3.2, we could immediately derive a simple Bernstein inequality for sampling without replacement via an application of Theorem 2.4 to the random variables $Z_{i}=(X_{i}-\mu)^{2}$. However, Maurer and Pontil and Audibert, Munos and Szepesvári showed that, in the case of sampling with replacement, a careful use of self-bounded properties of the variance yields better bounds. We now explain how to get a similar improvement on the naive Bernstein inequality in the case of sampling without replacement. We start with a technical lemma.

For all $\delta\in$, with probability larger than $1-\delta$, it holds

Similarly, with probability larger than $1-\delta$, it holds

When $N\to\infty$, the upper bound on $\max_{1\leq k\leq n}\sigma_{>,k}^{2}$ reduces to $\sigma^{2}$. Indeed, this limit case intuitively corresponds to sampling with replacement, for which the conditional variance equals $\sigma^{2}$.

Proof of Lemma 3.3 We first prove (17). By definition and Lemma 3.1, it holds that

Let $V_{k-1}=\frac{1}{k-1}\sum_{i=1}^{k-1}(X_{i}-\mu)^{2}$. Equation (3) yields

The rest of the proof proceeds by establishing a suitable maximal concentration bound for the quantity $V_{k-1}$, the mean of which is $\sigma^{2}$.

We remark that $-Q_{k-1}^{\star}=\frac{k-1}{N-k+1}(\sigma^{2}-V_{k-1})$ is a martingale. Indeed, it satisfies

where we applied Lemma 3.1 in the third line. Doob’s maximal inequality thus yields that, for all $\lambda>0$,

At this point, we fix $\lambda>0$ and apply Lemma 1.1 to the random variables $X^{\prime}_{i}=(X_{i}-\mu)^{2}$ and function $f\mathchoice{\nobreak\,\colon}{\nobreak\,\colon}{\nobreak\,\colon\;}{\nobreak\,\colon\;}x\to\exp(-\lambda(n-1)x)$. We deduce that, for all $\varepsilon^{\prime}>0$ and $\lambda>0$,

Now, we check that the assumptions of Theorem 13 of Maurer hold. We first introduce the modification

and, on the other hand, that the following self-bounded property holds:

Finally, we have proven that for all $\delta\in$, with probability higher than $1-\delta$,

We now turn to proving (18). First, we remark that

where in the second line we used that $Z_{k+1}=\mu-X_{N}-\cdots-X_{k+2}$, and in the third line we used the change of variables $Y_{u}=X_{N-u+1}$. It follows that

Now $(Y_{1},\ldots,Y_{N-n})$ has the same marginal distribution as $(X_{1},\ldots,X_{N-n})$, so that the proof of (17) applies and yields the result.

We emphasize that we used Hoeffding’s reduction Lemma 1.1 in the proof of Lemma 3.3. This allowed us to apply the key result from Maurer . We will discuss alternatives to this proof in Section 5. We can now state our Bernstein–Serfling bound.

Let $\mathcal{X}=(x_{1},\ldots,x_{N})$ be a finite population of $N>1$ real points, and $(X_{1},\ldots,X_{n})$ be a list of size $n<N$ sampled without replacement from $\mathcal{X}$. Then, for all $\varepsilon>0$ and $\delta\in$, the following concentration inequality holds

$c_{n}(\delta)=\sigma(b-a)\sqrt{\frac{2\log(1/\delta)}{n}}$, and $f_{n-1}=\frac{n-1}{N}$. Similarly, it holds

We first prove (22). Applying Proposition 3.2 together with Markov’s inequality, we obtain that for all $\lambda,\delta>0$,

Thus, combining equations (23) and (18) with a union bound, we get that for all $\lambda>0$ for all $\delta,\delta^{\prime}$, with probability higher than $1-\delta-\delta^{\prime}$, it holds that

where we used in the second line the fact that $\varphi$ is nondecreasing and where we applied (2) in the last line. For convenience, let us now introduce the quantities $f_{n}=\frac{n}{N}$ and

The previous bound can be rewritten in terms of $\varepsilon>0$ and $\delta^{\prime}$ only, in the form

We now optimize the bound (24) in $\lambda$. Let us introduce the function

corresponding to the term in brackets in (24). By definition of $\varphi$, it comes

and the value $\lambda^{\star}$ that optimizes $f$ is given by

where we introduced in the last line the function $\zeta(u)=(1+u)\log(1+u)-u$. Now, using the identify $\zeta(u)\geq u^{2}/(2+2u/3)$ for $u\geq 0$, we obtain

which concludes the proof of (22). The proof of (21) follows the very same lines, simply using (17) instead of (18). ∎

Inverting the bounds of Theorem 3.5, we obtain Corollary 3.6.

Let $n\leq N$ and $\delta\in$. With probability larger than $1-2\delta$, it holds that

where we remind the definition of $\rho_{n}$ (14)

Let $\delta,\delta^{\prime}\in$. From (21) in Theorem 3.5, it comes that, with probability higher than $1-\delta-\delta^{\prime}$,

where we introduced for convenience $B=\frac{2}{3}(b-a)$ and

Solving this equation in $\varepsilon$ leads to

On the other hand, following the same lines but starting from (22) in Theorem 3.5, it holds that, with probability higher than $1-\delta-\delta^{\prime}$,

Thus, when $n\leq N/2$, we deduce that for all $1\leq n\leq N-1$, with probability higher than $1-2\delta$, it holds

whereas when $N>n>N/2$, it holds, with probability higher than $1-2\delta$, that

Finally we note that when $n=N$, $g_{n+1}(1-f_{n})=0$ and $\rho_{n}=0$. So the bound is still satisfied. ∎

An empirical Bernstein–Serfling inequality

In this section, we derive a practical version of Theorem 3.5 where the variance $\sigma^{2}$ is replaced by an estimate. A natural (biased) estimator is given by

We also define, for notational convenience, the quantity $\widehat{\sigma}_{n}=\sqrt{\widehat{\sigma}_{n}^{2}}$.

Before proving our empirical Bernstein–Serfling inequality, we first need to control the error between $\widehat{\sigma}_{n}$ and $\sigma$. For instance, in the standard case of sampling with replacement, it can be shown (Maurer and Pontil ) that, for all $\delta\in$,

We now show an equivalent result in the case of sampling without replacement.

When sampling without replacement from a finite population $\mathcal{X}=(x_{1},\ldots,x_{N})$ of size $N$, with range $[a,b]$ and variance $\sigma^{2}$, the empirical variance $\widehat{\sigma}_{n}^{2}$ defined in (26) using $n<N$ samples satisfies the following concentration inequality (using the notation of Corollary 2.5)

We conjecture that it is possible, at the price of a more complicated analysis, to reduce the term $(1+\sqrt{1+\rho_{n}})$ to $\sqrt{4\rho_{n}}$, which would then be consistent with the analogous result for sampling with replacement in Maurer and Pontil . We further discuss this technically involved improvement in Section 5.

Proof of Lemma 4.1 In order to prove Lemma 4.1, we again use Lemma 1.1, which allows us to relate the concentration of the quantity $V_{n}=\frac{1}{n}\sum_{i=1}^{n}(X_{i}-\mu)^{2}$ to that of its equivalent

The first line results of the application of Markov’s inequality. The second line follows from the application of Lemma 1.1 to $X^{\prime}_{i}=(X_{i}-\mu)^{2}$ and $f(x)=\exp(-\lambda\frac{n}{(b-a)^{2}}x)$. The last steps are the same as in the proof of Lemma 3.3.

So far, we have shown that, with probability at least $1-\delta$,

that is, $V_{n}=(\widehat{\mu}_{n}-\mu)^{2}+\widehat{\sigma}_{n}^{2}$. In order to complete the proof, we thus resort twice to Theorem 2.4 to obtain that, with probability higher than $1-\delta$, it holds

Combining equations (27) and (28) with a union bound argument yields that, with probability at least $1-\delta$,

Eventually, combining Theorem 3.5 and Lemma 4.1 with a union bound argument, we finally deduce the following result.

Let $\mathcal{X}=(x_{1},\ldots,x_{N})$ be a finite population of $N>1$ real points, and $(X_{1},\ldots,X_{n})$ be a list of size $n\leq N$ sampled without replacement from $\mathcal{X}$. Then for all $\delta\in$, with probability larger than $1-5\delta$, it holds

where we remind the definition of $\rho_{n}$ (14)

and $\kappa=\frac{7}{3}+\frac{3}{\sqrt{2}}$.

First, Theorem 4.3 has the familiar form of Bernstein bounds. The alternative definition of $\rho_{n}$ guarantees that we get the best reduction out of the no replacement setting. In particular, when $n$ is large, the factor $(1-f_{n})$ replaces $(1-f_{n-1})$ and the corresponding factor eventually equals when $n=N$, a feature that was missing in Proposition 2.2. Second, the constant $\kappa$ is to relate to the constant $7/3$ in Maurer and Pontil , Theorem 11, for sampling with replacement.

Proof of Theorem 4.3 First, by application of Corollary 3.6, it holds for all $\delta\in$ that, with probability higher than $1-2\delta$,

where we remind the definition of $\rho_{n}$ (14)

We then apply Lemma 4.1 to get that, with probability higher than $1-5\delta$, if $n\leq N/2$, then

We now simplify this result. Assume first that $n\leq N/2$. We thus get

Assume now that $n>N/2$. In this case, it holds

Respectively combining (31) and (32) with equations (4) and (4) concludes the proof.

Discussion

In this section, we discuss the bounds of Theorem 3.5 and Theorem 4.3 from the perspective of both theory and application.

First, both bounds involve either the factor $1-f_{n-1}$ or $1-f_{n}$, thus leading to a dramatic improvement on the usual Bernstein or empirical Bernstein bounds, which do not make use of the no replacement setting. This is crucial, for instance, when the user needs to rapidly compute an empirical mean from a large number of samples up to some precision level. To better understand the improvement of Serfling bounds, we plot in Figure 2 the bounds of Corollaries 2.5 and 3.6, and Theorem 4.3 for an example where $\mathcal{X}$ is a sample of size $N=10^{6}$ from each of the following four distributions: unit centered Gaussian, log-normal with parameters $(1,1)$, and Bernoulli with parameter 1$/$10 and 1$/$2. As $n$ increases, we keep sampling without replacement from $\mathcal{X}$ until exhaustion, and report the corresponding bounds. Note that all our bounds have their leading term exactly equal to zero when $n=N$, though our Hoeffding–Serfling bound only is exactly zero. In all experiments, the loss of tightness as a result of using the empirical variance is small. Our empirical Bernstein–Serfling demonstrates here a dramatic improvement on the Hoeffding–Serfling bound of Corollary 2.5 in Figures 2(a) and 2(b). A slight improvement is demonstrated in Figure 2(c) where the standard deviation of $\mathcal{X}$ is roughly a third of the range. Finally, Bernstein–Serfling itself does not improve on Hoeffding–Serfling in Figure 2(d), where the standard deviation is roughly half of the range, again indicating that Bernstein bounds are not uniformly better than Hoeffding bounds.

There is a number of nontrivial applications of our bounds. Scratch games, for instance, were introduced in Féraud and Urvoy as a variant of the multi-armed bandit problem, to model two real world problems: selecting ads to display on web pages and optimizing e-mailing campaigns. In particular, Féraud and Urvoy discuss practical situations where an upper confidence bound algorithm based on a Hoeffding–Serfling inequality outperforms a standard algorithm based on Hoeffding’s inequality. Similar improvements should appear in practice when using our empirical Bernstein–Serfling inequality. As another application, our results could be useful in optimization. The stochastic dual-coordinate ascent algorithm (SDCA; Shalev-Shwartz and Zhang ) is a state-of-the-art optimization algorithm used in machine learning. Shalev-Shwartz and Zhang introduce a variant of SDCA called SDCA-Perm, which – unlike SDCA – relies on sampling without replacement, and achieves better empirical performance than SDCA. However, the analysis in Shalev-Shwartz and Zhang does not cover SDCA-Perm. We believe that the use of Serfling bounds is an appropriate tool for that purpose.

To conclude, we discuss potential improvements of our bounds. A careful look at Lemmas 3.3 and 4.1 indicates that our bounds may be further improved, though at the price of a more intricate analysis. Indeed, these two lemmas both resort to Hoeffding’s reduction Lemma 1.1, in order to be able to apply concentration results known for self-bounded random variables to the setting of sampling without replacement. As a result, we lose here a potential factor $\rho_{n}$ for the confidence bound around the variance, and we conjecture that the term $1+\sqrt{1+\rho_{n}}$ in Lemma 4.1 could ultimately be replaced with $2\sqrt{\rho_{n}}$. A natural tool for this would be a dedicated tensorization inequality for the entropy in the case of sampling without replacement (Boucheron, Lugosi and Massart , Maurer , Bousquet ). Indeed, it is not difficult to show that $\widehat{\sigma}_{n}^{2}$ satisfies a self-bounded property similar to that of Maurer and Pontil , Theorem 11, involving the factor $\rho_{n}$. Thus, in order to be able to get a version of Maurer and Pontil , Theorem 11, in our setting, a specific so-called tensorization inequality would be enough. Unfortunately, we are unaware of the existence of such an inequality for sampling without replacement, where the samples are strongly dependent. We are also unaware of any tensorization inequality designed for $U$-statistics, which could be another possible way to get the desired result. Although we believe this is possible, developing such tools goes beyond the scope of this paper, and the current results of Theorem 3.5 and Theorem 4.3 are already appealing without resorting to further technicalities, which would only affect second-order terms in the end.

Acknowledgements

This work was supported by both the 2020 Science program, funded by EPSRC grant number EP/I017909/1, and the Technion.

References