System Identification Under Bounded Noise: Optimal Rates Beyond Least Squares
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912423798112256 |
|---|---|
| author | Zeng, Xiong Yu, Jing Ozay, Necmiye |
| author_facet | Zeng, Xiong Yu, Jing Ozay, Necmiye |
| contents | System identification is a fundamental problem in control and learning, particularly in high-stakes applications where data efficiency is critical. Classical approaches, such as the ordinary least squares estimator (OLS), achieve an $O(1/\sqrt{T})$ convergence rate under Gaussian noise assumptions, where $T$ is the number of samples. This rate has been shown to match the lower bound. However, in many practical scenarios, noise is known to be bounded, opening the possibility of improving sample complexity. In this work, we establish the minimax lower bound for system identification under bounded noise, proving that the $O(1/T)$ convergence rate is indeed optimal. We further demonstrate that OLS remains limited to an $Ω(1/\sqrt{T})$ convergence rate, making it fundamentally suboptimal in the presence of bounded noise. Finally, we instantiate two natural variations of OLS that obtain the optimal sample complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16817 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | System Identification Under Bounded Noise: Optimal Rates Beyond Least Squares Zeng, Xiong Yu, Jing Ozay, Necmiye Systems and Control System identification is a fundamental problem in control and learning, particularly in high-stakes applications where data efficiency is critical. Classical approaches, such as the ordinary least squares estimator (OLS), achieve an $O(1/\sqrt{T})$ convergence rate under Gaussian noise assumptions, where $T$ is the number of samples. This rate has been shown to match the lower bound. However, in many practical scenarios, noise is known to be bounded, opening the possibility of improving sample complexity. In this work, we establish the minimax lower bound for system identification under bounded noise, proving that the $O(1/T)$ convergence rate is indeed optimal. We further demonstrate that OLS remains limited to an $Ω(1/\sqrt{T})$ convergence rate, making it fundamentally suboptimal in the presence of bounded noise. Finally, we instantiate two natural variations of OLS that obtain the optimal sample complexity. |
| title | System Identification Under Bounded Noise: Optimal Rates Beyond Least Squares |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2503.16817 |