PaperlayerView exact revision on arXiv

Source-linked AI summary

Quickest Change Detection with Diffusion-Integrated Scores

Arman Adibi, Mohammadreza Maleki, Sanjeev Kulkarni, H. Vincent Poor

arXiv:2610.12200v1stat.MLcs.LG

TL;DR

In sample-based quickest change detection, the likelihood ratio required by classical CUSUM is generally unavailable from finite pre- and post-change samples. DI-SCUSUM combines closed-form scores across Gaussian smoothing scales and, under fixed empirical distributions, links its mean increments to directed KL divergence, supporting false-alarm and delay guarantees.

  • Problem

    With finite pre- and post-change samples, the underlying log-likelihood ratio is unavailable, so sequential detection needs computable evidence with negative pre-change and positive post-change means.

    Source: §1 · p. 1

  • Method

    DI-SCUSUM uses closed-form Hyvärinen scores of Gaussian-smoothed sample models and importance-weights score differences sampled across diffusion times in a CUSUM recursion.

    Source: §1 · pp. 1–2

  • Results

    Under fixed empirical distributions, the mean increments link to directed KL divergence between smoothed models, supporting exponential false-alarm scaling and first-order delay bounds.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Integrating score evidence across smoothing scales gives a KL-based mean increment rather than relying on a single-scale score comparison.

    Source: §1 · pp. 1–2

    The theoretical plug-in analysis assumes observations follow fixed empirical distributions defined by reference samples, with expectations conditional on those samples.

    Source: §2 · p. 2, §2.1 · p. 3

Abstract

from arXiv · show

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\"arinen 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.

1 INTRODUCTION

In the sample-based setting, finite pre- and post-change samples do not provide the underlying likelihood ratio required by classical CUSUM. DI-SCUSUM integrates score evidence across Gaussian smoothing scales, connecting its mean increments to directed KL divergence and supporting sequential guarantees.

1 INTRODUCTION

  • Finite pre- and post-change samples leave the underlying log-likelihood ratio unavailable, motivating computable evidence with negative pre-change and positive post-change means.Classical CUSUM accumulates log-likelihood-ratio evidence when the distributions are known.Source: §1 · p. 1
  • The central question is whether integrating score evidence across Gaussian smoothing scales can recover directed KL divergences and support sequential guarantees.Prior approaches include kernel comparisons, single-scale score differences, learned score functions, and matrix-weighted score methods.Source: §1 · p. 1
  • DI-SCUSUM is a training-free, sample-based detector that uses closed-form Hyvärinen scores and importance-samples their difference across Gaussian smoothing scales.Its contributions also include directed-KL identities under fixed empirical plug-in models, false-alarm and delay guarantees, and an evaluation on Gaussian and image data.Source: §1 · pp. 1–2
  • The paper links DI-SCUSUM’s mean increments to directed KL divergences between Gaussian-smoothed empirical distributions, yielding negative pre-change and positive post-change means.The stated connection supports the false-alarm and detection-delay guarantees.Source: §1 · p. 2

2 METHODOLOGY

The methodology constructs smooth pre- and post-change empirical models, compares their Hyvärinen scores, and uses the resulting evidence in sequential detection. Its theoretical setup fixes the reference samples and relates the detector’s score evidence to the smoothed distributions.

2.1 Change Model and Gaussian Smoothing

  • The analysis assumes fixed reference sample sets and treats observations as following their empirical distributions; its expectations are conditional on those sets.The alarm time is a stopping time based on observations and auxiliary draws, and delay is measured by Pollak’s conditional mean-delay criterion.Source: §2 · p. 2, §2.1 · p. 3
  • Adding Gaussian noise gives the empirical models positive common support, while further convolution at time t varies their smoothing scale.The base scale ε > 0 makes the models smooth and their KL divergences finite; integrating over t connects score evidence to KL divergence, unlike using ε alone.Source: §2.1 · p. 3

2.2 Closed-Form Score from Samples

  • DI-SCUSUM compares the Hyvärinen scores of Gaussian-smoothed pre- and post-change sample models, with negative pre-change and positive post-change mean evidence when the models differ.The evidence is computable from the sample sets at each fixed diffusion time.Source: §2 · p. 2, §2.2 · p. 3
  • The Hyvärinen score comparison is invariant to multiplying a density by an unknown positive normalizing constant.This property makes the score suitable for comparing unnormalized models.Source: §2.2 · p. 4

Appendix A.3 gives a short derivation.

The detector estimates integrated score evidence by sampling diffusion times, importance-weighting the score difference, and accumulating increments with a reflected CUSUM rule. Under the stated heat-flow and terminal-KL conditions, the integrated evidence yields directed KL mean increments and sequential guarantees.

Appendix A.3 gives a short derivation.

  • At a fixed diffusion time, the score comparison has a nonpositive pre-change mean and a nonnegative post-change mean, with strict signs when the smoothed distributions differ.The smoothed Gaussian-mixture scores can be computed exactly from weighted sample moments without training a score network.Source: Appendix A.3 · p. 4

2.3 The DI-SCUSUM Stopping Rule

  • For each observation, DI-SCUSUM samples a diffusion time, perturbs the observation, importance-weights the score difference, and updates a reflected CUSUM statistic.The factor 1/f(t) compensates for how often a diffusion time is sampled; the threshold τ triggers the alarm, and larger thresholds reduce false alarms but increase delay.Source: §2.3 · p. 4

2.4 Sequential Guarantees

  • When the terminal KL divergence vanishes, integrating score evidence over diffusion time recovers the initial KL divergence.The identity applies to positive smooth densities evolving under a common heat flow, subject to conditions justifying differentiation and integration by parts.Source: §2.4 · p. 5
  • Under fixed empirical models, DI-SCUSUM’s mean increment is proportional to the directed KL divergence between smoothed post-change and pre-change distributions.The relative de Bruijn identity gives the integrated score evidence as KL divergence when the terminal KL divergence vanishes.Source: §2.4 · p. 5

Appendix A.6 gives the conditioning argument.

Under the stated sequential assumptions, the appendix separates false-alarm calibration from post-change delay: the pre-change Cramér root governs false-alarm scaling, while forward KL governs first-order delay. It also details how smoothing and integral estimation affect the evidence and calibration.

Appendix A.6 gives the conditioning argument.

  • For large thresholds, the false-alarm theorem gives exponential average-run-length scaling, with τ ≈ log(γ)/θλ,ε as the leading-order calibration for target ARL γ.The result relies on the stated pre-change conditions for the increment distribution.Source: Appendix A.6 · p. 6
  • After the change, the mean increment is λ KL(Q̂ε∥P̂ε), and forward KL governs the first-order detection-delay bound.The delay result is under the stated post-change conditions.Source: Appendix A.6 · p. 6
  • Increasing ε improves regularity and numerical stability but can reduce the KL information available for detection.The smoothing parameter turns empirical measures into positive distributions with finite KL divergence, creating a statistical tradeoff.Source: Appendix A.6 · p. 6
  • These drift identities and guarantees assume fixed reference sets and the exact empirical plug-in model; actual stream increments need not have the stated KL means otherwise.The score increments remain computable when the stream differs from those models, but the stated guarantees require the model assumptions.Source: Appendix A.6 · p. 6

2.5 Estimation and Calibration

  • Monte Carlo estimates the time integral unbiasedly under integrability, while quadrature removes time-sampling variance but introduces truncation and discretization error.Averaging M independent time-noise draws preserves the mean and divides conditional sampling variance by M, when finite.Source: §2.5 · p. 6
  • For target ARL γ, the theoretical threshold approximation initializes calibration, then no-change simulations and bisection refine τ; changing only λ requires proportional threshold rescaling.Calibration is repeated when ε, f, or the estimator changes.Source: Appendix A.6 · p. 5, §2.5 · p. 6

3 BENEFITS OF DIFFUSION INTEGRATION

Diffusion integration accumulates score evidence across smoothing scales, recovering forward-KL information that a single-scale score statistic can miss. Its finite-window identity quantifies the recovered information, while the anisotropic Gaussian comparison explains the single-scale gap.

3 BENEFITS OF DIFFUSION INTEGRATION

  • Integrating score differences across diffusion times recovers the forward KL divergence when the terminal KL divergence vanishes, unlike SCUSUM’s use of only the t = 0 score difference.The result follows from the stated heat-flow identity for smooth population distributions.Source: §3 · p. 7
  • R(T) is exactly the fraction of forward KL information recovered by diffusion times in [0, T], and the sampling density f affects estimation variance but not R(T).Source: §3 · p. 7
  • In the anisotropic Gaussian comparison, SCUSUM’s inverse-variance-squared weights cannot match likelihood-ratio CUSUM’s inverse-variance weights when the shift spans directions with different variances.Equality holds when all directions carrying the shift have the same variance.Source: §3 · p. 7
  • With exact noise averaging and integration over all diffusion times, the ideal integrated increment equals the log-likelihood ratio, so IDI = ICUSUM.Finite numerical implementations approximate this identity, and adaptive weights across times change the target evidence and require separate calibration.Source: §3 · p. 7

4 EXPERIMENTS

The experiments test whether diffusion integration recovers likelihood-ratio CUSUM performance in an anisotropic Gaussian model and compare sample-based methods on MNIST and Oxford-IIIT Pet. DI-SCUSUM-quad closely tracks KDE-CUSUM on the image tasks and has lower CADD than SCUSUM at comparable ARLs.

4 EXPERIMENTS

  • The Gaussian diagnostic calibrates thresholds separately at γ ∈ {500, 1000, 2000}; image experiments evaluate four targets using independent paths from fixed empirical populations.The Gaussian delay uses a horizon-censored fixed-change estimate and does not estimate Pollak’s supremum over change times.Source: §4.1 · pp. 7–8, §4.2 · p. 8

4.1 Anisotropic Gaussian Diagnostic

  • On the anisotropic Gaussian diagnostic, DI-SCUSUM-quad reduces fixed-change delay by about 91% relative to SCUSUM and tracks CUSUM within 0.054 observations for quadrature and 0.028 for exact integration.The reported censored no-change means are within 4.43% of their targets.Source: Figure 2 · p. 8, §4.1 · p. 8

4.2 Sample-Based Image Experiments

  • On MNIST, DI-SCUSUM-quad reduces CADD relative to SCUSUM by 39.5–42.7% with ARL gaps at most 3.76% across all four targets, while strict six-method comparisons are unsupported at targets 500 and 2000.The six-method target-error and pairwise-ARL audit passes at targets 250 and 1000; DI-SCUSUM-quad remains close to KDE-CUSUM.Source: §4.2 · p. 8
  • On Oxford-IIIT Pet, DI-SCUSUM-quad reduces CADD relative to SCUSUM by 6.3–12.6% with ARL gaps below 4.3%, and remains close to KDE-CUSUM.All methods pass the 99% lower-confidence-bound audit for ARL ≥ γ.Source: §4.2 · p. 8

AI use statement

The authors used ChatGPT and Codex as supporting tools during manuscript revision, while retaining responsibility for the final paper content.

AI use statement

  • ChatGPT and Codex supported editorial revision, including grammar, wording, clarity, flow, presentation, and figure and reference formatting.They also checked literature and citations.Source: AI use statement · p. 9
  • The tools supported review of mathematical derivations and proof explanations, diagnostic numerical checks of identities, and interpretation of existing experimental results.The diagnostic checks did not generate the reported detection experiments.Source: AI use statement · p. 9
  • The authors retain responsibility for evaluating AI-assisted suggestions and for the paper’s final text, mathematical claims, proofs, code, citations, and experimental results.Source: AI use statement · p. 9

A.1 Parameter Roles

The appendix distinguishes the role of base smoothing from the roles of diffusion-time sampling and increment scaling. These choices affect either the detected distributions, the integral estimator, or the alarm rule.

A.1 Parameter Roles

  • The base scale ε sets minimum Gaussian smoothing and changes the empirical plug-in probability distributions, whereas diffusion time t produces progressively smoother views of those fixed models.At large t, the common-smoothed distributions’ KL divergence decreases toward zero, so large times contribute progressively weaker evidence.Source: §A.1 · p. 11
  • The time density f determines how often diffusion times are sampled and affects estimator variance, while λ rescales increments and τ sets the stopping threshold.Changing f is an estimation choice; changing ε changes the statistical problem being detected.Source: §A.1 · p. 11
  • Small ε keeps smoothed distributions close to empirical measures but can yield sharp scores and large KL values when supports differ; large ε improves numerical stability while attenuating distributional differences.The time density f does not change the target integral when it has adequate support.Source: §A.1 · p. 11

A.2 Gaussian-Mixture Heat-Flow Calculation

The calculation uses Gaussian convolution and differentiation to show that the smoothed empirical densities satisfy the heat equation.

A.2 Gaussian-Mixture Heat-Flow Calculation

  • The proof obtains the smoothed empirical expressions by convolution and then differentiates them.Source: §A.2 · p. 11
  • Because finite sums commute with the differential operators and ∂sφs = ∆φs, both smoothed empirical densities satisfy the heat equation ∂t b pε.Source: §A.2 · p. 11

A.3 Hyv¨arinen Score-Matching Identity

The appendix develops score and KL identities for DI-SCUSUM, then details its guarantees, estimator design, finite-window information, and Gaussian and adaptive variants.

A.3–A.6 Score and KL identities

  • Integration by parts yields the Hyvärinen score-matching identity; Gaussian-mixture score terms are exact, and integrated KL dissipation recovers the limiting divergence.The Gaussian-mixture terms can be evaluated in O(Nrd) operations.Source: §A.3 · p. 12, §A.4 · p. 12, §A.5 · p. 14

A.7–A.8 Proofs of Lemma 2 and Theorem 1

  • A unique positive moment-generating-function root yields exponential false-alarm scaling, with log E∞[TDI] = θλ,ετ + O(1).The proof uses negative drift, strict convexity, and regenerative excursions of the reflected statistic.Source: §A.7 · p. 15, §A.8 · p. 16

A.9 Proof of Theorem 2

  • Conditional delay is bounded by the zero-start delay; Wald’s identity and bounded overshoot give matching bounds after substituting the KL drift.The reflected statistic crosses the threshold no later than the corresponding unreflected random walk.Source: §A.9 · pp. 16–17

A.10 Time-Density Optimization and Monte Carlo Estimation

  • The second-moment-optimal time density samples diffusion times in proportion to the root second moment; pilot-grid estimates can approximate it.Averaging more independent time–noise pairs costs more per observation.Source: §A.10 · p. 17

A.11 Additional Computation and Approximation Details

  • Nearest-neighbor truncation reduces per-time cost but has geometry-dependent pointwise error with no sequential theory; the KL drift identity applies directly only at σ = 0.Retained neighborhoods must grow as diffusion weights spread at larger times.Source: §A.11 · pp. 18–19

A.12 Details for Proposition 1

  • R(T) tracks cumulative forward-KL information: a short diffusion window captures most when the curve rises quickly, while sampling density cannot change the curve.Sequential delay comparisons additionally require equal false-alarm calibration.Source: §A.11 · p. 18, §A.12 · p. 19

A.13 Details for Remark 1

  • Heat-flow integration restores likelihood-ratio inverse-variance weighting direction by direction, so ideal DI-SCUSUM matches its information number while SCUSUM can be less informative.The equality condition is constant variance across the active shift directions.Source: §A.13 · p. 20

A.14 Adaptive Weighting across Diffusion Times

  • Adaptive weighting learns a feature direction from estimated mean separation and covariance, but its weights must be fixed offline and its KL guarantees do not follow automatically.The construction’s empirical evaluation is left to future work.Source: §A.14 · pp. 20–21
Loading 2610.12200v1…