Unbiased Local Quadrature for Divide-and-Conquer Integration

Suppose a large set of function evaluations is spread across many machines, and we want the integral of that function. Each machine could fit a smart weighted rule to its own points, because optimized weights beat plain averaging by a wide margin. It could then send one number to a central server, which averages the numbers. The trouble is that each locally optimized rule is slightly biased, and averaging removes noise but never removes bias. Past some number of machines, that shared bias becomes the error floor. We propose a simple fix. Each machine fits its smart rule on half of its points and then corrects it with a plain average of the leftover error on the other half. Every machine's estimate is then exactly unbiased, so averaging across machines only shrinks error. We predict the resulting distributed estimator loses a factor of $m^{s/d}$ against the best centralized randomized rule, where $m$ is the number of machines, $s$ is the smoothness of the function, and $d$ is the dimension of the domain. The usual "partitioning threshold" (a hard limit on how many machines you can use before accuracy collapses) then becomes an explicit, smoothness-dependent trade-off.

This matters because two literatures have not met. Work on quadrature weights (the coefficients used to combine function values into an integral estimate) shows that optimizing them on random points gives near-grid accuracy. On the 2-sphere, optimized weights reach a log-log error slope of $-0.75$ against $-0.5$ for Monte Carlo (Optimal Monte Carlo integration on closed manifolds). But this requires an $\mathcal{O}(N^3)$ solve over all points. Work on divide-and-conquer estimation shows exactly how one-shot averaging breaks: parametric averaging matches centralized error only for $m \le \sqrt{N}$ (Communication-Efficient Algorithms for Statistical Optimization). Nobody has asked what happens when the thing being averaged is an optimized quadrature rule.

Core Claim

Fix notation. $f$ is the integrand, $\mu$ the target measure, and $K$ a kernel whose function space contains $f$. The integral of $K(\cdot,x)$ under $\mu$ (the "kernel mean") is assumed computable, which is the same assumption every optimized-weight method already makes. Machine $j$ holds $n = N/m$ points. It splits them into a fitting half and a holdout half.

On the fitting half, it computes the optimal kernel weights: the minimizer of worst-case error, which is equivalent to the posterior mean of a Gaussian process, a smooth random-function prior (Numerically Optimizing Weights for Monte Carlo Integration on Smooth Compact Manifolds). Equivalently, it builds the kernel interpolant $\hat f_j$, whose exact integral $I(\hat f_j)$ is a weighted sum of fitting-half values. It then forms

$$ \hat I_j = I(\hat f_j) + \frac{2}{n}\sum_{x \in \text{holdout}_j} \big(f(x) - \hat f_j(x)\big), $$

which is unbiased for $\int f\,d\mu$ because the holdout points are independent of $\hat f_j$. The server reports $\bar I = \frac{1}{m}\sum_j \hat I_j$.

The variance of $\hat I_j$ is about $\|f-\hat f_j\|^2_{L^2(\mu)}/n$. Kernel interpolation on $n$ random points has $L^2$ error of order $n^{-s/d}$ up to logarithms. That rate comes from the covering-radius bound in Optimal Monte Carlo integration on closed manifolds. Averaging $m$ independent unbiased terms therefore gives

$$ \mathbb{E}\,|\bar I - I(f)|^2 \lesssim \frac{1}{m}\cdot\frac{(N/m)^{-2s/d}}{N/m} = N^{-1-2s/d}\, m^{2s/d}. $$

Two consequences follow. First, there is no bias floor at any $m$: the estimator degrades smoothly. Second, it beats centralized optimized weights, whose error is of order $N^{-s/d}$, exactly when $m \le N^{d/(2s)}$. That inequality is our proposed partitioning threshold for distributed quadrature.

The contrasting hypothesis is that naively averaging locally optimal rules, without the holdout correction, stalls. Its error would be governed by the expected local residual, of order $n^{-s/d}$, which averaging does not reduce. This would be the quadrature analogue of the $\mathcal{O}(m^2/N^2)$ bias term in parametric averaging.

We do not claim the control-variate trick itself is new; holdout correction is standard Monte Carlo practice. What is new is using it to remove partition-induced bias in distributed kernel quadrature, and deriving and testing the resulting threshold.

Relation to Prior Work

The closest work is Distributed Learning via Filtered Hyperinterpolation on Manifolds. It averages local filtered polynomial approximations on manifolds and proves centralized rates for $m \le cN^{r/(r+d/2)}$. However, it assumes each machine already has an exact positive quadrature rule and the known Laplace–Beltrami eigenfunctions (the natural "Fourier modes" of the manifold). It also offers no debiasing. We assume neither: weights are computed from whatever points a machine holds, and unbiasedness replaces the threshold condition.

Three papers supply debiasing ideas for other estimators, and they constrain our design:

All three reduce bias approximately. Our correction is exact, needs no extra pass, and needs no knowledge of $s$.

Two papers supply methods we reuse. Kernel Quadrature with Randomly Pivoted Cholesky gives a way to fit $\hat f_j$ on a subset of nodes without knowing the kernel's eigenfunctions, which keeps local cost below $n^3$. Sampling-based Nyström Approximation and Kernel Quadrature gives low-rank approximations that keep $k - k_{\text{app}}$ positive semidefinite, which keeps local rules valid.

Research Program

The theory has three parts. First, we will prove the variance bound above. It requires a high-probability $L^2$ interpolation bound on random points, adapted from the covering-radius argument for closed manifolds and from push-forward domains (Numerically Optimizing Weights for Monte Carlo Integration on Smooth Compact Manifolds). Second, we will characterize the expected local residual of uncorrected optimal rules. This should establish when naive averaging hits a floor, and whether non-negative weights change it. Third, we will analyze two-fold cross-fitting, in which each half takes a turn as fitting set and holdout and the two estimates are averaged. This should recover the factor of two lost by splitting without breaking unbiasedness.

On the algorithm side, we will implement the estimator with exact local solves for $n \le 10^4$ and with Randomly Pivoted Cholesky node selection beyond that. Each machine sends one scalar to the server.

Baselines

The naive reference is distributed Monte Carlo: each machine averages its function values and the server averages those averages. It is unbiased and costs nothing, and it fixes the $N^{-1/2}$ slope that everything must beat. It will be run on identical point sets.

The strongest centralized competitor is optimal weights computed on all $N$ points (Optimal Monte Carlo integration on closed manifolds). On the 2-sphere it reports a log-log slope of $-0.75$, and on the Grassmannian $G_{2,4}$ (the space of 2-dimensional planes in $\mathbb{R}^4$) a slope of $-7/8$ against $-1/2$ for Monte Carlo. We will rerun it with the same kernels, up to the largest $N$ that fits in memory. The distributed method beats it if it has lower root-mean-square error at matched $N$ for $m$ inside the predicted threshold. A second target is the centralized holdout-corrected estimator, which should show the $-s/d - 1/2$ slope our method approaches. On QM9, the strongest reported result is from Kernel Quadrature with Randomly Pivoted Cholesky: with 512 nodes it "reduced the estimation error by a factor of three" relative to independent random sampling. We will use that as the single-machine reference.

The distributed competitors fall into two groups. One is the naive average of locally optimal rules. The other is BAVGM-style subsample extrapolation applied to those local rules. For distributed kernel quadrature specifically, no reported result was found on Lacuna, so all of these must be run by us under one tuning budget. Every method gets the same kernel bandwidth, chosen once on a pilot integrand and then frozen.

The key ablation removes the holdout correction while keeping the identical half-size fitting set. This isolates unbiasedness as the cause of any gain, rather than the change in fitting-set size.

Why not just…?

Why not just use distributed Monte Carlo, which is already unbiased? Because it throws away smoothness. Our estimator is also unbiased, but its variance is smaller by a factor of about $n^{-2s/d}$. On the 2-sphere and the Grassmannian, the gap between slopes of $-0.5$ and $-0.75$ or $-0.875$ already reported for centralized methods tells us how much this leaves on the table.

Why not just apply BAVGM's subsample extrapolation to each local quadrature rule? Extrapolation cancels bias only if the bias exponent is known. Quadrature bias scales like $n^{-s/d}$, with $s/d$ fractional and unknown, whereas BAVGM's cancellation assumes a $1/n$ expansion. We will run BAVGM with its suggested subsampling rate and with an oracle exponent. If the oracle version matches our method, extrapolation becomes a legitimate competitor whenever $s$ can be estimated, and we will report that.

Why not have each machine compress its data to a few weighted nodes and let the server re-optimize weights on the union? This merge-and-reduce scheme is a real threat. Recombination (Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombination) and Randomly Pivoted Cholesky both make compression cheap. With $r$ nodes per machine, the server solves an $(mr)^3$ problem and may approach centralized accuracy. Its costs are $r$ points and values per machine of communication, a central solve, and a bias floor set by compression. We will compare at equal communication, sweeping $r$. If merge-and-reduce dominates, the right design is a hybrid: merge-and-reduce for the fit, plus a holdout correction to remove its bias. We will test that hybrid directly.

Proposed Experiments

The decisive experiment fixes $N$ and sweeps $m$ from 2 to 1024, plotting root-mean-square error against $m$ on log-log axes. It will run on three settings:

The theory predicts two signatures. Our estimator's curve should rise with slope $s/d$. The naive-average curve should flatten into a floor. The crossover with centralized optimal weights should sit near $m = N^{d/(2s)}$.

A second experiment uses QM9, estimating mean isotropic polarizability under the empirical measure, where the kernel mean is computable from the pool. Molecules are sharded across machines. We report error relative to the factor-of-three single-machine reference.

The idea fails if either of two things happens. The holdout ablation could show no floor for naive averaging, meaning the bias we posit is negligible. Or the measured slope against $m$ could depart substantially from $s/d$, meaning the variance argument is wrong.