- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies how to locate changes in the distribution of a sequence of high-dimensional observations, including changes in dependence between coordinates that leave their individual means and variances unchanged. The method uses part of the data to learn a quadratic function whose expectation differs across a change, then applies that function to separate observations and locates the resulting scalar mean change. Assuming bounded densities and a low-rank matrix of changes in first and second moments, the authors prove detection and localization guarantees, with extensions to temporally dependent observations. Their experiments examine how accuracy depends on dimension, signal strength, the chosen rank, and temporal dependence.
Critical strengths
The method combines changes in many pairwise interactions into a single statistic obtained through a quadratic form, allowing it to detect changes that are difficult to see in individual coordinates. The theory gives explicit conditions under which the estimated statistic preserves enough of the signal for accurate localization.
Critical weaknesses
- The paper is extremely poorly-written and almost impossible to read. A clear, self-contained explanation of when the method works and what it improves over existing methods is missing. This is my primary concern, since it makes the contribution difficult to assess even after careful reading.
- The advantage over existing methods is not convincingly demonstrated. The experiments do not establish whether combining more directions provides a substantial benefit once the additional data needed to estimate them is taken into account.
Questions for authors
- Can you give a self-contained statement of the assumptions and sample size requirements for your main result, and explain precisely what it improves over the closest existing method? In particular, can you improve the writing throughout the paper?
- Do you have theoretical or experimental evidence that combining several changing directions substantially improves accuracy over using the strongest direction alone, after accounting for the additional data needed to estimate those directions?
5 comments
Weakness 2. Localization accuracy at the same training and evaluation budgets
Thank you for asking whether the gain survives the cost of estimating the second direction. Table 1 lets us make that comparison within each trial. Both estimators see exactly the same sequence. Each scans the same candidate locations using the odd observations and learns its own weights. One uses the strongest estimated direction and the other uses two. On the even observations, both use the first and last quarters to estimate the two means and the same scalar least squares criterion to locate the change. Thus any difficulty estimating the extra direction already affects the reported error.
Both estimators are told that there is one change and search the central half of the sequence. The true location is drawn uniformly among the integers from to , with the total sample size. The dense rank two jump has Frobenius norm 0.9. Each entry in the last two columns is the median absolute location error in time points over 40 trials.
Dimension Learning Evaluation One direction Two directions
16 2,048 2,048 7 2.5
32 2,048 2,048 9.5 4.5
64 2,048 2,048 24.5 4.5
128 2,048 2,048 41 9.5
200 2,048 2,048 618.5 472
200 4,096 4,096 12 6
200 8,192 8,192 9.5 3.5
At dimension 200, with 4,096 observations for learning and another 4,096 for evaluation, including the second direction halved the median error from 12 to 6. On those same 40 sequences, two directions gave a closer estimate in 24 trials, tied in 7, and gave a larger error in 9. This comparison isolates the choice of rank within a common procedure.
Question 1. Assumptions, sample size and comparison with covariance projection
Theorem 3.3 treats independent observations in with changes. Within each segment the distribution is constant, with density at most relative to uniform probability on the cube. Coordinates within an observation may be dependent.
We measure change by , the difference between the mean feature matrices after and before the change. The symmetric feature matrix has , , , and for . Assume each has rank at most . Its Frobenius norm is the jump size, and . A coefficient matrix of unit Frobenius norm defines the scalar , whose mean changes by .
Split the data into pairs. The odd observations learn the directions and the even observations locate the changes. Write for the number of odd observations in the shortest segment, including the end segments. Choose a minimum scan window that is a multiple of four with . Two requirements determine how much data is sufficient.
- To learn the directions, require and use threshold . One conservative pilot noise bound is , where is the failure probability, and counts the candidate window and split pairs, including expanded windows. This count is at most .
- To estimate the scalar means on each side, it suffices that exceed a universal constant times .
Together these conditions guarantee, with probability at least , that the procedure finds exactly changes and retains at least of each jump. The location error at change is at most a universal constant times time points.
Wang, Yu and Rinaldo’s WBSIP also learns projections on separate data. For centered sub-Gaussian observations it measures a covariance change of any rank by its largest absolute eigenvalue. Our method targets low rank changes in the normalized moment matrix defined above. Its best single direction captures the largest absolute eigenvalue of , while the best rank contrast captures the square root of the sum of its squared eigenvalues. Both methods give inverse squared dependence on their respective jump sizes for small jumps. The improvement here is that several components, even with opposite signs, can increase the scalar jump used for localization. The first sample requirement accounts for learning them. Table 1 compares the two ranks within our procedure. Wang, Yu and Rinaldo (2021)
For the revision, we propose opening with the two group example, defining the two samples before the algorithm, stating the learning and localization requirements together before the proofs, and leading the experiments with the comparison at equal sample sizes.
Weakness 1. When combining directions helps locate a change
Thank you for pointing out that the paper needs an example showing when the extra directions help. Consider two groups of coordinates whose individual means and variances stay fixed. What changes is how the groups move together. In our example, adding the coordinates within each group and multiplying the two sums gives a scalar whose mean changes. If the coefficient matrices are normalized to unit Frobenius norm, the best single direction captures at most 70.7% of the available quadratic moment signal, measured by the change in the scalar mean. Combining two directions with known weights captures all of it.
The question in practice is whether we can learn those weights. For independent observations, we use the odd observations to learn a weighted sum of coordinates, their squares and their pairwise products. We apply that function to the even observations and locate the change in its mean. The guarantee applies when the change in these moments has low rank and each segment is long enough both to learn the weights and to estimate the two scalar means. With high probability the learned function then retains at least half of each jump. Once it is learned, the location error bound has no further factor for the number of coordinates (Theorem 3.3).
For each candidate interval, Wang, Yu and Rinaldo (2021) learn a projection along which the variance changes. Our gain comes from combining several changing components in one scalar. In our 64 dimensional experiment with one known change and unknown location, both ranks of our estimator learned from the same 2,048 observations and evaluated on the same other 2,048. Using two directions reduced the median absolute location error from 24.5 to 4.5 time points over 40 trials (Table 1).