# Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case

arXiv: https://arxiv.org/abs/2401.15792 · HTML: https://mlsanity.com/paper/2401.15792/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 28 Jan 2024.

## Builds on (most cited first, 6 of 6)

- [Sign-Perturbed Sums: A New System Identification Approach for Constructing Exact Non-Asymptotic Confidence Regions in Linear Regression Models](https://mlsanity.com/paper/1807.08216/) (2018)
- [Distribution-Free Uncertainty Quantification for Kernel Methods by Gradient Perturbations](https://mlsanity.com/paper/1812.09632/) (2018)
- [Nonparametric, Nonasymptotic Confidence Bands with Paley-Wiener Kernels for Band-Limited Functions](https://mlsanity.com/paper/2206.13629/) (2022)
- [Perturbed Datasets Methods for Hypothesis Testing and Structure of Corresponding Confidence Sets](https://mlsanity.com/paper/1412.2352/) (2014)
- [Sign-Perturbed Sums (SPS) with Instrumental Variables for the Identification of ARX Systems - Extended Version](https://mlsanity.com/paper/1509.04774/) (2015)
- [Exact Distribution-Free Hypothesis Tests for the Regression Function of Binary Classification via Conditional Kernel Mean Embeddings](https://mlsanity.com/paper/2103.05126/) (2021)

## Built on by (most cited first, 3 of 3)

- [Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits](https://mlsanity.com/paper/2406.05710/) (2024)
- [Sample Complexity of the Sign-Perturbed Sums Method](https://mlsanity.com/paper/2409.01243/) (2024)
- [Finite Sample Analysis of Distribution-Free Confidence Ellipsoids for Linear Regression](https://mlsanity.com/paper/2409.08801/) (2024)

## Abstract (arXiv)

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.