Quickest Change Detection with Diffusion-Integrated Scores

The gist Quickest Change Detection with Diffusion-Integrated Scores proposes a training-free detector, DI-SCUSUM, that integrates score evidence across Gaussian smoothing scales to recover directed KL divergences and achieve superior detection delay bounds compared to single-scale methods.

How it works

DI-SCUSUM is a sequential procedure that combines score evidence across Gaussian smooth scales to detect distributional changes using pre- and post-change samples (b) DI-SCUSUM construction, where For each incoming observation, we sample a diffusion time, perturb the observation, and use the importance-weighted score difference as an increment in the DI-SCUSUM recursion. The procedure first collects pre- and post-change samples and Gaussmooth them to obtain two density estimates with closed-form Hyv¨arinen scores (b) DI-SCUSUM construction, where "Pre- and post-change samples define Gaussiansmoothed models. Each new observation is perturbed at a sampled diffusion time; the resulting score difference is importance-weighted and accumulated by CUSUM to detect a distributional change".

Key Mathematical Principles

The core mechanism relies on the relative de Bruijn identity along a common Gaussian heat flow, which links integrated score evidence to KL divergence (a) Anisotropic Gaussian. The lemma states that for distinct Gaussian-smoothed empirical models, the time integral recovers the initial KL divergence (d) Details for Proposition 1. This leads to the mean increments being proportional to the Kullback–Leibler (KL) divergence from one smoothed distribution to another (a) Change and detection.

Sequential Guarantees and Bounds

The paper establishes strong theoretical guarantees for DI-SCUSUM, including exponential false-alarm scaling and a first-order delay bound (c) Conditional detection delay. Theorem 1 shows that the prechange Cram´er root governs false alarms, while the forward KL divergence governs the first-order delay (a) Proof of the KL drift identities. Specifically, it proves that the post-change mean increment is proportional to the Kullback–Leibler (KL) divergence from the smoothed post-change to the smoothed pre-change empirical distribution (b) DI-SCUSUM construction.

Estimation and Calibration

The procedure involves several tuning quantities:

1. The base scale ε, which changes the statistical problem being detected by setting the minimum amount of Gaussian smoothing (A.1 Parameter Roles).

2. The time density f, which determines which diffusion times are sampled more often and therefore affects the variance of the integral estimator (A.2 Gaussian-Mixture Heat-Flow Calculation).

3. The multiplier λ, which rescales every increment (A.3 Hyv¨arinen Score-Matching Identity).

4. The threshold τ, which determines how much accumulated evidence is required before stopping (A.2 Gaussian-Mixture Heat-Flow Calculation).

The optimal time density f⋆(t) is proportional to the second moment of the increment, minimizing the post-change second moment (Proposition 3). The threshold τ is calibrated by simulating no-change streams and refining it by bisection until the empirical ARL matches the target (2.5 Estimation and Calibration).

Benefits of Diffusion Integration

Integration across diffusion times retains information lost by single-scale score statistics (3 BENEFITS OF DIFFUSION). Proposition 1 shows that Z T 0 a(t) dt = KL(P1∥P∞) − KL(P1,T ∥P∞,T) (A.12 Details for Proposition 1). Furthermore, the ideal integrated increment equals the loglikelihood ratio (A.13 Details for Remark 1), which has the same information number as likelihood-ratio CUSUM (A.13 Details for Remark 1). This demonstrates that integration recovers weights, unlike SCUSUM which can be strictly less informative (A.14 Adaptive Weighting across Diffusion Times).

The paper concludes that DI-SCUSUM nearly matches likelihood-ratio CUSUM and reduces the measured detection delay by about 91% relative to score-based CUSUM in the calibrated anisotropic Gaussian simulation (4.1 Anisotropic Gaussian Diagnostic Setup and Methods). It also shows lower empirical conditional detection delay than SCUSUM at comparable false-alarm levels on MNIST and Oxford-IIIT Pet streams (4.2 Sample-Based Image Experiments).

The final result shows that the detection delay is bounded by CADD(TDI) = τλ KL(Qbε∥Pbε) + O(1) (Theorem 2). This demonstrates that the pre-change Cram´er root governs false alarms, while the forward KL divergence governs the first-order delay (a) Proof of the KL drift identities.

The final sentence states that The drift identities in (10) and the guarantees in Theorems 1 and 2 are conditional on the fixed reference sets and the exact empirical plug-in model (A.14 Adaptive Weighting across Diffusion Times). This means that for distributions different from the fixed empirical models, the stated guarantees therefore require the model assumptions (A.14 Adaptive Weighting across Diffusion Times).

The final sentence states that The mean increment does not depend on f, but its variance does (A.14 Adaptive Weighting across Diffusion Times). This means that the sampling density f changes the variance, not the target integral, provided it has adequate support (A.2 Gaussian-Mixture Heat-Flow Calculation).

The final sentence states that The computational cost and local mixture approximations are discussed (A.11 Additional Computation and Approximation Details). This means that Exact evaluation of both barycentric maps and local variances costs O((N0 + N1)d) per diffusion time, and hence O(M(N0 + N1)d) for M sampled times or quadrature nodes (A.11 Additional Computation and Approximation Details).

The final sentence states that The Gaussian diagnostic interpretation is discussed (A.11 Additional Computation and Approximation Details). This means that The Gaussian panel reports the four methods at the same nominal ARL targets, with horizon-censored delay values read directly from the plotted points (A.11 Additional Computation and Approximation Details).

The final sentence states that Pilot time-density selection and Monte Carlo estimation are discussed (A.10 Time-Density Optimization and Monte Carlo Estimation). This means that The optimal density f⋆(t) ∝ p m2(t) depends on a postchange second moment that is usually unavailable in closed form (A.10 Time-Density Optimization and Monte Carlo Estimation).

The final sentence states that Rao–Blackwellization and quadrature are discussed (A.11 Additional Computation and Approximation Details). This means that Replacing Gt(X, W) by Gt(X) = E[Gt(X, W) X] removes the auxiliary-noise variance without changing the conditional target (A.11 Additional Computation and Approximation Details).

The final sentence states that Threshold calibration is discussed (A.11 Additional Computation and Approximation Details). This means that For a target ARL = γ, the renewal approximation τ0 = log(γ)/θλ,ε provides an initial threshold (A.11 Additional Computation and Approximation Details).

The final sentence states that Finite diffusion window is discussed (A.19 Supplementary Materials). This means that "If the time density is supported on 0 ≤ a < b < ∞, the post-change drift is λ Z b a DF (Pbε1,t∥Pbε∞,t) dt = λ h KL(Pbε1,a∥Pbε∞,a) − KL(Pbε1,b∥Pbε∞,b)" (A.19 Supplementary Materials).

The final sentence states that Additional barycentric smoothing is discussed (A.19 Supplementary Materials). This means that For perturbations ξ1,..., ξM and σ ≥ 0, one may replace k r,ε t by e k r,ε tσ(y) = 1/M X M m=1 k r,ε t(y + σξm), se r,ε tσ(y) = e k r,ε tσ(y) − y 2ht (A.19 Supplementary Materials).

The final sentence states that AI use statement is discussed (A.

1. The DI-SCUSUM detector can be implemented as a training-free sequential change detection system by sampling a diffusion time, perturbing observations, and using an importance-weighted score difference as an increment in the DI-SCUSUM recursion. This allows for quick identification of distributional changes without needing to train a score network.

2. The system can recover the likelihood-ratio CUSUM performance under specific conditions by utilizing the ideal integrated increment equals the loglikelihood ratio when using a suitable time density and integrating over all diffusion times, as shown in Appendix A.13.

3. The detector's performance can be optimized for computational efficiency by employing Rao–Blackwellization to remove noise sampling variance, yielding an increment that is the least expensive Monte Carlo estimator when averaged over independent time–noise pairs.

4. The system can achieve superior detection delay compared to score-based CUSUM by leveraging the relative de Bruijn identity which links the mean increments to directed KL divergences, leading to a reduction in measured detection delay by about 91% on calibrated anisotropic Gaussian simulations.

5. The system can be adapted for scenarios with different observation frequencies or noise characteristics by selecting an adaptive weighting scheme, such as defining "z ad n = a0∆0(Xn) + X L sum a l Gt l(Xn), a l >= 0," which allows the target evidence to be modified offline.

Classical CUSUM relies on the log-likelihood ratio of the underlying distributions, which cannot generally be computed from finite pre- and post-change samples alone. We propose diffusion-integrated score CUSUM (DI-SCUSUM), a training-free detector. We add Gaussian noise to the samples to form two smooth density estimates and calculate their Hyvärinen scores exactly, without training a score network. For each incoming observation, we sample a diffusion time, perturb the observation, and use the importance-weighted score difference as an increment in the DI-SCUSUM recursion. Under the assumption that observations follow the fixed empirical distributions, the post-change mean increment is proportional to the Kullback-Leibler (KL) divergence from the smoothed post-change to the smoothed pre-change empirical distribution. We establish exponential false-alarm scaling and a first-order delay bound that, for a fixed threshold and increment scaling, is inversely proportional to the KL divergence. In the calibrated anisotropic Gaussian simulation, DI-SCUSUM nearly matches likelihood-ratio CUSUM and reduces the measured detection delay by about 91% relative to score-based CUSUM. On MNIST and Oxford-IIIT Pet, DI-SCUSUM also has lower empirical conditional detection delay than SCUSUM at comparable false-alarm levels.