SPB Git

spb/wp28_uqo

Public
7.3 KB · 35 lines latex
1\section{Introduction}\label{sec:intro}23When $N$ observations are stored on $K$ machines, the centralized maximum likelihood estimator (MLE) $\thetaN$ is the natural benchmark: under regularity it attains the inverse Fisher information as asymptotic variance, but computing it requires either moving the data or iterating many synchronized passes over the network. The simplest distributed alternative fits the model on each block of $m = N/K$ observations and averages the $K$ local estimates. Averaging reduces variance but not the $O(1/m)$ bias of a nonlinear local estimator, so the average is first-order equivalent to $\thetaN$ only when $K = o(N^{1/2})$ \citep{zhang2013communication,battey2018distributed,rosenblatt2016optimality}. Two ideas relax this barrier. One is \emph{local}: debias each local estimate before averaging, by subsampling \citep{zhang2013communication}, by an analytic bias formula \citep{gu2023heterogeneity,yin2022newton} or by a jackknife \citep{wu2023subsampling}. The other is \emph{global}: broadcast the average and add one Newton step computed from aggregated scores and Hessians \citep{huang2019distributed}, or several rounds of gradient-only surrogate updates \citep{jordan2019communication,fan2023communication}. Each idea has its own cost: a local correction multiplies the number of local fits, a global correction adds a synchronization round and, for dense Hessians, an uplink of order $p^2$ numbers per worker.45This paper studies the two ideas jointly. Each worker computes the MLE on its block and on nested sub-blocks of sizes $m/s_2, \dots, m/s_r$, combines them with Richardson-type weights that cancel the first $r-1$ terms of the bias expansion while preserving the first-order influence function exactly, and uploads the corrected estimate. The coordinator averages, broadcasts the average and applies $q$ Newton corrections from aggregated derivatives. Our question is quantitative: for fixed parameter dimension $p$, how fast may $K$ grow with $N$ while the resulting estimator remains first-order equivalent to $\thetaN$, how does the answer depend on $(r,q)$, when is the answer sharp, and what happens when the curvature used by the coordinator is inexact, stale or quantized?67\paragraph{Contributions.}8\begin{enumerate}[leftmargin=1.4em]9\item \emph{A joint order--round frontier} (\cref{thm:frontier}). Under a uniform stochastic expansion with a bias expansion of order $r$ and local Newton regularity, first-order equivalence to $\thetaN$ holds whenever10\begin{equation}\label{eq:frontier-intro}11K = o\big(N^{\alphafr{r}{q}}\big), \qquad \alphafr{r}{q} = 1 - \frac{1}{2^{\,q+1}\, r}.12\end{equation}13The exponent depends on $(r,q)$ only through the \emph{effective depth} $D = 2^{q} r$, so that doubling the local order and adding one synchronization round are exchangeable. The half-block jackknife with one Newton step gives $K = o(N^{7/8})$; the plain average with one step gives $3/4$; the quarter-block extrapolation with one step gives $11/12$. The proof keeps the centered random remainder of the local corrections, of order $(m\sqrt{K})^{-1}$, which cannot be dropped even though its mean vanishes.14\item \emph{Exact analysis and sharpness} (\cref{thm:exponential}). In the exponential model we derive the exact bias and variance of the corrected local estimators, an exact Newton error identity, the basin of attraction of the Newton map, and the boundary behaviour: if $K / N^{\alphafr{r}{q}} \to c \in (0,\infty)$ then15\begin{equation}\label{eq:boundary-intro}16\sqrt{N}\,\big(\iter{r}{q} - \thetaN\big) \;\pto\; -\theta_0\,\big(\betar\, c^{\,r}\big)^{2^q}, \qquad q \ge 1,17\end{equation}18where $\betar$ is an explicit rational constant ($\beta_2 = -2$, so that the half-block jackknife with one step has the limiting shift $-4\theta_0 c^4$), and the estimator is not even $\sqrt{N}$-close to $\thetaN$ when $K/N^{\alphafr{r}{q}} \to \infty$. The sufficient exponent is therefore necessary for this construction.19\item \emph{The price of inexact curvature} (\cref{thm:inexact}). If the Newton step uses a Hessian within $\delta_N$ of $H_N(\thetaN)$ in operator norm, the admissible exponent changes in a computable way:20\begin{equation}\label{eq:inexact-intro}21\alpha = 1 - \frac{1}{2(r+q)} \ \text{(stale averaged local Hessians)}, \qquad22\alpha = 1 - \frac{1}{2r+q} \ \text{(single-machine Hessian)},23\end{equation}24the second of which reproduces, for $r = 1$, the $(t+1)/(t+2)$ rounds frontier of \citet{fan2023communication} and the $2/3$ exponent of \citet{jordan2019communication}. Relative quantization of the transmitted score and Hessian to $b$ bits costs nothing asymptotically once25\begin{equation}\label{eq:bits-intro}26b \;\ge\; \Big(\tfrac12 - r\,(1-\alpha)\Big)\log_2 N + \omega(1) \qquad \text{when } K \sim N^{\alpha},27\end{equation}28so that higher local order permits coarser derivative uplinks.29\item \emph{Evidence.} Paired-replication Monte Carlo experiments for exponential, logistic and Poisson likelihoods with $N$ up to $2^{22}$, an exact-model boundary study, ablations over split patterns, Newton rounds and derivative quantization, and timed benchmarks of the full coordinator--worker protocol on up to \benchHosts{} Apple-silicon hosts quantify the finite-sample variance cost of higher-order corrections (which can reverse the asymptotic ranking at moderate $m$), the fraction of local fits that fail, interval coverage, transmitted bytes per round and the measured exchange rate between local fits and synchronization rounds.30\end{enumerate}3132\paragraph{What is not claimed.} The two building blocks are known: split-sample extrapolation is the generalized jackknife of \citet{quenouille1956notes} and \citet{schucany1971bias}, applied to panels by \citet{dhaene2015split}; one-step distributed Newton estimation is due to \citet{huang2019distributed}. ``Debias locally, then average'' exists in several forms \citep{zhang2013communication,gu2023heterogeneity,wu2023subsampling,yin2022newton}, and ``average, then correct globally'' in several others \citep{huang2019distributed,zhu2021least,jordan2019communication,fan2023communication}. What we add is the joint analysis, the sharpness statement, and the inexact-curvature frontier. We claim no minimax or communication lower bound: in exponential families the pooled sufficient statistic recovers $\thetaN$ exactly with one round of $p$ numbers per worker, and the exponential model is used here as an analytically transparent laboratory, not as an application. All results are for fixed $p$ and i.i.d.\ data; constants depend on $p$ and the theory does not transfer to growing dimension without new arguments. Wall-clock statements are measurements on specific hardware and are reported as such.3334The paper is organized as follows. \Cref{sec:lit} positions the results against the closest theorems in the literature. \Cref{sec:env} defines the likelihood environment, the protocol and the assumptions. \Cref{sec:construction} develops the general local correction. \Cref{sec:results} states the frontier theorem and its inferential corollary, \cref{sec:exact} the exact exponential analysis, \cref{sec:inexact} the inexact-curvature theorem, \cref{sec:cost} the cost model. \Cref{sec:mc,sec:bench} report the Monte Carlo and benchmark evidence, \cref{sec:robust} the extensions, \cref{sec:discussion} the limitations. Proofs are in \cref{app:proofs,app:exp}; replication material is described in \cref{app:replication}.35
Files · dd2471a83ff836060f8585aef5236d77d6a11c15
Menu

Theme