Abstract
This paper introduces Sign-Perturbed Sums (SPS), a novel method for constructing exact non-asymptotic confidence regions for parameters in linear regression models. While standard approaches rely on asymptotic theory—assuming Gaussian error distributions as sample sizes approach infinity—SPS provides rigorous guarantees for any finite sample size. The method requires only that system noise be independent and symmetric. We show that SPS regions are star-convex, centered on the least-squares estimate, and can be efficiently bounded by ellipsoidal approximations, offering a robust alternative to traditional heuristic regions in system identification.
Introduction
In system identification and machine learning, point estimates of parameters are often insufficient; practitioners require confidence regions to quantify uncertainty. Traditional methods for constructing these regions typically rely on asymptotic theory, which assumes that estimation errors follow a Gaussian distribution as the dataset size grows to infinity. However, for small or finite datasets, these heuristic regions can be misleading and lack strict theoretical guarantees.
Previous attempts to address this, such as the Leave-out Sign-dominant Correlation Regions (LSCR) method, faced challenges with multidimensional parameters or failed to ensure that the standard Least-Squares Estimate (LSE) was included within the confidence region. Sign-Perturbed Sums (SPS) addresses these gaps by providing a distribution-free method that is exact for any sample size, includes the LSE, and scales to multidimensional systems.
Methodology
The core of the SPS approach is a sign-perturbation mechanism applied to the normal equations of standard Least Squares. The process involves four primary steps:
- Reference Sum Definition: A "reference sum" is defined based on the prediction errors of a candidate parameter $\theta$.
- Sign Flipping: $m-1$ "perturbed" versions of this sum are created by randomly flipping the signs ($\pm 1$) of the terms.
- Statistical Ranking: If $\theta$ is the true parameter, the reference sum and the perturbed sums share the same distribution and are statistically indistinguishable.
- Indicator Function: A candidate $\theta$ is included in the confidence region if its reference sum ranks among the smallest $m-q$ sums. The probability that the true parameter lies within this region is exactly $1 - q/m$.
To overcome the computational "curse of dimensionality" when checking candidate parameters in high-dimensional space, the authors introduce an Ellipsoidal Outer Approximation. This convex optimization-based algorithm identifies a tight ellipsoid that encapsulates the SPS region, ensuring practical utility.
Key Results and Discussion
The authors evaluated SPS across various simulated scenarios, including second-order FIR systems, heavy-tailed (Laplacian) noise, and undermodelled systems.
Small Sample Performance
One of the most significant advantages of SPS is its reliability with small datasets. In simulations with only 25 data points, SPS regions maintained their 95% theoretical guarantee. In contrast, traditional asymptotic regions remained purely heuristic and potentially inaccurate in this regime.
Convergence and Efficiency
As the sample size increases, the SPS regions align more closely with traditional optimal regions if the noise is Gaussian, yet they maintain their exactness regardless of the noise distribution. For a system with 3,200 data points, the ellipsoidal approximation was computed in approximately 23 seconds on a standard laptop, demonstrating its feasibility for real-world engineering tasks.
Conclusion
SPS represents a significant advancement in system identification by providing exact, non-asymptotic confidence regions with minimal assumptions. The method's star-convexity ensures it is well-behaved around the LSE, and the "block" strategy allows for adaptation to correlated noise. Future work will focus on extending these guarantees to closed-loop systems where inputs depend on past noise, a non-trivial challenge for current exact methods.
Summary updated