\section{Proofs for Section~\ref{sec:efficient}}\label{app:efficient}

\subsection{Halfspaces in context}

\prophalfspace*

\begin{proof}[Proof of \cref{prop:halfspace}]
\begin{steps}
\step{1}{1} The statements for $\BP$ hold.
\pf $h^{\BP}_\sigma(x)=\ind[\langle\sigma,x\rangle\ge0]$ is the definition, and $\langle\sigma,x\rangle$ is an
integer, so it is at most $-1$ when it is negative.
\step{1}{2} \Let $t$ be the number of $i\in\supp(x)$ with $x_i=\sigma_i$. Then $\langle\sigma,x\rangle=2t-r$.
\pf Each $i\in\supp(x)$ contributes $\sigma_ix_i=+1$ if $x_i=\sigma_i$ and $-1$ otherwise.
\qedstep{1}{3}
\pf By definition $h^{\LD}_\sigma(x)=\ind[t\ge1]$. By \sref{1}{2}, $t\ge1$ if and only if
$\langle\sigma,x\rangle+r-2=2t-2\ge0$, and $t=0$ gives $-2$.
\end{steps}
\end{proof}

\thmlp*

\begin{proof}[Proof of \cref{thm:lp}]
\begin{steps}
\step{1}{1} If the context is consistent with $\sigma$, then $v=\sigma$ satisfies \eqref{eq:lp}.
\pf By \cref{prop:halfspace}: a positive example has $\langle\sigma,x_i\rangle+c(x_i)\ge0$, and a negative one has
$\langle\sigma,x_i\rangle\le-1$ with $c=0$ for $\BP$, and $\langle\sigma,x_i\rangle+c(x_i)=-2$ for $\LD$.
\step{1}{2} Every solution $v$ of \eqref{eq:lp} classifies every example of the context correctly.
\pf Positive examples get value at least $0$ and negative ones at most $-1<0$.
\step{1}{3} \Let $\mathcal G=\{x\mapsto\ind[\langle v,x\rangle+c(x)\ge0]:v\in\R^n\}$. It contains every
$h_\sigma$ and has VC dimension at most $n+1$.
\pf It contains $h_\sigma$ by \cref{prop:halfspace}. Every element is $x\mapsto\ind[\langle(v,1),(x,c(x))\rangle\ge0]$,
the restriction of a homogeneous halfspace in $\R^{n+1}$ to the image of $x\mapsto(x,c(x))$, and homogeneous
halfspaces in $\R^{n+1}$ have VC dimension $n+1$.
\step{1}{4} $\Alp$ runs in time $\poly(n,m)$.
\pf \eqref{eq:lp} is a linear program with $n$ variables and $m$ constraints whose coefficients are in
$\{-1,0,1\}$ and whose right-hand sides are integers of absolute value at most $n+2$. Linear programming in
polynomial time decides feasibility and finds a rational solution.
\step{1}{5} $\Alp$ is $(\eps,\delta)$-PAC from $\mVC(n+1,\eps,\delta)$ examples.
\pf In the realizable case, \sref{1}{1} and \sref{1}{2} show that the output is an element of $\mathcal G$
consistent with the context. Apply \cref{fact:samples}(a) with \sref{1}{3}.
\qedstep{1}{6}
\pf For the risk, let $\eps_m=C_B(n+2)\log(2m)/m$ and $\delta_m=1/m$. If $\eps_m\ge1$ there is nothing to prove.
Otherwise $\eps_m\ge1/m$, so $\log(2/\eps_m)\le\log(2m)$ and $\mVC(n+1,\eps_m,\delta_m)\le C_B(n+2)\log(2m)/\eps_m=m$.
By \sref{1}{5} the risk is at most $\eps_m+\delta_m=O(n\log m/m)$.
\end{steps}
\end{proof}

\subsection{Local Fourier features and regression}

\thmlinear*

\begin{proof}[Proof of \cref{thm:linear}]
\begin{steps}
\step{1}{1} For every $x$ and every $\beta\in\{0,1\}^{R(x)}$,
$f_x(\beta)=\sum_{T\subseteq R(x)}\psi_T(x)\chi_T(\beta)$.
\pf This is the Fourier expansion of a function on $\{0,1\}^{R(x)}$~\cite[Chapter~1]{ODo14}: the characters
$\chi_T$, $T\subseteq R(x)$, are orthonormal for the uniform measure, and $\psi_T(x)$ is the coefficient of
$\chi_T$.
\step{1}{2} $h_w(x)=\langle\Phi(w),\Psi(x)\rangle$.
\pf For $T\subseteq R(x)$ we have $\chi_T(w|_{R(x)})=\chi_T(w)$. So by \sref{1}{1}, $h_w(x)=f_x(w|_{R(x)})$ equals
$\sum_{T\subseteq R(x)}\psi_T(x)\chi_T(w)$. Every $T\subseteq R(x)$ has $|T|\le\kappa$, and
$\psi_T(x)=0$ for the other $T$ with $|T|\le\kappa$.
\step{1}{3} $\Psi(x)$ has at most $2^{|R(x)|}$ nonzero entries, all in $2^{-\kappa}\Z$, and it can be computed in
time $\poly(N,|x|)\cdot\kappa2^\kappa$.
\pf Only $T\subseteq R(x)$ give nonzero entries. Each entry is $2^{-|R(x)|}$ times an integer. Compute $R(x)$, the
$2^{|R(x)|}$ values of $f_x$, each in time $\poly(N,|x|)$, and the Walsh--Hadamard transform of the value table
in $O(|R(x)|2^{|R(x)|})$ operations.
\qedstep{1}{4}
\pf For $1\le\kappa\le N$ and $j\le\kappa$ we have $(\kappa/N)^\kappa\le(\kappa/N)^j$, so
$(\kappa/N)^\kappa\sum_{j\le\kappa}\binom Nj\le\sum_{j\le N}\binom Nj(\kappa/N)^j=(1+\kappa/N)^N\le e^\kappa$.
\end{steps}
\end{proof}

\thmregression*

\begin{proof}[Proof of \cref{thm:regression}]
\begin{steps}
\step{1}{1} \Let $\mathcal G_\Psi=\{x\mapsto\ind[\langle v,\Psi(x)\rangle\ge\theta]:v\in\R^{D_\kappa},\theta\in\R\}$.
It has VC dimension at most $D_\kappa+1$, and it contains every $h_w$.
\pf Its elements are affine halfspaces in $\R^{D_\kappa}$ composed with $\Psi$. By \cref{thm:linear},
$h_w(x)=\langle\Phi(w),\Psi(x)\rangle\in\{0,1\}$, so $h_w(x)=\ind[\langle\Phi(w),\Psi(x)\rangle\ge1/2]$.

\step{1}{2} Part~\ref{it:alin} holds.
\pf In the realizable case $v=\Phi(w)$ solves the system, so Gaussian elimination over $\Q$ finds a solution
$v$. Every solution has $\langle v,\Psi(x_i)\rangle=y_i\in\{0,1\}$, so the output
$\ind[\langle v,\Psi(\cdot)\rangle\ge1/2]\in\mathcal G_\Psi$ is consistent with the context. Apply
\cref{fact:samples}(a) with \sref{1}{1}.

\step{1}{3} Part~\ref{it:aone} holds.
\begin{steps}
\step{2}{1} \Let $\cD'$ be a distribution on $\cX\times\{0,1\}$, let $w^*$ minimize the error of $h_w$ under
$\cD'$, and let $\hat v$ be the regression solution. Then
$\sum_i|\langle\hat v,\Psi(x_i)\rangle-y_i|\le\sum_i[h_{w^*}(x_i)\ne y_i]$.
\pf $\Phi(w^*)$ is a feasible point with $|\langle\Phi(w^*),\Psi(x_i)\rangle-y_i|=[h_{w^*}(x_i)\ne y_i]$, by
\cref{thm:linear}.
\step{2}{2} Let $z\in\R$, $y\in\{0,1\}$ and $\bar z=\min\{\max\{z,0\},1\}$. If $\theta$ is uniform in $[0,1]$,
then $\Pr_\theta[\ind[z\ge\theta]\ne y]=|\bar z-y|\le|z-y|$.
\pf If $y=1$, the error event is $\theta>z$; if $y=0$, it is $\theta\le z$.
\step{2}{3} The classifier $g$ chosen by $\Aone$ makes at most as many errors on the context as $h_{w^*}$.
\pf By \sref{2}{2} and \sref{2}{1}, the average over $\theta\in[0,1]$ of the number of errors of
$\ind[\langle\hat v,\Psi(\cdot)\rangle\ge\theta]$ is at most the number of errors of $h_{w^*}$, so some $\theta$
achieves at most that number. The number of errors is a step function of $\theta$ that changes only at the
values $\langle\hat v,\Psi(x_i)\rangle$, and on each piece its value is attained at the right end of the piece,
at $0$ or at $1$; so the minimum over $[0,1]$ is attained at one of at most $m+2$ candidates, which $\Aone$ tries.
\step{2}{4} With probability at least $1-\delta$, $g$ has error at most $\opt+\eps$ under $\cD'$.
\pf By \cref{fact:samples}(b) and \sref{1}{1}, with probability at least $1-\delta$ every element of
$\mathcal G_\Psi$, in particular $g$ and $h_{w^*}$, has empirical error within $\eps/2$ of its error. Then the
error of $g$ is at most its empirical error plus $\eps/2$, which by \sref{2}{3} is at most the empirical error of
$h_{w^*}$ plus $\eps/2$, which is at most $\opt+\eps$.
\qedstep{2}{5}
\pf For an episode with noise rate $\eta$ and a fixed task $w$, the examples are independent draws from the
distribution of $(x,h_w(x)\oplus\xi)$, under which $h_w$ has error $\eta$, so $\opt\le\eta$, and the query with its
target is one more draw. By \sref{2}{4} the risk is at most $\eta+\eps+\delta$.
\end{steps}

\step{1}{4} Part~(c) holds.
\pf Computing $\Psi(x_1),\dots,\Psi(x_m)$ takes time $m\cdot\poly(N)\cdot\kappa2^\kappa$ by \cref{thm:linear}.
Gaussian elimination over $\Q$ and linear programming with $D_\kappa+m$ variables and $O(m)$ constraints, with
entries in $2^{-\kappa}\Z$ of polynomial size, take time $\poly(D_\kappa,m)$, and the threshold search takes
time $\poly(m,D_\kappa)$. Since $D_\kappa\le(eN/\kappa)^\kappa=2^{\kappa\log(eN/\kappa)}$, this is polynomial for
constant $\kappa$, $N^{O(\log N)}$ for $\kappa=O(\log N)$, and $2^{o(N)}\poly(m)$ when $\kappa\log(eN/\kappa)=o(N)$,
since then also $2^\kappa=2^{o(N)}$.

\qedstep{1}{5}
\end{steps}
\end{proof}