# Noisy Computing of the $\mathsf{OR}$
and $\mathsf{MAX}$ Functions

Banghua Zhu∗ Ziao Wang∗ Nadim Ghaddar∗ Jiantao Jiao  Lele Wang $*$ Banghua
Zhu, Ziao Wang and Nadim Ghaddar contributed equally to this work.Banghua Zhu
is with the Department of Electrical Engineering and Computer Sciences,
University of California Berkeley, Berkeley, CA 94720, USA, (email:
banghua@berkeley.edu).Ziao Wang is with the Department of Electrical and
Computer Engineering, University of British Columbia, Vancouver, BC V6T1Z4,
Canada (email: ziaow@ece.ubc.ca).Nadim Ghaddar is with the Department of
Electrical and Computer Engineering, University of California San Diego, La
Jolla, CA 92093, USA, (email: nghaddar@ucsd.edu).Jiantao Jiao is with the
Department of Electrical Engineering and Computer Sciences, University of
California Berkeley, Berkeley, CA 94720, USA, (email:
jiantao@eecs.berkeley.edu).Lele Wang is with the Department of Electrical and
Computer Engineering, University of British Columbia, Vancouver, BC V6T1Z4,
Canada (email: lelewang@ece.ubc.ca).

###### Abstract

We consider the problem of computing a function of $n$ variables using noisy
queries, where each query is incorrect with some fixed and known probability
$p\in(0,1/2)$. Specifically, we consider the computation of the $\mathsf{OR}$
function of $n$ bits (where queries correspond to noisy readings of the bits)
and the $\mathsf{MAX}$ function of $n$ real numbers (where queries correspond
to noisy pairwise comparisons). We show that an expected number of queries of

$(1\pm o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p\|1-p)}$

is both sufficient and necessary to compute both functions with a vanishing
error probability $\delta=o(1)$, where $D_{\mathsf{KL}}(p\|1-p)$ denotes the
Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and
$\mathsf{Bern}(1-p)$ distributions. Compared to previous work, our results
tighten the dependence on $p$ in both the upper and lower bounds for the two
functions.

##  I Introduction

Coping with noise in computing is an important problem to consider in large
systems. With applications in fault tolerance (Hastad et al., 1987, Pease et
al., 1980, Pippenger et al., 1991), active ranking (Shah and Wainwright, 2018,
Agarwal et al., 2017, Falahatgar et al., 2017, Heckel et al., 2019, Wang et
al., 2022, Gu and Xu, 2023), noisy searching (Berlekamp, 1964, Horstein, 1963,
Burnashev and Zigangirov, 1974, Pelc, 1989, Karp and Kleinberg, 2007), among
many others, the goal is to devise algorithms that are robust enough to detect
and correct the errors that can happen during the computation. More
concretely, the problem can be defined as follows: suppose an agent is
interested in computing a function $f$ of $n$ variables with an error
probability at most $\delta$, as quickly as possible. To this end, the agent
can ask binary questions (referred to hereafter as _queries_) about the
variables in hand. The binary response to the queries is observed by the agent
through a binary symmetric channel (BSC) with crossover probability $p$. The
agent can adaptively design subsequent queries based on the responses to
previous queries. The goal is to characterize the relation between $n$,
$\delta$, $p$, and the query complexity, which is defined as the minimal
number of queries that are needed by the agent to meet the intended goal of
computing the function $f$.

This paper considers the computation of the $\mathsf{OR}$ function of $n$ bits
and the $\mathsf{MAX}$ function of $n$ real numbers. For the computation of
the $\mathsf{OR}$ function, the noisy queries correspond to noisy readings of
the bits, where at each timestep, the agent queries one of the bits, and with
probability $p$, the wrong value of the bit is returned. For the computation
of the $\mathsf{MAX}$ function, the noisy queries correspond to noisy pairwise
comparisons, where at each timestep, the agent asks to compare two numbers in
the given sequence, and with probability $p$, the incorrect result of the
comparison is returned.

This model for the $\mathsf{OR}$ and $\mathsf{MAX}$ functions has been
previously considered in (Feige et al., 1994), where upper and lower bounds on
the number of queries that are needed to compute the two functions are derived
in terms of the number of variables $n$, the noise probability $p$ and the
desired error probability $\delta$. The upper and lower bounds in (Feige et
al., 1994) are tight only in terms of dependence on $n$; however, the exact
dependence of the query complexity on the parameters $p$ and $\delta$ is not
very clear. In this paper, we derive new upper and lower bounds for the
computation of the $\mathsf{OR}$ and $\mathsf{MAX}$ functions, with tight
dependence on $p$ and $\delta$.

###  I-A Main Contribution

The main result of this paper can be stated as follows: it is both sufficient
and necessary to use

$(1\pm o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p\|1-p)}$

queries in expectation to compute the $\mathsf{OR}$ and $\mathsf{MAX}$
functions with a vanishing error probability $\delta=o(1)$, where
$D_{\mathsf{KL}}(p\|1-p)$ denotes the Kullback-Leibler divergence between
$\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. This result
simultaneously improves the dependence on $p$ in both the upper and lower
bounds derived in (Feige et al., 1994).

From a technical standpoint, our lower bound for both functions is based on Le
Cam’s two point method, which transforms the noisy computing problem in hand
into a proper binary testing problem between two instances of the input
variables. By carefully designing the two instances to look at, Le Cam’s two
point lemma (Yu, 1997) then gives a non-asymptotic lower bound on the error
probability of any estimator that wishes to distinguish the evaluation of the
function over those two instances.

The algorithms that attain the upper bounds are executed in two steps. In the
first step, a subset of the input variables of sublinear size is chosen. In
the second step, an existing algorithm (e.g., one of the algorithms in (Feige
et al., 1994)) is executed over the chosen subset. For the $\mathsf{OR}$
function, the chosen subset corresponds to the input variables that, when
queried, return a value of 1. For the $\mathsf{MAX}$ function, the subset
corresponds to the elements of the sequence that appear to be larger than the
maximum of a random subsample of the input variables (of sublinear size). We
show that $(1+o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p\|1-p)}$
queries are used on average in the first step, while the query complexity of
the second step ends up being a lower order term.

###  I-B Related Work

The noisy computation of the $\mathsf{OR}$ function has been first studied in
the literature of circuit with noisy gates (Dobrushin and Ortyukov, 1977a, b,
Von Neumann, 1956, Pippenger et al., 1991, Gács and Gál, 1994) and noisy
decision trees (Feige et al., 1994, Evans and Pippenger, 1998, Reischuk and
Schmeltz, 1991). Since the querying model for the $\mathsf{OR}$ function
corresponds to noisy reading of the bits, it is closely related to the best
arm identification problem, where the variables correspond to real-valued arms
and the goal is to identify the arm with the largest value (i.e., reward)
(Bubeck et al., 2009, Audibert et al., 2010, Garivier and Kaufmann, 2016,
Jamieson and Nowak, 2014, Gabillon et al., 2012, Kaufmann et al., 2016).
Indeed, any best-arm identification algorithm can be converted to an
$\mathsf{OR}$ computation since the evaluation of the $\mathsf{OR}$ function
of $n$ bits is equal to the evaluation of their maximum. This observation
gives an upper bound
${\mathcal{O}}\left(\frac{n\log(1/\delta)}{1-H(p)}\right)$ on the number of
queries needed for the computation of the $\mathsf{OR}$ function (Audibert et
al., 2010), where $H(\cdot)$ denotes the binary entropy function. However, as
we shall see in this paper, this bound doesn’t give a tight dependence on $p$.

On the other hand, the noisy computation of the $\mathsf{MAX}$ function has
closely followed the literature on the active ranking problem (also known as
“noisy sorting”) and the top-$k$ selection problem (Mohajer et al., 2017, Shah
and Wainwright, 2018, Agarwal et al., 2017, Falahatgar et al., 2017, Heckel et
al., 2019, Wang et al., 2022, 2023, Gu and Xu, 2023), where the ranking of a
subset of the $n$ items is required. Many of these works considered
generalized noise models, where the noise probability can depend on the pair
of elements to be compared. For our simplified noise model, however, the best
known upper and lower bounds for the computation of the $\mathsf{MAX}$
function are due to (Feige et al., 1994) which gives an upper bound based on
the popular knockout tournament algorithm and a lower bound of
$\Omega\left(\frac{n\log(1/\delta)}{\log((1-p)/p)}\right)$ queries. As we
shall see, the dependence on $p$ in both bounds can be improved.

###  I-C Paper Organization and Notation

This paper is organized as follows. In Section II, the noisy $\mathsf{OR}$ and
noisy $\mathsf{MAX}$ problems are formally defined, and the main results are
stated. In Section III, we derive the upper and lower bounds for the noisy
$\mathsf{OR}$ problem, whereas in Section IV, we derive the upper and lower
bounds for the noisy $\mathsf{MAX}$ problem. In Section V, we discuss the
extension of the model to the case of a varying crossover probability $p$ that
depends on $n$.

Notation: The following notation will be used in this paper. Sets are denoted
in calligraphic letters, random variables in upper-case letters, and
realizations of random variables in lower-case letters, i.e., ${\mathcal{X}}$
and ${\mathcal{Y}}$ are two sets, $X$ and $Y$ are random variables, and $x$
and $y$ are their respective realizations. Bold face letters are used for
vectors, whereas normal face letters are used for scalars. The probability of
an event $A$ is denoted as $\operatorname{\mathsf{P}}(A)$, and the expectation
of real-valued random variable $X$ is denoted as
$\operatorname{\mathbb{E}}[X]$. We will often use the shorthand notation
$\operatorname{\mathbb{E}}_{x}(Y)$ to denote the conditional expectation
$\operatorname{\mathbb{E}}[Y\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}X=x]$,
where the random variable $X$ would be clear from the context. For a finite
set ${\mathcal{S}}$, we write $|{\mathcal{S}}|$ to denote the cardinality of
${\mathcal{S}}$. For $p\in(0,1)$,
${D_{\mathsf{KL}}(p\|1-p)}\triangleq(1-2p)\log\left(\frac{1-p}{p}\right)$
denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and
$\mathsf{Bern}(1-p)$ distributions, and $H(p)\triangleq-p\log
p-(1-p)\log(1-p)$ denotes the binary entropy function.

##  II Problem Formulation and Main Results

###  II-A Noisy $\mathsf{OR}$ Problem

Let us first consider the problem of computing the $\mathsf{OR}$ function of
$n$ bits using noisy observations of the bits. To this end, let ${\bf
X}=(X_{1},\ldots,X_{n})\in\\{0,1\\}^{n}$ be a sequence of $n$ bits. The
$\mathsf{OR}$ function is defined as

$\displaystyle\mathsf{OR}({\bf X})=\begin{cases}1,&\text{ if
}\exists\,i\in[n]:X_{i}=1\\\ 0,&\text{ otherwise.}\end{cases}$ (1)

At the $k$th time step, an agent can submit a query $U_{k}$ corresponding to
one of the bits, i.e., $U_{k}\triangleq X_{i}$ for some $i\in[n]$. The
response $Y_{k}$ can be expressed as

$Y_{k}=U_{k}\oplus Z_{k},$

where $Z_{k}\sim\mathrm{Bern}(p)$ is a sequence of i.i.d. random variables.
Note that the queries are designed adaptively, i.e.,

$U_{k}=f_{k}({\bf U}^{k-1},{\bf Y}^{k-1}),$

for some (possibly stochastic) function $f_{k}$. Moreover, the querying
strategy may have a variable stopping time that depends on the query
responses, i.e., the number of queries $M$ may be random. The goal of the
agent is to estimate the $\mathsf{OR}$ function using the noisy queries and
responses.

###  II-B Noisy $\mathsf{MAX}$ Problem

With a slight abuse of notation, for the noisy $\mathsf{MAX}$ problem, we use
${\bf X}=(X_{1},\ldots,X_{n})\in\mathbb{R}^{n}$ as a sequence of $n$ real
numbers. The $\mathsf{MAX}$ function is defined as

$\mathsf{MAX}({\bf X})=\operatorname*{arg\,max}_{i\in[n]}\,X_{i}.$

At the $k$th time step, the agent can submit a query
$(U_{k},V_{k})\triangleq(X_{i},X_{j})$ for some $i,j\in[n]$. The response
$Y_{k}$ can be expressed as

$Y_{k}=\mathbbm{1}_{\\{U_{k}<V_{k}\\}}\oplus Z_{k},$

where $\mathbbm{1}_{\\{.\\}}$ denotes the indicator function, and
$Z_{k}\sim\mathrm{Bern}(p)$ is a sequence of i.i.d. random variables. As for
the $\mathsf{OR}$ problem, the queries can be designed adaptively, i.e.,

$(U_{k},V_{k})=g_{k}({\bf U}^{k-1},{\bf V}^{k-1},{\bf Y}^{k-1}),$

for some (possibly stochastic) function $g_{k}$. Moreover, the querying
strategy may have a variable stopping time. The goal of the agent is to
estimate the $\mathsf{MAX}$ function using the responses to the noisy pairwise
comparisons.

######  Remark II.1.

Notice the difference in the querying models for the noisy $\mathsf{OR}$ and
$\mathsf{MAX}$ problems. While the queries in the noisy $\mathsf{OR}$ problem
correspond to readings of the bits, the queries in the noisy $\mathsf{MAX}$
problem correspond to pairwise comparisons between the elements in the given
sequence. Due to this distinction, one cannot immediately translate any upper
or lower bound on the number of queries from one problem to the other (despite
the fact that, for example, the $\mathsf{OR}$ of $n$ bits is equal to their
maximum).

###  II-C Main Results

Our main results can be summarized in the following four theorems, which give
tight upper and lower bounds on the expected number of queries needed to
compute the noisy $\mathsf{OR}$ and noisy $\mathsf{MAX}$ functions.

######  Theorem II.1 (Lower bound for $\mathsf{OR}$).

For the noisy $\mathsf{OR}$ problem, it holds that

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\\{0,1\\}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{OR}({\bf
x}))\geq\frac{1}{4}\cdot\exp\left(-\frac{m\cdot
D_{\mathsf{KL}}(p\|1-p)}{n}\right),$

where $m$ is the expected number of queries under the worst-case input binary
sequence. Thus, the expected number of queries needed to compute the
$\mathsf{OR}$ function with worst-case error probability at most $\delta=o(1)$
is lower bounded by
$(1-o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p\|1-p)}$.

######  Theorem II.2 (Upper bound for $\mathsf{OR}$).

For any vanishing $\delta=o(1)$, there exists an algorithm (Algorithm 3 in
Section III-B) that computes the $\mathsf{OR}$ function with an expected
number of queries at most

$(1+o(1))\frac{n\log\frac{1}{\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$ (2)

and worst-case error probability at most $\delta$.

######  Theorem II.3 (Lower bound for $\mathsf{MAX}$).

For the noisy $\mathsf{MAX}$ problem, it holds that

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\mathbb{R}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{MAX}({\bf
x}))\geq\frac{1}{4}\cdot\exp\left(-\frac{m\cdot
D_{\mathsf{KL}}(p\|1-p)}{n}\right),$

where $m$ is the expected number of queries under the worst-case input
sequence. Thus, the expected number of queries needed to compute the
$\mathsf{MAX}$ function with worst-case error probability at most
$\delta=o(1)$ is lower bounded by
$(1-o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p\|1-p)}$.

######  Theorem II.4 (Upper bound for $\mathsf{MAX}$).

For any vanishing $\delta=o(1)$, there exists an algorithm (Algorithm 6 in
Section IV-B) that computes the $\mathsf{MAX}$ function with an expected
number of queries at most

$(1+o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p||1-p)}$

and worst-case error probability at most $\delta$.

##  III Noisy $\mathsf{OR}$ Problem

###  III-A Lower Bound

First, we consider the lower bound for the noisy $\mathsf{OR}$ problem
(Theorem II.1). We give a proof of the theorem based on Le Cam’s two point
method (LeCam, 1973, Yu, 1997), which is stated in Lemma A.1 in Appendix A for
the reader’s convenience.

###### Proof of Theorem II.1.

Let ${\bf x}_{0}$ be the length-$n$ all-zero sequence, and let ${\bf
x}_{j}\in\\{0,1\\}^{n}$ be such that $x_{jj}=1$ and $x_{ji}=0$ for $i\neq j$,
where $x_{ji}$ refers to the $i$-th element in the $j$th binary sequence ${\bf
x}_{j}$. We can first verify that for any estimate $\hat{\mu}$, one has

$\displaystyle\mathds{1}(\hat{\mu}\neq\mathsf{OR}({\bf
x}_{0}))+\mathds{1}(\hat{\mu}\neq\mathsf{OR}({\bf x}_{j}))\geq 1.$

By applying Le Cam’s two point lemma on ${\bf x}_{0}$ and ${\bf x}_{j}$, we
know that

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\\{0,1\\}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{OR}({\bf
x}))$ $\displaystyle\geq\frac{1}{2}\left(1-\mathsf{TV}(\mathbb{P}_{{\bf
x}_{0}},\mathbb{P}_{{\bf x}_{j}})\right).$

Here, $\mathbb{P}_{{\bf x}_{j}}$ denotes the distribution of the query
responses in $m$ rounds when the underlying binary sequence is ${\bf x}_{j}$.
By taking maximum over $j$ on the right-hand side, we have

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\\{0,1\\}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{OR}({\bf
x}))$ $\displaystyle\geq\sup_{1\leq j\leq
n}\frac{1}{2}\left(1-\mathsf{TV}(\mathbb{P}_{{\bf x}_{0}},\mathbb{P}_{{\bf
x}_{j}})\right)$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sup_{1\leq
j\leq n}\frac{1}{4}\exp\left(-D_{\mathsf{KL}}(\mathbb{P}_{{\bf
x}_{0}},\mathbb{P}_{{\bf x}_{j}})\right),$

where $(a)$ follows due to the Bretagnolle–Huber inequality (Bretagnolle and
Huber, 1979) (Lemma A.2 in Appendix A). Now, we aim at computing
$D_{\mathsf{KL}}(\mathbb{P}_{{\bf x}_{0}},\mathbb{P}_{{\bf x}_{j}})$. Let
$M_{j}$ be the random variable that denotes the number of times the $j$th
element is queried among all $m$ rounds. From the divergence decomposition
lemma (Auer et al., 1995) (Lemma A.3 in Appendix A) and the fact that ${\bf
x}_{0}$ and ${\bf x}_{j}$ only differ in the $j$th position, we have

$\displaystyle D_{\mathsf{KL}}(\mathbb{P}_{{\bf x}_{0}},\mathbb{P}_{{\bf
x}_{j}})=\operatorname{\mathbb{E}}_{{\bf x}_{0}}[M_{j}]\cdot
D_{\mathsf{KL}}(p\|1-p).$

Here, $\mathbb{E}_{{\bf x}_{0}}[M_{j}]$ denotes the expected number of times
the $j$th element is queried when the underlying sequence is ${\bf x}_{0}$.
Thus we have

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\\{0,1\\}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{OR}({\bf
x}))\geq\sup_{1\leq j\leq
n}\frac{1}{4}\exp\left(-\operatorname{\mathbb{E}}_{{\bf x}_{0}}[M_{j}]\cdot
D_{\mathsf{KL}}(p\|1-p)\right).$

Now, since $\sum_{j}\operatorname{\mathbb{E}}_{{\bf
x}_{0}}[M_{j}]=\operatorname{\mathbb{E}}_{{\bf x}_{0}}[M]\leq\sup_{\bf
x}\operatorname{\mathbb{E}}_{\bf x}[M]\triangleq m$, there must exist some $j$
such that $\operatorname{\mathbb{E}}_{{\bf x}_{0}}[M_{j}]\leq m/n$. This gives

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\\{0,1\\}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{OR}({\bf
x}))$ $\displaystyle\geq\frac{1}{4}\exp\left(-\frac{m\cdot
D_{\mathsf{KL}}(p\|1-p)}{n}\right).$

Therefore, to achieve an error probability $\delta$ for any input sequence
${\bf x}$, the number of queries must satisfy that

$m\geq\frac{n\log\frac{1}{4\delta}}{D_{\mathsf{KL}}(p||1-p)}=(1-o(1))\frac{n\log\frac{1}{\delta}}{D_{\mathsf{KL}}(p||1-p)}.$

∎

###  III-B Upper Bound

Now, we prove the upper bound for the noisy $\mathsf{OR}$ problem (Theorem
II.2). Towards this end, we first describe two existing algorithms that will
be used as subroutines in our proposed algorithm for the noisy $\mathsf{OR}$
problem. The first algorithm is the CheckBit algorithm, which takes as input a
single bit and returns an estimate of the bit through repeated queries. The
following lemma holds for the CheckBit algorithm, which is given for
completion in Algorithm 1. Note that the parameter $\alpha$ in the $i$th
iteration of Algorithm 1 corresponds to the probability that the input bit is
one given the first $i$ noisy observations.

Algorithm 1 CheckBit  algorithm for finding the value of an input bit

Input: Input bit $x$, tolerated error probability $\delta$, crossover
probability $p$.
Output: Estimate of $x$.

1:Set $\alpha\leftarrow 1/2$.

2:while $\alpha\in(\delta,1-\delta)$ do

3: Query the input bit $x$.

4: if $1$ is observed then

5: Set $\alpha\leftarrow\frac{(1-p)\alpha}{(1-p)\alpha+p(1-\alpha)}$.

6: else

7: Set $\alpha\leftarrow\frac{p\alpha}{p\alpha+(1-p)(1-\alpha)}$.

8:if $\alpha\geq 1-\delta$ then

9: return $1$.

10:else

11: return $0$.

######  Lemma III.1 (Lemma 13 in (Gu and Xu, 2023)).

There exists a randomized algorithm, namely, the CheckBit  algorithm, that
finds the value of any input bit $x$ with error probability at most $\delta$.
The algorithm makes at most
$\frac{1}{1-2p}\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil$
queries in expectation.

The second algorithm is the Tournament_OR algorithm for computing the
$\mathsf{OR}$ function from noisy queries. This algorithm has been previously
proposed in our earlier work (Zhu et al., 2023), and is given here for
completion in Algorithm 2. The following lemma gives an upper bound on the
expected number of queries made by the Tournament_OR algorithm.

######  Lemma III.2 (Theorem J.1 in (Zhu et al., 2023)).

For any $\delta<1/2$, there exists an algorithm, namely the Tournament_OR
algorithm, that computes the $\mathsf{OR}$ function with error probability at
most $\delta$. The expected number of queries made by the algorithm is upper
bounded by
$C\left(\frac{n}{1-H(p)}+\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right)$,
where $C$ is an absolute constant.

Algorithm 2 Tournament_OR algorithm for computing noisy $\mathsf{OR}$ function

Input: Bit sequence ${\bf x}=(x_{1},\ldots,x_{n})$, tolerated error
probability $\delta$, crossover probability $p$.
Output: Estimate of $\mathsf{OR}({\bf x})$.

1:Set ${\bf y}\leftarrow{\bf x}$, $r\leftarrow n$.

2:for iteration $i=1:\lceil\log_{2}(n)\rceil$ do

3: Set $\tilde{\delta}_{i}\leftarrow\delta^{2(2i-1)}$.

4: for iteration $j=1:\lfloor r/2\rfloor$ do

5: Set $a\leftarrow\textsc{CheckBit }(y_{2j-1},\,\tilde{\delta}_{i},\,p)$.

6: if $a=1$ then

7: Set $z_{j}\leftarrow y_{2j-1}$.

8: else

9: Set $z_{j}\leftarrow y_{2j}$.

10: if $r$ is even then

11: Set ${\bf y}\leftarrow(z_{1},\ldots,z_{r/2})$.

12: else

13: Set ${\bf y}\leftarrow(z_{1},\ldots,z_{\lfloor r/2\rfloor},y_{r})$.

14: Set $r\leftarrow\lceil r/2\rceil$.

15:return CheckBit ($y$, $\delta$, p)

Now, we are ready to describe the proposed NoisyOR algorithm for the noisy
$\mathsf{OR}$ problem. The algorithm is given in Algorithm 3, in which the
CheckBit and Tournament_OR algorithms appear as subroutines. In the following,
we analyze the error probability and the expected number of queries made by
the NoisyOR algorithm.

Algorithm 3 Proposed NoisyOR algorithm

Input: Bit sequence ${\bf x}=(x_{1},\ldots,x_{n})$, tolerated error
probability $\delta$, crossover probability $p$.
Output: Estimate of $\mathsf{OR}({\bf x})$.

1:Set ${\bf y}\leftarrow\emptyset$, $r\leftarrow 0$.

2:for $i\in[n]$ do

3: if CheckBit ($x_{i}$, $\delta$, $p)=1$ then

4: Append $x_{i}$ to ${\bf y}$.

5: Set $r\leftarrow r+1$.

6:if $r=0$ then

7: return $0$

8:else if $r\geq\max(\log n,\,n\delta\log\frac{1}{\delta})$ then

9: return $1$

10:else

11: return Tournament_OR (${\bf y}$, $\delta$, $p$)

####  III-B1 Error Analysis

For the NoisyOR algorithm, the following lemma holds.

######  Lemma III.3.

For any input parameter $\delta<1/2$ and bit sequence ${\bf x}$, the error
probability of the NoisyOR algorithm is upper bounded by $2\delta$.

###### Proof.

Let $\hat{\mu}$ denote the output of the NoisyOR algorithm, and let
${\mathcal{S}}$ denote the set of bits appended to ${\bf y}$ in Line 4 of the
algorithm. To prove Lemma III.3, we are going to separately consider two types
of input sequences ${\bf x}$.

First, suppose that at least one bit of the input sequence is $1$, i.e.,
$\mathsf{OR}({\bf x})=1$. Without loss of generality, assume that $x_{1}=1$.
Let $\mathcal{E}_{1}\triangleq\\{\hat{\mu}=0\\}$ be the error event in this
case, and let $\mathcal{A}\triangleq\\{x_{1}\notin\mathcal{S}\\}$ denote an
auxiliary event that $x_{1}$ is not appended into ${\bf y}$. By the union
bound, we have

$\operatorname{\mathsf{P}}(\mathcal{E}_{1})\leq\operatorname{\mathsf{P}}({\mathcal{A}})+\operatorname{\mathsf{P}}({\mathcal{E}}_{1}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c}).$

For the first term, we notice that
$\operatorname{\mathsf{P}}({\mathcal{A}})\leq\delta$ by Lemma III.1. For the
second term, note that $|\mathcal{S}|\geq 1$ on the event ${\mathcal{A}}^{c}$.
Therefore, the only possibility for the algorithm to return $0$ is that the
function call of Tournament_OR on Line 11 incorrectly returns $0$. By Lemma
III.2, we have that
$\operatorname{\mathsf{P}}({\mathcal{E}}_{1}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c})\leq\delta$.
This leads to the upper bound
$\operatorname{\mathsf{P}}({\mathcal{E}}_{1})\leq 2\delta$.

Next, we move on to consider the all-zero input sequence. Let
${\mathcal{E}}_{0}\triangleq\\{\hat{\mu}=1\\}$ denote the error event in this
case, and define an auxiliary event
${\mathcal{B}}=\\{|\mathcal{S}|\geq\max(\log
n,\,n\delta\log\frac{1}{\delta})\\}$. As before, we have

$\operatorname{\mathsf{P}}(\mathcal{E}_{0})\leq\operatorname{\mathsf{P}}({\mathcal{B}})+\operatorname{\mathsf{P}}({\mathcal{E}}_{0}|{\mathcal{B}}^{c}).$

By Lemma III.2, we know that
$\operatorname{\mathsf{P}}({\mathcal{E}}_{0}|{\mathcal{B}}^{c})\leq\delta$.
Moreover, we claim that $\operatorname{\mathsf{P}}({\mathcal{B}})=o(\delta)$.
These would together imply that
$\operatorname{\mathsf{P}}({\mathcal{E}}_{0})=(1+o(1))\delta$.

Now we move on to show the claim. By Lemma III.1, we know that the random
variable $|\mathcal{S}|$ is statistically dominated by
$\mathrm{Binom}(n,\delta)$. We will separately consider two different regimes
to show the claim.

Regime 1: $\delta\geq\frac{1}{n}$. In this case, $\max(\log
n,\,n\delta\log\frac{1}{\delta})=n\delta\log\frac{1}{\delta}$. We have

$\displaystyle\operatorname{\mathsf{P}}\left(|\mathcal{S}|\geq
n\delta\log\frac{1}{\delta}\right)$
$\displaystyle\leq\operatorname{\mathsf{P}}\left(\mathrm{Binom}(n,\delta)\geq
n\delta\log\frac{1}{\delta}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\exp\left(-nD_{\mathsf{KL}}\left(\delta\log\frac{1}{\delta}\Big{\|}\delta\right)\right)$
$\displaystyle=\exp\left(-n\delta\log\frac{1}{\delta}\log\log\frac{1}{\delta}(1-o(1))\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}o(\delta),$

where $(a)$ follows by the additive Chernoff bound (Lemma A.4 in Appendix A),
and $(b)$ follows because $n\delta\geq 1$ and
$\log\log\frac{1}{\delta}=\omega(1)$.

Regime 2: $\delta<\frac{1}{n}$. In this case, $\max(\log
n,\,n\delta\log\frac{1}{\delta})=\log n$. We have

$\displaystyle\operatorname{\mathsf{P}}(|\mathcal{S}|\geq\log n)$
$\displaystyle\leq\operatorname{\mathsf{P}}\left(\mathrm{Binom}(n,\delta)\geq\log
n\right)$ $\displaystyle\leq\exp\left(-nD_{\mathsf{KL}}\left(\frac{\log
n}{n}\Big{\|}\delta\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\exp\left(-\log n\log\frac{\log
n}{n\delta}(1-o(1))\right)$ $\displaystyle=\left(\frac{n\delta}{\log
n}\right)^{(1-o(1))\log n},$

where $(c)$ follows because $\delta<1/n$. To complete the argument, first
suppose that $\delta=n^{-\Theta(1)}$. In this case, because $n\delta<1$, we
have

$\left(\frac{n\delta}{\log n}\right)^{(1-o(1))\log n}<\frac{1}{(\log
n)^{(1-o(1))\log n}}=n^{-\omega(1)}=o(\delta).$

Secondly, suppose $\delta=n^{-\omega(1)}$. Then we have

$\exp\left(-\log n\log\frac{\log n}{n\delta}(1-o(1))\right)=\exp\left(-\log
n\log\frac{1}{\delta}(1-o(1))\right)=o(\delta).$

∎

####  III-B2 Query Analysis

Let $M$ denote the number of queries made by the NoisyOR algorithm. The
following lemma provides an upper bound on the expectation of $M$, and hence
completes the proof of Theorem II.2.

######  Lemma III.4.

For $\delta=o(1)$, the expected number of queries made by the NoisyOR
algorithm satisfies that

$\operatorname{\mathbb{E}}[M]\leq(1+o(1))\frac{n\log\frac{1}{\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}.$

###### Proof.

As before, let ${\mathcal{S}}$ denote the set of bits appended to ${\bf y}$ in
Line 4 of the algorithm. To bound $\operatorname{\mathbb{E}}[M]$, we only need
to bound the expected number of queries made by the $n$ calls of the CheckBit
function on Line 3, and the single call of the Tournament_OR function on Line
11. By Lemma III.1, we know that the expected number of queries spent at Line
3 is at most

$\frac{n}{1-2p}\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil\leq\frac{n}{1-2p}\left(\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}+1\right)=(1+o(1))\frac{n\log\frac{1}{\delta}}{(1-2p)\log\frac{1-p}{p}}=(1+o(1))\frac{n\log\frac{1}{\delta}}{{D_{\mathsf{KL}}(p\|1-p)}},$

where the penultimate equality follows because $\delta=o(1)$ and $p$ is
bounded away from $0$ and $1/2$, and the last equality follows because
${D_{\mathsf{KL}}(p\|1-p)}\triangleq(1-2p)\log\frac{1-p}{p}$. By Lemma III.2,
we know that the expected number of queries spent at Line 11 is at most

$C\left(\frac{\operatorname{\mathbb{E}}[|\mathcal{S}|]}{1-H(p)}+\frac{\operatorname{\mathbb{E}}[|\mathcal{S}|]\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right)=C(1+o(1))\operatorname{\mathbb{E}}[|\mathcal{S}|]\log(1/\delta)=o(n\log(1/\delta)),$

where the penultimate equality follows because $\delta=o(1)$ and $p$ is
bounded away from $0$ and $1/2$, and the last equality follows because we
always have $|\mathcal{S}|=o(n)$ on the event that Line 11 is executed.

Finally, by the linearity of expectation, we have
$\operatorname{\mathbb{E}}[M]\leq(1+o(1))\frac{n\log\frac{1}{\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$.
∎

##  IV Noisy $\mathsf{MAX}$ Problem

###  IV-A Lower Bound

In this part, we turn our attention to the noisy $\mathsf{MAX}$ problem. We
first consider the lower bound established in Theorem II.3. As for the
$\mathsf{OR}$ problem, our proof of the lower bound is based on Le Cam’s two
point method (see Lemma A.1 in Appendix A).

###### Proof of Theorem II.3.

Consider an arbitrary sequence ${\bf y}\in\mathbb{R}^{n}$. Without loss of
generality, assume that $y_{1}<\cdots<y_{n}$. Clearly, in this case, we have
$\mathsf{MAX}({\bf y})=n$. Now, for $i\in[n-1]$, consider the sequence ${\bf
z}_{i}=(y_{1},\ldots,y_{i-1},y_{n},y_{i},\ldots,y_{n-1})$, i.e., we move the
$n$th element in ${\bf y}$ and insert it between $y_{i-1}$ and $y_{i}$. Notice
that $\mathsf{MAX}({\bf z}_{i})=i$ for all $i\in[n-1]$.

Let $M$ denote the total number of queries made by the estimator, and let
$M_{i,j}$ represent the number of pairwise comparisons made between the $i$th
and $j$th elements in the $M$ rounds. We first notice that, for any estimator
$\hat{\mu}$ and any $i\in[n-1]$,

$\displaystyle\mathds{1}(\hat{\mu}\neq\mathsf{MAX}({\bf
y}))+\mathds{1}(\hat{\mu}\neq\mathsf{MAX}({\bf z}_{i}))\geq 1.$

Following a similar proof as Theorem II.1, it holds that

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\mathbb{R}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{MAX}({\bf
x}))$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sup_{1\leq i\leq
n-1}\frac{1}{2}\left(1-\mathsf{TV}(\mathbb{P}_{{\bf y}},\mathbb{P}_{{\bf
z}_{i}})\right)$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\sup_{1\leq
i\leq n-1}\frac{1}{4}\exp\left(-D_{\mathsf{KL}}(\mathbb{P}_{{\bf
y}},\mathbb{P}_{{\bf z}_{i}})\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\sup_{1\leq i\leq
n-1}\frac{1}{4}\exp\left(-\sum_{j=i+1}^{n}\operatorname{\mathbb{E}}_{{\bf
y}}[M_{i,j}]\cdot D_{\mathsf{KL}}(p\|1-p)\right),$

where $\mathbb{P}_{{\bf z}_{i}}$ denotes the distribution of query responses
in $m$ rounds when the underlying sequence is ${\bf z}_{i}$. Here, $(a)$
follows by Le Cam’s two point lemma (Lemma A.1 in Appendix A), $(b)$ follows
from the Bretagnolle–Huber inequality (Lemma A.2 in Appendix A), and $(c)$
follows from the divergence decomposition lemma (Lemma A.3 in Appendix A) and
the fact that the distributions $\mathbb{P}_{{\bf y}}$ and $\mathbb{P}_{{\bf
z}_{i}}$ only differ when the $i$th element is compared with a subsequent
element. Now, since $\sum_{i,j\in[n],i<j}\operatorname{\mathbb{E}}_{{\bf
y}}[M_{i,j}]=\operatorname{\mathbb{E}}_{{\bf y}}[M]\leq\sup_{\bf
x}\operatorname{\mathbb{E}}_{\bf x}[M]\triangleq m$, there must exist some
index $i$ such that $\sum_{j=i+1}^{n}\operatorname{\mathbb{E}}_{{\bf
y}}[M_{i,j}]\leq\frac{m}{n-1}$. This gives

$\displaystyle\inf_{\hat{\mu}}\sup_{{\bf
x}\in\mathbb{R}^{n}}\operatorname{\mathsf{P}}(\hat{\mu}\neq\mathsf{MAX}({\bf
x}))$
$\displaystyle\geq\frac{1}{4}\exp\left(-\frac{m\cdot{D_{\mathsf{KL}}(p\|1-p)}}{n-1}\right).$

It follows that, to achieve an error probability at most $\delta=o(1)$ for any
input sequence ${\bf x}$, the number of queries must satisfy that

$m\geq\frac{(n-1)\log\frac{1}{4\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}=(1-o(1))\frac{n\log\frac{1}{\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}.$

∎

###  IV-B Upper Bound

Next, we prove the upper bound stated in Theorem II.4. To prove the theorem,
we devise a querying strategy for the noisy $\mathsf{MAX}$ problem. Towards
this end, we first highlight the NoisyCompare algorithm for comparing two
elements in the presence of noise with an error probability at most $\delta$.
This function is given in Algorithm 4, which can be seen as a recast of
Algorithm 1 in (Gu and Xu, 2023).

######  Lemma IV.1 (Lemma 13 in (Gu and Xu, 2023)).

The NoisyCompare algorithm has an error probability at most $\delta$, and the
expected number of queries made by the algorithm is at most
$\frac{1}{1-2p}\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil$.

Algorithm 4 NoisyCompare for comparing two elements in the presence of noise

Input: Elements $x_{1}$ and $x_{2}$ to be compared, tolerated error
probability $\delta$, crossover probability $p$.
Output: Boolean variable indicating if $x_{1}$ is less than $x_{2}$.

1:Set $\alpha\leftarrow\frac{1}{2}$.

2:while $\mathrm{true}$ do

3: Make a noisy pairwise comparison between $x_{1}$ and $x_{2}$.

4: if $x_{1}<x_{2}$ is returned from the comparison then

5: Set $\alpha\leftarrow\frac{(1-p)\alpha}{(1-p)\alpha+p(1-\alpha))}$.

6: else

7: Set $\alpha\leftarrow\frac{p\alpha}{p\alpha+(1-p)(1-\alpha)}$.

8: if $\alpha\geq 1-\delta$ then

9: return $\mathrm{true}$

10: if $\alpha\leq\delta$ then

11: return $\mathrm{false}$

######  Remark IV.1.

Note that to compute the noisy $\mathsf{MAX}$ function, one can repeatedly
apply the NoisyCompare algorithm $n-1$ times, while setting the tolerated
error probability to $\frac{\delta}{n-1}$ each time. This would guarantee that
the noisy $\mathsf{MAX}$ function can be computed with an overall error
probability $\delta$; however, the total expected number of queries in this
case would be $(1+o(1))\frac{n\log\frac{n}{\delta}}{D_{\mathsf{KL}}(p\|1-p)}$,
which is not tight compared to the lower bound derived in Section IV-A.

Another subroutine that will be used in our proposed algorithm is the
Tournament_Max algorithm, given in Algorithm 5, which can be used to compute
the noisy $\mathsf{MAX}$ function. The following lemma states that
$O(n\log(1/\delta))$ queries are made by the algorithm on average. Note that
the exact multiplicative constant may depend on $p$; however, for the sake of
the analysis of our proposed algorithm, the exact constant does not matter.

######  Lemma IV.2 (Theorem J.1 in (Zhu et al., 2023)).

The Tournament_Max algorithm computes the $\mathsf{MAX}$ function with error
probability at most $\delta$. The algorithm makes at most
$C\left(\frac{n}{1-H(p)}+\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right)$
queries on average, where $C$ is an absolute constant.

Algorithm 5 Tournament_Max algorithm for computing the noisy $\mathsf{MAX}$
function

Input: Sequence ${\bf x}=(x_{1},\ldots,x_{n})$, tolerated error probability
$\delta$, crossover probability $p$.
Output: Estimate of $x_{\mathsf{MAX}({\bf x})}$.

1:Set ${\bf y}\leftarrow{\bf x}$, $r\leftarrow n$.

2:for iteration $i=1:\lceil\log_{2}(n)\rceil$ do

3: Set $\tilde{\delta}_{i}\leftarrow\delta^{2(2i-1)}$.

4: for iteration $j=1:\lfloor r/2\rfloor$ do

5: if NoisyCompare($y_{2j-1}$, $y_{2j}$, $\tilde{\delta}_{i}$, $p$) then

6: Set $z_{j}\leftarrow y_{2j}$.

7: else

8: Set $z_{j}\leftarrow y_{2j-1}$.

9: if $r$ is even then

10: Set ${\bf y}\leftarrow(z_{1},\ldots,z_{r/2})$.

11: else

12: Set ${\bf y}\leftarrow(z_{1},\ldots,z_{\lfloor r/2\rfloor},y_{r})$.

13: Set $r\leftarrow\lceil r/2\rceil$.

14:return $y$

Algorithm 6 Proposed NoisyMax algorithm

Input: Sequence ${\bf x}=(x_{1},\ldots,x_{n})$, tolerated error probability
$\delta$, crossover probability $p$.
Output: Estimate of $x_{\mathsf{MAX}({\bf x})}$.

1:Set ${\bf y}\leftarrow\emptyset$, ${\bf z}\leftarrow\emptyset$.

2:for iteration $i=1:n$ do

3: Append $x_{i}$ to ${\bf y}$ with probability $\frac{1}{\log n}$.

4:Let $\mathcal{S}$ be the set of elements of ${\bf x}$ that were appended to
${\bf y}$.

5:Set $\hat{y}\leftarrow$ Tournament_Max $({\bf y},\delta,p)$.

6:Append $\hat{y}$ to ${\bf z}$.

7:for element $u\in\mathcal{S}^{c}$ do

8: if NoisyCompare($\hat{y}$, $u$, $\delta$, $p$) then

9: Append $u$ to ${\bf z}$.

10:Set $\hat{x}\leftarrow$ Tournament_Max $({\bf z},\delta,p)$.

11:return $\hat{x}$

The proposed NoisyMax algorithm is given in Algorithm 6, where the
Tournament_Max and NoisyCompare algorithms appear as subroutines. In the
following, we analyze the error probability and the number of queries of the
proposed algorithm.

####  IV-B1 Error Analysis

Let $x^{*}=x_{\mathsf{MAX}({\bf x})}$ denote the largest element in ${\bf x}$.
In the following, we provide an upper bound on the error probability
$\operatorname{\mathsf{P}}(\hat{x}\neq x^{*})$.

######  Lemma IV.3 (Error probability of NoisyMax).

The error probability of the NoisyMax algorithm satisfies that

$\operatorname{\mathsf{P}}(\hat{x}\neq x^{*})\leq 3\delta.$

###### Proof.

To prove Lemma IV.3, we first define a few error events. Let
${\mathcal{E}}=\\{\hat{x}\neq x^{*}\\}$ denote the error probability of the
NoisyMax algorithm. Let $y^{*}\triangleq\mathsf{MAX}({\bf y})$ and
$z^{*}\triangleq\mathsf{MAX}({\bf z})$ denote the indices of the largest
elements of ${\bf y}$ and ${\bf z}$, where ${\bf y}$ and ${\bf z}$ are as
constructed in Lines 3 and 9 of Algorithm 6 respectively. We define
${\mathcal{E}}_{1}=\\{\hat{y}\neq y^{*}\\}$ as the event that the
Tournament_Max algorithm outputs an incorrect estimate in Line 5. We let
${\mathcal{E}}_{2}=\\{x^{*}\text{ is not contained in }{\bf z}\\}$ denote the
event that the true maximum element $x^{*}$ does not belong to the vector
${\bf z}$. Finally, we define ${\mathcal{E}}_{3}=\\{\hat{x}\neq z^{*}\\}$ as
the event that the Tournament_Max algorithm in Line 10 returns an incorrect
estimate.

By the union bound, we clearly have

$\operatorname{\mathsf{P}}({\mathcal{E}})\leq\operatorname{\mathsf{P}}({\mathcal{E}}_{1})+\operatorname{\mathsf{P}}({\mathcal{E}}_{2}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})+\operatorname{\mathsf{P}}({\mathcal{E}}_{3}).$

By Lemma IV.2, we have that
$\operatorname{\mathsf{P}}({\mathcal{E}}_{1})\leq\delta$ and
$\operatorname{\mathsf{P}}({\mathcal{E}}_{3})\leq\delta$. To bound
$\operatorname{\mathsf{P}}({\mathcal{E}}_{2}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})$,
we consider two cases. First, in the case that $x^{*}$ is appended to ${\bf
y}$ in Line 3, we have that $x^{*}=y^{*}$. Given the event
${\mathcal{E}}_{1}^{c}$, we thus know that $\hat{y}=x^{*}$, which is appended
to ${\bf z}$ in Line 6. Hence, we have that
$\operatorname{\mathsf{P}}({\mathcal{E}}_{2}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})=0$
in this case. In the second case that $x^{*}$ is not appended to ${\bf y}$ in
Line 3, we have that $x^{*}\in{\mathcal{S}}^{c}$. It follows that $x^{*}$ is
not appended to ${\bf z}$ only if the result of the noisy comparison of
$\hat{y}$ and $x^{*}$ in Line 8 is incorrect. Since this happens with error
probability at most $\delta$, we have that
$\operatorname{\mathsf{P}}({\mathcal{E}}_{2}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})\leq\delta$
in this case, and the statement of the lemma follows. ∎

####  IV-B2 Query Analysis

Let $M$ denote the number of queries made by the NoisyMax algorithm. In the
following lemma, we provide an upper bound on $\operatorname{\mathbb{E}}[M]$.

######  Lemma IV.4.

Suppose $\delta=o(1)$. The expected number of queries
$\operatorname{\mathbb{E}}[M]$ of the NoisyMax algorithm satisfies that

$\operatorname{\mathbb{E}}[M]\leq(1+o(1))\frac{n\log(1/\delta)}{D_{\mathrm{KL}}(p||1-p)}.$

###### Proof.

To prove Lemma IV.4, we first define two auxiliary sets. Let ${\mathcal{S}}$
be the set of elements $x_{i}$ that were appended to ${\bf y}$ (as defined in
Line 4 of Algorithm 6), and let ${\mathcal{T}}$ be the set of elements $x_{i}$
that were appended to ${\bf z}$ in Lines 6 and 9. Consider the two events:

$\displaystyle{\mathcal{A}}$
$\displaystyle=\\{|{\mathcal{S}}|\leq\frac{n}{\log n}+n^{3/4}\\},$
$\displaystyle{\mathcal{B}}$
$\displaystyle=\\{|{\mathcal{T}}|\leq\sqrt{n}+\delta n+n^{3/4}\\}.$

By the law of total expectation, we know that

$\operatorname{\mathbb{E}}[M]=\operatorname{\mathbb{E}}[M\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}\cap{\mathcal{B}}]\operatorname{\mathsf{P}}({\mathcal{A}}\cap{\mathcal{B}})+\operatorname{\mathbb{E}}[M\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}]\operatorname{\mathsf{P}}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}).$

In the following, we analyze the two conditional expectations. We notice that
all the queries made by the NoisyMax algorithm are spent on the two calls of
the Tournament_Max algorithm in Lines 5 and 10, and the $n-|{\mathcal{S}}|$
calls of the NoisyCompare algorithm in Line 8. By Lemma IV.2, we know that the
expected number number of queries spent on Lines 5 and 10 are
$O\left(\operatorname{\mathbb{E}}\left[|{\mathcal{S}}|\right]\log(1/\delta)\right)$
and
$O\left(\operatorname{\mathbb{E}}\left[|{\mathcal{T}}|\right]\log(1/\delta)\right)$
respectively, because $\delta=o(1)$ and $p$ is a constant bounded away from
$0$ and $1/2$. By Lemma IV.1, we have that the expected number of queries
spent on Line 8 is at most
$(1+o(1))\frac{(n-\operatorname{\mathbb{E}}\left[|{\mathcal{S}}|\right])\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}$.
Therefore, by the linearity of expectation, we have that

$\operatorname{\mathbb{E}}[M]=O\left(\operatorname{\mathbb{E}}\left[|{\mathcal{S}}|\right]\log(1/\delta)\right)+O\left(\operatorname{\mathbb{E}}\left[|{\mathcal{T}}|\right]\log(1/\delta)\right)+(1+o(1))\frac{(n-\operatorname{\mathbb{E}}\left[|{\mathcal{S}}|\right])\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}.$

Notice that on the event ${\mathcal{A}}\cap{\mathcal{B}}$, we have that
$\operatorname{\mathbb{E}}\left[|{\mathcal{S}}|\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}\cap{\mathcal{B}}\right]=o(n)$
and
$\operatorname{\mathbb{E}}\left[|{\mathcal{T}}|\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}\cap{\mathcal{B}}\right]=o(n)$
(since $\delta=o(1)$). It follows that

$\operatorname{\mathbb{E}}\left[M\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}\cap{\mathcal{B}}\right]\leq(1+o(1))\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}.$

In the case when ${\mathcal{A}}$ or ${\mathcal{B}}$ does not hold, we still
have that
$\operatorname{\mathbb{E}}\left[|{\mathcal{S}}|\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}\right]=O(n)$
and
$\operatorname{\mathbb{E}}\left[|{\mathcal{T}}|\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}\right]=O(n)$.
Thus, we have that

$\operatorname{\mathbb{E}}\left[M\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}\right]=O\left(\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right).$

It follows that

$\displaystyle\operatorname{\mathbb{E}}[M]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[M\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}\cap{\mathcal{B}}\right]+\operatorname{\mathbb{E}}\left[M\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}\right]\operatorname{\mathsf{P}}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c})$
$\displaystyle\leq(1+o(1))\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}+O\left(\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right)\operatorname{\mathsf{P}}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c}).$

Hence, to complete the proof, it suffices to show that
$\operatorname{\mathsf{P}}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c})=o(1)$. This
is implied by the following two lemmas, whose proofs are deferred to Appendix
B.

######  Lemma IV.5.

The probability of event ${\mathcal{A}}^{c}$ satisfies that

$\operatorname{\mathsf{P}}({\mathcal{A}}^{c})={\mathcal{O}}(\exp(-n^{c_{1}}))$

for some positive constant $c_{1}$.

######  Lemma IV.6.

Let ${\mathcal{E}}_{1}=\\{\hat{y}\neq y^{*}\\}$ denote the event that the
Tournament_Max algorithm returns an incorrect estimate in Line 5 of Algorithm
6. The conditional probability of event ${\mathcal{B}}^{c}$ given event
${\mathcal{E}}_{1}^{c}$ satisfies that

$\operatorname{\mathsf{P}}({\mathcal{B}}^{c}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})={\mathcal{O}}(\exp(-n^{c_{2}}))$

for some positive constant $c_{2}$.

Together with Lemma IV.2, Lemmas IV.5 and IV.6 imply that

$\operatorname{\mathsf{P}}({\mathcal{A}}^{c}\cup{\mathcal{B}}^{c})\leq\operatorname{\mathsf{P}}({\mathcal{A}}^{c})+\operatorname{\mathsf{P}}({\mathcal{B}}^{c})\leq\operatorname{\mathsf{P}}({\mathcal{A}}^{c})+\operatorname{\mathsf{P}}({\mathcal{B}}^{c}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})+\operatorname{\mathsf{P}}({\mathcal{E}}_{1})\leq{\mathcal{O}}(\exp(-n^{c_{1}}))+{\mathcal{O}}(\exp(-n^{c_{2}}))+\delta=o(1),$

which completes the proof of Lemma IV.4. Along with Lemma IV.3, this implies
the result stated in Theorem II.4. ∎

##  V Extension to Varying $p$

In our main results for the $\mathsf{OR}$ problem and the $\mathsf{MAX}$
problem, we established tight achievability and converse results under the
assumptions that $\delta=o(1)$ and $p$ is a constant bounded away from $0$ and
$1/2$. In this section, we maintain the premise of a diminishing error
probability, $\delta=o(1)$, but explore scenarios where $p$ converges to
either zero or half as $n$ approaches infinity. Within this context, we delve
into the two problems while demonstrating that we can still derive matching
achievability and converse results—except in the specific instance where
$\frac{\log(1/\delta)}{\log(1/p)}=\Theta(1)$. Our subsequent discussion will
primarily revolve around the $\mathsf{OR}$ problem, with a parallel argument
applicable to the $\mathsf{MAX}$ problem.

#####  $p\rightarrow 1/2$ as $n\rightarrow\infty$

In this case, we can still show that $(1\pm
o(1))\frac{n\log{1/\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$ queries in expectation
are both necessary and sufficient for achieving a vanishing error probability
$\delta$. Firstly, the proof of Theorem II.1 does not use the constant
assumption on $p$, so the lower bound
$(1-o(1))\frac{n\log{1/\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$ still holds for
any $p$. Secondly, at most
$(1+o(1))\frac{n\log{1/\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$ in expectation can
still be achieved by the proposed NoisyOR algorithm. To see this, we focus on
the proof of Lemma III.4, where we analyze the expected number of queries of
the algorithm. Recall that in this proof, we bounded the number of queries
spent on Lines 3 and 11 using Lemmas III.1 and III.2 respectively. These two
lemmas hold for any $p$, and in the case of $p\rightarrow 1/2$, it is not hard
to see the the number of queries spent on Lines 3 and 11 are
$(1+o(1))\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}$ and
$o\left(\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right)$
respectively. Therefore, the total expected number of queries is at most
$(1+o(1))\frac{n\log{1/\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$.

#####  $p\rightarrow 0$ as $n\rightarrow\infty$

In the case of vanishing $p$, we will discuss three sub-cases separately.

Firstly, suppose that $\frac{\log(1/\delta)}{\log(1/p)}=\omega(1)$. In this
case, we still have that $(1\pm
o(1))\frac{n\log{1/\delta}}{{D_{\mathsf{KL}}(p\|1-p)}}$ queries in expectation
are both necessary and sufficient for achieving a vanishing error probability
$\delta$. The lower bound follows because Theorem II.1 holds for any $p$. The
upper bounded is achieved by the proposed NoisyOR algorithm for the same
reason as the case $p\rightarrow 1/2$.

Secondly, suppose that $\frac{\log(1/\delta)}{\log(1/p)}=o(1)$. In this case,
at least $n$ queries are necessary for achieving a vanishing error probability
$\delta$, while the proposed NoisyOR algorithm uses at most $(1+o(1))n$
queries in expectation. To see the lower bound, we notice that trivially each
of the $n$ bits must be queried at least once to achieve any error probability
$\delta<1/2$. To see the upper bound, we use Lemmas III.1 and III.2 to bound
the number of queries spent on Lines 3 and 11 of the NoisyOR algorithm
respectively. By Lemma III.1, we know that the expected number of queries
spent on Line 3 is at most

$\frac{n}{1-2p}\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil=\frac{n}{1-2p}=(1+o(1))n.$

By Lemma III.2, we know that the expected number of queries spent on Line 11
is at most

$C\left(\frac{\operatorname{\mathbb{E}}[|\mathcal{S}|]}{1-H(p)}+\frac{\operatorname{\mathbb{E}}[|\mathcal{S}|]\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\right)=O(\operatorname{\mathbb{E}}[|\mathcal{S}|])=o(n),$

where $\mathcal{S}$ denote the set of elements in ${\bf y}$, and the first
equality follows because $1-H(p)=\Theta(1)$ and
$\frac{\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}=\Theta(\frac{\log(1/\delta)}{\log(1/p)})$.
Therefore the expected number of queries made by NoisyOR algorithm is at most
$(1+o(1))n$.

Finally, suppose $\frac{\log(1/\delta)}{\log(1/p)}=\Theta(1)$. In this case,
the expected number of queries for achieving error probability $\delta$ is at
least
$\max\\{n,(1-o(1))\frac{n\log(1/\delta)}{{D_{\mathsf{KL}}(p\|1-p)}}\\}=\Theta(n)$,
while the expected number of queries of the proposed NoisyOR algorithm is at
most
$\frac{(1+o(1))n}{1-2p}\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil=\Theta(n)$.
So our upper and lower bounds are tight up to constant, but the exact constant
is still unknown. This untightness is because when
$\frac{\log(1/\delta)}{\log(1/p)}$ is a constant, the
$\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil$
term in Lemma III.1 cannot be upper bounded by
$(1+o(1))\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}$. How to get
the exact constant in this case is still an open problem.

## Acknowledgements

This work was supported in part by the NSERC Discovery Grant No.
RGPIN-2019-05448, the NSERC Collaborative Research and Development Grant CRDPJ
54367619, NSF Grant IIS-1901252 and NSF Grant CCF-1909499.

## References

  * Agarwal et al. (2017) A. Agarwal, S. Agarwal, S. Assadi, and S. Khanna.  Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons.  In _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pages 39–75. PMLR, 07–10 Jul 2017.
  * Audibert et al. (2010) J.-Y. Audibert, S. Bubeck, and R. Munos.  Best arm identification in multi-armed bandits.  In _COLT_ , pages 41–53, 2010.
  * Auer et al. (1995) P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire.  Gambling in a rigged casino: The adversarial multi-armed bandit problem.  In _Proceedings of IEEE 36th annual foundations of computer science_ , pages 322–331. IEEE, 1995.
  * Berlekamp (1964) E. R. Berlekamp.  _Block coding with noiseless feedback_.  Ph.D. thesis, MIT, Cambridge, MA, USA, 1964.
  * Bretagnolle and Huber (1979) J. Bretagnolle and C. Huber.  Estimation des densités: risque minimax.  _Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete_ , 47(2):119–137, 1979.  doi: 10.1007/BF00535278.
  * Bubeck et al. (2009) S. Bubeck, R. Munos, and G. Stoltz.  Pure exploration in multi-armed bandits problems.  In _International conference on Algorithmic learning theory_ , pages 23–37. Springer, 2009.
  * Burnashev and Zigangirov (1974) M. V. Burnashev and K. Zigangirov.  An interval estimation problem for controlled observations.  _Problemy Peredachi Informatsii_ , 10(3):51–61, 1974.
  * Dobrushin and Ortyukov (1977a) R. L. Dobrushin and S. Ortyukov.  Lower bound for the redundancy of self-correcting arrangements of unreliable functional elements.  _Problemy Peredachi Informatsii_ , 13(1):82–89, 1977a.
  * Dobrushin and Ortyukov (1977b) R. L. Dobrushin and S. Ortyukov.  Upper bound on the redundancy of self-correcting arrangements of unreliable functional elements.  _Problemy Peredachi Informatsii_ , 13(3):56–76, 1977b.
  * Evans and Pippenger (1998) W. Evans and N. Pippenger.  Average-case lower bounds for noisy boolean decision trees.  _SIAM Journal on Computing_ , 28(2):433–446, 1998\.
  * Falahatgar et al. (2017) M. Falahatgar, A. Orlitsky, V. Pichapati, and A. T. Suresh.  Maximum selection and ranking under noisy comparisons.  In D. Precup and Y. W. Teh, editors, _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1088–1096. PMLR, 06–11 Aug 2017.
  * Feige et al. (1994) U. Feige, P. Raghavan, D. Peleg, and E. Upfal.  Computing with noisy information.  _SIAM Journal on Computing_ , 23(5):1001–1018, 1994.
  * Gabillon et al. (2012) V. Gabillon, M. Ghavamzadeh, and A. Lazaric.  Best arm identification: A unified approach to fixed budget and fixed confidence.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Gács and Gál (1994) P. Gács and A. Gál.  Lower bounds for the complexity of reliable boolean circuits with noisy gates.  _IEEE Transactions on Information Theory_ , 40(2):579–583, 1994.
  * Garivier and Kaufmann (2016) A. Garivier and E. Kaufmann.  Optimal best arm identification with fixed confidence.  In _Conference on Learning Theory_ , 2016.
  * Gu and Xu (2023) Y. Gu and Y. Xu.  Optimal bounds for noisy sorting, 2023.  URL https://arxiv.org/abs/2302.12440.
  * Hastad et al. (1987) J. Hastad, T. Leighton, and M. Newman.  Reconfiguring a hypercube in the presence of faults.  In _Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing_ , STOC ’87, page 274–284, New York, NY, USA, 1987.
  * Heckel et al. (2019) R. Heckel, N. B. Shah, K. Ramchandran, and M. J. Wainwright.  Active ranking from pairwise comparisons and when parametric assumptions do not help.  _Ann. Stat._ , 47(6):3099 – 3126, 2019.
  * Horstein (1963) M. Horstein.  Sequential transmission using noiseless feedback.  _IEEE Trans. Inf. Theory_ , 9(3):136–143, 1963\.  doi: 10.1109/TIT.1963.1057832.
  * Jamieson and Nowak (2014) K. Jamieson and R. Nowak.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _48th Annual Conference on Information Sciences and Systems_ , pages 1–6, 2014.
  * Karp and Kleinberg (2007) R. M. Karp and R. Kleinberg.  Noisy binary search and its applications.  In _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’07, page 881–890, USA, 2007. Society for Industrial and Applied Mathematics.  ISBN 9780898716245.
  * Kaufmann et al. (2016) E. Kaufmann, O. Cappé, and A. Garivier.  On the complexity of best arm identification in multi-armed bandit models.  _Journal of Machine Learning Research_ , 17:1–42, 2016\.
  * Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * LeCam (1973) L. LeCam.  Convergence of estimates under dimensionality restrictions.  _The Annals of Statistics_ , pages 38–53, 1973.
  * Mitzenmacher and Upfal (2005) M. Mitzenmacher and E. Upfal.  _Probability and Computing: Randomized Algorithms and Probabilistic Analysis_.  Cambridge University Press, 2005.  doi: 10.1017/CBO9780511813603.
  * Mohajer et al. (2017) S. Mohajer, C. Suh, and A. Elmahdy.  Active learning for top-$k$ rank aggregation from noisy comparisons.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, page 2488–2497. JMLR.org, 2017.
  * Pease et al. (1980) M. Pease, R. Shostak, and L. Lamport.  Reaching agreement in the presence of faults.  _J. ACM_ , 27(2):228–234, April 1980.
  * Pelc (1989) A. Pelc.  Searching with known error probability.  _Theoretical Computer Science_ , 63(2):185–202, 1989.
  * Pippenger et al. (1991) N. Pippenger, G. D. Stamoulis, and J. N. Tsitsiklis.  On a lower bound for the redundancy of reliable networks with noisy gates.  _IEEE Transactions on Information Theory_ , 37(3):639–643, 1991.
  * Reischuk and Schmeltz (1991) R. Reischuk and B. Schmeltz.  Reliable computation with noisy circuits and decision trees-a general n log n lower bound.  In _[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science_ , pages 602–611. IEEE Computer Society, 1991.
  * Shah and Wainwright (2018) N. B. Shah and M. J. Wainwright.  Simple, robust and optimal ranking from pairwise comparisons.  _J. Mach. Learn. Res._ , 18(199):1–38, 2018.
  * Tsybakov (2004) A. B. Tsybakov.  Introduction to nonparametric estimation.  _Springer_ , 9(10), 2004.
  * Von Neumann (1956) J. Von Neumann.  Probabilistic logics and the synthesis of reliable organisms from unreliable components.  _Automata studies_ , 34:43–98, 1956.
  * Wang et al. (2022) Z. Wang, N. Ghaddar, and L. Wang.  Noisy sorting capacity.  In _2022 IEEE International Symposium on Information Theory (ISIT)_ , pages 2541–2546. IEEE, 2022.
  * Wang et al. (2023) Z. Wang, N. Ghaddar, B. Zhu, and L. Wang.  Variable-length insertion-based noisy sorting.  In _2023 IEEE International Symposium on Information Theory (ISIT)_ , pages 1782–1787, 2023.  doi: 10.1109/ISIT54713.2023.10206482.
  * Yu (1997) B. Yu.  Assouad, fano, and le cam.  In _Festschrift for Lucien Le Cam_ , pages 423–435. Springer, 1997\.
  * Zhu et al. (2023) B. Zhu, Z. Wang, N. Ghaddar, J. Jiao, and L. Wang.  On the optimal bounds for noisy computing, 2023.  URL https://arxiv.org/abs/2306.11951.

##  Appendix A Useful Lemmas

Here, we introduce several important lemmas.

######  Lemma A.1 (Le Cam’s Two Point Lemma, see e.g. (Yu, 1997)).

Let $\Theta$ and $\hat{\Theta}$ be arbitrary parameter spaces, and let
$L:\Theta\times\hat{\Theta}\to\mathbb{R}$ be any loss function. Suppose that
$\theta_{0},\theta_{1}\in\Theta$ satisfy the following separation condition:

$\displaystyle\forall{\hat{\theta}\in\hat{\Theta}},L(\theta_{0},\hat{\theta})+L(\theta_{1},\hat{\theta})\geq\Delta>0.$

Then we have

$\displaystyle\inf_{\hat{\theta}}\,\sup_{\theta}\,\mathbb{E}_{\theta}[L(\theta,\hat{\theta})]\geq\frac{\Delta}{2}\left(1-\mathsf{TV}(\mathbb{P}_{\theta_{0}},\mathbb{P}_{\theta_{1}})\right),$

where $\mathbb{P}_{\theta_{i}}$, $i\in\\{0,1\\}$, denotes the sample
distribution under the parameter $\theta_{i}$.

######  Lemma A.2 (Bretagnolle–Huber inequality ((Bretagnolle and Huber,
1979), and Lemma 2.6 in (Tsybakov, 2004))).

For any two distributions $\mathbb{P}_{1},\mathbb{P}_{2}$, one has

$\displaystyle\mathsf{TV}(\mathbb{P}_{1},\mathbb{P}_{2})\leq
1-\frac{1}{2}\exp\left(-D_{\mathsf{KL}}(\mathbb{P}_{1},\mathbb{P}_{2})\right).$

######  Lemma A.3 (Divergence Decomposition ((Auer et al., 1995), and Lemma
15.1 in Lattimore and Szepesvári (2020))).

Let $M_{i}$ be the random variable denoting the number of times experiment
$i\in[n]$ is performed under some policy $\pi$, then for two distributions
$\mathbb{P}^{\pi}$, $\mathbb{Q}^{\pi}$ under policy $\pi$,

$\displaystyle
D_{\mathsf{KL}}(\mathbb{P}^{\pi},\mathbb{Q}^{\pi})=\sum_{i\in[n]}\mathbb{E}_{\mathbb{P}^{\pi}}[M_{i}]D_{\mathsf{KL}}(\mathbb{P}_{i}^{\pi},\mathbb{Q}_{i}^{\pi}).$

######  Lemma A.4 (Chernoff bound (Mitzenmacher and Upfal, 2005)).

Let $Z\sim\mathrm{Binom}(n,p)$. For all $0<\delta<1$ and $\epsilon>0$, it
holds that

$\operatorname{\mathsf{P}}\left(Z\geq(1+\delta)np\right)\leq\exp\left(-\frac{\delta^{2}np}{3}\right),$

and

$\operatorname{\mathsf{P}}\left(Z\geq
n(p+\epsilon)\right)\leq\exp\big{(}-nD_{\mathsf{KL}}(p+\epsilon\|p)\big{)}.$

##  Appendix B Helper Lemmas for Theorem II.4

In this appendix, we prove Lemmas IV.5 and IV.6, which were used to complete
the proof of Theorem II.4.

###### Proof of Lemma IV.5.

Notice that

$\displaystyle\operatorname{\mathsf{P}}({\mathcal{A}}^{c})$
$\displaystyle=\operatorname{\mathsf{P}}\left(\mathrm{Binom}\left(n,\frac{1}{\log
n}\right)>\frac{n}{\log n}+n^{3/4}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\exp\left(-\frac{n^{1/2}\log
n}{3}\right),$

where $(a)$ follows from the multiplicative Chernoff bound (Lemma A.4 in
Appendix A). Hence,
$\operatorname{\mathsf{P}}({\mathcal{A}}^{c})={\mathcal{O}}(\exp(-n^{c_{1}}))$
for any constant $c_{1}<1/2$. ∎

###### Proof of Lemma IV.6.

Notice that on the event ${\mathcal{E}}_{1}^{c}$, we have that
$\hat{y}=y^{*}$. Define

$\displaystyle{\mathcal{X}}^{+}$
$\displaystyle\triangleq\\{x\in{\mathcal{S}}^{c}:x>y^{*}\\},$
$\displaystyle{\mathcal{X}}^{-}$
$\displaystyle\triangleq\\{x\in{\mathcal{S}}^{c}:x<y^{*}\\}.$

Notice that there are two types of elements in the set ${\mathcal{T}}$. The
first type consists of the elements $x\in{\mathcal{X}}^{+}$ appended into
${\mathcal{T}}$ because NoisyCompare$(y^{*},x,\delta)$ correctly outputs true.
The other type consists of the elements $x\in{\mathcal{X}}^{-}$ appended into
${\mathcal{T}}$ because NoisyCompare$(y^{*},x,\delta)$ incorrectly returns
true. By Lemma IV.1, the NoisyComparealgorithm returns an incorrect estimate
with probability at most $\delta$. Thus, $|{\mathcal{T}}|$ is statistically
dominated by the random variable
$|{\mathcal{X}}^{+}|+\mathrm{Binom}(|{\mathcal{X}}^{-}|,\delta)$. Next, we
derive large deviation bounds for $|{\mathcal{X}}^{+}|$ and
$\mathrm{Binom}(|{\mathcal{X}}^{-}|,\delta)$. First, notice that

$\displaystyle\operatorname{\mathsf{P}}(|{\mathcal{X}}^{+}|\geq\sqrt{n})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\left(1-\frac{1}{\log
n}\right)^{\sqrt{n}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\exp\left(-\frac{\sqrt{n}}{\log
n}\right),$

where (a) follows because the event $\\{|{\mathcal{X}}^{+}|\geq\sqrt{n}\\}$ is
equivalent to the event that the largest $\sqrt{n}$ elements are not sampled
into ${\mathcal{S}}$, and (b) follows by $1+x\leq\exp(x)$. Next, we have that

$\displaystyle\operatorname{\mathsf{P}}(\mathrm{Binom}(|{\mathcal{X}}^{-}|,\delta)\geq\delta
n+n^{3/4})$
$\displaystyle\leq\operatorname{\mathsf{P}}(\mathrm{Binom}(n,\delta)\geq\delta
n+n^{3/4})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\exp\left(-\frac{\sqrt{n}}{3}\right),$

where $(c)$ follows by the multiplicative Chernoff bound (Lemma A.4 in
Appendix A). Finally, the proof is completed by realizing that

$\displaystyle\operatorname{\mathsf{P}}({\mathcal{B}}^{c}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})$
$\displaystyle\leq\operatorname{\mathsf{P}}(|{\mathcal{X}}^{+}|+\mathrm{Binom}(|{\mathcal{X}}^{-}|,\delta)\geq\sqrt{n}+\delta
n+n^{3/4})$
$\displaystyle\leq\operatorname{\mathsf{P}}\left(\\{|{\mathcal{X}}^{+}|\geq\sqrt{n}\\}\cup\\{\mathrm{Binom}(|{\mathcal{X}}^{-}|,\delta)\geq\delta
n+n^{3/4}\\}\right)$
$\displaystyle\leq\operatorname{\mathsf{P}}(|{\mathcal{X}}^{+}|\geq\sqrt{n})+\operatorname{\mathsf{P}}(\mathrm{Binom}(|{\mathcal{X}}^{-}|,\delta)\geq\delta
n+n^{3/4})$ $\displaystyle\leq\exp\left(-\frac{\sqrt{n}}{\log
n}\right)+\exp\left(-\frac{\sqrt{n}}{3}\right),$

which implies that
$\operatorname{\mathsf{P}}({\mathcal{B}}^{c}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}{\mathcal{E}}_{1}^{c})={\mathcal{O}}(\exp(-n^{c_{2}}))$
for any constant $c_{2}<1/2$. ∎