Optimal Online Change Detection via Random Fourier Features
Authors: Florian Kalinke
Shakeel Gavioli-Akilagun
Venue: NeurIPS 2025 poster ()
Keywords: change point detection
information-theoretic lower bounds
kernel mean embedding
non-parametric testing
Primary area: general_machine_learning
TL;DR: We propose a kernel-based online change detection algorithm, running in O(log n) time and space, and show its minimax optimality.

Abstract: This article studies the problem of online non-parametric change point detection in multivariate data streams. We approach the problem through the lens of kernel-based two-sample testing and introduce a sequential testing procedure based on random Fourier features, running with logarithmic time complexity per observation and with overall logarithmic space complexity. The algorithm has two advantages compared to the state of the art. First, our approach is genuinely online, and no access to training data known to be from the pre-change distribution is necessary. Second, the algorithm does not require the user to specify a window parameter over which local tests are to be calculated. We prove strong theoretical guarantees on the algorithm's performance, including information-theoretic bounds demonstrating that the detection delay is optimal in the minimax sense. Numerical studies on real and synthetic data show that our algorithm is competitive with respect to the state of the art.

Optimal Online Change Detection via Random Fourier Features
Florian Kalinke"
Shakeel Gavioli-Akilagun'
Information Systems
Department of Decision Analytics and Operations
Karlsruhe Institute of Technology (KIT)
City University Hong Kong
Karlsruhe, Germany
Hong Kong, China sgavioli@cityu. edu
florian edl
Abstract
This article studies the problem of online non-parametric change point detection in multivariate data streams. We approach the problem through the lens of kernel- based two-sample testing and introduce sequential testing procedure based on random Fourier features, rumning with logarithmic time complexity per observation and with overall logarithmic space complexity. The algorithm has two advantages compared to the state of the art. First, our approach is genuinely online, and no access training data known be from the pre-change distribution is necessary. Second, the algorithm does not require the user to specify window parameter over which local tests are to be calculated. We prove strong theoretical guarantees on the algorithm's 's performance, including information-theored bounds demonstrating that the detection delay optimal in the minimax sense. Numerical studies on real and synthetic data show that algorithm is competitive with respect to the state the art.
Introduction
In the online change point detection problem, data is observed sequentially, and the goal is to flag change if the distribution of the data changes. The problem dates back to the early work of Page
[43] and has now been extensively studied in the statistics and machine learning literature [30 3 52). However, these classical approaches assume that the data are low-dimensional and that the pre- and post-change distributions belong to a known parametric f'amily. In modern applications, both assumptions are usually not satisfied. Examples modern online change point detection problems include: detecting changes in audio streams 4 in videos 23). in highway traffic data (15), in internet traffic data (3T) or cardiac time series [o]. Further, such data frequently has high volume, and online change point detection procedures should still be able to process new data in real time and with limited memory.
While algorithms for the problem of non-parametric online change point detection have been proposed-ss see Section 2 for brief sateviewwstate-f--ttee suffer from at least one of the following two limitations. First, most procedures are not genuinely online from statistical perspective, the sense that they either assume the pre-change distribution to be known completely they assume having access to historical data known to be from the pre-change distribution. Second, most approaches require the user to specify a window parameter over which local tests for change in distribution will be applied. Choosing such window is notoriously difficult and choosing the window too small too large leads to a reduction in power or an increase in the detection delay, respectively. Moreover, the window size imposes a limit on the historic data considered, rendering detecting sufficiently small changes impossible.
methods suitable for modern data
"Contributed equally.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Motivated by the above limitations and challenges, we propose a new algorithm called Online RFF- MMD (Random Fourier Feature Maximum Mean Discrepancy). On high level, the algorithm performs sequential two-sample tests based on the kernel-based maximum mean discrepancy (MMD;
Crucially, approximating the maximum mean discrepancy using random Fourier features (RFFs; [45)) leads to detection statistic that can be computed in linear and updated in constant time. By embedding these local tests a sequential testing scheme on dyadic grid of candidate change point locations, we obtain algorithm that does not require window parameter and features time and space complexity logarithmic in the amount data observed.
53 14)
This article makes the following contributions:
We propose Online RFF-MMD, fully non- con-parmettric change point detection algorithm that does not require access to historical data, has no window parameter, and features logarithmic runtime and space complexity.
Computational efficiency:
Minimax optimality: Online RFF-MMD comes with strong theoretical guarantees. In particular, derive information-theorette bounds showing that the detection delay incurred by Online RFF-MMD is optimal up to logarithmic terms the minimax sense. While related results are known in the offline setting [1 42 and in the parametric online setting 30 64]. ours is the first. result of this kind for kernel-based online change point detection.
We perform a suite of benchmarks synthetic data, the MNIST data, and the HASC data to demonstrate the applicability of the proposed method. Our approach achieves competitive results throughout all experiments.
Empirical validation:
The article is structured as follows. We recall related work in Section 2 and introduce our notations and the problem in Section minimax optimality. Experiments are Section and limitations in Section 7 Additional results and all proofs in the appendices.
our algorithm and its guarantees, and Section [ its
Table 1: Comparison of kernel- based change detectors. Genuinely online whether the algorithm
can be executed without reference data known be from the pre-change distribution; Window free whether the algorithm requires selection of window parameter over which the detection statistic calculated; Time comp. - runtime complexity per new observation; Space comp. - total space complexity; total number of observations
Algorithm
Genuinely online
Window free
Time comp.
Space comp.
Scan B-statistics
33
x
x
ONNW2)
((NW)
NEWMA (24)
/
x
((r)
((r)
Online kernel CUSUM 59
X
X
O ONNW2
((NW)
Online RFF-MMD
/
/
loggogn)
Orllog))
2 Related work
In the case of univariate data, numerous methods for non-parametric online change point detection have been proposed; we refer to Ross [49] for more comprehensive overview. The most successful among these approaches exploit the fact that all information is contained in the data's empirical distribution function, which a functional of the ranks. Rank-based online change point detection methods have been proposed by 133 [9 48 However, their extension to multivariate data is challenging as this requires a computationally efficient multivariate analogue to scalar ranks.
To tackle change point detection on multivariate data, many approaches exist; see Wang and Xie [58 for survey. For example, Yilmaz (62. Kurt al. (28 introduce procedures using summary statisties based on geometric entropy minimization, but assume knowledge of the pre-change distribution. An alternative non-parametric approach is using information on distances between data points 77 g) However, here one can construct alternatives which the procedures will always fail to detect as the limits of the test statistics employed do not metrize the space of probability distributions.
In Table 1 where applicable, denotes the number of random Fourier features, W denotes the size of the window, and N denotes the number of blocks of historical data. We treat the dimension of the data tixed.

---

One principled approach to tackle this challenging setting is using kernel-based two sample tests via the MMD, which we recall briefly in Section 3.2] The key property, if the underlying kernel is characteristic [1] 55 is that the MMD metrizes the space of probability distributions and thus allows detecting any change. However, the sample estimators of the MMD typically have a quadratic runtime complexity, which prohibits their direct application in the online setting. To overcome this challenge, Zaremba et al. [66] propose Scan B-statistics, which achieve sub-quadratic time complexity by splitting the data into blocks and computing the quadratic-time MMD on each block. Consequently, Li et 32 331 introduce an online change point detection algorithm that recursively estimates the Scan Btsttiistic over sliding window. Extending this idea, Wei and Xie [59] propose an algorithm which performs the same operation over grid of windows of different sizes. However, these algorithms all require the choice of window parameter and are not genuinely online as they require historical data known to be from the pre-change distribution. Keriven et al. (24) propose comparing exponentially smoothed MMD statistics, where the MMD is approximated by using random Fourier features. However, the window selection problem is not avoided because, as shown by the authors, the smoothed statistic can be interpreted as computing differences between MMDs calculated on two windows of different sizes.
We summarize the kernel-based approaches coming with theoretical guarantees in Table and note that we present two extensions of our proposed Online RFF-MMD approach in the appendix. The first allows taking historical data into account (Appendix (A.Ip. The second permits detecting multiple change points within the same stream, with thcoretical guarantees (Appendix A.2
Preliminaries
In this section, formally introduce the online change point detection problem (Section 3.1 and recall kernel-based two sample testing together with its RFF-baseed approximation (Section 3.2
3.1 Problem statement
We consider data stream 11, X2.... observed online, where the X,-s are independent random variables taking values in Rd, with d arbitrary but fixed. Let IP, Q E MI == MM (Rd) and P + Q where Mt (IRd) denotes the set of all Borel probability measures on TR... We assume that there exists an 17 E N = (1. such that
P
for = 1.....77 for = 7 1, 2,
X,
IQ
The goal to stop the process with minimal delay as soon as 1 is reached, but not before. Note that may have 1) in which case the process should never be stopped. Formally, one wants to test
Ho X, ~ P for each
IS n and some IP E M
versus
IP 1Q
if stsn and some MT where P * Q if < 1
H1n Bn < n s.t. X,
for each n E N, until a local null is rejected. A secondary aim, once a local null has been rejected, to accurately estimate 7). Solving the aforementioned problems boils down to constructing an extended stopping time N, which, in a sense we make precise in Section 4.3 3 is close to π). Let F, (X, s 1,....t) ... be the natural filtration generated by the X.'s 's up to time t and recall that a random variable N is an extended stopping time if (i) N takes vales in N U {co} and (ii) for each t N the event (N < t) F-meeuurable.
Minimizing the distance between and N is analogous to maximizing the power of a particular sequential testing procedure, and it is therefore natural impose some conditions on the sequential testing analogue of statistical size; we recall the two most frequent ones in the following. In the sequel, let Py be the joint distribution of (X1)s20 when (n k} (k N), and let E, be the expectation under this distribution.
1.
The average run length until a spurious rejection under the global null should be bounded from below by a chosen quantity (36). Specifically, for given y > 1 should hold that
[N][N] 2 7.
(I)
3

---

2.
The uniform false alarm probability should be bounded from above by chosen quantity [30]. Specifically, for given a E (0, 1) should hold that
(N 00) S
We show in Section 4.3 that Online RFF-MMD is able to satisfy either of the conditions 1
3.2 Fast kernel-based two sample tests
To resolve the change point detection problem (Section 3.1 we embed fast two sample tests based on RFF approximations to the MMD into particular sequential testing scheme. In this section, we briefly recall the MMD statistic and its RFF approximation.
Let H. a reproducing kernel Hilbert space (RKHS; [2] (56) on R with (reproducing) kernel K _d x IR + R. Denote by (upp = {AA E ( A(A) > 0f the support of Borel measure A on IRd, where A denotes the closure of a set A and o (IR)) the Borel o-algebra on Rd. Throughout the article, we make the following assumption on the kerne::
Assumption 1. The kernel K Rd R I is non-negative, continuous, bounded (3B >> 0 s.t. SuPxERs K (x, x) & B), translation-ivvrrinn (K (K(x y) = v0(x - for some positive definite Rd R), and characteristic (supp(A) A) I with (xx)) = j-e-t xdA(w)).
To simplify exposition, we also assume that K(0,0) = 1, which can be achieved by scaling any bounded kernel. The conditions in Assumption [ are satisfied by several commonly used kernels, including the Gaussian kernel, mixtures of Gaussians, inverse multi-quadratic kernels, Matérn kernels, Laplace kernels, or B-spline kernels (55). Assumption permits to approximate the respective kernel function by ditte--imessionll feature maps through Bochner's 's theorem (elaborated below), which, in turn, allows the effective online estimation of MMD detailed in Section 4
[
To any P E &Mt. one can associate the kernel mean embedding μx (P) E Hg, taking the form
/
px (P)
JEz X(.x))d(xx)
where the integral is meant in Bochner's sense [TO Chapter II.2]. The continuity and boundedness
assumptions ensure the existence of (xxPP) for any P E M [55] Proposition 2]. Expression (3) gives rise to the MMD, which quantifies the distance between two measures P, Q E MM via the distance between their mean embeddings in terms of the RKHS norm, and takes the form
MMDx [IP, Q] = (P) Px (Q) IK
Crucially, the characteristic assumption ensures that is injective and that the MMD metrizes the space M [55] Theorem 9], implying MMD,
Q
0 iff. F Q. Given samples
XI,...,,, P and YI...., Ym iid. Q with associated empirical measures P., =: X and
@m =: Yi.m. respectively, the squared plug-in estimator of MMDx [IP, Q] takes the form
(MMDx{ [X Isn; ===m)))==11mm
|k (Px)- FK
2m
=
K(, X,)
Σ K(.Y,
MK
n2
1=1
Hx
2
K(X, X,) m
KYY,
K(X, Yj).
(5)
The computation of (5) costs ((max(mm n)) rendering its use in an online testing procedure computationally infeasible.
Random Fourier features [45 54 alleviate this bottleneck in the offline setting: we recall the method in the following. For some E Rd write (x) e -i'x where = I By Bochner's theorem,
K(x,y) = 1b(x - y) / e - (x- (x->) Eura [Sw (x) Sw (y)*). gd
For E Ie (e,KK( a - IR denotes the map x' K(X,xx)

---

where denotes the complex conjugate and, using that (), = 1. one has that A E M As A and K are real-valued, Euler's identity implies that f fe- (x-Y) dA(w) = cos (w (x y)) dA(w).
Therefore, using that cos(a 3) cos cos 3 + sin oisin 3, picking some N, and sampling wh...,wwp A. low variance estimator for K (x, is given by
1
y(x,y) (2x (x), 2x (y)) where 2K (x)
((in(ww]x), x))) RR (6)
VF
By noting that K IR x Rd R is the kernel associated with the RKHS H R22r, we may approximate (5) by
MMD R X Yiml 1| (P..) Mg (za)
1
1
Σ kx (x 1=1
R X1)
(7)
Hx
Importantly, as the mean embeddings 7 are Euclidean vectors, their distance can be computed with the standard Euclidean norm. This leads to statistic which can computed in linear time and updated in constant time, allowing its use for sequential testing.
Online change point detection via random Fourier features
In this section, present our proposed stopping time for resolving the change point detection problem. In particular, we give a precise definition in Section 4.1 an efficient algorithm Section and theoretical guarantees in Section 4.3
4.1 The RFF-MMD stopping time
The intuitive construction of our RFF-MMD stopping time is as follows. We begin by choosing an r E N and kernel K, and construct its RFF approximation (6) using random features. For every 2, having observed data {X (........ X, we consider log, n possible sample splits of the domain {1. .......R. n) at locations n 2 with j = 0, ... [log2 n. 1. For every such split, we approximate
the MMD between the two samples using 7 change declared the first n for which least
one such statistic, appropriately normalized so that it is (1()) under its local null, is larger than
given threshold. Formally, we have
[log(10)-11
V 22 (2((-22)
25)
= = inf
n 2 2
U j=0
MMD & (X ( ((n-2((()))))) +))m) > An
(8)
where {Ap n N) is a non-decreasing sequence that we make precise in Section 4.3 taking
requirements [ or (2) into account.
The first of exponential grid in online change point detection appears be due Lai 29
Recently, similar techniques have been used by Yu [63]. Kalinke et al. [23. Moen (39]. The dyadic grid used in (8) has advantages. First, only logarithmic number of tests must be performed with each new observation. Second, the grid is sufficiently dense, so the obtained stopping time
has essentially the same behavior as the computationally infeasible variant, which considers every possible candidate change point location.
4.2 The REF-MMD algorithm
We now present efficient implementation of (8) and analyze its runtime and space complexity. We show the pseudo code of our proposed method in Algorithm [ see also Example and Figure[[oor summary. The details are as follows. For each new observation X,, create new window W. storing 2 = 2x (X,) and = 1 (Lines 4 The window W is then added to the list of all windows W (Line 5). The remaining algorithm has two main parts.
1.
Change point detection. To detect changes, we iterate [W] - dyadic points i (Line 6 and, for each i, merge the feature maps coming before and coming after i (along with their counts) to compute the MMD statistic (Lines 7... If the statistic exceeds the threshold (Line TO see Section for its value), change is flagged and we drop the data coming before the change.
5

---

2. Structure maintenance. To set up and maintain the dyadic structure. we merge windows that have the same counts (Line by first summing their 2-s and their c-s (Lines [7 [ and then replacing them in the list of windows W "accordingly (Line T9 We note that pop removed the windows beforehand.
Algorithm 1 Online RFF-MMD change point detection
Input: Stream X1, X2.... ... and sequence of thresholds {), e NJ.
Output: Changepoint location and detection time.
1: W < empty list
2: for X2 E X1, X2.... do
Main loop
3:
W. t (X(),)
4:
W.c t
5:
W f- Wappped W)
6:
for i E ,..... I - do
Detect changes
C1 - Σ 1=1+1 Wj.c
7:
8:
02 2i=1 Wj.c
MMD; K + 1 E W - c2 En= W3
9:
10:
if
C1 MMD X then
11:
print Change detected at element XN; most likely at position i. return
12:
13:
while [W] 2 2 do
Maintain exponential structure
W1 pop W
15:
W2 + pop W
if W1.c W2.c then
17:
W.c t Wi.c W2.c
W.z +- Wi.2 + W2.z
19:
W + W.append(W))
else
21:
W + W.appen((Wi).appedddd
22:
break
We now analyze the runtime and space complexity of Online RFF-MMD. For each insert operation, Algorithm performs three steps, which we analyze independently.
1. Setup. The computation of & (X,), defined in (6). requires computing 2r trigonometric functions of d-dimensional inner products and thus (rd)..
2. Change point detection. The dominating term is computing MMD g. which requires ((M)r) computations. Repeating the computation [W] times leads to a cost of ((W))r) The calculation of the threshold is in (1), which gives overall cost of ((W))2) However, we note that memoization of all sums allows to implement the change point detection in a single sweep over W (at each step, the attributes of one W W subtracted from one sum and added to another sum) and thereby reduces the runtime complexity to ([W)r).
3. Maintenance. In the worst case, O(W)) merge operations need be performed. Fach merge requires (rr) operations, which yields a total cost of O(M])))
Adding the results obtained in steps 1.-3. shows that the algorithm has an overall runtime complexity of O([)r) = Or log n) per insert operation. As the algorithm stores, for each W W, a number (W.c) and vector (W.z E "2",, the total space complexity when having observed samples is O(W)r) = (r log n.). We note that r is a fixed parameter in practice and thus constant.
The following Example [ and the corresponding Figure illustrate how Algorithm I operates upon observing the first samples N.....,X6..
Example 1. When observing the first element X1, the algorithm creates new window W, storing the feature map åx (X1) and that W has one element (c 1). Similarly, when observing X2, the algorithm creates new window W', storing (x())) and c= 1. As both windows, W and W have the same counts, the algorithm merges them into new window W, storing Ex (X1) åx (X2) and
= 2, thereby maintaining the dyadic structure. The algorithm proceeds in this manner, resulting

---

R
ix (X1)
c= 1
Merge
7
2 = 2x (X,) x (x(x(X))
Σ xx(Xi)
1
c=
o=
Mergo
8
(X))
Ex (X)) (X6)
ml
4
Figure 1: Schematic representation of the proposed algorithm upon observing the first elements.
Merging equal sized "windows" yields the division along dyadic points.
in the construction of the dyadic grid outlined in Section 4.1 For example, when observing X6. there are again two windows of size I, which the algorithm merges store total of two windows, one capturing .1. and the other one capturing Xs, X6. We recall that the observations themselves are never stored explicitly.
Before presenting out theoretical results in the following section, emphasize that Algorithm matches (8) that is, there is no approximation error.
4.3 Theoretical results
In this section, we analyze the theoretical behavior the RFF-MMD algorithm. We first study the behavior of the stopping time defined in (8) under the global null of no change. Theorems/ and
show that with an appropriately chosen sequence of thresholds the stopping time can be made to
attain, respectively, desired average run length T or desired uniform false alarm probability (
Theorem 1. Let N be the extended stopping time defined via {8) For any 1, if the sequence of thresholds satisfies A,, v2 + /2 (47 (27)) for all n E N, it holds that [N] %
Theorem 2. Let N be the extended stopping time defined via (8). For any (0, the sequence thresholds satisfies An 2 /2+ /2 (log(n/ax log (log2(n)) log (logg(2n)) for each n E N, it holds that (N < oo) S a.
emphasize that these guarantees do not depend on the number of random features used in constructing (6) and the bounds on the threshold sequences do not require any knowledge of the pre-change distribution.
Next, we study the detection delay incurred by when the threshold sequence is chosen to control the uniform false alarm probability some level (0, 1). In the following, we assume that the data take values in compact subset of R&d and denote the Lebesgue measure of by | The following result shows that with high probability, provided the number of RFFs is chosen sufficiently large, the detection delay incurred by (8) is bounded from above by quantity depending only the chosen the number of pre-change observations, and the squared MMD between the pre- and post-change distributions.
Theorem 3. Let be the extended stopping time defined via (8) with threshold sequence
(An E N} defined as in Theorem for a chosen E (0, 1). If supp (P) U supp (Q) C X
for some compact set X C CR, the quantities a, and MMD x [P, Q jointly satisfy
log (2n/a)
n 2 Ci (MMD [T, Q)
(9)
and the number of random features in is chosen so that
Vr C2 |x), |X), .) + /olo (2/a) (MMD [IP Q))
(10)

---

then with probability at least 1 - Ot, it holds that
log (2m/ a)
(N -) SIVC3
(1I)
(MMD& [P. Q1)
where C₁, C2 and C3 are absolute constants independent of a, and MMDx(E Q and, with
o² - Saa ||w|12 dA (w), we have put
h(d, (2) 2 2dg (2 + / 2d (a + + 16 2d [log (2 [x]] + 1)]"
which is likewise independent of T,, a, and MMD (P.Q)
Condition 4 can be interpreted as a signal strength requirement, measuring the strength according to the number of observations from the pre-change distribution and the squared MMD between I' and Q. The term (og(2n)(a reflects the cost of multiple testing when the data are drawn from P. Such requirements are unavoidable from the minimax perspective in the corresponding offline problem [63 42 and the discussion in Yu et al. [64] Section 4. suggests that the same is true for genuinely online change point problems.
The requirement on the number of RFFs in (10) depends on MMD x [P. Q] which is unknown in practice. However, if one assumes asymptotic setting with fixed distance between P and Q, and a 4 O, then (0)p suggests that the number of RFFs should be chosen as r = Ollg 1/a). To put this result into perspective, we compare it online change procedures having a window. Here, the optimal window length also depends on the distance between the pre- and post-change distributions 33 (59. However, choosing the window larger than this quantity can lead an increase in the detection delay. This is not the case for RFF-MMD: in practice, one may choose the number of RFFs large as possible subject computational constraints, and choosing larger number of RFFs does not negatively impact the detection delay.
Minimax optimality of RFF-MMD
Recall that with the conditions of Assumption T the underlying kernel characteristic and MMD K metrizes the space M Therefore, MMD P.P. Q 0 for any P * Q and we have that (II) guarantees that our stopping time (8) obtains finite detection delay, with high probability for any fixed alternative. Still, one may ask whether the detection delay is optimal. The following theorem
resolves this question and shows that the detection delay of RFF-MMD is essentially optimal from minimax perspective, up to logarithmic terms.
Theorem 4. For every kernel K Rdd x Rd + R satisfying Assumption D there is a constant Ck depending only K and absolute constants ao 30 E (0, 1) independent of K, such that for any S og it holds that
log (1/a) N n N
inf N P (o
sup P. 1>1
2 30
(12)
(MMDx [P, Q1)
7.EM
with the infinum being over all extended stopping times.
We remark that in the online change point detection literature 40 46). it is more common to study the expected risk of stopping time. For example, for fixed F. Q it is common to work with the so-called worst-worst-case average detection delay [37] of a given stopping time N, which is defined via
sup ess sup Ery (NN - n)} 1 n>1
However, in the absence of further restrictions, studying this quantity for the problem at hand does not seem possible. In fact, as long as p : P 8 ... & IP and Q Q @ ... & Q have a total variation distance smaller than 1, one can couple the given process and process where all X,'s are drawn from Q so that with non-zero probability the two processes have identical sequences. In this case, we either lose control of the null and a cannot be arbitrarily close to zero, or we maintain control over the null but with non-zero probability the detection delay is infinite.

---

Experiments
We collect our experiments on synthetic data in Section 6.1 and on the MNIST data set in Section 6.2 We refer to Appendix A.3 for additional experiments and numerical comparison of different thresholds for the stopping rule. To interpret the change point detection performance of the proposed method, compare its average run length (ARL) and expected detection delay (EDD) to the existing kernel-based methods presented in Table | For all experiments, we use the Gaussian kernel ((x. y) ->>|x-ylf with y set by the median heuristic [12] or its RFF approximation, depending on the algorithm. All results were obtained on PC with Ubuntu 20.04 LTS, 124GB RAM, and 32 cores with 2GHz each.
6.1 Synthetic data
In this section, we evaluate the runtimes of different configurations of the proposed Online RFF-MMD algorithm and compare its change point detection performance on synthetic data to that of other kernel-based approaches.
Runtime. Figure 2 summarizes the runtime results of Algorithm with the number of random Fourier features r E {10. 50, 100, 500, 1 100) and for streams of length up to n = 250 000. The experiments verify the Orr log n)) runtime complexity of the proposed algorithm, derived analytically in Section 4.2
We note that the dependence on is linear; we consider only.
10
50
100
++-
500
1000
Time per insertion (s)
0.00020
Total runtime
40
0.00015
20-
0.00010
50000
100000
150000
200000
250000
50000
100000
150000
200000 250000
Number of observations n
Number observations
Figure 2: Average runtime (10 repetitions) of RFF-MMD per insert operation (left) and total (right).
ARL vs. expected detection delay. To illustrate the EDD for a given target ARL, we reproduce the experiments of Wei and Xie (59] Figure 4], also taking our method into account. Specifically,
consider the pre-change distribution = -O20 I2o) and set the parameters of each algorithm as follows. Matching the settings of the reproduced experiment, for online kernel CUSUM; for Scan B-statistics and NewMA, we set Bo 50. The remaining parameters of NewMA then follow from the heuristics detailed by the authors (24]. For Online RFF-MMD, we set = 1 100. We compute the thresholds for given target ARL by processing 10 (target ARL) samples with each algorithm, repeating for 100 Monte Carlo (MC) iterations, and computing the 1 1/ (target ARL) quantile of the resulting test statistics. For approximating the EDD of each algorithm, we draw 64 samples from respectively, before sampling from Q: we report the average over 100 repetitions. OKCUSUM and ScanB additionally receive 1 (000 samples from upfront, to use as a reference sample. For NewMA, we process 400 additional samples from P for both the MC estimate and the EDD experiment, to reduce its variance.
choose Bmax 50 and N 15
Having processed the indicated number of samples from P. we then start sampling from either mixed normal, a Laplace, or Uniform distribution. Figure coolects the average detection delay; the respective post-change distribution Q is given on top. The results show that our algorithm achieves smaller detection delay than the competitors for all considered post-change distributions, sometimes by a large margin.
4 All code replicating our experiments is available in the supplement and at https: :/tp::///tttuie /ttp://tttthhhom//. FlopsKa/rff http:/fff-ccagg--etttttttttoo

---

Online RIF MMD
OKCUSUM
ScanB
NewMA
0.7N o Imn) 0,30)
Laplace oj
Uniformí o², o2)
20
Detection delay
X0- 10
3,0
3.5
4.0
4.5
5.0
3.0
3.5
4.0
4.5
5.0
3.0
3.5
4.0
4.5
5.0
10g ARL
1og
ARL
Jog ARL
Figure 3: Average detection delay from P P= ==N(020 I20) to the Q indicated on top (d = 20, o = 2).
6.2 MNIST data
In this section, we interpret the MNIST data set [9] as high-dimensional data stream, similar to Wei and Xie [59] Figure 7], with the goal of detecting a change when the digit changes from 0 to a different digit. The experimental setup matches that of Section 6.. but with d = 784. Figure collects our results; the results for the digits 4-6 are similar and in Appendix [A.3.] Similar to Figure 3 the proposed Online RFF-MMD algorithm shows very good performance. In particular, it achieves a lower EDD than all tested competitors throughout.
Online RFF MMD
coof OKCUSUM
ScanB
+
NewMA
MNISTI
MNIST2
MNIST3
wage
EDD
4.0
5.0
4.0
5.0
3.5
4.0
5.0
Log ARL
log ARL
logio ARL
Figure 4: Average detection delay from MNIST digit 0 to digits 1, 2, and 3 (left to right).
Limitations
As with all kernel-based tests, the choice of kernel impacts the power of the test. While our theoretical guarantees (Section (4.)) hold for any kernel satisfying Assumption [ and do not require any pre- change data, one usually selects the kernel or its parameters using a few available samples in practice. While kernel optimization is not the focus of this work, there exist works 20 34 50 (6 to (approximately) achieve this goal; it is interesting future work to tackle this problem in the sequential setting. A separate future direction is considering non-i.i.d. data, for example, data that is strongly mixing [6] or data exhibiting functional dependence [60].
Acknowledgments and Disclosure of Funding
The authors thank Zoltán Szabó and Tengyao Wang for helpful discussions. FK thanks Georg Gntuni and Marius Bohnert for exchanges the algorithm's implementation. This work supported by the pilot program Core- Informatossas of the Helmholtz Association (HGF).
References
[1] Abdalbassir Abou-Flailah, Valérie Gouet-Bruned and Isabelle Bloch. Detection of abrupt changes in spatial relationships in video sequences. In International Conference Pattern
10

---

Recognition Applications and Methods (ICPRAM), pages 89 89-106, 2015.
[2] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathemati- cal Sociery, 68:337-404, 1950.
[3] Michèle Basseville and Igor V. Nikiforov. Detection of abrupt changes: theory and application. Prentice Hall, 1993.
[4] Alberto Bietti, Francis R. Bach, and Arshia Cont. An online EM algorithm in hidden (semi-) Markov models for audio segmentation and clustering. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1881-1885, 2015.
[5] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities. Oxford University Press, 2013.
[6] Richard C. Bradley. Basic properties of strong mixing conditions. A survey and some open questions. Probability Surveys, 2: 2:107-144, 2005. Update of, and a supplement to, the 1986 original.
[7] Hao Chen. Sequential change-poing point detection based on nearest neighbors. The Annals of Statistics, 47(3):1311-1407, 2019.
[8] Lynna Chu and Hao Chen. Sequential change-point detection for high-dimensional and non- Euclidean data. IEEE Transactions on Signal Processing, 70:4498 4511,, 2022.
[9] Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, pages 141-142, 2012.
[10] Joseph Diestel and John J. Uhl. Vector Measures. American Mathematical Society, 1977.
[11] Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of conditional dependence. In Advances in Neural Information Processing Systems (NeurIPS), pages 489-496, 2007.
[12] Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa, Large sample analysis of the median heuristic. Technical report, 2018.
[13] Louis Gordon and Moshe Pollak. An efficient sequential nonparametric scheme for detecting change of distribution. The Annals of Statistics, 22(2):763-804, 1994.
[14] Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf. and Alexander Smola. kernel two-sample test. Journal of Machine Learning Rexearch, 13(25):723-773, 2012.
[15] Robert Grossman, Michal Sabala, Anushka Aanand, Steve Eick, Leland Wilkinson, Pei Zhang, John Chaves, Steve Vejcik, John Dillenburg, Peter Nelson, et al. Real time change detection and alerts from highway traffic data. In ACM/IEEE Conference on Supercomputing (SC), pages 69-69, 2005.
[16] Omar Hagrass, Bharath K. Sriperumbudur, and Bing Li. Spectral regularized kernel two-sample tests. The Annals of Statistics, 52(3): 2024.
[17] Omar Hagrass, Bharath K. Sriperumbudur, and Bing Li. Spectral regularized kernel goodness- of-fit tests. Journal of Machine Learning Research, 25(309):1-22, 2024.
[18) Omar Hagrass, Bharath Sriperumbudur, and Krishnakumar Balasubramanian. Minimax optimal goodness-of-ft testing with kernel Stein discrepancy. Bernoulli, 2025. (accepted; preprint:
hwtps/wwwww.//a/////...o/ 08278)
[19] Douglas M. Hawkins and Qiqi Deng. A nonparametric change-point control chart. Journal of Quality T 1252)3165-173, 2010.
[20] Wittawat Jitkrittum, Zoltán Szabó, Kacper Chwialkowski, and Arthur Gretton. Interpretable dis- tribution features with maximum testing power. Advances Neural Information Processing Systems (NeurIPS), pages 181-189,200

---

[21] Wittawat Jitkrittuum, Zoltán Szabó, and Arthur Gretton. An adaptive test of independence with analytic kernel embeddings. In International Conference on Machine Learning (ICML), pages 1742-1751, 2017.
[22] Wittawat Jitkrittum, Wenkai Xu, Zoltán Szabó, Kenji Fukumizu, and Arthur Gretton. A linear-time time kernel goodness-os -f-fit test. In Advances Neural Information Processing Systems (NeurIPS), pages 262-2722222 222-271, 2017.
[23] Florian Kalinke, Marco Heyden, Georg Gntuni, Edouard Fouché, and Klemens Böhm. Maxi- mum mean discrepancy on exponential windows for online change detection. Transactions on Machine Learning Research, 2025.
[24] Nicolas Keriven, Damien Garreau, and Iacopo Poli. NEWMA: new method for scalable model-free online change-pon point detection. IEEE Transactions on Signal Processing, 68:3515- 3528, 2020.
[25] Albert Y. Kim, Caren Marzban, Donald B. Percival, and Werner Stuetzle. Using labeled data to evaluate change detectors in multivariate streaming environment. Signal Processing, 89(12): 2529-2536, 2009.
[26] Katerina Kosta, Rebecca Killick, Oscar Bandtlow, and Elaine Chew. Dynamic change points in music audio capture dynamic markings in score. In International Society for Music Information Retrieval Conference (ISMIR), 2017.
[27] Katerina Kosta, Oscar F. Bandtlow, and Elaine Chew. MazurkaBL: score-aligned loudness, beat, and expressive markings data for 2000 Chopin Mazurka recordings. In International Conference on Technologies for Music Notation and Representation (TENOR), pages 85-94, 2018.
[28] Mehmet N. Kurt, Yasin Yilmaz, and Xiaodong Wang. Real-time nonparametric anomaly detection in high-dimennional settings. IEEE Transactions Pattern Analysis and Machine Intelligence, 43(7):2463-2479 2020.
[29] Tze Leung Lai. Sequential changepoint detection in quality control and dynamical systems. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 57(4):613-644, 1995.
[30] Tze Leung Lai. Information bounds and quick detection of parameter changes in stochastic systems. IEEE Transactions on Information Theory, 44(7):2917-2922 1998.
[31] Céline Lévy-Leduc and François Roueff. Detection and localization of change-points in high- dimensional network traffic data. The Annals of Applied Statistics, 3(2):637-662, 2009.
[32] Shuang Li, Yao Xie, Hanjun Dai, and Le Song. M-statistic for kernel change-point detection. In Advances in Neural Information Processing Systems (NeurIPS), pages 3366-3374, 2015.
[33] Shuang Li, Yao Xie, Hanjun Dai, and Le Song. Scan B-statistic for kernel change-point detection. Sequential Analysis, 384))503-544, 2019.
[34] Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J. Sutherland. Learning deep kernels for non-parametric two-sample tests. In International Conference on Machine Learning (ICMI., pages 6316-6326, 2020.
[35] Song Liu, Makoto Yamada, Nigel Collier, and Masashi Sugiyama. Change-pont point detection in time-series data by relative density- estimation. Neural Networks, 43:72 83, 2013.
[36] Gary Lorden. On excess the boundary. Annals of Mathematical Statistics, 11:520-527. 1970.
[37] Gary Lorden. Procedures for reacting to change in distribution. Annals of Mathematical Staristics, 42:1897-1908, 1971.
[38] Colin McDiarmid, On the method of bounded differences. Surveys in combinatorics, 141(1): 148-188 1989.
12

---

[39] Per August Jarval Moen. A general methodology for fast online changepoint detection. Technical report, 2025. / 09573
[40] George V. Moustakides. Optimal stopping times for detecting changes in distributions. The Annals of Statistics, 14(4):1379-138)) 1986.
[41] Carlos Misael Madrid Padilla, Haotian Xu, Daren Wang, Oscar Hernan Madrid Padilla, and Yi Yu. Change point detection and inference in multivariate non-parametric models under mixing conditions. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[42] Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal nonpara- metric multivariate change point detection and localization. IEEE Transactions on Information Theory, 68(3):1922-1444, 2021.
[43] Ewan S. Page. Continuous inspection schemes. Biometrika, 41:100-115, 1954.
[44] Moshe Pollak and David Siegmund. Sequential detection of change in a normal mean when the initial value is unknown. The Annals of Statistics, 19(1)394-4166 1991.
[45] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), pages 1177-1184, 2007.
[46] Ya' acov Ritov. Decision theoretic optimality of the CUSUM procedure. The Annals of Statistics,
1 18(3):146441490) 1990.
[47] Gaetano Romano, Idris A. Eckley, Paul Fearnhead, and Guillem Rigaill. Fast online changepoint detection via functional pruning CUSUM statistics. Journal of Machine Learning Research, 24 181):1-36, 2023.
[48] Gaetano Romano, Idris A. Eckley, and Paul Fearnhead. log-linear non- non-parametric online changepoint detection algorithm based on functional pruming. IEEE Transactions on Signal Processing. 72:594 6066 2024.
[49] Gordon Ross. Parametric and nonparametric sequential change detection in R: The cpm package. Journal of Statistical Software, 66:1-20. 2015.
[50] Antonin Schrab, Benjamin Guedj, and Arthur Gretton. KSD aggregated goodness-of-fit test. In Advances in Neural Information Processing Systems (NeurIPS), pages 32624-32638, 2022.
[51] Antonin Schrab, Ulmun Kim, Benjamin Guedj, and Arthur Gretton. Efficient aggregated kernel tests using incomplete U-statistics. In Advances in Neural Information Processing Systems (NeurIPS), pages 18793-18807, 2022.
[52] David Siegmund. Sequential analysis: tests and confidence intervals. Springer, 2013.
[53] Alexander Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A Hilbert space embed- ding for distributions. In Algorithmic Learning Theory (ALT), pages 13-31, 2007.
[54] Bharath K. Sriperumbudur and Zoltán Szabó. Optimal rates for random Fourier features. In Advances in Neural Information Processing Systems (NeurIPS), pages 1144-1152, 2015.
[55] Bharath K. Sriperumbudur. Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert Lanckriet. Hilbert space embeddings and metrics on probability measures. Journal of Machine Learning Research, 11500) 2010.
[56] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer, 2008
[57] Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Reynaud-Boured Optimal change-point detection and localization. The Annals of Statistics, 5144):188-11610, 2023.
[58] Haoyun Wang and Yao Xie. Sequential change-point detection: Computation versus statistical performance. Wiley Interdisciplinary Reviews: Computational Statistics, 16(1):e1628, 2024.
[59] Song Wei and Yao Xie. Online kernel CUSUM for shange-point detection. Technical report,
2022. https: //tpx//iivv///////////////////aa org/ htte//bbs22211...111 15070
13

---

[60] Wei Biao Wu. Nonlinear system theory: another look at dependence. National Academy of Sciences of the United States of America, 102(40;141500144554 2005.
[61] Ping Yang, Guy Dumont, and John M. Ansermino. Adaptive change detection in heart rate trend monitoring in anesthetized children. IEEE Transactions on Biomedical Engineering, 53 (1 (11):2211 1222, 2006.
[62] Yasin Yilmaz. Online nonparametric anomaly detection based on geometric entropy mini- mization. In IEEE International Symposium on Information Theory (ISIT), pages 3010-3014, 2017.
[63] Yi Yu, A review on minimax rates in change point detection and localisation. Technical report, 2020. https://arxiv. htwp://w...gggaa////eaaa// 01857
[64] Yi Yu, Oscar Hernan Madrid Padilla, Daren Wang, and Alessandro Rinaldo. A note on online change point detection. Sequential Analysis, 42(4):438 471, 2023.
[65] Vadim Yurinsky. Sums and Gaussian vectors. Springer, 1995.
[66] Wojeiech Zaremba, Arthur Gretton, and Matthew Blaschko. B-test: non-parametric, low variance kernel two-sample test. In Advances in Neural Information Processing Systems (NeurIPS), pages 755-763, 2013.
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction motivate and summarize the theoretical and experi- mental results that we establish in the article.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It fine include aspirational goals motivation as long as it is clear that these goals attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We make all our assumptions explicit in Assumption and in the statements of the results. One theoretical difference to the offline setting is additionally elaborated right after Theorem 4 A runtime analysis is provided Section 4.2 with a comparison to existing kernel-based approaches in Table I We elaborate limitations w.r.t. kernel choice in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
14

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with a few runs. In general. empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance the approach. For example, a facial recognition algorithm may perform poorly when imgge resolution is low or images are taken in low lighting. a speech-to-text system might not used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The assumptions on the kernel function are listed in Assumption lists the additional assumptions that it requires. All our proofs are in the appendix, where we also collect the external statements that we use, ensuring self-completeness.
[and and each statement
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We include pseudo code describing efficient implementation of our algorithm as Algorithm[[] the corresponding Figure gigves additional intuition. Further, we elaborate the we extend existing benchmarks, to simplify comparison and reproducibility. Additionally, all source code replicating our experiments is available online (see footnote 4 and in the supplement.
experimental setup in Section where
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution novel architecture, describing the architecture fully might
15

---

suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
the case of
Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We include a link to the repository hosting our source code (see footnote 4 and also make it available in the supplement. The code contains scripts and additonal instructions for reproducing all results and figures.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nipsscc/ppb))) Geidde/CoodeSubnng ssi ssioniolccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurIPS code and data submission guidelines pottps://nipas cc/ mablic/guidessCodeSSii wttpuummmmiiiiooooooi.oomo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We elaborate the experimental setup in Section 6 where we also specify all param- eter choices for the proposed algorithm and the tested competitors. Our results extend known benchmarks.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yss]
Justification: We include the estimated 95%-errro quantile in runtime plots (Figure but these are negligbly small. The remaining experiments show averages over 100 repetitions. respectively. Here, is common for these experiments in the literature, do not include error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e-g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric етror bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [Yes]
Justification: We make the resources used for our experiments explicit at the end the introduction to Section 6 Explicit runtime results are in Figure 2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics httppp///eerrrpppcccc/a/a//aaaaa
Answer: [Yes]
17

---

Justification:
The research conducted in this work complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Our proposed change detection algorithm does not have any direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
18

---

Answer: [Yes]
Justification; We reference all competitors that we compare against in the main part of the paper; in particular, we summarize these with references in Table 1 The MNIST data set that we use is referenced in Section 6.2 HASC is referenced in Section A.3.2 and the MazurkaML data set is referenced in Section A.3.3
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release all code replicating our experiments online (see footnote 4 and in the sup- plement. The code contains detailed instructions for reproducing all results in the RRAADE.mdd file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human
subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals
19

---

(or an equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethies and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper does not involve LLMs in any direct way.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy [ttees///eerrrreeccc///ooorrreee for what should or should not described.
20

---

A Appendix
This appendix is structured follows. We detail the extension of Online RFF-MMD take known or observed pre-change distribution into account in Appendix A.. In particular, we show that in these settings tighter thresholds are possible. Appendix A.2 shows how to adapt our algorithm to detect multiple change points and gives corresponding guarantees. Additional numerical results of MMD-REE RFF are in Appendix [A.3] we include numerical results w.r.t our tighter thresholds in Appendix A.3.5] Appendix A.44 collect all our proofs, with auxiliary results in Appendix A.5 and external statements in Appendix A.6
A.1 Known or estimable pre-change distribution
In this section, we discuss practical extensions of Online RFF-MMD when additional information about the pre-change distribution is available. Specifically, in Section A.I.II. we show how the algorithm can be adapted to settings in which (i) one has access to historical data known to be from the pre-change distribution, (ii) knows the pre-change distribution exactly. In Section we describe how this additional information allows sharpening the thresholds proposed in Theorems and in the main text.
A.1.1 Incorporating information of the pre-change distribution
To begin with, we consider the setting in which, for some v E N, historical data X X- K-p+1..... Xo known to be from the (nonetheless unknown) pre-change distribution is available. This setting has been studied in the literature from both the parametric [44] and non-parametrie (59) perspectives. It straightforward to extend the Online RFF-MMD stopping time defined in the main text to take advantage of the additional information. Intuitively, for each local test one may prepend the historical data to the block of data taken be from the pre-change distribution. More formally, the following stopping time can be used:
[oga(n))
27 (n 21) n+
N inf n 2 2
MMD k (X(-441)(n-21); ((n-2+ An
This stopping time can be implemented similarly to Algorithm I and such an implementation features the same time and space complexity as the original algorithm.
Next, we consider the setting in which the pre-change distribution IP is known exactly. With this additional information, rather than performing local two sample tests, may perform local one sample tests where the RFF approximation to the mean embedding of the data's 's empirical distribution is compared to the RFF approximation to the mean embedding of P.. More formally, the following stopping time can be used:
(n)1 U
N inf
n 2
20 MMD & [TP, X(nnXxnn2- (n-22 An
The exact knowledge of P permits a precise approximation or the exact computation of Ex-e [&x (X) wi....,,,,) wy]. given Wi,...,Wy sampled from A. Again, this stopping time can be implemented similarly to Algorithm [ original algorithm.
enjoying the same time and space complexity as the
A.1.2 Sharper thresholds through knowledge of the pre-change distribution
Access to additional information about the pre-change distribution paves the way to sharpening the thresholds proposed in Theorems I and Indeed, although Theorem 4 suggests the thresholds proposed in the main paper are unimprovable up to constants, in practice these thresholds will be quite conservative as they completely agnostic to the distribution of the data.
The main tool for proving Theorems I and 2 Lemma 5 which controls the tail behavior of the tests performed by Online RFF-MMD under their respective Tocal nulls. With additional knowledge of the pre-change distribution, Lemma can be significantly sharpened by taking the second moment the feature map into account. To that end, we have the following result.
21

---

Lemma 1. Given two independent samples , and (Yi...., ... each with mutually independent entries drawn frawn.from some P E MM for any ε >> 0, it holds that
P(MMD, ( Y1ml > I 4ex (-2 min min(m, n)e? 102 +
where 8² Ex~p [K (X, Ex [K (X,
Lemma
D Tallows the following improvements of Theorems and
Corollary 1. For any y > 1, replacing the thresholds in Theorem thresholds
with the scale dependent
2v/52(77) +ōf(7),
Ang = /min (2) 22)
n nEN, i (ng)(n)
(13)
f(7) = 2 log( 16y 1ogz
it holds that [N] Y where N is as defined in
(8)
Corollary 2. For any a E (0,1), replacing the thresholds in Theorem with the scale dependent thresholds
2/2f2 (a, + +ōf(a, n),
Anj V /min(2), (2in(2), 2
n E N. s log2(n)
f(a, n) /2(log(4//o)))) 2 log(log, + log
it holds that Po (N < <00 S a where is as defined in
To put the above results in context, detail Corollary On large scales (large j-s), where detections tend occur, the scale dependent thresholds behave approximately like ā / log which differs from the threshold used in Theorem byy a factor ō. Therefore, when is significantly smaller than 1, the thresholds in (I3) will be sigmificantly smaller than those suggested by Theorem []] As the kernel is assumed to be bounded from above by 1, these smaller thresholds generally occur.
(27)).
A.2 Online detection of multiple change points
In this section, we explain how the algorithm in the main part can be extended to detect multiple
change points in an online fashion. Indeed, consider the setting where data X1, X2, ... are observed sequentially. There is sequence of integers (7h M with nou = 0 and Th < M for each & E N. and a sequence of measures (Qa)een each M with Qs + Q++1 for each N such that for each / E N the data are distributed according to
Q1 Q2
if
70 1 S m <
if
X,
Consider running Algorithm on this data stream using the threshold sequence given in Theorem As soon as a change is detected, say at location we re-start the algorithm at X,+1- However, the index on the threshold sequence maintained. More precisely: having detected a change time n, at the (n -)-th iteration (for j > 1), we construct local statistics over the interval {n + 1..., + j) according to Section 4.1, however the local statistics continue to be compared with the threshold Antj. We are able to prove the following guarantee on the change point locations recovered in this way:
Theorem 5. For any deterministic time T values in f1....,T). T). Write öş = min (7) 77k-1: Mh+11 Th) for = 1,..., M and δm min (ljM 115-1, T mps) for the effective sample size associated with the k-th change point location. For some a (0, 1), let M be the number of change points detected up to time T using the threshold sequence given in Theorem 2 and the procedure described above, and let , ii be their locations. If UM supp (Q&) S X for some compact set X C TR...
let M denote the number of Mj-S taking
log (2T/a)
8% 2 C1 (MMDk (Qu, Qb+1l)²
for k == 1,..,,M.
22

---

and the number of random Fourier features is chosen so that
Vr 2 C2 (X], + 22lo (2/a)
(ming= I...M MMD K (Qu, Qk+11)²
then with probability at least 1 22 it holds that M M and
Tee nK S Th + C3 log (2T/a)
for k= -
(MMDk (Ck, Qk+1l)²
Here hid, .)) is as given in Theorem 3, and C₁, C2 and C3 are absolute constants independent of a and the sequences {ōx]am km1...,................ I...,M and (MMDx k (Qu,
A.3 Additional experiments
In this section, we summarize additional numerical results. The MNIST results with the MC threshold as in the main text are in Section [A.31] We include results obtained without threshold estimation in Section A.3.4 A comparison of the distribution dependent and distribution-fie free bounds is in Section A.3.5 Numerical studies on the Human Activity Sensing Consortium (HASC) and on the MarzukaBL, data sets are in Section A.3.2 and in Section A.3.3 respectively.
A.3.1 MNIST data digits 4-9
In the following Figure we collect the change detection performances the algorithms of Table T on MNIST data, where the digit changes from 0 to one of 4-9; the results on the other digits and the experimental setup are in Section 6.2 As in the corresponding experiment in the main part of this article, our proposed Online REF-MMD algorithm consistently achieves the lowest expected detection delay, highlighting its good practical performance.
Online RFF MMD
-..... OKCUSUM
-
ScanB
+
NewMA
Q = MNIST4
= MNISTS
N = MNIST6
Q MNIST7
MNISTS
MNIST9
Me No
HDD
5
5
5
3
5
log1o ARL
logio ARL
logio ARL
log10 ARL
log ARL
log ARL
Figure 5: Average detection delay from MNIST digit 0 to digits 4-9 (left to right).
A.3.2 HASC (Human Activity Sensing Consortium) data
This section collects our experiments on the Human Activity Sensing Consortium (HASC; available
//hasc. httt:://hasc.jj/hcc0000 hp/hc2011/ challenge 2011 data set, which is also considered in Liu et al. (35), Li
al. 33 Wei and Xie [59] As in Wei and Xie (59]. consider the change from walking to staying of participant 101. For preprocessing, we order the corresponding csv-files in the data set lexicographically. omitting the first 1 596 (detailed below) samples of walking, and then concatenating 100 walking observations and 100 staying observations to obtain a total of 10 data sets (with d = 3) with a single change point each. For obtaining the thresholds for the proposed Online RFF MMD, NewMA, Scan-B statistics, and OKCUSUM change detection algorithms, we proceed as elaborated in Section 6.1 that is, we use Monte Carlo approach with a 0.1 on all 10 walking data sets. As per Wei and Xie [59] for ScanB and OKCUSUM, we set the number of windows N = 14 and the window length w = 114, implying that both algorithms receive 14. 114 = 596 samples from walking upfront. Likewise, we process 1 596 elements with NewMA upfront. All kernel-based approaches use the (approximated) Gaussian kernel with the ? > 0 parameter set by the median heuristic.
23

---

For the density ratio-based (i.e., non-kemell RuLSIF Algorithm-wiie showed the best performance HASC in Liu al. [35-- we use the python changepoynt implementation and consider the 12-norm of each three-dimensional observation We then obtain the change scores for [
the full data set and select the point with the highest score as predicted change point, as done in Liu et al. 35 Section 4.2]. To match their setup, we set the window length to 50, the number of windows to 10, and a 0.1. Additionally, due to the large number "too early" cases reported in this setup, we introduce an offset and take the window length to be equal to the offset. In this setup, we consider the point with the highest score plus the offset as reported change point. A "miss" can not occur, due to the scores reported to RuLSIF having at least one maximum. Table collects our results.
Table 2: Comparison of change detection algorithms on 10 data sets derived from the HASC data set. "Too early" refers to the number of times algorithm reported change point before the actual change occurred. "Miss" reports cases in which no change was reported.
Algorithm
Average delay
Too early
Miss
Online REF MMD
21.86
NewMA
34.25
1
5
ScanB
31.20
0
0
OKCUSUM
17.44
0
RuI.SIF
4.50
8
0
RuI.SFF (offset -30)
20.38
2
0
RuLSIF (offset = -00)
35.0
3
0
RuLSIF (offset -50)
39.2
0
We emphasize that in the above all algorithms except for the proposed and RuLSIF receive 1 596 samples upfiront, to use as a reference sample. Even though this fundamentally favors the kernel-based competitors, our proposed method achieves results that comparable to those of the other kernel-based approaches and to RuL.IF.
A.3.3 MazurkaBL data
In Kosta et al. 26 the authors found that change points in loudness information of Chopin's Mazurkas correspond score positions having dynamic markings, tempo, expression markings, among others. To further validate our algorithm's performance, we additionally run the proposed method on the "M17-4" sample (illustrated in Figure of pianist "pid50534-05" of their MazurkaBL data set with the goal of detecting these changes. Here, the dimensionality is d 1.
27
Lento ma non troppo 152) )
espressivo
ten.
p
sotto voce
Figure 6: An excerpt of Frédéric Chopin's Mazurka Op. 17 No. 4.
As in the main article (see Section 6). we approximate the Gaussian kernel with > 0 set by the median heuristic. For obtaining the thresholds using Monte Carlo iterations, we slice the data along each annotated change point, where we consider the annotations provided by Kosta et al. [27] as ground truth, and compute the test statistics obtained by the proposed Online RFF MMD algorithm individually each one. We then select the I 0.1 -quantte across all test statistics obtained as threshold.
To detect change points, we again slice the loudness data, but now such that each slice contains precisely one change point, which yields total of 25 samples with an average length of 1 561.32.
'The changepoynt library is available phttps::/ggiieee http:///ttitt///tto///////////aa
24

---

We process each one of these with our proposed method and consider the first time the test statistic exceeds the threshold as "change". In total, our proposed method flags 10 change points too early. and, on the remaining 15 has an average detection delay of 73.67, with median detection delay of 64.0.
While, when contrasting these results with the results obtained on the MNIST (Section A.3 and HASC (Section A.3.2) data sets, detecting changes in the selected loudness data of a Mazurka seems substantially more challenging, the proposed algorithm still manages to detect many changes with relatively small delay.
A.3.4 Distribution-free bound
In this section, we show the change detection performance of the proposed Online RFF-MMD algorithm if no pre-change sample used estimate the threshold. Instead, we use Theorem | to compute the distribution-fice threshold sequence {An N} for given target ARL. To obtain an EDD estimate, we sample and process 512 observations from MNIST digit (pre-change) and 1 024 samples from digits 1-9 (post-change), respectively, averaging the detection delay over 100 repetitions. The results are in Figure 7 When comparing to Figure and Figure the figure shows that our method has an increased detection delay, which is due to the looser distribution-fie frree bound (see Section A3..5 for a numerical comparison). Still, except for the change the digit with guaranteed ARL of 109, Online RFF-MMD detects all changes reliably.
Online REF MMD
500
EDD
250
EDD
250
500
EDD
3.0
logio ARL
log ARL
10g10 ARL
Figure 7: Average detection delay from MNIST digit 0 to digits 1-3, 4-6, 7-9 (top bottom) with the distribution- threshold sequence of Theorem
A.3.5 Threshold comparison
In this section, we compare the tightness our thresholds in the offline two-sample testing setting. Specifically, fix the level
0.01 and let IP Q 1). We then approximate the 1 a quantile of MMD & (Pn.. Qn (with = 1 0000, K approximating the Gaussian kernel with r 1 000 RFFs, and 7 > 0 set by the median heuristic) by (i) obtaining new samples from IP, Q and (ii) permuting a fixed sample from P, Q for 1 1000 rounds. Figure 8 shows the respective histograms and the estimated quantiles along with the thresholds obtained by Lemma
Lemma respectively. As expects, the figure shows that the variance estimate used in Lemma T allows to obtain tighter bound, where we consider the resampling/eermuaation based thresholds as ground truth. We emphasize that independent of the threshold used, the resulting test is consistent against any fixed alternative.
A.4 Proofs
This section is dedicated to our proofs. The proof of Theorem i in Appendix A.4.1 that of Theorem is Appendix(A.44 that of Theorem 3 Appendix A.4.3 and that our minimax result (Theorem is in Scction A.4.4 The tighter threshold detailed Lemma is proved in
25

---

Permutation quantile
Distribution free level Bernstein-bound level &
Permutation baaseatttio---eedd based
Resampling I-a quantile
Resampling- baseee
100
80
Count
60
20
0.000
0.025
0.050
0.075
0.100
0.125
0.150
0.175
0.200
Figure 8: Comparison of different thresholds for the acceptance region of the MMD two-sample test.
Appendix A.4.5 and we state the proof for our multiple change point detection result (Theorem (5) in Appendix A.4.6
A.4.1 Proof of Theorem 1
Proof. For ease of reading, for each and O,..., [log2(n)] put
2 - 22) MMD k (1:(n-21), ((no-2+11mm)
Mag
(14)
By the law of total expectation, we have that
Ex [N] = Ex [N
N < 2n] Po (N < 2n) + E.o NN N > 27 (N > 2ny
2 2y Po (N s 27)].
(15)
Putting = /2 log, (2 a union bound argument together with Lemma 5 gives that
(u U (w),( Mn.s v2 /2+A)
Poo (N < 27) = Poo
2x
(n)]
f Poo (Miss V2 An w.r dA (WI) ... dA (w,)
1=0
2 102/ (2
X²/2
(16)
2'
Finally, plugging 16 into
15
proves the desired result.
A.4.2 Proof of Theorem
Proof. Write
Tr = /2 (log(n/a) + 2 2lg (log2(n) + log (logz (2n))) for each n N. Applying standard peeling arguments (64. 57], we have that
(17)
Poo (N 00) P.. (Um- _ [ogg((m)] -1 Mn. v2 + Tn
Poo (L (loga(m)1-1 Mnss > V2 + TT))
2
max
Poo (u.l [logg(m)) MM. > V2 + n
(18a)
2i 11
1=1
[log. Σ
8
2
max
Poo (Maj > V2 + nr
(18b)
1=0
26

---

where in line T8a we apply union bound and bound the resulting sum by its maximum. Then, applying Lemma as was done in (66), we obtain that
F Fo (N < x0)
Logg (m)]
2
max
Σ 1=0
j...
Poo (Mms > V2 + an wi....,ws,) ws) dA (wi).
(oz)...du ......d .A (w,)
Sn52
12'e 12
1=1
Finally using the facts that (i) exp (-12:/2) Sal at (1+1))-- for all E N and (ii) Ei=1 1
1) = 1, we obtain that Poo (N < x:) a.
A.4.3 Proof of Theorem
Proof. We first observe that for any triplet of integers (m, n, v/) satisfying (i) m S n and (ii) S n/2. given two samples
Xim Xn- Y - Pn
and
Yim = {Yi,.... Ym),
with mutually independent entries taking values in some bounded set X' C Rd where the X's are sampled from and the ''s and Y's are sampled from Q for some IP, Q E MM (X) not identical, for any E > O, it holds that
P
mm
MMD & [Xim: Y1mm] S v2+
+
K (x,y) - K (x, 1
V2 -1 -2-1
10
))
<
P
2
m sup
Vm
MMDx [P, - E
x,EEX'
3
2v2
v2
V2 1
10
4exp
m
MMDx [P. Q
(+
v 0
(19)
18
2/2
V
where MMDx is in and MMD & is defined in sampled independently from IP and introduce the quantities
7
To show
(19 let the X's below be
(.xi)
4
(1,
(x)
+
Σ K (-RーP41
K (.. Yi)
n
m
1=1
n
42
Σ
K
(.
X
K
(..Y.
Hx
Note that by the reverse triangle inequality
MMD [Xim Y1m]
A
Consequently, using the above and by repeated applications of the triangle inequality, one has that
nm
MMD & [Nims Y1m]
n2 + m
1 1
MMDK PP. Q
+
nm
MMD K (X V1ml MMM (X Y1m]]
(20a)
+
nu
E E[A]]
2m
|A E[A2]
(20b)
n + m
n +
2m
[[ - MMD [PP QlI
LE [12]]
MMDx [I. Ql|
(20c)
+
m
27

---

For term 20a). applying Lemmas and 3 togetherr with the fact that the X's and Y's take values in some compact X R we obtain that
7m m
MMD K [X1m: Yiml] - MMD [X1ms Y1mm S 221
sup x.yEX'
K (x,y) K (xc, (x)
(21)
For the penultimate term in 20c applying the bound
1
E |MMD K [1.. Yim] MMDx P.. Q
2
(22)
Vn
Vm
for X's sampled from IP and Y's sampled from Q, whose proof can be found for instance in Section
A.2 of [14], together with the bound vx y 2 (V2/2) (Vr v8) for all x, y 2 0, which holds due to the concavity of the square root, one has that
TOTR
E [
MMDx
P. Q
Tum
E B| - MMD Q|
v + v m
4
(23)
vn + m
V2
Identical arguments together with the fact that m implies that (2m) (m + n)) S 1 give
2m
v E |2 - MMDx [P. Q S
(206
(24)
+ m
2
V2
Therefore, combining 21).
(33
and
(24. rearranging, and applying the rough bound
K
K P P
Zi>0 x
((z;>x/K)
j=1
which holds for any x R. K E N and any random variables Z ....... ZR. we obtain that
K (x,y) K (x.
19 <
P
2 m
sup x.yEX
V2-1
MMD QP, - ( v2 )
V m
v0)
3
2v2
+ P
nmm
A - E
[Ai]]
1
mm
V2
MMD P.Q - 8 +
10
v0
+ m
3
2v2
V2
(25a)
V22 -
10
+ PP
12 11 2(22)
Vm
MMDR [P. e
vo
(25b)
3
2v2
Note that we assume 0 < K(.,) < 1. Therefore, arguing as in Lemma 4, one can show that MMD as defined in <5) has the bounded differences property with constants (41). Hence, applying Theorem 6
to terms (25a) and (25b) one arrives at (19). Turning to the problem of interest we first make explicit the constants in Theorem 3
C 2 x C3
1
V22 -
550 + V6
C
= 3
VCs
O= (v + V54) x (4/(v2-11)
Next, define the quantities
k. = min k E N k < and Vi x MMDx [P, Q 2 CC log (2n/a))
(26a)
4. = min {t = 2' | E N and < k*)
(26b)
28

---

Note that condition j appearing 226b
guarantees that (2aa) exists and it can be checked that C2 > 0. Let j be the Consequently, using (19 and the fact that k- /2 S tg- I k* we obtain that
P (AV 71) > k²)
[1og2 (1+++~>+)--111-
23 (1) + kt 26
P
MMD (X1 Nm X1jo S V2 + 1pt
11 + h*
j=0
1x- (1) + A: (x-)
MMDR & Ni | S <v2+ + X2n
11 n 1+h* h*
P
2
sup
R (x, K (x,y))
Vh V2-1
MMDx x [P. Q] - (220 +
10
a.VER'
3
4
v2
(27a)
V -2-1
10
+ exp
MMDK [P,
Q1
X22n +
v0
(27b)
18
4
/2
where for typographical reasons we have put:
1,,,x- = 1: k-
Jz == (1+ - + 1))
for = 0,..., [log2 (n + k*] 1. Now 26a together with the fact that X2n + 10 <
(v50 + /6) x
v2
/log (2n/a) for all E (0, 1) and 17 N guarantees that the term on the right of the inequality in (7a is no larger than C2 Vk* MMDx [P. Q). Hence, appealing (10h and Theorem
we obtain
that 27a I a/2. Moreover, since for each S it holds that
{ VE
V2
10
2n
MMDx [P, Q)
A2n
2
V
18 x 3 log
4
V2
a
'n
S
Vk x MMD [P
Cs log
with k* defined as in 26ap. we obtain that the theorem proved.
27b < 4 x (a/2n)² I a/2. With these facts in place
A.4.4 Proof of Theorem
4
Proof. Let 1 (L,... 1)ad E Rd and (0, (0,...,0)) 0) Rdd let 8 denote the Dirac measure (for
any set (Rd) and any æ E Rdd (A) 1 if x A and otherwise). and let
M QP M RRd)
P= pō1 + (1 p) 80 Q qd1 + (1 q) 80.
P.q [1/4,3/4] and y 2 1/4]
Therefore, for any P. Q MM,, making use of the symmetry of K, we have that
(MMDx P.. Q
= =Ex,x=< XX') (X - -E [K (X,Y)
(28)
(1
+=0X((1))0+0--033200000--111110- (1,0)
-2(pp(( (11))=((--010000((000)))-
((.())))+(((0)-))2(((00000)) -) + g(1 - p)) K (1,
(29)
29

---

Moreover, for any P. Q E M we also have that
1 p
KL (Q P) - log
(1 q) log
p
1 -
9
- (q p)
(30a)
2 - (p + 9)
17
$ (g -p)
(30b)
34 -p)²
(30c)
where (30a) holds due the bound [=1 < log(x) S for x 2 1, 30b holds because
P, q E [1/4, 3/4], and (30c) holds due to the bound æ < 4x for x 2 1/4. Combining 29 and 330
and additionally making use of the shift invariance of K, obtain that
17 3 KL Q PP)
(0, K
MMD (P.Q).
(31)
Therefore, putting CK (1/2) (K (0.0) K (1, for the constant in
12
using
31
along with the fact that M M (R.), we have that
N 7 (1/2) log (L/a)
L.H.S. of (12) 2
inf N.P So
sup
(32)
KL (Q P)
n>1 P.QEM
Consequently the theorem is proved if we find absolute constants oo. Po E (0, 1) and pre- and post-change distributions P,Q Q MM such that for all a S og it holds that
(1/2) log (1/o) sup P N 2 oe (N n>1
inf
2 B..
(33)
KL QQ P)
To show (33 one can use change of measure argument originally due to Lai [30]. In fact one can directly use the version of Lai's argument adapted to finite sample analysis by Yu et al. [64] Proposition I]. For clarity of exposition, we repeat the argument below. The following holds for arbitrary P, Q E M For each n E N let Fn be the a-field generated by {X;) and let pan be the restriction the joint law Fn.
We can write
dp
exp
Σ 1=1
Zz
for 1)
where, as in the main text, the subscripts indicate the time at which the change occurs. For a chosen (0, 1) and an arbitrary stopping time satisfying Po 20) S introduce the events
(1/2) log (1/a)
N
17 N hn+
Σ
Z, S (3/4) log (1/a)
KL
$=1+1
(1/2) log (1/a) KL Q P)
N
Eg
S N +
Σ
2, (3/4) log (1/a)
1=1+1
For the first event we have that
N dp, < exp (33/4) log (1/a)) Po (E1) s 1/4
/ exp
P. (E =
2 E 1=1
(34)
E1
where the first inequality is due the definition of & and the second inequality holds because the probability of N being finite when no change occurs is bounded from above by For the second
30

---

event we have that
1-1 n-t
P.y (E2) s P,
U
Σ
4> (3/4) log (1/a)
1=t
i=+1
(1/2)) --1
pn
U
Σ
(Z. KL (LQ (1/4) log (1/a)
(35a)
1=t
i=+1
(1/2) (g/{)
exp (- log(1/a))
(35b)
KL Q P))
</
(35c)
where in particular 35a) holds by subtracting x KL P) from both sides of the inequality and using the fact that for every t the union holds that t KL (Q || P) < (1/2) log(1/a)), (3bb) holds due to union bound argument followed by an application of Hoeffding's ss inequality, and (35c)
holds for all a I an where
ag = sup { a (0,1) (1/2) log(1/a)a
inf KL (L P) and 20 1 2.0EM
}
S
Since the above arguments do not depend on the stopping time N or the change point location 7). the bounds (34) and (35ch together imply that R.H.S. of 32 20 1/4 which proves the desired result.
A.4.5 Proof of Lemma
Proof. It suffices to show that for any > 0 it holds that
(1 n Σ 72
ne² 2 32 + 25
P A
ER(X, B (X)
>c)
2exp
(36)
which implies the stated result by using & (XX), the triangle inequality, and a union bound. Here and in the following Ei (resp. P w) refers to the expectation (resp. probability) with w fixed. To prove (36), we fix w = (wi....,de ..,) and let = (x,),) E (X).. Then, all 1/-s are zero mean w.r.t. and i..dd Further, we have for any p 2 that
Eyllm I| Il 2| s sup |/ 3 2 2 2 || 11
where the last inequality follows by using the triangle inequality and (ax (X1): 2x (x())) to obtain
sup |mm 1|022 < - sup 11 (X1))I 2
Hence, we have the bound
E N Il
1P < 2 |n 11 < 7 p120- 2 || 1|
and the n satisfy the Bernstein condition with B² = Ew and H = 2. The application of Theorem yields that for any e
0
n
1 n²=²
n
TH
>E
2exp
< 2exp
2
B2 + enH
Ba + EH
To lift the conditioning, observe that
(1
"2
ns22
Po A
> 6 = EP p
>
< 2E 2Eexp
2 B² EH
1=1
n
< 2eep
2 B. 2
+ eH
31

---

where the last inequality holds by the concavity of exp(-1/x) for >> 0 and Jensen's 's inequality. Finally, we conclude the proof by using that
EB² E (2x 2K (X)) + (Bpêk (X), Bp²k (Y))
(xx
= EK [X, X) - (X(X,Y) =
where the boundedness of all terms allows exchanging the expectations by the Fubini-Tonell theorem.
A.4.6 Proof of Theorem S
Proof. We first show that with probability least - no local tests conducted on null intervals will cause the algorithm to wrongly declare a change. For each n < T define kn = max $ M + Th S n.. With n. defined in (17). introduce the event
A 2
(n nen +1]--1 Mn. Tn mnj- N==1
(37)
We therefore have that
Logg (n
+1]] -1
P(AA)
S
Σ 2
max $nn2++1
Σ
P MMss Fn
(38a)
1=1
T
<
12 é - -15g1)
(38b)
1=1
a log (T)
< aa
+ (T)
where (8a)
follows by arguments similar to 18a and (38b) holds due to Lemma 5 Therefore, if M done. We tackle the case M O. We will show that when M 0 with probability at least 2a all true change points are detected and localized at the stated rate. We first make the constants in Theorem eeppicii::
C = 2 C3
C =
C3 (2x (V²+ V+++)++)6))
Introduce also the event
5 1 hdd, + / Hog((/o)) Vr
A2
sup xyEx
x(x,))
(39)
on which the random Fourier feature kernel K is close to K in sup norm sense. Note that by Theorem 7 the event (39) holds with probability least a/2. Introduce also the sequence of events
log (T/a)
Bg
Tk
S
Th
C3s
for k= 1...... M, (MMD& (Qe, 12+1l)2
such that on the event B& the k-th change point is detected and localized at the required rate. If M < M we employ the convention îi. T for all M. We now show that on (37 and 39 the event B holds with probability at least T/(2a). Introduce the quantity
n = min n < 1/2 | n 7n = 2 for ji E N, V2D (2) V log(2T/
32

---

To ease the notation put 17 = 1 1/, J = (n + 1) : ni. and V 24 (mi-24i)
Observe that
ni
MMDMD & [X1;, X,²
2 v VVMMDD QQ1 O2l + V/2 (MMDR (Xi; XJ;] -E [MMD (Xxz Xx;1)
(40a)
-2V sup
R (xx,1) y) - (x, y)
R.
VV E [MMD K [Xr; X,;1] MMDx [Qi, Qa]
2 VV/'MMD (Qu, Q2) + VVT (MMDx [Xr;, X,;] - E [MMDx [X1; Xx;1])
v2
(40b)
Where (40a) holds by the triangle inequality and arguments similar to 21 and (40b) holds by arguments similar to 22 together with the fact that on 339 will have that
sup z.y
R(x, y) K kxx I min (MMDK I= M
[Qk, Qu+1))? -
(MMDR [Qu, Q2))
Using the above we therefore have that (LV(VVVVMMM
PP (B))) IP
VVVMMMD & [Xi [,r] S Ar))
$ E MMD & X,;]] - -MMD x,;1)
VFMMDD (Qi, Q2] - (Vi+ v6) v Vlog(2T/a)
a
27
where the final inequality follows from the definition of C3, the bounded difference property of MMDx. and Theorem 6 By the definition we must have that 2 S 81/2, therefore on the event A the first change point is detected and the algorithm starts at most mid way between 7)1 and 722- Identical arguments to those above therefore give that, on the events A₁, A2, and B₁ the event B2 holds with probability at least -a aa(2))) and having detected the second change point the algorithm re-starts at most mid way between 722 and 178- By induction and a union bound argument, on the events (37) and (39) the events B ... BM hold with probability at least 1 Ma/(2T) 2 1 a/2. Since 337 and 39 jointly hold with probability 1 3a/2 we are done.
A.5 Auxiliary results
In this section, we collect a few auxiliary results. Besides establishing useful bounds real numbers Lemma 2 and Lemma 3 we show that the bounded differences property of RFF-MMD (Lemma 4 leads to its exponential concentration (Lemma 5). The latter is one of the key ingredients for deriving
our threshold sequences elaborated Section 4.3
Lemma 2. For any x, it holds that
xy + y
min (I,
< min (I,
and, moreover, both inequalities are tight.
Proof. We first note that
xy min (x, y) max (x, v) min (x, y) (I+ min (z. v) max (2r, y)
-1
+ y min (x, y) + max (x, y)
For the lower bound we use the fact that min(x.y)
< 2, where equality holds when .r y. For 2 1, where equality holds in the limit when, for instance,
max(
the upper bound, we use that 1 + max(wa)) x is fixed and + +o0.
min(x.x)
Lemma 3. For x, y > 0 it holds that V V
1 yl
33

---

Proof. When x the statement is trivially true. When x & y it holds that
x - yl
- yl
V/2 vil
Vx
V S v
vl-
VI+ V V
Lemma 4. The RFF-MMD as defined in 7 between two empirical measures composed respectively of and sample points is function mapping from (IR") ( - R. This function has the bounded differences property with constants
22/n
ifi 1. n,
(41)
12/m
ifi
m.
Proof. Recall that if K Rd x Rd + I is the reproducing kernel for some RKHS H.K, for any P.Q Q MI. one has that
sup MMD [P fe
(Ex~p (X)] Ey-a
S1
Note that R Rd Rd + as defined in (6) is the reproducing kernel for an RKHS Hg whose elements are vectors 262" Introduce the set
g= (f Hg | I 13.
Let MMD (Xmn Im Mim) (Rx) stand for 7 with inputs (xi...., xn and , with the i' -tth x replaced by XR. We therefore have that
sup ym
MMD & [Xins [1mnsy - MMD & (Xi=n, V1sml (ix)
m
sup
sup SEğ
f(x))
Σ f(y.))
n 1=1
j=1
1
Σ f(x,)
1 [f(xx) - [(x;))]
1 -
Σ f(ys) ==1
sup
i=1
sup
1f(x) f(x)) = sup
1
R (.xx) R (1,30
x. n2
x. n
(1) k x)) 11 +
|| |
2
sup
x. n
n
where we used the reverse triangle inequality, the reproducing property, CBS for obtaining the supremum a unit ball and that, for any Rdd one has that
K (x)), R (.,))
=cos(0) = 1.
HR
The same calculations can be applied to MMD & (X1m1 V1:m) (5,). This proves the desired result.
Lemma 5. Given two independent samples , Xn3 and (YI...., Ynh. J. each with mutually independent entries drawn from some E .M for any e > 0, it holds that
IP
nm
MMD & [Xims Yımm > v2+e) S0-51/2
34

---

Proof. It is an immediate consequence of Lemma 4 and Theorem 6 that for any E' > 0
P (MMD, k (X1:n V1mm B[MMD K (1m Y1m] W1, w1.... : wir s w1...., wwr)
E² nm
exp 2 n m
(42)
Moreover, arguing as in the last step of the proof of Proposition 4 in 23 gives
E [MMD, K [xims Y1mml W1,..... Wi....,
M
MR
= E
R (X), +
K (Y,,)))
n2
m
1=1
2
m
R (x.)
lwi...,ww
Tim
j=1
+
E
K (X
m
=1
4 2 E (X,Y) ||]] wi....,,.!, cin]
m 1 72 1
)
1 m j
(1-B (X,Y) W1, Wi,...,Wy
n
2-1
2 (m + n)
(43)
mn
where the first inequality follows from Jensen's inequality. Consequently, setting 8'
nm
plugging 443 into (42). and integrating over the w-s with respect to the product measure A Gr
X A yields the desired result.
A.6 External statements
In this section, we collect the external statements that we use, to ensure self-completeness. Theorem recalls McDiarmid's inequality from Boucheron al. [5] Section 6. which is also known as bounded differences inequality (38). Theorem iis about the concentration of random Fourier features and part of the proof of Sriperumbudur and Szabó [54] Theorem 1]. We recall the concentration result Yurinsky (65 Theorem 3.3.4] on random variables taking values in separable Hilbert space in Theorem
Theorem 6 (Bounded differences inequality). Let X be measurable space. A function f x IR has the bounded difference property for some constants C1, CI...., Cn if. for each I,..., n,
sup BLa...Rn
Ri 2
- (xI, Zi 2'1 Ziti, Zit,... Ina] [l Ci. (44)
Then, if X1,.... X, is a sequence of independently distributed random variables and putting Z = f (X Xn) and y _ Ei of for any >> 0, it holds that
44 holds,
P P - E (7)
(((1))
Theorem 7 (RFF exponential concentration). Let K be defined as in (6). Let X be proper subset of Rdd and denote by |X| its Lebesgue measure, For any t > O, it holds that
h (2), .)) + +1)
P
sup xyEx
(x,x)) - K (xx,))
Vr
< - 12/2
35

---

where o² -g3 11 dA (w) and
h (d. [X| = 2 / 2d log (2 + 32V (or + 1) 16 2d flog (2 + 1)] (45)
Theorem 8 (Hilbert space Bernstein inequality). Let X1,..., Xn be sequence of zero mean independent random variables taking values in real and separable Hilbert space X with inner product (.))) and norm |I-|| -V..). Write S = supmsa [| + + Xm If the random variables satisfy the moment condition
X| * - HIB2H*3
for k 2 2, = 1ai==...... I....,
for some constants B > 0 and H > 0, then for any x > 0 it holds that
xH
P (S > xB)= & 2exp
- x
1 +
2
B
36


Reviews:
[{"review_id": "vBUBJLSCdC", "reviewer": "Reviewer_gyF2", "summary": "The paper proposes an online change point detection framework designed to identify abrupt changes in the probability measure of a data stream. The method employs a kernel two-sample test, approximated using random Fourier features. At each time n, the sequence is partitioned into log2​(n) candidate splits using a dyadic grid, and each split is tested using the two-sample test procedure.", "questions": "While the limitations of existing online change point detection methods based on fixed-size windows are emphasized, a key drawback of the proposed approach is that its computational complexity increases with sequence length. As a result, suitability to long sequences with no change points is limited. This limitation needs a more detailed discussion.\n\nThe description of the algorithm in Section 4.2 and Algorithm 1 is not very easy to follow. Including a schematic diagram in the main paper can improve clarity. In particular, the maintenance steps in step 3 of the algorithm, including window merging operations, are not well explained.\n\nThe theoretical results rely on properties of random Fourier features. Theorems 1 and 2 provide bounds on thresholds to achieve a desired average run length or uniform false alarm probability, while Theorem 4 establishes the minimax optimality of the test.\n\nHowever, the analysis considers the procedure in Equation 10, without including window merging and other management operations. It remains unclear how these components affect performance metrics such as run length, false alarm rate, and detection delay.\n\nTheorem 3 bounds the detection delay, but the expressions are difficult to interpret. How can the thresholds can be selected to achieve a target detection delay when the difference between pre- and post-change distributions is bounded?\n\nThe paper lacks a deeper comparative discussion with prior theoretical works. How does the proposed approach compares with existing algorithms such as OKCUSUM, NewMA, or ScanB in terms of run length and detection delay?\n\nThe experimental section should explicitly state which thresholds were used.", "limitations": "The increase of computational complexity with sequence length should be discussed in the limitations. No significant negative societal impact.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and generally clear.\n- Theoretical results seem correct.\n\nWeaknesses:\n- The computational complexity of the algorithm increases with the sequence length.\n- Certain steps in the algorithm are not described with sufficient clarity.\n- It is not evident whether the theoretical results can be used to control the detection delay.", "was_revised": true, "final_justification": "The paper is clearly written and with solid theoretical results. The additional comparisons to traditional methods such as RulSIF and Scan-B during the discussion was helpful to clarify the experimental performance of the method. The main advantage of the method is the lack of dependence on a window. However, I encourage the authors to provide an in-depth discussion on challenges and limitations of the work in the revised paper, such as the dependence on shift-invariant kernels, multiple change point detection, the non-iid case, and the log(n) complexity increase with the number of samples.", "rebuttal": "We thank the reviewer for the time and effort invested and for the valuable feedback. Below, we answer all questions in detail.\n\n> **Computational complexity increases with the sequence length**\n\nWhile some authors  (e.g., Chen et al. 2022)  impose the strict requirement that the complexity for processing a new observation may only depend on the number of bits needed to represent the new observation, to the best of our knowledge, there are no algorithms for the problem at hand meeting this requirement, save for those which (implicitly or explicitly) consider a fixed window over which to search for a change---effectively ``forgetting'' data which falls outside of this window. Still, we agree that that the computational complexity of the procedure increasing with the number of data observed can be a limitation.\n\nA key difficulty in achieving $\\mathcal{O}(1)$ time complexity for the problem we consider is that, unlike for parametric problems in which under the null (no change) the entire history of the sequence can be represented by a finite-dimensional sufficient statistic, we must keep track of the entire distribution. We also remark that optimal algorithms for online change detection in the parametric change setting generally exhibit $\\mathcal{O} (\\log n)$ complexity at the $n$-th iteration. See for instance the FOCuS algorithm of Romano et al. [2024] which solves Page's recursion to detect a change in mean in a sequence of i.i.d. Gaussians, running with expected $\\mathcal{O} (\\log n)$ complexity. \n\nNevertheless, achieving $\\mathcal{O}(1)$ time complexity for the problem at hand is an important open question and an interesting direction for future work.\n\n\n> **Details on merge operations** \n\nWe recall from Section 4.2 that each window stores a count $c$ and the sum of the Fourier features $z$ corresponding to the observations that the window captures; the observations themselves are not stored explicitly. The intuition regarding lines 13--22 of Algorithm 1, that is, \"the merge'', is as follows: When merging two windows---which, to maintain the dyadic grid structure, happens each time two windows have the same counts (line 16)---it suffices to sum their respective counts (line 17) and to add both their $z$ vectors element-wise (line 18), storing the results in a new window (line 19) and omitting the original two windows (handled by the ``pop'' operations). If no merge happens due to no windows having the same size (line 20), we undo the \"pop'' operations of lines 14--15 in line 21.\n\nFor a schematic representation of these steps, we refer to Appendix A.2 in the supplement, which we are happy to move to the main part of manuscript, together with the elaborations above.\n\n> **Relationship of (10) and the algorithm's implementation on run length, false alarm rate, and detection delays.**\n\nThe window management and merging operations described in Section 4.2 give back exactly the quantity defined in equation (10) with no approximation error. Therefore, the theoretical guarantees obtained by analyzing equation (10) are valid for the outputs of Algorithm 1. We will further emphasize this important point in the final version of the manuscript.\n\n\n> **Application of Theorem 3 to achieve a target detection delay**\n\nThank you for the question. We appreciate the opportunity to further clarify how the theoretical results in the paper should be understood. \n\nFirst, we emphasize that the threshold sequence $\\lambda_n$ is not chosen to attain a target detection delay, but rather to control the multiple testing analogue of statistical size at a given level.  To elaborate, similar to the methods that we compare against (OKCUSUM, ScanB, NewMA), we work in the sequential testing analogue of the Neyman-Pearson framework. That is, the quantity we seek to control is the multiple testing analogue of statistical size (that is, (i) the average run length defined in line 111, or (ii) the uniform false alarm probability defined in line 113) and subject to either constraint being satisfied, we seek the most powerful procedure (where power is understood in terms of the detection delay). Theorems 1 and 2 show how $\\lambda_n$ may be chosen to control either of (i) or (ii) at a desired level, Theorem 3 bounds the detection delay when $\\lambda_n$ is chosen to control (ii) according to the result in Theorem 2, and Theorem 4 shows that detection delay guarantee provided in Theorem 3 cannot be improved in general (up to logarithmic terms).  \n\nTherefore, Theorem 3 does not provide any guidance on how the thresholds should be chosen beyond the result already given in Theorem 2. However, Theorem 3 details how $r$ (the number of random Fourier features used to approximate the target kernel $K$) should be chosen (recall that the results in Theorems 1 and 2 hold for any choice of $r$). The result is qualitative, and says that when $MMD_K [\\mathbb{P}, \\mathbb{Q}]$ is bounded away from zero, the number of features should scale as $r = \\Theta(\\log 1/\\alpha)$ with $\\alpha$ being the desired uniform false alarm probability in the asymptotic framework where $\\alpha \\downarrow0$. However, in practice, one may choose $r$ as large as possible subject to computational constraints, keeping in mind that the time and space complexity of RFF-MMD scales like $\\mathcal{O} (r \\log n)$ at the $n$-th iteration. \n\n\n> **Qualitative comparison to OKCUSUM, NewMA, ScanB w.r.t.\\ run length/detection delay**\n\n* **Average run length** All considered algorithms (the proposed Online RFF MMD, OKCUSUM, NewMA, and ScanB) can be calibrated to achieve a desired average run length. The run length analysis for OKCUSUM and ScanB makes use of Siegmund's analysis of boundary crossing probabilities for Gaussian fields whereas our analysis employs simple tail bounds and the law of total probabilities. Nevertheless, we attain the same thresholds up to constant factors.\n\n* **Uniform false alarm probability** However, unlike the proposed method (Theorem 2), neither OKCUSUM, NewMA, nor ScanB offer guidance on calibrating the procedures for controlling the uniform false alarm probability. However, we believe that a peeling argument as in the proof of our Theorem 2 can be used to derive similar guarantees for these methods. \n\n* **Detection delay**  The authors of NewMA and ScanB do not provide a theoretical analysis of the respective detection delay. Moreover, these methods (implicitly and explicitly, respectively) maintain a window, which implies that (i) the detection delay will be at least as long as the window (that is, maintaining a window of size $w$ means the algorithm cannot declare a change earlier than the $w$-th iteration), and (ii) at the $n$-th iteration data with index $n - w$ is effectively \"forgotten'' by the algorithm, which can lead to a loss of power. Regarding OKCUSUM, Wei and Xie (Section 4.4) shows that when the OKCUSUM algorithm is run with a maximum window of the order $\\Theta ( \\log (\\gamma) \\times  (MMD_K [\\mathbb{P}, \\mathbb{Q}])^{-2} )$, it will attain an expected detection delay that is asymptotically equivalent to $\\log (\\gamma) \\times  (MMD_K [\\mathbb{P}, \\mathbb{Q}])^{-2}$ as  $\\gamma \\uparrow \\infty$, where $\\gamma$ represents the desired average run length. To emphasize, our analysis is finite sample and is concerned with the setting in which one aims to control the uniform false alarm probability ($\\alpha$) under the null, whereas the analysis of Wei and Xie is asymptotic and considers the setting in which one aims to control the average run length. Loosely speaking, in the asymptotic framework where $\\alpha \\downarrow 0$ and when setting $\\gamma = \\alpha^{-1}$, our results coincide. Note, however, that Wei and Xie work in the asymptotic setting where a growing number of observations known to be from the pre-change distribution are available to the algorithm, whereas our procedure does not require access to any such information.\n\n> **Thresholds used in experiments**\n\nRegarding the experiments in the main part of the manuscript, we recall from lines 288--290 that we ``compute the thresholds for a given target ARL by processing $10 \\times (\\text{target ARL})$ samples with each algorithm, repeating for $100$ Monte Carlo (MC) iterations, and computing the $1-1/(\\text{target ARL})$ quantile of the resulting test statistics.'' This testing procedure enables a fair comparison of the detection delays because it allows us to ensure that each method is run with the sharpest possible threshold. We are happy to emphasize the latter point in the manuscript. For the additional MNIST experiments provided in Appendix A.3.1, the setup is equivalent to the one described above. The experiments in Appendix A.3.2 use the distribution-free bound of Theorem 1 and therefore require no Monte Carlo iterations.\n\nWe hope these answers fully settle all open questions.\n\nYudong Chen, Tengyao Wang, and Richard J Samworth. High-dimensional, multiscale online changepoint detection. Journal of the Royal Statistical Society. Series B (Statistical Methodology), 84(1):234–266, 2022.\n\nGaetano Romano, Idris A. Eckley, and Paul Fearnhead. A log-linear non-parametric online change-point detection algorithm based on functional pruning. IEEE Transactions on Signal Processing, 72:594–606, 2024."}, {"review_id": "LdlwQDMah7", "reviewer": "Reviewer_ArQr", "summary": "The authors consider the problem of online nonparametric change point detection. They consider an algorithm based on a kernel maximum mean discrepancy (MMD) test statistic. Using the Bochner's theorem, they show that (approximate) calculation of the MMD statistic can be reduced to computation of the distance between empirical Fourier features. They suggest a way to update the test statistic in $\\mathcal O(r \\log n)$ operations on the $n$-th round, which is extremely fast. Here $r$ is the dimension of the RKHS associated with random Fourier features. The authors study theoretical properties of the procedure proving a lower bound on the average running length and a high-probability  upper bound on the detection delay. They also conduct numerical experiments on artificial and real data to illustrate performance of the procedure.", "questions": "1. I would appreciate if the authors provided a bit more intuition why Algorithm 1 computes the test statistic from eq. (10) in logarithmic time. Is it true that you save computational time computing averages over segments of length $2^j$ in a recursive manner using averages over segments of length $2^{j - 1}$? If so, can you elaborate on the differences of your procedure compared to online kernel CUSUM, where the authors also update the statistic in a recursive manner?\n\n2. Can you compare your procedure with one of nonparametric change point detection methods based on density ratio estimation (KLIEP, uLSIF, RuLSIF, see S. Liu, M. Yamada, N. Collier, and M. Sugiyama. Changepoint detection in time-series data by relative density ratio estimation. Neural Networks, 43:72–83, 2013)?\n\n3. Can you check performance of your algorithm on other real data sets?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths.\n\n1. While the idea to use random Fourier features was already used by Keriven, Garreau and Poli [22], their NEWMA procedure required a proper choice of the sliding window size. In the present paper, the authors avoid the sliding window technique and obtain a procedure which is almost as fast as NEWMA (up to a $\\mathcal O(\\log n)$ factor) and uses smaller number of hyperparameters.\n\n2. The authors prove strong theoretical guarantees on performance of the procedure. While study of the test statistic behaviour under the null hypothesis is ubiquitous in the literature on change point detection, not so many papers provide rigorous bounds on the detection delay.\n\n\nWeaknesses.\n\n1. Numerical experiments on real data are not extensive enough. There is only one real data set.\n\n2. The method is compared with kernel-based approaches only. It is not clear how the method will perform against, say, nonparametric change point detection methods based on density ratio estimation (KLIEP, uLSIF, RuLSIF, see S. Liu, M. Yamada, N. Collier, and M. Sugiyama. Changepoint detection in time-series data by relative density ratio estimation. Neural Networks, 43:72–83, 2013). \n\n\nSmall remark. In Lemma 4, it is better to write ''bounded differences property'', instead of ''self bounding property''. Self-bounding functions are defined differently (see, e.g., Definition 1 in [Boucheron, Lugosi, Massart, Electron. J. Probab., 2009]).", "was_revised": true, "final_justification": "The authors addressed my main concerns during the rebuttal. I decided to keep my score, because the suggested algorithm performs similarly to RuLSIF on the HASC data set. Probably, the method needs further evaluation on real-world data. Nevertheless, the merits of the paper outweight the drawbacks.", "rebuttal": "We thank the reviewer for the time and effort invested and for the valuable feedback. Below, we answer all questions in detail.\n\n> **Logarithmic complexity for computing (10)**\n\nThe computation of (10) requires the computation of $\\operatorname{MMD}_{\\hat K}$ across all divisions of the dyadic grid, that is, a logarithmic amount. We elaborate the algorithm as follows (in particular, lines 193--195 of the submitted work) and also refer to Appendix A.2 for a schematic representation of the procedure. See below for a comparison to the recursive structure of OKCUSUM.\n\n* **Step 1** Given the data structure employed by Algorithm 1, we may assume that computing MMD at the leftmost division costs $\\mathcal O(\\log n)$ as one considers the \"leftmost\" $z$ (given, hence $\\mathcal O(1)$) and the sum of all other $z$-s, of which there are at most $\\log n$ (the reasoning for the $c$-s is the same), which, for the first computation of MMD results in a time complexity of $\\mathcal O(\\log n)$ using that (9) is simply their Euclidean distance.\n* **Step 2+** Now, to compute MMD at the next division, we may add the $z$ of the next window to the $z$ of the first and subtract it from the sum of the \"right\" $z$-s obtained in the previous step. Proceeding equivalently with the corresponding $c$-s, we may again use (9) to obtain MMD, which only gives an additional cost of $\\mathcal O(1)$ (as $r$, the number of Fourier features, is fixed).\n\nAs we repeat step 2+ at most $\\log n$ times, the runtime complexity for obtaining all MMD values is logarithmic in the number of samples. Now, we recall from line 196 that the data structure---which was assumed as given in both steps above---can be maintained in $\\mathcal O(\\log n)$, which yields the claimed total runtime complexity of $\\mathcal O(\\log n)$.\n\n\n> **Comparison to recursive structure of OKCUSUM**\n\nThe proposed method differs from OKCUSUM in two key aspects. First, OKCUSUM relies on a windowing scheme, essentially instantiating Scan-B statistics for different window sizes, which also requires a pool of reference data known to be from the pre-change distribution (we also refer to our answers to Reviewer \"gyF2'' for a quantitative comparison of the respective theoretical results and their implications). Second, OKCUSUM computes the full Gram matrices for estimating MMD. Its recursive update step entails removing the (row,column)-pair corresponding to an old observation and adding the (row,column)-pair corresponding to a new observation. This procedure is illustrated for Scan-B statistics in Appendix A of Li, Xie, Dai, and Song (Sequential Analysis, 2019); OKCUSUM replicates the procedure. Our proposed method does not compute any Gram matrix. Instead, we rely on (9) for approximating MMD using the Euclidean norm of the random Fourier features. While one, in principle, may use recursion for maintaining our dyadic grid structure, we chose to present Algorithm 1 using \"for-loops'' instead.\n\n\n> **Comparison to density ratio estimation RuLSIF and other real data sets** \n\nThank you for the nice reference. While the approaches in Liu, Yamada, Collier, and Sugiyama (Neural Networks, 2013) fundamentally differ from the kernel-based approaches that were considered in our manuscript, we compare them to RuLSIF experimentally on the HASC and MNIST data sets in the following. \n\n* **HASC** The Human Activity Sensing Consortium (HASC) challenge 2011 data set is also considered in the RuLSIF, Scan-B, and OKCUSUM papers. As in the OKCUSUM paper, we consider the change from \"walking'' to \"staying'' of participant $101$. For pre-processing, we order the corresponding csv-files in the data set lexicographically, omitting the first $1596$ (see below) samples of \"walking'', and then concatenating $100$ \"\"walking'' observations and $100$ \"staying'' observations to obtain a total of 10 data sets (with $d=3$) with a single change point each. For obtaining the thresholds of the proposed Online RFF MMD, NewMA, Scan-B statistics, and OKCUSUM, we proceed as elaborated for the MNIST data in Section 6.1, that is, we use a Monte Carlo approach with $\\alpha=0.1$ on all $10$ \"walking'' data sets. As per the setup in the OKCUSUM paper, for ScanB and OKCUSUM, we set the number of windows $N=14$ and the window length $w=114$, implying that both algorithms receive $14 \\times 114 = 1596$ samples from \"walking'' upfront. Likewise, we process $1596$ elements with NewMA upfront. \n\n* For RuLSIF (which showed the best performance on HASC in the respective paper), we use the python \\texttt{changepoynt} implementation and consider the $l_2$-norm of each three-dimensional observation. We then obtain the change scores for the full data set and select the point with the highest score as predicted change point, as done in Section 4.2 of Liu, Yamada, Collier, and Sugiyama (Neural Networks, 2013). To match their setup, we set the window length to $10$, the number of windows to $50$, and $\\alpha=0.1$. With these settings, RuLSIF yields the change points $91, 109,  98,  60,  99, 100,  97,  60,  82,  96$ (up to statistical fluctuations), which we summarize together with the results obtained by the other algorithms in the following table (where we count \"too early'' if the change point is flagged before $100$ samples were processed, \"miss'' if no change point is flagged, and compute the average over all change points flagged after $100$ observations).\n\n| Algorithm      | Average delay | Too early | Miss |\n|----------------|---------------|-----------|------|\n| Online RFF MMD | 21.86         | 2         | 1    |\n| NewMA          | 34.25         | 1         | 5    |\n| ScanB          | 31.20         | 0         | 0    |\n| OKCUSUM        | 17.44         | 1         | 0    |\n| RuLSIF         | 4.50          | 8         | 0    |\n\n* We emphasize that in the above case all algorithms except for the proposed one and RuLSIF receive $1596$ samples upfront, to use as a reference sample. Even though this fundamentally favors the competitors, our proposed method achieves results that are comparable to those of the other kernel-based approaches. The change points estimated by the RuLSIF algorithm are close to the actual change points in most cases (see the list of change points above), with a tendency of being too early. In practice, one could take this behavior into account by adding a fixed offset. %FK: My guess is that RuLIF estimates the most likely change point posthumously, not really online. I.e., if we have one 1 sample of the post-change distribution, it would not work. We should point this out.\n\n* **MNIST** We recall from Section 6.2 that we consider the changes of $64$ samples of digit $0$ to $64$ samples of digits $1$--$9$. Applying RuLSIF (with the same settings as in the HASC experiments) to the respective $l_2$-norms of the data, the points with the highest change score are $66, 61, 61, 61, 60, 60, 66, 67, 65$; when omitting the $5$ \"too early'' cases, the algorithm has an average detection delay of $2.0$.\n\n* **MazurkaBL** We additionally validated our approach on the MazurkaBL data set and refer to our answer to reviewer \"4v7u\" for details.\n\nWe are happy to include these additional results together with all code in the manuscript.\n\n\n> **Performance on other real data sets** \n\nPlease see above for additional experiments on the suggested HASC data set.\n\nWe hope these answers fully settle all open questions."}, {"review_id": "OSeKqGJ0X6", "reviewer": "Reviewer_jvfE", "summary": "The paper proposes a scheme for online change point detection using a two-sample test based on maximum mean-discrepancy on a transformed version of the data (feature map based on random Fourier features).  Rigorous guarantees on the performance are obtained including a result showing that it is essentially minimax optimal. A key ingredient of the scheme is performing a logarithmic (in n) number of tests at each time step n.", "questions": "- In Section 7, it is mentioned that the theoretical results are valid for any kernel satisfying Assumption 1. Why is the Random Features kernel emphasized, including in the title of the paper — is is due to computational advantages? Could the authors comment on how the performance of the method depends on the choice of kernel (at least empirically)?\n\n- Please clarify how \\Lambda is determined — is it just the Lebesgue measure in this case?\n\n- Could you comment on how restrictive Assumption 1 is? It is mentioned that is satisfied by many commonly used kernels, but does it rule out others that are used in practice?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The problem studied is interesting and relevant.  There is a substantial literature on onlie change point detection, but the scheme is novel with strong theoretical guarantees, and the numerical results show that the method outperforms the state of the art.  The paper is well-written. \n\nSome potential weaknesses:\n\n- The authors should compare their scheme with the recent framework proposed in https://arxiv.org/abs/2504.09573 which also seems to an approach based on a geometric grid.\n\n- The method appears to be tailored to detect at most one change point. Can it be extended to handle multiple change points?\n\n- The paper emphasizes that other methods require selection of a window parameter. Could the authors explain why this is significant? And Algorithm 1 seems to maintain a window in any case — is that the point that there is no parameter to be optimized?\n\nTypos:\n\n- l. 243: constrains —> constraints\n- l. 250: 250.000 —> 250,000\n- I think “metrizes” is more standard than “metricizes\"", "was_revised": true, "final_justification": "Thanks to the authors for the response. It would be good to include in the paper some of the points clarified in the response, especially  on the choice of the kernel. Overall a solid paper.", "rebuttal": "We thank the reviewer for the time and effort invested and for the valuable feedback. Below, we answer all questions in detail.\n\n__Restrictiveness of Assumption 1/emphasis on random Fourier features.__ The class of so-called translation-invariant kernel functions, which are kernel functions on $\\mathbb R^d$ that only depend on the difference of their inputs (in other words, for a given kernel function $K : \\mathbb R^d \\times \\mathbb R^d \\to \\mathbb R$ there exists a positive definite function $\\psi : \\mathbb R^d \\to \\mathbb R$ such that $K(\\mathbf x, \\mathbf y) = \\psi(\\mathbf x - \\mathbf y)$; please also refer to Assumption 1 of our manuscript) encompasses many well-known and frequently-used kernel functions, for example, Gaussian kernels, mixtures of Gaussian kernels, inverse multi-quadratic kernels, Matérn kernels, or Laplace kernels. The translation-invariant property permits to approximate the respective kernel function by finite-dimensional feature maps ($\\hat z_K$ in the article) through Bochner's theorem, which, in turn, allows the effective online estimation of MMD detailed in the article. The choice of kernel (resp.\\ kernel parameter) impacts the online analogue of testing power, that is, a good choice allows to reduce the expected detection delay of our procedure. We emphasize that (i) the results stated in the article hold for all bounded continuous characteristic translation-invariant kernel functions and (ii) the class of such translation-invariant kernel functions is sufficiently large to contain most kernel functions employed on Euclidean spaces in practice. A kernel function on Euclidean space that does not permit a random Fourier feature representation is the unbounded exponential kernel, employed in particular financial contexts \\citep{chamakh21kernel}.\n\nWe also refer to Section 7 of our manuscript, where we provide references on tuning the kernel w.r.t.\\ to testing power (resp.\\ a proxy thereof), which in itself is a deep topic outside the scope of this manuscript.\n\n\n__Determining $\\Lambda$.__ The existence of the measure $\\Lambda$ in Asssumption 1 and (7) follows from Bochner's theorem (see, for example, Wendland 2005, Theorem 6.6), which, besides existence, asserts that $\\Lambda$ is a non-negative finite Borel measure (implying that normalization yields a probability measure). For computation, one uses the spectral density associated to $\\Lambda$ (in other words, the Radon-Nikodym derivative of $\\Lambda$ w.r.t.\\ to Lebesgue measure). For many translation-invariant kernel functions these spectral densities are known, see, for example, Sriperumbudur et al. [2010, Table 2], or Rahimi and Recht [2007, Figure 1]. As a concrete example, for the Gaussian kernel, one has a Gaussian spectral density (up to normalization).\n\nWe are happy to include the statement of Bochner's theorem in Appendix A.6 ``External statements'' and add a reference in the main part to clarify this point in the manuscript.\n\n\n__Comparison to Moen (2025).__ Unfortunately, we do not think a comparison with the recent work by Moen (2025) would be fair, since their method is designed to detect parametric changes whereas our proposed method is non-parametric. To elaborate: one could easily design a simulation study where Moen's procedure performs poorly, for example, by simulating data where the change occurs in the variance while asking Moen's algorithm to look for a change in the mean. Going in the other direction: if we design a simulation in which Moen's algorithm is run with a contrast function tailored to the specific moment in which the change occurs, then it will have an unfair advantage over the non-parametric methods we currently compare to, which do not have access to this information. \n\n__Detection of multiple change points.__ Detecting multiple change points in a sequential manner is an important problem which has not received much attention in the literature. However, having reviewed the proof of Theorem 3, we observe that the proposed RFF-MMD algorithm can indeed be extended to consistently detect multiple changes in an online manner and we were able to prove a guarantee on the detection delay in this regime, which we are happy to include in the appendices of the manuscript together with a detailed proof.\n\n\n__Benefit of no window parameter.__ As correctly pointed out by the reviewer, one key benefit of having  no window parameter is that there are fewer parameters to tune. A second benefit of having no windows is that our proposed method does not have the minimum detection delay that comes from having to observe at least a window length of data. The third benefit is that we do not \"forget\" data that falls out of a window. We note that, while we dub the elements of our data structure \"windows\" in Algorithm 1, these do not correspond to the windowing approach typically employed in online change detection contexts. Still, as each of our \"windows\" sees a summary of a subset of the data (with all windows capturing the full history), we believe that the naming is appropriate.\n\nWe hope these answers fully settle all open questions.\n\nPer August Jarval Moen. A general methodology for fast online changepoint detection. Technical report, 2025. https://arxiv.org/abs/2504.09573.\n\nBharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert Lanckriet. Hilbert space embeddings and metrics on probability measures. Journal of Machine Learning Research, 11(50):1517–1561, 2010.\n\nHolger Wendland. Scattered data approximation. Cambridge University Press, 2005."}, {"review_id": "AtTw9Faqt0", "reviewer": "Reviewer_4v7u", "summary": "The paper addresses a problem of online non-parametric change point detection. More precisely, the authors advance existing change point detection kernel-based methods and propose to approximate Maximum Mean Discrepancy using random Fourier features. Such an approach results in a faster procedure compared to established Scan B-statistics and does not require any historical data or a specification of window parameters. Theoretical results guarantee the control of the average running length or, alternatively, false alarm probability, bounding of detection delay, and its optimality in the minimax perspective. Experimental results also confirm the superiority of the method compared to several baselines.", "questions": "**Main questions:**\n\n(1) Do the authors consider other real-world datasets common for change point detection problems? What was the model's performance? \n\n(2) In the work, the authors use a Gaussian kernel for all experiments. Do the conclusions the same for other kernels? How do empirical results change when the used kernel does not satisfy Assumption 1? \n\nJust an additional comment. According to line 94, the authors consider independent random variables. It is another limitation of the work not mentioned in the corresponding section. However, I understand that taking into account the dependency of the data for change point detection is still a challenging task. \n\n**Minor comments:**\n\n(1) Footnote 1 should be placed near Table 1. Now, it is located on the next pages, thereby complicating understanding;\n(2) Line 216,\"In the following...\" missing comma.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper represents strong and consistent scientific work. The presentation is concise, the text is well-written, and the mathematician language is rigorous and accurate with all necessary articulation of corresponding attributes. At the same time, main concepts are explained in natural collocations, thereby enhancing the overall comprehension of the text. Although this research is closely connected with previous works (e.g., Scan B-statistic, M-statistic, KL-CPD), the proposed method overcomes several challenges through the framework of random Fourier features. Thus, my overall impression is good. \n\n**Weaknesses**\n\nMy main concern is devoted to the experimental part. The work considers two types of data: synthetic sets and MNIST sequences. Actually, neither of them corresponds to real-world tasks. The latent manifold of MNIST images is relatively simple and can be separated efficiently, even with linear methods. Therefore, the performance of the method on real-world data (at least to some extent from the real world) remains underexplored. One of the most interesting scenarios is the detection of changes in video data mentioned in line 21. Therefore, I recommend considering such data, but different typical low-dimensional sequences for CPD (e.g., Human Activity Recognition, EEG signals, financial data) are also worthy of consideration. Moreover, although I understand how the authors choose their baselines for comparison, I would rather want to see a wider range of competitors to make sure the novel approach is a new \"state-of-the-art\".", "was_revised": true, "final_justification": "In general, I have no sensitive concerns about the papers before rebuttal. \nI will recommend accepting the paper.", "rebuttal": "We thank the reviewer for the time and effort invested and for the valuable feedback. Below, we answer all questions in detail.\n\n__Other real world data set: MazurkaBL.__ To further validate our algorithm's performance, we additionally ran the proposed method on the \"M17-4\" sample of the MazurkaBL [Kosta et al., 2018] data set with the goal of detecting changes in the so-called \"sones\" (see their \"scripts/ismir\\_tutorial.ipynb\"); as in the article, we use the Gaussian kernel with the median heuristic. For obtaining the thresholds using Monte Carlo iterations, we slice the sone data along each change point and compute the test statistics obtained by the proposed method individually on each one. We then select the $1-0.1$ quantile across all test statistics so obtained as our threshold.\n\nTo then search for change points, we again slice the sone data, but in this case such that each slice contains precisely one change point, which yields a total of $25$ samples. We process each one of these with our proposed method and consider the first time the test statistic exceeds the threshold as detected change. In total, our proposed method flags $10$ change points too early, and, on the remaining $15$ has an average detection delay of $93.4$, with a median detection delay of $74.0$.\n\nWe also refer to our additional experiments on the popular HASC data set in the response to reviewer ``ArQr''.\n\n\n__Non-Gaussian kernels.__ Our theoretical results hold for any continuous bounded characteristic translation-invariant kernel, that is, any kernel that satisfies Assumption 1. Kernel functions that do not satisfy Assumption 1 (for example the unbounded exponential kernel; Chamakh and Szabó 2021) do not permit the Bochner representation (7) and hence can not be approximated by random Fourier features. In this case our method is not applicable. \nHowever, we emphasize that the class of kernels satisfying Assumption 1 is large and, in particular, encompasses most kernels typically employed on Euclidean spaces. For example, the considered class includes Gaussian kernels, mixtures of Gaussian kernels, inverse multi-quadratic kernels, Matérn kernels, or Laplace kernels.\n\nWhile, as indicated, all our results hold for these kernels, we recall from Section 7 that the particular choice of kernel influences the online analogue of testing power. Hence, in practice, one chooses a kernel function that captures the characteristics of the data. The Gaussian kernel with the median heuristic, used in our experiments, is a sensible default.\n\n\n__Non-i.i.d. random sequences.__ We agree that non-i.i.d.\\ sequences occur in practice and that considering only independently distributed data can be seen as a limitation. Intuitively, we believe that analogues to Theorems 1--3 can be obtained if one were to replace the independence assumption with a suitable notion of weak dependence such as strong mixing g [Bradley, 2005] or functional dependence [Wu, 2005]. However, we do not have a clear idea of how minimax optimality results in this setting (i.e., an analogue to Theorem 4) would look like. Hence, extending our results to non-i.i.d. sequences is interesting future work.\n\nWe hope these answers fully settle all open questions.\n\nLinda Chamakh and Zoltán Szabó. Kernel minimum divergence portfolios. 2021. https://arxiv.org/abs/2110.09516.\n\nRichard C. Bradley. Basic properties of strong mixing conditions. A survey and some open questions. Probability Surveys, 2:107–144, 2005. Update of, and a supplement to, the 1986 original.\n\nWei Biao Wu. Nonlinear system theory: another look at dependence. National Academy of Sciences of the United States of America, 102(40):14150–14154, 2005."}]

Author rebuttal:

Meta-review: The paper proposed a method for online nonparametric change point detection that builds on the kernel Maximum Mean Discrepancy (MMD) test, where the kernel MMD statistic is efficiently approximated using random Fourier features. The work provides a theoretical guarantee of the proposed method. Several weaknesses of the paper, such as the limitation to the kernel type and i.i.d. data, were pointed out by the reviewers. The author's rebuttal addressed the major concerns, and through the discussion, the reviewers reached a consensus on the merit of the work. The authors are encouraged to incorporate the rebuttal into the revised manuscript.
Decision: Accept (poster)