Compute the exact weighted average
- DistanceLocate neighbors
- OrderRank responses
- WeightsApply the scale
- SumReturn the estimate
| Step | Calculation | Reuse or cost |
|---|---|---|
| Fit | Store training data and construct w(n,s). | O(n) weight calculation, cached once per scale |
| Distance | Compute squared Euclidean distances to x. | O(nd), shared across scales at this query |
| Order | Stable-sort training indices by distance. | O(n log n), ties retain original row order |
| Predict | Take the weighted sum of ordered responses. | O(n), no enumeration of subsets |
wi+1 = wi(n−i−s+1)/(n−i), i = 1,…,n−s.
The recurrence evaluates the binomial ratio without constructing large binomial coefficients. The maintained implementation keeps the exact nonzero support, rather than cutting off small weights arbitrarily. One query costs O(nd + n log n).
Squared distances preserve Euclidean ordering. Direct coordinate differences avoid a cancellation problem that can occur when distances are formed by subtracting large squared norms.
One ordering serves both scales
Cache the rank weights for s₁ and s₂, or their combined vector. Use the same distance order for the two base estimates.
a1 = −1 / [(s2/s1)2/d−1], a2 = 1−a1.
The coefficients use the actual integer scales and distance dimension. Rounding a proposed second scale changes the ratio; recompute the coefficients for that ratio. A stable logarithmic/exponential formulation helps when ratios are close.
Reuse work in resampling
| Routine | Statistical operation | Computational operation |
|---|---|---|
| Bootstrap | Draw n paired observations with replacement. Recompute the estimator for each draw. | Reuse distance ordering through counts and cumulative weights. Exact ties use a stable-sort fallback. |
| Jackknife | Delete each observation and apply the paper's variance formula. | Prefix/suffix sums avoid n refits and repeated sorts. |
| Multiple queries | Use the same resampled observation indices across queries. | Preserve pairing so cross-query relationships are retained in the draws. |
The base estimator's subsampling scheme and the inference bootstrap are distinct. BNN uses all fixed-size subsets without replacement; the bootstrap resamples the training dataset with replacement and then evaluates BNN on that resample.
The bootstrap sample variance uses denominator B−1. The jackknife is centered on the original estimate as in the paper's formula, and scales must be admissible for the n−1 sample.
Scale selection defines the procedure
The package's held-out helper minimizes global validation MSE over supplied pairs. Each validation query's distance ordering is shared across pairs, making the search cheaper than fitting and sorting anew for every candidate.
The paper replication includes its pointwise tuning procedures. Specify which rule is used when reporting results. Bootstrap inference with fixed selected scales does not automatically include the randomness of the selection step.
Read timings as measured workloads
The current package measurements concern 64 regression queries with n = 20,000, d = 4, scales 20/40, and float64. Fit and transfer are excluded. The records use warmed medians of five runs; CUDA measurement boundaries synchronize, and JAX completion is awaited.
| Path | 64 queries | Context |
|---|---|---|
| NumPy CPU | 0.0867 s | Independent reference formulation; separate generated sample |
| PyTorch CPU | 0.0295 s | NumPy agreement and original scalar-call comparison |
| PyTorch CUDA · RTX 3090 | 0.0024 s | Synchronized boundaries; NumPy and original comparison |
| JAX CPU | 0.0379 s | Warmed execution; first call includes compilation |
NumPy's generated sample differs from the backend-comparison sample. These records document measured configurations rather than a controlled ranking of all backends. JAX's first call was 0.132 s including compilation. Environment and raw records.
Saved paper computation table
The original paper's timing workload includes derivative-based estimation and first-stage calculations, rather than only the regression queries above. Scales are 7/14. Each cell gives point-estimate time / 100-bootstrap time in seconds.
| n | Numba CPU | PyTorch CPU | PyTorch GPU |
|---|---|---|---|
| 5,000 | 0.0066 / 0.0468 | 0.0404 / 1.1523 | 0.0032 / 0.2872 |
| 20,000 | 0.0234 / 0.0814 | 0.0361 / 5.2778 | 0.0139 / 0.7940 |
| 80,000 | 0.1050 / 0.1867 | 0.1290 / 15.9575 | 0.0305 / 2.5163 |
| 320,000 | 0.3619 / 1.0241 | 0.3108 / 29.4274 | 0.0511 / 3.5945 |
| 1,280,000 | 1.4909 / 5.7144 | 1.0065 / 116.9538 | 0.0817 / 6.3980 |
Retained from the saved source table. Original GPU timing code lacks explicit synchronization at measurement boundaries. This is historical reported evidence, separate from the synchronized package measurements.
Batching and hardware parallelism help when enough queries are available. For small workloads, device transfer and compilation can dominate. Warmed kernel time and end-to-end latency answer different practical questions.
The metric and workspace are part of computation
Euclidean distance on differently scaled features changes the neighborhood. Choose transformations and scaling intentionally, and apply them consistently. The dimension affects locality and the bias-correction coefficients.
Accelerator prediction works in bounded query batches. The direct-difference distance workspace scales with batch size, n, and d. Reusing fitted weights removes repeated construction but does not remove distance calculation or sorting for a new query.
Exact ordering is retained in the maintained implementation. A future approximate neighbor search would need its own accuracy analysis. Run the current implementation.