Anytime-Valid Distribution Shift Detection via Predictive Rank Martingales
Abstract
Many sequential distribution shift detectors update a growing reference set with incoming observations. After a change, this update contaminates the reference set with post-change observations and can weaken subsequent evidence. Keeping the calibration sample fixed mitigates this contamination, but repeated reuse induces dependence among fixed-reference ranks, so arguments based on independent conformal p-values do not apply. We derive the exact conditional null distribution of the next rank given the preceding ranks and use it to construct a predictive rank martingale (PRM). Thresholding a PRM gives distribution-free, finite-sample anytime marginal type I error control. To target specific departures, we apply a pre-specified feature to each rank, center the resulting payoff under the predictive null law, and use Online Newton Step (ONS) to adapt the bet. Order and dispersion features target directional and center-versus-tail changes, respectively. For any Lipschitz feature with nonzero induced contrast under the alternative, we establish a finite-window detection guarantee and show that the test is consistent as the initial calibration size increases. At a fixed calibration size, however, we derive a power ceiling for every distribution-free detection procedure. Across synthetic and real data, our PRM methods achieve better detection performance than conditional conformal test martingale (CCTM).
Related
- Anytime Valid Confidence Bands for Distribution Functions
- Anytime-valid detection of LLM weight exfiltration
- Anytime-Valid Inference in Linear Models with Applications to Regression-Adjusted Causal Inference
- Asymptotic Anytime-Valid Quantile Inference under Local Differential Privacy
- Boot-AVT: Asymptotically Anytime-Valid Testing with Degenerate U-Statistics via Bootstrap
BibTeX
@misc{kuang2026anytimevalid,
title = {{Anytime-Valid Distribution Shift Detection via Predictive Rank Martingales}},
author = {Qi Kuang and Yin Xia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00536},
eprint = {2609.00536},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00536},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Anytime-Valid Distribution Shift Detection via Predictive Rank Martingales
AU - Qi Kuang
AU - Yin Xia
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00536
UR - https://arxiv.org/abs/2609.00536
AB - Many sequential distribution shift detectors update a growing reference set with incoming observations. After a change, this update contaminates the reference set with post-change observations and can weaken subsequent evidence. Keeping the calibration sample fixed mitigates this contamination, but repeated reuse induces dependence among fixed-reference ranks, so arguments based on independent conformal p-values do not apply. We derive the exact conditional null distribution of the next rank given the preceding ranks and use it to construct a predictive rank martingale (PRM). Thresholding a PRM gives distribution-free, finite-sample anytime marginal type I error control. To target specific departures, we apply a pre-specified feature to each rank, center the resulting payoff under the predictive null law, and use Online Newton Step (ONS) to adapt the bet. Order and dispersion features target directional and center-versus-tail changes, respectively. For any Lipschitz feature with nonzero induced contrast under the alternative, we establish a finite-window detection guarantee and show that the test is consistent as the initial calibration size increases. At a fixed calibration size, however, we derive a power ceiling for every distribution-free detection procedure. Across synthetic and real data, our PRM methods achieve better detection performance than conditional conformal test martingale (CCTM).
ER -