Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case
This work addresses a theoretical gap for researchers in system identification by analyzing the sample complexity of an existing method, but it is incremental as it extends prior work on SPS.
This paper tackles the problem of analyzing the sample complexity of the Sign-Perturbed Sums (SPS) identification method, providing the first high-probability upper bounds showing that SPS confidence intervals shrink at a geometric rate around the true parameter for scalar linear regression with subgaussian noise.
Sign-Perturbed Sum (SPS) is a powerful finite-sample system identification algorithm which can construct confidence regions for the true data generating system with exact coverage probabilities, for any finite sample size. SPS was developed in a series of papers and it has a wide range of applications, from general linear systems, even in a closed-loop setup, to nonlinear and nonparametric approaches. Although several theoretical properties of SPS were proven in the literature, the sample complexity of the method was not analysed so far. This paper aims to fill this gap and provides the first results on the sample complexity of SPS. Here, we focus on scalar linear regression problems, that is we study the behaviour of SPS confidence intervals. We provide high probability upper bounds, under three different sets of assumptions, showing that the sizes of SPS confidence intervals shrink at a geometric rate around the true parameter, if the observation noises are subgaussian. We also show that similar bounds hold for the previously proposed outer approximation of the confidence region. Finally, we present simulation experiments comparing the theoretical and the empirical convergence rates.