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": "Zrrs64JuqrI", "reviewer": "Reviewer_W1jH", "summary": "This paper analyzes the problem of characterizing a gradual change in the probability measure of an independent-across-time time series $Y_t,$ $t \\in \\{0, 1, \\ldots, T\\}$ over an observed interval $[0, T]$. The authors are interested in:  1) detecting whether or not a change has occurred; 2) Localizing the change within $[0,T]$. The authors seek only some time $\\rho^* \\in [0,T]$ where the change begins to occur. They propose a procedure for detecting the change and localizing it, in addition to providing theoretical results that establish statistical guarantees, and experimental results that show the benefits of their approach. \n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "Novelty: The paper formulates a novel gradual anomaly detection and localization problem that goes beyond the historied quickest change detection problem in which one seeks to detect and localize an abrupt change with probability one, e.g., Lorden 1971, as the number of observations tends to infinity. They characterize the solution to their gradual change problem under the assumptions that the gradual change must be continuous with respect to the standard topology in $[0,T]$ and the weak topology on the space of measures $\\{P_t \\}$. That is, as $t \\rightarrow x$ in $[0,T]$, $P_t$ must approach $P_x$ weakly.  For localization, there is less novelty. The authors take the change-point estimate of (Vogt 2015) and modify it slightly with hyperparameter $c_T$. They then minimize the expected absolute difference of this change-point estimate minus the true change point with respect to the asymptotic ($T \\rightarrow \\infty$) distribution over possible values of $c_T$.\n \nSignificance:  The authors present a new change point detection statistic that is highly versatile and requires few assumptions on the distribution of the time-series in which the change point may occur. Moreover, the proposed statistic can detect a wide variety of changes. This contrasts with existing approaches that seek a specific change (requiring domain knowledge). The authors also prove asymptotic distributions of their statistic, find an optimal localization estimator of the CPD with respect to a heuristic established in (Vogt 2015), and evaluate p-values using the derived asymptotic distribution. \n\nScholarship: The authors do an excellent job at placing their contribution in the context of previous work. Existing approaches for this problem (Vogt 2015) partition the interval of observation into $[0, v] \\cup (v, T]  = [0, T]$ and compare, as a function of $v$, the difference between $E[f(Y_t)]$ for $t \\in [0, v]$ vs $t \\in (v, T]$. This comparison is made for a set of functions $f \\in \\mathcal{F}$ that is pre-specified. The authors rightfully criticize this approach because the set of functions $\\mathcal{F}$ is typically finite, which excludes some classes of changes in distribution. Instead of the statistic of (Vogt 2015), which returns the max-max over partitions $v$ and functions $f$ that yield the largest difference in $E[f(Y_t)]$,  the authors' define a new statistic, \nequation (6), that measures the similarity in measure of the $Y$'s across the partitions, comparing it to the similarity within  the partition. Intuitively, this statistic is 0 if there is no change in [0, T] because the ``within'' and ``across'' estimates are close. This is all clearly exposited in the paper.\n\nCompleteness of theory:  The authors show that the distribution of their statistic under the no-change hypothesis is asymptotically Chi-squared, allowing them to calculate $p-$values required to defined the stopping time of their procedure. They then argue that their approach encapsulates infinite-cardinality function sets $\\mathcal{F}$ of the (Vogt 2015) approach with the appropriate choice of kernel function.\n\nExperiments: The empirical results section is very complete. There are several comparisons to existing methods for both detection and localization of change-points. The proposed algorithm is compared to previous approaches on simulated data involving various types of gradual changes for which the previous approaches were designed and  should achieve a high level of performance in localization. The proposed algorithm is also compared to 3 abrupt change-point detection methods, showing that the proposed algorithm achieves exceptional performance on detection and good performance on localization. Although, as mentioned earlier, it is being compared to localization estimators that are designed to detect a specific type of change.\n\nQuality of writing: The quality of writing is excellent overall. The only suggestion is that the authors should be more specific about which limit is in question when using the word \"asymptotic.\" This was not entirely clear in the body of the paper, and required me to look to the Theory section and appendix.\n\nAdditional comments:\n\nAlthough not stated in the document, the hypothesis testing problem can be stated as a test of hypotheses of the distribution change function $f$: H0: $f$ is constant on $[0, T]$ vs.\nH1: $f$ is continuous with respect to the weak topology, but not constant on $[0, T]$. This would better contrast the proposed problem against Lorden's approach in which $f$ is a Heaviside step function on $[0, \\infty)$ under H1 and constant under H0.  Stating the problem in this way clarify the difference between the standard formulation of the change detection problem and the authors' proposed formulation. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no limitations or negative societal impact implications.", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "VbRP9yQ6qC", "reviewer": "Reviewer_oZvV", "summary": "This paper proposes a nonparametric, kernel-based approach for detecting and localizing gradual changes in time-series data, provides theoretical guarantees on its performance, and validates its efficacy via numerical experiments with both synthetic and real data.", "questions": "", "limitations": "", "rating": 7, "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 think this work makes solid contributions to the problem of detecting and localizing gradual changes. \n* The proposed nonparametric algorithms are flexible and have few tuning parameters, requiring minimal assumption/knowledge on data distributions; the intuitions behind algorithm design are well explained. \n* The presentation of theoretical results seem rigorous to me, with a complete set of technical assumptions and concise statements (as well as intuitive explanations) of the main results (though I did not carefully check the correctness). On the downside, the presented results are mostly asymptotic in nature.\n* The numerical experiments are convincing; in particular, the authors are honest about when the proposed methods work better or worse than other existing algorithms.\n* The comparison with related work is rather exhaustive.  In terms of writing, this paper is well written and easy to follow.\n\nMy only suggestion is to add a quick but formal explanation to Lines 93-94, i.e. why the defined \"within-group similarity\" should be large compared with \"between-group similarity\", where \"similarity\" is defined by kernel. This point might not be immediately clear to readers who are not familiar with change detection or RKHS theory. Such an explanation will also help to explain Remark 3.1, e.g. why dot-product kernel is suggested for location model, but might fail for other model of changes.\n\n--------\nAfter rebuttal:\nThanks for the authors' response. I decide to keep my score.", "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": "2"}, "extra_text": {}}, {"review_id": "UJ65gxA4YKM", "reviewer": "Reviewer_ZPrG", "summary": "The paper proposes a method for the detection and localization of a gradual change in the distribution of sequence data. In contrast to existing work (which mostly focuses on abrupt changes in the distribution), this paper considers a smooth, gradual change. The approach is non-parametric and does not make major assumptions on the data/change model. The paper introduces a kernel-based statistic to detect the change that captures similarities between the observations before and after the change has occurred. \n", "questions": "", "limitations": "", "rating": 7, "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": "+ This is a solid paper and is well written. It provides a good balance between theory and experimentation. \n+ The problem statement dispenses with model assumptions made in prior work such as particular parametric models, changes in pre-specified moments of a distribution, monotonicity of the change, and mixture models. \n+ The max-gap estimator of the change point is promising and has good empirical performance with finite samples.\n+ The paper gives theoretical asymptotic guarantees.  \n- If I understand correctly, the approach is a special case of [Vogt et al., 2015]. In particular, by setting the function f to be the feature map associated with the kernel of a Reproducing Kernel Hilbert Space, we get the proposed statistic by invoking the kernel trick. So, the novelty beyond [Vogt et al. 2015] is somewhat limited.\n- The paper assumes independent observations, which may be unrealistic for practical applications with a gradual change. The paper claims that their method can be adapted to the setting with correlated observations, but obviously this is not considered in this work. \n- The assumptions in the theoretical analysis of Section 4 are a little obscure. The paper should do a better job motivating these assumptions. \n\n\n", "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": "4"}, "extra_text": {}}, {"review_id": "DoaOmftbWv9", "reviewer": "Reviewer_5aeA", "summary": "This paper considers the problem of detecting gradual change-points. This setting is more general than the abrupt change-point detection setting, and is often encountered in applied situations. The authors propose a kernel-based statistics to estimate a single change, and prove the asymptotic consistency of their estimator. The numerical experiment are convincing.", "questions": "", "limitations": "", "rating": 7, "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": "This work builds on the setting and results of [1] and propose a (conceptually) similar estimator. However, the authors make an original contribution by resorting to a kernel to improve the estimator of [1]. Thanks to this, the change-point detection procedure can now be used without knowing a priori the class of transformations that best measure the change. In addition, the estimator is shown to be asymptotically consistent, making the complete procedure theoretically sound. \n\n\nOverall, the paper is clear and well-written. Two minor improvements could be made in my opinion:\n- Summarize somewhere (in a pseudo-code if space allows it, or in a few sentences) all the steps needed to estimate a change and compute the associated p-value. All parameters and equations are spread out within the paper, making it difficult for a motivated reader to implement the method. Also, the computational complexity of the procedure is an interesting piece of information to provide for readers.\n- There lacks references to the Maximum Mean Discrepancy (MMD) which is a kernel-based statistical test and is also used to do change-point detection. At first sight, the estimator $\\hat{\\Kappa}_T$ (Equation 6) seems very close to the MMD between the group before $[Tv]$ and the group after $[Tv]$.\n\n[1] Vogt, M., & Dette, H. (2015). Detecting gradual changes in locally stationary processes. Annals of Statistics, 43(2), 713–740.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no negative societal impact in my opinion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8IHML13hiRV", "reviewer": "Reviewer_hFCk", "summary": "The manuscript proposed a kernel-based nonparametric method to detect and localize gradual change points in time-ordered observations. Theoretical properties are studied and the proposed method is assessed by several simulation examples and two real data applications.", "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": "Originality and Significance: The manuscript follows the gradual changes detection framework introduced in Vogt and Dette (2015). The authors proposed to change the sets of moment functions used in Vogt and Dette (2015) to a kernel function. In my regard, this manuscript provides marginal contributions to existing work.\n\nQuality and Clarity: The presentation of the paper needs to be improved. (1) The claim that the proposed new statistic is applicable to any data type and any generating process may be exaggerated. The authors assume the observed sequence is independent, local stationery, and of gradual changes. These assumptions certainly rule out some data-generating processes from the discussion. (2) The authors claimed they do not put any assumptions on the data type of distribution of Y_{t,T}. However, it is not clear to me if the proposed method is appropriate if Y_{t,T} is categorical as the distances among the levels may not be well defined.  (3) The max-gap estimator proposed in the paper is also a bit unclear to me. If there are multiple change points, will the monotonic pattern shown in Figure 3 always hold? (4) The presentation of Table 1 needs to be improved. The simulations are summarized over only 20 replications. (5) Both real datasets studied has clear serial dependence which may not be the best showcase examples as the theory is developed under independence.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Besides the major comments listed in the Main Review section, I list some minor comments as follows:\n\n(1) Several citation format errors. For example \"Vogt et al. (2012)\" should be \"Vogt  (2012)\", and \"Vogt et al. (2015)\" should be \"Vogt and Dette (2015)\".\n\n(2) The definition of the alternative hypothesis on page 2 (between lines 48 and 49) is a bit confusing. As the authors allow u to approach \\rho^* from above and \\epsilon to approach 0 from above.  I wonder if it is feasible to detect the alternative in an extreme case when the change is allowed to happen at any slow rate.\n\n(3) In line 96 of page 4, u can reach the left boundary 0 where equation (6) is not well defined. \n\n(4) In line 87 of page 3, what does the term \"non-Euclidean data\" mean here? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors are proposing a general method for detecting and localizing gradual changes without a specific data model, type or prior knowledge on the features. Despite these relaxations, they provide a new method with guarantees, which they empirically demonstrate. Overall, this is great scholarly work, from its writing to empirical demonstrations and the work should be accepted. 
Decision: Accept (Poster)