REVIEW 2 minor 1 cited by
Online change point detection under heavy-tailedness and contamination
T0 review · 0 major / 2 minor · reviewed 2026-06-27 · grok-4.3
Pith's one-line read Univariate online robust mean change point detection partitions detection delay into four regimes determined by change location, signal size and contamination level, with procedures achieving near-optimal performance and matching lower boun
desk verdict The paper gives the first analysis of online change point detection that simultaneously handles dynamic Huber contamination and heavy-tailed inliers, with a four-regime partition and matching lower bounds for the univariate case. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Partitioning of the univariate parameter space into four regimes (defined by true change location, signal size and contamination level) that determines the achievable detection delay, together with matching upper and lower bounds.
What would settle it
An experiment that records detection delays for a range of change locations, signal sizes and contamination fractions and finds that the observed delays fall outside the four predicted regimes or exceed the derived lower bounds by more than poly-logarithmic factors would falsify the characterization.
Extended reading notes
Core claim
We study an online version of the robust mean change point detection problem under a dynamic Huber contamination model with arbitrary contamination distribution and inlier distribution possessing exponentially- or polynomially-decaying tails. This robustness framework is systematically studied for the first time in the change point literature. For univariate data, we characterise the detection delay by partitioning the parameter space into four regimes, in terms of the true change location, signal size and contamination level. Efficient detection procedures are accompanied by matching lower bounds, up to poly-logarithmic factors. For the multivariate setting, we devise an efficient robust me
Load-bearing premise
The clean observations come from a distribution whose tails decay at least polynomially (or exponentially) while contamination follows the dynamic Huber model with arbitrary contaminating distribution.
Editorial extensions
If this is right
- Detection procedures attain the information-theoretic delay limits in each of the four regimes.
- The same robust testing subroutine extends the univariate guarantees to the multivariate setting.
- Numerical simulations confirm that the theoretical delay bounds are attained in practice.
- The analysis covers both polynomially and exponentially tailed inlier distributions under time-varying contamination.
Reading between the lines
- The four-regime partition may supply a template for deriving sharp delay bounds in other online problems such as covariance or quantile shifts.
- An adaptive algorithm could estimate the current regime on the fly and switch between the four specialized detectors.
- The robust mean-testing subroutine could be reused as a building block for robust sequential hypothesis testing beyond change-point settings.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online robust mean change point detection under a dynamic Huber contamination model with arbitrary contamination and inlier distributions having exponentially or polynomially decaying tails. For univariate data, detection delay is characterized via a partition of the parameter space into four regimes depending on change location, signal size, and contamination level; efficient procedures are given with matching lower bounds up to poly-log factors. For multivariate data, a robust mean testing procedure is developed (handling both Huber contamination and heavy tails) and applied to the online change point problem. Numerical experiments support the theory.
Significance. This appears to be the first systematic study of this robustness framework in the change point literature. The four-regime partition with matching upper and lower bounds (up to poly-log factors) would provide sharp, non-asymptotic insight if the derivations hold. The multivariate robust mean testing analysis is novel in jointly treating contamination and heavy tails and is of independent interest. Reproducible experiments and explicit regime characterizations are strengths.
minor comments (2)
- The abstract states that the parameter space is partitioned into four regimes but does not name or briefly describe them; adding one sentence would improve readability for readers deciding whether to read further.
- Notation for the dynamic Huber model (contamination level, inlier tail parameters) should be introduced with a short display equation or table in the introduction or model section to avoid later ambiguity.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript, accurate summary of our contributions, and recommendation for minor revision. We appreciate the recognition of the novelty in systematically studying this robustness framework for change point detection.
Circularity Check
No significant circularity
full rationale
The paper's central claims involve partitioning the parameter space into four regimes to characterize detection delay for univariate robust mean change point detection, deriving efficient procedures, and establishing matching lower bounds (up to poly-log factors) under Huber contamination and heavy-tailed inlier assumptions. The multivariate extension uses a robust mean testing procedure. No quoted equations, self-citations, or derivations in the provided abstract reduce any result to a fitted input, self-definition, or prior author work by construction. The analysis appears self-contained with independent theoretical content (upper/lower bounds derived from the model assumptions), consistent with standard minimax analysis in statistics. No load-bearing steps exhibit the enumerated circularity patterns.
Assumptions & free parameters
Cite this review
Pith. "Pith review of Online change point detection under heavy-tailedness and contamination." pith.science (2026). https://pith.science/paper/56M7BNQV
@misc{pith2026260609737,
author = {Pith},
title = {Pith review of: Online change point detection under heavy-tailedness and contamination},
year = {2026},
howpublished = {\url{https://pith.science/paper/56M7BNQV}},
note = {Machine review of arXiv:2606.09737}
}
read the original abstract
We study an online version of the robust mean change point detection problem under a dynamic Huber contamination model with arbitrary contamination distribution and inlier distribution possessing exponentially- or polynomially-decaying tails. This robustness framework is systematically studied for the first time in the change point literature. For univariate data, we characterise the detection delay by partitioning the parameter space into four regimes, in terms of the true change location, signal size and contamination level. Efficient detection procedures are accompanied by matching lower bounds, up to poly-logarithmic factors. For the multivariate setting, we devise an efficient robust mean testing procedure and apply this to the robust online change point problem. The theoretical analysis of the robust mean testing procedure is the first in dealing with both Huber contamination and heavy-tailedness, and is thus of independent interest. Extensive numerical experiments are conducted to support our theoretical findings.
Figures
Figures from the paper (3 more)
Forward citations
Cited by 1 Pith paper
-
Conformal Changepoint Localization and Root Cause Analysis with Corrupted Observations
Weighted conformal changepoint localization (W-CONCH) and root-cause analysis (W-CROC) downweight likely-corrupted observations via classifier uncertainty, preserving coverage and shrinking confidence sets.
Reference graph
Works this paper leans on
-
[1]
Aue, A., H¨ ormann, S., Horv´ ath, L., and Reimherr, M. (2009). Break detection in the covariance structure of multivariate time series models.The Annals of Statistics, 37(6B):4046–4087. Avanesov, V. and Buzun, N. (2018). Change-point detection in high-dimensional covariance structure. Electronic Journal of Statistics, 12(2):3254–3294. Balakrishnan, S., D...
2009
-
[2]
The group fused Lasso for multiple change-point detection
Bleakley, K. and Vert, J.-P. (2011). The group fused lasso for multiple change-point detection.arXiv preprint arXiv:1106.4199. Bousquet, O., Boucheron, S., and Lugosi, G. (2004).Introduction to Statistical Learning Theory, pages 169–207. Springer Berlin Heidelberg, Berlin, Heidelberg. Canonne, C., Hopkins, S. B., Li, J., Liu, A., and Narayanan, S. (2023)....
work page Pith review arXiv 2011
-
[3]
Neural network-based CUSUM for online change-point detection.arXiv preprint arXiv:2210.17312, 2022
Cho, H. and Owens, D. (2024). High-dimensional data segmentation in regression settings permitting temporal dependence and non-gaussianity.Electronic Journal of Statistics, 18(1):2620—-2664. Chu, C.-S. J., Stinchcombe, M., and White, H. (1996). Monitoring structural change.Econometrica, 64(5):1045–1065. Comminges, L., Collier, O., Ndaoud, M., and Tsybakov...
-
[4]
Curran Associates, Inc. Hill, B. M. (1975). A simple general approach to inference about the tail of a distribution.The Annals of Statistics, 3(5):1163–1174. Hopkins, S., Li, J., and Zhang, F. (2020). Robust and heavy-tailed mean estimation made simple, via regret minimization. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors,...
-
[5]
Lerasle, M. and Oliveira, R. I. (2011). Robust empirical mean estimators.arXiv preprint arXiv:1112.3914. Li, L. and Li, J. (2023). Online change-point detection in high-dimensional covariance structure with application to dynamic networks.J. Mach. Learn. Res., 24(1). Li, M., Chen, Y., Wang, T., and Yu, Y. (2026). Robust mean change point testing in high-d...
-
[6]
Maidstone, R., Hocking, T., Rigaill, G., and Fearnhead, P. (2017). On optimal multiple changepoint algorithms for large data.Statistics and Computing, 27(2):519–533. Mei, Y. (2006). Sequential change-point detection when unknown parameters are present in the pre- change distribution.The Annals of Statistics, 34(1):92–122. Mitzenmacher, M. and Upfal, E. (2...
-
[7]
Proof.To begin, note first that for anyf∈ S(∆, κ),f 0 ∈ S0,T∈ T(α) from (2), we have Pf(ˆt >∆ +n) =P f(ˆt >∆ +n) +P f0(ˆt≤∆ +n)−P f0(ˆt≤∆ +n)
Proposition S2(Moen, 2025, Proposition 8).For anyn,∆∈N,σ >0,α∈(0,1)andω∈(0,1−α), there exist a constantc >0depending only onωsuch that ifκ 2∆≤cσ 2, we have inf ˆt∈T(α) sup P∈Θ(∆,κ,N σ) PP ˆt−∆> n ≥1−α−ω. Proof.To begin, note first that for anyf∈ S(∆, κ),f 0 ∈ S0,T∈ T(α) from (2), we have Pf(ˆt >∆ +n) =P f(ˆt >∆ +n) +P f0(ˆt≤∆ +n)−P f0(ˆt≤∆ +n). Since ˆt∈ ...
2025
-
[8]
39 Now, letf (1) i =uκ1 {i≤∆} andf (2) i =mκ1 {i≤∆}, wherem, u i.i.d.∼Unif({−1,1})
Define the prior distributionνto be the distribution off∈ S(∆, κ) generated according to the following process.f i =uκ1 {i≤∆} whereu i.i.d.∼Unif({−1,1}). 39 Now, letf (1) i =uκ1 {i≤∆} andf (2) i =mκ1 {i≤∆}, wherem, u i.i.d.∼Unif({−1,1}). Thus we have σ−2X i∈[l] f (1) i f (2) i = ∆κ2σ−2mu≤cmu. Thus, for any value ofκ, it holds that E(f(1),f(2))∼ν⊗ν exp ...
2023
Show all 24 references
-
[9]
Combining the results above, we have sup φ≥1 Pφ (φ < T < φ+⌈d⌉)≤α 1/4. Step 3: We now have for any change point time ∆, E∆[(T−∆) +]≥ 3 8 log(1/α) log((1−ε)/ε) P∆ T−∆≥ 3 8 log(1/α) log((1−ε)/ε) ≥ 3 8 log(1/α) log((1−ε)/ε) [P∆(T >∆)−P ∆ (∆< T <∆ +⌈d⌉)] ≥ 3 8 log(1/α) log((1−ε)/ε...
2021
-
[10]
where the third inequality follows from (S22) and fourth inequality follows from (S17)
≤P(Y d4,∆+d4 < χ d4,∆+d4) =P(|median(X 1:d4)−median(X (∆+1):(∆+d4))|<2c d4,∆+d4) ≤P(κ− |median(X 1:d4)−f 1| − |median(X(∆+1):(∆+d4))−f ∆+1|<2c d4,∆+d4) =P(|median(X1:d4)−f 1|+|median(X (∆+1):(∆+d4))−f ∆+1|> κ−2c d4,∆+d4) ≤P(|median(X1:d4)−f 1|+|median(X (∆+1):(∆+d4))−f ∆+1|>2c...
2021
-
[11]
For our proofs below, we will assume our variablesε, p, n, δsatisfy u≤0.08
implies that, with probability at least 1−δ, |B| ≤un,whereu=q+ r 2qlog(1/δ) n + 2 log(1/δ) 3n .(S36) Denote eventA={|B| ≤un}. For our proofs below, we will assume our variablesε, p, n, δsatisfy u≤0.08. Choice of parameters We next describe the choices ofRandγ, together with an...
2023
-
[12]
Then, fort= 1 until termination, we proceed as follows
w(t+1) i ← 1− τi maxj τj w(t) i t←t+ 1 end while Returnw (t) Algorithm S1 begins by initialising the weights asw (1) =1. Then, fort= 1 until termination, we proceed as follows. For anyw∈Γ n, letD(w) =p·diag(w). Letλdenote the top singular value of Gram(w,Y)−D(w), and letvbe it...
2023
-
[13]
Remark S1.Given eventA, defined in(S36), the number of iterationsNbeing at most6unensures ∥1B −w (N) B ∥1 ≤un, which implies∥1 G −w (N) G ∥1 ≤5unusing(S40)
Then, with probability at least1−δ, Algorithm S1 terminates inN≤6uniterations, each takingO(pn 2)time, and outputs w(N) ∈Λ n such that for allM ⊂ Ywith|M| ≤un, Sum(w(N) ,M) 2 = w(N) M 1 p±O(un R f). Remark S1.Given eventA, defined in(S36), the number of iterationsNbeing at mos...
2023
-
[14]
Indeed, suppose not, and let vG denote the restriction ofvonto the coordinates inG, and letv B denote the restriction ofvonto the coordinates inB
We claim that this implies that 5 P i∈B v2 i >P i∈G v2 i . Indeed, suppose not, and let vG denote the restriction ofvonto the coordinates inG, and letv B denote the restriction ofvonto the coordinates inB. This means that v⊤ Gram(w(t))−D(w) v = v⊤ G Gram(w(t),G)−D(w (t) G ) vG...
2023
-
[15]
The f-Orlicz norm of a real-valued random variableXis ∥X∥ f = inf{t >0 :Ef(|X|/t)≤1}. Definition S2(Sub-Weibull random variables).A random variableXis sub-Weibull with parameter θ >0, denoted sub-Weibull(θ), if ∥X∥ ψθ <∞, with the functionψ θ defined byψ θ(x) = exp(xθ)−1forx≥0...
2020
-
[16]
Then, ∥XY∥ ψθ/2 =∥X∥ ψθ ∥Y∥ ψθ
Lemma S23(Zhang and Wei, 2022, Proposition 2).LetX,Ybe random variables such that max(∥X∥ ψθ ,∥Y∥ ψθ)<∞for someθ∈(0,∞). Then, ∥XY∥ ψθ/2 =∥X∥ ψθ ∥Y∥ ψθ . Lemma S24(Zhang and Wei, 2022, Corollary 4).LetXbe a random variable such that∥X∥ θ <∞ for someθ∈(0,∞). Then X2 ψθ/2 =∥X∥ 2 ...
2022
-
[17]
A slightly-modified version of their approach is described in Algorithm S5
enables robust estimation of the inlier mean under the dynamic Huber contamination model (1), even whenFis heavy-tailed. A slightly-modified version of their approach is described in Algorithm S5. Algorithm S5 is similar to that of trimmed means (Lugosi and Mendelson, 2021). B...
2021
-
[18]
Li and Yu (2021) has generalised the proof to study the dynamic Huber contamination model setting stated in Definition 1 under the finite variance assumption ofF
The estimation error of RUME is of the order O(σ √ ε′). Li and Yu (2021) has generalised the proof to study the dynamic Huber contamination model setting stated in Definition 1 under the finite variance assumption ofF. Here, we further generalise the proof forF∈ G θ,M andF∈ P ...
2021
-
[19]
Vershynin, 2026, Corollary 1.6.3)
=P(Z i ∈I ∗|Zi ∼F 0)P(Zi ∼F 0)≥(1−ε ′)(1−ε)≥1−2ε ′, where the first inequality follows from Chebyshev’s inequality (e.g. Vershynin, 2026, Corollary 1.6.3). Now letX i =1{Z i ∼F 0 andZ i ∈I ∗}andF h 0 (I ∗) = Ph i=1 Xi/h. Note thatX i is a Bernoulli random variable with success...
2026
-
[20]
To get the claimed bound, we need to studyF 0(ˆI) andF h 0 (ˆI) = |ˆhF0 |P Zi∈Z1 1 Zi∼F0
E h Z|Z∈ ˆI i F0(ˆI) =F 0(ˆI c) E h Z|Z̸∈ ˆI i , 87 we have T2b ≤ϕ F0(ˆI c)1−1/v F0(ˆI) .(S81) Combining (S79), (S80), and (S81), with probability at least 1−3δ, we have |RUME| ≤12.4ϕε ′1−1/v h |ˆIF0| + ϕv F0(ˆI) !1/vs 2 log(1/δ) |ˆIF0| + ϕv ε′ 1/v 4 log(1/δ) 3|ˆIF0| +ϕ F0(ˆI ...
2004
-
[21]
Theorem 8.3.9 in Vershynin (2026))
2 by the Sauer-Shelah Lemma (e.g. Theorem 8.3.9 in Vershynin (2026)). Substituting the upper bound onS F(2h) andF h 0 ( ˆI c) into equation (S84), we get with probability at least 1−2δ F0(ˆI c)≤8ε ′ + 2 √ 8ε′ r 2 log(2h+
2026
-
[22]
Letα >0,δ t = 8α/(3t 3 −3t)andε ′ s,t = max ε, 1 s log(1/δt) for allt∈Nandt≥2. If we set the following detection thresholds for the RUME estimator ht = ⌈20 log(1/δt)⌉ifε <0.1, 2 0.5− √ 2ε(1−2ε) log(1/δt) if0.1≤ε <0.25, then∀t≥2∀s∈[h t,⌊t/2⌋], we haveδ t ≤min(1/s,1/4)and ...
2017
-
[23]
−Cθ R2 −p M 2 θ/2# + 2 exp −Cθ (R2 −p) 2 pM 4 . 97 Therefore, using (S95), we have ∥M(G)−nI∥ op ≤ p 2nplog(2p/δ) + 4R2 3 log(2p/δ) + √ 2nϕ2 exp
¯Xi ¯X ⊤ i ] =P(d i = 0)E Xi∼F [1( ¯Xi 2 ≤R) ¯Xi ¯X ⊤ i ] =P(d i = 0)P Xi∼F ( ¯Xi 2 ≤R)E Xi∼F [ ¯Xi ¯X ⊤ i | ¯Xi 2 ≤R] = (1−ε)(1−γ)Σ, we can apply matrix Bernstein inequality (Theorem S41) to bound the first term on the RHS of (S95). With probability 1−δ, we have nX i=1 ζi ¯Xi...
2013
-
[24]
Let Z= nX ℓ=1 aℓYℓ 2 ,EZ 2 =nE∥Y∥ 2 2, and σ2 = sup ∥x∥2≤1 E|⟨x,Y⟩| 2 = E[YY⊤] op
Assume∥Y∥ 2 ≤Rfor someK >0. Let Z= nX ℓ=1 aℓYℓ 2 ,EZ 2 =nE∥Y∥ 2 2, and σ2 = sup ∥x∥2≤1 E|⟨x,Y⟩| 2 = E[YY⊤] op . Then, fort >0, P(Z≥ √ EZ2 +t)≤exp − t2/2 nσ2 + 2R √ EZ2 +tR/3 ! . Lemma S41(Matrix Bernstein inequality, Tropp, 2012, Theorem 1.4).Consider a finite sequence {Mk}n k...
2012
Reviewed June 27, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.