\section{Bayesian inference in context}\label{sec:bayes}

This section shows that the Bayes and Gibbs in-context predictors of a local class are counting
problems, and that they are statistically efficient for every class with short descriptions.

\subsection{Algorithms}\label{sec:bayesalg}

Without noise, the posterior is uniform on the version space, and the posterior predictive is a ratio of
two version-space sizes. With noise, it is a ratio of two weighted sums, and two error profiles determine
both.

\begin{restatable}[Bayesian inference in context for local classes]{theorem}{thmbayesalg}\label{thm:bayesalg}
Let $\cH$ be $\kappa$-local with $N$-bit descriptions, let $S$ be a context of size $m$, and let $x$ be a
query.
\begin{enumerate}[label=(\alph*)]
\item\label{it:noiseless} \emph{Without noise.} If $\VS(S)\ne\emptyset$, then $p_S(x)$ and $\Bayes(S,x)$ can
be computed exactly and deterministically in time $\poly(N,m)\cdot2^\kappa\cdot T_\kappa(N)$, and the Gibbs
predictor can be run exactly in the same time, given uniform random integers. This is $\poly(m)\cdot2^{o(N)}$
when $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$.
\item\label{it:noisy} \emph{With noise.} Let $\eta=a/b$ for integers $0<a$, $2a<b$, and let
$s=\max\{4\kappa(m+1),m+2,\kappa^2\}$. Then $p_S(x)$ and $\Bayes(S,x)$ can be computed exactly in time
$\poly(N,m,\log b)\cdot2^{O(s/\sqrt{\log s})}$, and the Gibbs predictor can be run in the same time, exactly
given exact samples from explicitly given distributions on
$\{0,\dots,m\}$, and otherwise within statistical distance $\nu$ for any $\nu\ge2^{-\poly(N,m)}$. For
$m\ge\max\{\kappa,2\}$ the time is $\poly(N,m,\log b)\cdot2^{O(\kappa m/\sqrt{\log m})}$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
For~\ref{it:noiseless}, append the example $(x,1)$ to $S$ to obtain $S^+$. Then
$p_S(x)=|\VS(S^+)|/|\VS(S)|$, and \cref{fact:vs} computes both counts; Gibbs sampling is uniform sampling
from $\VS(S)$. For~\ref{it:noisy}, write $a_j$ and $b_j$ for the numbers of descriptions with $e_S(w)=j$ and
$h_w(x)=1$, respectively $h_w(x)=0$. The coefficient of $V^j$ is $a_j+b_j$ in $E_S$ and $a_j+b_{j-1}$ in
$E_{S^+}$, so the two profiles of \cref{fact:profile} determine all $a_j$ and $b_j$ recursively, starting
from $b_{-1}=0$. Then $p_S(x)=\sum_ja_j\mu^j/\sum_j(a_j+b_j)\mu^j$. Gibbs sampling is \cref{fact:expmech}
with $e^{-\lambda}=\mu$ (\cref{app:bayes}).
\end{proof}

The same reduction runs in the other direction: \cref{sec:hardness} turns $\#k$-SAT into exact Bayesian
inference in context. For the upper bound, any algorithm for $\#\kappa$-SAT can replace \cref{fact:vs}.

\begin{restatable}[Bayesian inference from counting]{corollary}{corfromcount}\label[corollary]{cor:fromcount}
If $\#\kappa$-SAT on $N$ variables with $M$ clauses can be solved in time $T(N,M)$, with $T$ nondecreasing,
then noiseless Bayesian inference in context for every $\kappa$-local class with $N$-bit descriptions takes
time $2T(N,(m+1)2^\kappa)+\poly(N,m)\cdot2^\kappa$ on consistent contexts of size $m$.
\end{restatable}

\begin{proof}[Proof sketch]
By \cref{fact:vscnf}, $\VS(S)$ and $\VS(S^+)$ are the solution sets of $\kappa$-CNFs with at most
$(m+1)2^\kappa$ clauses (\cref{app:bayes}).
\end{proof}

\subsection{The Bayes risk}\label{sec:risk}

The Bayes in-context predictor learns every class with short descriptions from few examples. The bound
needs no locality.

\begin{restatable}[Bayes risk]{theorem}{thmrisk}\label{thm:risk}
Let $\cH=\{h_w:w\in\{0,1\}^N\}$ be any class, $\cD$ any input distribution and $\eta\in[0,1/2)$ the noise
rate. Let $\Hb(\eta)=-\eta\log\eta-(1-\eta)\log(1-\eta)$, with $\Hb(0)=0$.
\begin{enumerate}[label=(\alph*)]
\item\label{it:mono} $R^*_{m+1}\le R^*_m$ for every $m\ge0$.
\item\label{it:bound} $R^*_m\le\eta+\dfrac{(1-2\eta)N}{(1-\Hb(\eta))(m+1)}$ for every $m\ge0$. In particular,
without noise $R^*_m\le N/(m+1)$.
\item\label{it:gibbs} Without noise, the Gibbs predictor has risk at most $2R^*_m\le2N/(m+1)$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
For~\ref{it:mono}, fix the query. Its posterior predictive $\hat p$ of \eqref{eq:phat} is a martingale as
examples are added to the context, and the Bayes error $\min\{\hat p,1-\hat p\}$ is a concave function of
$\hat p$; Jensen's inequality gives the claim. For~\ref{it:bound} without noise, run the Bayes predictor on
the examples of an episode in order. Each mistake leaves at most half of the version space, which starts with
$2^N$ elements and always contains the task, so every episode has at most $N$ mistakes among its first $m+1$
rounds. The expected number of these mistakes is $\sum_{t=0}^{m}R^*_t\ge(m+1)R^*_m$ by~\ref{it:mono}. With
noise, the log-loss regret of the Bayes mixture against the task is at most $N$ bits, so the expected
Kullback--Leibler divergences between the true label distribution and the predictive sum to at most $N$. A
mistake of $\Bayes$ against $h_w(x)$ costs at least $1-\Hb(\eta)$ bits of divergence and adds $1-2\eta$ to the
error. For~\ref{it:gibbs}, the Gibbs error at a query is $2p(1-p)\le2\min\{p,1-p\}$ (\cref{app:bayes}).
\end{proof}

Without noise, the halving argument behind~\ref{it:bound} is that of~\cite{BF72,Lit88}, with posterior
weights, and bounds of this kind on the Bayes and Gibbs learning curves go back to Haussler, Kearns and
Schapire~\cite{HKS94}. So the Bayes in-context predictor has risk $\eps$ from $N/\eps$ examples, for every
class with $N$-bit descriptions and every input distribution, and \cref{thm:bayesalg} computes it in time
$2^{o(N)}$ for local classes of small locality. The next section shows that, up to the rate of SAT, this
computation cannot be avoided.