# Uniform regret bounds over Rd for the sequential linear regression problem with the square loss

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2018.

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

- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Locality Sensitive Sparse Encoding for Learning World Models Online](https://mlsanity.com/paper/2401.13034/) (2024)
- [Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge](https://mlsanity.com/paper/2111.01602/) (2021)
- [Quasi-Newton Steps for Efficient Online Exp-Concave Optimization](https://mlsanity.com/paper/2211.01357/) (2022)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback](https://mlsanity.com/paper/2302.09357/) (2023)
- [Online nonparametric regression with Sobolev kernels](https://mlsanity.com/paper/2102.03594/) (2021)
- [Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits](https://mlsanity.com/paper/2202.13603/) (2022)
- [Decentralized Online Regularized Learning Over Random Time-Varying Graphs](https://mlsanity.com/paper/2206.03861/) (2022)
- [Multivariate Online Linear Regression for Hierarchical Forecasting](https://mlsanity.com/paper/2402.14578/) (2024)
- [Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning](https://mlsanity.com/paper/2503.20087/) (2025)
- [A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS](https://mlsanity.com/paper/2506.22631/) (2025)
- [Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression](https://mlsanity.com/paper/2605.01628/) (2026)
- [Agnostic Smoothed Online Regression with Adversarial Responses](https://mlsanity.com/paper/2609.32478/) (2026)

## Abstract (arXiv)

We consider the setting of online linear regression for arbitrary deterministic sequences, with the square loss. We are interested in the aim set by Bartlett et al. (2015): obtain regret bounds that hold uniformly over all competitor vectors. When the feature sequence is known at the beginning of the game, they provided closed-form regret bounds of 2d B2 ln T + OT(1), where T is the number of rounds and B is a bound on the observations. Instead, we derive bounds with an optimal constant of 1 in front of the d B2 ln T term. In the case of sequentially revealed features, we also derive an asymptotic regret bound of d B2 ln T for any individual sequence of features and bounded observations. All our algorithms are variants of the online non-linear ridge regression forecaster, either with a data-dependent regularization or with almost no regularization.