UQO Working Papers · WP28 · v1.0
Beyond One-Step Distributed Maximum Likelihood: Local Bias Cancellation, Global Synchronization, and the Price of Inexact Curvature
A joint order–round frontier, its sharpness in an exact model, and measured communication costs
- Year
- 2026
- First release
- October 2026
- Latest revision
- October 2026
- Publication status
- Working paper
One synchronization round is worth a doubling of local jackknife order
Local order-r debiasing plus q aggregated Newton steps matches the centralized MLE whenever K = o(N^(1−1/(2^(q+1) r))); the half-block jackknife with one step reaches K = o(N^(7/8)) against the K = O(N^(1/2)) regime of plain averaging.
Abstract
Distributed maximum likelihood estimation trades statistical efficiency for communication. The paper studies a two-phase protocol in which each of K workers corrects the bias of its local maximum likelihood estimator by an r-th order split-sample extrapolation over nested sub-blocks, the coordinator averages the corrected estimates, and q globally synchronized Newton corrections follow. For fixed-dimensional regular likelihoods with N observations it proves a joint order–round frontier: first-order equivalence to the centralized estimator holds whenever K = o(N^(1−1/(2^(q+1) r))), so that one extra local extrapolation level and one extra synchronization round are exchangeable in the exponent, and the half-block jackknife followed by one Newton step tolerates K = o(N^(7/8)) partitions, against the K = O(N^(1/2)) regime stated for the plain-average one-step estimator.
In the exponential model exact bias, variance and Newton identities are derived; the exponent is shown to be sharp for the construction, with limiting shift −θ0(βr c^r)^(2^q) when K ~ cN^α(r,q), and the Newton basin of attraction is characterized. A perturbation theorem for inexact curvature recovers the known single-machine-Hessian frontiers as special cases and gives the number of bits to which transmitted derivatives may be quantized at each local order.
Monte Carlo experiments with paired replications (exponential, logistic and Poisson likelihoods, N up to 2^22), an exact-model boundary study, ablations and timed multi-node benchmarks on an Apple-silicon cluster quantify the finite-sample variance cost of higher-order corrections and the wall-clock exchange rate between local fits and synchronization rounds. The components combined are known; the joint frontier, its sharpness and the bit-precision result are new. No universal communication lower bound is claimed.
Key findings
K = o(N^(7/8))
half-block jackknife plus one Newton step
1 − 1/(2^(q+1) r)
joint order–round exponent, fixed dimension
−4θ0c^4
sharp boundary shift, exponential model, (r,q) = (2,1)
27
Lean 4 / Mathlib theorems, no sorry
N ≤ 2^22
paired Monte Carlo, 2,000 replications per cell
54 ms → 1.83 s
derivative round on 16 hosts, p = 8 to 64
Scientific contributions
- A joint order–round frontier
- Theorem 1: first-order equivalence to the centralized MLE whenever K = o(N^(1−1/(2^(q+1) r))); the exponent depends on (r, q) only through the depth D = 2^q r, keeping the centered random remainder of order (m√K)^(−1).
- Sharpness in an exactly solvable model
- Theorem 2: in the exponential model the scaled gap converges to −θ0(βr c^r)^(2^q) at the boundary K ~ cN^α(r,q) and diverges beyond it, so the sufficient exponent is necessary for this construction; the Newton basin is (0, 2θ̂N).
- The price of inexact curvature
- Theorem 3: stale averaged local Hessians give exponent 1 − 1/(2(r+q)), a single-machine Hessian 1 − 1/(2r+q), recovering the (t+1)/(t+2) and 2/3 frontiers of Fan et al. (2023) and Jordan et al. (2019); quantization is free once b ≥ (1/2 − r(1−α)) log2 N bits.
- Exact variance cost of the half-block correction
- Var J2 = θ0² m²(m² − 6m + 17)/((m−4)(m−2)²(m−1)²), whose first two terms coincide with the raw MLE; order 3 beats order 2 only at the smallest block sizes in the simulations.
- Measured exchange rate between rounds and local levels
- On a 16-host Apple-silicon LAN the synchronized derivative phase costs 54 ms at p = 8 (network round trip about 0.4 ms) against a local phase that grows from 0.26 to 0.96 s from order 1 to 4, so one more round is cheaper than one more local level.
Methodology
Methodology (5)
Generalized split-sample jackknife
Each worker fits the MLE on its block and on nested sub-blocks of sizes m/s_j, combining them with Vandermonde weights that cancel the first r − 1 bias terms while preserving the first-order influence function exactly.
Aggregated Newton synchronization
The coordinator averages the corrected estimates, broadcasts, and applies q Newton steps from aggregated scores and Hessians; variants use stale, single-machine or b-bit quantized curvature.
Uniform stochastic expansions
Proofs rest on a bias expansion of order r and local Newton regularity under fixed p and i.i.d. data, with exact identities in the exponential model and a perturbation argument for inexact Hessians.
Machine-checked and symbolic verification
The algebraic content of the exact identities is formalized in 27 Lean 4 / Mathlib theorems without sorry and re-derived in SymPy; probabilistic steps are proved in the appendix.
Cost model calibrated on measurements
Proposition 5 gives the wall-clock exchange rate between one local extrapolation level and one synchronization round, calibrated on the benchmark timings for this hardware.
Research data
- Paired Monte Carlo designs
- Seeded synthetic samples (seed base 20261028): exponential model with N in {2^14, …, 2^22} and m in {8, …, 1024}, 2,000 replications per cell (500 at N = 2^22); logistic and Poisson regressions with p in {3, 8} and a p = 20 stress design (1,000 and 500 replications); robustness designs with misspecification, ill-conditioning, one percent contamination and very small blocks; 40 exponential cells on a laptop and 136 cells spread over 18 MacLustr nodes.
- Exact-model boundary study and ablations
- Exponential-model runs along K ~ cN^α(r,q) that compare the finite-m gap with the predicted limit, plus ablations over split patterns, Newton rounds and derivative quantization.
- Cluster benchmarks
- A real coordinator–worker protocol (Python/NumPy over TCP) on up to 16 Apple-silicon hosts with K ≤ 256 workers and p in {8, 32, 64}: 23 designs, 75 timed runs, each logging per-stage wall clock, per-worker latency and bytes per message.
Reproducibility
- End-to-end pipeline in experiments/ (Monte Carlo, boundary, ablations, skewed, benchmarks, processing, tables) with an EXPERIMENT_MANIFEST.csv and JSON manifests recording commit, versions, host and SHA-256 per raw file
- 30 pytest tests, SymPy symbolic checks of every identity and scripts/check_lean.sh for the 27 Lean 4 theorems
- All figures and LaTeX tables regenerated from results/ by process_results.py and make_tables.py; raw Monte Carlo outputs committed
- Full LaTeX source of the 56-page paper with proofs in the appendices; provenance disclosure and frozen prior note in references/initial_pamle/ with SHA256SUMS
Research artifacts
Version history
| Version | Date | Description | File |
|---|---|---|---|
| v1.0current | October 2026 | Current manuscript as published on www.spboucher.ai (revised edition after the 2026-10-17 scientific review for papers 1–17). | PDF · 56 p. |