2025/03/21 by Jing Yu, Zeng, Xiong, Yu, Jing +2
Computer Science · Engineering · #Advanced Adaptive Filtering Techniques #Control Systems and Identification #FOS: Electrical engineering #Machine Learning and Algorithms #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2503.16817
openalex publication_date 2025/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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/√(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/√(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.