Sample Complexity of the Sign-Perturbed Sums Identification Method:
  Scalar Case
Szabolcs Szentpéteri Balázs Csanád Csáji
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.