\section{The price of inexact curvature}\label{sec:inexact}

The exact protocol uploads $p + p(p+1)/2$ numbers per worker in every derivative phase. Three cheaper variants are common in practice: a \emph{stale} Hessian, equal to the average of the local Hessians evaluated at the local MLEs and shipped once together with the pilot, after which every round costs $p$ numbers; a \emph{single-machine} Hessian evaluated at the current iterate on one worker, as in the surrogate-likelihood approach of \citet{jordan2019communication}; and a \emph{quantized} exact Hessian. The following perturbation theorem covers all three and inexact scores as well. Let $\vartheta$ be the current iterate, $e := \vartheta - \thetaN$, and let the coordinator compute $\tilde\vartheta := \vartheta - \widehat H^{-1}\widehat g$ with $\widehat g = g_N(\vartheta) + \delta_g$.

\begin{theorem}[Inexact Newton steps]\label{thm:inexact}
Let \cref{ass:lin,ass:bias,ass:newton} hold, $\vartheta \pto \theta_0$, $\norm{\widehat H - H_N(\thetaN)} = \op(\delta_N)$ with $\delta_N \to 0$ and $\norm{\widehat H^{-1}} = \op(1)$. Then
\begin{equation}\label{eq:inexact}
\norm{\tilde\vartheta - \thetaN} = \op\big(\norm{e}^2 + \delta_N\norm{e} + \norm{\delta_g}\big).
\end{equation}
With $q$ such steps from the order-$r$ pilot and a Hessian error $\delta_N$ at every step, $\norm{\iter{r}{q} - \thetaN} = \op(\norm{e_0}\delta_N^{\,q} + \norm{e_0}^{2^q} + \text{cross terms})$, and $\sqrt N(\iter{r}{q} - \thetaN) \pto 0$ provided $\sqrt N\,m^{-r}\delta_N^{\,q} \to 0$ together with the conditions of \cref{thm:frontier}. In particular:
\begin{enumerate}[label=(\alph*)]
\item (\emph{stale averaged local curvature}) under \cref{ass:third}, $\widehat H = K^{-1}\sum_k H_{D_k}(\thetahat_{D_k})$ has $\delta_N = m^{-1} + N^{-1/2}$, and the sufficient exponent becomes $\alpha = 1 - 1/(2(r+q))$ for $q \ge 1$;
\item (\emph{single-machine curvature}) $\widehat H = H_{D_1}(\vartheta)$ has $\delta_N = m^{-1/2}$ (no third-derivative condition needed), and the sufficient exponent becomes $\alpha = 1 - 1/(2r + q)$;
\item (\emph{relative quantization}) if the score and the Hessian are transmitted with relative precision $\varepsilon$ (every entry rounded to $b$ significant bits, $\varepsilon = 2^{-b}$), then \eqref{eq:inexact} holds with $\delta_N = \varepsilon$ and $\norm{\delta_g} = \op(\varepsilon\norm{e})$, so that one quantized step from the order-$r$ pilot is first-order equivalent to $\thetaN$ whenever $\sqrt N\,\varepsilon\, m^{-r} \to 0$ in addition to $K = o(N^{\alphafr{r}{1}})$. When $K \sim N^{\alpha}$ with $1 - 1/(2r) \le \alpha < \alphafr{r}{1}$, it suffices that
\begin{equation}\label{eq:bits}
b \;\ge\; \Big(\tfrac12 - r(1-\alpha)\Big)\log_2 N + \omega(1),
\end{equation}
and for $\alpha < 1 - 1/(2r)$ any fixed number of bits suffices (the pilot alone is already first-order equivalent).
\end{enumerate}
\end{theorem}

The proof (\cref{app:proofs}) is a matrix-perturbation argument around the integral form of the Newton remainder: $\tilde\vartheta - \thetaN = \widehat H^{-1}[\widehat H - \int_0^1 H_N(\thetaN + te)\,\dd t]\,e - \widehat H^{-1}\delta_g$, and the bracket is bounded by $\norm{\widehat H - H_N(\thetaN)} + \tfrac12\Lambda_N\norm{e}$. The theorem turns the qualitative statements in the literature---the $m^{-1/2}$ factor of \citet[Theorem~3.1]{jordan2019communication}, the $(\beta/\lambda)^2 \asymp m^{-1}$ contraction of averaged local Hessians in \citet[Theorem~2]{shamir2014communication} and \citet{fan2023communication}---into exponents. \Cref{tab:protocols} tabulates them with the communication they require. Case~(b) with $r = 1$ gives $\alpha = 1 - 1/(2+q) = (q+1)/(q+2)$, exactly the rounds frontier that \citet{fan2023communication} state for CEASE up to logarithms, and $q = 1$ gives the $2/3$ of \citet{jordan2019communication}; case~(a) with $(r,q) = (1,1)$ gives $3/4$, the regime of \citet{zhu2021least}. The stale variant has effective depth $r + q$ (linear in $q$) against $2^q r$ for exact curvature: with stale curvature a second round is worth one more local level, with exact curvature it is worth doubling the local order.

Case~(c) is, to our knowledge, new in this form. It says that the precision needed for the derivative uplink is governed by how far the pilot already is from $\thetaN$: a pilot of order $r$ with $K \sim N^\alpha$ has error $m^{-r} = N^{-r(1-\alpha)}$, and a relative error $\varepsilon$ in the step costs $\varepsilon N^{-r(1-\alpha)}$, which is negligible at the $N^{-1/2}$ scale iff \eqref{eq:bits}. For the half-block jackknife at $\alpha = 0.8$ the requirement is $0.1\log_2 N$ bits, i.e.\ two bits of mantissa at $N = 2^{20}$, whereas the plain average at the same $\alpha$ needs $0.3\log_2N = 6$ bits and is outside its own frontier ($3/4$) anyway. The mantissa bits multiply the $p(p+1)/2$ Hessian entries per worker and round, so the saving in bytes is $(64 - b)/64$ of the Hessian payload. The statement is asymptotic in the same sense as \cref{thm:frontier}, and the Monte Carlo ablation of \cref{sec:mc} shows at which $b$ the quantization error becomes visible at finite $N$.

\begin{table}[t]
\centering\small
\begin{threeparttable}
\caption{Protocol variants: local fits, synchronized phases, uplink per worker, and sufficient exponents.}\label{tab:protocols}
\begin{tabular}{@{}llccl@{}}
\toprule
Variant & Curvature used by the coordinator & Local fits & Uplink per worker (numbers) & Sufficient exponent $\alpha$ \\
\midrule
$(r,0)$ & none & $\sum_j s_j$ & $p$ & $1 - 1/(2r)$ \\
$(r,q)$ exact & aggregated $H_N(\theta)$ at each iterate & $\sum_j s_j$ & $p + q\,(p + p(p+1)/2)$ & $1 - 1/(2^{q+1}r)$ \\
$(r,q)$ stale & $K^{-1}\sum_k H_{D_k}(\thetahat_{D_k})$, shipped once & $\sum_j s_j$ & $p + p(p+1)/2 + q\,p$ & $1 - 1/(2(r+q))$ \\
$(r,q)$ single & $H_{D_1}(\theta)$ on worker 1 & $\sum_j s_j$ & $p + q\,p$ (+ none for curvature) & $1 - 1/(2r+q)$ \\
$(r,1)$ quantized & aggregated, $b$ mantissa bits & $\sum_j s_j$ & $p + (p + p(p+1)/2)\,b/64$ (in 64-bit units) & $1 - 1/(4r)$ if $b \ge (\tfrac12 - r(1-\alpha))\log_2 N + \omega(1)$ \\
AEE \citep{lin2011aggregated} & local Jacobians at local estimates & 1 & $p + p(p+1)/2$ & $< 1/4$ (their Thm 4.2) \\
CSL \citep{jordan2019communication}, $t$ rounds & machine 1, full surrogate & 1 & $t\,p$ & $1 - 1/(2 + t)$ from the average \\
exact pooling (exponential families) & sufficient statistic & 1 & $\dim(T)$ & any $K \le N$ \\
\bottomrule
\end{tabular}
\begin{tablenotes}\footnotesize
\item Downlink per worker: $qp$ numbers for every variant with $q \ge 1$. Headers, serialization and the pilot's validity flag are excluded; measured bytes appear in \cref{sec:bench}. Exponents are sufficient conditions from \cref{thm:frontier,thm:inexact}; the CSL and AEE rows are the cited authors' results translated to our notation.
\end{tablenotes}
\end{threeparttable}
\end{table}