\section{Introduction}

In property testing and learning, the goal is to design algorithms that use as little information as
possible about the input while still being correct (with high probability). This includes using as
little information as possible about the probability distribution against which correctness is
measured. Information about the probability distribution could be in the form of guarantees on this
distribution (e.g.~it is guaranteed to be uniform, or Gaussian), or in the form of samples from the
distribution. So we want to minimize the requirements on this distribution, as well as the number of
samples used by the algorithm.

Progress on high-dimensional property testing and learning problems is usually made by studying
algorithms for the uniform distribution over the hypercube $\{\pm 1\}^d$, or the standard Gaussian
distribution over $\ensuremath{\mathbb{R}}^d$, as the simplest case. For example, efficiently learning
intersections of halfspaces is a major open problem in learning theory \cite{DKS18,KOS04}, and
progress on this problem has been made by studying the uniform distribution over the hypercube
$\{\pm 1\}^d$ and the Gaussian as special cases \cite{KKMS08,KOS08,Vem10a}.
Another important example is the class of degree-$k$ polynomial threshold functions (PTFs). Unlike
intersections of halfspaces, these can be efficiently learned in the PAC model~\cite{KOS04}, but
\emph{agnostic}\footnote{See the Glossary in \cref{glossary} for standard definitions in
learning theory and property testing.} learning is more challenging. Again, progress has been made
by studying the hypercube \cite{DHK+10}. An even more extreme example is the class of convex sets,
which are not learnable in the distribution-free PAC model, because they have infinite VC dimension,
but which become learnable under the Gaussian \cite{KOS08}. The uniform distribution over the
hypercube and the Gaussian are both examples of \emph{product distributions}, so the next natural
question to ask is, can these results be generalized to any \emph{unknown} product distribution?
A partial answer was given by Blais, O'Donnell, \& Wimmer \cite{BOW10} for some of these classes; in
this paper we resolve this question.

Similar examples appear in the property testing literature. Distribution-free property testing and
testing functions with domain $\ensuremath{\mathbb{R}}^d$ are emerging trends in the field (e.g.~\cite{BBBY12, DMN19,
Har19, CDS20, FY20, BFH21}). Testing monotonicity is one of the most well-studied problems in
property testing, and recent work \cite{BCS20} has extended this study to product distributions over
domain $\ensuremath{\mathbb{R}}^d$. Work of Chakrabarty \& Seshadhri \cite{CS16}, Khot, Minzer, \& Safra \cite{KMS18},
and Black, Chakrabarty, \& Seshadhri \cite{BCS18,BCS20} has resulted in efficient $o(d)$-query
algorithms for the hypercube $\{\pm 1\}^d$ \cite{KMS18} and the hypergrid $[n]^d$. Black, Chakrabarty,
\& Seshadhri \cite{BCS20} showed that testing monotonicity over unknown product distributions on
$\ensuremath{\mathbb{R}}^d$ could be done with $\widetilde O(d^{5/6})$ queries and $O(d^7)$ samples.  Their ``domain
reduction'' method is intricate and specialized for the problem of testing monotonicity.  We
improve\footnote{An early version of this paper proved a weaker result, with two-sided error and
worse sample complexity.} the sample complexity to $\widetilde O(d^3)$ using a much simpler proof.
We also generalize the testers of \cite{CFSS17,CGG+19} for convex sets and $k$-alternating
functions, respectively, and provide new testers for arbitrary functions of convex sets.

This paper provides a general framework for designing distribution-free testing and learning
algorithms under product distributions on $\ensuremath{\mathbb{R}}^d$, which may be finite or continuous. An algorithm
is distribution-free under product distributions if it does not require any prior knowledge of the
probability distribution, except the guarantee that it is a product distribution. The technique in
this paper, which we call \emph{downsampling}, improves upon previous methods (in particular,
\cite{BCS20,BOW10}), in a few ways. It is more general and does not apply only to a specific
type of algorithm \cite{BOW10} or a specific problem \cite{BCS20}, and we use it to obtain many
other results.  It is conceptually simpler. And it allows quantitative improvements over both
\cite{BOW10} and \cite{BCS20}.

\paragraph*{Organization.}
In \cref{section:results}, we describe the main results of this paper
in context of the related work. In \cref{section:techniques}, we briefly describe the main
techniques in the paper. \cref{section:downsampling} presents the definitions and lemmas required by
the main results. The following sections present the proofs of the results. For simplicity, the main
body of the paper handles only continuous product distributions; finite distributions are handled in
\cref{section:discrete distributions}.
Definitions of standard terminology in property testing and machine learning can be found in the
Glossary in Section~\ref{glossary}.


\subsection{Results}
\label{section:results}

See \cref{table:testing} for a summary of our results on property testing, and \cref{table:learning}
for a summary of our results on learning.


\subsubsection{Testing Monotonicity}

Testing monotonicity is the problem of testing whether an unknown function $f : X \to \{0,1\}$ is
monotone, where $X$ is a partial order. It is one of the most commonly studied problems in the field
of property testing. Previous work on this problem has mostly focused on uniform probability
distributions (exceptions include \cite{AC06,HK07,CDJS17,BFH21}) and finite domains.  However, there
is growing interest in property testing for functions on domain $\ensuremath{\mathbb{R}}^d$
(\cite{BBBY12,DMN19,Har19,CDS20,FY20,BFH21}) and \cite{BCS20} generalized the problem to this
domain.

Testing monotonicity under product distributions has been studied a few times.
Ailon \& Chazelle \cite{AC06} gave a distribution-free monotonicity tester for real-valued functions
under product distributions on $[n]^d$, with query complexity $O(\tfrac{1}{\epsilon} d2^d \log n)$.
Chakrabarty \emph{et al.}~\cite{CDJS17} improved this to $O(\tfrac{1}{\epsilon} d \log n)$ and gave
a matching lower bound. This lower bound applies to the \emph{real-valued} case. For the
\emph{boolean-valued} case, monotonicity testers under the uniform distribution on $\{\pm 1\}^d$
\cite{CS16,KMS18} and $[n]^d$ \cite{BCS18,BCS20} are known with query complexity $o(d)$. In
\cite{BCS20}, an $o(d)$-query tester was given for domain $\ensuremath{\mathbb{R}}^d$. That paper showed
that there is a one-sided, non-adaptive, distribution-free monotonicity tester under product
distributions on $\ensuremath{\mathbb{R}}^d$, with query complexity
$O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\poly\log(d/\epsilon)\right)$ and sample complexity
$O((d/\epsilon)^7)$. In this paper we improve the sample complexity to $\widetilde
O((d/\epsilon)^3)$, while greatly simplifying the proof.

\begin{restatable}{restate-theorem}{thmmonotonicity}\label{thm:monotonicity}
There is a one-sided, non-adaptive $\epsilon$-tester for monotonicity of functions $\ensuremath{\mathbb{R}}^d \to \{0,1\}$
that is distribution-free under (finite or continuous) product distributions, using
\[
O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\poly\log(d/\epsilon)\right)
\]
queries and $O(\frac{d^3}{\epsilon^3}\log(d/\epsilon))$ samples.
\end{restatable}

The main result of \cite{BCS20} is a ``domain reduction'' theorem, allowing a change of domain from
$[n]^d$ to $[r]^d$ where $r = \poly(d/\epsilon)$; by applying this theorem together with their
earlier $\widetilde O(\tfrac{d^{5/6}}{\epsilon^{4/3}} \poly\log(dn))$-query tester for the uniform
distribution on $[n]^d$, they obtain a tester for monotone functions with query complexity
independent of $n$. Our result replaces this domain reduction method with a simpler and more general
2-page argument, and gives a different generalization to the distribution-free case. See
\cref{section:monotonicity} for the proofs.

\begin{table}[t]
\caption{Testing results.}\label{table:testing}
\begin{tabularx}{470pt}{ X | p{55pt} | p{60pt} | p{50pt} | X }
  & $\mathsf{unif}(\{\pm 1\}^d)$ & $\mathsf{unif}([n]^d)$ & Gaussian & $\forall$ Products \\
\hline
1-Sided Testing Monotonicity \newline (Query model)
  & $\widetilde O\left(\frac{\sqrt d}{\epsilon^2}\right)$ \newline
                \cite{KMS18}
  & $\widetilde O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\right)$ \newline
                 \cite{BCS20}
  & $\widetilde O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\right)$ \newline
                 \cite{BCS20}
  & $\widetilde O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\right)$ queries,\hfill \newline
    $\widetilde O\left(\left(\frac{d}{\epsilon}\right)^3\right)$ samples\hfill \newline
     (Thm.~\ref{thm:monotonicity}) \\
\hline
1-Sided Testing Convex Sets \newline (Sample model)
  & --
  & --
  & $\left(\frac{d}{\epsilon}\right)^{(1+o(1))d}$ \newline $2^{\Omega(d)}$ \newline
    \cite{CFSS17}
  & $\left(\frac{d}{\epsilon}\right)^{(1+o(1))d}$ (Thm.~\ref{thm:convex tester}) \\
\hline
Tolerant Testing Functions of $k$ Convex Sets \newline (Sample model)
  & --
  & --
  & --
  & $\left(\frac{dk}{\epsilon}\right)^{O(d)}$ (Thm.~\ref{thm:convex distance approximator}) \\
\hline
Tolerant Testing $k$-Alternating Functions \newline (Sample model)
  & --
  & $\left(\frac{dk}{\tau}\right)^{O\left(\frac{k\sqrt d}{\tau^2}\right)}$ \newline
    $\tau = \epsilon_2-3\epsilon_1$ \newline
    \cite{CGG+19}
  & --
  & $\left(\frac{dk}{\tau}\right)^{O\left(\frac{k\sqrt d}{\tau^2}\right)}$ \newline
    $\tau = \epsilon_2-\epsilon_1$ \newline
    (Thm.~\ref{thm:testing k-alternating})
\end{tabularx}
\end{table}

\begin{table}[t]
\caption{\emph{Learning results. All learning algorithms are agnostic except that of
\cite{Vem10a}. The PTF result for the Gaussian follows from the two cited works but is not stated in
either. All statements are informal, see references for restrictions and
qualifications. For PTFs, $\psi(k,\epsilon) :=
\min\left\{O(\epsilon^{-2^{k+1}}),
2^{O(k^2)}\left(\log(1/\epsilon)/\epsilon^2\right)^{4k+2}\right\}$.}}\label{table:learning}
\begin{tabularx}{470pt}{X | p{55pt} | p{50pt} | p{90pt} | X}
& $\mathsf{unif}(\{\pm 1\}^d)$ & $\mathsf{unif}([n]^d)$ & Gaussian & $\forall$ Products \\
\hline
Functions of $k$ \newline Convex Sets
  & $\Omega(2^d)$
  & --
  & $d^{O\left(\frac{\sqrt d}{\epsilon^4}\right)}, 2^{\Omega(\sqrt d)}$ \newline
          \cite{KOS08}
  & $O\left(\frac{1}{\epsilon^2}\left(\frac{6dk}{\epsilon}\right)^d\right)$
    (Thm.~\ref{thm:learning convex sets})
           \\
\hline
Functions of $k$ \newline Halfspaces
  & $d^{O\left(\frac{k^2}{\epsilon^4}\right)}$ \newline \cite{KKMS08}
  & $(dn)^{O\left(\frac{k^2}{\epsilon^4}\right)}$ \newline \cite{BOW10}
  & $d^{O\left(\frac{\log k}{\epsilon^4}\right)},$ \newline
    $\poly\left(d, \left(\frac{k}{\epsilon}\right)^k\right)$ \newline \cite{KOS08,Vem10a}
    (Intersections only)
  & $\left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k^2}{\epsilon^4}\right)}$
    (Thm.~\ref{thm:halfspaces}) \\
\hline
Degree-$k$ PTFs
  & $d^{\psi(k,\epsilon)}$ \newline \cite{DHK+10}
  & $(dn)^{\psi(k,\epsilon)}$ \newline \cite{DHK+10,BOW10}
  & $d^{\psi(k,\epsilon)}$ \newline \cite{DHK+10,BOW10}
  & $\left(\frac{dk}{\epsilon}\right)^{\psi(k,\epsilon)}$ (Thm.~\ref{thm:ptfs}) \\
\hline
$k$-Alternating \newline Functions
  & $2^{\Theta\left(\frac{k \sqrt d}{\epsilon}\right)}$ \newline \cite{BCO+15}
  & $\left(\frac{dk}{\tau}\right)^{O\left(\frac{k \sqrt d}{\tau^2} \right)}$ \newline
    (Testing) \cite{CGG+19}
  & --
  & $\left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k\sqrt d}{\epsilon^2}\right)}$
    (Thm.~\ref{thm:k-alternating}) \\
\hline
\end{tabularx}
\end{table}

\subsubsection{Learning Functions of Halfspaces}

Intersections of $k$ halfspaces have VC dimension $\Theta(dk\log k)$~\cite{BEHW89,CMK19}, so the
sample complexity of learning is known, but it is not possible to efficiently find $k$ halfspaces
whose intersection is correct on the sample, unless $\mathsf{P}=\mathsf{NP}$~\cite{BR92}. Therefore
the goal is to find efficient ``improper'' algorithms that output a function other than an
intersection of $k$ halfspaces. Several learning algorithms for intersections of $k$ halfspaces
actually work for arbitrary functions of $k$ halfspaces. We will write $\ensuremath{\mathcal{B}}_k$ for the set of all
functions $[k] \to \{0,1\}$, and for any class $\ensuremath{\mathcal{F}}$ of functions we will write $\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{F}}$ as the
set of all functions $x \mapsto g(f_1(x), \dotsc, f_k(x))$ where $g \in \ensuremath{\mathcal{B}}_k$ and each $f_i \in
\ensuremath{\mathcal{F}}$. Then for $\ensuremath{\mathcal{H}}$ the class of halfspaces, Klivans, O'Donnell, \& Servedio~\cite{KOS04} gave a
(non-agnostic) learning algorithm for $\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}}$ over the uniform distribution on $\{\pm 1\}^d$
with complexity $d^{O(k^2/\epsilon^2)}$, Kalai, Klivans, Mansour, \& Servedio~\cite{KKMS08}
presented an agnostic algorithm with complexity $d^{O(k^2/\epsilon^4)}$ in the same setting using
``polynomial regression''\!\!.

Polynomial regression is a powerful technique, so it is important to understand when it can be
applied. Blais, O'Donnell, \& Servedio~\cite{BOW10} studied how to generalize it to arbitrary
product distributions. With their method, they obtained an agnostic learning algorithm for $\ensuremath{\mathcal{B}}_k
\circ \ensuremath{\mathcal{H}}$ with complexity $(dn)^{O(k^2/\epsilon^4)}$ for product distributions $X_1 \times \dotsm
\times X_d$ where each $|X_i|=n$, and complexity $d^{O(k^2/\epsilon^4)}$ for the ``polynomially
bounded'' continuous distributions. This is not a complete generalization, because, for example, on
the grid $[n]^d$ its complexity depends on $n$. This prevents a full
generalization to the domain $\ensuremath{\mathbb{R}}^d$. Their algorithm also requires some prior knowledge of the
support or support size. We use a different technique and fully generalize the polynomial regression
algorithm to arbitrary product distributions. See \cref{section:halfspaces} for the proof.

\begin{restatable}{restate-theorem}{thmhalfspaces}\label{thm:halfspaces}
There is a distribution-free, improper agnostic learning algorithm for $\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}}$ under
(continuous or finite) product distributions over $\ensuremath{\mathbb{R}}^d$, with time complexity
\[
\min\left\{
		\left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k^2}{\epsilon^4}\right)},
		O\left(\frac{1}{\epsilon^2}\left(\frac{3dk}{\epsilon}\right)^d\right)
	\right\} \,.
\]
\end{restatable}



\subsubsection{Learning Polynomial Threshold Functions}
Degree-$k$ PTFs are another generalization of halfspaces. A function $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ is a
degree-$k$ PTF if there is a degree-$k$ polynomial $p: \ensuremath{\mathbb{R}}^d \to \ensuremath{\mathbb{R}}$ such that $f(x) =
\sign(p(x))$. Degree-$k$ PTFs can be PAC learned in time $d^{O(k)}$ using linear
programming~\cite{KOS04}, but agnostic learning is more challenging. Diakonikolas~\emph{et
al.}~\cite{DHK+10} previously gave an agnostic learning algorithm for degree-$k$ PTFs in the uniform
distribution over $\{\pm 1\}^d$ with time complexity $d^{\psi(k,\epsilon)}$, where
\[
\psi(k,\epsilon) := \min\left\{O(\epsilon^{-2^{k+1}}),
2^{O(k^2)}\left(\log(1/\epsilon)/\epsilon^2\right)^{4k+2}\right\} \,.
\]
The main result of that paper is an upper bound on the noise sensitivity of PTFs. Combined with the
reduction of Blais \emph{et al.}~\cite{BOW10}, this implies an algorithm for the uniform
distribution over $[n]^d$ with complexity $(dn)^{\psi(k,\epsilon)}$ and for the Gaussian
distribution with complexity $d^{\psi(k,\epsilon)}$.

Our agnostic learning algorithm for degree-$k$ PTFs eliminates the dependence on $n$ and works for
any unknown product distribution over $\ensuremath{\mathbb{R}}^n$, while matching the complexity of~\cite{DHK+10} for
the uniform distribution over the hypercube.  See \cref{section:ptfs} for the proof.

\begin{restatable}{restate-theorem}{thmptfs}\label{thm:ptfs}
There is an improper agnostic learning algorithm for degree-$k$ PTFs under
(finite or continuous) product distributions over $\ensuremath{\mathbb{R}}^d$, with time complexity
\[
\min\left\{ \left(\frac{kd}{\epsilon}\right)^{\psi(k,\epsilon)} \;,\;
O\left(\frac{1}{\epsilon^2}\left(\frac{9dk}{\epsilon}\right)^d\right)
\right\} \,.
\]
\end{restatable}

\subsubsection{Testing \& Learning Convex Sets}

One of the first properties (sets) of functions $\ensuremath{\mathbb{R}}^d \to \{0,1\}$ to be studied in the property
testing literature is the set of indicator functions of convex sets, i.e.~functions $f : \ensuremath{\mathbb{R}}^d \to
\{0,1\}$ where $f^{-1}(1)$ is convex. Write $\ensuremath{\mathcal{C}}$ for this class of functions. This problem has been
studied in various models of testing \cite{Ras03, RV04, CFSS17, BMR19, BB20}. In this paper we
consider the \emph{sample-based} model of testing, where the tester receives only random examples of
the function and cannot make queries.  This model of testing has received a lot of recent attention
(e.g.~\cite{BBBY12, BMR19, BY19, CFSS17, GR16, Har19, RR21, BFH21}), partly because it matches the
standard sample-based model for learning algorithms.

Chen \emph{et al.}~\cite{CFSS17} gave a sample-based tester for $\ensuremath{\mathcal{C}}$ under the Gaussian
distribution on $\ensuremath{\mathbb{R}}^d$ with one-sided error and sample complexity $(d/\epsilon)^{O(d)}$, along with
a lower bound (for one-sided testers) of $2^{\Omega(d)}$. We match their upper bound while
generalizing the tester to be distribution-free under product distributions. See
\cref{section:convex sets} for proofs.

\begin{restatable}{restate-theorem}{thmconvextester}\label{thm:convex tester}
There is a sample-based distribution-free one-sided
$\epsilon$-tester for $\ensuremath{\mathcal{C}}$ under (finite or continuous) product distributions that uses at most
$O\left(\left(\frac{6d}{\epsilon}\right)^d\right)$ samples.
\end{restatable}

A more powerful kind of tester is an \emph{$(\epsilon_1,\epsilon_2)$-tolerant} tester, which must
accept (with high probability) any function that is $\epsilon_1$-close to the property, while
rejecting functions that are $\epsilon_2$-far. Tolerantly testing convex sets has been studied by
\cite{BMR16} for the uniform distribution over the 2-dimensional grid, but not (to the best of our
knowledge) in higher dimensions. We obtain a sample-based tolerant tester (and distance)
approximator for convex sets in high dimension. In fact, recall that $\ensuremath{\mathcal{B}}_k$ is the set of all
functions $\{0,1\}^k \to \{0,1\}$ and $\ensuremath{\mathcal{B}}' \subset \ensuremath{\mathcal{B}}_k$ any subset, so $\ensuremath{\mathcal{B}}' \circ \ensuremath{\mathcal{C}}$ is any property
of functions of convex sets. We obtain a distance approximator for any such property:

\begin{restatable}{restate-theorem}{thmconvexdistance}\label{thm:convex distance approximator}
Let $\ensuremath{\mathcal{B}}' \subset \ensuremath{\mathcal{B}}_k$.  There is a sample-based distribution-free algorithm under (finite or
continuous) product distributions that approximates distance to $\ensuremath{\mathcal{B}}' \circ \ensuremath{\mathcal{C}}$ up to additive
error $\epsilon$ using $O\left(\frac{1}{\epsilon^2}\left(\frac{3dk}{\epsilon}\right)^d \right)$
samples. Setting $\epsilon = (\epsilon_2-\epsilon_1)/2$ we obtain an
$(\epsilon_1,\epsilon_2)$-tolerant tester with sample complexity
$O\left(\frac{1}{(\epsilon_2-\epsilon_1)^2}\left(\frac{6dk}{\epsilon_2-\epsilon_1}\right)^d\right)$.
\end{restatable}

General distribution-free learning of convex sets is not possible, since this class has infinite VC
dimension. However, they can be learned under the Gaussian distribution. Non-agnostic learning under
the Gaussian was studied by Vempala \cite{Vem10a,Vem10b}. Agnostic learning under the Gaussian was
studied by Klivans, O'Donnell, \& Servedio \cite{KOS08} who presented a learning algorithm with
complexity $d^{O(\sqrt{d}/\epsilon^4)}$, and a lower bound of $2^{\Omega(\sqrt d)}$.

Unlike the Gaussian, there is a trivial lower bound of $\Omega(2^d)$ in arbitrary product
distributions, because any function $f : \{\pm 1\}^d \to \{0,1\}$ belongs to this class. However, unlike
the general distribution-free case, we show that convex sets (or any functions of convex sets) can
be learned under unknown product distributions.

\begin{restatable}{restate-theorem}{thmlearningconvexsets}\label{thm:learning convex sets}
There is an agnostic learning algorithm for $\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{C}}$ under
(finite or continuous) product distributions over $\ensuremath{\mathbb{R}}^d$, with time complexity
$O\left(\frac{1}{\epsilon^2} \cdot \left(\frac{6dk}{\epsilon}\right)^d\right)$.
\end{restatable}


\subsubsection{Testing \& Learning $k$-Alternating Functions}

A $k$-alternating function $f : X \to \{\pm 1\}$ on a partial order $X$ is one where for any chain $x_1
< \cdots < x_m$ in $X$, $f$ changes value at most $k$ times. Learning $k$-alternating functions on
domain $\{\pm 1\}^d$ was studied by Blais \emph{et al.}~\cite{BCO+15}, motivated by the fact that these
functions are computed by circuits with few negation gates. They show that $2^{\Theta(k
\sqrt{d}/\epsilon)}$ samples are necessary and sufficient in this setting.  Canonne \emph{et
al.}~\cite{CGG+19} later obtained an algorithm for $(\epsilon_1,\epsilon_2)$-tolerant testing
$k$-alternating functions, when $\epsilon_2 > 3\epsilon_1$, in the uniform distribution over
$[n]^d$, with query complexity $(kd/\tau)^{O(k \sqrt{d} / \tau^2)}$, where $\tau =
\epsilon_2-3\epsilon_1$.

We obtain an agnostic learning algorithm for $k$-alternating functions that matches the query
complexity of the tester in~\cite{CGG+19}, and nearly matches the complexity of the (non-agnostic)
learning algorithm of~\cite{BCO+15} for the uniform distribution over the hypercube. See
\cref{section:k alternating} for proofs.

\begin{restatable}{restate-theorem}{thmkalternating}\label{thm:k-alternating}
There is an agnostic learning algorithm for $k$-alternating functions under
(finite or continuous) product distributions over $\ensuremath{\mathbb{R}}^d$ that runs in time
at most
\[
\min\left\{
	\left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k \sqrt d}{\epsilon^2}\right)},
	O\left(\frac{1}{\epsilon^2}\left(\frac{3kd}{\epsilon}\right)^d\right)
	\right\} \,.
\]
\end{restatable}

We also generalize the tolerant tester of \cite{CGG+19} to be distribution-free under product
distributions, and eliminate the condition $\epsilon_2 > 3\epsilon_1$.

\begin{restatable}{restate-theorem}{thmtestingkalternating}\label{thm:testing k-alternating}
For any $\epsilon_2 > \epsilon_1 > 0$, let $\tau = (\epsilon_2-\epsilon_1)/2$, there is a
sample-based $(\epsilon_1,\epsilon_2)$-tolerant tester for $k$-alternating functions using
$\left(\frac{dk}{\tau}\right)^{O\left(\frac{k\sqrt d}{\tau^2}\right)}$ samples, which is
distribution-free under (finite or continuous) product distributions over $\ensuremath{\mathbb{R}}^d$.
\end{restatable}





\subsection{Techniques}\label{section:techniques}

What connects these diverse problems is a notion of rectilinear surface area or isoperimetry that we
call ``block boundary size''\!\!.  There is a close connection between learning \& testing and
various notions of isoperimetry or surface area (e.g.~\cite{CS16,KOS04,KOS08,KMS18}). We show that
testing or learning a class $\ensuremath{\mathcal{H}}$ on product distributions over $\ensuremath{\mathbb{R}}^d$ can be reduced to testing
and learning on the \emph{uniform} distribution over $[r]^d$, where $r$ is determined by the block
boundary size, and we call this reduction ``downsampling''\!\!. The name \emph{downsampling} is used
in image and signal processing for the process of reducing the resolution of an image or reducing
the number of discrete samples used to represent an analog signal. We adopt the name because our
method can be described by analogy to image or signal processing as the following 2-step process:
\begin{enumerate}
  \item Construct a ``digitized'' or ``pixellated'' image of the function $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ by
    sampling from the distribution and constructing a grid in which each cell has roughly equal
    probability mass; and
	\item Learn or test the ``low-resolution'' pixellated function.
\end{enumerate}
As long as the function $f$ takes a constant value in the vast majority of ``pixels''\!\!, the low
resolution version seen by the algorithm is a good enough approximation for testing or learning.
The block boundary size is, informally, the number of pixels on which $f$ is not constant.

This technique reduces distribution-free testing and learning problems to the uniform distribution
in a way that is conceptually simpler than in the prior work \cite{BOW10,BCS20}. However, some
technical challenges remain.  The first is that it is not always easy to bound the number of
``pixels'' on which a function $f$ is not constant -- for example, for PTFs. Second, unlike in the
uniform distribution, the resulting downsampled function class on $[r]^d$ is not necessarily ``the
same'' as the original class -- for example, halfspaces on $\ensuremath{\mathbb{R}}^d$ are not downsampled to halfspaces
on $[r]^d$, since the ``pixels'' are not of equal size. Thus, geometric arguments may not work,
unlike the case for actual images.

A similar technique of constructing ``low-resolution'' representations of the input has been used
and rediscovered ad-hoc a few times in the property testing literature; in prior work, it was
restricted to the uniform distribution over $[n]^d$ \cite{KR00,Ras03,FR10,BY19,CGG+19} (or the
Gaussian in \cite{CFSS17}).  With this paper, we aim to provide a unified and generalized study of
this simple and powerful technique.

\subsection{Block Boundary Size}

Informally, we define the \emph{$r$-block boundary size} $\mathsf{bbs}(\ensuremath{\mathcal{H}},r)$ of a class $\ensuremath{\mathcal{H}}$ of functions
$\ensuremath{\mathbb{R}}^d \to \{0,1\}$ as the maximum number of grid cells on which a function $f \in \ensuremath{\mathcal{H}}$ is non-constant,
over all possible $r \times \dotsm \times r$ grid partitions of $\ensuremath{\mathbb{R}}^d$ (which are not necessarily
evenly spaced) -- see \cref{section:downsampling} for formal definitions. Whether downsampling can
be applied to $\ensuremath{\mathcal{H}}$ depends on whether
\[
  \lim_{r \to \infty} \frac{\mathsf{bbs}(\ensuremath{\mathcal{H}},r)}{r^d} \to 0 \,,
\]
and the complexity of the algorithms depends on how large $r$ must be for the non-constant blocks to
vanish relative to the whole $r^d$ grid. A general observation is that any function class $\ensuremath{\mathcal{H}}$
where downsampling can be applied can be learned under unknown product distributions with a finite
number of samples; for example, this holds for convex sets even though the VC dimension is infinite.

\begin{proposition}[Consequence of \cref{lemma:brute force}]
Let $\ensuremath{\mathcal{H}}$ be any set of functions $\ensuremath{\mathbb{R}}^d \to \{0,1\}$ (measurable with respect to continuous product
distributions) such that
\[
  \lim_{r \to \infty} \frac{\mathsf{bbs}(\ensuremath{\mathcal{H}},r)}{r^d} = 0 \,.
\]
Then there is some function $\delta(d,\epsilon)$ such that $\ensuremath{\mathcal{H}}$ is distribution-free learnable
under product distributions, up to error $\epsilon$, with $\delta(d,\epsilon)$ samples.
\end{proposition}

For convex sets, monotone functions, $k$-alternating functions, and halfspaces, $\mathsf{bbs}(\ensuremath{\mathcal{H}},r)$ is
easy to calculate. For degree-$k$ PTFs, it is more challenging. We say that a function $f : \ensuremath{\mathbb{R}}^d
\to \{0,1\}$ induces a connected component $S$ if for every $x,y \in S$ there is a continuous curve in
$\ensuremath{\mathbb{R}}^d$ from $x$ to $y$ such that $f(z)=f(x)=f(y)$ for all $z$ on the curve, and $S$ is a maximal
such set. Then we prove a general lemma that bounds the block boundary size by the number of
connected components induced by functions $f \in \ensuremath{\mathcal{H}}$.

\begin{lemma}[Informal, see \cref{lemma:bbs for low-components}]
Suppose that
for any axis-aligned affine subspace $A$ of affine dimension $n \leq d$, and any
function $f \in \ensuremath{\mathcal{H}}$, $f$ induces at most $k^n$ connected components in $A$. Then for $r =
\Omega(dk/\epsilon)$, $\mathsf{bbs}(\ensuremath{\mathcal{H}},r) \leq \epsilon \cdot r^d$.
\end{lemma}

This lemma in fact generalizes all computations of block boundary size in this paper (up to constant
factors in $r$). Using a theorem of Warren \cite{War68}, we get that any degree-$k$ polynomial
$\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ achieves value 0 in at most $\epsilon r^d$ grid cells, for sufficiently large $r
= \Omega(dk/\epsilon)$ (\cref{cor:ptf bbs bound}).

\subsection{Polynomial Regression}

The second step of downsampling is to find a testing or learning algorithm that works for the
uniform distribution over the (not necessarily evenly-spaced) hypergrid. Most of our learning
results use \emph{polynomial regression}.  This is a powerful technique introduced in~\cite{KKMS08}
that performs linear regression over a vector space of functions that approximately spans the
hypothesis class. This method is usually applied by using Fourier analysis to construct such an
approximate basis for the hypothesis class~\cite{BOW10,DHK+10,CGG+19}. This was the method used, for
example, by Blais, O'Donnell, \& Wimmer~\cite{BOW10} to achieve the $\poly(dn)$-time algorithms for
intersections of halfspaces.

We take the same approach but we use the Walsh basis for functions on domain $[n]^d$
(see e.g.~\cite{BRY14}) instead of the bases used in the prior works.  We show that if one can
establish bounds on the noise sensitivity in the Fourier basis for the hypothesis class restricted
to the uniform distribution over $\{\pm 1\}^d$, then one gets a bound on the number of Walsh functions
required to approximately span the ``downsampled'' hypothesis class. In this way, we establish that
if one can apply standard Fourier-analytic techniques to the hypothesis class over the
\emph{uniform} distribution on $\{\pm 1\}^d$ and calculate the block boundary size, then the results
for the hypercube essentially carry over to the distribution-free setting for product distributions
on $\ensuremath{\mathbb{R}}^d$.

An advantage of this technique is that both noise sensitivity and block boundary size grow at most
linearly during function composition: for functions $f(x) = g(h_1(x),\dotsc,h_k(x))$ where each
$h_i$ belongs to the class $\ensuremath{\mathcal{H}}$, the noise sensitivity and block boundary size grow at most
linearly in $k$. Therefore learning results for $\ensuremath{\mathcal{H}}$ obtained in this way are easy to extend to
arbitrary compositions of $\ensuremath{\mathcal{H}}$, which is how we get our result for intersections of halfspaces.

\section{Downsampling}
\label{section:downsampling}

We will now introduce the main definitions, notation, and lemmas required by our main results. The
purpose of this section is to establish the main conceptual component of the downsampling technique:
that functions with small enough block boundary size can be efficiently well-approximated by a
``coarsened'' version of the function that is obtained by random sampling.
See Figure~\ref{fig:block partition} for an illustration of the following definitions.

\begin{figure}
	\centering
	\includegraphics[scale=0.6]{figure.png}
	\caption{Left: Random grid $X$ (pale lines) with induced block partition (thick lines)
	and $\mathsf{blockpoint}$ values (dots), superimposed on $f^{-1}(1)$ (gray polygon).
	Right: $f^\mathsf{coarse}$ (grey) compared to $f$ (polygon outline).}\label{fig:block partition}
\end{figure}
\begin{definition}[Block Partitions]
An $r$-\emph{block partition} of $\ensuremath{\mathbb{R}}^d$ is a pair of functions $\mathsf{block}
: \ensuremath{\mathbb{R}}^d \to {[r]}^d$ and $\mathsf{blockpoint} : {[r]}^d \to \ensuremath{\mathbb{R}}^d$ obtained as follows.
For each $i \in [d],j \in [r-1]$ let $a_{i,j} \in \ensuremath{\mathbb{R}}$ such that $a_{i,j} <
a_{i,j+1}$ and define $a_{i,0}=-\infty, a_{i,r}=\infty$ for each $i$. For each
$i \in [d], j \in [r]$ define the interval $B_{i,j} = (a_{i,j-1},a_{i,j}]$ and a
point $b_{i,j} \in B_{i,j}$. The function $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ is defined
by setting $\mathsf{block}(x)$ to be the unique vector $v \in [r]^d$ such that $x_i \in
B_{i,v_i}$ for each $i \in [d]$. The function $\mathsf{blockpoint} : [r]^d \to \ensuremath{\mathbb{R}}^d$ is
defined by setting $\mathsf{blockpoint}(v) = (b_{1,v_1}, \dotsc, b_{d,v_d})$; note that
$\mathsf{blockpoint}(v) \in \mathsf{block}^{-1}(v)$ where $\mathsf{block}^{-1}(v) = \{ x \in \ensuremath{\mathbb{R}}^d :
\mathsf{block}(x) = v\}$.
\end{definition}

\begin{definition}[Block Functions and Coarse Functions]
For a function $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$, we define $f^\mathsf{block} : [r]^d \to \{\pm 1\}$
as $f^\mathsf{block} := f \circ \mathsf{blockpoint}$ and $f^\mathsf{coarse} : \ensuremath{\mathbb{R}}^d \to \ensuremath{\mathbb{R}}$ as
$f^\mathsf{coarse} := f^\mathsf{block} \circ \mathsf{block} = f \circ \mathsf{blockpoint} \circ \mathsf{block}$. For any set
$\ensuremath{\mathcal{H}}$ of functions $\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$, we define $\ensuremath{\mathcal{H}}^\mathsf{block} := \{
f^\mathsf{block} \;|\; f \in \ensuremath{\mathcal{H}} \}$.  For a distribution $\mu$ over
$\ensuremath{\mathbb{R}}^d$ and an $r$-block partition $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ we define
the distribution $\mathsf{block}(\mu)$ over $[r]^d$ as the distribution of
$\mathsf{block}(x)$ for $x \sim \mu$.
\end{definition}

\begin{definition}[Induced Block Partitions]
When $\mu$ is a product
distribution over $\ensuremath{\mathbb{R}}^d$, a \emph{random grid} $X$ of
length $m$ is the grid obtained by sampling $m$ points $x_1, \dotsc, x_m \in \ensuremath{\mathbb{R}}^d$
independently from $\mu$ and for each $i \in [d], j \in [m]$ defining $X_{i,j}$
to be the $j^\mathrm{th}$-smallest coordinate in dimension $i$ among all sampled
points. For any $r$ that divides $m$ we define an $r$-block partition depending
on $X$ by defining for each $i \in [d], j \in [r-1]$ the point $a_{i,j} =
X_{i,mj/r}$ so that the intervals are $B_{i,j} :=
(X_{i,m(j-1)/r}, X_{i,mj/r}]$ when $j \in \{2,\dotsc,r-1\}$ and $B_{i,1} =
(-\infty, X_{i,m/r}], B_{i,r} = (X_{i,m(r-1)/r},\infty)$; we let the points
$b_{i,j}$ defining $\mathsf{blockpoint}$ be arbitrary. This is the $r$-block
partition \emph{induced} by $X$.
\end{definition}

\begin{definition}[Block Boundary Size]\label{def:block boundary size}
For a block partition $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$, a
distribution $\mu$ over $\ensuremath{\mathbb{R}}^d$, and a function $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$,
we say $f$ is \emph{non-constant} on a block $v \in [r]^d$ if there are sets
$S,T \subset \mathsf{block}^{-1}(v)$ such that $\forall s \in S, t \in T: f(s) = 1, f(t)=-1$;
and $S,T$ have positive measure (in the product of Lebesgue measures).
For a function $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ and a number $r$, we define the $r$-block
boundary size $\mathsf{bbs}(f,r)$ as the maximum number of blocks on which $f$
is non-constant, where the maximum is taken over all $r$-block
partitions $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$.  For a set $\ensuremath{\mathcal{H}}$ of functions
$\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$, we define $\mathsf{bbs}(\ensuremath{\mathcal{H}},r) := \max\{ \mathsf{bbs}(f,r)
\;|\; f \in \ensuremath{\mathcal{H}}\}$.
\end{definition}

The \emph{total variation distance} between two distributions $\mu,\nu$ over a
finite domain $\ensuremath{\mathcal{X}}$ is defined as
\[
  \|\mu-\nu\|_\mathsf{TV} := \frac{1}{2} \sum_{x \in \ensuremath{\mathcal{X}}} |\mu(x)-\nu(x)|
  = \max_{S \subseteq \ensuremath{\mathcal{X}}} |\mu(S)-\nu(S)| \,.
\]
The essence of downsampling is apparent in the next proposition. It shows that
the distance of $f$ to its coarsened version $f^\mathsf{coarse}$ is bounded by two
quantities: the fraction of blocks in the $r$-block partition on which $f$ is
not constant, and the distance of the distribution $\mathsf{block}(\mu)$ to uniform.
When both quantities are small, testing or learning $f$ can be done by
testing or learning $f^\mathsf{coarse}$ instead. The uniform distribution over a
set $S$ is denoted $\mathsf{unif}(S)$:
\begin{proposition}\label{prop:distance to coarse}
Let $\mu$ be a continuous product distribution over $\ensuremath{\mathbb{R}}^d$, let $X$ be a
random grid, and let $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ be the induced
$r$-block partition. Then, for any measurable $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$,
the following holds with probability 1 over the choice of $X$:
\[
  \Pru{x \sim \mu}{f(x) \neq f^\mathsf{coarse}(x)}
  \leq r^{-d}\cdot \mathsf{bbs}(f,r)
    + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} \,.
\]
\end{proposition}
\begin{proof}
We first establish that, with probability 1 over $X$ and $x \sim \mu$,
if $f(x) \neq f^\mathsf{coarse}(x)$ then $f$ is non-constant on $\mathsf{block}(x)$.
Fix $X$ and suppose there exists a set $Z$
of positive measure such that for each $x \in Z, f(x) \neq f^\mathsf{coarse}(x)$
but $f$ is not non-constant on $\mathsf{block}(x)$, i.e.~for $V = \mathsf{block}^{-1}(\mathsf{block}(x))$, either
$\mu(V \cap f^{-1}(1)) = \mu(V)$ or $\mu(V \cap f^{-1}(-1)) = \mu(V)$. Then
there is $v \in [r]^d$ such that for $V = \mathsf{block}^{-1}(v)$, $\mu(Z \cap
V) > 0$.  Let $y = \mathsf{blockpoint}(v)$.  If $\mu(V \cap f^{-1}(f(y)) =
\mu(V)$ then $\mu(Z \cap V)=0$, so $\mu(V \cap f^{-1}(f(y)) = 0$. But
for random $X$, the probability that there exists $v \in [r]^d$ such
that $\mu(V \cap f^{-1}(\mathsf{blockpoint}(v))) = 0$ is 0, since
$\mathsf{blockpoint}(v)$ is random within $V$.

Assuming that the above event occurs,
\begin{align*}
\Pru{x \sim \mu}{f(x) \neq f^\mathsf{coarse}(x)}
  &\leq \Pru{x \sim \mu}{f \text{ is non-constant on } \mathsf{block}(x)} \\
  &\leq \Pru{v \sim [r]^d}{f \text{ is non-constant on } v}
    + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} \,.
\end{align*}
Since $v \sim [r]^d$ is uniform, the probability of hitting a non-constant block
is at most $r^{-d} \cdot \mathsf{bbs}(f,r)$.
\end{proof}

Next we give a bound on the number of samples required to ensure that $\mathsf{block}(\mu)$ is close to
uniform. We need the following lemma.
\begin{lemma}
\label{lemma:uniform intervals}
Let $\mu$ be continuous probability distribution over $\ensuremath{\mathbb{R}}$, $m,r \in \ensuremath{\mathbb{N}}$ such that $r$ divides
$m$, and $\delta \in (0,1/2)$. Let $X$ be a set of $m$ points sampled
independently from $\mu$. Write $X = \{ x_1, \dotsc, x_m \}$ labeled such that $x_1 < \dotsm < x_m$
(and write $x_0 = -\infty$).  Then for any $i \in [r]$,
\[
  \Pr{ \mu\left( x_{(i-1)(m/r)}, x_{i(m/r)} \right] < \frac{1-\delta}{r} } \leq
4 \cdot e^{-\frac{\delta^2 m}{32 r}} \,.
\]
\end{lemma}
\begin{proof}
We assume that $i-1 \leq r/2$. If $i-1 > r/2$ then we can repeat the following analysis with
the opposite ordering on the points in $X$. Write $x^* = x_{(i-1)\tfrac{m}{r}}$ and $\beta =
\mu(-\infty, x^*]$. First suppose that $(1-\delta/2)\frac{i-1}{r} < \beta <
(1+\delta/2)\frac{i-1}{r} \leq (1+\delta/2)/2$; we will bound the probability of this event later.

Let $t \in \ensuremath{\mathbb{R}}$ be the point such that $\mu(x^*,t] = (1-\delta)/r$ (which must exist since $\mu$ is
continuous). Let $\eta = \frac{\delta}{1-\delta} \geq \delta$.  Write $X^* = \{ x \in X : x > x^*
\}$. The expected value of $|X^* \cap (x^*,t]|$ is $|X^*| \frac{1-\delta}{r(1-\beta)} =
\left(1-\frac{i-1}{r}\right)\frac{1-\delta}{r(1-\beta)}$, where the factor $1-\beta$ in the
denominator is due to the fact that each element of $X^*$ is sampled from $\mu$ conditional on being
larger than $x^*$. The event $\mu(x^*, x_{i(m/r)}] < (1-\delta)/r$ occurs if and only if $|X^* \cap
(x^*,t]| > m/r$, which occurs with probability
\begin{align*}
  \Pr{ |X^* \cap (x^*,t]| > \frac{m}{r} }
= \Pr{ |X^* \cap (x^*,t]| > m\left(1-\frac{(i-1)}{r}\right) \frac{1-\delta}{r(1-\beta)}(1+\eta) }
\end{align*}
where
\begin{align*}
  1 + \eta
      &= \frac{(1-\beta)}{(1-\delta)\left(1-\frac{i-1}{r}\right)} 
      \geq \frac{\left(1-(1+\delta/2)\frac{i-1}{r}\right)}{(1-\delta)\left(1-\frac{i-1}{r}\right)}
      = \frac{1}{1-\delta} \left(1 - \frac{(\delta/2)(i-1)}{r-(i-1)}\right)  \\
      &\geq \frac{1 - \delta/2 }{1-\delta}
      = 1 + \frac{\delta}{2(1-\delta)} \geq 1 + \delta/2 \,.
\end{align*}
Since the expected value satisfies
\[
|X^*|\frac{1-\delta}{r(1-\beta)} \geq \frac{m}{r}(1-\frac{i-1}{r}) \frac{2(1-\delta)}{1 - \delta/2}
\geq \frac{m}{r} (1-\delta/2) \geq \frac{m}{2r}\,,
\]
the Chernoff bound gives
\[
  \Pr{ |X^* \cap (x^*,t]| > \frac{m}{r} }
  \leq \exp{-\frac{\delta^2 |X^*|(1-\delta)}{3 \cdot 4 \cdot r(1-\beta)}}
  \leq e^{-\frac{\delta^2 m}{3 \cdot 4 \cdot 2 r}} \,.
\]
Now let $t \in \ensuremath{\mathbb{R}}$ be the point such that $\mu(x^*,t] = (1+\delta)/r$. The expected value of $|X^*
\cap (x^*,t]|$ is now $|X^*|\frac{1+\delta}{r(1-\beta)}$. The event $\mu(x^*, x_{i(m/r)}] >
(1+\delta)/r$ occurs if and only if $|X^* \cap (x^*,t]| < m/r$, which occurs with probability
\[
  \Pr{ |X^* \cap (x^*,t]| < \frac{m}{r} }
  = \Pr{ |X^* \cap (x^*, t]| < m\left(1-\frac{i-1}{r}\right)\frac{1+\delta}{r(1-\beta)}(1-\eta) }
\]
where
\begin{align*}
  1 - \eta
  &= \frac{1-\beta}{(1+\delta)(1-\tfrac{i-1}{r})}
  \leq \frac{1 - (1+\delta/2)\tfrac{i-1}{r}}{(1+\delta)\left(1-\frac{i-1}{r}\right)}
  = \frac{1}{1+\delta}\left(1 + \frac{(\delta/2)(i-1)}{r-(i-1)}\right) \\
  &\leq \frac{1+\delta/2}{1+\delta}
  = 1 - \frac{\delta/2}{1+\delta}
  \leq 1 - \frac{\delta}{4} \,.
\end{align*}
The expected value satisfies $|X^*| \frac{1+\delta}{r(1-\beta)} > m/r$, so the Chernoff bound gives
\[
  \Pr{ |X^* \cap (x^*,t]| < \frac{m}{r} }
  \leq \exp{-\frac{\delta^2 |X^*|(1+\delta)}{2 \cdot 4^2 \cdot r(1-\beta)}}
  \leq e^{-\frac{\delta^2 m}{2 \cdot 4^2}} \,.
\]
It remains to bound the probability that $(1-\delta/2)\frac{i-1}{r} < \beta <
(1+\delta/2)\frac{i-1}{r}$. Define $t \in \ensuremath{\mathbb{R}}$ such that $\mu(-\infty, t] =
(1+\delta/2)\frac{i-1}{r}$. $\beta = \mu(-\infty,x^*] \geq (1+\delta/2)\frac{i-1}{r}$ if and only if
$x^* > t$, i.e.~$|X \cap (-\infty,t]| < \frac{i-1}{r}$.  The expected value of $|X \cap
(-\infty,t]|$ is $m\frac{(1+\delta/2)(i-1)}{r}$, so for $\eta = \frac{\delta/2}{1+\delta/2} \geq
\delta/3$, the Chernoff bound implies
\begin{align*}
  \Pr{|X \cap (-\infty,t]| < m\frac{i-1}{r}}
  &= \Pr{|X \cap (-\infty,t]| < m\frac{(1+\delta/2)(i-1)}{r}(1-\eta) } \\
  &\leq e^{-\frac{\delta^2 m(1+\delta/2)(i-1)}{18 r}}
  \leq e^{-\frac{\delta^2 m}{18 r}} \,.
\end{align*}
Now define $t \in \ensuremath{\mathbb{R}}$ such that $\mu(-\infty, t] = (1-\delta/2)\frac{i-1}{r}$. $\beta =
\mu(-\infty,x^*] \leq (1-\delta/2)\frac{i-1}{r}$ if and only if $x^* < t$, i.e.~$|X \cap
(-\infty,t]| > \frac{i-1}{r}$. The expected value of $|X \cap (-\infty,t]|$ is
$m\frac{(1-\delta/2)(i-1)}{r}$, so for $\eta = \frac{\delta}{2-\delta} \geq \delta/2$,
\begin{align*}
  \Pr{|X \cap (-\infty,t]| > m\frac{i-1}{r}}
  &= \Pr{|X \cap (-\infty,t]| > m\frac{(1-\delta/2)(i-1)}{r}(1+\eta) } \\
  &\leq e^{-\frac{\delta^2 m(1-\delta/2)(i-1)}{2 \cdot 4 r}}
  \leq e^{-\frac{\delta^2 m}{4^2 r}} \,.
\end{align*}
The conclusion then follows from the union bound over these four events.
\end{proof}

\begin{lemma}
\label{lemma:continuous uniform blocks}
Let $\mu = \mu_1 \times \dotsm \times \mu_d$ be a product distribution over $\ensuremath{\mathbb{R}}^d$ where each
$\mu_i$ is continuous. Let $X$ be a random grid with length $m$ sampled from $\mu$, and let $\mathsf{block}
: \ensuremath{\mathbb{R}}^d \to [r]^d$ be the $r$-block partition induced by $X$. Then
\[
  \Pru{X}{ \|\mathsf{block}(\mu) - \mathsf{unif}([r]^d) \|_\mathsf{TV} > \epsilon }
    \leq 4 rd \cdot e^{-\frac{\epsilon^2 m}{18 r d^2}}
\]
\end{lemma}
\begin{proof}
For a fixed grid $X$ and each $i \in [d]$, write $p_i : [r] \to [0,1]$ be the probability
distribution on $[r]$ with $p_i(z) = \mu_i(B_{i,z})$. Then $\mathsf{block}(\mu) = p_1 \times \dotsm \times
p_d$.

Let $\delta = \frac{4\epsilon}{3d}$.  Suppose that for every $i,j \in [d] \times [r]$ it holds that
$\frac{1+\delta}{r} \leq p_i(j) \geq \frac{1-\delta}{r}$.  Note that $d\delta = \frac{4\epsilon}{3}
\leq \ln(1+2\epsilon) \leq 2\epsilon$. Then for every $v \in [r]^d$,
\begin{align*}
\Pru{u \sim \mu}{\mathsf{block}(u) = v}
&= \prod_{i=1}^d p_i(v_i) \begin{cases}
\leq {(1+\delta)}^d r^{-d}
\leq e^{d\delta} r^{-d} \leq (1+2\epsilon)r^{-d} \\
\geq {(1-\delta)}^d r^{-d}
\geq (1-d\delta) r^{-d} \geq (1-2\epsilon) r^{-d} \,.
\end{cases}
\end{align*}
So
\[
\| \mathsf{block}(\mu) - \mathsf{unif}([r]^d) \|_\mathsf{TV}
= \frac{1}{2} \sum_{v \in [r]^d} | \Pru{u \sim \mu}{\mathsf{block}(u) = v} - r^{-d} |
  \leq \frac{1}{2} \sum_{v \in [r]^d} 2\epsilon r^{-d} = \epsilon \,.
\]
By \cref{lemma:uniform intervals} and the union bound, the probability that there is some $i \in
[d], j \in [r]$ that satisfies $p_i(j) < (1-\delta)/r$ is at most
$4 rd \cdot e^{-\frac{\epsilon^2 m}{18 r d^2}}$.
\end{proof}

\section{Testing Monotonicity}
\label{section:monotonicity}

\subsection{Testing Monotonicity on the Hypergrid}\label{section:warm-up}

A good introduction to downsampling is the following short proof of the main result of Black,
Chakrabarty, \& Seshadhri~\cite{BCS20}. In an earlier work,~\cite{BCS18}, they gave an
$O((d^{5/6}/\epsilon^{4/3})\poly\log(dn))$ tester for the domain $[n]^d$, and in the later work they
showed how to reduce the domain $[n]^d$ to $[r]^d$ for $r = \poly(d/\epsilon)$.

Our monotonicity tester will use as a subroutine the following tester for \emph{diagonal} functions.
For a hypergrid $[n]^d$, a \emph{diagonal} is a subset of points $\{ x \in [n]^d : x = v + \lambda
\vec 1, \lambda \in \ensuremath{\mathbb{Z}} \}$ defined by some $v \in [n]^d$. A function $f : [n]^d \to \{0,1\}$ is a
\emph{diagonal function} if it has at most one 1-valued point in each diagonal. 

\begin{lemma}
\label{lemma:diagonal tester}
There is an $\epsilon$-tester with one-sided error and query complexity
$O\left(\tfrac{1}{\epsilon}\log^2(1/\epsilon)\right)$ for diagonal functions on $[n]^d$.
\end{lemma}
\begin{proof}
\newcommand{\mathrm{diag}}{\mathrm{diag}}
For each $t \in [n]$ let $D_t$ be the set of diagonals with length $t$. For any $x \in [n]^d$ let
$\mathrm{diag}(x)$ be the unique diagonal that contains $x$. For input $f : [n]^d \to \{0,1\}$ and any $x \in
[n]^d$, let $R(x) = \frac{|\{ y \in \mathrm{diag}(x) : f(y) = 1 \}|}{|\mathrm{diag}(x)|}$.

Suppose that $f$ is $\epsilon$-far from diagonal. Then $f$ must have at least $\epsilon n^d$
1-valued points; otherwise we could set each 1-valued point to 0 to obtain the constant 0 function.
Now observe
\begin{align*}
\Exu{x \sim [n]^d}{R(x)} 
&= \Exu{x \sim [n]^d}{ \sum_{t=1}^n \sum_{L \in D_t}
  \ind{\mathrm{diag}(x)=L} \frac{|\{ y \in L : f(y) = 1 \}|}{t}} \\
&= \sum_{t=1}^n \sum_{L \in D_t} \Pru{x \sim [n]^d}{x \in L} \frac{|\{ y \in L : f(y) = 1\}|}{t}
= \sum_{t=1}^n \sum_{L \in D_t} \frac{t}{n^d} \frac{|\{ y \in L : f(y) = 1\}|}{t} \\
&= \frac{1}{n^d} |\{ y \in [n]^d : f(y) = 1 \}| \geq \epsilon \,.
\end{align*}
For each $i$, define $A_i = \left\{ x \in [n]^d : \frac{1}{2^i} < R(x) \leq \frac{1}{2^{i-1}}
\right\}$.  Let $k = \log(4/\epsilon)$. Then
\begin{align*}
  \epsilon
  &\leq \Ex{R(x)}
  \leq \sum_{i=1}^{\infty} \frac{|A_i|}{n^d} \max_{x \in A_i} R(x)
  \leq \sum_{i=1}^{\infty} \frac{|A_i|}{n^d 2^{i-1}}
  \leq \sum_{i=1}^{k} \frac{|A_i|}{n^d 2^{i-1}} + \sum_{i=k+1}^{\infty} \frac{1}{2^{i-1}} \\
  &\leq \sum_{i=1}^{k} \frac{|A_i|}{n^d 2^{i-1}} + \frac{1}{2^{k-1}}
  \leq \sum_{i=1}^{k} \frac{|A_i|}{n^d 2^{i-1}} + \frac{\epsilon}{2} \\
  \implies \frac{\epsilon}{2} &\leq \sum_{i=1}^{k} \frac{|A_i|}{n^d 2^{i-1}} \,.
\end{align*}
Therefore there is some $\ell \in [k]$ such that $|A_\ell| \geq \frac{\epsilon n^d 2^{\ell-1}}{2k}$.

The tester is as follows.  For each $i \in [k]$:
\begin{enumerate}
\item Sample $p = \frac{k}{\epsilon 2^{i-2}}\ln(6)$ points $x_1,
\dotsc, x_p \sim [n]^d$.
\item For each $j \in [p]$, sample $q = 2^{i+2}\ln(12)$ points $y_1, \dotsc, y_q$ from $\mathrm{diag}(x_i)$ and reject
if there are two distinct 1-valued points in the sample.
\end{enumerate}
The query complexity of the tester is
$\sum_{i=1}^k 4^2 \ln(6)\ln(12) \frac{k}{\epsilon 2^i} 2^i = O\left(\frac{1}{\epsilon}
\log^2(1/\epsilon)\right)$.

The tester will clearly accept any diagonal function.  Now suppose that $f$ is $\epsilon$-far from
having this property, and let $\ell \in [k]$ be such that $|A_\ell| \geq \frac{\epsilon n^d
2^{\ell-2}}{k}$. On iteration $i=\ell$, the algorithm samples $p = \frac{k}{\epsilon
2^{\ell-2}}\ln(6)$ points $x_1, \dotsc, x_p$. The probability that $\forall j \in [p], x_j \notin
A_\ell$ is at most
\[
\left(1 - \frac{|A_\ell|}{n^d}\right)^p \leq \left(1 - \frac{\epsilon 2^{\ell-2}}{k}\right)^p
  \leq \exp{-\frac{\epsilon p 2^{\ell-2}}{k}} \leq 1/6 \,.
\]
Now assume that there is some $x_j \in A_\ell$, so that $R(x_j) > 2^{-\ell}$. Let $A,B \subset
\mathrm{diag}(x_j)$ be disjoint subsets that partition the 1-valued points in $\mathrm{diag}(x_i)$ into
equally-sized parts. Then for $y$ sampled uniformly at random from $\mathrm{diag}(x_j)$, $\Pr{y \in A},
\Pr{y \in B} \geq 2^{-(\ell+1)}$. The probability that there are at least 2 distinct 1-valued points
in $y_1, \dotsc, y_q$ sampled by the algorithm is at least the probability that one of the first
$q/2$ samples is in $A$ and one of the last $q/2$ samples is in $B$. This fails to occur with
probability at most $2(1-2^{-(\ell+1)})^{q/2} \leq 2e^{-q2^{-(\ell+2)}} \leq 1/6$. So the total
probability of failure is at most $2/6=1/3$.
\end{proof}

\begin{theorem}\label{thm:monotonicity tester grid}
There is a non-adaptive monotonicity tester on domain $[n]^d$ with one-sided error and query
complexity $\widetilde O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\right)$.
\end{theorem}
\begin{proof}
Set $r = \ceil{4d/\epsilon}$, and assume without loss of generality that $r$
divides $n$.
Partition $[n]$ into $r$ intervals $B_i = \{(i-1)(n/r) + 1, \dotsc, i(n/r)\}$. For each $v \in[r]^d$
write $B_v = B_{v_i} \times \dotsm \times B_{v_d}$. Define $\mathsf{block} : [n]^d \to [r]^d$ where
$\mathsf{block}(x)$ is the unique vector $v \in [r]^d$ such that $x \in B_v$. Define
$\mathsf{block}^{-\downarrow}(v) = \min\{x \in B_v\}$ and $\mathsf{block}^{-\uparrow}(v) = \max\{x \in B_v \}$,
where the minimum and maximum are with respect to the natural ordering on $[n]^d$. For $f : [n]^d
\to \{0,1\}$, write $f^\mathsf{block} : [r]^d \to \{0,1\}, f^\mathsf{block}(v) = f(\mathsf{block}^{-\downarrow}(v))$. We may
simulate queries $v$ to $f^\mathsf{block}$ by returning $f(\mathsf{block}^{-\downarrow}(v))$. We will call $v \in
[r]^d$ a \emph{boundary block} if $f(\mathsf{block}^{-\downarrow}(v)) \neq f(\mathsf{block}^{-\uparrow}(v))$.

The test proceeds as follows: On input $f : [n]^d \to \{0,1\}$ and a block $v \in [r]^d$, define the
following functions:
\begin{align*}
  g : [n]^d \to \{0,1\}, \qquad g(x) &=
      \begin{cases}
        f^\mathsf{block}(\mathsf{block}(x)) &\text{ if } \mathsf{block}(x) \text{ is not a boundary block} \\
        f(x)                &\text{ if } \mathsf{block}(x) \text{ is a boundary block.}
      \end{cases} \\
  b : [r]^d \to \{0,1\}, \qquad b(v) &=
      \begin{cases}
        0 &\text{ if } v \text{ is not a boundary block} \\
        1 &\text{ if } v \text{ is a boundary block.}
      \end{cases} \\
  h : [r]^d \to \{0,1\}, \qquad h(v) &=
      \begin{cases}
        f^\mathsf{block}(v) &\text{ if } v \text{ is not a boundary block} \\
        0           &\text{ if } v \text{ is a boundary block.}
      \end{cases}
\end{align*}
Queries to each of these functions can be simulated by 2 or 3 queries to $f$. The tester performs:
\begin{enumerate}
\item Test whether $g=f$, or whether $\mathsf{dist}(f,g) > \epsilon/4$, using $O(1/\epsilon)$ queries.
\item Test whether $b$ is diagonal, or is $\epsilon/4$-far from diagonal, using Lemma
\ref{lemma:diagonal tester}, with $O\left(\tfrac{1}{\epsilon}\log^2(1/\epsilon)\right)$ queries.
\item Test whether $h$ is monotone or $\epsilon/4$-far from monotone, using the tester of Black,
Chakrabarty, \& Seshadhri with $\widetilde O\left(\frac{d^{5/6}}{\epsilon^{4/3}}\right)$ queries.
\end{enumerate}
\begin{claim}
If $f$ is monotone, the tester passes all 3 tests with probability 1.
\end{claim}
\begin{proof}[Proof of claim]
To see that $g=f$, observe that if $v=\mathsf{block}(x)$ is not a boundary block then
$f(\mathsf{block}^{-\downarrow}(v)) = f(\mathsf{block}^{-\uparrow}(v))$. If $f(x) \neq f^\mathsf{block}(\mathsf{block}(x))$ then
$f(x) \neq f(\mathsf{block}^{-\downarrow}(v))$ and $f(x) \neq f(\mathsf{block}^{-\uparrow}(v))$ while
$\mathsf{block}^{-\downarrow}(v) \preceq x \preceq \mathsf{block}^{-\uparrow}(v)$, and this is a violation of the
monotonicity of $f$. Therefore $f$ will pass the first test with probability 1.

To see that $f$ passes the second test with probability 1, observe that if $f$ had 2 boundary blocks
in some diagonal, then there are boundary blocks $u,v \in [r]^d$ such that $\mathsf{block}^{-\uparrow}(u)
\prec \mathsf{block}^{-\downarrow}(v)$. But then there is $x,y \in [n]^d$ such that $\mathsf{block}(x)=u,
\mathsf{block}(y)=v$ and $f(x) = 1, f(y) = 0$; since $x \preceq \mathsf{block}^{-\uparrow}(u) \prec
\mathsf{block}^{-\downarrow}(v) \preceq y$, this contradicts the monotonicity of $f$. So $f$ has at most 1
boundary block in each diagonal.

To see that $h$ is monotone, it is sufficient to consider the boundary blocks, since all other
values are the same as $f^\mathsf{block}$. Let $v \in [r]^d$ be a boundary block, so there exist $x,y \in
[n]^d$ such that $\mathsf{block}(x)=\mathsf{block}(y)$ and $f(x)=1,f(y)=0$. Suppose $u \prec v$ is not a boundary
block (if it is a boundary block then $h(u)=h(v)=0$). If $h(u)=1$ then
$f(\mathsf{block}^{-\downarrow}(u))=1$, but $\mathsf{block}^{-\downarrow}(u) \prec \mathsf{block}^{-\downarrow}(v) \preceq
y$ while $f(\mathsf{block}^{-\downarrow}(u)) > f(y)$, a contradiction. So it must be that $h(u)=0$ whenever
$u \prec v$. For any block $u \in [r]^d$ such that $v \prec u$, we have $0 = h(v) \leq h(u)$, so
monotonicity holds. Since the tester of Black, Chakrabarty, \& Seshadhri has one-sided error, the
test passes with probability 1.
\end{proof}

\begin{claim}
\label{claim:monotonicity grid claim 2}
If $g$ is $\epsilon/4$-close to $f$, $b$ is $\epsilon/4$-close to diagonal, and $h$ is
$\epsilon/4$-close to monotone, then $f$ is $\epsilon$-close to monotone.
\end{claim}
\begin{proof}[Proof of claim]
Let $h^\mathsf{coarse} : [n]^d \to \{0,1\}$ be the function $h^\mathsf{coarse}(x) = h(\mathsf{block}(x))$. Suppose that $f(x)
\neq h^\mathsf{coarse}(x)$. If $v = \mathsf{block}(x)$ is not a boundary block of $f$ then $h^\mathsf{coarse}(x) = h(v) =
f^\mathsf{block}(v) = g(x)$, so $f(x) \neq g(x)$. If $v$ is a boundary block then $h^\mathsf{coarse}(x) = h(v) = 0$
so $f(x)=1$, and $b(v) = 1$.

Suppose for contradiction that there are more than $\tfrac{\epsilon}{2} r^d$ boundary blocks $v \in
[r]^d$, so there are more than $\tfrac{\epsilon}{2} r^d$ 1-valued points of $b$. Any diagonal
function  has at most $d r^{d-1}$ 1-valued points. Therefore the distance of $b$ to diagonal is at
least
\[
r^{-d}\left(\frac{\epsilon}{2} r^d - d r^{d-1}\right)
= \frac{\epsilon}{2} - \frac{d}{r}
= \frac{\epsilon}{2} - \frac{\epsilon}{4} = \frac{\epsilon}{4} \,,
\]
a contradiction. So $f$ has at most $\tfrac{\epsilon}{2} r^d$ boundary blocks. Now
\begin{align*}
\mathsf{dist}(f,h^\mathsf{coarse})
&= \mathsf{dist}(f,g) + \Pru{x \sim [n]^d}{f(x)=1, \mathsf{block}(x) \text{ is a boundary block}}
\leq \frac{\epsilon}{4} + r^{-d} \cdot \frac{\epsilon r^d}{2} = \frac{3}{4} \epsilon \,.
\end{align*}
Let $p : [r]^d \to \{0,1\}$ be a monotone function minimizing the distance to $h$, and let $p^\mathsf{coarse} :
[n]^d \to \{0,1\}$ be the function $p^\mathsf{coarse}(x) = p(\mathsf{block}(x))$. Then
\[
  \mathsf{dist}(h^\mathsf{coarse}, p^\mathsf{coarse}) = \Pru{x \sim [n]^d}{h(\mathsf{block}(x)) \neq p(\mathsf{block}(x))} = \Pru{v \sim
[r]^d}{ h(v) \neq p(v) } \leq \epsilon / 4 \,.
\]
Finally, the distance of $f$ to the nearest monotone function is at most
\[
  \mathsf{dist}(f,p^\mathsf{coarse}) \leq \mathsf{dist}(f, h^\mathsf{coarse}) + \mathsf{dist}(h^\mathsf{coarse},p^\mathsf{coarse})
  \leq \frac{3}{4}\epsilon + \frac{1}{4} \epsilon = \epsilon \,. \qedhere
\]
\end{proof}
These two claims suffice to establish the theorem.
\end{proof}

\subsection{Monotonicity Testing for Product Distributions}

The previous section used a special case of downsampling, tailored for the uniform distribution over
$[n]^d$.  We will call a product distribution $\mu = \mu_1 \times \dotsm \times \mu_d$ over $\ensuremath{\mathbb{R}}^d$
\emph{continuous} if each of its factors $\mu_i$ are continuous (i.e.~absolutely continuous with
respect to the Lebesgue measure). The proof for discrete distributions is in \cref{section:finite
algorithms}.

\thmmonotonicity*

\begin{proof}
We follow the proof of \cref{thm:monotonicity tester grid}, with some small changes. Let $r =
\ceil{16 d/\epsilon}$. The tester first
samples a grid $X$ with length $m = O\left(\frac{r d^2}{\epsilon^2}\log(rd)\right)$ and constructs
the induced $(r+2)$-block partition, with cells labeled $\{0, \dotsc, r+1\}^d$. We call a block $v
\in \{0, \dotsc, r+1\}^d$ \emph{upper extreme} if there is some $i \in [d]$ such that $v_i = r+1$,
and we call it \emph{lower extreme} if there is some $i \in [d]$ such that $v_i = 0$ but $v$ is not
upper extreme. Call the upper extreme blocks $U$ and the lower extreme blocks $L$. Note that $[r]^d
= \{0, \dotsc, r+1 \}^d \setminus (U \cup L)$.

For each $v \in [r]^d$, we again define $\mathsf{block}^{-\uparrow}(v), \mathsf{block}^{-\downarrow}(v)$ as,
respectively, the supremal and infimal point $x \in \ensuremath{\mathbb{R}}^d$ such that $\mathsf{block}(x) = v$. The algorithm
will ignore the extreme blocks $U \cup L$, which do not have a supremal or an infimal point.
Therefore it is not defined whether these blocks are boundary blocks.

By \cref{lemma:continuous uniform blocks}, with probability at least $5/6$, we will have $\|
\mathsf{block}(\mu) - \mathsf{unif}(\{0,\dotsc,r+1\}) \|_\mathsf{TV} \leq \epsilon/8$.
We define $b,h$ as before, with domain $[r]^d$. Define $g$ similarly but with domain $\ensuremath{\mathbb{R}}^d$ and
values
\[
  g(x) = \begin{cases}
    1    &\text{ if } \mathsf{block}(x) \in U \\
    0    &\text{ if } \mathsf{block}(x) \in L \\
    f(x) &\text{ if } \mathsf{block}(x) \in [n]^d \text{ is a boundary block} \\
    f^\mathsf{block}(\mathsf{block}(x)) &\text{ otherwise.}
  \end{cases}
\]
If $f$ is monotone, it may now be the case $f \neq g$, but we will have $f(x) = g(x)$ for all $x$
with $\mathsf{block}(x) \in [r]^d$, where the algorithm will make its queries. The algorithm will test
whether $f(x)=g(x)$ on all $x$ with $\mathsf{block}(x) \in [r]^d$, or $\epsilon/8$-far from this property,
which can be again done with $O(1/\epsilon)$ samples. Note that if $f$ is $\epsilon/8$-close to
having this property, then
\begin{align*}
  \mathsf{dist}_\mu(f,g)
  &\leq \Pru{x \sim \mu}{\mathsf{block}(x) \notin [n]^d} + \epsilon/8 \\
  &\leq \frac{d(r+2)^{d-1}}{(r+2)^d} + \epsilon/8 + \| \mathsf{block}(\mu) - \mathsf{unif}([r]^d \cup U \cup L)
\|_\mathsf{TV} \\
  &\leq  \frac{\epsilon}{16} + \frac{\epsilon}{8} + \frac{\epsilon}{4} \leq \frac{\epsilon}{2} \,.
\end{align*}
The algorithm then procedes as before, with error parameter $\epsilon/2$. To test whether $g=f$, the
algorithm samples from $\mu$ and throws away any sample $x \in \ensuremath{\mathbb{R}}^d$ with $\mathsf{block}(x) \notin [r]^d$.
It then tests $b$ and $h$ using the uniform distribution on $[r]^d$. It suffices to prove the
following claim, which replaces \cref{claim:monotonicity grid claim 2}.

\begin{claim}
If $g$ is $\epsilon/2$-close to $f$, $b$ is $\epsilon/16$-close to diagonal, and $h$ is
$\epsilon/8$-close to monotone, then $f$ is $\epsilon$-close to monotone.
\end{claim}
\begin{proof}[Proof of claim]
Let $p : [r]^d \to \{0,1\}$ be a monotone function minimizing the distance to $h$. Then $p(v) \neq h(v)$
on at most $\frac{\epsilon r^d}{8}$ blocks $v \in [r]^d$. Define $p^\mathsf{coarse} : \ensuremath{\mathbb{R}}^d \to \{0,1\}$ as
$p^\mathsf{coarse}(x) = p(\mathsf{block}(x))$ when $\mathsf{block}(x) \in [r]^d$, and $p^\mathsf{coarse}(x) = g(x)$ when $\mathsf{block}(x)
\in U \cup L$. Note that $p^\mathsf{coarse}$ is monotone.

By the triangle inequality,
\[
  \mathsf{dist}_\mu(f,p^\mathsf{coarse}) \leq \mathsf{dist}_\mu(f, g) + \mathsf{dist}_\mu(g, p^\mathsf{coarse}) \,.
\]
From above, we know $\mathsf{dist}_\mu(f,g) \leq \epsilon/2$. To bound the second term, observe that since
$b$ is $\epsilon/16$-close to diagonal, there are at most
\[
\frac{\epsilon}{16} r^d + dr^{d-1} \leq \frac{\epsilon}{16} r^d + \frac{d}{r} r^d \leq
\frac{\epsilon}{16} r^d + \frac{\epsilon}{16} r^d = \frac{\epsilon}{8} r^d
\]
boundary blocks. Then observe that if $g(x) \neq p^\mathsf{coarse}(x)$ then $\mathsf{block}(x) \in [r]^d$ and either
$\mathsf{block}(x)$ is a boundary block, or $g(x) = f^\mathsf{block}(\mathsf{block}(x)) = h(\mathsf{block}(x))$ and $h(\mathsf{block}(x))
\neq p(\mathsf{block}(x))$. Then
\begin{align*}
  \mathsf{dist}_\mu(g, p^\mathsf{coarse})
  &\leq \left(\frac{1}{(r+2)^d} \sum_{v \in [r]^d}
    \ind{ v \text{ is a boundary block, or } h(v) \neq p(v) } \right) \\
  &\qquad + \|\mathsf{block}(\mu) - \mathsf{unif}(\{0,\dotsc,r+1\}^d) \|_\mathsf{TV} \\
  &\leq \frac{\epsilon r^d}{8 r^d} + \frac{\epsilon r^d}{8 r^d} + \frac{\epsilon}{4}
  \leq \frac{\epsilon}{2} \,. \qedhere
\end{align*}
\end{proof}
\end{proof}


\section{Learning and Testing Functions of Convex Sets}\label{section:convex sets}

In this section we present our learning and testing results for functions of $k$ convex sets: an
agnostic learning algorithm, a sample-based distance approximator, and a sample-based one-sided
tester. All our algorithms will follow from more general results that actually hold for any class
$\ensuremath{\mathcal{H}}$ with bounded $r$-block boundary size; this shows that bounded block-boundary size is
sufficient to guarantee learnability in product distributions.

Let $\ensuremath{\mathcal{C}}$ be the set of functions $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ such that $f^{-1}(1)$
is convex. Let $\ensuremath{\mathcal{B}}_k$ be the set of all Boolean functions $h : \{\pm 1\}^k \to \{\pm 1\}$.
\begin{definition}[Function Composition]
For a set $\ensuremath{\mathcal{H}}$ of functions $h : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$,
we will define the composition $\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}}$ as the set of functions of the form
$f(x) = g(h_1(x), \dotsc, h_k(x))$ where $g \in \ensuremath{\mathcal{B}}_k$ and each $h_i$ belongs to $\ensuremath{\mathcal{H}}$.
\end{definition}

\begin{proposition}\label{prop:resolution of composed functions}
Let $\ensuremath{\mathcal{H}}$ be any class of functions $\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ and fix any $r$. Then
$\mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}},r) \leq k \cdot \mathsf{bbs}(\ensuremath{\mathcal{H}},r)$.
\end{proposition}
\begin{proof}
If $f(\cdot) = g(h_1(\cdot),\dotsc,h_k(\cdot))$ is not constant on
$\mathsf{block}^{-1}(v)$ then one of the $h_i$ is not constant on that block. Therefore
$\mathsf{bbs}(f,r) \leq \sum_{i=1}^k \mathsf{bbs}(h_i,r) \leq k \cdot \mathsf{bbs}(\ensuremath{\mathcal{H}},r)$.
\end{proof}

\begin{lemma}
For any $r$, $\mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{C}},r) \leq 2dkr^{d-1}$.
\end{lemma}
\begin{proof}
We prove $\mathsf{bbs}(\ensuremath{\mathcal{C}},r) \leq 2dr^{d-1}$ by induction on $d$; the result will hold
by Proposition~\ref{prop:resolution of composed functions}. Let $\mathsf{bbs}(\ensuremath{\mathcal{C}},r,d)$
be the $r$-block boundary size in dimension $d$.  Recall that block $v \in
[r]^d$ is the set $B_v = B_{1,v_1} \times \dotsm \times B_{d,v_d}$ where
$B_{i,j} = (a_{i,j-1},a_{i,j}]$ for some $a_{i,j-1} < a_{i,j}$. Let $f \in \ensuremath{\mathcal{C}}$.

For $d=1$, if there are 3 intervals $B_{1,i_1},B_{1,i_2},B_{1,i_3}$, $i_1 < i_2
< i_3$, on which $f$ is not constant, then within each interval the function
takes both values $\{\pm 1\}$. Thus, there are points $a \in B_{1,i_1}, b \in
B_{1,i_2}, c \in B_{1,i_3}$ such that $f(a)=1,f(b)=-1,f(c)=1$, which is a
contradiction.

For each block $B_v$, let $A_v = \{a_{1,v_1}\} \times B_{2,v_2} \times \dotsc
\times B_{d,v_d}$ be the ``upper face''.  For $d > 1$, let $P \subseteq [r]^d$
be the set of non-constant blocks $B_v$ such that $f$ is constant on the upper
face and let $Q$ be the set of non-constant blocks that are non-constant on the
upper face, so that $\mathsf{bbs}(f,r,d) = |P|+|Q|$. We argue that $|P| \leq 2r^{d-1}$:
for a vector $w \in [r]^{d-1}$ define the line $L_w := \{ v \in [r]^d \;|\;
\forall i > 1, v_i=w_i\}$. If $|P \cap L_w| \geq 3$ then there are $t,u,v \in
L_w$ with $t < u < v$ such that $f$ is constant on $A_t,A_u,A_v$ but
non-constant on $B_t,B_u,B_v$. Let $x,y,z$ be points in $B_t,B_u,B_v$
respectively such that $f(x)=f(y)=f(z)=1$. If $f$ is constant $-1$ on $A_t$ or
$A_u$ then there is a contradiction since the lines through $(x,y)$ and $(y,z)$
pass through $A_t,A_u$; so $f$ is constant 1 on $A_t,A_u$. But then there is a
point $q \in A_u$ with $f(q)=-1$, which is a contradiction since it is within the
convex hull of $A_t,A_u$. So $|L_w \cap P| < 3$; since there are at most
$r^{d-1}$ lines $L_w$, $|P| \leq 2r^{d-1}$.

To bound $|Q|$, observe that for each block $v \in Q, f$ is non-constant on the
plane $\{a_{1,v_1}\} \times \ensuremath{\mathbb{R}}^{d-1}$, there are $(r-1)$ such planes, $f$ is
convex on each, and the $r$-block partition induces an $r$-block partition on
the plane where $f$ is non-constant on the corresponding block. Then, by
induction $|Q| \leq (r-1) \cdot \mathsf{bbs}(\ensuremath{\mathcal{C}},r,d-1) \leq 2(d-1)(r-1)r^{d-2}$. So
\[
  \mathsf{bbs}(\ensuremath{\mathcal{C}},r,d) \leq 2\left[ (d-1)(r-1)r^{d-2} + r^{d-1} \right] < 2dr^{d-1}
\,.\qedhere
\]
\end{proof}

The above two lemmas combine to show that $r^{-d} \cdot \mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{C}}, r)
\leq r^{-d}(2dkr^{d-1}) = 2dk/r \leq \epsilon$ when $r = \ceil{2dk/\epsilon}$.

\subsection{Sample-based One-sided Tester}
First, we prove a one-sided sample-based tester for convex sets.

\thmconvextester*

\begin{proof}
We prove the result for continuous distributions. The proof for finite distributions is in
\cref{thm:finite algorithms}.

On input distribution $\mu$ and function $f$, let $r = \ceil{6d/\epsilon}$ so that $r^{-d}\cdot
\mathsf{bbs}(\ensuremath{\mathcal{C}},r) \leq \epsilon/3$.
\begin{enumerate}
\item Sample a grid $X$ of size $m = O\left(\frac{rd^2}{\epsilon^2}\log(rd/\epsilon)\right)$ large
enough that Lemma~\ref{lemma:continuous uniform blocks} guarantees
$\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} < \epsilon/9$ with probability $5/6$.
\item Take $q = O\left(\frac{r^d}{\epsilon}\right)$ samples $Q$ and accept if there exists $h \in
\ensuremath{\mathcal{C}}$ such that $f(x) = h^\mathsf{coarse}(x)$ on all $x \in Q$ that are not in a boundary block of $h$.
\end{enumerate}
This tester is one-sided since for any $h \in \ensuremath{\mathcal{C}}$, $h(x)=h^\mathsf{coarse}(x)$ for all $x \in Q$ that are
not in a boundary block, regardless of whether the $r$-block
decomposition induced by $X$ satisfies $\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} \leq \epsilon/3$. Now
suppose that $\mathsf{dist}_\mu(f,\ensuremath{\mathcal{C}}) > \epsilon$, and suppose that $\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} \leq
\epsilon$. For $h \in \ensuremath{\mathcal{C}}$, let $B_h \subseteq [r]^d$ be the set of non-constant blocks. If $\exists
h \in \ensuremath{\mathcal{C}}$ such that $\Pru{x \sim \mu}{h^\mathsf{coarse}(x) \neq f(x) \wedge \mathsf{block}(x) \notin B_h} <
\epsilon/9$, then
\begin{align*}
  \mathsf{dist}_\mu(f,h^\mathsf{coarse})
    &\leq \Pru{x \sim \mu}{\mathsf{block}(x) \in B_h}
      + \Pru{x \sim \mu}{h^\mathsf{coarse}(x) \neq f(x) \wedge \mathsf{block}(x) \notin B_h} \\
    &\leq r^{-d}\cdot\mathsf{bbs}(\ensuremath{\mathcal{C}},r) + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} + \frac{\epsilon}{9} \\
    &\leq \left(\frac{1}{3}+\frac{2}{9}\right)\epsilon = \frac{5}{9} \cdot \epsilon \,.
\end{align*}
Therefore
\begin{align*}
  \mathsf{dist}_\mu(f,h)
    &\leq \mathsf{dist}_\mu(f,h^\mathsf{coarse}) + \mathsf{dist}_\mu(h^\mathsf{coarse},h) \\
    &\leq \mathsf{dist}_\mu(f,h^\mathsf{coarse}) + r^{-d} \cdot \mathsf{bbs}(\ensuremath{\mathcal{C}},r) + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} \\
    &\leq \frac{5}{9}\epsilon + \frac 1 3 \cdot \epsilon + \frac 1 9 \epsilon = \epsilon \,,
\end{align*}
a contradiction. So it must be that for every $h \in \ensuremath{\mathcal{C}}, \Pr{f(x) \neq h^\mathsf{coarse}(x) \wedge x \notin
B_h} \geq \epsilon/9$. There are at most ${r^d \choose \tfrac{\epsilon}{3} r^d} \leq
(3e/\epsilon)^{\epsilon r^d / 3}$ choices of boundary set $B$. Because the 1-valued blocks must be
the convex hull of the boundary points, for each boundary set $B$ there are at most 2 choices of
function $h^\mathsf{coarse}$ with boundary $B$ (with a second choice occurring when the complement of
$h^\mathsf{coarse}$ is also a convex set with the same boundary). Therefore, by the union bound, the
probability that $f$ is accepted is at most
\[
    \left(\frac{3e}{\epsilon}\right)^{\frac{\epsilon}{3}r^d} \cdot {\left(1-\frac\epsilon
9\right)}^q \leq e^{\epsilon\left(\frac{r^d}{3} - \frac{q}{9}\right)} \,,
\]
which is at most $1/6$ for sufficiently large $q = O\left(r^d + \frac{1}{\epsilon}\right)$.
\end{proof}

\subsection{Sample-based Distance Approximator}
Our sample-based distance approximator follows from the following general result.
\begin{lemma}
For any set $\ensuremath{\mathcal{H}}$ of functions $\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$, $\epsilon > 0$, and $r$ satisfying $r^{-d} \cdot
\mathsf{bbs}(\ensuremath{\mathcal{H}},r) \leq \epsilon/3$, there is a sample-based distribution-free algorithm for product
distributions that approximates distance to $\ensuremath{\mathcal{H}}$ up to additive error $\epsilon$ using
$O\left(\frac{r^d}{\epsilon^2} \right)$ samples.
\end{lemma}
\begin{proof}
On input distribution $\mu$ and function $f : \ensuremath{\mathbb{R}}^d \to \{0,1\}$, let $r = 3dk/\epsilon$, then:
\begin{enumerate}
\item Sample a grid $X$ of size $m = O(\frac{rd^2}{\epsilon^2}\log\frac{rd}{\epsilon})$ large enough that
Lemma~\ref{lemma:continuous uniform blocks} guarantees $\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} <
\epsilon/3$ with probability $5/6$.
\item Let $\ensuremath{\mathcal{H}}^\mathsf{coarse}$ be the set of all functions $h^\mathsf{coarse}$ where $h \in \ensuremath{\mathcal{H}}$; note that
$|\ensuremath{\mathcal{H}}^\mathsf{coarse}| \leq 2^{r^d}$.
\item Draw $q = O\left(\frac{r^d}{\epsilon^2}\right)$ samples $Q$ and output the distance on $Q$ to
the nearest function in $\ensuremath{\mathcal{H}}^\mathsf{coarse}$.
\end{enumerate}
We argue that with probability at least $5/6$, $\ensuremath{\mathcal{H}}^\mathsf{coarse}$ is an $\tfrac{5}{6}\epsilon$-cover of
$\ensuremath{\mathcal{H}}$.  With probability at least $5/6$, $\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} < \epsilon/6$. Then by
Proposition~\ref{prop:distance to coarse}, for any $h \in \ensuremath{\mathcal{H}}$,
\[
  \Pru{x \sim \mu}{h(x) \neq h^\mathsf{coarse}(x)} \leq r^{-d} \cdot \mathsf{bbs}(f,r)
    + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV}
  \leq \left(\frac{2}{3} + \frac{1}{6}\right)\epsilon
  = \frac{5}{6}\epsilon \,,
\]
so $\ensuremath{\mathcal{H}}^\mathsf{coarse}$ is a $\tfrac 5 6 \epsilon$-cover; assume this event occurs.

Write $\mathsf{dist}_Q(f,g) := \frac{1}{q} \sum_{x \in Q}\ind{f(x) \neq g(x)}$.
By the union bound and Hoeffding's inequality, with $q$ samples we fail to get an estimate of
$\mathsf{dist}_\mu(f,\ensuremath{\mathcal{H}}^\mathsf{coarse})$ up to additive error $\frac 1 6 \epsilon$ with probability at most
\[
  |\ensuremath{\mathcal{H}}^\mathsf{coarse}| \cdot \max_{h^\mathsf{coarse} \in \ensuremath{\mathcal{H}}^\mathsf{coarse}} \Pru{Q}{ \left|\mathsf{dist}_\mu(f,h^\mathsf{coarse}) -
\mathsf{dist}_Q(f,h^\mathsf{coarse})\right| > \frac{1}{6}\epsilon}
    \leq |\ensuremath{\mathcal{H}}^\mathsf{coarse}| \exp{-2\frac{q \epsilon^2}{36}} < \frac{1}{6}
\]
for appropriately chosen $q = O\left(\frac{1}{\epsilon^2} \log(|\ensuremath{\mathcal{H}}^\mathsf{coarse}|)\right) =
O\left(\frac{r^d}{\epsilon^2}\right)$.  Assume this event occurs. We want to show that
$|\mathsf{dist}_Q(f,\ensuremath{\mathcal{H}}^\mathsf{coarse})-\mathsf{dist}_\mu(f,\ensuremath{\mathcal{H}})| \leq \epsilon$.  Let $h \in \ensuremath{\mathcal{H}}$ minimize
$\mathsf{dist}_\mu(f,h)$ so $\mathsf{dist}_\mu(f,h)=\mathsf{dist}_\mu(f,\ensuremath{\mathcal{H}})$. Then
\begin{align*}
\mathsf{dist}_Q(f,\ensuremath{\mathcal{H}}^\mathsf{coarse})
  &\leq \mathsf{dist}_Q(f,h^\mathsf{coarse}) 
  \leq \mathsf{dist}_\mu(f,h^\mathsf{coarse}) + \frac{\epsilon}{6} \\
  &\leq \mathsf{dist}_\mu(f,h) + \mathsf{dist}_\mu(h,h^\mathsf{coarse}) + \frac{\epsilon}{6} 
  \leq \mathsf{dist}_\mu(f,\ensuremath{\mathcal{H}}) + \epsilon \,.
\end{align*}
Now let $g \in \ensuremath{\mathcal{H}}$ minimize $\mathsf{dist}_Q(f,g^\mathsf{coarse})$ so
$\mathsf{dist}_Q(f,g^\mathsf{coarse})=\mathsf{dist}_Q(f,\ensuremath{\mathcal{H}}^\mathsf{coarse})$. Then
\begin{align*}
  \mathsf{dist}_Q(f,\ensuremath{\mathcal{H}}^\mathsf{coarse})
    &= \mathsf{dist}_Q(f,g^\mathsf{coarse}) \geq \mathsf{dist}_\mu(f,g^\mathsf{coarse}) - \frac{\epsilon}{6}
    \geq \mathsf{dist}_\mu(f,h^\mathsf{coarse}) - \frac{\epsilon}{6} \\
    &\geq \mathsf{dist}_\mu(f,h) - \mathsf{dist}_\mu(h,h^\mathsf{coarse}) - \frac{\epsilon}{6}
    \geq \mathsf{dist}_\mu(f,h) - \epsilon \,,
\end{align*}
which concludes the proof.
\end{proof}

Applying the bound on $\mathsf{bbs}(\ensuremath{\mathcal{B}}_k,r)$ we conclude:
\thmconvexdistance*

\subsection{Agnostic Learning}
We begin our learning results with an agnostic learning algorithm for functions of $k$ convex sets:
the class $\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{C}}$.
For a distribution $\ensuremath{\mathcal{D}}$ over $\ensuremath{\mathbb{R}}^d \times \{\pm 1\}$ and an $r$-block partition
$\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$, define the distribution $\ensuremath{\mathcal{D}}^\mathsf{block}$ over $[r]^d \times \{\pm 1\}$
as the distribution of $(\mathsf{block}(x),b)$ when $(x,b) \sim \ensuremath{\mathcal{D}}$.
\begin{lemma}\label{lemma:brute force}
Let $\ensuremath{\mathcal{H}}$ be any set of functions $\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$, let $\epsilon > 0$,
and suppose $r$ satisfies ${r^{-d} \cdot \mathsf{bbs}(\ensuremath{\mathcal{H}},r) \leq \epsilon/3}$. Then
there is an distribution-free agnostic learning algorithm for continuous product distributions
that learns $\ensuremath{\mathcal{H}}$ in $O\left(\frac{r^d+rd^2\log(rd/\epsilon)}{\epsilon^2}\right)$ samples
and time.
\end{lemma}
\begin{proof}
On input distribution $\ensuremath{\mathcal{D}}$:
\begin{enumerate}
\item Sample a grid $X$ of size $m =
O(\frac{rd^2}{\epsilon^2}\log(rd/\epsilon))$ large enough that Lemma~\ref{lemma:continuous uniform blocks} guarantees
$\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} < \epsilon/3$ with probability $5/6$,
where $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ is the induced $r$-block partition.
\item Agnostically learn a function $g : [r]^d \to \{\pm 1\}$ with error $\epsilon/3$
	and success probability $5/6$ using $O(r^d/\epsilon^2)$ samples
	from $\ensuremath{\mathcal{D}}^\mathsf{block}$. Output the function $g \circ \mathsf{block}$.
\end{enumerate}
The second step is accomplished via standard learning results
(\cite{SB14} Theorem 6.8): the number of samples required for agnostic learning is
bounded by $O(1/\epsilon^2)$ multiplied by the logarithm of the number of functions in the class,
and the number of functions $[r]^d \to
\{\pm 1\}$ is $2^{r^d}$. Assume that both steps succeed, which occurs
with probability at least $2/3$. Let $f \in \ensuremath{\mathcal{H}}$ minimize $\Pru{(x,b)
\sim \ensuremath{\mathcal{D}}}{f(x) \neq b}$.  By Proposition~\ref{prop:distance to coarse},
 \[
\Pru{x \sim \mu}{f(x) \neq f^\mathsf{coarse}}
  \leq r^{-d} \cdot \mathsf{bbs}(f,r) + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV}
  < 2\epsilon/3 \,.
\]
Then
\begin{align*}
	\Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{g(\mathsf{block}(x)) \neq b}
	&= \Pru{(v,b) \sim \ensuremath{\mathcal{D}}^\mathsf{block}}{g(v) \neq b}
	\leq \Pru{(v,b) \sim \ensuremath{\mathcal{D}}^\mathsf{block}}{f^\mathsf{block}(v) \neq b} + \epsilon/3 \\
	&= \Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{f^\mathsf{coarse}(x) \neq b} + \epsilon/3
	< \Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{f(x) \neq b} + \epsilon \,. \qedhere
\end{align*}
\end{proof}

Lemma~\ref{lemma:brute force} then gives the following result
for continuous product distributions, with the result for finite distributions
following from Theorem~\ref{thm:finite algorithms}.

\thmlearningconvexsets*

\section{Learning Functions of Halfspaces}\label{section:halfspaces}
A halfspace, or linear threshold function, is any function $h : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ such that for some
$w \in \ensuremath{\mathbb{R}}^d, t \in \ensuremath{\mathbb{R}}, h(x) = \sign(\inn{w,x}-t)$, where $\sign(z) = 1$ if $z \geq 0$ and $-1$
otherwise. Let $\ensuremath{\mathcal{H}}$ be the set of halfspaces. Recall that downsampling reduces learning $\ensuremath{\mathcal{H}}$ in
$\ensuremath{\mathbb{R}}^d$ to learning $\ensuremath{\mathcal{H}}^\mathsf{block}$ over $[r]^d$, and $\ensuremath{\mathcal{H}}^\mathsf{block}$ is \emph{not} the set of halfspaces
over $[r]^d$. Fortunately, agnostically learning a halfspaces $h$ is commonly done by giving a bound
on the degree of a polynomial $p$ that approximates $h$~\cite{KOS04,KOS08,KKMS08}, and we will
show that a similar idea also suffices for learning $\ensuremath{\mathcal{H}}^\mathsf{block}$.  We first present a general
algorithm based on ``polynomial regression''\!\!, and then introduce the Fourier analysis necessary
to apply the general learning algorithm to halfspaces, polynomial threshold functions, and
$k$-alternating functions.

\subsection{A General Learning Algorithm}
The learning algorithm in this section essentially replaces step 2 of the brute
force algorithm (Lemma~\ref{lemma:brute force}) with the ``polynomial regression''
algorithm of Kalai \emph{et al.}~\cite{KKMS08}. Our general algorithm is
inspired by an algorithm of Canonne \emph{et al.}~\cite{CGG+19} for tolerantly
testing $k$-alternating functions over the uniform distribution on $[n]^d$; we
state the regression algorithm as it appears in~\cite{CGG+19}. For a set $\ensuremath{\mathcal{F}}$
of functions, $\mathsf{span}(\ensuremath{\mathcal{F}})$ is the set of all linear combinations of
functions in $\ensuremath{\mathcal{F}}$:

\begin{theorem}[\cite{KKMS08, CGG+19}]\label{thm:polynomial regression}
Let $\mu$ be a distribution over $\ensuremath{\mathcal{X}}$,
let $\ensuremath{\mathcal{H}}$ be a class of functions $\ensuremath{\mathcal{X}} \to \{\pm 1\}$ and $\ensuremath{\mathcal{F}}$ a collection of
functions $\ensuremath{\mathcal{X}} \to \ensuremath{\mathbb{R}}$ such that for every $h \in \ensuremath{\mathcal{H}}$, $\exists f \in
\mathsf{span}(\ensuremath{\mathcal{F}})$ where $\Exu{x \sim \mu}{{(h(x)-f(x))}^2} \leq \epsilon^2$.
Then there is an algorithm that, for any distribution $\ensuremath{\mathcal{D}}$ over $\ensuremath{\mathcal{X}} \times
\{\pm 1\}$ with marginal $\mu$ over $\ensuremath{\mathcal{X}}$, outputs a function $g : \ensuremath{\mathcal{X}} \to \{\pm 1\}$
such that $\Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{g(x)\neq b} \leq \inf_{h \in \ensuremath{\mathcal{H}}} \Pru{(x,b)
\sim \ensuremath{\mathcal{D}}}{g(x) \neq b} + \epsilon$, with probability at least $11/12$, using
at most $\poly(|\ensuremath{\mathcal{F}}|, 1 /\epsilon)$ samples and time.
\end{theorem}

Our general learning algorithm will apply to any hypothesis class that has
small $r$-block boundary size, and for which there is a set of functions $\ensuremath{\mathcal{F}}$
that approximately span the class $\ensuremath{\mathcal{H}}^\mathsf{block}$. This algorithm is improved
to work for finite (rather than only continuous) product distributions in
Lemma~\ref{lemma:finite general algorithm}.
\begin{lemma}\label{lemma:general algorithm}
Let $\epsilon > 0$ and let $\ensuremath{\mathcal{H}}$ be a set of measurable functions $f : \ensuremath{\mathbb{R}}^d \to
\{\pm 1\}$ that satisfy:
\begin{enumerate}
\item There is some $r = r(d,\epsilon)$ such that $\mathsf{bbs}(\ensuremath{\mathcal{H}},r) \leq \frac{\epsilon}{3} \cdot r^d$;
\item There is a set $\ensuremath{\mathcal{F}}$ of functions $[r]^d \to \ensuremath{\mathbb{R}}$ satisfying:
$\forall f \in \ensuremath{\mathcal{H}}, \exists g \in \mathsf{span}(\ensuremath{\mathcal{F}})$ such that for $v \sim
[r]^d, \Ex{(f^\mathsf{block}(v)-g(v))^2} \leq \epsilon^2/4$.
\end{enumerate}
Let $n = \poly(|\ensuremath{\mathcal{F}}|,1/\epsilon)$ be the sample complexity of the algorithm in
Theorem~\ref{thm:polynomial regression}, with error parameter $\epsilon/2$.  Then there is an
agnostic learning algorithm for $\ensuremath{\mathcal{H}}$ on continuous product distributions over $\ensuremath{\mathbb{R}}^d$, that uses
$O(\max(n^2,1/\epsilon^2) \cdot rd^2\log(dr))$ samples and runs in time polynomial in the sample
size.
\end{lemma}
\begin{proof}
We will assume $n > 1/\epsilon$.  Let $\mu$ be the marginal of $\ensuremath{\mathcal{D}}$ on $\ensuremath{\mathbb{R}}^d$.
For an $r$-block partition, let $\ensuremath{\mathcal{D}}^\mathsf{block}$ be the distribution of
$(\mathsf{block}(x),b)$ when $(x,b) \sim \ensuremath{\mathcal{D}}$. We may simulate samples from $\ensuremath{\mathcal{D}}^\mathsf{block}$
by sampling $(x,b)$ from $\ensuremath{\mathcal{D}}$ and constructing $(\mathsf{block}(x),b)$.  The algorithm
is as follows:
\begin{enumerate}
\item Sample a grid $X$ of length $m = O(rd^2n^2\log(rd))$ large enough that
	Lemma~\ref{lemma:continuous uniform blocks} guarantees
	$\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} < 1/12n$ with
	probability $5/6$.
Construct $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ induced by $X$. We may construct the
$\mathsf{block}$ function in time $O(dm\log m)$ by sorting, and once constructed it
takes time $O(\log r)$ to compute.
\item Run the algorithm of Theorem~\ref{thm:polynomial regression} on a sample of $n$ points from
$\ensuremath{\mathcal{D}}^\mathsf{block}$ to learn the class $\ensuremath{\mathcal{H}}^\mathsf{block}$; that algorithm returns a function $g : [r]^d \to
\{\pm 1\}$.  Output $g \circ \mathsf{block}$.\label{item:general algorithm learning}
\end{enumerate}
Assume that step 1 succeeds, which occurs with probability at least $5/6$.  By
condition 2, the algorithm in step 2 is guaranteed to work on samples
$(v,b) \in [r]^d \times \{\pm 1\}$ where the marginal of $v$ is $\mathsf{unif}([r]^d)$; let
$\ensuremath{\mathcal{D}}^\mathsf{unif}$ be the distribution of $(v,b)$ when $v \sim \mathsf{unif}([r]^d)$ and $b$
is obtained by sampling $(x,b) \sim (\ensuremath{\mathcal{D}} \mid x \in \mathsf{block}^{-1}(v))$. The algorithm
of step~\ref{item:general algorithm learning} will succeed on $\ensuremath{\mathcal{D}}^\mathsf{unif}$; we
argue that it will also succeed on the actual input $\ensuremath{\mathcal{D}}^\mathsf{block}$ since
these distributions are close. Observe that for samples $(v,b) \sim
\ensuremath{\mathcal{D}}^\mathsf{unif}$ and $(\mathsf{block}(x),b') \sim \ensuremath{\mathcal{D}}^\mathsf{block}$, if $v=\mathsf{block}(x)$ then
$b,b'$ each have the distribution of $b'$ in $(x,b') \sim (\ensuremath{\mathcal{D}} \mid
\mathsf{block}(x)=v)$. Therefore
\begin{align*}
  \|\ensuremath{\mathcal{D}}^\mathsf{unif} - \ensuremath{\mathcal{D}}^\mathsf{block}\|_\mathsf{TV}
  &= \|(v,b) - (\mathsf{block}(x),b')\|_\mathsf{TV}
  = \|v - \mathsf{block}(x)\|_\mathsf{TV} \\
  &= \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} 
  < \frac{1}{12n} \,.
\end{align*}
It is a standard fact that for product distributions $P^n,Q^n,
\|P^n-Q^n\|_\mathsf{TV} \leq n \cdot \|P-Q\|_\mathsf{TV}$; using this fact,
\[
\|(\ensuremath{\mathcal{D}}^\mathsf{unif})^n-(\ensuremath{\mathcal{D}}^\mathsf{block})^n\|_\mathsf{TV}
\leq n \cdot \|\ensuremath{\mathcal{D}}^\mathsf{unif} - \ensuremath{\mathcal{D}}^\mathsf{block}\|_\mathsf{TV}
< \frac{1}{12} \,.
\]
We will argue that step~\ref{item:general algorithm learning} succeeds with probability $5/6$;
i.e.~that with probability $5/6$,
\[
  \Pru{(v,b) \sim \ensuremath{\mathcal{D}}^\mathsf{block}}{g(v) \neq b} < \inf_{h \in \ensuremath{\mathcal{H}}} \Pru{(v,b) \sim
\ensuremath{\mathcal{D}}^\mathsf{block}}{h^\mathsf{block}(v) \neq b} + \epsilon/2 \,.
\]
Let $E(S)$ be the event that success occurs given sample $S \in ([r]^d \times
\{\pm 1\})^n$. The algorithm samples $S \sim (\ensuremath{\mathcal{D}}^\mathsf{block})^n$ but the success guarantee of step~\ref{item:general algorithm learning} is for $(\ensuremath{\mathcal{D}}^\mathsf{unif})^n$; this step will still succeed with
probability $5/6$:
\begin{align*}
  \Pru{S \sim (\ensuremath{\mathcal{D}}^\mathsf{unif})^n}{E(S)}
  &\geq \Pru{S \sim (\ensuremath{\mathcal{D}}^\mathsf{block})^n}{E(S)} - \|(\ensuremath{\mathcal{D}}^\mathsf{unif})^n - (\ensuremath{\mathcal{D}}^\mathsf{block})^n\|_\mathsf{TV} \\
  &> \Pru{S \sim \ensuremath{\mathcal{D}}^n}{E(S)} - \frac{1}{12} \geq \frac{11}{12}- \frac{1}{12} = \frac{5}{6}\,.
\end{align*}
Assume that each step succeeds, which occurs with probability at least $1-2\cdot(5/6)=2/3$.
By Proposition~\ref{prop:distance to coarse}, our condition 1, and the fact that $n > 1/\epsilon$,
we have for any $h \in \ensuremath{\mathcal{H}}$ that
\begin{align*}
  \Pru{x \sim \mu}{h(x) \neq h^\mathsf{coarse}(x)}
  \leq r^{-d}\cdot \mathsf{bbs}(\ensuremath{\mathcal{H}},r) + \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV}
  \leq \epsilon/3 + \frac{1}{12n} < \epsilon/2 \,.
\end{align*}
The output of the algorithm is $g \circ \mathsf{block}$, which for any $h \in \ensuremath{\mathcal{H}}$
satisfies:
\begin{align*}
	\Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{g(\mathsf{block}(x)) \neq b}
	&= \Pru{(v,b) \sim \ensuremath{\mathcal{D}}^\mathsf{block}}{g(v) \neq b}
	\leq \Pru{(v,b) \sim \ensuremath{\mathcal{D}}^\mathsf{block}}{h^\mathsf{block}(v) \neq b} + \epsilon/2 \\
	&= \Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{h^\mathsf{coarse}(x) \neq b} + \epsilon/2 \\
	&\leq \Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{h(x) \neq b} + \Pru{x}{h(x) \neq h^\mathsf{coarse}(x)} + \epsilon/2 \\
	&< \Pru{(x,b) \sim \ensuremath{\mathcal{D}}}{h(x) \neq b} + \epsilon \,.
\end{align*}
Then $\Pr{g(\mathsf{block}(x)) \neq b} \leq \inf_{h \in \ensuremath{\mathcal{H}}}{h(x) \neq b} + \epsilon$, as desired.
\end{proof}
\subsection{Fourier Analysis on \texorpdfstring{${[n]}^d$}{[n]\string^d}}
We will show how to construct a spanning set $\ensuremath{\mathcal{F}}$ to satisfy condition
2 of the general learning algorithm, by using noise sensitivity and the
Walsh basis. For any $n$, let $u \sim {[n]}^d$ uniformly
at random and draw $v \in {[n]}^d$ as follows: $v_i = u_i$ with probability
$\delta$, and $v_i$ is uniform in $[n]\setminus\{u_i\}$ with probability
$1-\delta$. The noise sensitivity of functions $[n]^d \to \{\pm 1\}$
is defined as:
\[
  \mathsf{ns}_{n,\delta}(f) := \Pru{u,v}{f(u) \neq f(v)} =
  \frac{1}{2}-\frac{1}{2}\cdot\Exu{u,v}{f(u)f(v)} \,.
\]
Note that we include $n$ in the subscript to indicate the size of the domain.
We will use $\mathsf{ns}_{r,\delta}(f)$ to obtain upper bounds on the spanning
set, and we will obtain bounds on $\mathsf{ns}_{r,\delta}$ by relating it
to $\mathsf{ns}_{2,\delta}$, for which many bounds are known.
For a function $f : {[n]}^d \to \{\pm 1\}$, two vectors $u,v \in {[r]}^d$, and $x
\in \{\pm 1\}^d$, define ${[u,v]}^x \in {[n]}^d$ as the vector with ${[u,v]}^x_i =
u_i$ if $x_i = 1$ and $v_i$ if $x_i=-1$. Then define $f_{u,v} : \{\pm 1\}^d \to
\{\pm 1\}$ as the function $f_{u,v}(x) = f({[u,v]}^x)$.  The next lemma is
essentially the same as the reduction in~\cite{BOW10}.
\begin{lemma}\label{lemma:noise sensitivity reduction}
Let $\ensuremath{\mathcal{H}}$ be a set of functions $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ such that for any linear
transformation $A \in \ensuremath{\mathbb{R}}^{d \times d}$, the function $f \circ A \in
\ensuremath{\mathcal{H}}$, and let $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ be any $r$-block partition.
Let $\mathsf{ns}_{2,\delta}(\ensuremath{\mathcal{H}}) = \sup_{f \in \ensuremath{\mathcal{H}}}
\mathsf{ns}_{2,\delta}(f)$ where $\mathsf{ns}_{2,\delta}(f)$ is the
$\delta$-noise sensitivity on domain $\{\pm 1\}^d$.  Then
$\mathsf{ns}_{r,\delta}(f^\mathsf{block}) \leq \mathsf{ns}_{2,\delta}(\ensuremath{\mathcal{H}})$.
\end{lemma}
\begin{proof}
Let $u \sim [r]^d$ and let $v$ be uniform among the vectors $[r]^d$ where
$\forall i, v_i \neq u_i$. Now let $x \sim \{\pm 1\}^d$ uniformly at random and let
$y$ be drawn such that $y_i = x_i$ with probability $\delta$ and $y_i = -x_i$
otherwise. Then ${[u,v]}^x$ is uniform in ${[r]}^d$, because ${[u,v]}^x_i$ is
$u_i$ or $v_i$ with equal probability and the marginals of $u_i,v_i$ are
uniform. ${[u,v]}^y_i= {[u,v]}^x_i$ with probability $1-\delta$ and is otherwise
uniform in $[r] \setminus\{{[u,v]}^x_i\}$. Let $f : {[r]}^d \to \{\pm 1\}$ and
$\delta \in [0,1]$.  Let $(u',v')$ be an independent copy of $(u,v)$
and observe that $\mathsf{ns}_{r,\delta}(f^\mathsf{block}) = \Pr{f^\mathsf{block}(u') \neq
f^\mathsf{block}(v')}$.  Now observe that $({[u,v]}^x,{[u,v]}^y)$ has the same
distribution as $(u',v')$, so:
\begin{align*}
\Exu{u,v}{\mathsf{ns}_{2,\delta}(f_{u,v})}
&= \Exu{u,v}{\Pru{x,y\sim_\delta x}{f({[u,v]}^x) \neq f({[u,v]}^y)}} \\
&= \Exu{u,v,{(x,y)}_\delta}{\ind{f({[u,v]}^x) \neq f({[u,v]}^y)}}  \\
&= \Exu{u',v'}{\ind{f(u') \neq f(v')}} = \mathsf{ns}_{r,\delta}(f^\mathsf{block}) \,.
\end{align*}
For any $u,v \in [r]^d$, define the function $\Phi_{u,v} : \{\pm 1\}^d \to [r]^d$
by $\Phi_{u,v}(x) = \mathsf{blockpoint}([u,v]^x)$. This function maps $\{\pm 1\}^d$
to a set $\{b_{1,i_1}, b_{1,j_1}\} \times \dotsm \times \{b_{d,i_d},b_{d,j_d}\}$
and can be obtained by translation and scaling, which is a linear transformation.
Therefore $f_{u,v} = f \circ \Phi_{u,v}^{-1}$, so we are guaranteed that
$f_{u,v} \in \ensuremath{\mathcal{H}}$. So
\[
  \mathsf{ns}_{r,\delta}(f) = \Exu{u,v}{\mathsf{ns}_{2,\delta}(f_{u,v})}
  \leq \mathsf{ns}_{2,\delta}(\ensuremath{\mathcal{H}}) \,. \qedhere
\]
\end{proof}

We define the Walsh basis, an orthonormal basis of functions $[n]^d \to
\ensuremath{\mathbb{R}}$; see e.g.~\cite{BRY14}.
Suppose $n=2^m$ for some positive integer $m$.
For two functions $f,g : {[n]}^d \to \ensuremath{\mathbb{R}}$, define the inner product $\inn{f,g} =
\ensuremath{\mathbb{E}}_{x \sim {[n]}^d}[f(x)g(x)]$. The Walsh functions $\{\psi_0, \dotsc,
\psi_m\}, \psi_i : [n] \to \{\pm 1\}$ can be defined by $\psi_0 \equiv 1$ and
for $i \geq 1$, $\psi_i(z) := (-1)^{\mathsf{bit}_i(z-1)}$ where
$\mathsf{bit}_i(z-1)$ is the $i^\mathrm{th}$ bit in the binary representation of
$z-1$, where the first bit is the least significant (see e.g.~\cite{BRY14}). It is easy
to verify that for all $i,j \in \{0, \dotsc, m\}$, if $i \neq j$ then
$\inn{\psi_i,\psi_j}=0$, and $\ensuremath{\mathbb{E}}_{x \sim [n]}[\psi_i(x)] = 0$ when $i \geq 1$.
For $S \subseteq [m]$ define $\psi_S = \prod_{i \in S} \psi_i$ and note that for
any set $S \subseteq [m], S \neq \emptyset$,
\begin{equation}
\label{eq:walsh function has mean 0}
\Exu{x \sim [n]}{\psi_S(x)} = \Exu{x \sim [n]}{\prod_{i \in S} \psi_i(x)}
= \Exu{x \sim [n]}{(-1)^{\sum_{i \in S}\mathsf{bit}_i(x-1)}} = 0
\end{equation}
since each bit is uniform in $\{0,1\}$, while $\psi_\emptyset \equiv 1$.  For $S,T
\subseteq [m]$,
\[
\inn{\psi_S,\psi_T} = \ensuremath{\mathbb{E}}_{x \sim [n]}[\psi_S(x)\psi_T(x)] =
\ensuremath{\mathbb{E}}_x[\psi_{S \Delta T}(x)] \,,
\]
where $S \Delta T$ is the symmetric difference, so
this is 0 when $S \Delta T \neq \emptyset$ (i.e.~$S \neq T$) and 1 otherwise;
therefore $\{\psi_S : S \subseteq [m]\}$ is an orthonormal basis of functions
$[n] \to \ensuremath{\mathbb{R}}$. Identify each $S \subseteq [m]$ with the number $s \in \{0,
\dotsc, n-1\}$ where $\mathsf{bit}_i(s) = \ind{i \in S}$. Now for every $\alpha
\in \{0,\dotsc,n-1\}^d$ define $\psi_\alpha : [n]^d \to \{\pm 1\}$ as
$\psi_\alpha(x) = \prod_{i=1}^d \psi_{\alpha_i}(x_i)$ where $\psi_{\alpha_i}$ is
the Walsh function determined by the identity between subsets of $[m]$ and the
integer $\alpha_i \in \{0, \dotsc, n-1\}$. It is easy to verify that the set
$\{\psi_\alpha : \alpha \in {\{0,\dotsc,n-1\}}^d\}$ is an orthonormal basis.
Every function $f : {[n]}^d \to \ensuremath{\mathbb{R}}$ has a unique representation $f =
\sum_{\alpha \in \{0,\dotsc,n-1\}^d} \hat f(\alpha) \psi_\alpha$ where $\hat{f}(\alpha) = \inn{f,\psi_\alpha}$.

\newcommand{\mathsf{stab}}{\mathsf{stab}}
For each $x \in {[n]}^d$ and $\rho \in [0,1]$ define $N_\rho(x)$ as the
distribution over $y \in {[n]}^d$ where for each $i \in [d]$, $y_i = x_i$ with
probability $\rho$ and $y_i$ is uniform in $[n]$ with probability $1-\rho$.
Define $T_\rho f(x) := \Exu{y \sim N_\rho(x)}{f(y)}$ and $\mathsf{stab}_\rho(f)
:= \inn{f,T_\rho f}$. For any $\alpha \in {\{0,\dotsc,n-1\}}^d$,
\begin{align*}
  T_\rho \psi_\alpha(x)
  &= \Exu{y \sim N_\rho(x)}{\psi_\alpha(y)}
  = \Exu{y \sim N_\rho(x)}{\prod_{i=1}^d \psi_{\alpha_i}(y_i)}
  = \prod_{i=1}^d \Exu{y_i \sim N_\rho(x_i)}{\psi_{\alpha_i}(y_i)}  \\
  &= \prod_{i=1}^d \left[ \rho \psi_{\alpha_i}(x_i)
    + (1-\rho)\Exu{z \sim [n]}{\psi_{\alpha_i}(z)} \right] \,.
\end{align*}
If $\alpha_i \geq 1$ then $\Exu{z \sim [n]}{\psi_{\alpha_i}(z)} = 0$; otherwise,
$\psi_1 \equiv 1$ so $\Exu{y_i \sim N_\rho(x_i)}{\psi_0(y_i)} = 1$. Therefore
\[
  T_\rho \psi_\alpha(x) = \rho^{|\alpha|} \psi_\alpha(x) \,,
\]
where $|\alpha|$ is the number of nonzero entries of $\alpha$; so
$\widehat{T_\rho f}(\alpha) = \inn{\psi_\alpha,T_\rho f} = \inn{T_\rho
\psi_\alpha, f} = \rho^{|\alpha|} \widehat f(\alpha)$. Since $T_\rho$ is a
linear operator,
\[
  \mathsf{stab}_\rho(f) = \inn{f,T_\rho f} = \sum_\alpha \rho^{|\alpha|} \hat{f}{(\alpha)}^2 \,.
\]
Note that for $f : \{\pm 1\}^d \to \{\pm 1\}$, $\mathsf{stab}_\rho(f)$ is the usual notion of
stability in the analysis of Boolean functions.
\begin{proposition}
For any $f : {[n]}^d \to \{\pm 1\}$ and any $\delta,\rho \in [0,1]$,
$\mathsf{ns}_{n,\delta}(f) = \frac{1}{2} - \frac{1}{2} \cdot
\mathsf{stab}_{1-\frac{n}{n-1}\delta}(f)$.
\end{proposition}
\begin{proof}
For $v \sim N_\rho(u), v_i = u_i$ with probability $\rho +
\frac{1-\rho}{n}$, so in the definition of noise sensitivity, $v$ is distributed
as $N_\rho(u)$ where $(1-\delta) = \rho +\frac{1-\rho}{n}$, i.e.~$\delta = 1 -
\rho - \frac{1-\rho}{n} = (1-1/n) - \rho(1-1/n) = (1-\rho)(1-1/n)$; or, $\rho =
1 - \frac{n}{n-1}\delta$. By rearranging, we arrive at the conclusions.
\end{proof}
\begin{proposition}\label{prop:noise sensitivity to fourier degree}
For any $f : {[n]}^d \to \ensuremath{\mathbb{R}}$ and $t = \frac{2}{\delta}$, $\sum_{\alpha : |\alpha|
\geq t} \hat f{(\alpha)}^2 \leq 2.32 \cdot \mathsf{ns}_{n,\delta}(f)$.
\end{proposition}
\begin{proof}
Following~\cite{KOS04}:
\begin{align*}
2\mathsf{ns}_{n,\delta}(f)
&= 1-\sum_\alpha {\left(1-\frac{n}{n-1}\delta\right)}^{|\alpha|} \hat f{(\alpha)}^2
\geq 1 - \sum_\alpha {\left(1-\delta\right)}^{|\alpha|} \hat f{(\alpha)}^2 \\
&= \sum_\alpha (1-{\left(1-\delta\right)}^{|\alpha|}) \hat f{(\alpha)}^2  
\geq \sum_{\alpha:|\alpha|\geq 2/\delta}
  (1-{\left(1-\delta\right)}^{|\alpha|}) \hat f{(\alpha)}^2 \\
&\geq \sum_{\alpha:|\alpha|\geq 2/\delta}
  (1-{\left(1-\delta\right)}^{2/\delta}) \hat f{(\alpha)}^2
\geq (1-e^{-2})\sum_{\alpha:|\alpha|\geq 2/\delta} \hat f{(\alpha)}^2 \,.
\end{align*}
The result now holds since $2/(1-e^{-2}) < 2.32$.
\end{proof}

\begin{lemma}\label{lemma:noise sensitivity to polynomial regression}
Let $\ensuremath{\mathcal{H}}$ be a set of functions $[n]^d \to \{\pm 1\}$ where $n$ is a power of 2,
let $\epsilon,\delta > 0$ such that $\forall h \in \ensuremath{\mathcal{H}},
\mathsf{ns}_{n,\delta}(h) \leq \epsilon^2/3$, and let $t = \ceil{\frac{2}{\delta}}$.
Then there is a set $\ensuremath{\mathcal{F}}$ of functions ${[n]}^d \to \ensuremath{\mathbb{R}}$ of size $|\ensuremath{\mathcal{F}}| \leq
{(nd)}^t$, such that that for any $h \in \ensuremath{\mathcal{H}}$, there is a function $p \in
\mathsf{span}(\ensuremath{\mathcal{F}})$ where $\Ex{{(h(x)-p(x))}^2} \leq \epsilon^2$.
\end{lemma}
\begin{proof}
Let $p = \sum_{|\alpha| < t} \hat f(\alpha) \phi_\alpha$.
Then by Proposition~\ref{prop:noise sensitivity to fourier degree},
\begin{align*}
  \Ex{{(p(x)-f(x))}^2}
  &= \Ex{{\left(\sum_{|\alpha| \geq t} \hat f(\alpha) \phi_\alpha(x)\right)}^2}
  = \Ex{\sum_{|\alpha| \geq t}\sum_{|\beta| \geq t}
    \hat f(\alpha) \hat f(\beta) \phi_\alpha(x) \phi_\alpha(x) } \\
  &= \sum_{|\alpha| \geq t}\sum_{|\beta| \geq t}
    \hat f(\alpha) \hat f(\beta) \inn{\phi_\alpha,\phi_\beta}
  = \sum_{|\alpha| \geq t} \hat f{(\alpha)}^2 \leq \epsilon^2 \,.
\end{align*}
Therefore $p$ is a linear combination of functions $\phi_\alpha = \prod_{i=1}^d
\phi_{\alpha_i}$ where at most $t$ values $\alpha_i \in \{0, \dotsc, n-1\}$ are
not 0. There are at most ${((n-1)d)}^t$ such products since for each
non-constant $\phi_{\alpha_i}$ we choose $i \in [d]$ and $\alpha_i \in [n-1]$.
We may take $\ensuremath{\mathcal{F}}$ to be the set of these products.
\end{proof}

\subsection{Application}
To apply Lemma~\ref{lemma:general algorithm}, we must give bounds on
$\mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}},r)$ and the noise sensitivity:

\begin{lemma}\label{lemma:halfspace block boundary}
Fix any $r$. Then $\mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}},r) \leq dkr^{d-1}$.
\end{lemma}
\begin{proof}
Any halfspace $h(x) = \sign(\inn{w,x}-t)$ is unate, meaning there is a vector
$\sigma \in \{\pm 1\}^d$ such that the function $h^\sigma :=
\sign(\inn{w,x^\sigma}-t)$, where $x^\sigma = (\sigma_1x_1, \dotsc,
\sigma_d x_d)$, is monotone. For any $r$-block partition $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to
[r]^d$ defined by values $\{a_{i,j}\}$ for $i \in [d], j \in [r-1]$, we can
define $\mathsf{block}^\sigma : \ensuremath{\mathbb{R}}^d \to [r]^d$ as the block partition obtained by
taking $\{\sigma_i \cdot a_{i,j}\}$. The number
of non-constant blocks of $h$ in $\mathsf{block}$ is the same as that of $h^\sigma$ in
$\mathsf{block}^\sigma$, but $h^\sigma$ is monotone. Thus the bound on $\mathsf{bbs}$ for
monotone functions holds, so $\mathsf{bbs}(\ensuremath{\mathcal{H}},r) \leq dr^{d-1}$ by
Lemma~\ref{lemma:monotone block boundary}, and Lemma~\ref{prop:resolution of
composed functions} gives $\mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}},r) \leq dkr^{d-1}$.
\end{proof}

The bounds on noise sensitivity follow from known results for the hypercube.
\begin{proposition}\label{prop:noise sensitivity composition}
Let $h_1, \dotsc, h_k : {[n]}^d \to \{\pm 1\}$ and let $g : \{\pm 1\}^k \to \{\pm 1\}$.
Let $f := g \circ (h_1, \dotsc,h_k)$. Then $\mathsf{ns}_\delta(f) \leq
\sum_{i=1}^k \mathsf{ns}_\delta(h_i)$.
\end{proposition}
\begin{proof}
For $u,v$ drawn from ${[n]}^d$ as in the definition of noise sensitivity, the
union bound gives
$\mathsf{ns}_\delta(f) = \Pru{u,v}{f(u) \neq f(v)}
  \leq \Pru{u,v}{\exists i : h_i(u) \neq h_i(v)}
  \leq \sum_{i=1}^k \mathsf{ns}_\delta(h_i)$.
\end{proof}

\begin{lemma}\label{lemma:halfspace noise sensitivity}
Let $f = g \circ (h_1, \dotsc, h_k) \in \ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}}$. For any $r$-block
partition $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$, and any $\delta \in [0,1],
\mathsf{ns}_{r,\delta}(f^\mathsf{block}) = O(k \sqrt \delta)$.
\end{lemma}
\begin{proof}
It is known that $\mathsf{ns}_{2,\delta}(\ensuremath{\mathcal{H}}) = O(\sqrt \delta)$ (Peres'
theorem~\cite{OD14}). Let $A$ be any full-rank linear transformation and let $h
\in \ensuremath{\mathcal{H}}$, $h \circ A \in \ensuremath{\mathcal{H}}$.  This holds since for some $w \in \ensuremath{\mathbb{R}}^d, t \in
\ensuremath{\mathbb{R}}$, $h(Ax) = \sign(\inn{w,Ax}-t) = \sign(\inn{Aw,x}-t)$, which is a halfspace.
Then Lemma~\ref{lemma:noise sensitivity reduction} implies
$\mathsf{ns}_{r,\delta}(h^\mathsf{block}) \leq \mathsf{ns}_{2,\delta}(\ensuremath{\mathcal{H}}) = O(\sqrt
\delta)$ and we conclude with Proposition~\ref{prop:noise sensitivity
composition}.
\end{proof}


	
	

\thmhalfspaces*
\begin{proof}
Here we prove only the continuous distribution case. The finite case is proved in \cref{thm:finite
algorithms}.

For $r = \ceil{dk/\epsilon}$, we have $r^{-d}\cdot \mathsf{bbs}(\ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}},r) \leq
\epsilon$ by Lemma~\ref{lemma:halfspace block boundary}, so condition 1 of
Lemma~\ref{lemma:general algorithm} holds. Lemma~\ref{lemma:halfspace noise
sensitivity} guarantees that for any $f \in \ensuremath{\mathcal{B}}_k \circ \ensuremath{\mathcal{H}},
\mathsf{ns}_{r,\delta}(f^\mathsf{block}) = O(k \sqrt \delta)$. Setting $\delta =
\Theta(\epsilon^4/k^2)$ so that $\mathsf{ns}_{r,\delta}(f^\mathsf{block}) \leq
\epsilon^2/3$, we obtain via Lemma~\ref{lemma:noise sensitivity to polynomial
regression} a set $\ensuremath{\mathcal{F}}$ of size $|\ensuremath{\mathcal{F}}| \leq (rd)^{O(k^2/\epsilon^4)}$ satisfying
condition 2 of Lemma~\ref{lemma:general algorithm}. Then for $n =
\poly(|\ensuremath{\mathcal{F}}|,1/\epsilon)$ we apply Lemma~\ref{lemma:general algorithm} to get an
algorithm with sample complexity
\[
  O\left(rd^2n^2\log(rd)\right)
  = O\left(\frac{d^3k}{\epsilon}\log(dk/\epsilon)\right)
  \cdot
\left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k^2}{\epsilon^4}\right)} \,.
\]
The other time complexity follows from Lemma~\ref{lemma:brute force}.
\end{proof}

\section{Learning Polynomial Threshold Functions}\label{section:ptfs}
A \emph{degree-$k$ polynomial threshold function (PTF)} is a function $f : \ensuremath{\mathbb{R}}^d
\to \{\pm 1\}$ such that there is a degree-$k$ polynomial $p : \ensuremath{\mathbb{R}}^d \to \ensuremath{\mathbb{R}}$ in
$d$ variables where $f(x) = \sign(p(x))$; for example, a halfspaces is a
degree-1 PTF\@. Let $\ensuremath{\mathcal{P}}_k$ be the set of degree-$k$
PTFs. As for halfspaces, we will give bounds on the noise sensitivity
and block boundary size and apply the general learning algorithm. The bound on
noise sensitivity will follow from known results on the hypercube~\cite{DHK+10},
but the bound on the block boundary size is much more difficult to obtain than
for halfspaces.

\subsection{Block-Boundary Size of PTFs}

A theorem of Warren~\cite{War68} gives a bound on the number of connected
components of $\ensuremath{\mathbb{R}}^d$ after removing the 0-set of a degree-$k$ polynomial. This
bound (Theorem~\ref{thm:warren} below) will be our main tool.

\newcommand{\mathsf{comp}}{\mathsf{comp}}
A set $S \subseteq \ensuremath{\mathbb{R}}^d$ is \emph{connected}\footnote{Here we are using the
fact that \emph{connected} and \emph{path-connected} are equivalent in $\ensuremath{\mathbb{R}}^d$.}
if for every $s,t \in S$ there is a continuous function $p : [0,1] \to S$ such
that $p(0)=s,p(1)=t$. A subset $S \subseteq X$ where $X \subseteq \ensuremath{\mathbb{R}}^d$ is a
\emph{connected component} of $X$ if it is connected and there is no connected
set $T \subseteq X$ such that $S \subseteq T$. Write $\mathsf{comp}(X)$ for the number of
connected components of $X$.

A function $\rho : \ensuremath{\mathbb{R}}^d \to (\ensuremath{\mathbb{R}} \cup \{*\})^d$ is called a \emph{restriction}
and we will denote $|\rho| = |\{i \in [d] : \rho(i) = *\}|$. The affine subspace
$A_\rho$ induced by $\rho$ is $A_\rho := \{ x \in \ensuremath{\mathbb{R}}^d \;|\; x_i = \rho(i)
\text{ if } \rho(i) \neq *\}$ and has affine dimension $|\rho|$.

For $n \leq d$, let $\ensuremath{\mathcal{A}}_n$ be the set of affine subspaces
$A_\rho$ obtained by choosing a restriction $\rho$ with $\rho(i) = *$ when $i
\leq n$ and $\rho(i) \neq *$ when $i > n$, so in particular $\ensuremath{\mathcal{A}}_d = \{\ensuremath{\mathbb{R}}^d\}$.

Let $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ be a measurable function and define the boundary of
$f$ as:
\[
  \partial f := \{ x \in \ensuremath{\mathbb{R}}^d \;|\; \forall \epsilon > 0, \exists y :
\|x-y\|_2 < \epsilon, f(y) \neq f(x) \} \,.
\]
This is equivalent to the boundary of the set of $+1$-valued points, and the
boundary of any set is closed.  Each measurable $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ induces a
partition of $\ensuremath{\mathbb{R}}^d \setminus
\partial f$ into some number of connected parts.
For a set $\ensuremath{\mathcal{H}}$ of functions $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ and $n \leq d$, write
\newcommand{\mathsf{parts}}{\mathsf{parts}}
\[
M(n) :=
  \max_{f \in \ensuremath{\mathcal{H}}} \max_{A \in \ensuremath{\mathcal{A}}_n} \mathsf{comp}(A \setminus \partial f) \,.
\]
For each $i \in [d]$ let $\ensuremath{\mathcal{P}}_i$ be the set of hyperplanes of the form $\{x \in
\ensuremath{\mathbb{R}}^d \;|\; x_i = a\}$ for some $a \in \ensuremath{\mathbb{R}}$.
An \emph{$(r,n,m)$-arrangement} for $f$ is any set $A \setminus \left(\partial f
\cup \bigcup_{i=1}^m \bigcup_{j=1}^{r-1} H_{i,j}\right)$ where $A \in \ensuremath{\mathcal{A}}_n$ and
$H_{i,j} \in \ensuremath{\mathcal{P}}_i$ such that all $H_{i,j}$ are distinct. Write $R_f(r,n,m)$ for
the set of $(r,n,m)$-arrangements for $f$. Define
\[
  P_r(n,m) := \max_{f \in \ensuremath{\mathcal{H}}} \max\{ \mathsf{comp}(R) \;|\; R \in R_f(r,n,m) \}
\]
and observe that $P_r(n,0) = M(n)$.


\begin{proposition}\label{prop:bbs bound}
For any set $\ensuremath{\mathcal{H}}$ of functions $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ and any $r > 0$,
$\mathsf{bbs}(\ensuremath{\mathcal{H}}, r) \leq P_r(d,d) - r^d$.
\end{proposition}
\begin{proof}
Consider any $r$-block partition, which is obtained by choosing values $a_{i,j}
\in \ensuremath{\mathbb{R}}$ for each $i \in [d], j \in [r-1]$ and defining $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to
[r]^d$ by assigning each $x \in \ensuremath{\mathbb{R}}^d$ the block $v \in [r]^d$ where $v_i$ is
the unique value such that $a_{i,v_i-1} < x_i \leq a_{i,v_i}$, where we define
$a_{i,0} = -\infty, a_{i,r} = \infty$. Suppose $v$ is a non-constant block, so
there are $x,y \in \mathsf{block}^{-1}(v) \setminus \partial f$ such that $f(x) \neq f(y)$.
Let $H_{i,j} = \{ x \in \ensuremath{\mathbb{R}}^d \;|\; x_i = a_{i,j}\}$ and let $B = \partial f
\cup \bigcup_{i,j} H_{i,j}$. Consider the set $\ensuremath{\mathbb{R}}^d \setminus B$. Since $x \notin \partial f$
there exists some small open ball $R_x$ around $x$ such that $\forall x' \in R_x, f(x') = f(x)$;
and since $x \in \mathsf{block}^{-1}(v)$, $R_x \cap \mathsf{block}^{-1}(v)$ is a set of positive
Lebesgue measure. Since $B$ has Lebesgue measure 0, we conclude that
$(R_x \cap \mathsf{block}^{-1}(v)) \setminus B$ has positive measure, so there
is $x' \in \mathsf{block}^{-1}(v) \setminus B$ with $f(x')=f(x)$. Likewise, there
is $y' \in \mathsf{block}^{-1}(v) \setminus B$ with $f(y')=f(y) \neq f(x')$. Therefore
$x',y'$ must belong to separate components, so $\mathsf{block}^{-1}(v)\setminus B$ is
partitioned into at least 2 components.  Meanwhile, each constant block
is partitioned into at least 1 component. So
\[
  P_r(d,d) \geq 2 \cdot (\#\text{ non-constant blocks}) + (\#\text{ constant
blocks}) = \mathsf{bbs}(\ensuremath{\mathcal{H}},r) + r^d \,. \qedhere
\]
\end{proof}

The following fact must be well-known, but not to us:
\begin{proposition}\label{prop:cutting bound}
Let $A$ be an affine subspace of $\ensuremath{\mathbb{R}}^d$,
let $B \subset A$, and for $a \in \ensuremath{\mathbb{R}}$ let $H = \{ x \in \ensuremath{\mathbb{R}}^d \;|\; x_1 = a
\}$. Then
\[
  \mathsf{comp}(A \setminus (H\cup B)) - \mathsf{comp}(A \setminus B)
  \leq \mathsf{comp}(H \setminus B) \,.
\]
\end{proposition}
\begin{proof}
Let $G$ be the graph with its vertices $V$ being the components of $A \setminus
(H \cup B)$ and the edges $E$ being the pairs $(S,T)$ where $S,T$ are components
of $A \setminus (H \cup B)$ such that $\forall s \in S, s_1 < a$, $\forall t \in
T, t_1 > a$, and there exists a component $U$ of $A \setminus B$ such that $S,T
\subset U$. Clearly $\mathsf{comp}(A \setminus (H \cup B)) = |V|$; we will show that
$\mathsf{comp}(A \setminus B)$ is the number of connected components of $G$ and that
$|E| \leq \mathsf{comp}(H \setminus B)$. This suffices to prove the statement. We will
use the following claim:
\begin{claim}
Let $U$ be a connected component of $A \setminus B$.  If $S,T \in V$ and there
is a path $p : [0,1] \to U$ such that $p(0) \in S, p(1) \in T$ and either
$\forall \lambda,p(\lambda)_1 \leq a$ or $\forall \lambda, p(\lambda)_1 \geq a$,
then $S=T$.
\end{claim}
\begin{proof}[Proof of claim]
Assume without loss of generality that $p(\lambda)_1 \leq a$ for all $\lambda$.
Let $P = \{ p(\lambda) \;|\; \lambda \in [0,1]\}$. Since $U$ is open we can
define for each $\lambda$ a ball $B(\lambda) \ni p(\lambda)$ such that
$B(\lambda) \subset U$. Consider the sets $B_a(\lambda) := \{ x \in
B(\lambda) \;|\; x_1 < a \}$, which are open, and note that for all
$\alpha,\beta \in [0,1]$, if $p(\alpha) \in B(\beta)$ then $B_a(\alpha)\cap
B_a(\beta) \neq \emptyset$ since $p(\alpha)_1,p(\beta)_1 \leq a$.

Assume for contradiction that there is $\lambda$ such that $B_a(\lambda)$ is not
connected to $S$ or $T$; then let $\lambda'$ be the infimum of all such
$\lambda$, which must satisfy $\lambda' > 0$ since $p(0) \in S$. For any
$\alpha$, if $p(\alpha) \in B(\lambda')$ and $B_a(\alpha)$ is connected to $S$
or $T$ then since $B_a(\lambda') \cap B_a(\alpha)$ it must be that
$B_a(\lambda)$ is connected as well; therefore $B_a(\alpha)$ is not connected to
either $S$ or $T$. But since $p$ is continuous, there is $\alpha < \lambda'$
such that $p(\alpha) \in B(\lambda')$, so $\lambda'$ cannot be the infimum,
which is a contradiction. Therefore every $\lambda$ has $B_a(\lambda)$ connected
to either $S$ or $T$. If $S \neq T$, this is a contradiction since there must
then be $\alpha,\beta$ such that $p(\alpha) \in B(\beta)$ but
$B_a(\alpha),B_a(\beta)$ are connected to $S,T$ respectively.  Therefore $S=T$.
\end{proof}
We first show that $\mathsf{comp}(A \setminus B)$ is the number of graph-connected
components of $G$.  Suppose that vertices $(S,T)$ are connected, so there is a
path $S = S_0, \dotsc, S_n = T$ in $G$. Then there are connected components
$U_i$ of $A \setminus B$ such that $S_{i-1},S_i \subset U_i$; so $S_i \subset
U_i \cap U_{i+1}$, which implies that $\bigcup_i U_i \subset A \setminus B$ is
connected.  Therefore we may define $\Phi$ as mapping each connected component
$\{S_i\}$ of $G$ to the unique component $U$ of $A \setminus B$ with $\bigcup_i
S_i \subset U$. $\Phi$ is surjective since for each component $U$ of $A
\setminus B$ there is some vertex $S$ (a component of $A \setminus (H \cup B)$)
such that $S \subseteq U$: this is $U$ itself if $U \cap H = \emptyset$. For
some connected component $U$ of $A \setminus B$, let $S,T \subseteq U$ be
vertices of $G$, and let $s \in S, t \in T$; since $U$ is connected, there is a
path $p : [0,1] \to U$ such that $s=p(0),t=p(1)$. Let $S=S_0, \dotsc, S_n = T$
be the multiset of vertices such that $\forall \lambda \in [0,1], \exists i :
p(\lambda) \in S_i$; let $\psi(\lambda) \in \{0, \dotsc, n\}$ be the index such
that $p(\lambda) \in S_{\psi(\lambda)}$, and order the sequence such that if
$\alpha < \beta$ then $\psi(\alpha) \leq \psi(\beta)$ (note that we may have
$S_i = S_j$ for some $i < j$ if $p(\lambda)$ visits the same set more than
once). Then for any $i$, $S_i,S_{i+1} \subseteq U$ since the path visits both
and is contained in $U$. If $S_i,S_{i+1}$ are on opposite sides of $H$, then
there is an edge $(S_i,S_{i+1})$ in $G$; otherwise, the above claim implies
$S_i=S_{i+1}$. Thus there is a path $S$ to $T$ in $G$; this proves that $\Phi$
is injective, so $\mathsf{comp}(A \setminus B)$ is indeed the number of graph-connected
components of $G$.

Now let $(S,T) \in E$, so there is a component $U$ of $A \setminus B$ such that
$S,T \subset U$. For any $s \in S, t \in T$ there is a continuous path $p_{s,t}
: [0,1] \to U$ where $p_{s,t}(0)=s,p_{s,t}(1)=t$. There must be some $z \in
[0,1]$ such that $p_{s,t}(z) \in H$, otherwise the path is a path in $\ensuremath{\mathbb{R}}^d
\setminus B$ and $S=T$. Since $p_{s,t}(z) \in H \cap U$, so $p_{s,t}(z) \notin
B$, there is some component $Z \in \ensuremath{\mathcal{C}}_H$ containing $p_{s,t}(z)$. We will map
the edge $(S,T)$ to an arbitrary such $Z$, for any choice $s,t,z$, and show that
it is injective.  Suppose that $(S,T),(S',T')$ map to the same $Z \in \ensuremath{\mathcal{C}}_H$.
Without loss of generality we may assume that $S,S'$ lie on the same side of $H$
and that $\forall x \in S\cup S', x_1 < a$. Then there are $s \in S, s' \in S',
t \in T, t' \in T'$, and $z,z' \in [0,1]$ such that $p_{s,t}(z),p_{s',t'}(z') \in
Z$. Then since $Z$ is a connected component, we may take $z,z'$ to be the least
such values that $p_{s,t}(z),p_{s',t'}(z) \in Z$, and connected
$p_{s,t}(z),p_{s',t'}(z)$ by a path in $Z$ to obtain a path $q : [0,1] \to U$
such that $q(0)=s,q(1)=s'$, and $\forall \lambda, q(\lambda)_1 \leq a$. Then by
the above claim, $S=S'$; the same holds for $T,T'$, so the mapping is injective.
This completes the proof of the proposition.
\end{proof}

\begin{proposition}\label{prop:induction}
For any set $\ensuremath{\mathcal{H}}$ of measurable functions $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ and any $r > 1$,
\[
  P_r(n,m) \leq P_r(n,m-1) + (r-1) \cdot P_r(n-1,m-1) \,.
\]
\end{proposition}
\begin{proof}
Let $A \in \ensuremath{\mathcal{A}}_n$ and $a_{i,j} \in \ensuremath{\mathbb{R}}$, $i\in [m],j \in [r-1]$ such that the
number of connected components in $A \setminus B$, where $B = \partial f
\cup \bigcup_{i,j} H_{i,j}$ and $H_{i,j} = \{ x \in A \;|\; x_i = a_{i,j}\}$, is
$P_r(n,m)$. For $0 \leq k \leq r-1$ let
\[
B_k := \partial f \cup
  \left(\bigcup_{i=1}^{m-1} \bigcup_{j=1}^{r-1} H_{i,j}\right) \cup
  \left(\bigcup_{j=1}^{k} H_{m,j}\right) \,,
\]
so that $B = B_{r-1}$ and $B_k = B_{k-1} \cup H_{m,k}$. Since $B_0$ is an
$(r,n,m-1)$-arrangement, $\mathsf{comp}(A \setminus B_0) \leq P_r(n,m-1)$. For
$k > 0$,  since $B_k$ is obtained from $B_{k-1}$ by
adding a hyperplane $H_{m,k}$, Proposition~\ref{prop:cutting bound} implies
\[
\mathsf{comp}(A \setminus B_k)
\leq \mathsf{comp}(A \setminus B_{k-1}) + \mathsf{comp}(H \setminus B_{k-1})
\leq \mathsf{comp}(A \setminus B_{k-1}) + P_r(n-1,m-1) \,,
\]
because $H \setminus B_{k-1}$ is an $(r,n-1,m-1)$-arrangement. Iterating $r-1$
times, once for each added hyperplane, we arrive at
\begin{align*}
  P_r(n,m)
    &= \mathsf{comp}(A \setminus B) \\
    &= \mathsf{comp}(A \setminus B_0) + \sum_{k=1}^{r-1}\left(
      \mathsf{comp}(A \setminus B_k) - \mathsf{comp}(A \setminus B_{k-1}) \right) \\
    &\leq P_r(n,m-1) + (r-1) P_r(n-1,m-1) \,. \qedhere
\end{align*}
\end{proof}

\begin{lemma}\label{lemma:bernoulli sum}
For any set $\ensuremath{\mathcal{H}}$ of measurable functions $\ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ and any $r$,
\[
  P_r(d,d) \leq (r-1)^d
	+ \sum_{i=0}^{d-1}  \binom{d}{i}  \cdot M(d-i) \cdot (r-1)^i \,.
\]
\end{lemma}
\begin{proof}
Write $s = r-1$ for convenience.
We will show by induction the more general statement that for any $m \leq n \leq
d$,
\[
	P_r(n,m) \leq \sum_{i=0}^m \binom{m}{i} \cdot M(n-i) \cdot s^i
\]
where we define $M(0) := 1$. In the base case, note that
$P_r(n,0) = M(n)$.  Assume the statement holds for
$P_r(n',m')$ when $n' \leq n, m' < m$.  Then by
Proposition~\ref{prop:induction},
\begin{align*}
P_r(n,m)
&\leq P_r(n,m-1) + s \cdot P_r(n-1,m-1) \\
&\leq \sum_{i=0}^{m-1} {m-1 \choose i} \cdot M(n-i) \cdot s^i
    + \sum_{i=0}^{m-1} {m-1 \choose i} \cdot M(n-1-i) \cdot s^{i+1} \\
&\leq \sum_{i=0}^{m-1} {m-1 \choose i} \cdot M(n-i) \cdot s^i
    + \sum_{i=1}^{m} {m-1 \choose i-1} \cdot M(n-i) \cdot s^{i} \\
&= M(n) + M(n-m) \cdot s^m + \sum_{i=1}^{m-1}\left({m-1 \choose i} + {m-1
\choose i-1}\right) \cdot M(n-i) \cdot s^i \\
&= \sum_{i=0}^m \binom{m}{i} \cdot M(n-i) \cdot s^i \,. \qedhere
\end{align*}
\end{proof}

\begin{lemma}\label{lemma:bbs for low-components}
Let $\ensuremath{\mathcal{H}}$ be a set of functions $f : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ such that for some $k
\geq 1$, $M(n) \leq k^n$.  Then for any $\epsilon > 0$ and $r \geq
3dk/\epsilon$, $\mathsf{bbs}(\ensuremath{\mathcal{H}},r) < \epsilon \cdot r^d$.
\end{lemma}
\begin{proof}
Write $s = r-1$.  By Proposition~\ref{prop:bbs bound} and Lemma~\ref{lemma:bernoulli sum}, the
probability that $v$ is a non-constant block is
\begin{align*}
  \frac{\mathsf{bbs}(r)}{r^d}
  &\leq r^{-d}\left(P_r(d,d) - r^d\right)
  \leq r^{-d}\left(\sum_{i=0}^{d-1}\left[{d \choose i} \cdot M(d-i)
    \cdot s^i\right] + s^d - r^d\right) \\
  &\leq r^{-d} \sum_{i=0}^{d-1}{d \choose i} \cdot M(d-i) \cdot s^i \,.
\end{align*}
Split the sum into two parts:
\begin{align*}
&
  \sum_{i=0}^{\floor{d/2}}{d \choose i} \cdot \frac{M(d-i) \cdot s^i}{r^d}
+ \sum_{i=1}^{\ceil{d/2}-1} {d \choose i} \cdot \frac{M(i) \cdot s^{d-i}}{r^d} \\
&\qquad\leq
  \sum_{i=0}^{\floor{d/2}}{d \choose i} \cdot \frac{k^{d-i} \cdot r^i}{r^d}
+ \sum_{i=1}^{\ceil{d/2}-1} {d \choose i} \cdot \frac{k^i \cdot r^{d-i}}{r^d} \\
&\qquad\leq
  \sum_{i=0}^{\floor{d/2}}\frac{d^i k^{d-i} \cdot r^i}{r^d}
+ \sum_{i=1}^{\ceil{d/2}-1} \frac{d^i k^i \cdot r^{d-i}}{r^d}
\qquad\leq
  \sum_{i=0}^{\floor{d/2}}\frac{\epsilon^{d-i}}{3^{d-i}d^{d-i}}
+ \sum_{i=1}^{\ceil{d/2}-1} \frac{\epsilon^i}{3^i} \\
&\qquad\leq
  \frac{\epsilon}{3} + \sum_{i=2}^{\ceil{d/2}-1} \frac{\epsilon^i}{3^i}
  + \floor{d/2} \cdot \frac{\epsilon^{\ceil{d/2}}}{3^{\ceil{d/2}}d^{\ceil{d/2}}}
\qquad\leq
  \frac{\epsilon}{3} + \frac{\epsilon}{3} \sum_{i=1}^{\infty} \frac{\epsilon^i}{3^i}
  + \frac{\epsilon^{\ceil{d/2}}}{3^{\ceil{d/2}}}
\leq \epsilon \,. \qedhere
\end{align*}
\end{proof}

It is a standard fact that for degree-$k$ polynomials, $M(1) \leq k$, and a
special case of a theorem of Warren bounds gives a bound for larger dimensions:
\begin{theorem}[\cite{War68}]\label{thm:warren}
Polynomial threshold functions $p : \ensuremath{\mathbb{R}}^d \to \{\pm 1\}$ of degree $k$ have
$M(n) \leq 6(2k)^n$.
\end{theorem}
Since $M(1) \leq \sqrt{24} k$ and $6(2k)^n \leq (\sqrt{24}k)^n$, for $n > 1$,
Lemma~\ref{lemma:bbs for low-components} gives us:
\begin{corollary}\label{cor:ptf bbs bound}
For $r \geq 3 \sqrt{24} dk/\epsilon$, $r^{-d} \cdot \mathsf{bbs}(\ensuremath{\mathcal{P}}_k,r) < \epsilon$.
\end{corollary}

\subsection{Application}

As was the case for halfspaces, our reduction of noise sensitivity on $[r]^d$ to
$\{\pm 1\}^d$ requires that the class $\ensuremath{\mathcal{P}}_k$ is invariant under linear
transformations:
\begin{proposition}\label{prop:linear transform ptfs}
For any $f \in \ensuremath{\mathcal{P}}_k$ and full-rank linear transformation $A \in \ensuremath{\mathbb{R}}^{d \times
d}$, $f \circ A \in \ensuremath{\mathcal{P}}_k$.
\end{proposition}
\begin{proof}
Let $f(x) = \sign(p(x))$ where $p$ is a degree-$k$ polynomial and let $c_q
\prod_{i=1}^d x_i^{q_i}$ be a term of $p$, where $c \in \ensuremath{\mathbb{R}}$ and $q \in
\ensuremath{\mathbb{Z}}_{\geq 0}^d$ such that $\sum_i q_i \leq k$.  Let $A_i \in \ensuremath{\mathbb{R}}^d$ be the
$i^\text{th}$ row of $A$. Then
\[
  \prod_{i=1}^d (Ax)_i^{q_i}
  = \prod_{i=1}^d \left(\sum_{j=1}^d A_{i,j}x_j\right)^{q_i}
  = p_q(x)
\]
where $p_q(x)$ is some polynomial of degree at most $\sum_{i=1}^d q_i \leq k$.
Then $p \circ A = \sum_q c_q p_q$ where $q$ ranges over $\ensuremath{\mathbb{Z}}_{\geq 0}$ with
$\sum_i q_i \leq k$, and each $p_q$ has degree at most $k$, so $p \circ A$ is a
degree-$k$ polynomial.
\end{proof}
The last ingredient we need is the following bound of Diakonikolas \emph{et
al.}~on the noise sensitivity:
\begin{theorem}[\cite{DHK+10}]\label{thm:ptf noise sensitivity}
Let $f : \{\pm 1\}^d \to \{\pm 1\}$ be a degree-$k$ PTF\@. Then for any $\delta \in
[0,1]$,
\begin{align*}
  \mathsf{ns}_{2,\delta}(f) &\leq O(\delta^{1/2^k}) \\
  \mathsf{ns}_{2,\delta}(f) &\leq 2^{O(k)} \cdot
\delta^{1/(4k+2)}\log(1/\delta) \,.
\end{align*}
\end{theorem}
Putting everything together, we obtain a bound that is polynomial in $d$ for any
fixed $k,\epsilon$, and which matches the result of Diakonikolas \emph{et
al.}~\cite{DHK+10} for the uniform distribution over $\{\pm 1\}^d$.

   
 
 
 

\thmptfs*

\begin{proof}
We prove the continuous case here; the finite case is proved in \cref{thm:finite algorithms}.

Let $r = \ceil{9dk/\epsilon}$, so that by Corollary~\ref{cor:ptf bbs bound},
condition 1 of Lemma~\ref{lemma:general algorithm} is satisfied. Due to
Proposition~\ref{prop:linear transform ptfs}, we may apply Theorem~\ref{thm:ptf
noise sensitivity} and Lemma~\ref{lemma:noise sensitivity reduction} to conclude
that for all $f \in \ensuremath{\mathcal{P}}_k$
\begin{align*}
\mathsf{ns}_{r,\delta}(f^\mathsf{block})
  &\leq O(\delta^{1/2^k}) \\
\mathsf{ns}_{r,\delta}(f^\mathsf{block})
  &\leq 2^{O(k)} \cdot \delta^{1/(4k+2)}\log(1/\delta) \,.
\end{align*}
In the first case, setting $\delta = O(\epsilon^{2^{k+1}})$ we get
$\mathsf{ns}_{r,\delta}(f^\mathsf{block}) < \epsilon^2/3$, so by Lemma~\ref{lemma:noise
sensitivity to polynomial regression} we get a set $\ensuremath{\mathcal{F}}$ of functions $[r]^d \to
\ensuremath{\mathbb{R}}$ of size $|\ensuremath{\mathcal{F}}| \leq (rd)^{O\left(\frac{1}{\epsilon^{2^{k+1}}}\right)}$
satisfying condition 2 of Lemma~\ref{lemma:general algorithm}. For $n =
\poly(|\ensuremath{\mathcal{F}}|,1/\epsilon)$, Lemma~\ref{lemma:general algorithm} implies an
algorithm with sample size
\[
  O(rd^2n^2\log(rd))
  = O\left(\frac{d^3k}{\epsilon}\log(dk/\epsilon)\right) \cdot
    \left(\frac{kd}{\epsilon}\right)^{O\left(\frac{1}{\epsilon^{2^{k+1}}}\right)}
\,.
\]
In the second case, setting $\delta =
O\left(\left(\frac{2^{O(k)}\log(2^k/\epsilon)}{\epsilon^2}\right)^{4k+2}\right)$,
we again obtain $\mathsf{ns}(f^\mathsf{block})_{r,\delta} \leq \epsilon^2/3$ and get
an algorithm with sample size
\[
  \left(\frac{kd}{\epsilon}\right)^{2^{O(k^2)}\left(\frac{\log(1/\epsilon)}{\epsilon^2}\right)^{4k+2}} \,.
\]
The final result is obtained by applying Lemma~\ref{lemma:brute force}.
\end{proof}

\section{Learning \& Testing \texorpdfstring{$k$}{k}-Alternating Functions}\label{section:k alternating}
A function $f : \ensuremath{\mathcal{X}} \to \{\pm 1\}$ on a partial order $\ensuremath{\mathcal{X}}$ is \emph{$k$-alternating}
if for every chain $x_1 < \dotsc < x_{k+2}$ there is $i \in [k+1]$ such that
$f(x_i) = f(x_{i+1})$. Monotone functions are examples of 1-alternating functions. We consider
$k$-alternating functions on $\ensuremath{\mathbb{R}}^d$ with the usual partial order: for $x,y \in
\ensuremath{\mathbb{R}}^d$ we say $x < y$ when $x_i \leq y_i$ for each $i \in [d]$ and $x \neq y$.
Once again, we must bound the block boundary size, which has been done already by
Canonne~\emph{et al.}. We include the proof because their work does not share
our definition of block boundary size, and because we use it in our short proof
of the monotonicity tester in Section~\ref{section:warm-up}.
\begin{lemma}[\cite{CGG+19}]\label{lemma:monotone block boundary}
The $r$-block boundary size of $k$-alternating functions is at most $kdr^{d-1}$.
\end{lemma}
\begin{proof}
Let $f$ be $k$-alternating, let $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to {[r]}^d$ be any block
partition and let $v_1, \dotsc, v_m$ be any chain in ${[r]}^d$. Suppose that
there are $k+1$ indices $i_1, \dotsc, i_{k+1}$ such that $f$ is not constant on
$\mathsf{block}^{-1}(v_{i_j})$. Then there is a set of points $x_1, \dotsc, x_{k+1}$
such that $x_j \in \mathsf{block}^{-1}(v_{i_j})$ and $x_j \neq x_{j+1}$ for each $j \in
[k]$. But since $v_{i_1} < \dotsm < v_{i_{k+1}}$, $x_1 < \dotsm < x_{k+1}$ also,
which contradicts the fact that $f$ is $k$-alternating. Then every chain in
${[r]}^d$ has at most $k$ non-constant blocks, and we may partition ${[r]}^d$
into at most $dr^{d-1}$ chains by taking the diagonals $v + \lambda \vec 1$
where $v$ is any vector satisfying $\exists i : v_i=1$ and $\lambda$ ranges over
all integers.
\end{proof}
Canonne \emph{et al.}~also use noise sensitivity bound to obtain a spanning set
$\ensuremath{\mathcal{F}}$; we quote their result.
\begin{lemma}[\cite{CGG+19}]\label{lemma:k-monotone grid basis}
There is a set $\ensuremath{\mathcal{F}}$ of functions ${[r]}^d \to \ensuremath{\mathbb{R}}$, with size
\[
|\ensuremath{\mathcal{F}}| \leq
\exp{O\left(\frac{k\sqrt{d}}{\epsilon^2} \log(rd/\epsilon)\right)} \,,
\]
such that for any $k$-alternating function $h : {[r]}^d \to \{\pm 1\}$, there is $g : {[r]}^d \to \ensuremath{\mathbb{R}}$
that is a linear combination of functions in $\ensuremath{\mathcal{F}}$ and $\Exu{x \sim {[r]}^d}{{(h(x)-g(x))}^2} \leq
\epsilon^2$.
\end{lemma}

\thmkalternating*
\begin{proof}
We prove the continuous case; for the finite case see \cref{thm:finite algorithms}.

Let $r = \ceil{dk/\epsilon}$ and let $\mathsf{block} : \ensuremath{\mathbb{R}}^d \to [r]^d$ be any $r$-block
partition. By Lemma~\ref{lemma:monotone block boundary},  the
first condition of Lemma~\ref{lemma:general algorithm} is satisfied. Now let $f
\in \ensuremath{\mathcal{H}}$ and consider $f^\mathsf{block}$. For any chain $v_1 < v_2 < \dotsm < v_m$ in
$[r]^d$, it must be $\mathsf{blockpoint}(v_1) < \mathsf{blockpoint}(v_2) < \dotsm <
\mathsf{blockpoint}(v_m)$ since every $x \in \mathsf{block}^{-1}(v_i), y \in \mathsf{block}^{-1}(v_j)$
satisfy $x < y$ when $v_i < v_j$; then $f$ alternates at most $k$ times on the
chain $\mathsf{blockpoint}(v_1) < \dotsm < \mathsf{blockpoint}(v_m)$ and, since $f^\mathsf{block}(v_i) =
f(\mathsf{blockpoint}(v_i))$, $f^\mathsf{block}$ is also $k$-alternating.  Therefore the set
$\ensuremath{\mathcal{F}}$ of functions given by Lemma~\ref{lemma:k-monotone grid basis} satisfies
condition 2 of Lemma~\ref{lemma:monotone block boundary}, and we have $n =
\poly(|\ensuremath{\mathcal{F}}|,1/\epsilon) =
\exp{O\left(\frac{k\sqrt{d}}{\epsilon^2}\log(rd/\epsilon)\right)}$. Applying
Lemma~\ref{lemma:general algorithm} gives an algorithm with sample complexity
\[
  O\left(rd^2n^2\log(rd)\right)
  = O\left(\frac{d^3k}{\epsilon} \log(dk/\epsilon) \cdot
	\left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k \sqrt d}{\epsilon^2}\right)}\right)
  = \left(\frac{dk}{\epsilon}\right)^{O\left(\frac{k \sqrt d}{\epsilon^2}\right)} \,.
\]
	The other sample complexity follows from Lemma~\ref{lemma:brute force}.
\end{proof}

\thmtestingkalternating*

\begin{proof}
The following argument is for the continuous case, but generalizes to the finite case using the
definitions in \cref{section:discrete distributions}.

Let $\ensuremath{\mathcal{H}}$ be the class of $k$-alternating functions.
Suppose there is a set $\ensuremath{\mathcal{K}} \subset \ensuremath{\mathcal{H}}$, known to the algorithm, that is a $(\tau/2)$-cover. Then,
taking a set $Q$ of $q=O(\tfrac{1}{\epsilon^2}\log |\ensuremath{\mathcal{K}}|)$ independent random samples from $\mu$ and
using Hoeffding's inequality,
\begin{align*}
  \Pru{Q}{\exists h \in \ensuremath{\mathcal{K}} : |\mathsf{dist}_Q(f,h)-\mathsf{dist}_\mu(f,h)| > \frac \tau 2 }
  &\leq |\ensuremath{\mathcal{K}}| \cdot \max_{h \in \ensuremath{\mathcal{K}}} \Pr{ |\mathsf{dist}_Q(f,h) - \mathsf{dist}_\mu(f,h)| > \frac \tau 2 } \\
  &\leq |\ensuremath{\mathcal{K}}| \cdot 2\exp{-\frac{q\tau^2}{2}} < 1/6 \,.
\end{align*}
Then the tester accepts if $\mathsf{dist}_Q(f,\ensuremath{\mathcal{K}}) < \epsilon_1 + \tau$ and rejects otherwise; we now
prove that this is correct with high probability. Assume that the above estimation is accurate,
which occurs with probability at least $5/6$.  If $\mathsf{dist}_\mu(f,\ensuremath{\mathcal{H}}) \leq \epsilon_1$ then
$\mathsf{dist}_\mu(f,\ensuremath{\mathcal{K}}) \leq \mathsf{dist}_\mu(f,h) + \mathsf{dist}_\mu(h,\ensuremath{\mathcal{K}}) \leq \epsilon_1 + \tau/2$. Then for $g \in
\ensuremath{\mathcal{K}}$ minimizing $\mathsf{dist}_\mu(f,g)$,
\[
  \mathsf{dist}_Q(f,\ensuremath{\mathcal{K}}) \leq \mathsf{dist}_Q(f,g) < \mathsf{dist}_\mu(f,g) + \frac \tau 2
  \leq \epsilon_1 + \tau \,,
\]
so $f$ is accepted. Now suppose that $f$ is accepted, so $\mathsf{dist}_Q(f,\ensuremath{\mathcal{K}}) < \epsilon_1 + \tau$. Then
\[
  \mathsf{dist}_\mu(f,\ensuremath{\mathcal{H}}) \leq \mathsf{dist}_\mu(f,g) \leq \mathsf{dist}_Q(f,g) + \frac \tau 2 < \epsilon_1 +
\frac{3}{2}\tau = \epsilon_1 + \frac{3}{4}(\epsilon_2-\epsilon_1) \leq \epsilon_2  \,.
\]
What remains is to show how the tester constructs such a cover $\ensuremath{\mathcal{K}}$.

Consider the learning algorithm of Theorem~\ref{thm:k-alternating} with error parameter $\tau/12$,
so $r = \ceil{12dk/\tau}$.  Let $X$ be the grid constructed by that algorithm and let $\mathsf{block} :
\ensuremath{\mathbb{R}}^d \to [r]^d$ be the induced $r$-block partition. We may assume that with probability at least
$5/6$, $\|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} < \tau/12$; suppose that this event occurs. The learner
then takes $m = \left(\frac{dk}{\tau}\right)^{O\left(\frac{k \sqrt d}{\tau^2}\right)}$ additional
samples to learn the class $\ensuremath{\mathcal{H}}^\mathsf{block}$ with domain $[r]^d$. For every $f \in \ensuremath{\mathcal{H}}$ the learner has
positive probability of outputting a function $h : [r]^d \to \{0,1\}$ with $\Pru{v}{h(v) \neq
f^\mathsf{block}(v)} < \tau/12$ (where $v$ is chosen from $\mathsf{block}(\mu)$). Let $\ensuremath{\mathcal{K}}'$ be the set of possible
outputs of the learner; then $\ensuremath{\mathcal{K}}'$ is a $(\tau/12)$-cover for $\ensuremath{\mathcal{H}}^\mathsf{block}$.  Construct a set
$\ensuremath{\mathcal{K}}^\mathsf{block}$ by choosing, for each $h \in \ensuremath{\mathcal{K}}'$, the nearest function $g \in \ensuremath{\mathcal{K}}$ with respect to
the distribution $\mathsf{block}(\mu)$. Then $\ensuremath{\mathcal{K}}^\mathsf{block}$ is a $(\tau/6)$-cover, since for any function
$f^\mathsf{block} \in \ensuremath{\mathcal{H}}^\mathsf{block}$, if $h \in \ensuremath{\mathcal{K}}'$ is the nearest output of the learner and $g \in
\ensuremath{\mathcal{K}}^\mathsf{block}$ is nearest $h$, then by the triangle inequality $f^\mathsf{block}$ has distance at most $\tau/6$
to $g$ with respect to $\mathsf{block}(\mu)$. Finally, construct a set $\ensuremath{\mathcal{K}} \subset \ensuremath{\mathcal{H}}$ by taking each
function $h \in \ensuremath{\mathcal{H}}$ such that $h^\mathsf{coarse}=h$ and $h^\mathsf{block} \in \ensuremath{\mathcal{K}}^\mathsf{block}$ (note that there exists
$h \in \ensuremath{\mathcal{H}}$ such that $h^\mathsf{coarse}=h$ since $h^\mathsf{coarse}$ is $k$-alternating when $h^\mathsf{block}$ is
$k$-alternating). Then $\ensuremath{\mathcal{K}}$ is a $(\tau/2)$-cover since for any $f \in \ensuremath{\mathcal{H}}$, when $h \in \ensuremath{\mathcal{K}}$
minimizes $\Pru{v \sim \mathsf{block}(\mu)}{f^\mathsf{block}(v) \neq h^\mathsf{block}}$,
\begin{align*}
  &\mathsf{dist}_\mu(f,\ensuremath{\mathcal{K}}) \\
    &\qquad\leq \mathsf{dist}_\mu(f,f^\mathsf{coarse}) + \mathsf{dist}_\mu(f^\mathsf{coarse}, \ensuremath{\mathcal{K}}) \\
    &\qquad\leq r^{-d}\cdot \mathsf{bbs}(\ensuremath{\mathcal{H}},r) + \Pru{v \sim \mathsf{block}(\mu)}{f^\mathsf{block}(v)\neq h^\mathsf{block}(v)}
      + 2 \|\mathsf{block}(\mu)-\mathsf{unif}([r]^d)\|_\mathsf{TV} \\
    &\qquad< \tau/6 + \tau/6 + 2\tau/12
    \leq \tau/2 \,.
\end{align*}
Now we bound the size of $\ensuremath{\mathcal{K}}^\mathsf{block}$. Since there are $m$ samples and each sample $v \sim
\mathsf{block}(\mu)$ is in $[r]^d$, labelled by $\{0,1\}$, there are at most $(r^d)^m 2^m$ possible sample
sequences, so at most $(2r^d)^m$ outputs of the learner (after constructing $X$), so $|\ensuremath{\mathcal{K}}^\mathsf{block}|
\leq (2r^d)^m$. Therefore, after constructing $X$, the tester may construct $\ensuremath{\mathcal{K}}^\mathsf{block}$ and run the
above estimation procedure, with $q = O\left(\frac{1}{\tau^2} dm \log r \right) =
\left(\frac{dk}{\tau}\right)^{O\left(\frac{k \sqrt d}{\tau^2}\right)}$.
\end{proof}

