# Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 36 references that are in the map.
- First posted on arXiv 2 Nov 2021.

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

- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Meta-learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2005.08531/) (2020)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Uniform regret bounds over Rd for the sequential linear regression problem with the square loss](https://mlsanity.com/paper/1805.11386/) (2018)

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

- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [Likelihood Ratio Confidence Sets for Sequential Decision Making](https://mlsanity.com/paper/2311.04402/) (2023)
- [Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback](https://mlsanity.com/paper/2302.09357/) (2023)
- [Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits](https://mlsanity.com/paper/2202.13603/) (2022)
- [A Batch-to-Online Transformation under Random-Order Model](https://mlsanity.com/paper/2306.07163/) (2023)
- [Incremental Online Learning of Randomized Neural Network with Forward Regularization](https://mlsanity.com/paper/2412.13096/) (2024)
- [Multivariate Online Linear Regression for Hierarchical Forecasting](https://mlsanity.com/paper/2402.14578/) (2024)
- [Testing Credibility of Public and Private Surveys through the Lens of Regression](https://mlsanity.com/paper/2410.05458/) (2024)
- [OLR-WAA: Adaptive and Drift-Resilient Online Regression with Dynamic Weighted Averaging](https://mlsanity.com/paper/2512.12779/) (2025)
- [msData: A Millisecond-Resolution Network Dataset for Advancing Time Series Foundation Models](https://mlsanity.com/paper/2603.16497/) (2026)

## Abstract (arXiv)

We consider the problem of online linear regression in the stochastic setting. We derive high probability regret bounds for online ridge regression and the forward algorithm. This enables us to compare online regression algorithms more accurately and eliminate assumptions of bounded observations and predictions. Our study advocates for the use of the forward algorithm in lieu of ridge due to its enhanced bounds and robustness to the regularization parameter. Moreover, we explain how to integrate it in algorithms involving linear function approximation to remove a boundedness assumption without deteriorating theoretical bounds. We showcase this modification in linear bandit settings where it yields improved regret bounds. Last, we provide numerical experiments to illustrate our results and endorse our intuitions.