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.

Sign-Perturbed Sum (SPS) 是一种强大的有限样本系统辨识算法，可以为任何有限样本大小的真实数据生成系统构造具有确切覆盖概率的置信区间。本论文旨在填补这一研究空白，首次提供了关于 SPS 样本复杂度的结果，以及对于标量线性回归问题中 SPS 置信区间行为的研究，提供了基于三组不同假设条件的高概率上界，表明如果观测误差是亚高斯分布，那么 SPS 置信区间的大小将以几何速率收敛于真实参数，并且同样的界限适用于先前提出的置信区域外估计，最后，我们通过模拟实验证明了理论和经验的收敛速度。