StatScale ECR Event 2022 Titles and Abstracts
Gaurav Agarwal (Lancaster University)
Title: Changepoint modeling in spatio-temporal processes with application to Ireland wind data
Abstract: Spatio-temporal modeling has become increasingly important for studying climate change and environmental applications. Changepoints have been extensively studied for time series data, but there is limited literature on detecting changes in spatial data over time. This paper develops a likelihood-based methodology for the simultaneous estimation of both changepoints and model parameters of spatio-temporal processes. Contrasting to existing spatial changepoint methods, which fit a piecewise stationary model assuming independence across segments, we fit a nonstationary model without any independence assumption. To deal with the complexity of the full likelihood model, we propose a computationally efficient Markov approximation of the likelihood. We study the effect of such an approximation and compare our method with existing methodologies through a comprehensive set of simulation studies. We apply the proposed method for detecting changes in the pattern of daily wind speed measured across different synoptic weather stations in Ireland over two years.
Ed Austin (Lancaster University)
Title: Monitoring Multivariate Functional Data for Emergent Anomalous Structures
Abstract: Motivated by an application monitoring a telecommunications network I present mvFAST, a method for detecting emergent anomalous structures in multivariate functional data. Many existing multivariate functional anomaly detection techniques require the curves to be observed in full, assume the different dimensions of an observation to be independent, or cannot identify which of the dimensions are contaminated by an anomaly. Our approach models the expected structure of the multivariate observation using a system of ODEs, capturing the relationships between the dimensions, and uses a multivariate CUSUM test to detect anomalies in the different dimensions of the data. The test is considered in both offline, and online, settings and the performance of the method will be examined on both simulated and telecommunications data.
Annika Betken (University of Twente)
Title: Ordinal pattern based time series analysis
Lorenzo Cappello (Barcelona School of Economics)
Title: Bayesian variance change point detection with credible sets
Abstract: We introduce a novel Bayesian approach to detect changes in the variance of a Gaussian sequence model, focusing on quantifying the uncertainty in the change point locations and providing a scalable algorithm for inference. We do that by framing the problem as a product of multiple single changes in the scale parameter. We fit the model through an iterative procedure similar to what is done for additive models. The novelty is that each iteration returns a probability distribution on time instances, which captures the uncertainty in the change point location. Leveraging a recent result in the literature, we will show that our proposal is a variational approximation of the exact model posterior distribution. We study the convergence of the algorithm and the change point localization rate. Numerical experiments, applications to biological data, and future extensions will be discussed.
Rachel Carrington (Lancaster University)
Title: Improving power in post-selection inference for changepoints by conditioning on less information
Abstract: Post-selection inference has recently been proposed as a way of quantifying uncertainty about detected changepoints. The idea is to run a changepoint detection algorithm, and then re-use the same data to perform a test for a change near each of the detected changes. By defining the p-value for the test appropriately, so that it is conditional on the information used to choose the test, this approach will produce valid p-values. We show how to improve the power of these procedures by conditioning on less information. This gives rise to an ideal selective p-value that is intractable but can be approximated by Monte Carlo. We show that for any Monte Carlo sample size, this procedure produces valid p-values, and empirically that noticeable increase in power is possible with only very modest Monte Carlo sample sizes. Our procedure is easy to implement given existing post-selection inference methods, as we just need to generate perturbations of the data set and re-apply the post-selection method to each of these.
Oliver Feng (University of Cambridge)
Title: Nonparametric, tuning-free estimation of S-shaped functions
Abstract: We consider the nonparametric estimation of an S-shaped regression function. The least squares estimator provides a very natural, tuning-free approach, but results in a non-convex optimisation problem, since the inflection point is unknown. We show that the estimator may nevertheless be regarded as a projection onto a finite union of convex cones, which allows us to propose a mixed primal-dual bases algorithm for its efficient, sequential computation. After developing a projection framework that demonstrates the consistency and robustness to misspecification of the estimator, our main theoretical results provide sharp oracle inequalities that yield worst-case and adaptive risk bounds for the estimation of the regression function, as well as a rate of convergence for the estimation of the inflection point. These results reveal not only that the estimator achieves the minimax optimal rate of convergence for both the estimation of the regression function and its inflection point (up to a logarithmic factor in the latter case), but also that it is able to achieve an almost-parametric rate when the true regression function is piecewise affine with not too many affine pieces.
Shakeel Gavioli-Akilagun (London School of Economics)
Title: Uncovering Causality in Change Point Regressions
Abstract: We propose a method for estimating graphs which encode (non-) causality between change points present in a moderate number of data streams. Typically after performing change point analysis relationships between estimated change points can only be described qualitatively, since in general change point locations are held to be unknown but non-stochastic. From the perspective of practitioners this is a limitation, since in many settings it is reasonable to believe change points will be causally linked. For example: in climatology changes in concentrations levels of certain gasses actively cause changes in the environment (Schmittner 2018). We model unobserved change point locations as arrival times of a marked point process, for which non-causality is well understood (Didelez 2008). Estimated change point locations can therefore be seen as a noisy sample path of the same process, to which existing estimation procedures can be applied. We will give details of
this ongoing work, and provide real data examples illustrating its practical value.
Anica Kostic (London School of Economics)
Title: Tail-summed scores method for inference in the Gaussian sequence model with applications to change-point analysis
Abstract: We propose the Tail-summed scores method (TSS), a new method for inference in the Gaussian sequence model, and consider it from both signal estimation and multiple testing perspectives. Starting from the full set of values, the pseudo-sequential TSS procedure excludes the largest absolute values one by one, which are then declared as signals, until the remaining set of values begins to resemble noise as a group. This is achieved by comparing the norm of the remaining signal with a certain threshold at each step and stopping the procedure when this norm drops below the threshold. The conservativeness of the procedure can be adjusted by choosing different sequences of thresholds. We discuss its applications to the problem of estimating the subset of coordinates with change in the panel data change-point model, and its potential to improve the accuracy of a change-point estimation method.
Solt Kovács (ETH Zurich)
Title: Optimistic Search Strategy: Change-point Detection for Large-scale Data via Adaptive Logarithmic Queries
Abstract: As a classical and ever reviving topic, change point detection is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. Searching through all candidate split points on the grid for finding the best one requires O(T) evaluations of the gain function for an interval with T observations. If each evaluation is computationally demanding (e.g. in high-dimensional models), this can become infeasible. Instead, we propose optimistic search strategies with O(log T) evaluations exploiting the specific structure of the gain function. Towards solid understanding of our strategies, we investigate in detail the Gaussian change in mean setup. For some of our proposals, we prove asymptotic minimax optimality for single and multiple change point scenarios. Our search strategies generalize far beyond the theoretically analyzed setup. We illustrate, as an example, the massive computational speedup in change point detection for high-dimensional Gaussian graphical models. More generally, we demonstrate empirically that optimistic search methods lead to competitive estimation performance while heavily reducing run-time, both in classical univariate, as well as in high-dimensional problems.
Owen Li (Lancaster University)
Title: Modelling periodic data using changepoints
Abstract: Traditional changepoint approaches consider changepoints to occur linearly in time; one changepoints happens after another and they are not linked. However, there exists fixed periods, e.g.\ days or years, which are repeated across time which results in periodic behaviours. Applying traditional changepoint approaches to these data sets will result in suboptimal solutions as they fail to utilise the periodic nature of these data processes. We propose a deterministic changepoint search method which utilises the periodic nature of these data processes by treating the time axis as circular. This method results in a computational complexity which is independent of the length of the data. Furthermore, we extend this method to detect data processes which exhibit long term changes to periodic behaviour. We demonstrate these methods detect both periodic and global changepoints with high accuracy on motivating digital health applications.
Arnaud Liehrmann (Université Paris-Saclay)
Title: Ms.FPOP: An Exact and Fast Segmentation Algorithm With a Multiscale Penalty
Abstract: Given a time series in R^n with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm to minimize a least square criterion with a multiscale penalty promoting well-spread changepoints. Such a penalty has been proposed in Verzelen et al. (2020), and it achieves optimal rates for changepoint detection and changepoint localization. Our proposed algorithm, named Ms.FPOP, extends functional pruning ideas of Rigaill 2015 and Maidstone et al. (2017) to multiscale penalties. For large signals, n>10^5, with relatively few real changepoints, Ms.FPOP is typically an order of magnitude faster than PELT. We propose an efficient C++ implementation interfaced with R of Ms.FPOP allowing to segment a profile of up to n=10^6 in a matter of seconds.
Malte Londschien (ETH Zurich)
Title: Random Forests for Change Point Detection
Abstract: Change point detection considers the localization of abrupt distributional changes in ordered observations, often time series. We propose a novel multivariate nonparametric change point detection method using classifiers. We construct a classifier log-likelihood ratio that uses class probability predictions to compare different change point configurations. We propose a computationally feasible search method that is particularly well suited for random forests, denoted by changeforest. However, the method can be paired with any classifier that yields class probability predictions, which we illustrate by also using a k-nearest neighbor classifier. We provide theoretical results motivating our choices. In a large simulation study, our proposed changeforest method achieves improved empirical performance compared to existing nonparametric change point detection methods.
This is joint work with Peter Bühlmann and Solt Kovács.
Euan McGonigle (University of Bristol)
Title: Robust multiscale estimation of time-average variance for time series segmentation
Abstract: There exist several methods developed for the canonical change point problem of detecting multiple mean shifts, which search for changes over sections of the data at multiple time scales. In such methods, estimation of the noise level is often required in order to distinguish genuine changes from random fluctuations due to the noise. When serial dependence is present, using a single estimator of the noise level may not be appropriate. Instead, we propose to adopt a scale-dependent time-average variance constant that depends on the length of the data section in consideration, to gauge the level of the noise therein, and propose an estimator that is robust to the presence of multiple change points. We examine the theoretical properties of the estimator and discuss its use within the moving sum and wild binary segmentation procedures. We illustrate the performance of the proposed estimator on an application to the house price index data set.
Hyeyoung Maeng (Durham University)
Title: Robust bottom-up algorithms for high dimensional trend segmentation
Abstract: We propose a new methodology for detecting multiple change-points corresponding to mean changes in high-dimensional panel data. A core ingredient is a new unbalanced wavelet transform: a conditionally orthonormal, bottom-up transformation of the high-dimensional panel data through an adaptively constructed unbalanced wavelet basis. Due to its bottom-up nature, our methodology enables to detect both long and short segments at once. Also, it is invented to be robust in detecting both sparse and dense changes, where a sparse (dense) change refers to a change point at which a sparse (dense) subset of coordinates undergo change. We show the consistency of the estimated number and locations of change-points. The practicality of our approach is demonstrated through simulations and real data examples. This is a joint work with Tengyao Wang and Piotr Fryzlewicz at LSE.
Per August Moen (University of Oslo)
Title: High-dimensional multiple change-point estimation using thresholded CUSUM statistics
Abstract: We study the detection and localization of an unknown number of changes in the mean-vector sequence of high-dimensional Gaussian vectors. We present a sparsity adaptive algorithm, called FAST, which uses both thresholded and partial sum CUSUM statistics to detect and localize change-points. FAST searches for multiple change-points using Seeded Binary Segmentation, and is therefore highly computationally efficient, obtaining a log linear computational complexity. FAST provably localizes all change-points with a near-optimal error rate and under minimal conditions in all sparsity regimes. In numerical simulations we demonstrate that FAST is highly competitive in terms statistical accuracy and computational cost.
Dominic Owens (University of Bristol)
Title: High-Dimensional Data Segmentation in Regression Settings Permitting Heavy Tails and Temporal Dependence
Abstract: We propose a data segmentation methodology for the high-dimensional linear regression problem where the regression parameters are allowed to undergo multiple changes. The proposed methodology, MOSEG, proceeds in two stages where the data is first scanned for multiple change points using a moving window-based procedure, which is followed by a location refinement stage. MOSEG enjoys computational efficiency thanks to the adoption of a coarse grid in the first stage, as well as achieving theoretical consistency in estimating both the total number and the locations of the change points without requiring independence or sub-Gaussianity. In particular, it nearly matches minimax optimal rates when Gaussianity is assumed. We also propose MOSEG.MS, a multiscale extension of MOSEG which, while comparable to MOSEG in terms of computational complexity, achieves theoretical consistency for a broader parameter space that permits multiscale change points. We demonstrate good performance of the proposed methods in comparative simulation studies and also in applications to climate science and economic datasets.
This is joint work with Dr. Haeran Cho.
Florian Pein (Lancaster University)
Title: High-dimensional change-point regression with structured information
Abstract: Observing a large number of time series of related processes at the same time occurs in more and more applications. Consequently, recently many works have considered the detection of change-points that occur in multiple of the time series simultaneously. Sharing the information of the change-point location among different time series increases detection power heavily. In this talk we will consider the situation where we additionally know that all changes have the same sign, i.e. all changes at a certain location are either upwards or downwards. We will propose methodology that have a larger detection power if this situation is given. We will discuss application where this setting occurs, show the increase of detection power in a minimax theory and in numerical simulations.
This is joint work with Hyeyoung Maeng, Paul Fearnhead and Idris Eckley.
Henry Reeve (University of Bristol)
Title: Subgroup selection in non-parametric regimes
Abstract: In this work we consider the challenge of subgroup selection in non-parametric regimes. The goal here is to output a large subset of the feature space which satisfies the following Type 1 error guarantee: On the selected set, the regression function (the conditional expectation of the response given the covariates) is uniformly above some pre-specified threshold, with high probability. We begin by considering a flexible regime where our distributional classes are characterised by the Holder continuity of the regression function on the level set. We then turn to a more benign setting in which we replace smoothness with shape constraints. In particular, we consider a setting in which the regression function is monotonic with respect to a natural partial ordering on the feature space. In this setting we build upon ideas from the multiple testing literature to construct an adaptive procedure with a near-optimal, high probability regret guarantee.
This is joint work with Manuel Muller (Cambridge), Richard Samworth (Cambridge) and Timothy Cannings (Edinburgh).
Gaetano Romano (Lancaster University)
Title: NP-FOCuS: Online Nonparametric Changepoint Detection via Functional Pruning LR tests
Abstract: Online changepoint detection aims to detect anomalies and changes in real-time in high-frequency data streams, sometimes with limited available computational resources. This is an important task that is rooted in many real-world applications, including and not limited to cybersecurity, medicine and astrophysics. While fast and efficient online algorithms have been recently introduced, these rely on parametric assumptions which are often violated in practical applications. Motivated by data streams from the telecommunications sector, we build a flexible nonparametric approach to detect a change in the distribution of a sequence. Our procedure, NP-FOCuS, builds a sequential likelihood ratio test for a change in a set of points of the empirical cumulative density function of our data. This is achieved by keeping track of the number of observations above or below those points. Thanks to functional pruning ideas, NP-FOCuS has a computational cost that is log-linear in the number of observations and is suitable for high-frequency data streams. In terms of detection power, NP-FOCuS is seen to outperform current parametric nonparametric online changepoint techniques in a variety of settings. We demonstrate the utility of the procedure on both simulated and real data.
Vincent Runge (University of Evry, LaMME)
Title: Efficient Pruning Rules For Optimal Partitioning Algorithms in Two-Dimensional Parameter Space
Abstract: We consider the problem of detecting multiple change-points in time series. In recent years, many efficient dynamic programming algorithms have been proposed for a wide class of time-series models. The acceleration from quadratic complexity to close-to-linear one (observed empirically in simulation studies) is made possible by using pruning methods. Most of these algorithms are based on the idea of functional pruning. The functional cost is particularly easy to update for one-parametric functions. This case corresponds (more or less) to univariate time-series.
In this talk, we consider change-point problems for which dynamic programming can be expressed through the update of a piecewise function in a two-dimensional parameter space. Many simple statistical problems correspond to this setting: changes in bi-variate independent time series, change in simple linear regression, change in slope with continuity constraint, changes in mean and variance... We propose a new class of pruning rules based on the update of some points of interest in the 3D space of the functional cost. These points are solutions of optimization problems under constraints. This is an ongoing work on this type of pruning in multidimensional setting. We will evaluate different models and pruning strategies with respect to pruning efficiency and time complexity.
Charles Truong (Centre Borelli)
Title: Automatic calibration of change-point detection methods
Abstract: In numerous applications involving time series, change-point detection is a common step of the data processing pipeline. This step detects the instants when certain user-defined characteristics of the signal abruptly change, for instance, the mean, the variance, the spectral content, etc. A significant difficulty of change detection methods is the calibration. Finding an appropriate set of calibration parameters often requires a laborious manual trial-and-error procedure and expert knowledge in both the application domain (e.g. biostatistics or econometrics) and change-point methods.To alleviate this issue, we propose in this work an automatic calibration procedure that only relies on labels provided by an expert. To that end, the combinatorial optimisation problem at the heart of the detection methods is modified to yield a differentiable (in the parameters) formulation that can then be used as an objective function to learn calibration parameters in a supervised manner. In addition to detection accuracy, this formulation is able to integrate a number of constraints if needed, such as dimension reduction, scaling, sparse representation, etc. We show on several real-world examples that our strategy can learn a correct detection algorithm, with very little input from the domain expert.
Martin Tveten (Norwegian Computing Centre)
Title: Changepoints in the wild
Abstract: This talk contains four short stories about the use of change detection techniques in modern technology: (1) Monitoring IT systems, (2) overheating detection in ship motors, (3) anomaly detection in hydro power plants, and (4) monitoring technical equipment by sound sensors. All the examples deal with streaming data. The focus of the talk is on the particular challenges in each setting and the role of change detection, which varies from detecting data and model drift to data compression and anomaly detection. Hopefully this will inspire some new problems to be solved rigorously.
Kata Vuk (Ruhr-Universität Bochum)
Title: Change-Point Analysis with U-Statistics
Abstract: We study non-parametric tests for changepoints in time series that are based on two-sample U-statistics. By a suitable choice of weights, we obtain tests that are able to detect changes that occur very early or very late during the observation period. Our tests cover both the CUSUM test and the Wilcoxon change-point test as well as many other robust and non-robust tests. We investigate the limit distribution of the tests under the hypothesis that no change occurs, but also under the alternative that there is a change. To illustrate the results and to investigate the power of the tests we will give some simulation results.
Fan Wang (University of Warwick)
Title: Online change point localization in multi-layer random dot product graphs
Abstract: We study the online change point localization problem in dynamic multilayer random dot product graphs (D-MRDPGs). To be specific, at every time point, we extend the nonparametric random dot product graph (RDPG) to the directed multilayer graph with the common node sets and the underlying distributions change when a change point occurs. The goal is to detect the change point as quickly as possible if it exists, subject to a constraint on the probability of false alarms. The change in our framework is in fact, a multivariate nonparametric distributional change. Instead of defining the jump size using a density, we use the expectation of the kernel density estimator (KDE). Our generic model setting allows the model parameters, including the number of nodes, the dimension of latent position, and the magnitude of the change, to vary as functions of the location of the change point. We propose a novel change point detection algorithm and proved an upper bound on the detection delay under a signal-to-noise ratio condition. Additionally, for a single multilayer random dot product graph (MRDPG), we study an estimation method based on the adjacency tensor and show it achieves the optimal statistical performance in estimation error. Finally, extensive numerical results including simulation studies and real data studies are provided to support our theoretical results.
Kes Ward (Lancaster University)
Title: A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint Detection for Exponential Family Models
Abstract: Online changepoint detection algorithms that are based on likelihood-ratio tests have been shown to have excellent statistical properties. However, a simple online implementation is computationally infeasible as, at time T, it involves considering O(T) possible locations for the change. Recently, the FOCuS algorithm has been introduced for detecting changes in mean in Gaussian data that decreases the per-iteration cost to O(log T). This is possible by using pruning ideas, which reduce the set of changepoint locations that need to be considered at time T to approximately log T. We show that if one wishes to perform the likelihood ratio test for a different one-parameter exponential family model, then exactly the same pruning rule can be used, and again one need only consider approximately log T locations at iteration T. Furthermore, we show how we can adaptively perform the maximisation step of the algorithm so that we need only maximise the test statistic over a small subset of these possible locations. Empirical results show that the resulting online algorithm, which can detect changes under a wide range of models, has a constant-per-iteration cost on average.
Ho Yun (EPFL)
Title: Robust Mean estimation on Non-Positive Curvature Spaces
Abstract: In Euclidean spaces, the empirical mean vector as a mean estimator only has polynomial concentration unless a strong tail assumption is imposed on the underlying probability measure. The median-of-means principle has been considered as a way of overcoming the sub-optimality of the empirical mean vector. What about general metric spaces, e.g. Polish spaces that are not necessarily compact nor of finite dimension? In this talk, we discuss the non-asymptotic estimation of the associated population Fréchet means in Polish spaces under only a second-moment condition on the underlying distribution. In this general setting, we first show that the empirical Fréchet mean is sub-optimal in the sense that it has only a polynomial concentration. Then, we extend the existing notion of median-of-means from vector spaces to metric spaces, and demonstrate that this new estimator achieves exponential concentration. We focus on spaces with non-positive Alexandrov curvature since they afford slower rates of convergence than spaces with positive curvature.