Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Forward Propagation Algorithm for Online Optimization of Nonlinear Stochastic Differential Equations
Optimizing over the stationary distribution of stochastic differential equations (SDEs) is computationally challenging. A new forward propagation algorithm has been recently proposed for the online optimization of SDEs. …
Forward Reachability for Discrete-Time Nonlinear Stochastic Systems via Mixed-Monotonicity and Stochastic Order
We present a method to overapproximate forward stochastic reach sets of discrete-time, stochastic nonlinear systems with interval geometry. This is made possible by extending the theory of mixed-monotone systems to incor…
Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits
We study the problem of online generalized linear regression in the stochastic setting, where the label is generated from a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of …
regressionA Convergent Linear Regression Method for Forward-Backward Stochastic Differential Equations with Jumps
In this paper, we introduce a large class of convergent numerical methods, based on (linear) basis function regression technique, to approximate the solution to a forward-backward stochastic differential equation with ju…
regressionSparsity regret bounds for individual sequences in online linear regression
We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension d can be much larger than the number of time rounds T. We introduce the notion of sparsity regret bound,…
regression