Overview
This paper investigates the detection and estimation of a single change within the framework of high-dimensional linear models. The research establishes minimax lower bounds for both the detection boundary and the estimation rate, which collectively reveal a phase transition. This transition is characterized by the sparsity of a metric termed the covariance-weighted differential parameter. This parameter, described as "inherent sparsity," captures the interaction between the regressor covariance structure and the change in regression coefficients, influencing the detectability of a change point.
Research Context
The problem of change point detection in high-dimensional linear models involves identifying when the underlying relationship between variables undergoes a structural shift. The complexity of this problem increases significantly with the number of variables (dimension). Understanding the fundamental limits of detectability and estimation accuracy, particularly under varying sparsity conditions, is central to developing effective detection methodologies.
Approach
The research first centered on deriving minimax lower bounds. These bounds provide theoretical limits on the best possible performance for change point detection and estimation in the specified high-dimensional linear models. The derivation of these bounds specifically aimed to identify the conditions under which a change point becomes detectable and the rate at which it can be estimated, revealing the influence of the covariance-weighted differential parameter's sparsity. This analysis led to the identification of a 'phase transition' as governed by this sparsity.
Following the theoretical analysis, two covariance scanning-based methods were introduced: McScan and QcSan. The architecture and operational principles of these methods were designed to complement the derived lower bounds. McScan was developed to perform optimally in sparse regimes, while QcSan was designed for optimal performance in dense regimes. QcSan is noted as the first method demonstrated to achieve consistency in the dense regime. A combined procedure was subsequently devised to integrate the strengths of both McScan and QcSan. This combined procedure aims to achieve adaptively minimax optimal performance across both sparse and dense regimes, without requiring prior knowledge of the true sparsity level.
Computationally, the covariance scanning-based methods avoid the use of costly Lasso-type estimators. Their design results in a worst-case computational complexity that is linear with respect to both the dimension and the sample size. Beyond general change point detection, the research also considers the post-detection estimation of the differential parameter and the subsequent refinement of the initial change point estimator.
Findings
- Minimax lower bounds were derived for the detection boundary and the estimation rate in high-dimensional linear models.
- A phase transition was identified, governed by the sparsity of the covariance-weighted differential parameter. This parameter represents the interplay between the regressor's covariance structure and the change in regression coefficients, affecting change point detectability.
- Two covariance scanning-based methods, McScan and QcSan, were introduced.
- McScan achieves minimax optimal performance (up to possible logarithmic factors) in sparse regimes.
- QcSan achieves minimax optimal performance (up to possible logarithmic factors) in dense regimes.
- QcSan is the first method shown to achieve consistency in the dense regime.
- A combined procedure was devised that achieves adaptively minimax optimal performance across both sparse and dense regimes without requiring prior knowledge of the sparsity.
- The covariance scanning-based methods exhibit worst-case computational complexity that is linear in the dimension and sample size, avoiding the high cost of Lasso-type estimators.
- Post-detection estimation of the differential parameter and refinement of the change point estimator were also considered.
- Simulation studies support the theoretical findings, demonstrating the computational and statistical efficiency of the proposed covariance scanning methods.