Weighted-Event Leverage-Score Two-Sample Tests

Physics simulations rarely produce plain samples. Each simulated collision event carries a weight that encodes cross section, luminosity scaling and detector efficiency. When the expected signal is a few events on top of a large background, those weights decide how much statistical evidence the simulation actually contains. Kernel two-sample tests ask whether two collections of events come from the same distribution. Recent work made them fast enough for multi-million-event datasets by compressing the kernel with a few well-chosen "landmark" events. Those fast tests, however, only handle unweighted samples.

We propose a weighted version of the fast test. It has two ingredients. The first chooses landmarks using ridge leverage scores, a per-event measure of how much each event contributes to the kernel's dominant directions, computed under the weighted distribution rather than the raw one. The second calibrates the test by permuting (event, weight) pairs, which gives an exact false-alarm guarantee whenever both samples come from the same simulator. The central prediction is quantitative. The power of the weighted test should depend on the Kish effective sample size $n_{\mathrm{eff}}=(\sum_i w_i)^2/\sum_i w_i^2$. The standard fix, "unweighting" by accept–reject, depends instead on the much smaller yield $\sum_i w_i/(n\max_i w_i)$. The gap between the two grows with how heavy-tailed the weights are, and that is exactly where rare-event searches are limited by statistics.

Core Claim and Prior Work

The closest existing work is An Efficient Permutation-Based Kernel Two-Sample Test. It tests whether two samples share a distribution using Maximum Mean Discrepancy (MMD), a kernel distance between distributions. To make this tractable it uses a Nyström approximation, which represents the full kernel matrix through a small set of landmarks, here chosen by approximate kernel ridge leverage scores. It calibrates with label permutations. The authors prove the test is minimax optimal, run it on the HIGGS and SUSY benchmarks, and explicitly state that it cannot handle weighted samples. That stated limitation is the gap this proposal fills.

The method comes from two places. Computational Efficiency under Covariate Shift in Kernel Ridge Regression combines importance weights with leverage-score Nyström sketching, but only for regression. Its guarantees also require all moments of the weights to be bounded, an assumption we specifically want to stress. Alessandro Rudi et al. show that sampling features by leverage scores, rather than uniformly, removes the requirement that the number of features grow linearly with the sample size. We carry both ideas over to testing, where neither paper goes.

Two papers motivate the proposal. Weighted Classification Cascades for Optimizing Discovery Significance in the HiggsML Challenge works on the HiggsML data, where every event's weight enters the Approximate Median Significance (AMS) discovery metric. Its contribution is optimizing that metric with full-data cascades of reweighted classifiers; it does not compress the data or test hypotheses. Searching for Exotic Particles in High-Energy Physics with Deep Learning shows that the analysis method alone can move the same HIGGS data from a $2.5\sigma$ hint to $4.9\sigma$. Sensitivity is therefore partly a property of the method, which is the premise of this work.

Concretely, let the pooled sample have events $x_i$ with normalized weights collected in a diagonal matrix $W$, and let $K$ be the kernel matrix. We define the weighted ridge leverage score of event $i$ at regularization $\lambda$ as

$$\ell_i^{W}(\lambda) = \Big[ W^{1/2} K W^{1/2}\big(W^{1/2} K W^{1/2} + \lambda I\big)^{-1}\Big]_{ii}.$$

This score is small for events that are either redundant or physically negligible (tiny weight). It is large for events in sparsely populated regions that carry real weight. Landmarks are drawn in proportion to $\ell_i^{W}$. The test statistic is the squared distance between the two groups' weighted mean embeddings, projected onto the span of the landmarks.

Because the variance of a weighted mean scales as $\sum_i w_i^2/(\sum_i w_i)^2$, we expect the minimax separation rate to hold with $n$ replaced by $n_{\mathrm{eff}}$. We also expect the number of landmarks needed to scale with the weighted effective dimension $\sum_i \ell_i^{W}(\lambda)$, rather than with the unweighted one.

Research Program

The work has three parts.

The first part is the estimator and its exact-validity regime. Permuting group labels is valid only if the pairs $(x,w)$ are exchangeable across groups when the null hypothesis holds. That is true when both samples are independent batches from the same proposal generator, each reweighted toward its own target hypothesis. This setting is common: it covers checking whether a systematic variation or an alternative model produces a detectably different distribution, and checking whether a signal-injected background differs from background alone. In this regime we prove finite-sample level-$\alpha$ control and an $n_{\mathrm{eff}}$-based power bound under weight moment conditions. We also test how far below the "all moments bounded" assumption of Della Vecchia et al. the bound survives.

The second part is the harder data-versus-weighted-simulation case, where exchangeability fails. Here we will not claim exact validity. We study a weighted bootstrap calibration and report its empirical false-alarm rate as the weight tails grow heavier. We say plainly where it breaks.

The third part is engineering. Weighted leverage scores will be approximated with the same recursive scheme used for the unweighted test, so the $O(nP\ell)$ cost is preserved, where $P$ is the number of permutations and $\ell$ the number of landmarks.

Baselines

The naive reference point is unweighting followed by the original test. Each event is kept with probability $w_i/\max_j w_j$, and the unweighted Nyström test of Chatalic et al. is run on the survivors with the same landmark budget and number of permutations. This is what a practitioner would do today. It is also valid in the exact regime, so it is the main validity-preserving competitor. Beating it means detecting a smaller injected signal fraction at equal compute.

The strongest scalable competitor is a weighted Random Fourier Features (RFF) test, in which kernel features are drawn independently of the data and the weights enter only through the mean embeddings. Chatalic et al. report that their leverage-score Nyström test matched RFF's power on HIGGS and SUSY while controlling Type-I error at $\alpha=0.05$. We found no reported numerical power value on Lacuna for either method, and no reported result on Lacuna for any weighted two-sample test on these benchmarks. Weighted RFF will be given the same feature count as our landmark count, the same bandwidth selection (the median heuristic), and the same tuning budget.

The ablation that isolates the key ingredient is weighted Nyström with landmarks chosen by unweighted leverage scores, and separately by uniform sampling. The weighting of the statistic stays fixed, so any difference comes from landmark selection alone. The full-data weighted MMD, computed on subsamples small enough to be tractable, serves as an oracle upper reference.

Why not just…?

Why not just unweight the events and use the existing test? This works well when weights are nearly uniform, and we expect it to roughly tie there. Its cost is that it keeps only about $n\,\bar w/\max w$ events, where $\bar w$ is the mean weight. One extreme weight can therefore discard most of the sample, while $n_{\mathrm{eff}}$ degrades far more gracefully. Experiment one varies the weight tail directly. If unweighting matches our test even under heavy tails, the proposal's main claim fails, and we will report that.

Why not just use weighted Random Fourier Features? This is a real threat. The existing evidence from Chatalic et al. shows parity in the unweighted case. Our argument is specific to weights: data-independent features spend capacity uniformly across feature space, while weighted leverage scores concentrate landmarks where high-weight events are sparse. Low-count signals tend to sit in exactly those regions. If weighted RFF matches us at equal feature count, the contribution reduces to the calibration and power analysis. We would then recommend RFF for the statistic and keep our permutation scheme.

Why not just train a weighted classifier and threshold it, as in the HiggsML cascades? The cascades of Mackey et al. optimize AMS, a discovery metric that presupposes a specified signal model. A two-sample test answers a different question: whether anything differs at all, with a calibrated false-alarm rate. Classifier thresholds tuned on the same data also risk the "hallucinated significance" that paper warns about. We will still run a classifier two-sample baseline with held-out calibration: train weighted XGBoost on one split and test whether its weighted mean score differs between groups on the other split, using the same compute.

Proposed Experiments

The first experiment uses HIGGS with controlled weights. We draw a biased subsample of the 11-million-event HIGGS data, tilting acceptance exponentially along one kinematic feature, so that each event's weight (the ratio of target to proposal density) is known exactly. The tilt strength is the dial that makes weights heavier-tailed. We then inject signal events at fraction $\varepsilon$ into one group. The primary metric is the minimum detectable fraction $\varepsilon^\ast$ at 80% power and $\alpha=0.05$, plotted against the ratio $n_{\mathrm{eff}}/n$ and against wall-clock time. We will also run the null case to check that the Type-I error stays at 0.05.

The second experiment repeats this on SUSY, a different physics process, to check that the result transfers.

The third experiment uses the real HiggsML event weights, taken from simulated ATLAS events, in the exact regime: two independent background batches, one with $H\to\tau\tau$ signal injected at physical weight. This tests the method under realistic rather than synthetic weight tails.

The fourth experiment is a stress test of the data-versus-simulation bootstrap calibration on HIGGS. We treat an unweighted draw as "data" and report the empirical false-alarm rate across the tilt grid.

The decisive checks are two. First, the advantage over unweighting should grow as $n_{\mathrm{eff}}$ separates from the unweighting yield; if it does not, the variance argument is wrong. Second, weighted leverage landmarks should beat both unweighted-leverage landmarks and weighted RFF at equal budget specifically in the heavy-tailed settings; if they do not, landmark selection is not the active ingredient.