Score-based change point detection via tracking the best of infinitely many experts

1. Problem Statement

The paper addresses the problem of nonparametric online change point detection.

• Setup: A sequence of independent random vectors $X_1, \dots, X_T$ is observed. The data is generated from an unknown density $p$ up to an unknown change point $\tau^*$, and from a different unknown density $q$ thereafter ($X_{\tau^*+1}, \dots, X_T \sim q$).
• Goal: Detect the moment $\tau^*$ as quickly as possible (minimizing detection delay) while controlling the false alarm rate, without assuming specific parametric forms (e.g., Gaussian) for $p$ and $q$.
• Challenge: Existing methods often rely on strong parametric assumptions (e.g., mean shifts in Gaussian distributions) or suffer from high computational costs when estimating complex densities (e.g., calculating partition functions for exponential families).

2. Methodology

The authors propose an algorithm that reframes change point detection as a problem of sequential prediction with expert advice and online convex optimization.

A. Core Concept: Tracking the Best Expert

The algorithm treats the problem as tracking the "best" static expert (a parameter vector $\theta$) in a pool of infinitely many experts.

• Pre-change ($t \le \tau^*$): The best expert remains constant. A standard Exponentially Weighted Average (EWA) forecaster performs well.
• Post-change ($t > \tau^*$): The best expert shifts to a new parameter. The EWA forecaster lags because it is "sticky" (it averages over history). A Fixed Share (FS) forecaster, designed to track changing experts, adapts quickly.
• Test Statistic: The detection statistic is the difference in cumulative losses between the two forecasters:
  $$\hat{S}_t = \hat{L}_{1:t}^{EW} - \hat{L}_{1:t}^{FS}$$
  • If $t \le \tau^*$, both forecasters perform similarly, so $\hat{S}_t$ remains small.
  • If $t > \tau^*$, the FS forecaster adapts to the new distribution while the EWA forecaster struggles, causing $\hat{S}_t$ to grow rapidly. A change is declared when $\hat{S}_t$ exceeds a threshold $z$.

B. Score-Based Loss Function

To avoid the computational bottleneck of calculating partition functions (integrals) required by log-loss in exponential families, the authors use Fisher Divergence as the loss metric.

• They approximate the densities $p$ and $q$ using a parametric reference class $\mathcal{P} = \{p_\theta : \theta \in \mathbb{R}^d\}$ where $\log p_\theta(x) = \Psi(x)^\top \theta - \Phi(\theta)$.
• Instead of log-loss, they minimize the Fisher divergence $F(p, p_\theta)$.
• Using Green's first identity, they construct an unbiased estimate of the Fisher divergence that depends only on the score function $\nabla \log p$ and the Laplacian $\Delta \Psi$, avoiding the need to compute the intractable integral $\Phi(\theta)$.
• The resulting loss function on round $t$ is quadratic:
  $$\ell_t(\theta) = \frac{1}{2}\theta^\top A_t \theta - b_t^\top \theta$$
  where $A_t$ and $b_t$ are constructed from $\nabla \Psi(X_t)$ and $\Delta \Psi(X_t)$.

C. Infinite Expert Fixed Share

Standard Fixed Share algorithms (Herbster & Warmuth, 1998) are designed for finite sets of experts. The authors develop a novel version tailored for infinitely many experts (continuous parameter space $\mathbb{R}^d$) with quadratic losses.

• They define a prior over compound experts (sequences of parameters) using a mixture of staying with the previous parameter or switching to a new one drawn from a Gaussian prior.
• They derive closed-form recursive formulas (Lemmas 2.2 and 2.3) to compute the Fixed Share prediction and the normalization constants efficiently, making the algorithm computationally feasible.

3. Key Contributions

1. Algorithm Proposal: A new nonparametric online change point detection algorithm (Algorithm 3.1) based on the difference between EWA and Fixed Share forecasters using Fisher divergence-based losses.
2. Theoretical Guarantees:
   • Pre-change: Proved that the test statistic $\hat{S}_t$ is bounded by $O(\log^3 \tau^*)$ with high probability, ensuring a low false alarm rate.
   • Post-change: Proved that $\hat{S}_t$ grows linearly with the Kullback-Leibler/Fisher divergence between the pre- and post-change distributions, ensuring rapid detection.
   • These bounds are non-asymptotic and hold under realistic assumptions (sub-Gaussian tails).
3. Computational Efficiency: The method avoids expensive numerical integration. With a constant learning rate, the complexity per round is $O(d^3 t)$, leading to a total runtime of $O(d^3 T^2)$, which is significantly faster than previous methods requiring integral calculations.
4. Infinite Expert Extension: A theoretical extension of the Fixed Share algorithm to handle infinite expert classes with quadratic losses, a result of independent interest in online learning.

4. Experimental Results

The authors evaluated the algorithm on both synthetic and real-world datasets, comparing it against state-of-the-art methods: FLH (Follow-the-Leading-History), FALCON, KLIEP, and M-statistic (Kernel-based).

• Synthetic Data: Tested on mean and variance shifts in univariate and multivariate Gaussian sequences.
  • Result: Algorithm 3.1 consistently achieved the lowest detection delay (often detecting changes within 1–4 observations) while maintaining zero false alarms.
• Real-World Data:
  • Human Activity (WISDM): Detected 16 activity changes in accelerometer data. Algorithm 3.1 had the shortest average delay (15.43) and fewest false alarms compared to competitors.
  • Speech Detection (CENSREC): Tested on clean and noisy speech recordings. The method outperformed others, particularly in noisy environments (SNR 15), maintaining robust detection.
  • Room Occupancy: Detected changes in temperature, humidity, light, and CO2 levels. The method showed competitive detection speed with low false positives.

5. Significance

• Bridging Theory and Practice: The paper successfully bridges the gap between theoretical online learning (tracking experts) and practical statistical change detection.
• Nonparametric Flexibility: By relying on score functions and Fisher divergence rather than explicit density estimation, the method is applicable to a much broader class of distributions than parametric approaches.
• Scalability: The avoidance of high-dimensional integration makes the method scalable to high-dimensional data, a common bottleneck in nonparametric change point detection.
• Robustness: Theoretical bounds and empirical results demonstrate robustness to noise and distributional shifts, making it a strong candidate for real-time monitoring systems in finance, IoT, and industrial control.

In summary, this paper presents a rigorous, efficient, and highly effective framework for detecting distributional changes in streaming data by leveraging the "tracking the best expert" paradigm adapted for infinite expert spaces and score-based losses.