Clustering piecewise stationary processes

Azadeh Khaleghi; Daniil Ryabko

arxiv: 1906.10921 · v1 · pith:UVQRJPPTnew · submitted 2019-06-26 · 📊 stat.ML · cs.LG· math.ST· stat.TH

Clustering piecewise stationary processes

Azadeh Khaleghi , Daniil Ryabko This is my paper

Pith reviewed 2026-05-25 15:28 UTC · model grok-4.3

classification 📊 stat.ML cs.LGmath.STstat.TH

keywords time series clusteringpiecewise stationary processesergodic processesconsistencynonparametric statistics

0 comments

The pith

Algorithms exist that consistently cluster time series from piecewise stationary ergodic processes by matching their sets of stationary distributions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses clustering of time-series samples where each sample is generated by a piecewise stationary ergodic process. It introduces a consistency requirement that places samples in the same cluster precisely when their generating processes share identical sets of stationary distributions. Simple and efficient algorithms are shown to achieve this consistency relying solely on the piecewise stationarity property. This relaxes the stationarity assumption common in prior non-parametric time-series work while handling arbitrary dependence structures.

Core claim

The central discovery is that consistent clustering of piecewise stationary processes is possible with computationally efficient algorithms that require no assumptions beyond piecewise stationarity and ergodicity, where consistency is defined by equality of the sets of stationary distributions across the piecewise segments.

What carries the argument

The notion of consistency defined by whether the piecewise stationary distributions share the same set of stationary distributions, which allows the algorithms to ignore the change points and focus on the stationary components.

Load-bearing premise

The samples come from piecewise stationary ergodic processes and that correctly identifying shared stationary distribution sets is the appropriate goal for clustering.

What would settle it

A dataset of time series from two piecewise stationary processes that have different sets of stationary distributions but where the proposed algorithms group them together.

read the original abstract

The problem of time-series clustering is considered in the case where each data-point is a sample generated by a piecewise stationary ergodic process. Stationary processes are perhaps the most general class of processes considered in non-parametric statistics and allow for arbitrary long-range dependence between variables. Piecewise stationary processes studied here for the first time in the context of clustering, relax the last remaining assumption in this model: stationarity. A natural formulation is proposed for this problem and a notion of consistency is introduced which requires the samples to be placed in the same cluster if and only if the piecewise stationary distributions that generate them have the same set of stationary distributions. Simple, computationally efficient algorithms are proposed and are shown to be consistent without any additional assumptions beyond piecewise stationarity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper is the first to frame clustering for piecewise stationary ergodic processes with a consistency notion based on matching sets of stationary distributions, but the no-extra-assumptions claim is likely too broad.

read the letter

The main thing to know is that this work extends non-parametric clustering to piecewise stationary processes for the first time and defines consistency as putting samples together exactly when their processes share the same collection of stationary distributions. They also give simple algorithms and claim these are consistent under just piecewise stationarity and ergodicity, with no further conditions stated in the abstract. That formulation is a clean way to handle regime changes without forcing a single stationary law on the whole series. The computational efficiency claim is useful if it holds up. The soft spot is the consistency guarantee. Recovering the right clusters requires reliable change-point detection plus consistent estimation on each piece. Standard results show this fails when stationary segments are too short relative to sample size or when the regimes are too close in total variation, both of which are allowed under the stated assumptions. The abstract gives no indication that such restrictions are imposed or circumvented, so the result either applies only to a narrower subclass or the proofs contain unstated steps. Without the full proofs or any experiments, it is hard to tell which. The citation pattern is fine for a new direction. This paper is aimed at researchers working on time-series clustering and non-parametric sequential methods. A reader looking for extensions beyond strict stationarity would find the problem setup and target useful. It deserves a serious referee because the modeling step is well-motivated and the consistency definition is precise, even though the central claim needs checking. I would send it out for peer review.

Referee Report

1 major / 1 minor

Summary. The paper formulates the clustering problem for time series generated by piecewise stationary ergodic processes, introduces a consistency notion (samples clustered together iff the processes share identical sets of stationary distributions), and proposes simple computationally efficient algorithms claimed to achieve this consistency under no assumptions beyond piecewise stationarity and ergodicity.

Significance. If the consistency holds under only the stated assumptions, the result would meaningfully extend nonparametric time-series clustering by dropping stationarity while retaining ergodicity (hence allowing long-range dependence). The computational simplicity of the algorithms is a positive feature.

major comments (1)

[Abstract / main consistency theorem] Abstract (and the consistency theorem): the claim of consistency 'without any additional assumptions beyond piecewise stationarity' is load-bearing for the central contribution. Standard change-point results show that consistent segmentation (necessary to recover the set of stationary distributions from a single path) fails when stationary segments have lengths o(n) or when distinct regimes have arbitrarily small total-variation distance; both regimes are permitted by the stated assumptions. The proof must either add the missing conditions or exhibit an argument that evades them.

minor comments (1)

[Section 2 (problem formulation)] The precise definition of 'same set of stationary distributions' should be stated formally early in the paper, including how ties or measure-zero differences are handled.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a key point regarding the strength of our consistency claim. We address the concern directly below.

read point-by-point responses

Referee: [Abstract / main consistency theorem] Abstract (and the consistency theorem): the claim of consistency 'without any additional assumptions beyond piecewise stationarity' is load-bearing for the central contribution. Standard change-point results show that consistent segmentation (necessary to recover the set of stationary distributions from a single path) fails when stationary segments have lengths o(n) or when distinct regimes have arbitrarily small total-variation distance; both regimes are permitted by the stated assumptions. The proof must either add the missing conditions or exhibit an argument that evades them.

Authors: The referee correctly notes that standard change-point detection requires conditions on minimum segment length and regime separation for consistency, and that our stated assumptions permit regimes where these fail. Our original proof sketch attempted to evade explicit segmentation by working directly with a clustering criterion based on pairwise distances between empirical occupation measures of entire samples; however, upon closer inspection we agree that recovering the exact set of stationary distributions (as required by the consistency definition) implicitly requires being able to distinguish the regimes, which cannot be guaranteed without further conditions. We will therefore revise the manuscript by (i) adding explicit assumptions that each stationary segment has length at least c n for some c>0 and that distinct regimes are separated by a fixed total-variation distance delta>0, (ii) updating the statement of the main consistency theorem and the abstract accordingly, and (iii) adding a brief discussion of why these conditions are necessary and how they relate to the literature on change-point detection. These changes constitute a major revision but preserve the core algorithmic contribution and the nonparametric flavor of the result. revision: yes

Circularity Check

0 steps flagged

New problem formulation and consistency definition; derivation self-contained

full rationale

The paper introduces a novel clustering task for piecewise stationary ergodic processes and defines consistency directly in terms of matching sets of stationary distributions. No quoted steps reduce a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or ansatz smuggled from prior work. The central consistency claim is presented as a theorem under the stated model class; any self-citations (if present) are not shown to be load-bearing for the main result. This matches the default expectation of no significant circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the ledger is inferred from stated assumptions; no free parameters or invented entities are mentioned.

axioms (2)

domain assumption The generating processes are ergodic.
Explicitly stated in the abstract as the class of processes considered.
domain assumption Piecewise stationarity is sufficient to define a meaningful clustering target via the set of stationary distributions.
The consistency notion rests on this modeling choice.

pith-pipeline@v0.9.0 · 5650 in / 1199 out tokens · 24413 ms · 2026-05-25T15:28:33.219942+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Balcan, A

M. Balcan, A. Blum, and S. V empala. A discriminative fram ework for clustering via similarity func- tions. In Proceedings of the 40th annual ACM symposium on Theory of com puting, pages 671–680. ACM, 2008

work page 2008
[2]

R. Gray. Probability, Random Processes, and Ergodic Properties. Springer V erlag, 1988

work page 1988
[3]

Gyorgy, T

A. Gyorgy, T. Linder, and G. Lugosi. Efﬁcient tracking of large classes of experts. IEEE Transactions on Information Theory , 58(11):6709–6725, 2012

work page 2012
[4]

Katsavounidis, C.-C

I. Katsavounidis, C.-C. J. Kuo, and Z. Zhang. A new initia lization technique for generalized Lloyd iteration. IEEE Signal Processing Letters, 1:144–146, 1994

work page 1994
[5]

Khaleghi and D

A. Khaleghi and D. Ryabko. Locating changes in highly dep endent data with unknown number of change points. In Proceedings of the 25th International Conference on Neural Information Processing Systems, pages 3095–3103, 2012

work page 2012
[6]

Khaleghi and D

A. Khaleghi and D. Ryabko. Asymptotically consistent es timation of the number of change points in highly dependent time series. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 539–547, 22–24 Jun 2014

work page 2014
[7]

Khaleghi and D

A. Khaleghi and D. Ryabko. Nonparametric multiple chang e point estimation in highly dependent time series. Theoretical Computer Science, 620:119–133, 2016

work page 2016
[8]

Khaleghi, D

A. Khaleghi, D. Ryabko, J. Mary, and P . Preux. Consistent algorithms for clustering time series. The Journal of Machine Learning Research , 17(1):94–125, 2016

work page 2016
[9]

D. Ryabko. Clustering processes. In Proceedings of the 27th International Conference on Machin e Learning, pages 919–926, 2010

work page 2010
[10]

D. Ryabko. Discrimination between B-processes is impo ssible. Journal of Theoretical Probability , 23(2):565–575, 2010

work page 2010
[11]

D. Ryabko. Asymptotic Nonparametric Statistical Analysis of Station ary Time Series. Springer, 2019

work page 2019
[12]

P . Shields. The Ergodic Theory of Discrete Sample Paths . AMS Bookstore, 1996

work page 1996
[13]

F. M. Willems. Coding for a binary independent piecewis e-identically-distributed source. IEEE Trans- actions on Information Theory , 42(6):2210–2217, 1996. 12

work page 1996

[1] [1]

Balcan, A

M. Balcan, A. Blum, and S. V empala. A discriminative fram ework for clustering via similarity func- tions. In Proceedings of the 40th annual ACM symposium on Theory of com puting, pages 671–680. ACM, 2008

work page 2008

[2] [2]

R. Gray. Probability, Random Processes, and Ergodic Properties. Springer V erlag, 1988

work page 1988

[3] [3]

Gyorgy, T

A. Gyorgy, T. Linder, and G. Lugosi. Efﬁcient tracking of large classes of experts. IEEE Transactions on Information Theory , 58(11):6709–6725, 2012

work page 2012

[4] [4]

Katsavounidis, C.-C

I. Katsavounidis, C.-C. J. Kuo, and Z. Zhang. A new initia lization technique for generalized Lloyd iteration. IEEE Signal Processing Letters, 1:144–146, 1994

work page 1994

[5] [5]

Khaleghi and D

A. Khaleghi and D. Ryabko. Locating changes in highly dep endent data with unknown number of change points. In Proceedings of the 25th International Conference on Neural Information Processing Systems, pages 3095–3103, 2012

work page 2012

[6] [6]

Khaleghi and D

A. Khaleghi and D. Ryabko. Asymptotically consistent es timation of the number of change points in highly dependent time series. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 539–547, 22–24 Jun 2014

work page 2014

[7] [7]

Khaleghi and D

A. Khaleghi and D. Ryabko. Nonparametric multiple chang e point estimation in highly dependent time series. Theoretical Computer Science, 620:119–133, 2016

work page 2016

[8] [8]

Khaleghi, D

A. Khaleghi, D. Ryabko, J. Mary, and P . Preux. Consistent algorithms for clustering time series. The Journal of Machine Learning Research , 17(1):94–125, 2016

work page 2016

[9] [9]

D. Ryabko. Clustering processes. In Proceedings of the 27th International Conference on Machin e Learning, pages 919–926, 2010

work page 2010

[10] [10]

D. Ryabko. Discrimination between B-processes is impo ssible. Journal of Theoretical Probability , 23(2):565–575, 2010

work page 2010

[11] [11]

D. Ryabko. Asymptotic Nonparametric Statistical Analysis of Station ary Time Series. Springer, 2019

work page 2019

[12] [12]

P . Shields. The Ergodic Theory of Discrete Sample Paths . AMS Bookstore, 1996

work page 1996

[13] [13]

F. M. Willems. Coding for a binary independent piecewis e-identically-distributed source. IEEE Trans- actions on Information Theory , 42(6):2210–2217, 1996. 12

work page 1996