papers/hanzo-aso/sections/06-convergence-analysis.tex

\section{Convergence Analysis}

\label{sec:convergence}

\subsection{Posterior Consistency}

We now prove that the ASO posterior converges to the Bayes-optimal predictor as
the number of experiential priors grows.

\begin{theorem}[ASO Posterior Consistency]
\label{thm:consistency}
Let $\pi^*$ be the Bayes-optimal predictor for task distribution $\mathcal{D}$.
Suppose experiential priors $\{\phi_m\}_{m=1}^M$ are drawn i.i.d.\ from a prior
generation process with quality $q_m > 0.5 + \delta$ for some $\delta > 0$.
Then the ASO posterior converges in KL divergence:
\begin{equation}
    \KL(\pi^* \| \pi_{\text{ASO}}^{(M)}) \xrightarrow{M \to \infty} 0
    \quad \text{almost surely}.
\end{equation}
\end{theorem}

\begin{proof}[Proof sketch]
The proof proceeds in three steps:

\textit{Step 1.} Each prior $\phi_m$ with quality $q_m > 0.5 + \delta$
contributes $\eta_m = \log(q_m / (1-q_m)) > 2\delta + O(\delta^2)$ to the
log-odds of the correct token at each position.

\textit{Step 2.} By the strong law of large numbers, the average contribution
of $M$ independent priors concentrates around $\mathbb{E}[\eta_m] > 2\delta$:
\begin{equation}
    \frac{1}{M} \sum_{m=1}^M \eta_m \log \frac{\phi_m(v^*)}{1 - \phi_m(v^*)}
    \xrightarrow{a.s.} \mathbb{E}\left[\eta \log \frac{q}{1-q}\right] > 0,
\end{equation}
where $v^*$ is the Bayes-optimal token.

\textit{Step 3.} The unnormalized log-probability of the correct token grows
linearly with $M$, while the log-probability of any incorrect token remains
bounded. After normalization, this implies $\pi_{\text{ASO}}^{(M)}(v^*) \to 1$,
yielding $\KL(\pi^* \| \pi_{\text{ASO}}^{(M)}) \to 0$.
\end{proof}

\subsection{Finite-Sample Convergence Rate}

\begin{theorem}[Convergence Rate]
\label{thm:rate}
Under the conditions of Theorem~\ref{thm:consistency}, for any $\varepsilon > 0$:
\begin{equation}
    P\left(\KL(\pi^* \| \pi_{\text{ASO}}^{(M)}) > \varepsilon\right)
    \leq 2V \exp\left(-\frac{M \delta^2}{2}\right),
\end{equation}
where $V = |\mathcal{V}|$ is the vocabulary size.
\end{theorem}

\begin{proof}
Apply Hoeffding's inequality to the sum of bounded log-odds contributions, then
take a union bound over the vocabulary. The exponential decay in $M$ ensures
rapid convergence even for large vocabularies.
\end{proof}

\begin{remark}
For typical values ($V = 32{,}000$, $\delta = 0.1$), achieving
$\varepsilon$-convergence with probability $1 - 10^{-6}$ requires approximately
$M \geq 2(\ln(2V) + 6\ln 10) / \delta^2 \approx 3{,}800$ priors. In practice,
convergence is much faster because priors are not worst-case binary classifiers
but informative structured factors.
\end{remark}

\subsection{Convergence Under 1-Bit Compression}

\begin{corollary}
The convergence guarantee of Theorem~\ref{thm:consistency} holds under 1-bit
compression provided the quality scores satisfy $q_m > 0.5 + \delta'$ where
$\delta' = \delta + O(\sigma / \sqrt{|\mathcal{V}_m|})$ accounts for the
additional noise from quantization (Lemma~\ref{lem:quant-error}).
\end{corollary}

% ============================================================================
% 7. COST ANALYSIS
% ============================================================================