Self-calibrating monitors adapt their threshold online to guarantee a prescribed long-run false-alarm rate under arbitrary drift. We compute the price of that guarantee, stating every law with its exact domain of validity. First, the guarantee is an accounting identity, insensitive to what the monitor is meant to detect. Two evidence identities make the cost exact for the online quantile tracker: a persistent step of height δ yields excess alarm mass within one alarm of δ/η, and exactly δ/η pathwise when δ is a lattice multiple of the gain η; a ramp of slope c yields a stationary excess rate of exactly c/η, independent of accumulated size, up to a boundary c=η(1−α) coinciding with the alarm-rate cap. Second, the certificate's own fluctuation obeys an exact law: the windowed alarm rate has standard deviation of order 1/L, not the binomial 1/L, since the windowed mass telescopes to a difference of a tight internal state; the closed-form constant is validated with no fitted parameter. Detectors calibrated on the binomial scale are miscalibrated by ηφ(q0)L, and correct calibration turns detection windows from quadratic to linear in the inverse fault speed. Third, any monitor required to tolerate a drift class D is blind, at any horizon and for any rule, to every fault in D−D; the proof is a deliberately elementary two-point argument and the contribution is the object it identifies: for speed-bounded classes the blind set is exactly the doubled-speed class, and the tracker absorbs a speed class fixed by its own gain, so that under a certification regime declaring absorbed drift normal, the monitor manufactures D. An exact Gaussian projection bound, sharper than Pinsker and never vacuous, quantifies power outside it.
Figures & tables
step δ
0.5
1.0
1.5
2.0
2.5
3.0
predicted δ/η
10
20
30
40
50
60
measured mean (CI 95 )
10.00 (0.00)
20.00 (0.00)
30.00 (0.00)
40.00 (0.00)
50.00 (0.00)
60.00 (0.00)
max per-path ∣ dev ∣
0.000
0.000
0.000
0.000
0.000
0.000
ramp slope c ( ×10−3 )
0.5
1
2
4
8
predicted α+c/η
0.110
0.120
0.140
0.180
0.260
measured rate
0.1100
0.1200
0.1400
0.1800
0.2600
Table 1: Exact evidence identities. Steps: 50 repetitions, horizon 4000; lattice steps are exact on every trajectory. Ramps: 20 repetitions, horizon 40000 after burn-in; all CI 95 below 10−4 .
η=0.05
η=0.02
L
predicted
measured
binom./true
predicted
measured
binom./true
100
2.451e-2
2.478e-2
1.21
2.757e-2
2.771e-2
1.08
200
1.457e-2
1.460e-2
1.45
1.799e-2
1.792e-2
1.18
400
7.888e-3
7.942e-3
1.89
1.100e-2
1.102e-2
1.36
800
4.001e-3
3.977e-3
2.67
6.137e-3
6.237e-3
1.70
1600
2.002e-3
1.966e-3
3.82
3.159e-3
3.185e-3
2.35
Table 2: Null standard deviation of the windowed alarm rate: closed form versus measurement, and the measured binomial miscalibration ratio.
Figure 1: The certificate’s null fluctuation follows the 1/L law of Theorem 3 (solid, no fitted parameter), not the binomial 1/L (dashed); measured points for two gains.
Figure 2: Top: windowed alarm rate for a 4σ step and an 8σ ramp; the dotted line is the target α . Bottom: the tracker threshold riding the ramp fault.
c/η
power, B=4σ
power, B=16σ
0.016
0.03 [0.00, 0.13]
0.12 [0.05, 0.26]
0.025
0.40 [0.26, 0.55]
0.97 [0.87, 1.00]
0.035
1.00 [0.91, 1.00]
1.00 [0.91, 1.00]
0.045
1.00 [0.91, 1.00]
1.00 [0.91, 1.00]
0.055–0.100
1.00 [0.91, 1.00]
1.00 [0.91, 1.00]
Table 3: Refined speed frontier with Wilson intervals, 40 repetitions per cell; same protocol as Figure 3 .
Figure 3: Detection power versus fault speed (as excess rate c/η ) and final fault size. Protocol: 2000 fault-free steps, a ramp of slope c to height B (duration B/c ), then 3000 steps at height B ; the same binomial-calibrated downstream detector as Table 3 ( L=400 , z=3 ); 200 repetitions per cell. The frontier is vertical outside its resolution band: speed decides, size does not. In the leftmost column the ramp is long and power grows weakly with size through the number of windows it offers, the repeated-attempt mechanism of the text; the three lowest cells there are indistinguishable at this repetition count.
Fault detection identifies abnormal behavior in machines, sensors, infrastructure, software, and autonomous systems before it causes harm or disruption.
Monitoring concept drift from an adaptive classifier's error stream creates an operational conflict with the model's own update loop. When internal adaptation outpaces evidence accumulation, accuracy recovers before cumulative detectors (CUSUM, Page-Hinkley) can reach threshold. Instrumenting an Adaptive Random Forest (ARF) shows that surviving trees absorb 98.6% of the post-drift error transient through incremental leaf updates alone. The first background tree swap accounts for just 0.71% of this erased error volume, but drops external detection rates by 31 percentage points. We derive the finite-horizon boundary where cumulative evidence fails to cross threshold and measure a critical magnitude floor (Δec=0.120) below which false-alarm budgets preclude detection. This failure manifests as missed shifts on stationary streams and false-alarm flooding triggered by internal tree swaps on noisy baselines. We validate on synthetic shifts, ARMA-GARCH series (ProteuS), and tabular benchmarks (BAF, INSECTS); on the synthetic sweep at a standard threshold, the blind spot appears at Δe≈0.25, showing why classical benchmarks like SEA (Δe≤0.21) failed to reach it.
Raphaël Minato, Fabrice Popineau, Arpad Rimmel +1
Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91190, Gif-sur-Yvette, France
Supermartingale certificates formally guarantee temporal properties of discrete and continuous-time stochastic dynamical systems. However, these guarantees rely on a mathematical model of the world, leaving a sim-to-real gap that can invalidate them for the deployed system. We formulate the runtime monitoring problem for supermartingale certificates, in which a monitor observes a single system trajectory and raises an alarm when there is sufficient statistical evidence that the supermartingale certificate has been violated during execution. We present an algorithm to automatically construct a monitor using betting-based sequential tests that bound the probability of ever raising a false alarm at a user-specified level. Within this betting framework, we formulate strategies that allow the monitor to exploit spatial regularity to improve detection power while preserving this statistical guarantee. We demonstrate the efficacy of our approach on supermartingale certificate benchmarks from the literature.
Mirco Giacobbe, Thomas A. Henzinger, Konstantin Kueffner +2
University of Birmingham · Institute of Science and Technology Austria · University of Oxford +2
Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.
Ibne Farabi Shihab, Adria Binte Habib
Department of Computer Science, Iowa State University, USA · Department of Computer Science & Engineering, Independent University of Bangladesh, Bangladesh