# Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone
Functions

Hadley Black
University of California, Los Angeles
<EMAIL_ADDRESS>Supported by NSF award AF:Small 2007682, NSF Award:
Collaborative Research Encore 2217033.

###### Abstract

We study monotonicity testing of functions $f\colon\\{0,1\\}^{d}\to\\{0,1\\}$
using _sample-based_ algorithms, which are only allowed to observe the value
of $f$ on points drawn independently from the uniform distribution. A classic
result by Bshouty-Tamon (J. ACM 1996) proved that monotone functions can be
learned with $\exp(O(\min\\{\frac{1}{\varepsilon}\sqrt{d},d\\}))$ samples and
it is not hard to show that this bound extends to testing. Prior to our work
the only lower bound for this problem was $\Omega(\sqrt{\exp(d)/\varepsilon})$
in the small $\varepsilon$ parameter regime, when $\varepsilon=O(d^{-3/2})$,
due to Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky (Combinatorica 2000).
Thus, the sample complexity of monotonicity testing was wide open for
$\varepsilon\gg d^{-3/2}$. We resolve this question, obtaining a tight lower
bound of $\exp(\Omega(\min\\{\frac{1}{\varepsilon}\sqrt{d},d\\}))$ for all
$\varepsilon$ at most a sufficiently small constant. In fact, we prove a much
more general result, showing that the sample complexity of $k$_-monotonicity_
testing and learning for functions $f\colon\\{0,1\\}^{d}\to[r]$ is
$\exp(\Theta(\min\\{\frac{rk}{\varepsilon}\sqrt{d},d\\}))$. For testing with
one-sided error we show that the sample complexity is $\exp(\Theta(d))$.

Beyond the hypercube, we prove nearly tight bounds (up to polylog factors of
$d,k,r,1/\varepsilon$ in the exponent) of
$\exp(\widetilde{\Theta}(\min\\{\frac{rk}{\varepsilon}\sqrt{d},d\\}))$ on the
sample complexity of testing and learning measurable $k$-monotone functions
$f\colon\mathbb{R}^{d}\to[r]$ under product distributions. Our upper bound
improves upon the previous bound of
$\exp(\widetilde{O}(\min\\{\frac{k}{\varepsilon^{2}}\sqrt{d},d\\}))$ by Harms-
Yoshida (ICALP 2022) for Boolean functions ($r=2$).

###### Contents

  1. 1 Introduction
    1. 1.1 Results
      1. 1.1.1 Sample-Based Testing and Learning on the Hypercube
      2. 1.1.2 Sample-Based Testing and Learning in Continuous Product Spaces
    2. 1.2 Proof Overviews
      1. 1.2.1 The Testing Lower Bound for Hypercubes
      2. 1.2.2 The Learning Upper Bound for Product Spaces
    3. 1.3 Discussion and Open Questions
    4. 1.4 Related Work
    5. 1.5 Learning Functions with Bounded Image Size: Proof of Theorem 1.3
  2. 2 Preliminaries on $k$-Monotonicity
  3. 3 Lower Bound for Sample-Based Testers
    1. 3.1 The Distributions $\mathcal{D}_{\texttt{yes}}$ and $\mathcal{D}_{\texttt{no}}$
    2. 3.2 Proof of 3.2
    3. 3.3 $\mathcal{D}_{\texttt{yes}}$ and $\mathcal{D}_{\texttt{no}}$ are Hard to Distinguish: Proof of Lemma 3.5
    4. 3.4 Functions Drawn from $\mathcal{D}_{\texttt{no}}$ are Far from $k$-Monotone: Proof of Lemma 3.4
  4. 4 Learning Upper Bound over Product Spaces
    1. 4.1 Reduction to Hypergrids via Downsampling
    2. 4.2 Learning over Hypergrids
    3. 4.3 Putting it Together: Proof of Theorem 4.1
      1. 4.3.1 Proof of 4.8
  5. 5 Sample-Based Testing with One-Sided Error
  6. 6 Acknowledgements
  7. A Low-Degree Algorithm with RCN: Proof of Theorem 4.6
  8. B Coupon Collecting Learner: Proof of Lemma 4.3
  9. C Testing by Learning

##  1 Introduction

A function $f\colon{\cal X}\to\mathbb{R}$ over a partial order
$\mathcal{P}=({\cal X},\preceq)$ is $k$-_monotone_ if there does not exist a
chain of $k+1$ points $x_{1}\prec x_{2}\prec\cdots\prec x_{k+1}$ for which (a)
$f(x_{i+1})-f(x_{i})<0$ when $i$ is odd and (b) $f(x_{i+1})-f(x_{i})>0$ when
$i$ is even. When $k=1$, these are the _monotone_ functions, which are the
non-decreasing functions with respect to $\preceq$. Monotone and $k$-monotone
_Boolean_ functions over domains $\\{0,1\\}^{d}$, $[n]^{d}$, and
$\mathbb{R}^{d}$ have been the focus of a significant amount of research in
property testing and computational learning theory. We give an overview of the
literature in Section 1.4.

The field of property testing is concerned with the design and analysis of
sub-linear time randomized algorithms for determining if a function has, or is
far from having, some specific property. A key aspect in the definition of a
property testing algorithm is the type of access it has to the function. Early
works on property testing, e.g. [RS96, GGR98], focused on the notion of
_query-based_ testers, which are allowed to observe the value of the function
on any point of their choosing, and since then this has become the standard
model. The weaker notion of _sample-based_ testers, which can only view the
function on independent uniform samples, was also considered by [GGR98] and
has received some attention over the years, see e.g. [KR00, BBBY12, FLV15,
GR16, FH23]. Sample-based algorithms are considered more natural in many
settings, for example in computational learning theory, where they are the
standard model. In fact, sample-based testing and learning are closely related
problems; given a learning algorithm, it is always possible to design a
testing algorithm with the same sample complexity, up to an additive
$\text{poly}(1/\varepsilon)$ factor111See Lemma C.1 for a precise statement.
Also, note that if the learning algorithm is _proper_ , then the time
complexity is also preserved. If the learning algorithm is _improper_ , then
there is a time complexity blow-up, but the sample complexity is still
preserved..

For many fundamental properties, there is still a large gap between how much
we know in the query-based vs the sample-based models. Monotonicity (and
$k$-monotonicity) is such a property; despite a vast body of research on
query-based monotonicity testing over the hypercube $\\{0,1\\}^{d}$, the only
work we know of which considers this problem in the sample-based model is
[GGL+00], who gave an upper bound of $O(\sqrt{2^{d}/\varepsilon})$ and a
matching lower bound for the case when $\varepsilon=O(d^{-3/2})$ on the number
of samples needed to test monotonicity of functions
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$. The upper bound for learning monotone
Boolean functions due to [BT96, LRV22] also implies a testing upper bound of
$\exp(O(\frac{1}{\varepsilon}\sqrt{d}))$. Thus, this question has been wide
open for $\varepsilon\gg d^{-3/2}$.

Our work addresses this gap in the monotonicity testing literature, proving a
lower bound which matches the learning upper bound for all $\varepsilon$ at
most some constant. More generally, we prove tight lower bounds for
$k$-monotonicity testing of functions, $f\colon\\{0,1\\}^{d}\to[r]$, i.e.
functions with image size at most $r$. To round out our results, we also give
an improved learning algorithm for $k$-monotone functions over
$\mathbb{R}^{d}$ under product distributions whose sample complexity matches
our sample-based testing lower bound, up to poly-logarithmic factors in the
exponent.

###  1.1 Results

Before explaining our results and the context for them, we first provide some
terminology and basic notation. Given a domain ${\cal X}$ and a distribution
$\mu$ over ${\cal X}$, we denote the Hamming distance between two functions
$f,g\colon{\cal X}\to\mathbb{R}$ under $\mu$ by
$d_{\mu}(f,g)=\mathbb{P}_{x\sim\mu}[f(x)\neq g(x)]$. We say that $f$ is
$\varepsilon$-far from $k$-monotone if $d_{\mu}(f,g)\geq\varepsilon$ for every
$k$-monotone function $g$. The results in this paper pertain to sample-based
testing and learning of $k$-monotone functions with respect to Hamming
distance. We use the following terminology:

  * •

The _example oracle_ for $f$ under $\mu$, denoted by $EX(f,\mu)$, when
queried, generates an example $(x,f(x))$ where $x$ is sampled according to
$\mu$.

  * •

A _sample-based $k$-monotonicity tester_ under $\mu$ is a randomized algorithm
which is given access to $EX(f,\mu)$ for an arbitrary input function $f$ and
satisfies the following: (a) if $f$ is $k$-monotone, then the algorithm
accepts with probability at least $2/3$, and (b) if $f$ is $\varepsilon$-far
from $k$-monotone, then the algorithm rejects with probability at least $2/3$.
The tester has _one-sided error_ if in case (a) it accepts with probability
$1$.

  * •

A _sample-based learning algorithm for $k$-monotone functions_ under $\mu$ is
a randomized algorithm which is given access to $EX(f,\mu)$ for an arbitrary
$k$-monotone input function $f$ and outputs a hypothesis $h$ such that
$d_{\mu}(f,h)\leq\varepsilon$ with probability at least $1-\delta$. If left
unspecified, $\delta=1/3$.

In all of the above definitions if $\mu$ is unspecified, then it is the
uniform distribution. Testing and learning are closely related problems; any
sample-based learning algorithm can be used to construct a sample-based tester
with the same sample complexity. We refer to this transformation as the
testing-by-learning reduction and although this is not a new idea we provide a
proof in Appendix C for completeness.

####  1.1.1 Sample-Based Testing and Learning on the Hypercube

The problem of _learning_ monotone Boolean functions over the hypercube
$\\{0,1\\}^{d}$ was studied by [BT96] who proved an upper bound222We remark
that any function over $\\{0,1\\}^{d}$ can be learned exactly with
$O(d2^{d})=\exp(O(d))$ samples by a coupon-collector argument. Combining this
with the $\exp(O(\frac{1}{\varepsilon}\sqrt{d}))$ upper bound by [BT96] yields
$\exp(O(\min\\{\frac{1}{\varepsilon}\sqrt{d},d\\}))$. We use this slightly
clunkier notation involving the min to emphasize that our upper and lower
bounds are matching in all parameter regimes. of
$\exp(O(\min\\{\frac{1}{\varepsilon}\sqrt{d},d\\}))$ for improper learning and
very recently by [LRV22, LV23] who obtained the same upper bound for agnostic
proper learning. The improper learning upper bound was extended by [BCO+15]
who showed matching upper and lower bounds of
$\exp(\Theta(\min\\{\frac{k}{\varepsilon}\sqrt{d},d\\}))$ for learning
$k$-monotone Boolean functions for any $k\geq 1$. The testing-by-learning
reduction shows that their upper bound also holds for sample-based _testing_.
The only prior lower bound for sample-based testing that we’re aware of is
$\Omega(\sqrt{2^{d}/\varepsilon})$ when $\varepsilon=O(d^{-3/2})$ and $k=1$
[GGL+00, Theorem 5]. Our main result is the following much more general lower
bound for this problem, which we prove in Section 3.

######  Theorem 1.1 (Testing Lower Bound).

There is an absolute constant $c>0$ such that for all $\varepsilon\leq c$,
every sample-based $k$-monotonicity tester for functions
$f\colon\\{0,1\\}^{d}\to[r]$ under the uniform distribution has sample
complexity

$\exp\left(\Omega\left(\min\left\\{\frac{rk}{\varepsilon}\sqrt{d},d\right\\}\right)\right)\text{.}$

Even for the special case of sample-based monotonicity testing of Boolean
functions ($k=1$ and $r=2$), Theorem 1.1 is already a new result, which
matches the upper bound for learning by [BT96] and is the first lower bound to
hold for $\varepsilon\gg d^{-3/2}$. Moreover, our lower bound is much more
general, holding for all $r,k$, and is optimal in all parameters,
$d,r,k,\varepsilon$, up to a constant factor in the exponent. We show a
matching upper bound in Theorem 1.3.

We also note that the testing-by-learning reduction implies that the same
lower bound holds for _learning_ with samples. As we mentioned, this result
was already known for Boolean functions (the $r=2$ case) [BCO+15], but the
general case of $r\geq 2$ was not known prior to our work.

######  Corollary 1.2 (Learning Lower Bound).

There is an absolute constant $c>0$ such that for every $\varepsilon\leq c$,
every sample-based uniform-distribution learning algorithm for $k$-monotone
functions $f\colon\\{0,1\\}^{d}\to[r]$ has sample complexity

$\exp\left(\Omega\left(\min\left\\{\frac{rk}{\varepsilon}\sqrt{d},d\right\\}\right)\right)\text{.}$

On the upper bound side, a relatively straightforward argument extends the
learning algorithm of [BCO+15] for Boolean $k$-monotone functions, to
$k$-monotone functions with image size at most $r$. We give a short proof in
Section 1.5. This shows that our lower bounds in Theorem 1.1 and Corollary 1.2
are tight.

######  Theorem 1.3 (Learning Upper Bound for Hypercubes).

There is a uniform-distribution learning algorithm for $k$-monotone functions
$f\colon\\{0,1\\}^{d}\to[r]$ which achieves error at most $\varepsilon$ with
time and sample complexity

$\exp\left(O\left(\min\left\\{\frac{rk}{\varepsilon}\sqrt{d},d\right\\}\right)\right)\text{.}$

The testing-by-learning reduction again gives us the following corollary.

######  Corollary 1.4 (Testing Upper Bound for Hypercubes).

There is a sample-based $k$-monotonicity tester for functions
$f\colon\\{0,1\\}^{d}\to[r]$ with sample complexity

$\exp\left(O\left(\min\left\\{\frac{rk}{\varepsilon}\sqrt{d},d\right\\}\right)\right)\text{.}$

Lastly, we consider the problem of sample-based testing with _one-sided
error_. For monotonicity testing of functions
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ with _non-adaptive queries_ , we know that
one-sided and two-sided error testers achieve the same query-complexity (up to
$\text{polylog}(d,1/\varepsilon)$ factors): there is a
$\widetilde{O}(\sqrt{d}/\varepsilon^{2})$ one-sided error upper bound due to
[KMS18] and a $\widetilde{\Omega}(\sqrt{d})$ two-sided error lower bound due
to [CWX17]. We show that the situation is quite different for _sample-based_
monotonicity testing; while the sample complexity of two-sided error testers
is $\exp(\Theta(\min\\{\frac{1}{\varepsilon}\sqrt{d},d\\}))$, one-sided error
testers require $\exp(\Theta(d))$ samples for all $\varepsilon$.

######  Theorem 1.5 (Testing with One-Sided Error).

For every $d,r,k$, and $\varepsilon>0$, sample-based $k$-monotonicity testing
of functions $f\colon\\{0,1\\}^{d}\to[r]$ with one-sided error requires
$\exp(\Theta(d))$ samples.

####  1.1.2 Sample-Based Testing and Learning in Continuous Product Spaces

Learning $k$-monotone Boolean-valued functions has also been studied over
$\mathbb{R}^{d}$ with respect to product measures by [HY22] who gave an upper
bound of $\exp(\widetilde{O}(\min\\{\frac{k}{\varepsilon^{2}}\sqrt{d},d\\}))$
where $\widetilde{O}(\cdot)$ hides polylog factors of $d,k$, and
$1/\varepsilon$. Our next result gives an upper bound which improves the
dependence on $\varepsilon$ from $1/\varepsilon^{2}$ to $1/\varepsilon$ in the
exponent. By the same approach we used to generalize the upper bound in
Theorem 1.3 to arbitrary $r\geq 2$, we get the same generalization for product
spaces. We obtain the following upper bound which matches our lower bound for
$\\{0,1\\}^{d}$ in Theorem 1.1 up to polylog factors of $d,k,r$, and
$1/\varepsilon$. We say that a function $f\colon\mathbb{R}^{d}\to[r]$ is
_measurable_ if the set $f^{-1}(i)$ is measurable for every $i\in[r]$.

######  Theorem 1.6 (Learning Upper Bound for Product Spaces).

Given an arbitrary product measure $\mu$, there is a learning algorithm under
$\mu$ for measurable $k$-monotone functions $f\colon\mathbb{R}^{d}\to[r]$ with
time and sample complexity

$\exp\left(\widetilde{O}\left(\min\left\\{\frac{rk}{\varepsilon}\sqrt{d},d\right\\}\right)\right)\text{.}$

The $\widetilde{O}(\cdot)$ hides polylogarithmic dependencies on $d,r,k$, and
$1/\varepsilon$.

We prove Theorem 1.6 in Section 4. Once again the testing-by-learning
reduction gives us the following corollary for sample-based testing.

######  Corollary 1.7 (Testing Upper Bound for Product Spaces).

Given an arbitrary product measure $\mu$, there is a $k$-monotonicity tester
for measurable functions $f\colon\mathbb{R}^{d}\to[r]$ under $\mu$ with sample
complexity

$\exp\left(\widetilde{O}\left(\min\left\\{\frac{rk}{\varepsilon}\sqrt{d},d\right\\}\right)\right)\text{.}$

The $\widetilde{O}(\cdot)$ hides polylogarithmic dependencies on $d,r,k$, and
$1/\varepsilon$.

###  1.2 Proof Overviews

In this section we give an overview of our proofs for Theorem 1.1 and Theorem
1.6.

####  1.2.1 The Testing Lower Bound for Hypercubes

Our proof of Theorem 1.1 uses a family functions known as _Talagrand’s random
DNFs_ introduced by [Tal96] which have been used by [BB16] and [CWX17] to
prove lower bounds for monotonicity testing of Boolean functions
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ against adaptive and non-adaptive query-
based testers. Very recently, they have also been used to prove lower bounds
for tolerant testing by [CDL+23].

To understand our construction, let us first consider the special case of
monotonicity of Boolean functions, i.e. $k=1$ and $r=2$. We think of a DNF
term as a point $t\in\\{0,1\\}^{d}$ which is said to be satisfied by
$x\in\\{0,1\\}^{d}$ if $t\preceq x$, where $\preceq$ denotes the standard bit-
wise partial order over $\\{0,1\\}^{d}$. Consider $N$ randomly chosen terms
$t^{1},\ldots,t^{N}$ each of width $|t^{j}|=w$. We will see later how to
choose $N$ and $w$. Let
$B:=\\{x\colon\frac{d}{2}\leq|x|\leq\frac{d}{2}+\varepsilon\sqrt{d}\\}$ and
for each $j\in[N]$, let

$U_{j}:=\\{x\in B\colon t^{j}\preceq x\text{ and }t^{j^{\prime}}\not\preceq
x\text{ for all }j^{\prime}\neq j\\}$

be the set of points in $B$ which satisfy $t^{j}$ and no other terms. Let
$U:=\bigcup_{j\in[N]}U_{j}$. Now observe that any two points lying in
different $U_{j}$’s are _incomparable_ and therefore independently embedding
an arbitrary monotone function into each $U_{j}$ will result in a function
which globally is monotone if one defines the function outside of $U$
appropriately. Using this fact we can define two distributions
$\mathcal{D}_{\texttt{yes}}$ and $\mathcal{D}_{\texttt{no}}$ as follows. Let
$A$ denote the set of points in $x\in\\{0,1\\}^{d}$ for which either
$|x|>\frac{d}{2}+\varepsilon\sqrt{d}$ or $x\in B$ and
$t^{j},t^{j^{\prime}}\preceq x$ for two different terms $j\neq j^{\prime}$.

  * •

$f\sim\mathcal{D}_{\texttt{yes}}$ is drawn by setting $f(x)=1$ if and only if
$x\in A\cup\left(\bigcup_{j\in T}U_{j}\right)$ where $T\subseteq[N]$ contains
each $j\in[N]$ with probability $1/2$, independently. Such a function is
always monotone.

  * •

$f\sim\mathcal{D}_{\texttt{no}}$ is drawn by setting $f(x)=1$ if and only if
$x\in A\cup R$ where $R$ contains each $x\in U$ with probability $1/2$,
independently. Such a function will be $\Omega(|U|\cdot 2^{-d})$-far from
monotone with probability $\Omega(1)$ since its restriction with $U$ is
uniformly random.

Now, each $x\in U$ satisfies
$\mathbb{P}_{f\sim\mathcal{D}_{\texttt{yes}}}[f(x)=1]=\mathbb{P}_{f\sim\mathcal{D}_{\texttt{no}}}[f(x)=1]=1/2$
and for both distributions the events $f(x)=1$ and $f(y)=1$ are independent
when $x,y$ lie in different $U_{j}$’s. Therefore, any tester will need to see
at least two points from the same $U_{j}$ to distinguish
$\mathcal{D}_{\texttt{yes}}$ and $\mathcal{D}_{\texttt{no}}$. Roughly
speaking, by birthday paradox this gives a $\Omega(\sqrt{N})$ lower bound on
the number of samples. The lower bound is thus determined by the maximum
number of terms $N$ that can be used in the construction for which
$|U|=\Omega(\varepsilon 2^{d})$.

So how are $N$ and $w$ chosen? By standard concentration bounds, we have
$|B|=\Omega(\varepsilon 2^{d})$ and observe that a point $x\in B$ satisfies a
random term with probability exactly $(|x|/d)^{w}$. We need $U$ to contain a
_constant fraction_ of $B$, i.e. we need $x$ to satisfy exactly $1$ term with
constant probability. The expected number of satisfied terms is
$N\cdot(|x|/d)^{w}$ and, roughly speaking, we need this value to be
$\Theta(1)$ for all $x\in B$. Applying this constraint to the case when
$|x|=d/2$ forces us to pick $N\approx 2^{w}$. Now when
$|x|=d/2+\varepsilon\sqrt{d}$, the expected number of satisfied terms is
$N\cdot
2^{-w}\cdot(1+2\varepsilon/\sqrt{d})^{w}\approx(1+2\varepsilon/\sqrt{d})^{w}$
and we are forced to choose $w\approx\sqrt{d}/\varepsilon$. The lower bound
for sample-based monotonicity testing of $f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ is
then $\Omega(\sqrt{N})\approx\exp(\Omega(\sqrt{d}/\varepsilon))$.

Let us now think about generalizing this construction to testing
$k$-monotonicity of functions $f\colon\\{0,1\\}^{d}\to[r]$. The moral of the
above argument is that the permitted number of terms is controlled by the
number of distinct Hamming weights in the set $B$. We observe that for larger
values of $k$ and $r$ we can partition $B$ into $k(r-1)$ blocks as
$B:=B_{1}\cup B_{2}\cup\cdots\cup B_{k(r-1)}$ each with a window of Hamming
weights of size only $\frac{\varepsilon\sqrt{d}}{k(r-1)}$. We are able to
essentially repeat the above construction independently within each block
wherein we can set $w\approx\frac{k(r-1)\sqrt{d}}{\varepsilon}$ and
consequently $N\approx 2^{\frac{k(r-1)\sqrt{d}}{\varepsilon}}$.

For each block $i\in[k(r-1)]$, the random Talagrand DNF within block $B_{i}$
is defined analogously to the above construction, except that it assigns
function values from $\\{i\bmod{(r-1)},i\bmod{(r-1)}+1\\}$, instead of
$\\{0,1\\}$. See Fig. 1 for an illustration. Since there are $k(r-1)$ blocks
in total, the distribution $\mathcal{D}_{\texttt{yes}}$ only produces
$k$-monotone functions. At the same time, a function
$f\sim\mathcal{D}_{\texttt{no}}$ assigns uniform random $\\{a,a+1\\}$ values
within each block $B_{m(r-1)+a}$. This results in a large number of long
chains through $B_{a}\cup B_{(r-1)+a}\cup\cdots\cup B_{(k-1)(r-1)+a}$ which
alternate between function value $a$ and $a+1$. Considering the union of all
such chains for $a=0,1,\ldots,r-2$ shows that $f$ is $\Omega(\varepsilon)$-far
from $k$-monotone with probability $\Omega(1)$.

Figure 1: An illustration of the construction used in our proof of Theorem
1.1. The image represents the set of points in the hypercube $\\{0,1\\}^{d}$
with Hamming weight in the interval
$[\frac{d}{2},\frac{d}{2}+\varepsilon\sqrt{d})$, increasing from bottom to
top. The numbers on the left denote the Hamming weight of the points lying in
the adjacent horizontal line. The $B_{i}$ blocks are the sets of points
contained between two adjacent horizontal lines. Each orange shaded region
within $B_{i}$ represents the set of points satisfied by a term $t^{i,j}$. The
blue numbers represent the value that functions in the support of
$\mathcal{D}_{\texttt{yes}}$ and $\mathcal{D}_{\texttt{no}}$ can take. We have
used the notation ?$r-1,2$? as shorthand for $r-2,r-1$.

####  1.2.2 The Learning Upper Bound for Product Spaces

As we discussed in Section 1.1, it suffices to prove Theorem 1.6 for the case
of $r=2$, i.e. learning functions $f\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ under
a product measure $\mu$. We use a downsampling technique to reduce this
problem to learning a discretized proxy of $f$ over a hypergrid $[N]^{d}$
where $N=\Theta(kd/\varepsilon)$ with mild label noise. This technique has
been used in previous works [GKW19, BCS20, HY22] and our proof borrows many
technical details from [HY22].

Next, for $N$ which is a power of $2$, we observe that a $k$-monotone function
$f\colon[N]^{d}\to\\{\pm 1\\}$ can be viewed as a $k$-monotone function over
the hypercube $\\{\pm 1\\}^{d\log N}$ by mapping each point $x\in[N]^{d}$ to
its bit-representation. We can then leverage a result of [BCO+15] which shows
that all but a $\varepsilon$-fraction of the mass of the Fourier coefficients
of $k$-monotone Boolean functions $f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ is
concentrated on the terms with degree at most $\frac{k\sqrt{d}}{\varepsilon}$.
We can then use the Low-Degree Algorithm introduced by [LMN93] which was shown
to work under random classification noise by [Kea98].

###  1.3 Discussion and Open Questions

Our results for sample-based testing and learning over the hypercube are tight
up to _constant factors_ in the exponent. Our upper bound for product spaces
matches the lower bound for hypercubes only up to _polylog_ factors of
$d,k,r,1/\varepsilon$ in the exponent. In particular, the upper bound for
product spaces goes to $\infty$ as any one of the parameters $r$, $k$, or
$1/\varepsilon$ grow to $\infty$, whereas the lower bound for the hypercube
can be at most $\exp(\Theta(d))$ simply because $|\\{0,1\\}^{d}|=2^{d}$ and so
any function $f\colon\\{0,1\\}^{d}\to\mathbb{R}$ can be learned _exactly_ with
$\exp(O(d))$ samples. It seems intuitive that sample-based testing and
learning of $k$-monotone functions over $[n]^{d}$ should require
$n^{\Omega(d)}$ samples as either of the parameters $k$ or $r$ approaches
$\infty$. A corollary of such a result would be that the sample-complexity of
these problems for $f\colon\mathbb{R}^{d}\to[r]$ grow to $\infty$ as $k$ or
$r$ approach $\infty$. Moreover, if this is true, then $k$-monotonicity of
functions $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is not testable with a finite
number of samples. Our results do not address this and it would be interesting
to investigate this further.

######  Question 1.8.

Is there a lower bound for sample-based $k$-monotonicity testing of functions
$f\colon[n]^{d}\to[r]$ which approaches $n^{\Omega(d)}$ as $r$ or $k$ go to
$\infty$?

###  1.4 Related Work

Monotone functions and their generalization to $k$-monotone functions have
been extensively studied within property testing and learning theory over the
last 25 years. We highlight some of the results which are most relevant to our
work. Afterwards, we discuss some selected works on sample-based property
testing.

##### Sample-based monotonicity testing:

Sample-based monotonicity testing of Boolean functions over the hypercube,
$\\{0,1\\}^{d}$, was considered by [GGL+00] (see [GGL+00, Theorems 5 and 6])
who gave an upper bound of $O(\sqrt{2^{d}/\varepsilon})$ and a lower bound of
$\Omega(\sqrt{2^{d}/\varepsilon})$ for $\varepsilon=O(d^{-3/2})$. Sample-based
monotonicity testing over general partial orders was studied by [FLN+02] who
gave a $O(\sqrt{N/\varepsilon})$ one-sided error tester for functions $f\colon
D\to\mathbb{R}$ where $D$ is any partial order on $N$ elements. Sample-based
monotonicity testing of functions on the line $f\colon[n]\to[r]$ was studied
by [PRV18] who gave a one-sided error upper bound of $O(\sqrt{r/\varepsilon})$
and a matching lower bound of $\Omega(\sqrt{r})$ for all sample-based testers.

##### Query-based monotonicity testing:

Monotonicity testing has been extensively studied in the standard query model
[Ras99, EKK+00, GGL+00, DGL+99, LR01, FLN+02, HK03, AC06, HK08, ACCL07, Fis04,
SS08, Bha08, BCSM12, FR10, BBM12, RRSW11, BGJ+12, CS13, CS14a, CST14, BRY14a,
BRY14b, CDST15, CDJS15, KMS15, BB16, CWX17, BCS18, PRV18, BCS20, HY22, BKR23,
BKKM23, BCS23b, BCS23a, CDL+23]. When discussing these works we treat
$\varepsilon$ as a small constant for brevity. For
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$, the non-adaptive query complexity has been
established at $\widetilde{\Theta}(\sqrt{d})$ [KMS18, CWX17] with an adaptive
lower bound of $\widetilde{\Omega}(d^{1/3})$ [CWX17]. This gap for adaptive
monotonicity testing of Boolean functions is still an outstanding open
question. For $f\colon[n]^{d}\to\\{0,1\\}$ and
$f\colon\mathbb{R}^{d}\to\\{0,1\\}$ under product measures, a recent result of
[BCS23a] established a non-adaptive upper bound of $d^{1/2+o(1)}$. For
functions $f\colon\\{0,1\\}^{d}\to[r]$, [BKR23] showed upper and lower bounds
of $\widetilde{\Theta}(\min(r\sqrt{d},d))$ for non-adaptive, one-sided error
testers and there is a general (adaptive) lower bound of
$\Omega(\min(d,r^{2}))$ due to [BBM12]. For real-valued functions
$f\colon[n]^{d}\to\mathbb{R}$, the query complexity is known to be
$\Theta(d\log n)$. The upper bound is non-adaptive [CS13] and the lower bound
holds even for adaptive testers [CS14b].

#####  $k$-Monotonicity testing:

The generalization to $k$-monotonicity testing has also been studied in the
standard query model by [GKW19, CGG+19]. These works show that the query-
complexity of non-adaptive one-sided error $k$-monotonicity testing is
$\exp(\widetilde{\Theta}(\sqrt{d}))$ for all $k\geq 2$, demonstrating an
interesting separation between (1-)monotonicity and 2-monotonicity.

##### Learning monotone functions:

Monotone Boolean functions $f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ were studied in
the context of learning theory by [BT96] who showed that they can be
(improperly) learned to error $\varepsilon$ under the uniform distribution
with $\exp(O(\frac{1}{\varepsilon}\sqrt{d}))$ time and samples. Very recent
works [LRV22, LV23] have given _agnostic proper_ learning algorithms with the
same complexity.

##### Learning $k$-monotone functions:

The result of [BT96] was generalized by [BCO+15] who gave upper and lower
bounds of $\exp(\Theta(\frac{k}{\varepsilon}\sqrt{d}))$ for learning
$k$-monotone Boolean functions $f\colon\\{0,1\\}^{d}\to\\{0,1\\}$. For Boolean
functions over hypergrids $f\colon[n]^{d}\to\\{0,1\\}$, [CGG+19] gave an upper
bound of $\exp(\widetilde{O}(\min(\frac{k}{\varepsilon^{2}}\sqrt{d},d)))$
where $\widetilde{O}(\cdot)$ hides polylog factors of $d,k,1/\varepsilon$.
This result was generalized to functions $f\colon\mathbb{R}^{d}\to\\{0,1\\}$
under product measures by [HY22].

##### Sample-based property testing:

The notion of sample-based property testing was first presented and briefly
studied by [GGR98]. Broader studies of sample-based testing and its
relationship with query-based testing have since been given by [FGL14, FLV15,
GR16]. A characterization of properties which are testable with a constant
number of samples was given by [BY19].

As we mentioned, sample-based algorithms are the standard model in learning
theory, and learning requires at least as many samples as testing for every
class of functions. Thus, it is natural to ask, when is testing _easier_ than
learning in terms of sample complexity? This question is referred to as
_testing vs learning_ and has been studied by [KR00] and more recently by
[BFH21, FH23].

There has also been work studying models that interpolate between query-based
and sample-based testers. For instance, [BBBY12] introduced the notion of
_active testing_ , where the tester may make queries, but only on points from
a polynomial-sized batch of unlabeled samples drawn from the underlying
distribution. This was inspired by the notion of _active learning_ which
considers learning problems under this access model.

Sample-based convexity testing of sets over various domains has also seen some
recent attention [CFSS17, BMR19a, BMR19b, BBH23].

###  1.5 Learning Functions with Bounded Image Size: Proof of Theorem 1.3

In this section we give a short proof showing that the learning algorithm of
[BCO+15] can be extended in a relatively straightforward manner to functions
$f\colon\\{0,1\\}^{d}\to[r]$ by increasing the sample-complexity by a factor
of $r$ in the exponent.

###### Proof of Theorem 1.3.

[BCO+15, Theorem 1.4] proved this result for the case of $r=2$. By standard
arguments, their theorem can be strengthened slightly so that with probability
at least $1-\delta$, the learner outputs a hypothesis with error at most
$\varepsilon$, and the time and sample complexity is only larger by a
multiplicative factor of $\text{poly}(\varepsilon^{-1},\delta^{-1})$. We will
need this slightly stronger statement.

For each $t\in[r]$, let $f_{t}\colon\\{0,1\\}^{d}\to\\{0,1\\}$ denote the
thresholded Boolean function defined as $f_{t}(x):=\mathbf{1}(f(x)\geq t)$.
Observe that for all $x\in\\{0,1\\}^{d}$ we have
$f(x)=\text{argmax}_{t}\\{f_{t}(x)=1\\}$. Thus, for each $t\in[r]$, run the
learning algorithm of [BCO+15] with error parameters set to
$\varepsilon^{\prime}:=\varepsilon/r$ and $\delta=1/3r$ to obtain a hypothesis
$h_{t}$. We have $\mathbb{P}[d(h_{t},f_{t})>\varepsilon/r]<1/3r$. By a union
bound, with probability at least $2/3$, every $t\in[r]$ satisfies
$d(h_{t},f_{t})\leq\varepsilon/r$. Moreover, if this holds then by another
union bound we have $\mathbb{P}_{x}[\exists t\in[r]\colon h_{t}(x)\neq
f(x)]\leq\varepsilon$. Thus, the hypothesis
$h(x):=\text{argmax}_{t}\\{h_{t}(x)=1\\}$ satisfies $d(h,f)\leq\varepsilon$.
The number of samples used is
$\text{poly}(\varepsilon^{-1},r)\cdot\exp(O(\min\\{\frac{k}{\varepsilon^{\prime}}\sqrt{d},d\\}))$
and this completes the proof. ∎

##  2 Preliminaries on $k$-Monotonicity

We use the notation $[n]:=\\{0,1,\ldots,n-1\\}$.

######  Definition 2.1.

Given a poset $\mathcal{P}=({\cal X},\preceq)$ and a function $f\colon{\cal
X}\to\mathbb{R}$, an $m$-alternating chain is a sequence of points $x_{1}\prec
x_{2}\prec\cdots\prec x_{m}$ such that for all $i\in\\{1,\ldots,m-1\\}$,

  1. 1.

$f(x_{i+1})-f(x_{i})<0$ when $i$ is odd, and

  2. 2.

$f(x_{i+1})-f(x_{i})>0$ when $i$ is even.

######  Definition 2.2 ($k$-monotonicity).

For a poset $\mathcal{P}=({\cal X},\preceq)$, a function $f\colon{\cal
X}\to\mathbb{R}$ is called $k$-monotone if it does not have any
$(k+1)$-alternating chains.

Let ${\cal M}_{\mathcal{P},k}$ denote the set of all $k$-monotone functions
$f\colon{\cal X}\to\mathbb{R}$ over the poset $\mathcal{P}=({\cal
X},\preceq)$. The Hamming distance between two functions $f,g\colon{\cal
X}\to\mathbb{R}$ is $d(f,g)=|{\cal X}|^{-1}\cdot|\\{x\in{\cal X}\colon
f(x)\neq g(x)\\}|$. The distance to $k$-monotonicity of $f$ is denoted by
$\varepsilon(f,{\cal M}_{\mathcal{P},k}):=\min_{g\in{\cal
M}_{\mathcal{P},k}}d(f,g)$. The following claim is our main tool for lower
bounding the distance to $k$-monotonicity.

######  Claim 2.3.

Let $f\colon{\cal X}\to\mathbb{R}$ and $k^{\prime}\geq 3k$ be an integer. Let
${\cal C}\subset{\cal X}^{k^{\prime}}$ be a collection of disjoint
$k^{\prime}$-alternating chains for $f$. Then

$\varepsilon(f,{\cal M}_{\mathcal{P},k})\geq\frac{1}{3|{\cal
X}|}\cdot\left|\bigcup_{C\in{\cal C}}C\right|\text{.}$

###### Proof.

Observe that every $k$-monotone function $g\in{\cal M}_{\mathcal{P},k}$ has
the following property: for every
$C=(x_{1},x_{2},\ldots,x_{k^{\prime}})\in{\cal C}$, the sequence

$\big{(}1,g(x_{2})-g(x_{1}),g(x_{3})-g(x_{2}),\ldots,g(x_{k^{\prime}})-g(x_{k^{\prime}-1})\big{)}$

changes sign at most $k-1$ times, whereas the sequence

$\big{(}1,f(x_{2})-f(x_{1}),f(x_{3})-f(x_{2}),\ldots,f(x_{k^{\prime}})-f(x_{k^{\prime}-1})\big{)}$

changes sign exactly $k^{\prime}-1$ times. We have prepended a $1$ so that the
first sign change occurs as soon as the function value decreases. Now,
changing $f(x_{i})$ can only reduce the number of times the sequence changes
sign by at most $2$ and so $|\\{i\colon f(x_{i})\neq
g(x_{i})\\}|\geq\frac{k^{\prime}-k}{2}$. Summing over all chains in ${\cal C}$
and normalizing yields

$d(f,g)\geq\frac{k^{\prime}-k}{2}\cdot\frac{|{\cal C}|}{|{\cal
X}|}\geq\frac{k^{\prime}}{3}\cdot\frac{|{\cal C}|}{|{\cal
X}|}\geq\frac{1}{3|{\cal X}|}\cdot\left|\bigcup_{C\in{\cal C}}C\right|$

where the second inequality follows from $k\leq k^{\prime}/3$ and the third
inequality is due to the fact that the chains in ${\cal C}$ are all disjoint
and each of size $k^{\prime}$. This completes the proof since this inequality
holds for all $g\in{\cal M}_{\mathcal{P},k}$. ∎

We use the notation $\mathcal{M}_{r,k}$ to denote the set of all $k$-monotone
functions $f\colon\\{0,1\\}^{d}\to[r]$ over the hypercube whose image has at
most $r$ distinct values.

##  3 Lower Bound for Sample-Based Testers

In this section we prove Theorem 1.1, our lower bound on the sample-complexity
of testing $k$-monotonicity of functions $f\colon\\{0,1\\}^{d}\to[r]$. Our
proof follows the standard approach of defining a pair of distributions
$\mathcal{D}_{\texttt{yes}},\mathcal{D}_{\texttt{no}}$ over functions
$f\colon\\{0,1\\}^{d}\to[r]$ which satisfy the following:

  * •

$\mathcal{D}_{\texttt{yes}}$ is supported over $k$-monotone functions.

  * •

Functions drawn from $\mathcal{D}_{\texttt{no}}$ are typically
$\Omega(\varepsilon)$-far from $k$-monotone:
$\mathbb{P}_{f\sim\mathcal{D}_{\texttt{no}}}[\varepsilon(f,{\cal
M}_{r,k})=\Omega(\varepsilon)]=\Omega(1)$.

  * •

The distributions over labeled examples from $\mathcal{D}_{\texttt{yes}}$ and
$\mathcal{D}_{\texttt{no}}$ are close in TV-distance.

Our construction uses a generalized version of a family functions known as
random Talagrand DNFs, which were used by [BB16] and [CWX17] to prove lower
bounds for testing monotonicity of Boolean functions with adaptive and non-
adaptive queries.

Let $r,k$ satisfy $rk\leq\frac{\varepsilon\sqrt{d}}{4800}$. For convenience,
we will assume that $\frac{k(r-1)}{\varepsilon}$ and $\sqrt{d}$ are integers
and that $\frac{k(r-1)}{\varepsilon}$ divides $\sqrt{d}$. Let
$L_{\ell}:=\left\\{x\in\\{0,1\\}^{d}\colon|x|=\ell\right\\}$ denote the
$\ell$’th Hamming level of the hypercube. We partition
$\bigcup_{\ell\in[0,\varepsilon\sqrt{d})}L_{d/2+\ell}$ into $k(r-1)$ blocks as
follows. For each $i\in[k(r-1)]$, define

$B_{i}=\bigcup_{\ell=i\cdot\frac{\varepsilon\sqrt{d}}{k(r-1)}}^{(i+1)\cdot\frac{\varepsilon\sqrt{d}}{k(r-1)}-1}L_{\frac{d}{2}+\ell}\text{.}$

The idea of our proof is to define a random DNF within each $B_{i}$. The
_width_ of each DNF will be set to $w:=\frac{(r-1)k\sqrt{d}}{2\varepsilon}$
and for each $i$, the number of terms in the DNF within $B_{i}$ will be set to
$N_{i}:=2^{w}\cdot e^{-i}=2^{\frac{(r-1)k\sqrt{d}}{2\varepsilon}(1-o(1))}$.
The DNF defined over $B_{i}$ will assign function values from
$\\{i\bmod{(r-1)},i\bmod{(r-1)}+1\\}$. The terms in each DNF will be chosen
randomly from the following distribution. We think of terms as points
$t\in\\{0,1\\}^{d}$ in the hypercube where another point $x$ _satisfies_ $t$
if $t\preceq x$, i.e. $t_{i}=1$ implies $x_{i}=1$.

######  Definition 3.1 (Term distribution).

A term $t\in\\{0,1\\}^{d}$ is sampled from the distribution
$\mathcal{D}_{\texttt{term}}$ as follows. Form a (multi)-set $S\subseteq[d]$
by choosing $w$ independent uniform samples from $[d]$. For each $a\in[d]$,
let $t_{a}:=\mathbf{1}(a\in S)$.

###  3.1 The Distributions $\mathcal{D}_{\texttt{yes}}$ and
$\mathcal{D}_{\texttt{no}}$

We now define the yes and no distributions over functions
$f\colon\\{0,1\\}^{d}\to[r]$. For each $i\in[k(r-1)]$, choose terms
$t^{i,1},\ldots,t^{i,N_{i}}$ i.i.d. from $\mathcal{D}_{\texttt{term}}$ and let
$\boldsymbol{t}=\\{t^{i,j}\colon i\in[k(r-1)]\text{, }j\in[N_{i}]\\}$ denote
the random set of all terms. Now, for each $i\in[k(r-1)]$ and $j\in[N_{i}]$,
define the set

$\displaystyle U_{i,j}=\left\\{x\in B_{i}\colon x\succeq t^{i,j}\text{ and
}x\not\succeq t^{i,j^{\prime}}\text{ for all }j^{\prime}\neq j\right\\}$ (1)

of all points in the $i$’th block that satisfy the $j$’th term _uniquely_. Let
$U_{i}=\bigcup_{j\in[N_{i}]}U_{i,j}$ denote the set of points in $B_{i}$ that
satisfy a unique term. The following claim is key to our result and motivates
our choice of $w$ and $N_{i}$. We defer its proof to Section 3.2.

######  Claim 3.2.

For any $i\in[k(r-1)]$, $j\in[N_{i}]$, and $x\in B_{i}$, we have

$\frac{1}{20N_{i}}\leq\mathbb{P}_{\boldsymbol{t}}[x\in
U_{i,j}]\leq\frac{3}{N_{i}}\text{.}$

As a corollary, we have $\mathbb{P}_{\boldsymbol{t}}[x\in U_{i}]\geq 1/20$.

Functions drawn from $\mathcal{D}_{\texttt{yes}}$ are generated as follows.
For each $i\in[k(r-1)]$ choose a uniform random assignment

$\boldsymbol{\phi}_{i}\colon[N_{i}]\to\left\\{i\bmod(r-1),i\bmod(r-1)+1\right\\}\text{
and let }\boldsymbol{\phi}=(\boldsymbol{\phi}_{i}\colon i\in[k(r-1)])\text{.}$

For every $x\in B_{i}$ define

$f_{\boldsymbol{t},\boldsymbol{\phi}}(x)=\begin{cases}i\bmod(r-1),&\text{if
}\forall j\in[N_{i}]\text{, }x\not\succeq t^{i,j}\\\ i\bmod(r-1)+1,&\text{if
}\exists j\neq j^{\prime}\in[N_{i}]\text{, }x\succeq
t^{i,j},t^{i,j^{\prime}}\\\ \boldsymbol{\phi}_{i}(j),&\text{if }x\in
U_{i,j}\text{.}\end{cases}$

Functions drawn $\mathcal{D}_{\texttt{no}}$ are generated as follows. For each
$i\in[k(r-1)]$ choose a uniform random function

$\boldsymbol{r}_{i}\colon
U_{i}\to\left\\{i\bmod(r-1),i\bmod(r-1)+1\right\\}\text{ and let
}\boldsymbol{r}=(\boldsymbol{r}_{i}\colon i\in[k(r-1)])\text{.}$

For each $x\in B_{i}$ define

$f_{\boldsymbol{t},\boldsymbol{r}}(x)=\begin{cases}i\bmod(r-1),&\text{if
}\forall j\in[N_{i}]\text{, }x\not\succeq t^{i,j}\\\ i\bmod(r-1)+1,&\text{if
}\exists j\neq j^{\prime}\in[N_{i}]\text{, }x\succeq
t^{i,j},t^{i,j^{\prime}}\\\ \boldsymbol{r}_{i}(x),&\text{if }x\in
U_{i}\text{.}\end{cases}$

For $x$ not belonging to any $B_{i}$: if $|x|<\frac{d}{2}$, then both the yes
and no distributions assign value $0$ and if
$|x|\geq\frac{d}{2}+\varepsilon\sqrt{d}$, then both the yes and no
distributions assign value $r-1$.

In summary, a function
$f_{\boldsymbol{t},\boldsymbol{\phi}}\sim\mathcal{D}_{\texttt{yes}}$ assigns
the same random value
$\boldsymbol{\phi}_{i}(j)\in\\{i\bmod(r-1),i\bmod(r-1)+1\\}$ to all points in
$U_{i,j}$, which results in a $k$-monotone function, whereas a function
$f_{\boldsymbol{t},\boldsymbol{r}}\sim\mathcal{D}_{\texttt{no}}$ assigns an
i.i.d. uniform random $\\{i\bmod(r-1),i\bmod(r-1)+1\\}$-value to each point in
$U_{i}$, resulting in a function that is far from being $k$-monotone. By
construction, to detect any difference between these cases a tester will need
to sample at least two points from the same $U_{i,j}$. Theorem 1.1 follows
immediately from the following three lemmas.

######  Lemma 3.3.

Every function in the support of $\mathcal{D}_{yes}$ is $k$-monotone.

###### Proof.

Consider any
$f_{\boldsymbol{t},\boldsymbol{\phi}}(x)\in\text{supp}(\mathcal{D}_{\texttt{yes}})$.
For each $a\in[k]$, consider the union of $r-1$ blocks formed by

$Y_{a}:=B_{a(r-1)}\cup B_{a(r-1)+1}\cup\cdots\cup B_{(a+1)(r-1)-1}\text{.}$

Recall that if $|x|<d/2$, then $f_{\boldsymbol{t},\boldsymbol{\phi}}(x)=0$ and
if $|x|\geq d/2+\varepsilon\sqrt{d}$, then
$f_{\boldsymbol{t},\boldsymbol{\phi}}(x)=r-1$. If
$d/2\leq|x|<d/2+\varepsilon\sqrt{d}$, then $x\in\bigcup_{a\in[k]}Y_{a}$.
Therefore, it suffices to show that for any pair of comparable points $x\prec
y\in Y_{a}$, we have $f_{\boldsymbol{t},\boldsymbol{\phi}}(x)\leq
f_{\boldsymbol{t},\boldsymbol{\phi}}(y)$. Firstly, observe that by
construction all points $z\in B_{a(r-1)+b}$ have function value
$f_{\boldsymbol{t},\boldsymbol{\phi}}(z)\in\\{b,b+1\\}$. Since $x\prec y$, if
$x$ and $y$ are in different blocks, then $x\in B_{a(r-1)+b}$ and $y\in
B_{a(r-1)+b^{\prime}}$ where $b<b^{\prime}$ and so the inequality is
satisfied. Therefore, we may assume $x,y\in B_{a(r-1)+b}$ are in the same
block. Since $x\prec y$, if $t\prec x$ for some term
$t\in\text{supp}(\mathcal{D}_{\texttt{term}})$, then $t\prec y$ as well. I.e.
the set of terms in $B_{a(r-1)+b}$ satisfied by $y$ is a superset of the set
of terms in $B_{a(r-1)+b}$ satisfied by $x$. By construction, this implies
$f_{\boldsymbol{t},\boldsymbol{\phi}}(x)\leq
f_{\boldsymbol{t},\boldsymbol{\phi}}(y)$. ∎

######  Lemma 3.4.

For $f_{\boldsymbol{t},\boldsymbol{r}}\sim\mathcal{D}_{no}$, we have
$\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}[\varepsilon(f_{\boldsymbol{t},\boldsymbol{r}},{\cal
M}_{r,k})=\Omega(\varepsilon)]=\Omega(1)$.

We prove Lemma 3.4 in Section 3.4.

######  Lemma 3.5.

Given a collection of points
$\boldsymbol{x}=(x_{1},\ldots,x_{s})\in(\\{0,1\\}^{d})^{s}$ and a function
$f\colon\\{0,1\\}^{d}\to[r]$, let
$(\boldsymbol{x},f(\boldsymbol{x}))=((x_{1},f(x_{1})),\ldots,(x_{s},f(x_{s}))))$
denote the corresponding collection of labelled examples. Let ${\cal E}_{yes}$
and ${\cal E}_{no}$ denote the distributions over
$(\boldsymbol{x},f(\boldsymbol{x}))$ when $\boldsymbol{x}$ consists of $s$
i.i.d. uniform samples and $f\sim\mathcal{D}_{\texttt{yes}}$ and
$f\sim\mathcal{D}_{\texttt{no}}$, respectively. If $s\leq
2^{\frac{(r-1)k\sqrt{d}}{5\varepsilon}}$, then the total variation distance
between $\mathcal{E}_{\texttt{yes}}$ and $\mathcal{E}_{\texttt{no}}$ is
$o(1)$.

We prove Lemma 3.5 in Section 3.3.

###  3.2 Proof of 3.2

###### Proof.

Recall $w=\frac{(r-1)k\sqrt{d}}{2\varepsilon}$, $N_{i}=2^{w}\cdot e^{-i}$, the
definition of $\mathcal{D}_{\texttt{term}}$ from Definition 3.1, and the
definition of $U_{i,j}$ from eq. 1. Since $x\in B_{i}$ we have
$|x|=\frac{d}{2}+\ell$ where
$\frac{i\varepsilon\sqrt{d}}{k(r-1)}\leq\ell<\frac{(i+1)\varepsilon\sqrt{d}}{k(r-1)}$.
Note that $\mathbb{P}_{t\sim\mathcal{D}_{\texttt{term}}}[t\preceq
x]=\left(|x|/d\right)^{w}$ since $t\preceq x$ iff the non-zero coordinates of
$t$ are a subset of the non-zero coordinates of $x$. Therefore, we have

$\displaystyle\mathbb{P}_{\boldsymbol{t}}[x\in U_{i,j}]$
$\displaystyle=\mathbb{P}_{t^{i,j}}[t^{i,j}\preceq
x]\cdot\prod_{j^{\prime}\in[N_{i}]\setminus\\{j\\}}\mathbb{P}_{t^{i,j^{\prime}}}[t^{i,j^{\prime}}\not\preceq
x]=\left(|x|/d\right)^{w}\left(1-\left(|x|/d\right)^{w}\right)^{N_{i}-1}\text{.}$

Note that the first term is upper bounded as

$\displaystyle(|x|/d)^{w}$
$\displaystyle\leq\left(\frac{\frac{d}{2}+\frac{(i+1)\cdot\varepsilon\sqrt{d}}{k(r-1)}}{d}\right)^{w}=\frac{1}{2^{w}}\left(1+\frac{2\varepsilon}{k(r-1)\sqrt{d}}\cdot(i+1)\right)^{w}\leq\frac{e^{i+1+o(1)}}{2^{w}}\leq\frac{e^{1+o(1)}}{N_{i}}$

and this immediately implies the upper bound on
$\mathbb{P}_{\boldsymbol{t}}[x\in U_{i,j}]$. We can also lower bound this
quantity by

$\displaystyle(|x|/d)^{w}$
$\displaystyle\geq\left(\frac{\frac{d}{2}+\frac{i\cdot\varepsilon\sqrt{d}}{k(r-1)}}{d}\right)^{w}=\frac{1}{2^{w}}\left(1+\frac{2\varepsilon}{k(r-1)\sqrt{d}}\cdot
i\right)^{w}\geq\frac{e^{i-o(1)}}{2^{w}}\geq\frac{1}{e^{o(1)}N_{i}}\text{.}$

Now, combining our upper and lower bounds on $(|x|/d)^{w}$ yields

$\displaystyle\mathbb{P}_{\boldsymbol{t}}[x\in U_{i,j}]$
$\displaystyle\geq\frac{1}{e^{o(1)}N_{i}}\left(1-\frac{e^{1+o(1)}}{N_{i}}\right)^{N_{i}}\geq\frac{1}{e^{o(1)}N_{i}}e^{-(1+o(1))\cdot
e^{1+o(1)}}\geq\frac{1}{e^{e+1}N_{i}}\geq\frac{1}{20N_{i}}\text{.}$

∎

###  3.3 $\mathcal{D}_{\texttt{yes}}$ and $\mathcal{D}_{\texttt{no}}$ are Hard
to Distinguish: Proof of Lemma 3.5

###### Proof.

Recall the definition of the set $U_{i,j}$ in eq. 1. For $a\neq b\in[s]$, let
$E_{ab}$ denote the event that $x_{a}$ and $x_{b}$ belong to the same
$U_{i,j}$ for some $i\in[k(r-1)]$ and $j\in[N_{i}]$. Observe that conditioned
on $\overline{\vee_{a,b}E_{ab}}$, the distributions $\mathcal{E}_{yes}$ and
$\mathcal{E}_{no}$ are identical. Let $x,y\in\\{0,1\\}^{d}$ denote two i.i.d.
uniform samples. We have

$\displaystyle\mathbb{P}[E_{ab}]=\mathbb{P}_{x,y,\boldsymbol{t}}\left[\bigvee_{i,j}(x\in
U_{i,j}\wedge y\in
U_{i,j})\right]=\sum_{i,j}\mathbb{P}_{x,y,\boldsymbol{t}}\left[x\in
U_{i,j}\wedge y\in U_{i,j}\right]=\sum_{i,j}\mathbb{P}_{x,\boldsymbol{t}}[x\in
U_{i,j}]^{2}$ (2)

where the first step holds since the $U_{i,j}$’s are disjoint and the second
step holds by independence of $x$ and $y$. Now, for a fixed $i\in[k(r-1)]$ and
$j\in[N_{i}]$ we have the following: by 3.2, for $x\in B_{i}$ we have
$\mathbb{P}_{\boldsymbol{t}}[x\in U_{i,j}]\leq\frac{3}{N_{i}}$ and for
$x\notin B_{i}$ we have $\mathbb{P}_{\boldsymbol{t}}[x\in U_{i,j}]=0$.
Therefore $\mathbb{P}_{x,\boldsymbol{t}}[x\in U_{i,j}]\leq\frac{3}{N_{i}}$.
Therefore, the RHS of eq. 2 is bounded as

$\displaystyle\sum_{i,j}\mathbb{P}_{x,\boldsymbol{t}}[x\in
U_{i,j}]^{2}=\sum_{i}N_{i}\cdot\mathbb{P}_{x,\boldsymbol{t}}[x\in
U_{i,j}]^{2}\leq\sum_{i}\frac{9}{N_{i}}\leq rk\cdot\frac{9}{N_{r-2}}$

since the $N_{i}$’s are decreasing with respect to $i$. Therefore,

$d_{TV}(\mathcal{E}_{\texttt{yes}},\mathcal{E}_{\texttt{no}})\leq\mathbb{P}_{\boldsymbol{x},\boldsymbol{t}}\left[\bigvee_{a,b\in[s]}E_{ab}\right]\leq
s^{2}\cdot rk\cdot\frac{9}{N_{r-2}}=o(1)$

since
$N_{r-2}=2^{\frac{(r-1)k\sqrt{d}}{2\varepsilon}(1-o(1))}=\omega(s^{2}\cdot
rk)$. ∎

###  3.4 Functions Drawn from $\mathcal{D}_{\texttt{no}}$ are Far from
$k$-Monotone: Proof of Lemma 3.4

###### Proof.

We will use 2.3, restated below for the special case of $r$-valued functions
over the hypercube. Recall that $\mathcal{M}_{r,k}$ is the set of $k$-monotone
functions $f\colon\\{0,1\\}^{d}\to[r]$.

######  Claim 3.6.

Let $f\colon\\{0,1\\}^{d}\to[r]$ and $k^{\prime}\geq 3k$ be an integer. Let
${\cal C}\subset(\\{0,1\\}^{d})^{k^{\prime}}$ be a collection of disjoint
$k^{\prime}$-alternating chains for $f$. Then

$\varepsilon(f,{\cal M}_{r,k})\geq\frac{1}{3\cdot
2^{d}}\cdot\left|\bigcup_{C\in{\cal C}}C\right|\text{.}$

From the above claim, we can lower bound the distance to $k$-monotonicity of
$f$ by showing that it contains a collection of disjoint
$k^{\prime}$-alternating chains where $k^{\prime}\geq 3k$ whose union makes up
an $\Omega(\varepsilon)$-fraction of the hypercube.

Recall $U_{i}=U_{i,1}\cup\cdots\cup U_{i,N_{i}}\subseteq B_{i}$ and note that
$f_{\boldsymbol{t},\boldsymbol{r}}\sim\mathcal{D}_{\texttt{no}}$ takes values
only from $\\{i\bmod{(r-1)},i\bmod{(r-1)}+1\\}$ in $B_{i}$. In particular, for
$a\in\\{0,1,\ldots,r-2\\}$, let

$\displaystyle X_{a}=B_{a}\cup B_{(r-1)+a}\cup B_{2(r-1)+a}\cup\cdots\cup
B_{(k-1)(r-1)+a}=\bigcup_{i\in[k]}B_{i(r-1)+a}$ (3)

and note that all points $x\in X_{a}$ are assigned value
$f_{\boldsymbol{t},\boldsymbol{r}}(x)\in\\{a,a+1\\}$. Moreover, this value is
chosen uniformly at random when $x\in\bigcup_{i\in[k]}U_{i(r-1)+a}$, which
occurs with probability $\geq 1/20$ by 3.2. Let
$k^{\prime\prime}:=\frac{\varepsilon\sqrt{d}}{r-1}$ and recall that we are
assuming $rk\leq\frac{\varepsilon\sqrt{d}}{4800}$ and so $k^{\prime\prime}\geq
4800k$. We first show there exists a large collection ${\cal C}_{a}$ of
length-$k^{\prime\prime}$ disjoint chains in $X_{a}$ for all
$a\in\\{0,1,\ldots,r-2\\}$.

######  Claim 3.7.

For every $a\in\\{0,1,\ldots,r-2\\}$, there exists a collection of vertex
disjoint chains ${\cal C}_{a}\subset(X_{a})^{k^{\prime\prime}}$ in $X_{a}$ of
length $k^{\prime\prime}$ of size $|{\cal
C}_{a}|\geq\Omega(\frac{2^{d}}{\sqrt{d}})$.

###### Proof.

We start by showing that there is a large matching in the transitive closure
of the hypercube from $L_{\frac{d}{2}}$ to
$L_{\frac{d}{2}+\varepsilon\sqrt{d}-1}$. Consider the bipartite graph
$(U,V,E)$ where $U:=L_{\frac{d}{2}}$,
$V:=L_{\frac{d}{2}+\varepsilon\sqrt{d}-1}$, and $E:=\\{(x,y)\in U\times
V\colon x\prec y\\}$. Observe that vertices in $U$ have degree exactly
$\Delta:={\frac{d}{2}\choose\varepsilon\sqrt{d}-1}$ while vertices in $V$ have
degree exactly
${\frac{d}{2}+\varepsilon\sqrt{d}-1\choose\varepsilon\sqrt{d}-1}\geq\Delta$.
Note also that
$|V|={d\choose\frac{d}{2}+\varepsilon\sqrt{d}-1}\geq\Omega(\frac{2^{d}}{\sqrt{d}})$
by Stirling’s approximation. We now use the following claim from [BBH23].

######  Claim 3.8 ([BBH23]).

Let $(U,V,E)$ be a bipartite graph and $\Delta>0$ be such that (a) each vertex
$x\in U$ has degree exactly $\Delta$ and (b) each vertex $y\in V$ has degree
at least $\Delta$. Then there exists a matching $M\subseteq E$ in $(U,V,E)$ of
size $|M|\geq\frac{1}{2}|V|$.

By the above claim and the previous observations, there exist subsets
$S\subseteq L_{\frac{d}{2}}$ and $T\subseteq
L_{\frac{d}{2}+\varepsilon\sqrt{d}-1}$ of size
$|S|=|T|=\Omega(\frac{2^{d}}{\sqrt{d}})$ and a bijection $\phi\colon S\to T$
satisfying $x\prec\phi(x)$ for all $x\in S$. We now use the following routing
theorem due to Lehman and Ron to obtain a collection of disjoint chains from
$S$ to $T$.

######  Theorem 3.9 (Lehman-Ron, [LR01]).

Let $a<b$ and $S\subseteq L_{a}$, $T\subseteq L_{b}$ where $m:=|S|=|T|$.
Moreover, suppose there is a bijection $\phi\colon S\to T$ satisfying
$x\prec\phi(x)$ for all $x\in S$. Then there exist $m$ vertex disjoint paths
from $S$ to $T$ in the hypercube.

Now, invoking the above theorem on our bijection $\phi\colon S\to T$ yields a
collection $P$ of $|P|\geq\Omega(\frac{2^{d}}{\sqrt{d}})$ vertex disjoint
paths from $L_{\frac{d}{2}}$ to $L_{\frac{d}{2}+\varepsilon\sqrt{d}-1}$. For
each $a\in\\{0,1,\ldots,r-2\\}$, let ${\cal C}_{a}$ denote the collection of
chains formed by taking a path in $P$ and including only the vertices from
$X_{a}$ (recall eq. 3). Note that the resulting chains in ${\cal C}_{a}$ are
of length $k^{\prime\prime}=\frac{\varepsilon\sqrt{d}}{r-1}$. This completes
the proof of 3.7. ∎

From 3.7, we have ${\cal C}_{0},{\cal C}_{1},\ldots,{\cal C}_{r-2}$ where each
${\cal C}_{a}\subset(X_{a})^{k^{\prime\prime}}$ is a collection of vertex
disjoint chains of length $k^{\prime\prime}\geq 4800k$ of size $|{\cal
C}_{a}|\geq\Omega(\frac{2^{d}}{\sqrt{d}})$. Fix a chain
$C=(x_{1},x_{2},\ldots,x_{k^{\prime\prime}})\in{\cal C}_{a}$. Let $A(C)$ be
the random variable which denotes the max-length alternating sub-chain (recall
Definition 2.1) of $C$ over a random
$f_{\boldsymbol{t},\boldsymbol{r}}\sim\mathcal{D}_{\texttt{no}}$. Fix $x_{j}$
in the chain and suppose $x_{j}\in B_{i}\subseteq X_{a}$. By 3.2,
$\mathbb{P}_{\boldsymbol{t}}[x_{j}\in U_{i}]\geq 1/20$. Moreover, conditioned
on $x_{j}\in U_{i}$, $f_{\boldsymbol{t},\boldsymbol{r}}(x_{j})$ is chosen from
$\\{a,a+1\\}$ uniformly at random. Thus, any step of the sequence

$(1,f_{\boldsymbol{t},\boldsymbol{r}}(x_{2})-f_{\boldsymbol{t},\boldsymbol{r}}(x_{1}),f_{\boldsymbol{t},\boldsymbol{r}}(x_{3})-f_{\boldsymbol{t},\boldsymbol{r}}(x_{2}),\ldots,f_{\boldsymbol{t},\boldsymbol{r}}(x_{k^{\prime\prime}})-f_{\boldsymbol{t},\boldsymbol{r}}(x_{k^{\prime\prime}-1}))$

is non-zero _and_ differs in sign from the previous non-zero step with
probability at least $1/40$ and so $\mathbb{E}[A(C)]\geq k^{\prime\prime}/40$.
I.e.,
$0\leq\mathbb{E}[k^{\prime\prime}-A(C)]<k^{\prime\prime}(1-\frac{1}{40})$.
Thus, using Markov’s inequality we have

$\displaystyle\mathbb{P}\left[A(C)<\frac{k^{\prime\prime}}{1600}\right]=\mathbb{P}\left[k^{\prime\prime}-A(C)>k^{\prime\prime}\left(1-\frac{1}{40}\right)\left(1+\frac{1}{40}\right)\right]\leq\frac{1}{(1+\frac{1}{40})}=1-\frac{1}{41}\text{.}$
(4)

Now, let ${\cal C}={\cal C}_{0}\cup{\cal C}_{1}\cup\cdots\cup{\cal C}_{r-2}$
and let $Z:=|\\{C\in{\cal C}\colon A(C)\geq\frac{k^{\prime\prime}}{1600}\\}|$.
By eq. 4 we have $\mathbb{E}[Z]\geq|{\cal C}|/41$ and $0\leq\mathbb{E}[|{\cal
C}|-Z]\leq|{\cal C}|(1-\frac{1}{41})$. Again using Markov’s inequality, we
have

$\displaystyle\mathbb{P}\left[Z<\frac{|{\cal
C}|}{1681}\right]=\mathbb{P}\left[|{\cal C}|-Z>|{\cal
C}|\left(1-\frac{1}{41}\right)\left(1+\frac{1}{41}\right)\right]\leq\frac{1}{(1+\frac{1}{41})}=1-\frac{1}{42}\text{.}$
(5)

Now, for $C\in{\cal C}$ such that $A(C)\geq k^{\prime\prime}/1600$, let
$C^{\prime}$ be any $(k^{\prime\prime}/1600)$-alternating sub-chain of $C$.
Let ${\cal C}^{\prime}=\\{C^{\prime}\colon C\in{\cal C}\text{ such that
}A(C)\geq k^{\prime\prime}/1600\\}$ which is a collection of disjoint
$(k^{\prime\prime}/1600)$-alternating chains for
$f_{\boldsymbol{t},\boldsymbol{r}}$. Now, recall that $k^{\prime\prime}\geq
4800k$ and so $k^{\prime\prime}/1600\geq 3k$. Thus, if $Z\geq|{\cal C}|/1681$,
then $|{\cal C}^{\prime}|\geq|{\cal C}|/1681$ and so by 3.6 we have

$\displaystyle\varepsilon(f_{\boldsymbol{t},\boldsymbol{r}},{\cal
M}_{r,k})\geq\frac{1}{3\cdot 2^{d}}\left|\bigcup_{C^{\prime}\in{\cal
C}^{\prime}}C^{\prime}\right|\geq\frac{1}{3\cdot 2^{d}}\cdot|{\cal
C}^{\prime}|\cdot\frac{k^{\prime\prime}}{1600}\geq\frac{k^{\prime\prime}\cdot|{\cal
C}|}{10,000,000\cdot 2^{d}}$ (6)

By 3.7 we have $|{\cal C}|\geq(r-1)\cdot\Omega(\frac{2^{d}}{\sqrt{d}})$ and
recall that $k^{\prime\prime}=\frac{\varepsilon\sqrt{d}}{r-1}$. Thus, the RHS
of eq. 6 is $\Omega(\varepsilon)$. In conclusion,

$\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[\varepsilon(f_{\boldsymbol{t},\boldsymbol{r}},{\cal
M}_{r,k})\geq\Omega(\varepsilon)\right]\geq\mathbb{P}\left[Z\geq\frac{|{\cal
C}|}{1681}\right]\geq\frac{1}{42}$

by eq. 5 and this completes the proof of Lemma 3.4. ∎

##  4 Learning Upper Bound over Product Spaces

In this section we prove Theorem 1.6, our upper bound for learning measurable
$k$-monotone functions in $\mathbb{R}^{d}$. We restate the theorem below
without any hidden logarithmic factors and for the case of $r=2$. The theorem
for general $r\geq 2$ can then be obtained by replacing $\varepsilon$ with
$\varepsilon/r$ and $\delta$ by $1/3r$ following the same approach we used to
prove Theorem 1.3 in Section 1.5.

######  Theorem 4.1.

Given an arbitrary product measure $\mu$, there is a learning algorithm under
$\mu$ which learns any measurable $k$-monotone function
$f\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ to error $\varepsilon$ with probability
$1-\delta$ with time and sample complexity

$\displaystyle\ln\left(\frac{1}{\delta}\right)\cdot\min\left\\{(d\log(dk/\varepsilon))^{O\left(\frac{k}{\varepsilon}\sqrt{d\log(dk/\varepsilon)}\right)},\left(\frac{dk}{\varepsilon}\right)^{O(d)}\right\\}$
(7)

Our proof uses downsampling to reduce our learning problem over
$\mathbb{R}^{d}$ to learning over a hypergrid, $[N]^{d}$, under the uniform
distribution with mild label noise. In Section 4.1 we synthesize the results
from [HY22] which we borrow for our proof. In Section 4.2 we give two learning
results for hypergrids whose time complexities correspond to the two arguments
inside the $\min$ expression in eq. 7. In Section 4.3 we describe the learning
algorithm and prove its correctness.

Throughout this section, let $\mu=\prod_{i=1}^{d}\mu_{i}$ be any product
measure over $\mathbb{R}^{d}$ and let $N$ be a power of two satisfying
$8kd/\varepsilon\leq N\leq 16kd/\varepsilon$.

###  4.1 Reduction to Hypergrids via Downsampling

The idea of downsampling is to construct a grid-partition of $\mathbb{R}^{d}$
into $N^{d}$ blocks such that (a) the measure of each block under $\mu$ is
roughly $N^{-d}$, and (b) the function $f$ we’re trying to learn is constant
on most of the blocks. Roughly speaking, this allows us to learn $f$ under
$\mu$ by learning a proxy for $f$ over $[N]^{d}$ under the uniform
distribution. The value of $N$ needed to achieve this depends on what [HY22]
call the ?block boundary size? of the function. Formally, the downsampling
procedure constructs query access to maps
$\mathsf{block}\colon\mathbb{R}^{d}\to[N]^{d}$ and
$\mathsf{blockpoint}\colon[N]^{d}\to\mathbb{R}^{d}$ which have various good
properties which we will spell out in the rest of this section. One should
think of $\mathsf{block}$ as mapping each point $x\in\mathbb{R}^{d}$ to the
block of the grid-partition that $x$ belongs to and $\mathsf{blockpoint}$ as
mapping each block to some specific point contained in the block. See [HY22,
Def 2.1] for a formal definition. Given these maps and a function
$f\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ we define the function
$f^{\mathsf{block}}\colon[N]^{d}\to\\{\pm 1\\}$ as
$f^{\mathsf{block}}(z)=f(\mathsf{blockpoint}(z))$. We let
$\mathsf{block}(\mu)$ denote the distribution over $[N]^{d}$ induced by
sampling $x\sim\mu$ and then taking $\mathsf{block}(x)$.

######  Proposition 4.2 (Downsampling, [HY22]).

Let $f\colon\mathbb{R}^{d}\to\\{0,1\\}$ be a $k$-monotone function and
$N,Q\in\mathbb{Z}^{+}$. Using

$m:=O\left(\frac{NQ^{2}d^{2}}{\min(\delta,\varepsilon)^{2}}\ln\left(\frac{Nd}{\delta}\right)\right)$

samples from $\mu=\mu_{1}\times\cdots\times\mu_{d}$, there is a downsampling
procedure that constructs query access to maps
$\mathsf{block}\colon\mathbb{R}^{d}\to[N]^{d}$ and
$\mathsf{blockpoint}\colon[N]^{d}\to\mathbb{R}^{d}$ such that with probability
at least $1-\delta$ over the random samples, the following two conditions are
satisfied:

  1. 1.

$\left\lVert\mathsf{block}(\mu)-\mathsf{unif}([N]^{d})\right\rVert_{\text{TV}}\leq\frac{\delta}{Q}$.

  2. 2.

$\mathbb{P}_{x\sim\mu}\left[f(x)\neq
f^{\mathsf{block}}(\mathsf{block}(x))\right]\leq\varepsilon$.

The total running time and number of samples is $O(m)$.

###### Proof.

[HY22, Prop. 2.5] shows that there is a randomized procedure using $m$ samples
from $\mu$ and $O(m)$ time which constructs the maps $\mathsf{block}$ and
$\mathsf{blockpoint}$ such that with probability $1$, we get

$\displaystyle\mathbb{P}_{x\sim\mu}\left[f(x)\neq
f^{\mathsf{block}}(\mathsf{block}(x))\right]\leq
N^{-d}\cdot\mathsf{bbs}(f,N)+\left\lVert\mathsf{block}(\mu)-\mathsf{unif}([N]^{d})\right\rVert_{\text{TV}}$
(8)

where $\mathsf{bbs}(f,N)$ is the $N$-block boundary size of $f$ [HY22, Def.
2.4], which is at most $kdN^{d-1}$ when $f$ is $k$-monotone [HY22, Lemma 7.1].
Thus, the first of the two quantities in the RHS is at most $kd/N$ which is at
most $\varepsilon/8$ using our definition of $N$. Then, [HY22, Lemma 2.7]
states that

$\displaystyle\mathbb{P}\left[\left\lVert\mathsf{block}(\mu)-\mathsf{unif}([N]^{d})\right\rVert_{\text{TV}}>\beta\right]\leq
4Nd\cdot\exp\left(-\frac{\beta^{2}m}{18Nd^{2}}\right)$ (9)

and so invoking this lemma with $\beta:=\min(\delta/4Q,\varepsilon/8)$ and
$m:=\frac{18Nd^{2}}{\beta^{2}}\ln\left(\frac{16Nd}{\delta}\right)$ completes
the proof. ∎

###  4.2 Learning over Hypergrids

For a function $f\colon{\cal X}\to\\{\pm 1\\}$ and a measure $\mu$ over ${\cal
X}$, recall that the _example oracle_ for $f$ under $\mu$, denoted by
$EX(f,\mu)$, when queried, generates an example, $(x,f(x))$, where $x$ is
sampled from $\mu$. Given a _noise parameter_ $\eta$, the _noisy example
oracle_ $EX^{\eta}(f,\mu)$, when queried, samples $x$ from $\mu$, returns the
true example $(x,f(x))$ with probability $1-\eta$, and returns the corrupted
example $(x,-f(x))$ with probability $\eta$. This is referred to as _random
classification noise_ (RCN).

We prove the following two upper bounds for learning over hypergrids under
RCN. The bound in Lemma 4.3 is relatively straightforward to prove using
coupon collector arguments plus some additional work to handle the label
noise. We give a proof in Appendix B.

######  Lemma 4.3 (Coupon Collecting Learner).

Let $\varepsilon,\delta\in(0,1)$, $\eta\in(0,1/2)$, and $N\in\mathbb{Z}^{+}$.
There is an algorithm which, given any $k$-monotone function
$f\colon[N]^{d}\to\\{\pm 1\\}$, uses at most

$\widetilde{O}\left(\frac{1}{(1-2\eta)^{2}}\left(\log\frac{1}{\varepsilon}+\log\frac{1}{\delta}\right)\right)\cdot
N^{O(d)}$

examples from $EX^{\eta}(f,\mathsf{unif}([N]^{d}))$ and returns
$h\colon[N]^{d}\to\\{\pm 1\\}$, satisfying
$\mathbb{P}_{h}[d(f,h)\leq\varepsilon]\geq 1-\delta$.

######  Lemma 4.4 (Hypercube Mapping Learner).

Let $\varepsilon,\delta\in(0,1)$, $\eta\in(0,1/2)$, and $N\in\mathbb{Z}^{+}$
be a power of two. There is an algorithm which, given any $k$-monotone
function $f\colon[N]^{d}\to\\{\pm 1\\}$, uses at most

$O\left(\frac{1}{\varepsilon^{2}(1-2\eta)^{2}}+\log\frac{1}{\delta}\right)(d\log
N)^{O\left(\frac{k}{\varepsilon}\sqrt{d\log N}\right)}$

examples from $EX^{\eta}(f,\mathsf{unif}([N]^{d}))$ and returns
$h\colon[N]^{d}\to\\{\pm 1\\}$, satisfying
$\mathbb{P}_{h}[d(f,h)\leq\varepsilon]\geq 1-\delta$.

###### Proof.

Let $b\colon[N]\to\\{\pm 1\\}^{\log N}$ denote the bijection which maps each
element of $[N]$ to its bit representation. Let
$\boldsymbol{b}\colon[N]^{d}\to\\{\pm 1\\}^{d\log N}$ be defined as
$\boldsymbol{b}(x)=(b(x_{1}),\ldots,b(x_{d}))$. Given $f\colon[N]^{d}\to\\{\pm
1\\}$ define the function $f^{\mathsf{cube}}\colon\\{\pm 1\\}^{d\log
N}\to\\{\pm 1\\}$ as $f^{\mathsf{cube}}(z)=f(\boldsymbol{b}^{-1}(z))$.

######  Observation 4.5.

If $f$ is $k$-monotone over $[N]^{d}$, then $f^{\mathsf{cube}}$ is
$k$-monotone over $\\{\pm 1\\}^{d\log N}$.

###### Proof.

Observe that if $\boldsymbol{b}(x)\prec\boldsymbol{b}(y)$ in $\\{\pm
1\\}^{d\log N}$, then $x\prec y$ in $[N]^{d}$. Thus, if
$\boldsymbol{b}(x_{1})\prec\cdots\prec\boldsymbol{b}(x_{m})$ is an
$m$-alternating chain for $f^{\mathsf{cube}}$, then $x_{1}\prec\cdots\prec
x_{m}$ is an $m$-alternating chain for $f$. Therefore, if $f^{\mathsf{cube}}$
is not $k$-monotone, then neither is $f$. ∎

Now, given 4.5 and the bijection $\boldsymbol{b}\colon[N]^{d}\to\\{\pm
1\\}^{d\log N}$, it suffices to provide a learning algorithm for
$f^{\mathsf{cube}}$. This is achieved using the Low-Degree Algorithm
introduced by [LMN93] which was shown by [Kea98] to be robust to
classification noise. Formally, we use the following theorem, which we prove
in Appendix A for the sake of completeness.

######  Theorem 4.6 (Low-Degree Algorithm with Classification Noise).

Let $\varepsilon,\delta\in(0,1)$ and $\eta\in(0,1/2)$. Suppose ${\cal C}$ is a
concept class of Boolean functions over $\\{\pm 1\\}^{d}$ such that for some
fixed positive integer $\tau$, all $f\in{\cal C}$ satisfy
$\sum_{S\subseteq[d]\colon|S|>\tau}\widehat{f}(S)^{2}\leq\varepsilon/2$. Then
there is an algorithm ${\cal A}$ which, on any input $f\in{\cal C}$, uses at
most

$O\left(\left(\frac{1}{\varepsilon^{2}(1-2\eta)^{2}}+\log\frac{1}{\delta}\right)\cdot
d^{\tau}\right)$

examples from $EX^{\eta}(f,\mathsf{unif}(\\{\pm 1\\}^{d}))$ and returns a
hypothesis $h\colon\\{\pm 1\\}^{d}\to\\{\pm 1\\}$ where
$\mathbb{P}_{h}[d(f,h)\leq\varepsilon]\geq 1-\delta$.

We use the following Fourier concentration lemma due to [BCO+15] for
$k$-monotone Boolean functions.

######  Lemma 4.7 ([BCO+15]).

If $f\colon\\{\pm 1\\}^{d}\to\\{\pm 1\\}$ is $k$-monotone, then
$\sum_{S\colon|S|>\frac{k\sqrt{d}}{\varepsilon}}\widehat{f}(S)^{2}\leq\varepsilon$.

By Lemma 4.7, we can invoke Theorem 4.6 with $\tau=\frac{k\sqrt{d\log
N}}{\varepsilon}$, concluding the proof of Lemma 4.4. ∎

###  4.3 Putting it Together: Proof of Theorem 4.1

###### Proof.

We now have all the tools to define the algorithm and prove its correctness.

Input: $\varepsilon,\delta\in(0,1)$ and access to examples from $EX(f,\mu)$
where $f\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ is $k$-monotone;

1\. Let $N$ be a power of $2$ such that $\frac{8kd}{\varepsilon}\leq
N\leq\frac{16kd}{\varepsilon}$. Let ${\cal A}$ denote the learning algorithm
for $k$-monotone functions $g\colon[N]^{d}\to\\{\pm 1\\}$ which has the
smaller sample-complexity among the algorithms guaranteed by Lemma 4.3 and
Lemma 4.4. Let $Q$ be the sample-complexity of ${\cal A}$;

2\. Run the downsampling procedure of Proposition 4.2 to obtain the maps
$\mathsf{block}$, $\mathsf{blockpoint}$, and access to the corresponding
function $f^{\mathsf{block}}\colon[N]^{d}\to\\{\pm 1\\}$ ;

3\. Obtain a set of $Q$ examples $S\in(\mathbb{R}^{d}\times\\{\pm 1\\})^{Q}$
from $(EX(f,\mu))^{Q}$;

4\. Let $S^{\mathsf{block}}=\\{(\mathsf{block}(x),f(x))\colon(x,f(x))\in
S\\}\in([N]^{d}\times\\{\pm 1\\})^{Q}$;

5\. Run ${\cal A}$ using the sample $S^{\mathsf{block}}$, which returns a
hypothesis $h^{\mathsf{block}}\colon[N]^{d}\to\\{\pm 1\\}$ for
$f^{\mathsf{block}}$;

Return the hypothesis $h\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ for
$f\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ defined as
$h(x)=h^{\mathsf{block}}(\mathsf{block}(x))$

Algorithm 1 Learning algorithm for $k$-monotone functions under product
measure $\mu$

Recall that given maps $\mathsf{block}\colon\mathbb{R}^{d}\to[N]^{d}$,
$\mathsf{blockpoint}\colon[N]^{d}\to\mathbb{R}^{d}$, and a function
$f\colon\mathbb{R}^{d}\to\\{\pm 1\\}$ we define the function
$f^{\mathsf{block}}\colon[N]^{d}\to\\{\pm 1\\}$ as
$f^{\mathsf{block}}(z)=f(\mathsf{blockpoint}(z))$. Recall that
$\mathsf{block}(\mu)$ is the distribution over $\mathsf{block}(x)\in[N]^{d}$
when $x\sim\mu$. By Proposition 4.2, step (2) of Alg. 1 results in the
following items being satisfied with probability at least $1-\delta$.

  1. 1.

$\left\lVert\mathsf{block}(\mu)-\mathsf{unif}([N]^{d})\right\rVert_{\text{TV}}\leq\frac{\delta}{Q}$.

  2. 2.

$\mathbb{P}_{x\sim\mu}\left[f(x)\neq
f^{\mathsf{block}}(\mathsf{block}(x))\right]\leq\varepsilon$.

Firstly, by item (2), an example $(\mathsf{block}(x),f(x))$ where $x\sim\mu$,
is equivalent to an example $(z,b)\sim
EX^{\eta}(f^{\mathsf{block}},\mathsf{block}(\mu))$ for some
$\eta\leq\varepsilon$. I.e. the set $S^{\mathsf{block}}\in([N]^{d}\times\\{\pm
1\\})^{Q}$ from step (4) of Alg. 1 is distributed according to
$(EX^{\eta}(f^{\mathsf{block}},\mathsf{block}(\mu)))^{Q}$. Now, as stated,
Lemma 4.3 and Lemma 4.4 only hold when ${\cal A}$ is given a sample from
$(EX^{\eta}(f^{\mathsf{block}},\mathsf{unif}([N]^{d})))^{Q}$. However, the
following claim shows that since $\mathsf{block}(\mu)$ and
$\mathsf{unif}([N]^{d}))$ are sufficiently close (item (1) above), the
guarantees on ${\cal A}$ from Lemma 4.3 and Lemma 4.4 also hold when ${\cal
A}$ is given a sample from
$(EX^{\eta}(f^{\mathsf{block}},\mathsf{block}(\mu)))^{Q}$.

######  Claim 4.8.

Let ${\cal C}\colon{\cal X}\to\\{\pm 1\\}$ be a concept class and let ${\cal
A}$ be an algorithm which given any $f\in{\cal C}$,
$\varepsilon,\delta\in(0,1)$, and $\eta\in[0,1/2)$ uses a sample from
$(EX^{\eta}(f,\mathsf{unif}([N]^{d})))^{Q}$ and produces $h$ satisfying
$\mathbb{P}_{x\sim\mathsf{unif}([N]^{d})}[h(x)\neq f(x)]\leq\varepsilon$ with
probability at least $1-\delta$. If $\mathcal{D}$ is a distribution over
$[N]^{d}$ with
$\left\lVert\mathcal{D}-\mathsf{unif}([N]^{d})\right\rVert_{TV}\leq\gamma$,
then given a sample from $(EX^{\eta}(f,\mathcal{D}))^{Q}$, ${\cal A}$ produces
$h$ satisfying $\mathbb{P}_{x\sim\mathcal{D}}[h(x)\neq
f(x)]\leq\varepsilon+\gamma$ with probability at least $1-(\delta+\gamma Q)$ .

Using 4.8 and item (1) above, if step (2) of Alg. 1 succeeds, then with
probability at least $1-2\delta$, step (5) produces $h^{\mathsf{block}}$ such
that $\mathbb{P}_{z\sim\mathsf{block}(\mu)}[h^{\mathsf{block}}(z)\neq
f^{\mathsf{block}}(z)]\leq 2\varepsilon$. By the triangle inequality and using
our definition of $h$ in the return statement of Alg. 1, we have

$\displaystyle\mathbb{P}_{x\sim\mu}[h(x)\neq f(x)]$
$\displaystyle\leq\mathbb{P}_{x\sim\mu}[f(x)\neq
f^{\mathsf{block}}(\mathsf{block}(x))]+\mathbb{P}_{x\sim\mu}[f^{\mathsf{block}}(\mathsf{block}(x))\neq
h^{\mathsf{block}}(\mathsf{block}(x))]$
$\displaystyle=\mathbb{P}_{x\sim\mu}[f(x)\neq
f^{\mathsf{block}}(\mathsf{block}(x))]+\mathbb{P}_{z\sim\mathsf{block}(\mu)}[f^{\mathsf{block}}(z)\neq
h^{\mathsf{block}}(z)]\text{.}$ (10)

The first term in the RHS is at most $\varepsilon$ by item (2) above and the
second term is at most $2\varepsilon$ as we argued in the previous paragraph.
Finally, adding up the failure probabilities of steps (2) and (5), we conclude
that Alg. 1 produces $h$ satisfying $\mathbb{P}_{x\sim\mu}[h(x)\neq f(x)]\leq
3\varepsilon$ with probability at least $1-3\delta$. ∎

####  4.3.1 Proof of 4.8

###### Proof.

It is a well-known fact that for two distributions $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$, the TV-distance between the corresponding product
distributions satisfies
$\left\lVert\mathcal{D}_{1}^{Q}-\mathcal{D}_{2}^{Q}\right\rVert_{TV}\leq
Q\left\lVert\mathcal{D}_{1}-\mathcal{D}_{2}\right\rVert_{TV}$ and thus we have

$\left\lVert\mathcal{D}^{Q}-\mathsf{unif}([N]^{d})^{Q}\right\rVert_{TV}\leq\gamma
Q$

Given a set of $Q$ examples $S\in([N]^{d}\times\\{\pm 1\\})^{Q}$, let $E(S)$
denote the event that the algorithm ${\cal A}$ fails to produce a hypothesis
with error at most $\varepsilon$, after sampling $S$. First, note the
distribution over labels for the distributions are the same, and therefore

$\displaystyle\mathbb{P}_{S\sim(EX^{\eta}(f,\mathcal{D}))^{Q}}[E(S)]-\mathbb{P}_{S\sim(EX^{\eta}(f,\mathsf{unif}([N]^{d})))^{Q}}[E(S)]=\mathbb{P}_{S\sim\mathcal{D}^{Q}}[E(S)]-\mathbb{P}_{S\sim\mathsf{unif}([N]^{d})^{Q}}[E(S)]\text{.}$
(11)

Using the definition of TV-distance we have

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{Q}}[E(S)]-\mathbb{P}_{S\sim\mathsf{unif}([N]^{d})^{Q}}[E(S)]\leq\left\lVert\mathcal{D}^{Q}-\mathsf{unif}([N]^{d})^{Q}\right\rVert_{TV}\leq\gamma
Q$ (12)

and therefore

$\displaystyle\mathbb{P}_{S\sim(EX^{\eta}(f,\mathcal{D}))^{Q}}[E(S)]\leq\mathbb{P}_{S\sim(EX^{\eta}(f,\mathsf{unif}([N]^{d})))^{Q}}[E(S)]+\gamma
Q\leq\delta+\gamma Q$ (13)

where we used
$\mathbb{P}_{S\sim(EX^{\eta}(f,\mathsf{unif}([N]^{d})))^{Q}}[E(S)]\leq\delta$
by the assumption in the statement of the claim. Now, conditioned on $\neg
E(S)$, we have that ${\cal A}$ produces $h$ satisfying
$\mathbb{P}_{x\sim\mathsf{unif}([N]^{d})}[h(x)\neq f(x)]\leq\varepsilon$.
Again using our bound on the TV-distance, we have

$\mathbb{P}_{x\sim\mathcal{D}}[h(x)\neq
f(x)]-\mathbb{P}_{x\sim\mathsf{unif}([N]^{d})}[h(x)\neq
f(x)]\leq\left\lVert\mathcal{D}-\mathsf{unif}([N]^{d})\right\rVert_{TV}\leq\gamma$

and so $\mathbb{P}_{x\sim\mathcal{D}}[h(x)\neq f(x)]\leq\varepsilon+\gamma$. ∎

##  5 Sample-Based Testing with One-Sided Error

In this section we prove Theorem 1.5, our upper and lower bound on sample-
based testing with one-sided error over the hypercube.

###### Proof of Theorem 1.5.

By a coupon-collecting argument, there is an $O(d\cdot 2^{d})$ sample upper
bound for _exactly learning_ any function over $\\{0,1\\}^{d}$ under the
uniform distribution and therefore the upper bound is trivial.

It suffices to prove the lower bound for the case of $r=2$ and $k=1$, i.e. for
testing monotonicity of Boolean functions. We will need the following fact.

######  Fact 5.1.

Let $A\subset\\{0,1\\}^{d}$ be any anti-chain and let $\ell\colon
A\to\\{0,1\\}$ be any labelling of $A$. Then there exists a monotone function
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ such that $f(x)=\ell(x)$ for all $x\in A$.
I.e. $A$ _shatters_ the class of monotone functions.

Now, let $T$ be any monotonicity tester with one-sided error and let
$S\subseteq\\{0,1\\}^{d}$ denote a set of $s$ i.i.d. uniform samples. Since
$T$ has one-sided error, if the input function is monotone, then $T$ must
accept. In other words, for $T$ to reject it must be sure without a doubt that
the input function is not monotone. By 5.1 for $T$ to be sure the input
function is not monotone, it must be that $S$ is _not_ an anti-chain. Let
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ be any function which is $\varepsilon$-far
from monotone. Since $T$ is a valid tester, it rejects $f$ with probability at
least $2/3$. By the above argument we have

$\displaystyle 2/3\leq\mathbb{P}_{S}[T\text{ rejects
}f]\leq\mathbb{P}_{S}[S\text{ is not an anti-chain}]\leq
s^{2}\cdot\mathbb{P}_{x,y\sim\\{0,1\\}^{d}}[x\preceq y]$ (14)

where the last inequality is by a union bound over all pairs of samples. We
then have

$\displaystyle\mathbb{P}_{x,y\sim\\{0,1\\}^{d}}[x\preceq
y]=\mathbb{P}_{x,y\sim\\{0,1\\}^{d}}[x_{i}\leq y_{i}\text{, }\forall
i\in[d]]=\prod_{i=1}^{d}\mathbb{P}_{x_{i},y_{i}\sim\\{0,1\\}}[x_{i}\leq
y_{i}]=(3/4)^{d}\text{.}$ (15)

Thus, combining eq. 14 and eq. 15 yields
$s\geq\sqrt{\frac{2}{3}(\frac{4}{3})^{d}}=\exp(\Omega(d))$. ∎

##  6 Acknowledgements

We would like to thank Eric Blais and Nathaniel Harms for helpful discussions
during the early stages of this work and for their thoughtful comments and
feedback.

## References

  * [AC06] Nir Ailon and Bernard Chazelle.  Information theory in property testing and monotonicity testing in higher dimension.  Information and Computation, 204(11):1704–1717, 2006.
  * [ACCL07] Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu.  Estimating the distance to a monotone function.  Random Structures Algorithms, 31(3):371–383, 2007.
  * [BB16] Aleksandrs Belovs and Eric Blais.  A polynomial lower bound for testing monotonicity.  In Proceedings, ACM Symposium on Theory of Computing (STOC), 2016\.
  * [BBBY12] Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang.  Active property testing.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2012.
  * [BBH23] Hadley Black, Eric Blais, and Nathaniel Harms.  Testing convexity of discrete sets in high dimensions.  CoRR, abs/2305.03194, 2023.
  * [BBM12] Eric Blais, Joshua Brody, and Kevin Matulef.  Property testing lower bounds via communication complexity.  Computational Complexity, 21(2):311–358, 2012.
  * [BCO+15] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan.  Learning circuits with few negations.  In RANDOM, 2015.
  * [BCS18] Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri.  A $o(d)\cdot\mathrm{polylog}(n)$ monotonicity tester for Boolean functions over the hypergrid $[n]^{d}$.  In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
  * [BCS20] Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri.  Domain reduction for monotonicity testing: A _o_(_d_) tester for boolean functions in $d$-dimensions.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, 2020.
  * [BCS23a] Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri.  A $d^{1/2+o(1)}$ monotonicity tester for boolean functions on $d$-dimensional hypergrids.  CoRR, abs/2304.01416, 2023.
  * [BCS23b] Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri.  Directed isoperimetric theorems for boolean functions on the hypergrid and an $\widetilde{O}(n\sqrt{d})$ monotonicity tester.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, 2023.
  * [BCSM12] Jop Briët, Sourav Chakraborty, David García Soriano, and Ari Matsliah.  Monotonicity testing and shortest-path routing on the cube.  Combinatorica, 32(1):35–53, 2012.
  * [BFH21] Eric Blais, Renato Ferreira Pinto Jr, and Nathaniel Harms.  Vc dimension and distribution-free sample-based testing.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 504–517, 2021.
  * [BGJ+12] Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyoming Jung, Sofya Raskhodnikova, and David Woodruff.  Lower bounds for local monotonicity reconstruction from transitive-closure spanners.  SIAM Journal on Discrete Mathematics (SIDMA), 26(2):618–646, 2012\.
  * [Bha08] Arnab Bhattacharyya.  A note on the distance to monotonicity of boolean functions.  Technical Report 012, Electronic Colloquium on Computational Complexity (ECCC), 2008.
  * [BKKM23] Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer.  Improved monotonicity testers via hypercube embeddings.  In 14th Innovations in Theoretical Computer Science Conference, ITCS, 2023.
  * [BKR23] Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova.  Isoperimetric inequalities for real-valued functions with applications to monotonicity testing.  In 50th International Colloquium on Automata, Languages, and Programming, ICALP, 2023.
  * [BMR19a] Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova.  The power and limitations of uniform samples in testing properties of figures.  Algorithmica, 81(3):1247–1266, 2019.
  * [BMR19b] Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova.  Testing convexity of figures under the uniform distribution.  Random Struct. Algorithms, 54(3):413–443, 2019.
  * [BRY14a] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev.  ${L}_{p}$-testing.  In Proceedings, ACM Symposium on Theory of Computing (STOC), 2014\.
  * [BRY14b] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev.  Lower bounds for testing properties of functions over hypergrid domains.  In Proceedings, IEEE Conference on Computational Complexity (CCC), 2014.
  * [BT96] Nader H. Bshouty and Christino Tamon.  On the fourier spectrum of monotone functions.  J. ACM, 43(4):747–770, 1996.
  * [BY19] Eric Blais and Yuichi Yoshida.  A characterization of constant-sample testable properties.  Random Struct. Algorithms, 55(1):73–88, 2019.
  * [CDJS15] Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri.  Property testing on product distributions: Optimal testers for bounded derivative properties.  In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
  * [CDL+23] Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio.  Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas, 2023.
  * [CDST15] Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan.  Boolean function monotonicity testing requires (almost) ${O}(n^{1/2})$ non-adaptive queries.  In Proceedings, ACM Symposium on Theory of Computing (STOC), 2015\.
  * [CFSS17] Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun.  Sample-based high-dimensional convexity testing.  CoRR, abs/1706.09362, 2017.
  * [CGG+19] Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer.  Testing k-monotonicity: The rise and fall of boolean functions.  Theory Comput., 15:1–55, 2019.
  * [CS13] Deeparnab Chakrabarty and C. Seshadhri.  Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids.  In Proceedings, ACM Symposium on Theory of Computing (STOC), 2013\.
  * [CS14a] Deeparnab Chakrabarty and C. Seshadhri.  An $o(n)$ monotonicity tester for Boolean functions over the hypercube.  SIAM Journal on Computing (SICOMP), 45(2):461–472, 2014.
  * [CS14b] Deeparnab Chakrabarty and C. Seshadhri.  An optimal lower bound for monotonicity testing over hypergrids.  Theory of Computing, 10:453–464, 2014.
  * [CST14] Xi Chen, Rocco A. Servedio, and Li-Yang. Tan.  New algorithms and lower bounds for monotonicity testing.  In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), 2014.
  * [CWX17] Xi Chen, Erik Waingarten, and Jinyu Xie.  Beyond talagrand: New lower bounds for testing monotonicity and unateness.  In Proceedings, ACM Symposium on Theory of Computing (STOC), 2017\.
  * [DGL+99] Yevgeny Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky.  Improved testing algorithms for monotonicity.  Proceedings, International Workshop on Randomization and Computation (RANDOM), 1999.
  * [EKK+00] Funda Ergun, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan.  Spot-checkers.  J. Comput. System Sci., 60(3):717–751, 2000.
  * [FGL14] Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish.  Partial tests, universal tests and decomposability.  In Innovations in Theoretical Computer Science, ITCS. ACM, 2014\.
  * [FH23] Renato Ferreira Pinto Jr and Nathaniel Harms.  Distribution testing under the parity trace, 2023.
  * [Fis04] Eldar Fischer.  On the strength of comparisons in property testing.  Information and Computation, 189(1):107–116, 2004.
  * [FLN+02] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, and Ronitt Rubinfeld.  Monotonicity testing over general poset domains.  Proceedings, ACM Symposium on Theory of Computing (STOC), 2002.
  * [FLV15] Eldar Fischer, Oded Lachish, and Yadu Vasudev.  Trading query complexity for sample-based testing and multi-testing scalability.  In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 2015.
  * [FR10] Shahar Fattal and Dana Ron.  Approximating the distance to monotonicity in high dimensions.  ACM Trans. on Algorithms (TALG), 6(3), 2010.
  * [GGL+00] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky.  Testing monotonicity.  Combinatorica, 20:301–337, 2000.
  * [GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Journal of the ACM, 45(4):653–750, 1998.
  * [GKW19] Elena Grigorescu, Akash Kumar, and Karl Wimmer.  Flipping out with many flips: Hardness of testing k-monotonicity.  SIAM J. Discret. Math., 33(4):2111–2125, 2019.
  * [GR16] Oded Goldreich and Dana Ron.  On sample-based testers.  ACM Trans. Comput. Theory, 8(2):7:1–7:54, 2016.
  * [HK03] Shirley Halevy and Eyal Kushilevitz.  Distribution-free property testing.  Proceedings, International Workshop on Randomization and Computation (RANDOM), 2003.
  * [HK08] Shirley Halevy and Eyal Kushilevitz.  Testing monotonicity over graph products.  Random Structures Algorithms, 33(1):44–67, 2008.
  * [HY22] Nathaniel Harms and Yuichi Yoshida.  Downsampling for testing and learning in product distributions.  In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, 2022.
  * [Kea98] Michael J. Kearns.  Efficient noise-tolerant learning from statistical queries.  J. ACM, 45(6):983–1006, 1998.
  * [KMS15] Subhash Khot, Dor Minzer, and Muli Safra.  On monotonicity testing and Boolean isoperimetric type theorems.  In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), 2015.
  * [KMS18] Subhash Khot, Dor Minzer, and Muli Safra.  On monotonicity testing and boolean isoperimetric-type theorems.  SIAM J. Comput., 47(6):2238–2276, 2018.
  * [KR00] Michael J. Kearns and Dana Ron.  Testing problems with sublearning sample complexity.  J. Comput. Syst. Sci., 61(3):428–456, 2000.
  * [LMN93] Nathan Linial, Yishay Mansour, and Noam Nisan.  Constant depth circuits, fourier transform, and learnability.  J. ACM, 40(3):607–620, 1993.
  * [LR01] Eric Lehman and Dana Ron.  On disjoint chains of subsets.  Journal of Combinatorial Theory, Series A, 94(2):399–404, 2001\.
  * [LRV22] Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan.  Properly learning monotone functions via local correction.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 75–86. IEEE, 2022.
  * [LV23] Jane Lange and Arsen Vasilyan.  Agnostic proper learning of monotone functions: beyond the black-box correction barrier.  CoRR, abs/2304.02700, 2023.
  * [PRV18] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma.  Parameterized property testing of functions.  ACM Trans. Comput. Theory, 9(4):17:1–17:19, 2018.
  * [Ras99] Sofya Raskhodnikova.  Monotonicity testing.  Masters Thesis, MIT, 1999.
  * [RRSW11] Dana Ron, Ronitt Rubinfeld, Muli Safra, and Omri Weinstein.  Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.  In Proceedings, International Workshop on Randomization and Computation (RANDOM), 2011.
  * [RS96] R. Rubinfeld and M. Sudan.  Robust characterization of polynomials with applications to program testing.  SIAM Journal of Computing, 25:647–668, 1996.
  * [SS08] Michael E. Saks and C. Seshadhri.  Parallel monotonicity reconstruction.  In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.
  * [Tal96] Michel Talagrand.  How much are increasing sets positively correlated?  Comb., 16(2):243–258, 1996.

##  Appendix A Low-Degree Algorithm with RCN: Proof of Theorem 4.6

In this section we prove Theorem 4.6, showing that concept classes with
bounded Fourier degree can be learned efficiently in the presence of random
classification noise (RCN). This fact is already implicit from previous works
[LMN93, Kea98], but we give a proof for the sake of completeness.

For $S\subseteq[d]$, the parity function $\chi_{S}\colon\\{\pm
1\\}^{d}\to\\{\pm 1\\}$ is defined as $\chi_{S}(x)=\prod_{i=1}^{d}x_{i}$. The
parity functions form a Fourier basis for the space of functions
$f\colon\\{\pm 1\\}^{d}\to\\{\pm 1\\}$ and the unique representation of $f$ is
given by

$f(x)=\sum_{S\subseteq[d]}\widehat{f}(S)\chi_{S}(x)\text{ where
}\widehat{f}(S)=\mathbb{E}_{x}[\chi_{S}(x)f(x)]$

is _Fourier coefficient_ for $f$ on $S$. The idea of the Low-Degree Algorithm
is to learn $f$ by learning its low-degree Fourier coefficients. From the
definition of $\widehat{f}(S)$, observe that an estimate of $\widehat{f}(S)$
can be viewed as a call to a statistical query oracle, which returns an
estimate of $\widehat{f}(S)$ to within some specified _allowed query error_ ,
$\alpha$. In [Kea98], Kearns showed how to simulate statistical query
algorithms using only examples with classification noise.

######  Theorem A.1 (Theorem 3 of [Kea98], paraphrased).

Suppose there is an algorithm which learns a concept class ${\cal C}$ of
Boolean functions over $\\{\pm 1\\}^{d}$ to error $\varepsilon$, using at most
$Q$ statistical queries with allowed query error $\alpha$. Then, for any
$\varepsilon,\delta\in(0,1)$, there is a learning algorithm for ${\cal C}$
which on any input $f\in{\cal C}$, uses at most

$O\left(\left(\frac{1}{\alpha(1-2\eta)}\right)^{2}\log\left(\frac{Q}{\delta}\right)+\frac{1}{\varepsilon^{2}}\log\left(\frac{1}{\delta\alpha(1-2\eta)}\right)\right)$

examples from $EX^{\eta}(f,\mathsf{unif}(\\{\pm 1\\}^{d}))$ and outputs a
hypothesis $h$ where $\mathbb{P}_{h}[d(f,h)\leq\varepsilon]\geq 1-\delta$.

In light of the above, we prove Theorem 4.6 by first giving an efficient
statistical query algorithm, and then applying Theorem A.1.

###### Proof of Theorem 4.6.

Since we assume $\sum_{S\colon|S|>\tau}\widehat{f}(S)^{2}\leq\varepsilon/2$
for all $f\in{\cal C}$, the idea is to use a statistical query to obtain an
estimate of $\widehat{f}(S)$ for all $|S|\leq\tau$. Define
$A:=\\{S\subseteq[d]:|S|\leq\tau\\}$ and note that

$\displaystyle|A|=\sum_{i=0}^{\tau}{d\choose
i}\leq\left(\frac{de}{\tau}\right)^{\tau}\leq O(d^{\tau})\text{.}$ (16)

We define our statistical query algorithm $L$ to do the following:

  1. 1.

For each $S\in A$, make a statistical query for an estimate of
$\widehat{f}(S)=\mathbb{E}_{x}[\chi_{S}(x)f(x)]$ to allowed query error
$\alpha=\sqrt{\varepsilon/(2|A|)}$. Let $Z_{S}$ denote the obtained estimate
for $\widehat{f}(S)$.

  2. 2.

Return $h\colon\\{\pm 1\\}^{d}\to\\{\pm 1\\}$ where
$h(x)=\texttt{sgn}\left(\sum_{S\in A}Z_{S}\chi_{S}(x)\right).$

We now prove that this hypothesis $h$ satisfies $\mathbb{P}_{x}\left[f(x)\neq
h(x)\right]\leq\varepsilon$. First, observe that

$\displaystyle\mathbb{P}_{x}\left[f(x)\neq
h(x)\right]=\frac{1}{4}\mathbb{E}_{x}\left[(f(x)-h(x))^{2}\right]\text{.}$
(17)

Now, if $f(x)\neq h(x)$, then $\left(f(x)-\sum_{S\in
A}Z_{S}\chi_{S}(x)\right)^{2}\geq 1=\frac{1}{4}(f(x)-h(x))^{2}$. In the other
case, clearly if $f(x)=h(x)$, then $\left(f(x)-\sum_{S\in
A}Z_{S}\chi_{S}(x)\right)^{2}\geq 0=\frac{1}{4}(f(x)-h(x))^{2}$. Thus, for any
$x\in\\{\pm 1\\}^{d}$, this inequality holds. Combining this observation with
eq. 17 yields

$\displaystyle\mathbb{P}_{x}\left[f(x)\neq h(x)\right]$
$\displaystyle\leq\mathbb{E}_{x}\left[\left(f(x)-\sum_{S\in
A}Z_{S}\chi_{S}(x)\right)^{2}\right]\text{.}$ (18)

In the next calculation, for $S\notin A$, let $Z_{S}:=0$. Now, writing
$f(x)=\sum_{S}\widehat{f}(S)\chi_{S}(x),$ expanding the squared sum, applying
linearity of expectation, and using the fact that
$\mathbb{E}_{x}[\chi_{S}(x)]=0$ for any $S\neq\emptyset$, the RHS of eq. 18 is
equal to

$\displaystyle\mathbb{E}_{x}\left[\left(\sum_{S}\chi_{S}(x)\left(\widehat{f}(S)-Z_{S}\right)\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{x}\left[\sum_{S,T}\chi_{S\Delta
T}(x)\left(\widehat{f}(S)-Z_{S}\right)\left(\widehat{f}(T)-Z_{T}\right)\right]$
$\displaystyle=\sum_{S}\left(\widehat{f}(S)-Z_{S}\right)^{2}\text{.}$ (19)

Using eq. 18, appendix A, and the fact that $|\widehat{f}(S)-Z_{S}|\leq\alpha$
for $S\in A$ and $\sum_{S\notin A}\widehat{f}(S)^{2}\leq\varepsilon/2$, yields

$\displaystyle d(f,h)=\mathbb{P}_{x}\left[f(x)\neq h(x)\right]$
$\displaystyle\leq\sum_{S}\left(\widehat{f}(S)-Z_{S}\right)^{2}=\sum_{S\in
A}\left(\widehat{f}(S)-Z_{S}\right)^{2}+\sum_{S\notin
A}\widehat{f}(S)^{2}\leq|A|\frac{\varepsilon}{2|A|}+\varepsilon/2=\varepsilon\text{.}$

Thus, $L$ makes $|A|\leq O(d^{\tau})$ statistical queries to $f$ with query
error $\alpha=\sqrt{\varepsilon/(2|A|)}$ and returns a hypothesis $h$
satisfying $d(f,h)\leq\varepsilon$. Therefore, applying Theorem A.1 completes
the proof of Theorem 4.6. ∎

##  Appendix B Coupon Collecting Learner: Proof of Lemma 4.3

###### Proof.

The learner is defined as follows. Take $s$ samples from
$EX^{\eta}(f,\mathsf{unif}([N]^{d}))$ and for each $x\in[N]^{d}$, let $m_{x}$
denote the number of times $x$ has been sampled. Let $m^{+}_{x},m^{-}_{x}$
denote the number of times $x$ has been sampled with the label $+1,-1$
respectively. The learner outputs the hypothesis $h\colon[N]^{d}\to\\{\pm
1\\}$ defined by $h(x)=\mathsf{sgn}(m^{+}_{x}-m^{-}_{x})$.

######  Claim B.1.

Suppose that $m_{x}\geq m:=\frac{2}{(1-2\eta)^{2}}\ln(2/\beta)$. Then
$\mathbb{P}[\mathsf{sgn}(m^{+}_{x}-m^{-}_{x})\neq f(x)]\leq\beta$.

###### Proof.

Each label seen for $x$ is an independent $\\{\pm 1\\}$-valued random variable
which is equal to $f(x)$ with probability $1-\eta$ and so
$\mathbb{E}[m^{+}_{x}-m^{-}_{x}]=m_{x}((1-\eta)f(x)+\eta(-f(x)))=m_{x}(1-2\eta)f(x)$.
Thus,

$\displaystyle\mathbb{P}\left[\mathsf{sgn}(m^{+}_{x}-m^{-}_{x})\neq
f(x)\right]\leq\mathbb{P}\left[\left|(m^{+}_{x}-m^{-}_{x})-\mathbb{E}[m^{+}_{x}-m^{-}_{x}]\right|\geq
m_{x}(1-2\eta)\right]\leq
2\exp\left(-\frac{2m_{x}^{2}(1-2\eta)^{2}}{4m_{x}}\right)\leq\beta$

by Hoeffding’s inequality and our bound on $m_{x}$. ∎

######  Claim B.2.

Suppose we take $s:=\ln(\frac{1}{\alpha})N^{2d}$ samples. Then
$\mathbb{P}[\exists x\in[N]^{d}\colon m_{x}=0]<\alpha$.

###### Proof.

For any $x$,
$\mathbb{P}[m_{x}=0]=(1-N^{-d})^{s}\leq\exp(-\frac{s}{N^{d}})\ll\alpha N^{-d}$
and a union bound completes the proof. ∎

The following claim is an immediate corollary of the previous claim.

######  Claim B.3.

Suppose we take $m\cdot\ln(\frac{2m}{\delta})N^{2d}$ samples. Then
$\mathbb{P}[\exists x\in[N]^{d}\colon m_{x}<m]<\frac{\delta}{2}$.

###### Proof.

Partition the samples into $m$ batches of size $\ln(\frac{2m}{\delta})N^{2d}$.
Invoke B.2 on each batch of samples with $\alpha:=\frac{\delta}{2m}$. By the
claim, each batch of samples contains a least $1$ copy of every point in
$[N]^{d}$ with probability at least $1-\frac{\delta}{2m}$. Thus, by a union
bound over the $m$ batches, our sample contains at least $m$ copies of every
point in $[N]^{d}$ with probability at least $1-\frac{\delta}{2}$. ∎

Let $m:=\frac{2}{(1-2\eta)^{2}}\ln\left(\frac{4}{\varepsilon\delta}\right)$
and $s:=m\ln(\frac{2m}{\delta})N^{2d}$. The learner takes $s$ samples from
$EX^{\eta}(f,\mathsf{unif}([N]^{d}))$. Let ${\cal E}$ denote the event that
$m_{x}\geq m$ for all $x\in[N]^{d}$. By B.3, we have $\mathbb{P}[{\cal E}]\geq
1-\frac{\delta}{2}$. For each $x\in[N]^{d}$, let
$\mathcal{B}_{x}=\mathbf{1}(\mathsf{sgn}(m_{x}^{+}-m_{x}^{-})\neq f(x))$, i.e.
the indicator that $x$ is misclassified by the learner.

By B.1, we have

$\displaystyle\mathbb{E}\left[\sum_{x\in[N]^{d}}\mathcal{B}_{x}\leavevmode\nobreak\
\Big{|}\leavevmode\nobreak\ {\cal
E}\right]\leq\frac{\varepsilon\delta}{2}N^{d}\text{ and thus
}\mathbb{P}\left[\sum_{x\in[N]^{d}}\mathcal{B}_{x}>\varepsilon
N^{d}\leavevmode\nobreak\ \Big{|}\leavevmode\nobreak\ {\cal
E}\right]\leq\frac{\delta}{2}$ (20)

by Markov’s inequality. Therefore,

$\displaystyle\mathbb{P}\left[\sum_{x\in[N]^{d}}\mathcal{B}_{x}>\varepsilon
N^{d}\right]$
$\displaystyle=\mathbb{P}\left[\sum_{x\in[N]^{d}}\mathcal{B}_{x}>\varepsilon
N^{d}\leavevmode\nobreak\ \Big{|}\leavevmode\nobreak\ {\cal
E}\right]\mathbb{P}[{\cal
E}]+\mathbb{P}\left[\sum_{x\in[N]^{d}}\mathcal{B}_{x}>\varepsilon
N^{d}\leavevmode\nobreak\ \Big{|}\leavevmode\nobreak\ \neg{\cal
E}\right]\mathbb{P}[\neg{\cal E}]$ (21)
$\displaystyle\leq\mathbb{P}\left[\sum_{x\in[N]^{d}}\mathcal{B}_{x}>\varepsilon
N^{d}\leavevmode\nobreak\ \Big{|}\leavevmode\nobreak\ {\cal
E}\right]+\mathbb{P}[\neg{\cal E}]$ (22)

which is at most $\delta$. The number of examples used by the learner is

$s=m\ln\left(\frac{2m}{\delta}\right)N^{2d}=\widetilde{O}\left(\frac{1}{(1-2\eta)^{2}}\left(\ln\frac{1}{\varepsilon}+\ln\frac{1}{\delta}\right)\right)\cdot
N^{O(d)}$

and this completes the proof. ∎

##  Appendix C Testing by Learning

######  Lemma C.1.

Let ${\cal X}$ be a domain, let $\mu$ be a measure over ${\cal X}$, and let
$\mathcal{F}\colon{\cal X}\to\\{\pm 1\\}$ be a class of Boolean-valued
functions over ${\cal X}$. Suppose that for every $\varepsilon\in(0,1)$ there
exists a learning algorithm $L$ for $\mathcal{F}$ under $\mu$ using
$s(\varepsilon)$ samples. Then for every $\varepsilon\in(0,1)$ there is an
$\varepsilon$-tester for $\mathcal{F}$ under $\mu$ using
$s(\varepsilon/4)+O(1/\varepsilon^{2})$ samples.

###### Proof.

We define the property testing algorithm $T$ as follows.

  1. 1.

Take $s:=s(\varepsilon/4,{\cal X})$ samples
$(x_{1},f(x_{1})),\ldots,(x_{s},f(x_{s}))$ and run $L$ to obtain a hypothesis
$h$ for $f$.

  2. 2.

Compute a function $g\in\mathcal{F}$ for which $d(h,g)=d(h,\mathcal{F})$. (We
remark that this step incurs a blowup in time-complexity, but does not require
any additional samples.)

  3. 3.

Take $s^{\prime}:=\frac{20}{\varepsilon^{2}}$ new samples
$(z_{1},f(z_{1})),\ldots,(z_{s^{\prime}},f(z_{s^{\prime}}))$ and let
$\alpha:=\frac{1}{s^{\prime}}\sum_{i=1}^{s^{\prime}}\mathbf{1}(g(z_{i})\neq
f(z_{i}))$ be an empirical estimate for $d(f,g)$.

  4. 4.

If $\alpha\leq\frac{3\varepsilon}{4}$, then accept. If
$\alpha>\frac{3\varepsilon}{4}$, then reject.

######  Claim C.2.

If $f\in\mathcal{F}$, then $\mathbb{P}[d(f,g)\leq\varepsilon/2]\geq 5/6$.

###### Proof.

By the guarantee of the learning algorithm, we have
$\mathbb{P}[d(f,h)\leq\varepsilon/4]\geq 5/6$. Now, since $g$ is a function in
$\mathcal{F}$ as close as possible to $h$, we have $d(h,g)\leq d(h,f)$. Thus,
if $d(f,h)\leq\varepsilon/4$, then $d(h,g)\leq\varepsilon/4$ as well. Thus, by
the triangle inequality, with probability at least $5/6$ we have $d(f,g)\leq
d(f,h)+d(h,g)\leq\varepsilon/2$ as claimed. ∎

Now, consider the quantity $\alpha$ from step (4) of the algorithm, $T$. Let
$X$ be the Bernoulli random variable which equals $1$ with probability
$d(f,g)$. Note that $\alpha=\frac{1}{s^{\prime}}\sum_{i=1}^{s^{\prime}}X_{i}$
where the $X_{i}$’s are independent copies of $X$. Using Hoeffding’s
inequality we have

$\displaystyle\mathbb{P}\left[|\alpha-d(f,g)|\geq\frac{\varepsilon}{4}\right]=\mathbb{P}\left[\left|\sum_{i=1}^{s^{\prime}}X_{i}-s^{\prime}\cdot
d(f,g)\right|\geq\frac{s^{\prime}\varepsilon}{4}\right]\leq
2\exp\left(-\frac{2\cdot(s^{\prime}\varepsilon/4)^{2}}{s^{\prime}}\right)=\frac{2}{e^{\frac{s^{\prime}\varepsilon^{2}}{8}}}$

which is at most $1/6$ when $s^{\prime}\geq 8\ln(12)/\varepsilon^{2}$. We can
now argue that the tester $T$ succeeds with probability at least $2/3$. There
are two cases to consider.

  1. 1.

$f\in\mathcal{F}$: By C.2, $d(f,g)>\varepsilon/2$ with probability less than
$1/6$ and by the above calculation $|\alpha-d(f,g)|\geq\varepsilon/4$ with
probability at most $1/6$. By a union bound, with probability at least $2/3$
neither event occurs, and conditioned on this we have $\alpha\leq
d(f,g)+\varepsilon/4\leq 3\varepsilon/4$ and the algorithm accepts.

  2. 2.

$d(f,\mathcal{F})\geq\varepsilon$: Then $d(f,g)\geq\varepsilon$ since
$g\in\mathcal{F}$. Again, $|\alpha-d(f,g)|<\varepsilon/4$ with probability at
least $5/6$ and conditioned on this event occurring we have
$\alpha>d(f,g)-\varepsilon/4\geq 3\varepsilon/4$ and the algorithm rejects.

Therefore, $T$ satisfies the conditions needed for lemma C.1. ∎