A nonparametric method for gradual change problems with statistical guarantees
Authors: Lizhen Nie
Dan L Nicolae
Venue: NeurIPS 2021 Poster (2021)
Keywords: Change point detection
gradual change
nonparametric

Abstract: We consider the detection and localization of gradual changes in the distribution of a sequence of time-ordered observations. Existing literature focuses mostly on the simpler abrupt setting which assumes a discontinuity jump in distribution, and is unrealistic for some applied settings. We propose a general method for detecting and localizing gradual changes that does not require any specific data generating model, any particular data type, or any prior knowledge about which features of the distribution are subject to change. Despite relaxed assumptions, the proposed method possesses proven theoretical guarantees for both detection and localization. 

A nonparametric method for gradual change problems with statistical guarantees
Lizhen Nie Department of Statistics The University of Chicago 1i lizhendstatistics.. wuw.sssiiiccc.ucc........o. edu
Dan Nicolae
Department of Statistics
The University of Chicago
nicolae@statisticc wchicago...........o edu
Abstract
We consider the detection and localization of gradual changes in the distribution of sequence of time-ordered observations. Existing literature focuses mostly on the simpler abrupt setting which assumes discontinuity jump in distribution, and is unrealistic for some applied settings. We propose general method for detecting and localizing gradual changes that does not require specific data generating model, particular data type, or prior knowledge about which features of the distribution are subject to change. Despite relaxed assumptions, the proposed method possesses proven thcoretical guarantees for both detection and localization.
Introduction
In a sequence of time-ordered observations {Yir : 1,2....,.. the aim of change point detection (CPD) is (a) detect: answer the question of whether the distribution of Yı, changes, and (b) localize: if it changes, answer the question of when. The classic formulation of CPD usually assumes that the possible change point abrupt, i.e., there is discontinuity jump in the distribution of Y.,r, leading to simpler problem. However, in many real-life situations, the changes in sequence happen smoothly or gradually, rather than abruptly. Figure illustrates some examples.
arrus axtrago temoo ature
0.55 0.10
10.5
1000 mturss
0.02
9.5
000-
8.
S&P
2008
7.5
800
1750
1850
1950
(a) Annual average temperature in central England.
(b) S&P 500 stock index daily returns.
Figure I: Examples of gradual changes. The vertical red dashed lines indicate the gradual change start points estimated by the method proposed in this paper.
The first example concerns climatology, and investigates the temperature patterns over years. Figure la depicts the annual average temperature in central England from 1750 to 2020, where we observe a smooth increase starting around 1850. The second example comes from finance. The S&P 500 stock index is an important indicator of the overall market. As shown in Figure 1b, its volatility level usually remains constant in stable market, and then gradually increases with the development of some events such as the financial crisis in 2008 or the COVID-19 pandemic in 2020.
Despite the wide variety of applications, inference for gradual changes is under-researched, and most existing methods require domain knowledge. Early research assumed that the gradual change follows particular parametric model. For example, Lombard (1987) considers setting where some
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

unknown parameter changes linearly, while others (Hušková, 1999; Hušková and Steinebach, 2002; Aue and Steinebach, 2002) consider models with polynomial changes.
Recent methods also consider nonparametric settings. However, most of them still require specific assumptions the data model. For example, Muller (1992); Raimondo (1998); Goldenshluger et al. (2006) consider the location model where first order moment of observations changes. Mallik et al. (2011, 2013) investigate stronger assumption: the mean change is monotonic. Mercurio al. (2004) consider the volatility model where second order moment of observations fluctuates. Quessy (2019) assumes that the sequence follows two stationary distributions at the beginning and the end, and the changing phase in- in-between is a mixture of them with weights changing linearly with time.
As far know Vogt and Dette (2015) is the only nonparametric method that applies to general types of models and data types. Despite its generality, the method proposed in Vogt and Dette (2015) requires prior knowledge about which stochastic feature(s) might change. Moreover, their method requires specification of a threshold determined through expensive simulations. Also, Vogt and Dette (2015) considers only the localization problem, while ignoring the detection step which is shown to be important for false positive control in real-data applications (Van den Burg and Williams, 2020).
We propose nonparametric method for detecting and localizing gradual changes. The proposed method requires no prior domain knowledge, and we offer theoretical guarantees on both detection (false positive rate, power) and localization (consistency).
2 Problem Statement
1.2,... , Suppose we observe a time-ordered independent sequence {Y,, 2,, general metric space ()r, - I1y) YG, is observed at time - L/T E [0, 1]. We are concerned with:
taking values in
(Detection) Deciding whether the distribution of observation changes with time u. This is formulated as a hypothesis testing problem with null Ho and alternative HA hypotheses shown below. Let P. be probability measure on ()), || lly) such that Y,T Pa for u = t/T, then
Hg Pa is constant over u E [o, 1].
HA: Pu is constant over u E [0, uo] for some un E (0, 1), but is not constant over u E [0, 1]. (1)
Further, we assume that P. is continuous with respect to the weak topology in the sense that Vu E [0, 1], P. weakly converges to Pu. as v + u.
2. (Localization) If rejecting Ho in step 1, obtain an estimator و of the gradual change point p" where the probability measure Pa starts change, i.e., p² sup(u P. Po. Yo [0, v/}.
Notice that we do not put specific assumptions on the data type or distribution of Y,r and thus, our formulation allows large number of special models such as
location model: YL ((t/T) +
(2) (3)
volatility model: Yur = (t/T))&,,
where (()),a() can be any continuous function, and E 's are zero mean i.i.d errors.
Notations. We denote [x] as the least integer no smaller than æ, 1== (1, (1...... ..)....)T......... .1) E Rdd, Ia E Rdd
the identity matrix. We use Il to denote indicator function, " weak convergence, E+ the set of positive integers. For set of constants dr, by and random variables Xr, we write dr = O(rr) if there exist constants C1, C2 > 0, to E Z_ s.t. Ciar & by I Czar, VT 2 tg. Denote X, = Og if Xr/ or is stochastically bounded, and Xy. op(ar) ) if Xr/or converges to zero in probability.
3 Methodology
Existing statistic. We consider first univariate Ys. Suppose the change is in EY,r; traditional CUSUM statistic (Page, 1954) solves CPD problem by defining
M Y.. s/(uT) Σ [u2 Y.r, for any 0 S v < a $ 1. Čr(u, r) = 1/TE|1 IVT
which compares cumulative sums of Yr,r over different time spans [0, v] and [0. m). Then
Dypi = (a Or( v)]. for any 0 5 5

---

Figure 2: Plots Vrr (top row) and their Dt (t/T) (bottom row) against f. The blue vertical line denotes true
change point. Data in column 1, follow location model (2) with & ~ N(0. 1), and (1()) = T(1 S S 2/3)(3u 1) + I(u > 2/3). pz(u)= 2 sin(44(u 1/3)) S S 2/3) + 2 (0on4//3)))0) /3) u 2 2/3), respectively. Data in column follows volatility model (3) with E ((, 1) and (()) p ()() + 1. Column 1, set = [ : æ + ær), and column
{ (f:
can be used detect changes in feature ,Y, over time span [0, Intuitively, there are no changes over [0, uj. Dymi (u) should be small. For example, in Figure 2, the first and second column depicts sequence with change in EY,r (shown in top row), and Dymi (shown in bottom row) take small values before r" 200 where 7* [Tp*], and then grow substantially. Thus, Dy (u) essentially measures the variation over [0, u| in these univariate settings.
For multivariateestmnctured Y.T or for changes in more general features of the form Ef(Y,) where f y > is a measurable function, Vogt and Dette (2015) replaces Dymi with
Drm (u) = Cr - 1/T (oT) f(Y.)) v/ o/ [MT] f(Yrr).
(r(u, /rr(,, v. f)l, where
(4)
De takes supremum over a pre-specified set of functions F to ensure that changes in Bf(rr) for all f E F are considered. Note that Duni special case of Dirn with F {f x}. and column of Figure 2 sets F= {f f x
There are three main issues with DE First, it relies heavily the pre-specified function class F. Also, to calculate Deen F can only contain a finite (usually small) number of functions (e.g., f: + x or f x + x²), the choice of which relies heavily on prior knowledge about which features might change. When F is misspecified, Dim can be non-informative and fail subsequent tasks. Second, Deea0 does not consider the scale of Cr(, f which could be incomparable for different ʃ's. Third, the limiting distribution of Demmm (.) unknown, leading to computational challenges in subsequent analyses.
Proposed statistic. We introduce new statistic that puts minimal assumptions on data types and generating process, and is free of the issues discussed above. It is motivated by the recent success of applying kernel approaches to abrupt CPD problems (e.g.. Harchaoui et (2008); Li et al. (2015); see Section 7 for more details). These kernel approaches assume access to positive semidefinite kernel y x y > R that measures pairwise similarity among observations. Compared with features, kernels are more flexible and easier to specify, especially for structured data, showing great potential for solving gradual CPD problem. Inference starts with measuring data variation time span [0, u]: for each possible change point < u, u divides the observations into two groups: those coming before [Tu]] and those after [Te]. Note that the average similarity among observations within the same group is:
S Swvithin (u, v) = 0.5(l)
2' K(Y,,, Yir)) + 0.5(r E1 Y.T)),
where = [o7 [uTT, and the average similarity among observations between different groups
Shetween (u, v) = [((r (((--1)--1)
k(Y,,, Y..)).
3

---

Intuitively, k(y. y/) should in general be larger if y.y/ follow the same distribution, and smaller if v. v/ follow different distributions. Thus, if e is the true change point, expect Sqyithin (u, v) to be
large compared with Sherween (u, v). This intuition underlies the following statistic,
(u) = max RT(u, v) where RT(u, v) = 20 (u- u)² /22 (Spiiin (u, v) St (u, u}}-
(5)
(6)
Dr takes the maximum over E [0, ud] using a similar idea as Dyri and DT The scaling factor uu =)2 /u" is important and ensures that the limiting distribution of Dr is well-defined for all
E (0, 1] (see more details in Section 4). Dr plays the same role as De and measures data variation among [0, u).
Note that Dr has also a CUSUM-style representtnnn, which is crucial for understanding its theoretical properties. Define a centered kernel ko(y, y/) k(y, v/) Ey k(y, Y) Ep kty', Y) By k(Y, Y"). Then kn can be decomposed in terms of eigenfunctions { } w.r.t Po as:
with koo(y. (0,,)")),))))((())) = (t)) J (5 (2)dP(()) = 63.5
- Ey,
and 65.5' is the Kronecker delta function. We denote the feature map @ associated with Ko as ((v) = (A 1/1 (V).
X (2),,, ... E H. (d(v),(())) = >E)00))) = ko(v.
1/2 Using properties of 1/ and denoting || 11 = (5 ( we have
Er(u,v) =r(,,,)=11/T)>> 11///11/ J ((Y,)) v/(uT) Jull o (Y 1r (8)
Equation (8) helps the comparison of Dy against Deg In general, Dr has three advantages. First, recall that Dgen strongly depends on the specification of the function class F; we allow implicitly much larger F with infinite functions. For example, by using universal kernels such as k(y.1/) = exp{- ly y' /113/22, we consider any change in (Y,r), cardinality and satisfies the property that under mild assumptions, there always exists f E F such that (X) * EX(( when random variables X, X' follow different distributions. Second, the asymptotic distribution of Dee" (as n grows to infinity) is intractable, caused by its dependence structure on Ör. There are two key facts, under Ho. for fixed u, as T goes to infinity,
F where F has infinite
Cr(u,v, U, 0j) 4 Gaussian random variable, and ElÂr(u, v, ,,) Cr v, dr)] 0, Vj.j' E Z4.
It implies Ür(u, v, Φ5) are asymptotically independent Gaussian random variables (r.v... Since the sum of squares of independent Gaussian r.v. follows a known distribution (chi-square), in view of (8), the asymptotic distribution of our statistic is much simpler than that of Dee0 Third, using kernels to define Ky does not lead to technical/mmplementtioo issues. In contrast, if we define R directly using (8) with the function class = {Ø, = 1, 1,2,.... ... replaced by an arbitrary function class of infinite cardinality, the infinite series will not necessarily converge, and even when it converges, it may not be calculated exactly. Using kernels, we circumvent this issue and with the trick mentioned in Appendix A, the total cost of calculating Dr(u) for all u's takes O(T2) in both time and space. Remark 3.1. Some useful kernels for the gradual CPD problem: (i) For y gd we recommend using the dot-product kernel k(y, 3²) = (y, y''R"' if location model (2) holds. Here oj x (x1, ...,...... xaa) x. Er, X,, Vj 1,... d. When d 1, Dy with this kernel equals Degn with F= (f: x x - X) and Dypi. (ii) For y = R, we recommend using k(y, v/) = (3 volatility model (3) holds. Here oj x + x² a where
Ex~P, X². And Dr with this kernel equals DRm with = {f : + x² a). (ii) For any general V, k(y, 3y' -elf-lly- y //1 is the RBF kernel with bandwidth h > 0. This can be set as the default kernel without any prior knowledge about data model.
Now will utilize Dr for the detection and localization of gradual change points.

---

Defection. As shown in Figure 2, under a good choice of k, Dr(u) summarizes the degree of variation over time span [0, u| and satisfies
(r( is
[smlll, when
u S p²: u > p¹.
(9)
large,, when
The case of no change point is equivalent to p 1. The existence of change point can be tested using (1). The p-value depends on the asymptotic null distribution of (1), the rigorous establishment of which requires many technical details and is deferred to the next section (Theorem 4.4). Practitioners can use the following formula to calculate p-values:
PPTTD, (1) > x) ~ 2(4+3)/2 (
(0-1)/2 2x/2, Ih (1--111-AAAA) 11/2)) (10)
where A 2 A2 2 ..... by are eigenvalues of the matrix (1/T)Ko where
Ko- HKH E RTT K = [k(Y,... Y,r)) E RTx and H = Ir (1/T))],, (1I)
and @ is the estimated multiplicity of the leading eigenvalue. Accuracy of this approximation depends on the accuracy of estimated eigenvalues. In practice, we find it works well when q is small (say, q S 5). When @ is large, we recommend estimating p- p-values by permutation tests.
Localization. Once a significant change point is detected, the next step is to localize it. Observing property (9) with Dr replaced by De Vogt and Dette (2015) propose an estimator for p² as:
p T Et I(T (t/T)= bit"),
where the scaling factor / ensures that T' follows non -on-degeneeate distribution asymptoti- cally as data size goes to infinity, and 1 is set to the (1 - at) quaantile of the limiting distribution of supre D7 (u). In practice, both p" and limiting distribution of Dem (-) are unknown, thus by is approximated by a two-step procedure with expensive simulations. For our statistic, we find that
under the null, (u) and u1D follow the same limiting distribution for any u. It implies that we can estimate p" by
S (I(TT)) where cr = uby,
(12)
and the scaling factor T ensures that TDr has a non-degenerate limiting distribution. Here, is affected by CT: a larger er will lead to larger and vice versa. Ideally, the optimal choice of er should minimize a measure of error, and we propose using (p) = E م p¹1 It depends on the finite sample distribution of Dr and could be hard control in nonparametric settings, but we know the asymptotic distribution of (.) (Theorem 4.4). Thus, we choose the er which minimizes the I error of the population version pd8 of p:
p²1 with p² = J I(Lo(u) S cr(u))du+ + /T + TDx()) S cr()))du,
where Lo).), (-) correspond to the asymptotic distribution of properly re-scaled and re-centered Dr(.) before and after p", respectively, and they are defined in Theorem 4.4. Under some assumptions, minimizing 4 (px²) leads to
(13) where k 2 2 is determined by the smoothness of change and the smoother it is, the larger is. The derivation of Equation (13) is included in the next section. The theoretical value of x is defined in Assumption 4, and it depends the alternative distribution of Y.T and the kernel k. For practitioners, we only need to know it for abrupt changes and any choice of kernel, x = 2 (indeed, our method is also applicable for abrupt changes). For RBF, if the change in E exp (Y.T} can be approximated by (u p²) p²)8 in time span
by / log T,
1p" p² + e) for some small E >> O, have k 2,3 2. We emphasize that the choice of x does not affect the consistency of p. In experiments, using rule of thumb x = 4 is introduced next.
works well. An alternative estimator that is less sensitive
Max-gap estimator. Despite its good theoretical properties, I has often a large positive bias. This arises from the nature of gradual changes, and is common to previous gradual CPD methods as discussed in Vogt and Dette (2015). Intuitively, we need to wait for enough signal strength in order to identify the gradual change point. To design less biased estimator, recall that in Figure 2, we plotted Dr(-) against time and casily visually identified the change point as the time when Dr(() starts to grow. For example, for data in the first column, a zoomed-in region is shown in Figure 3, where the
black line is 7 T-)(-) and red line cT (T()). In Figure 3, the growth starts around the point 285 (shown in
5

---

brown vertical line). However, using P gives f = 342 (shown in green vertical line). We want an algorithm capable of iden- tifying this elbow point (285). Note that from Theorem 4.4, we have
comparison of estimators
original est max-gap est Irah T'DBT) cITT)
mest
-(or(w) [D)( iinereases with u, i S p decreases with u,
-
if u > p².
Thus, p" should be the where -u) (u) (in Figure 3, this is where the gap between the red line and black curve is maximized). It suggests setting
(T) is maximized
0
1.00
200
330
400
m arg (0, - (D),
(14)
time
Figure 3: Comparison of max gap es- timator and original estimator in simu- lated data.
where m arg max takes the largest value in the set formed by arg max. In Figure 3, f is shown by the brown line.
Compared with أ. empirical studies show two advantages of the max-gap estimator pt more accurate, and is much less sensitive to choice of k. Some intuition for insensitivity to k: in Figure 3, x changes the slope of the red line and a slight change in slope does not affect the time where its gap between the black line is maximized. The higher accuracy of á also has theoretical explanation, which is included in the Appendix due to space limit. In short, the 4 error of أ consists of two parts: the overestimation error E[A- p*]+ and the underestimation error Eip² ما+ with [x]+ denotes the positive part of z. There is always a trade-off between overestimation and underestimation. Roughly, focuses more controlling the overestimation error (delay) while guaranteeing consistency of the estimator, since delay is the main concern in small samples. In contrast, á controls the over/under- estimation error equally, which might be less accurate in small samples.
Practical considerations. All steps of the proposed procedure are summarized Algorithm in Section A of the Appendix. There we also discuss its time and space complexity.
4 Theory
This section establishes all theoretical results mentioned previously.
Asymptotic distribution of Dr. In order to utilize Drr for downstream tasks, we need to know its asymptotic distribution. To establish that, we will first introduce some technical assumptions.
Assumption 1. 3M E (0, +oo). Vt E 21, ... ,T}. k(Y,,T, Yi,T) S M2 almost surely (a.s.). Remark 4.1. Assumption requires that the kernel is a.s. bounded for all Y,,.. is weak assumption which is satisfied when k(.,-) ) is continuous and y is closed and bounded, or when &s is RBF kernel.
Assumption 1 suffices for getting asymptotic null of Dy. Under HA, however, need to restrict the changing pattern of Yer: roughly, we require the change to be gradual, so the speed of change cannot be too fast compared with sample size. One useful concept to regulate such behavior the locally stationary process, which has been used in Vogt and Dette (2015) for gradual CPD problems.
Assumption (Locally Stationary Process). The array {Y.r : 1, T] is a locally stationary process, i.e., Vu E [0, there exists strictly stationary process (Yz(u) : Z} s.t.
|Yrr Y((w))ly I (It/T ul + 1/T) (u) a.s.
where (Urr(u): :t = 1,2, ,T is an array of positive random variables which satisfies E (u)) S co for some constant co E (00) 7 > 0.
Remark 4.2. Assumption 2 ensures that locally around each u = t/T, {Yrr] can be approximated by stationary process (T)). The constant y measures how well Yer is approximated by Y, (u): the larger y is, the better the approximation will be.
Define
= D(u)= = max K(u, with ICuu, v) = ( - v//fur(w)ddlll (15)
where ya()) = (=) ... TT, (,(()) (-)).. Comparing Equations (15) and (8), we find
that (r, v) is in fact an estimator for IC(u, v) and thus, Dr(u) is an estimator for D(u). Using the

---

decomposition Dr(4) - D(u) + [Dr(u) - D(u)], in order to study asymptotics of Dy, we only need study the approximation error Dr -D We will need the following assumptions:
Assumption 3. The feature map & and stochastic processes (uz(u): [0, Vj e E+ satisfy
(i) [| "(v')ln I -illy-v'li y for all y, v' e.. (ii) 7 2 2 where y is defined in Assumption 2.
(iii) Ej=1 max (u) < +00.
Remark 4.3. Condition (i) requires sufficient smoothness for I which is always satisfied for suffi- ciently smooth kernels Intuitively, this helps us preserve the smoothness of the change in Y.,-- Condition (ii) requires that Yır can be sufficiently well approximated by (ı( in the sense that (u) has finite variance. Condition (iii) roughly says that μ4j has a well-defined Riemann integral over [0, 1] so that the integral in D can be approximated by the Riemann sum in Dr.
Now we are ready to present our main result, where pa = corresponds to no change point. Theorem 4.4. Suppose Assumption holds.
(1) For any E (0,
T(D((u) D(u)] ", max (0.,) - Lo(u).
(16)
where X ss are defined in (7), and Wi(-), I,... are independent standard Wiener processes. (2) If. in addition, Assumptions 2 and 3 hold, any u E {p",, we have
(T) - D(u)] ", max G(v, u) =: (u(u,
(17)
where for any u, G(., u) a sample continuous Gaussian process.
Remark 4.5. Both >i=>>iWa - 2 and G(:, u) sample continuous and thus, the right hand size of (16) (17) are well-defined. Xy's are determined by Pa. k and (16) states that the higher the noise level of Po is, the more dispersed the asymptotic null of Dr will be. Note that the asymptotic distribution of Dr is quite different before and after the change point: before change point, for each u. (T( = (T and after re-scaling, (u) is maximum point, (u) = (u)) - Op 1/2) and after re-centering and re-scaling. Dr (u) maximum of a Gaussian process. This distinct property of D-(-) is critical for the success of the proposed procedure.
chi-square process; after change
Detection. To calculate p-values, Theorem 2.1 of Liu and Ji (2014) says that for Vn. E Z4 and A1 b Apt1 2 Apt2 2 ... 2 An > as x + 00,
P(max,e Ei (Wi(e) - uW)(1)) > r) = 22(++))/2(((/22)) VF ( exp 2x (1 II 11 (1- 1/2 (1+
Combined with Theorem 4.4, it implies (10). Also, we have the following:
Corollary 4.1 (Power Consistency). Suppose Assumption 1, 2, 3 hold. If VTD(1 + 00,
Vx > 0, P(TDr(1) x) 1, T
Remark 4.6. Corollary 4.1 shows that power of the proposed test affected by the magnitude of change measured in D(1). As long as D(1) goes zero at rate slower than 112 the change will be detected if it exists; it ensures correctness of the detection step.
Localization. Recall we need to optimize cr. This requires regulating the local behavior of D at p²:
Assumption 4. There is cusp of order k at p² for D(-), i.e., D(u)
>0 u- p" +
[u-p*)=
Remark 4.7. Assumption 4 says D can be locally approximated by a Taylor-tppe expansion around
p", which is common assumption for gradual CPD (Mallik al., 2013; Vogt and Dette, 2015).
Theorem 4.8. Suppose Assumptions 1, 2. 3. 4 hold, and or( = wdr. The minimizing I (p²)) satisfies
(T(u) = (urrr log T)/2, 1/k.
(18)
7

---

Remark 4.9. In Equation (18), the larger the noise level X1 is, the larger or is. The smoother the gradual change is (the larger K is), the smaller er is. And r can be viewed as a tuning parameter s.t. if we are less tolerant to delays in Å. we could set to be small, and vice versa. In practice, á is often overestimated. Thus, we suggest choosing = 1/K, which ultimately leads to (13).
Theorem 4.10. Under Assumptions 1, 2, 3, 4 and Equation (18), ý - p = op(1), P- p== op())
Remark 4. 11. Theorem 4. 10 shows that the original estimator and the max-gap estimator are both consistent, and establishes theoretical guarantees for the localization step.
Simulations
To better understand finite sample properties of the proposed method, we evaluate its performance in simulations and against baselines. Additional details and results including type I error (p-value calibration). power comparison and performance comparison on strings are included in the Appendix.
Data generating process. We set p² = 1/3. Following Vogt and Dette (2015), we consider a location model, volatility model, and we add a network model. For the location model (2), include univariate cases with E, ~ NN, 1) and four different types of change ordered in increasing difficulty: (i) linear change [i(u)
111/31333 < S 2/3 - 1)++ - I(u 2 2/3): (ii) quadratic change p2(u) = 1(1/3 < u S 2/3 1)2² + I(u 2 2/3); (ii)) one-sided change pa = 2 sin (2
S u S 2/3)+ 2/3) in the sense that uz(u) 2²( for all p²; and (iv) complex change (a(u) = (0n(4A(u-133)I(((
S u 2/3) sin /3) 2 2/3). We also consider multivariate YI, E Rd where (45 = // Ct ~ Na(0, Ia). For volatility model 8t NO,, Vi =1: =1,4. For network model, we set Y.. the Redos-Reeyl random graph with 10 nodes. At each time u. E [o, 1], there exists a 3-node community such that the possibility of forming an edge among them follows Binomial (1, p(u)) independently. Here p(u)= = 0181(1/3= S S 233 - 1) + 0. 2 2/3) 0.1. The probability of forming an edge between other pair of nodes always follows Binomial (1, O.1).
(3), we consider (w) (4((u)
Baselines. We consider four gradual CPD baselines, ordered in increasing generality: prely (Hušková, 1999) which requires univariate location model with polynomial change, pa (Mallik et al., 2013) which requires univariate location model with one-sided change, pmmix (Quessy, 2019) which requires any general model with mixture type of change whose mixture weight changes linearly with time, and jrsc (Vogt and Dette, 2015) which does not have any particular constraints on model or type of change. We also include three nonparametric abrupt CPD methods: KCpA (Harchaoui et al., 2008), Zu (Chu et al., 2019), and Q (Matteson and James, 2014)).
Detailed setup. Setting I (main experiment): We set T = 600. For gome-side we tune the bandwidth on 20 independently generated datasets among {0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1, 5). For each dataset, for fairness use the same kernel for P. á and KCpA, and use its corresponding
distance for Q, Zw and function class FF for paem_ For location model, F = {f : x + 2,, Vi = 1.... .d); for network model, F {f I Tij. Vi,j = 1.... 10}; for volatility model, F F : x z²), For aaoly we set the polynomial to the true degree if the polynomial model is correct, and otherwise. As recommended by their authors, we use a granularity of 20 for zTnix and minimum spanning tree to construct the binary graph for Zw. Threshold for peen is computed using strategy described in Section 6 of Vogt and Dette (2015).
Setting II (influence of bandwidth): We note that both the proposed method and KCpA are kernel- based. In setting I, we use the kernel that is theoretically best for both of them. As suggested by reviewers, in this setting, we search for the empirically best RBF kernel k(y. v/) = exp(-llu Ily y a/l2/h/ where is the bandwidth and is tuned among (0.01, 0.05, 0.1, 1, 5, 10, 20, 50, 100, 500} on 20 independently generated data sets. Here || is the le distance for scalars/vector and Frobenius norm for network. We set T = 210 and report the testing performance on 20 separate testing sets.
Metrics and Results. We report the power and l error of estimated change points. For faimesss power of all methods are computed via 500 permutations under significance level a = 0.05. Due to space limit, detailed results on power are included in the Appendix performance of all abrupt as well as gradual CPD methods are similar. In terms of localization, however, performance varies. In Table Ia, the abrupt CPD methods (KCpA, Q, Z..) have a large error in most settings, which is not surprising because KCpA, Q are designed for abrupt changes. For ppoly, / jone-side which require assumptions on the changing form, the localization is accurate when assumptions are satisfied, but
8

---

Table I: Comparison of average I1 localization error over 20 simulations. Numbers after :: the standard error of the average. Methods marked with means not applicable to that model. (a) Setting I.
MOUBEL
LOCATION
VOLAVILITY
NLTWORK
50 LINEAR
10
CHANGE
LINEAR
QUADRATIC
ONE-SIEE
COMPLEX
FINTA
UINRAR
LINEAR
COMPLEX
LINRAR
0.09#0.01
0. 18+00.01
0.03=00.00
0.03-20.01
0.07=6.01
0.06:0.01
0.05=0001
0.15+0.01
0.05-+0.00
0.10:1.02
0.10.10.11
0,2410.01
0.08.10.00
0.05:10.01
0.08-0001
0.10.0.01
0.0910001
0.2610.01
0.1210.00
0.1110..2
0.05++0011
0,09+0002
0.10=6.01
0.2340.00
0.07.1001
0.09110.0
0.02.10.00
0.62.10.00
0.05:10.01
0.09110.01
0.14::0.00 0.00
0.12:20.00 00
0.08 00
0:18:0.02
0.43:00.00
0.08::0011
0.14:10.00 00
0.17:10.01
0. 0.2411001
0.07::0.00
0.05:10.00
0.13=0001
0.15:0001
0.142:0.00
0.2611001
0.12:00.00
0.27:10.00
0.18++0.01 01
0. 0:23++0001
0.05+00.00
0.27+00.00 00
0.16-0.01
0:17-0.00
0. 0.166+0.00
0.21+0.01
0.06++0.00
0.16+-0.01
KCBA
0.1811001
0.2310.01
0.0510.00
0.27110.0
0.16.0001
0.16.00.00
0.16.10.00
0.2110.01
0.06100.00
0.1610.01
0.24110.04
0.29110.4
0.0910002
0.29.10.01
0.16:0001
0.17.0001
0.18100.11
0.1810.03
0,1610.03
0.1610.02
(b) Setting II.
MODRI
LOCATION
VOI ATILITY
NATWORK
20
50
10"
QUADRATIC
0.1410.01
0.1910.01
0.05.10.01
0.04.10.01
0.01
0.08.0.01
0.0810.01
0.1510.01
0.1310.01
0.02.1.011
0.12:0001
0.18:0001
0.09::0.01
0.07=#0.01
0.09=0.01
0.07=0.01
0.11=:0.01
0.15+0.01
0.21#0.01
0.07:#0.01
KCHA
0.18#0001
0.23+0.01
0.05=00.01
0.29#0.001
0.21=0001
0.16=0.01
0.18=00.11
0.28#0.02
0.23+00.06
0.17=00.01
poor otherwise. auix performs well in low dimensions and when the change (approximately) satisfies its assumption, but poorly when either one is violated. The proposed estimators p, ý are robust across different settings and ş has improved performance over p. peen is also significantly outperformed by P. Finally, note ğmix,, pare are more computationally expensive than the others. In Table 1b, the conclusion consistent where we use RBF kernel with tuned bandwidth. Together, Table I shows the advantage of ý. in terms of handling general types of data and general types of changes.
6 Real Data Applications
Different from most machine learning tasks, there are currently no benchmarking dataset with human annotations for gradual CPD. Thus, we consider the applications introduced in Section 1, and compare our result with known external events and/or other CPD estimators.
Central England Temperature. The Central England Temperature (CET) record (Parker et al., 1992) under Open Government License is the oldest temperature record worldwide and is a valuable source for studying climate change. It contains the monthly mean temperature in central England from 1750 to 2020. Since there is cycle of 12 months for the measurements, following Horváth et al. (1999), we view the data as n = 271 curves with 12 measurements on each curve. We set k(y, v/) = y TTy y/ where y. y' E 12 Using max-gap estimator, we identify 1827 as the change point (shown in red vertical line in Figure la), which roughly corresponds to the beginning of mass industrialization and is close to the 1850 estimated by Berkes al. (2009).
S&P 500 Index. The S&P 500 is a stock market index which tracks the stock of 500 large US companies and usually used as benchmark of the overall market. We investigate the daily return data of the S&P 500 index! in two periods, one from 2008/01/02 to 2008/12/31 and another from 2019/06/03 to 2020/06/01. Both time periods contain a change point where volatility level gradually increases. Following Vogt and Dette (2015), the daily return Y.r roughly follows the volatility model (3) and our task is to identify changes in al.). We define the kernel as k(y. y²) = y² (v²)² where V. R. In both periods, change point 2008/09/16, following Lehman Brothers Bankruptcy in September 15 which is often viewed turning point in the crisis. The second period has an estimated change point 2020/02/24, days in the initial phase of the community spread of COVID-19 in the United States. The estimated change points are shown in red vertical lines in Figure 1b.
detect change under a 0.05. The first period has estimated
7 Related Work
Here we discuss some related work, with some additional reviews included in Section E in Appendix.
' Dow Jones Indices LLC, S&P 500 (SP500J. retrieved from https: //fin/n/////ne////// yahoo.. com/ /uunt// XSEosPC/history/.

---

Difference with Vogt and Dette (2015). The major improvements of this work over Vogt and Dette (2015) are discussed in detail in Sections 1, Other differences include: Vogt and Dette (2015) allow correlated observations, while we assume independence; Vogt and Dette (2015) uses estimator (3), while we propose refined max-gap estimator that performs better empirically. We note that the our method might also be adapted for the correlated case, possible direction for future work.
Abrupt CPD. Abrupt CPD methods assume the distribution remains stationary until the change point when it jumps to another distribution, and remains stationary there. There is a rich literature on them; see Niu al. (2016); Aminikhanghahi and Cook (2017); Truong et al. (2020) for detailed surveys. In our experiments, we find that abrupt CPD methods seem to produce poor localization estimators for gradual changes. Here we explain this phenomenon by giving toy example in which the abrupt CPD methods fail to be consistent. Consider the case where Y,, = f (2/T)) with (u) T(1/3 /3 S u S 2/3 - 1) + T(u 2 2/3). Recall that all three abrupt CPD methods we consider (KCpA, Q, 7..)) estimate the change point as
P = arg max (()(), P((1),
(19)
where d( (())((), (t)) is some (standardized) discrepancy measure between the two groups of data separated by L. Notice that Equation (19) differs fundamentally from the proposed estimator (12). For Q, if we set a 2 in Equation (4) of Matteson and James (2014), one easily show that ø converges to 1/2, which is different from the truth 1/3. This same observation also holds for KCpA and Zw with more complicated analysis, but the general observation is that estimators of the form (19) may fail to be consistent under some gradual changes.
MMD. The Maximum Mean Discrepancy (MMD) is proposed in Gretton et al. (2012) for two-sample tests. We note that our intermediate statistic Cu, v) is similar to MMD. However, we emphasize the differences here: First, MMD is designed for two-sample tests where all theoretical analyses are based on two fixed samples, while we aim at the change point problem where we do not know where the true change point is. Thus, our final statistic D, requires extra and careful handling (e.g., the scaling factor o²(u u) /v² and the max over E [0, uJ). These extra terms complicate the theoretical analysis (see Theorem 4.4). Second, the alternative in two-sample tests is that the two groups of data follow two different distributions; however, with gradual change point problems, we really do not have two distinct distributions but an infinite number of different distributions! Indeed, the main theoretical difficulty of this work lies in characterizing the behavior of Dr under the alternative with gradual changes, which is quite different from the (local) alternatives in two-sample tests and requires more involved analysis. Further, the more difficult task we address is to localize the change point (instead of detecting change points), which does not exist for two sample tests.
CUSUM. The CUSUM principle was proposed by Page (1954) and has led to a rich literature. Some papers have investigated using CUSUM under gradual changes (Bissell, 1984a,b; Gan, 1992), but they considered only simple settings with a linear trend in the mean of univariate data, and their analyses are based mostly on empirical studies.
Kernel-based CPD methods. Existing bessel-based CPD methods all focus on the abrupt settings (Harchaoui et al., 2008; Arlot et al., 2012; Li et al., 2015; Garreau et al., 201 8). We emphasize that their method is fundamentally different from ours, and, as far as we know, none of them produces a consistent localization estimator in the settings considered in this paper.
8 Discussion
We propose a general method to detect and to localize gradual changes in sequence data. Despite the relaxed assumptions, the proposed method is theoretically guaranteed, and the proposed max-gap estimator achieves good empirical performance. Note that the proposed method also works for abrupt CPD with Corollary 4.1 and Theorem 4.10 hold. In contrast, many abrupt CPD methods perform poorly in gradual change settings. The trade-off is that for abrupt changes or gradual changes with known pattern (e.g., polynomial), our method often does not perform as good as those designed especially for those settings. There are no foreseeable negative social impacts of this work.
10

---

References
Aminikhanghahi, S. and D. J. Cook (2017). A survey of methods for time series change point detection. Knowledge and information systems 51(2), 339-367.
Arlot, S., Celisse, and Harchaoui (2012). kernel multiple change-point algorithm via model selection. arXiv:/202.387.
Aue, A. and J. Steinebach (2002). A note estimating the laaanne--ointt of gradually changing stochastic process. Statisties & probability letters 56(2), 177-191.
Berkes, L. R. Gabrys, L. Horváth, and P. Kokoszka (2009). Detecting changes in the mean of functional observations. Journal of the Royal Statistical Society: Series B (Statistical Methodol- ogy) 71(5), 927-946.
Bissell, A. (1984a). Estimation of linear trend from a cusum chart or tabulation. Journal of the Royal Statistical Society: Series C (Applied Statistics) 33(2), 152-157.
Bissell, A. (1984b). The performance of control charts and cusums under linear trend. Journal of the Royal Statistical Society: Series C (Applied Statistics) 33(2), 145-151.
Brown, B. M. et al. (1971). Martingale central limit theorems. Annals of Mathematical Statistics 42(1), 59-66.
Chen, H., N. Zhang, and L. Chu (2014). gseg: Graph-based change-point detection (g-segmentation). package version 0.I. Available at CRAN. R-project. org/package= gSeg.
Chu, L., H. Chen, et al. (2019). Asymptotic distribution- free change-poin detection for multivariate and non-euclidean data. The Annals of Statistics 47(1), 582-414.
Dehling, H., Rooch, M. S. Taqqu, et (2017). Power of change-point tests for long-range dependent data. Electronic Journal of Statistics //(1), 2168-2198,
Gan, F. (1992). Cusum control charts under linear drift. Journal of the Royal Statistical Society: Series (The Statistician) 41(1), 71-84.
Garreau, D., S. Arlot, et al. (2018). Consistent change-point detection with kernels. Electronic Journal of Statistics 12(2), 1440-4486
Goldenshluger, A., A. Tsybakov, A. Zeevi, et al. (2006). Optimal change-point estimation from indirect observations. The Annals of Statistics 34(1), 350-372.
Gretton, A., K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola (2012). A kernel two-sample test. The Journal of Machine Learning Research 13(1), 723-773.
Harchaoui, Z., E. Moulines, and F. Bach (2008). Kernel change-pon point analysis. Advances in neural information processing systems 21, 609-616.
Horváth, L., P. Kokoszka, and J. Steinebach (1999). Testing for changes in multivariate dependent observations with an application to temperature changes. Journal of Multivariate Analysis 68(1), 96-119.
Hušková, M. (1999). Gradual changes versus abrupt changes. Journal of Statistical Planning and Inference 76(1-2), 109-125.
Hušková, M. and Steinebach (2002). Asymptotic tests for gradual changes. Statistics Risk Modeling 20(1-4), 137-152.
Inglot, T. and T. Ledwina (2006). Asymptotic optimality of new adaptive test in regression model. In Annales de l'Institut Henri Poincare (B) Probability and Statistics, Volume 42, pp. 579-590. Elsevier.
Kim, S.-J. Koh, S. Boyd, and Gorinevsky (2009). é trend filtering. SIAM review 51(2), 339-360.

---

Levenshtein, V. et al. (1966). Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, Volume 10, pp. 707-710. Soviet Union.
Li, S., Y. Xie, H. Dai, and L. Song (2015), M-statistic for kernel change-point detection. In Advances in Neural Information Processing Systems, pp. 3366-3374.
Liu, P. and L.. Ji (2014). Extremes of chi-square processes with trend. arXiv preprint arXiv:
Lombard, F. (1987). Rank tests for changepoint problems. Biometrika 74(3), 615-624.
Mallik, A., M. Banerjee, B. Sen, al. (2013). Asymptotics for p-value based threshold estimation in regression settings. Electronic Journal of Statistics 7, 2477-2515.
Mallik, A., B. Sen, M. Banerjee, and G. Michailidis (2011). Threshold estimation based on ap-value framework in dose-response and regression settings. Biometrika 98(4), 887-900.
Matteson, D. S. and N. A. James (2014). A nonparametric approach for multiple change point analysis of multivariate data. Journal of the American Statistical Association 109(505), 334-345.
Mercurio, D., V. Spokoiny, al. (2004). Statistical inference for time-inhomogeneous volatility models. The Annals of Statistics 32(2), 577-602.
Moghtaderi, A., P. Flandrin, and P. Borgnat (2013). Trend filtering via empirical mode decompositions. Computational Statistics Data Analysis 58, 114-126.
Muller, H.-G. (1992). Change-points in nonparametric regression analysis. The Annals of Statistics, 737-761.
Niu, Y. S., N. Hao, and H. Zhang (2016). Multiple change-point detection: A selective overview. Statistical Science, 611-623.
Page, E. S. (1954). Continuous inspection schemes. Biometrika 4/(1/2), 100-115.
Parker, D. E., T. P. Legg, and C. K. Folland (1992). A new daily central england temperature series, 1772-1991. International Journal of Climatology 12(4), 317-342.
Quessy, J.-F. (2019). Consistent nonparametric tests for detecting gradual changes in the marginals and the copula of multivariate time series. Statistical Papers 60(3), 717-746.
Raimondo, M. (1998). Minimax estimation of sharp change points. Annals of statistics, 1379-1397.
Ramdas, A. and R. J. Tibshirani (2016). Fast and flexible admm algorithms for trend filtering. Journal of Computational and Graphical Statistics 25(3), 839-858.
Sadhanala, V. and R. J. Tibshirani (2017). Additive models with trend filtering, arXiv preprint 17210:170..05037.
Tewes, J. (2017). Change-point tests and the bootstrap under long-and short-range dependence. Ph. D. thesis, Ruhr- Universiätt Bochum.
Tibshirani, R. J. (2014). Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics 42(1), 285-323.
Truong, C., L. Oudre, and N. Vayatis (2020). Selective review of offline change point detection methods. Signal Processing 167, 107299.
Van den Burg, G. and C. K. I. Williams (2020). An evaluation of change point detection algorithms. arXiv preprint arXiv:2003.06222.
Vogt, M. and H. Dette (2015). Detecting gradual changes in locally stationary processes. The Annals of Statistics 43(2), 713-740.
Wang, Y.-X., Sharpnack, Smola, and R. Tibshirani (2015). Trend filtering on graphs. In Artificial Intelligence and Statistics, pp. 1042-1050. PMLR.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 8.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 8.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All methods included in the experiment are unsupervised and choice of other hyperparameters are specified in Section and the Appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes] See Section 6.
(b) Did you mention the license of the assets? [Yes] See Section 6.
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A] Data publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mkuGwgZD2jQ", "reviewer": "Reviewer_MgSk", "summary": "Paper proposed a kernel-based method to detect/localize graduate changing points in time series data. Paper claims flexibility compared to the existing methods and targeted some issues raised in the literature. Paper provides theoretical analysis and simulations / real data analysis to support the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Paper has some strong points\n- Careful analysis showing statistical guarantee of the methods and the comparison of the existing method is carefully carried out.\n- The proposed method has wide range of the potential applications due to its non-parametric nature\n- Author addressed the positive bias issue and proposed solutions\n\nIn general a good piece of theoretical work that could shed lights on future methodology development. Paper provided interesting angle to tackle the problem and analyse the theoretical properties. \n\nSome points of improvement:\n- Line 56: $[x]$ is usually representing $\\{1,2,\\ldots,x\\}$ instead of the integer part. Use $\\lfloor x \\rfloor$ instead on this.\n- Line 111: sum of Gaussian is a Gaussian. I think you are saying sum of standard Gaussian squares.\n- Thm4.10: we have convergence on the scale of 0 to 1, and this is time compressed, meaning all the time is divided by T. When T increases, is the convergence still holds true? E.g. when there is a sample on each integer time, will the following hold\n$$\n\\rho^* - \\hat{\\rho} = o(1/T)\n$$\nThis will ensure that the localization going close the place of change. At lease you don't want the  $T(\\rho^* - \\hat{\\rho}) \\to \\infty$ happen, which you may be far off eventually while still converging in the 0,1 scale.\n- Even if this is a non-parametric method, the kernel choice is still depending on some structure assumptions. Can we have comparison between kernel choices (e.g. inner product on $\\mathbb{R}^n$ versus general Gaussian kernel) so that we can get some insights on how the kernel choice affect the output?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical piece of work. I don't think this question apply.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "cZrd99WdRQ7", "reviewer": "Reviewer_Rm3m", "summary": "This paper proposes a new kernel-based nonparametric statistic for detecting gradual changes in the offline setting. Theoretical guarantees are provided for the detection power and localization accuracy.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contribution of the kernel-based new detection statistic is incremental and the method is mainly adapted from existing MMD-based methods. As compared with Vogt et al. (2015) where a supreme over a function class needs to be computed, this paper only needs to compute the detection statistic under a chosen kernel function. A natural limitation is that the choice of the kernel function can be very crucial for the good performance of the proposed method. And it would be interesting to provide some numerical studies on how different kernel functions may result in different detection performances.\n\nThe main contribution is theoretical characterizations of the detection power and estimation accuracy of the change-point. However, this paper does not provide explicit results regarding the tradeoff between the false alarm rate and detection/localization accuracy, which can be of more interest for change detection problems. Therefore the theoretical results seem a bit limited.\n\nFor the numerical results and especially the real data examples, the author only provides the detected change-point, which makes it a bit hard to judge the performance. Maybe it would be more convincing if the author could compare with other detection methods.\n\nThis paper mainly focus the offline change detection with only one change-point. It would be interesting to discuss possible extensions to the case with multiple change-points and to the online detection setting.\n\nMinor issues:\nLine 320: the eq(3) referred here is not an estimator used in Vogt et al. (2015).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "QcWJFjA00op", "reviewer": "Reviewer_PzmP", "summary": "This paper proposes methods for change detection and change point identification based on (kernel) nonparametric statistics. The detection problem is solved by deriving the asymptotic distribution of the nonparametric test statistics. For localization, two change point estimators are proposed. The proposed methods are evaluated on a small number of synthetic and real datasets and compared to conventional ones.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have the following comments and suggestions:\n\nThe dependence on the eigenstructure of the kernel operator is clearly described, but from the practical viewpoint, more attention should be paid to kernel selection and kernel bandwidth selection.\n\nThe computational complexity for calculating the proposed statistics should be explicitly stated.\n\nPossible extension to (nearly) online change point detection, and to multiple change-point detection should be mentioned.\n\nLine 256, (i) linear change,\n\"\\mu_1(u) = I(1/3 <= u <= 2/3) ( 3u - 3)\"\nThis should be\n\"\\mu_1(u) = I(1/3 <= u <= 2/3) ( 3u - 1)\"\n\n\n--- After reading the authors' response\nI read the author's reply and it basically resolved my questions. I understand it is not straightforward to extend the method to online/multiple CP detection. My questions are relatively minor or something which should have been clearly stated from the beginning, so I keep my score unchanged after reading the author's reply.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "C25YES-5hTo", "reviewer": "Reviewer_pviK", "summary": "The paper considers the \"gradual change detection problem\" i.e., the problem of identifying whether a time series has \"shifted\" (significantly) in a gradual / long term-ish way.  This is a bit different from the usual changepoint detection problem we are often concerned with in statistics (and to some extent machine learning), where we assume the change is much more abrupt (e.g., we might assume the underlying signal is piecewise constant).\n\nLet the observations $Y_{t,T} := Y_t \\sim P$, $t=1,\\ldots,T$, for some fixed $T > 0$, and unknown $P$; a key component of the paper is that the authors let the $Y_t$, $t=1,\\ldots,T$, take values in an arbitrary metric space.  Then, very roughly speaking, the authors say they are testing:\n$$\nH_0: P = P_0 \\quad \\textrm{vs.} \\quad \\textrm{$H_1:$ there exists some window such that $P = P_0$, and another such that $P \\neq P_0$},\n$$\n\nwhere $P_0$ is a null distribution.  Actually, the authors go further and additionally consider the changepoint localization problem, i.e., the problem of identifying the changepoint itself, call it $\\rho^*$.\n\nThe authors propose (something resembling) a kernelized version of the well-known absolute CUSUM statistic, derive its limit law (giving a Donsker-type theorem), and show that their test is asymptotically powerful.  They also propose two ways to localize $\\rho^*$ (one natural estimator, and another estimator seen to be less biased than the natural one).  They give a decent number of simulations with synthetic data, and two experiments with real-data (which is always nice to see), where they measure power and the $\\ell_1$ error in identifying $\\rho^*$.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper tackles a very interesting problem.  Below, I raise a few medium-sized issues, as well as one larger issue re: related work (that kind of prevents me from fully endorsing the paper, at least for now).  I break down my review below according to the categories suggested by the NeurIPS reviewer guidelines.\n\n**Originality.**  This seems to be a good place to raise the larger issue I mentioned above re: related work.  As the authors acknowledge in the paper, their proposal is very similar to that of Vogt et al. (2015).  However, to me, it also appears to be very similar to that of Harchaoui et al., 2008, i.e., the method called \"KCpA\" by the authors (essentially just without the covariance scaling of KCpA).  Therefore, I am a bit confused as to why KCpA performs so poorly in the experiments of Section 5.  Can the authors explain?  The authors mention that \"for fairness, we use the same kernel for [their two method(s) as well as KCPA]\"; but that actually doesn't seem entirely fair to me, as different methods certainly have different operating characteristics.  At the very least, different bandwidths should probably be used, but I assume this did not happen, either.\n\nOn the technical side of the originality question, it seems to me that the proofs largely combine ideas that can already be found in the literature (which is, of course, completely fine).\n\n**Quality.**  Overall, the paper is reasonably thorough and well put together, which I appreciate.  However, here are a few questions / issues that would be nice to see fixed, in any final version of the paper:\n\n* It seems that if allowing the $Y_t$, $t=1,\\ldots,T$ to live in a metric space is an important part of the overall contribution, then it would be good to have additional experiments along those lines, e.g., with say strings / text data (?).  (I know you did experiments with graphs, and that is definitely a sensible starting point.)\n* You could/should also report/study type 1 error, in your simulations.  That is, of course, an important part of the evaluation of any method.\n* How much does setting $\\rho^* = 1/3$ in Section 5 matter?\n* What if one does not know the value of the upper endpoint of the interval that contains $u$ (i.e., what if the \"1\" is unknown, in the display below line 48)?\n* Section 1: you might want to look into + cite \"trend filtering\" methods here; they are very related.\n* Line 339: maybe a kind of combined method makes sense here, i.e., to get the advantages of both the abrupt and gradual changepoint methods.\n\n**Clarity.**  The paper is well written.\n\n**Significance.**  As I mentioned above, I believe the paper certainly tackles an important (and under-investigated) problem.  It's not totally clear to me (yet) how novel the authors' contributions actually are, though.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors were blunt about the fact that their method is not best in all circumstances (they say their method is best suited to high-dimensional gradual change problems).  That was nice to see.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: As mentioned by the reviewers the paper tackles an exciting problem. The authors are also very knowledgeable on the topic, and the proposal sounds interesting. However, the paper requires a bit more work in order to be accepted at a top conference or journal. Here are a few suggestions for a future submission of the paper:

1. A proper and detailed comparison with the existing work seems to be required. Given that there are strong similarities between this proposal and other proposals such as MMD-Based methods and KCpA. This comparison should not happen in the authors' response and should be an important part of the paper. Also, intuitive explanations on why the authors think their proposal outperforms existing statistics could be a nice addition to the paper. Providing tables that compare different proposals in terms of computational complexity, ease of calculating asymptotic distribution, accuracy, ... can be a useful addition to the paper as well. 

2. Please provide a fair and convincing set of simulations by exploring the choice of the kernel and the impact of the bandwidth of the kernel on both the authors' proposal and KCpA. 

Hope the authors find the reviews helpful. 

Decision: Accept (Poster)