# Finite Sample Analysis of Distribution-Free Confidence Ellipsoids for Linear Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 49 references that are in the map.
- First posted on arXiv 13 Sep 2024.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [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)
- [Low Rank and Structured Modeling of High-dimensional Vector Autoregressions](https://mlsanity.com/paper/1812.03568/) (2018)
- [Set Membership identification of linear systems with guaranteed simulation accuracy](https://mlsanity.com/paper/2001.07628/) (2020)
- [Sign-Perturbed Sums (SPS) with Instrumental Variables for the Identification of ARX Systems - Extended Version](https://mlsanity.com/paper/1509.04774/) (2015)
- [Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case](https://mlsanity.com/paper/2401.15792/) (2024)
- [Non-Asymptotic State-Space Identification of Closed-Loop Stochastic Linear Systems using Instrumental Variables](https://mlsanity.com/paper/2301.12537/) (2023)
- [Finite-Sample Identification of Linear Regression Models with Residual-Permuted Sums](https://mlsanity.com/paper/2406.05440/) (2024)
- [Sample Complexity of the Sign-Perturbed Sums Method](https://mlsanity.com/paper/2409.01243/) (2024)

## Abstract (arXiv)

The least squares (LS) estimate is the archetypical solution of linear regression problems. The asymptotic Gaussianity of the scaled LS error is often used to construct approximate confidence ellipsoids around the LS estimate, however, for finite samples these ellipsoids do not come with strict guarantees, unless some strong assumptions are made on the noise distributions. The paper studies the distribution-free Sign-Perturbed Sums (SPS) ellipsoidal outer approximation (EOA) algorithm which can construct non-asymptotically guaranteed confidence ellipsoids under mild assumptions, such as independent and symmetric noise terms. These ellipsoids have the same center and orientation as the classical asymptotic ellipsoids, only their radii are different, which radii can be computed by convex optimization. Here, we establish high probability non-asymptotic upper bounds for the sizes of SPS outer ellipsoids for linear regression problems and show that the volumes of these ellipsoids decrease at the optimal rate. Finally, the difference between our theoretical bounds and the empirical sizes of the regions are investigated experimentally.