Skip to Main content Skip to Navigation
New interface
Conference papers

Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03410901
Contributor : reda ouhamma Connect in order to contact the contributor
Submitted on : Monday, November 1, 2021 - 8:38:08 PM
Last modification on : Tuesday, November 22, 2022 - 2:26:16 PM
Long-term archiving on: : Wednesday, February 2, 2022 - 6:26:21 PM

File

Neurips_Forward_Algo.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03410901, version 1

Collections

Citation

Reda Ouhamma, Odalric Maillard, Vianney Perchet. Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge. NeurIPS 2021 - 35th International Conference on Neural Information Processing Systems, Dec 2021, Virtual, Canada. ⟨hal-03410901⟩

Share

Metrics

Record views

55

Files downloads

47