Near-optimal inference in adaptive linear regression
Koulik Khamaru, Yash Deshpande, Tor Lattimore, Lester Mackey, Martin J. Wainwright
The Annals of Statistics · 2025 · Volume 53 · Issue 6
Abstract
When data is collected in an adaptive manner, even simple methods like ordinary least squares can exhibit nonnormal asymptotic behavior. As an undesirable consequence, hypothesis tests and confidence intervals based on asymptotic normality can lead to erroneous results. We propose a family of online debiasing estimators to correct these distributional anomalies in least squares estimation. Our proposed methods take advantage of the covariance structure present in the dataset and provide sharper estimates in directions for which more information has accrued. We establish an asymptotic normality property for our proposed online debiasing estimators under mild conditions on the data collection process and provide asymptotically exact confidence intervals. We additionally prove a minimax lower bound for the adaptive linear regression problem, thereby providing a baseline by which to compare estimators. There are various conditions under which our proposed estimators achieve the minimax lower bound. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
Keywords
6208, 62E20, Adaptive linear regression, asymptotic normality, autoregressive time series, minimax lower bound, Multi-armed bandits, online debiasing
Enable JavaScript for citation tools and additional paper interactions.