\section{Efficient in-context learning}\label{sec:efficient}

This section shows that learning in context is cheap for local classes when Bayes-optimality is not
required. For the families of the lower bounds a halfspace suffices, and every local class is a linear
class over local Fourier features.

\subsection{The hard families are halfspaces}\label{sec:lp}

\begin{restatable}[Halfspace forms]{proposition}{prophalfspace}\label[proposition]{prop:halfspace}
Let $\sigma\in\{\pm1\}^n$ and $x\in\{-1,0,1\}^n$ with $r=|\supp(x)|$. Then
$h^{\BP}_\sigma(x)=\ind[\langle\sigma,x\rangle\ge0]$ and $h^{\LD}_\sigma(x)=\ind[\langle\sigma,x\rangle+r-2\ge0]$.
If $h^{\BP}_\sigma(x)=0$ then $\langle\sigma,x\rangle\le-1$, and if $h^{\LD}_\sigma(x)=0$ then
$\langle\sigma,x\rangle+r-2=-2$.
\end{restatable}

\begin{proof}[Proof sketch]
The first form is the definition, and $\langle\sigma,x\rangle$ is an integer. For literal disjunctions, if
$t$ coordinates of $\supp(x)$ agree with $\sigma$, then $\langle\sigma,x\rangle=t-(r-t)$, so $t\ge1$ if and
only if $\langle\sigma,x\rangle+r-2\ge0$, and $t=0$ gives $-2$ (\cref{app:efficient}).
\end{proof}

Let $c(x)=0$ for binarized perceptrons and $c(x)=|\supp(x)|-2$ for literal disjunctions. The in-context
learner $\Alp$ solves the linear program
\begin{equation}\label{eq:lp}
\langle v,x_i\rangle+c(x_i)\ge0\ \text{ if }y_i=1,\qquad\langle v,x_i\rangle+c(x_i)\le-1\ \text{ if }y_i=0
\qquad(i\le m)
\end{equation}
over $v\in\R^n$ and predicts $\ind[\langle v,x\rangle+c(x)\ge0]$; if the program is infeasible it predicts
$0$.

\begin{restatable}[Linear programming in context]{theorem}{thmlp}\label{thm:lp}
For every $k\le n$, the in-context learner $\Alp$ for $\BP_k$ and for $\LD_k$ runs in time $\poly(n,m)$ and is
$(\eps,\delta)$-PAC from $\mVC(n+1,\eps,\delta)$ examples, which is $O((n\log(1/\eps)+\log(1/\delta))/\eps)$. Its
risk in every noiseless episode, for every input distribution, is $O(n\log m/m)$.
\end{restatable}

\begin{proof}[Proof sketch]
If the context is consistent with $\sigma$, then $v=\sigma$ is feasible by \cref{prop:halfspace}, and every
feasible $v$ classifies the context correctly. The classifiers
$x\mapsto\ind[\langle v,x\rangle+c(x)\ge0]$ are homogeneous halfspaces on $(x,c(x))\in\R^{n+1}$ with last
coefficient $1$, a class of VC dimension at most $n+1$, so \cref{fact:samples}(a) applies. For the risk, take
$\eps=C_B(n+2)\log(2m)/m$ and $\delta=1/m$ (\cref{app:efficient}).
\end{proof}

On the families of \cref{thm:hardness}\ref{it:seth}, the comparison is now complete.

\begin{corollary}[The price of Bayes-optimality]\label[corollary]{cor:price}
Assume \cref{hyp:cnfseth}, let $\gamma\in(0,1)$, and let $K$ and $c_\gamma$ be as in
\cref{thm:hardness}\ref{it:seth}. Consider $\BP_{\lceil K\log N\rceil}$ in dimension $N$.
\begin{enumerate}[label=(\alph*)]
\item The learner $\Alp$ runs in polynomial time and has risk $O(N\log m/m)$ in every noiseless episode.
\item The Bayes predictor has risk at most $N/(m+1)$ (\cref{thm:risk}).
\item No randomized algorithm computes the Bayes predictor, or a number within $1/4$ of the posterior
predictive, on all consistent contexts of size at most $N^{c_\gamma}$ in time $O(2^{(1-\gamma)N})$.
\end{enumerate}
The same holds for $\LD_{\lceil K\log N\rceil}$, and, with $\lenETH{C}$, time $2^{N/(\log N)^{C+\theta}}$ and contexts
of at most $36N^2$ examples in~(c), for $\LD_3$.
\end{corollary}

So for these families a polynomial-time in-context learner matches the sample efficiency of the Bayes
predictor up to a factor $\log m$, while the Bayes predictor itself costs time $2^{(1-\gamma)N}$. In the
language of~\cite{Li26}, the locality principle governs proper learning and Bayesian computation, but not
improper learning: proper PAC learning of $\BP_{\lceil K\log N\rceil}$ at inverse-polynomial accuracy needs time
$2^{(1-\gamma)N}$ under CNF-SETH~\cite[Theorem~3.8]{Li26}, and $\Alp$ is improper.

\subsection{Local classes are linear}\label{sec:linear}

For a general local class no halfspace in the input coordinates need exist, but a linear form in local
Fourier features always does. For $T\subseteq[N]$ let $\chi_T(w)=\prod_{i\in T}(-1)^{w_i}$, and let
$D_\kappa=D_\kappa(N)=\sum_{j=0}^{\kappa}\binom Nj$.

\begin{restatable}[Local Fourier features]{theorem}{thmlinear}\label{thm:linear}
Let $\cH$ be $\kappa$-local with $N$-bit descriptions. For $x\in\cX$ and $T\subseteq[N]$ with $|T|\le\kappa$,
let
\[
\psi_T(x)=2^{-|R(x)|}\sum_{\beta\in\{0,1\}^{R(x)}}f_x(\beta)\,\chi_T(\beta)\quad\text{if }T\subseteq R(x),
\qquad\psi_T(x)=0\quad\text{otherwise},
\]
and let $\Psi(x)=(\psi_T(x))_{|T|\le\kappa}$ and $\Phi(w)=(\chi_T(w))_{|T|\le\kappa}$, vectors of dimension
$D_\kappa$. Then $h_w(x)=\langle\Phi(w),\Psi(x)\rangle$ for all $w$ and $x$. The vector $\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$.
For $1\le\kappa\le N$, $D_\kappa\le(eN/\kappa)^\kappa$.
\end{restatable}

\begin{proof}[Proof sketch]
This is the Fourier expansion of $f_x$ on the cube $\{0,1\}^{R(x)}$~\cite{ODo14}, and
$\chi_T(w|_{R(x)})=\chi_T(w)$ for $T\subseteq R(x)$. The coefficients come from $2^{|R(x)|}$ evaluations of
$f_x$ and a fast Walsh--Hadamard transform (\cref{app:efficient}).
\end{proof}

The learner $\Alin$ solves the linear system $\langle v,\Psi(x_i)\rangle=y_i$ ($i\le m$) over $\Q$ by Gaussian
elimination and predicts $\ind[\langle v,\Psi(x)\rangle\ge1/2]$; if the system has no solution it predicts
$0$. The learner $\Aone$ minimizes $\sum_{i\le m}|\langle v,\Psi(x_i)\rangle-y_i|$ over $v\in\R^{D_\kappa}$ by
linear programming, then chooses $\theta\in[0,1]$ to minimize the number of errors of
$x\mapsto\ind[\langle v,\Psi(x)\rangle\ge\theta]$ on the context, and predicts with that classifier. This is the
$\ell_1$ regression of~\cite{KKMS08}.

\begin{restatable}[Regression in context]{theorem}{thmregression}\label{thm:regression}
Let $\cH$ be $\kappa$-local with $N$-bit descriptions.
\begin{enumerate}[label=(\alph*)]
\item\label{it:alin} $\Alin$ is $(\eps,\delta)$-PAC from $\mVC(D_\kappa+1,\eps,\delta)$ examples.
\item\label{it:aone} $\Aone$ is $(\eps,\delta)$-agnostic from $\mUC(D_\kappa+1,\eps,\delta)$ examples. In an episode
with noise rate $\eta$, its risk is at most $\eta+\eps+\delta$.
\item Both run in time $\poly(N,m,D_\kappa)\cdot2^\kappa$. This is polynomial for constant $\kappa$, it is
$N^{O(\log N)}$ for $\kappa=O(\log N)$, and it is $2^{o(N)}$ times a polynomial in $m$ whenever
$\kappa\log(eN/\kappa)=o(N)$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
For~\ref{it:alin}, $v=\Phi(w)$ solves the system, every solution is consistent with the context, and the
thresholded linear forms over $\Psi$ have VC dimension at most $D_\kappa+1$. For~\ref{it:aone}, for a
threshold $\theta$ uniform in $[0,1]$ the expected error of $\ind[z\ge\theta]$ against $y\in\{0,1\}$ is at
most $|z-y|$, so the chosen classifier has at most as many errors on the context as the best $h_w$, whose
linear form $\Phi(w)$ is feasible for the regression. Uniform convergence over the thresholded linear forms,
which contain every $h_w$, finishes the proof (\cref{app:efficient}).
\end{proof}

\begin{remark}[Improper learning of local classes]\label[remark]{rem:improper}
\Cref{thm:regression} uses no algorithm for SAT. Improper learning of local classes was polynomial at
constant locality before the refutation of ETH, and it stays quasi-polynomial at logarithmic locality, where
proper learning needs time $2^{(1-\gamma)N}$ under CNF-SETH~\cite{Li26}. From below, parities on a fixed set of
$\kappa$ description bits form a $\kappa$-local class, and agnostic learning them under uniform inputs with
constant noise rate is learning parity with noise on $\kappa$ bits. The best known algorithm for it runs in
time $2^{O(\kappa/\log\kappa)}$~\cite{BKW03}. If no algorithm is faster than $2^{\Omega(\kappa/\log\kappa)}$, then
for $\kappa=N^{\Omega(1)}$ the time of improper agnostic learning of $\kappa$-local classes lies between
$2^{\Omega(\kappa/\log\kappa)}$ and $N^{O(\kappa)}=2^{O(\kappa\log N)}$, so its exponent is $\kappa$ up to
polylogarithmic factors. Improper learning is governed by the locality itself, proper learning and Bayesian
inference by the rate of $\kappa$-SAT on $N$ variables.
\end{remark}

The price of these learners is in the examples: $\Alin$ needs about $D_\kappa\approx N^\kappa$ of them, where the
Bayes predictor needs $N$. \Cref{sec:average} shows that for random local functions some such price is
unavoidable for every efficient learner.