Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
Authors: Reda Ouhamma
Odalric-Ambrym Maillard
Vianney Perchet
Venue:  (2021)
Keywords: Online linear regression
Multi-armed bandit

Abstract: We consider the problem of online linear regression in the stochastic setting. We derive high probability regret bounds for online $\textit{ridge}$ regression and the $\textit{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.

Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
Reda Ouhamma
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRIStAL, F-59000 reda. ouharma@univ-iill..
Odalric. Maillard
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISIAL, F-59000
Vianney. Perchet
Criteo, ENSAE, ENS PARIS-SACLAY
Abstract
We consider the problem of online linear regression 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 yields improved regret bounds. Last, we provide numerical experiments to illustrate our results and endorse our intuitions.
Introduction and preliminaries
The forward regression algorithm, popularized in 24 3, shows competitive performance bounds in the challenging setup of online regression with adversarial bounded observations. We revisit the analysis of this strategy the practically relevant alternative situation of stochastic linear regression with sub-Gaussian noise, hence possibly unbounded observations. When compared to the classical ridge regression strategy its natural competitor the existing analysis in the adversarial bounded case suggests the forward algorithm has higher performances. It is then natural to ask whether this conclusion holds for the stochastic setup. However, we show that in the stochastic setup, the existing adversarial analysis does not seem sufficient to draw conclusions, it does not capture some important phenomena, such as the concentration of the parameter estimate around the regression parameter. It may further lead the practitioner to parameter. In order to overcome these issues, we revisit the analysis of the forward algorithm in the case of unbounded sub-Gaussian linear regression and provide a high probability regret bound the performance of the forward and ridge regression strategies. Owing to this refined analysis, we show that the forward algorithm is superior in this scenario well, but for different reasons than what is suggested by the adversarial analysis. We discuss the implications of this result in a practical application: stochastic linear bandits, both from theoretical and experimental perspectives.
improper tuning of the regularization
Setup: In the classical setting of online regression with the square loss, an environment initially chooses sequence of feature vectors (2x) Rd together with corresponding observations {ych
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

R. Then, at each decision step f. the learner receives feature vector 2; and must output prediction Dr R. Afterwards, the environment reveals the true label y4 and iteration begins. In this article, we focus on the case when the data generating process is a stochastic linear model:
38. E Rd such that Vt E N Yt = 02 +
where (er) is noise sequence. At iteration 4, strategy A computes a parameter 0,- to predict 0z4 x, 8 1- In the sequel, omit the subscript A when the algorithm is clear from context. The learner's prediction incurs the loss: E/ def ((x] 0 (út 3/ the learner then updates its prediction 1 to 02 and so on. The total cumulative loss at horizon T' denoted L = = 4. We also let (0) fxr; 0, Mh) (resp. LT(0) - -== (x) be the instantaneous (resp. cumulative) loss incurred by predicting at time & (resp. 14 1,...; T). Online regression algorithms are evaluated using different regret definitions, in the form of relative cumulative loss batch loss; The quantity of interest this paper is:
R - LT min LT(
From the perspective of online learning theory, online regression algorithms are usually designed for an adversarial setting, assuming an arbitrary bounded response variable Wel S Y each time step. While the mere existence of algorithms with tight guarantees in this general setting is remarkable, practitioner may also consider alternative settings, in which analysis for the adversarial setup may be overly conservative. For illustration, focus the practical setting of bounded parameter ||0_ 1l2 < S and i.idd zero-mean
noise sequences:
Vt 2 1,7 R E [exp(re)) S exp(o222/2).
We emphasize that while previous results in literature are valid for the adversarial bounded setting, we will still shed new light on the performance of these strategies in a stochastic unbounded setup, which is neither more general nor more restrictive than the adversarial one, and discuss their implications for the practitioner. Let recall the two popular online regression algorithms considered.
Online ridge regression [Algorithm 1]: the greedy version of batch ridge regression:
This folklore algorithm is defined in the online setting as
o E arg min (0) 21
where À is parameter and 1|10 is regularization used to penalize model complexity. Algorithm 1: Online ridge regression
Given Bg E Rdd for t = I....,T do
observe x2 E Rd and predict ú; x. 0:-1 E R observe Yt and incur loss & E TR update parameter: 07 E arg min, (0) + alellk
end
A solution to the quadratic optimization problem of Fq. 2 is given in closed form, by 0F = -
where GA) Al + E Zy and by = Σn= Lglly. We may further denote G2 instead of (A)
when À is clear from context.
The forward algorithm [Algorithm 2]: A subtle change the ridge regression takes advantage of the next feature 1 to better adapt to the next loss:
of E arg min (e( + (=2+10)2 + 21101k
(3)

---

Algorithm 2: The forward algorithm
Given 8g E R.a for t ,,..., do
observe E Rd
update parameter: - E arg (0-1(0) [x]0)² 1|101k
predict Ut = x. of 1 E IR
end observe Y/ and incur loss l E
Equivalently, the update step can be written: 0.5 == by where G2 is still defined same as before. Intuitively, the term (z 0)² in Eq. 3 is a "predictive loss", a penalty on the parameter 0 in the direction of the new feature vector 1 This approach can be linked to transductive methods for regression g 22 [22] describe two algorithms for linear prediction in supervised settings, and leverage the knowledge of the next test point to improve the prediction accuracy. However, these algorithms have significant computational complexities and are not adapted to online settings.
Related work Linear regression is perhaps one of the most known algorithms in machine learning, due to is simplicity and explicit solution. In contrast with the batch setting (when all observations are provided), online linear regression started receiving interest relatively recently. The first theoretical analyses date back to 9 14 7 13 Under the assumption that the response variable is bounded lyel S Y. it has been shown that the forward algorithm 24 3 achieves relative cumulative online error of dY² lTg(T) compared to the best batch regression strategy. This bound holds uniformly over bounded response variables and competitor vectors, and is 4 times better than the corresponding bound derived for online ridge regression.
Bartlett et al. 4 studied minimax regret bounds for online regression, and ingeniously removed dependence on the scale of features in existing bounds by considering the beforehand-kmovt features setting, where all feature points { ) hsss
known before the learning starts. Moreover, they derive a "backward algorithm" that is optimal under certain intricate assumptions on observations and features. Later on, [16] were able to prove that under new (tricky) assumptions on observed features and labels the backward algorithm is not only optimal but applicable in sequential settings as well. More recently, (11) provided an optimal algorithm in the setting of beforehand known features without imposing stringent conditions as in [6). They show that the forward algorithm with A = 0 yields first-order optimal asymptotic regret bound uniform over bounded observations. However, due to the lack of regularization, their bound (cf. Theorem 11 in (.) may blow up if the design matrix (0) is not full rank. It is hence not uniform over all bounded feature sequences {x+}..
Paper outline and contributions: In this paper, we continue the line of work initiated on the forward algorithm and advocate for its use in the stochastic setting with possibly unbounded response variables, in replacement for the ridge regression (whenever possible). To this end, we consider an online stochastic linear regression setup where the noise is assumed to be i.i.d o-sub-Gaussian.
In Section 2 we recall the online performance bounds established for ridge regression and the forward algorithm in the adversarial case with bounded observations. Next, in subsection 2.3] we diseuss some limitations of the adversarial results when comparing regression algorithms in the stochastic setting. For instance, these bounds compare the cumulative loss of strategy to the value of the batch optimization problem, which may not be indicative of the real performance of the strategy (cf. Corollary 1. and may encourage sub-optimal tuning of the regularization parameter.
In Section 3 we study the performance of these algorithms using the cumulative regret with respect to the true parameter (cf. Eq. 6). which we believe more practitioner-friend) than comparing to the batch optimization problem. We show in Theorem 3. how these two measures of performance are related. We provide in Theorems 3.2 and 3.3 novel analysis of online regression algorithms without assuming bounded observations. This key result is made possible by considering high probability bounds instead of bounded individual sequences. We show that the regret upper-bound bound for ridge regression is inversely proportional to the regularization parameter. Consequently, we argue that following these results, forward regression should be used in lieu of ridge regression.
In Section 4 we revisit the linear bandit setup previously analyzed assuming bounded rewards: we relax this assumption and provide -optimism in the face of uncertainty- style algorithm with the
3

---

forward algorithm instead of ridge, which is especially well-suited for the bandit setup, and provide novel regret analysis in Theorem 4.1 We proceed similarly in Appendix revisiting a setup of non-stationary (abruptly changing) linear bandits.
2
Adversarial bounds and limitations
In this section, we recall existing results regarding the aforementioned ridge and forward algorithms. We then discuss their limits and benefits when considered from a stochastic perspective.
2.1 Adversarial regret bounds (existing results)
One of the first theoretical analyses of online regression dates back to 24 and 33. and is recalled in the theorem below. It is stated in the form an toninieto-offline conversion" performance bound. Theorem 2.1. (Theorem 4. of (3)) The online ridge regression algorithm satisfies:
(1 (1+ TX2
L min (L) + (11111) I 2
Ad
where X = max |1 and y"= max 1SIST
{lvel 1,.
1S15T
The reader should note that this result compares the learner's ' online cumulative loss to the regularized batch ridge regression loss. As such, it is an online- to-fe-t conversion regret. This is different from the sequential regret that would compare the minimum achievable loss. This theorem highlights dependence on the range of predictions of the algorithm, as Y 2 max xx 0.-1|-
15tST
Remark 1. (Small losses) The regret bound for ridge regression can be improved if the learner knows that the loss is small for the best expert, see Orabona et al. [18]. Note however that such techniques require prior knowledge of all the best expert loss Li,, their optimal bound is O(y Li log T).
The forward algorithm has an enhanced performance in this setup according this next result. Theorem 2.2. (Theorem 5.6 of (3)) The forward algorithm satisfie
T
14 min (0) x|1013) S (Y1)
1 1+
Ad
where
|1x, and y 1SEST
max
max 1S
196]-
Notice that in this result Y different than in Theorem 2.1 and independent from the algorithm's predictions. Moreover, Theorem 2.2 exhibits a bound that is at least 4 times better than Theorem 2.1 More precisely, Theorem 2. suggests that, in order compare the two bounds, prior knowledge of Y is required to further clip the predictions of online ridge regression in [-y+ yf); and that even with such knowledge the forward algorithm may be 4-times better than ridge regression. We believe that this unfortunately led researchers to turn away from analyzing more deeply what may happen.
2.2 Limitation in the adversarial setup: rigid regularization
To evaluate online regression strategies, tight lower bound was derived in | The latter studied uniform minimax lower bounds the setting of beforehand-known features (that is when (z: ( known in advance), which is very challenging for lower bound. They show that, the minimax uniform regret bound is controlled as follows.
Theorem 2.3. (Gaillard et al. (T7)) For all T 2 8,Y we have:
R
(logl) (3 + log(d)) log(lo((d)))
where Ry [-Y]
inf
sup
sup 1 by SY
Eln(v (v 1 2
inf R Σh (v: 27 u)2
Note that there are typos in the statement of this theorem in original paper: compare Lemma 4.2 with Theorems 4.6 and 5.6 therein to see this. Reported theorems are accurate. See footnote |

---

We will use this result to evaluate the optimality of ridge and forward regressions. First, we need to convert Theorems 2.1 and 2.2 sequential regrer bounds. Indeed, their current form, they compare the cumulative loss of the learner to the value of regularized batch optimization. This next result transforms them, and a corollary Theorems 11.7 and 1 11.8 of
Lugosi [6]
Corollary 2.3.1. (Of Theorems 11.7 and I 11.8 of (6]) For all T 1, (81)sSEST IR. (M))sesT [-Y,Y] such that || S,
TX²
A (Y
for A {r. f}
s 1 Ad
AeT (GT(O))
where rr rank and Xry is its smallest positive eigenvalue, ct and c 1.
See proof in Appendix A This bound suggests that to obtain log(T) bound, À should not be chosen larger than about log (T)/T. due the second term, this is the stringent regularization limitation.
Choosing = 1/ yields a first order regret of 2 for the forward algorithm and 8dY² for ridge regression (with clipping and prior knowledge of Y), which is at best twice the first order term from the lower bound. This suggests the presence of an optimality gap. Strikingly, Gaillard et al. [I]] show that a non-regularized version of the forward algorithm achieves the optimal first order of dY². However, it also suffers from an important weakness: Indeed, the (Y /-1)//An, / (Gr((G)))) term in Corollary 2.3.1 features. In fact, double uniformity over features and observations is still an open question (see (II)
uniformly bounded over feature sequences, but only on specific "well-behaved"
2.3 Limitations in the stochastic setting
Now that have recalled the main properties of the forward and ridge algorithms in the adversarial setup, we advocate for the need of a complementary analysis of the previous algorithms in the stochastic unbounded setting by unveiling some key limitations.
Too unconstrained The existing analysis being for a different setting, it naturally ignores crucial aspects of the stochastic setup. For instance, the quantity Y is uninformative and may be substantial. Let us look at how the term Y appears in the proofs Azoury & Warmuth [3. For ridge regression, the penultimate step prove Theorem 2.1 writes:
T Σ t=1
D min (Lr(0) - xll111k < #
(x) 0 vi)
x2 GT x2 < 4(Y
G. x
(4)
t=1
first
In adversarial setting, the "first term" cannot be controlled without assuming bounded predictions
lo. 9,-1 < Y", and doing so yields bound (z. f - -w)² < 4(Y a stochastic setup
however, we expect the term (r,T0r-) 0 y1)² to reduce and stabilize around (x 0. y1) owing to
the convergence properties of the estimate towards 0..
For the forward algorithm, the final step in the proof of Theorem 2.2 writes:
4 min (LT + 1110 S
a G
2t Gr 2141 (z 0i)
first
socond term
Then, the analysis uses that 1y:l < yz and dis- regards the negative contribution of the "second term". Illustrative example: Iet us analyze these terms in an practice: consider d 5, 0. E 1R. we sample 200 features uniformly in [0. 1 and Gaussian noises (a 0.1). Fig. F displays the instantaneous first regret term of both algorithms (with À 1) and the second regret term of the forward algorithm, averaged over 100 replicates. We remark that the first terms vanish quickly for ridge regression and are quite stable for the forward algorithm. On the other hand, they are essentially cancelled out by the second term.
NidglstTemm Forwardi stf erm Farward2ndTer
10a
Online regret terms
10a
101
10-1
1000
175
#Observations
Figure Online regret. y-axis is logarithmic.
5

---

Overall, the two strategies perform par on this example. This suggests that Theorems 2.1 and 2.2
can be misleading this stochastic setup: for ridge regression they introduce a conservative 4() " bound on (x, (0c-1- 0.))². while in practice we observe that this term decreases rapidly zero; for the forward algorithm, the bound ignores the effect of a negative term, which, as we see in Fig. is essential explain why this algorithm may outperform ridge regression.
Time dependence: In the stochastic setup. can be confusing to introduce Y because this hides significant dependence on time. Indeed, for the forward algorithm y 1 |ar] 0. + eel- Considering the tractable setting of Gaussian i.i.d noise with variance o², by classical Sudakov minoration from 20 deduce that there exists C such that:
VT 2 EY E
max Et ISIST
X 1101112 2Cg/2og(T) X110-112-
Since (Y appears in the previous performance bounds, this suggests that y actually increases the order of the regret bound log(T)² in this setting.
By focusing on the unbounded stochastic scenario, we hope in this paper to shed novel light on the practical performance of these strategies and better explain these phenomena.
3 High probability bounds
In this section, we analyze online ridge regression and the forward algorithm the stochastic setting. We present our results in terms of the following intuitive regret definition:
R L (f.).).
This regret directly compares the cumulative loss of the learner to the cumulative loss of the oracle knowing the true parameter 0.. This contrasts with the online-to- -othhhhhh conversion result that compares the loss the learner to the value of a batch regularized optimization problem. Since we are in stochastic setup, we further state results in high probability. More precisely, state Theorems 3.2 3.3 below holding with high probability uniformly over T, and not simply for each T. As a first step, prove that for T great enough, can choose this definition instead of Rr defined in Eq. [ without altering the bounds.
Theorem 3.1. (Regret equivalence) In the stochastic setting with sub- Gaussiann noise, for all 5 0 with probability at least 5, for all T >> 0, (xi)isesT E IRd such that || S (r()r()) >
LT(0.) min (r) (log(T)²).
BERd
in particular, it comes
R = R$ + (log(T)))
We detail the proof in Appendix B Theorem 3.1 justifies choosing Rr to provide first order guarantees. Indeed, in the following sections we prove high probability upper bounds of order Ollog())²).
3.1 Online ridge regression
We start our results by stating new high probability regret bound for online ridge regression.
Theorem 3.2. In the stochastic setting with sub-Gaussian noise, for all 8 > O with probability at least 1 8. for all T > O:
x2
(1+ Tx2 (1+TX2/Ad) /
14 < llgg(1 + X2/X)
log (1 (1+TX3/Xd) log
+ o(log(T))),
6/2
where X maxigisT ||
We refer to Appendix [for for the proof and for the full regret expression. This result interesting because the ranges of both predictions and observations do not appear, hence predictions clipping and/or a prior knowledge assumption on yz are not required. On the other hand, a factor 1/A appears in the worst case of a singular design matrix. This seems to be the price for no longer assuming bounded predictions. Another notable improvement is that this bound no longer involves \| terms. In particular, it is uniform over bounded sequences of observations.

---

Remark 2. (Regularization in ridge) Note that the bound holds with high probability, uniformly over T, and not only for each individual time horizon. In the proof of this result, 1 emerges from bounding (man(G(())) in the worst case. When the collected features ensure the design matrix ()) invertible, 1/x virtually disappears. We highlight this experimentally in Section 3.4
3.2
The forward algorithm
We now derive a high probability regret bound for the forward algorithm using similar techniques.
Theorem 3.3. Assuming sub-Gausiian noise, with probability at least for all T Z 0:
+1+ / + ()oog()))))
R4 2do log (1 + (x+XX2/Ad) log
5/2
where = maxi | and the (T))g(T)²) depends on (see Appendix D
Proof. (sketch) We refer to Appendix D for the full proof and outline here the main steps leading to this bound. First, the instantaneous regret writes F; = (f(-1) (0.) ((0--1 10-1--00 -6,) xx)²
20, - 0.) xt. To control the term involving the noise Et, we derive ad-hoc self-normalized tail inequalities in the same style of Theorem in (T. which are of independent interest. Such an
adaptation is required due to the forward algorithm. We then focus on controlling the first term. We construct confidence intervals for 0, and resort to standard technical tools.
Theorem. 3.3
exhibits better bound than Theorem. 3.2 In fact, the coefficient of the first order term for the forward algorithm only depends on the dimensionality and the noise variance, whilst for ridge regression, it also depends on the features' scale and on the regularization parameter X.
Remark 3. (Unrestrained regularization) Compared to existing results, this analysis lifts the "strin- gent regularization" that requires X = 1/T or data-dependent regularization (cf. (T6]) to obtain uniform bounds. Therefore, Theorems 3.2 and 3.3 are not a mere consequence of bounding y2 with high probability in previous deterministic theorems. For completeness, we also derive a high probability regret bound for a non-regularized version of the forward algorithm in Appendix this algorithm was proven to be asymptotically first order minimax optimal the adversarial bounded setting M.
3.3 Tightness of the bounds
Here we clarify the impact of a tighter confidence width for regularized least squares that was proved concurrently with the writing of this paper. First we state the result then discuss its implications.
Theorem 3.4. (Theorem I of Tirinzoni et al. (221) Let 8 E (0, 1), 2 3, and O, be regularized least-square estimator obtained using E [ni] samples collected using an arbitrary bandit strategy = (Te)21 Then,
3t E [n] -10, P
0. - 2 Ven. 2
where 6n,5 is of order OOlog(1/8 + d doo log
This has important implications for Theorem 3.1 Theorem 3.2 and Theorem 3.3 in short it re-scales
their regret upper-bounds from Rr O ((da) (T) to Rt = (do² log (T) log log(T)). The first order (do)² log(T)² in our results is the product of 1) d log T from the elliptical lemma, for bounding the sum of feature norms and 2) x² o (og(TT/6) the confidence ellipsoid width in the estimation of the regression parameter. It is the second term that is altered following the new result from Tirinzoni et al. [21]. These tighter confidence intervals change the upper bounds to O(do² log(T) log log(T)). The latter matches the popular lower bounds in excess risk literature (see e.g. Theorem in Mourtada (17) up to sub-logarithmic terms suggesting the optimality of the forward algorithm in the stochastic setting.
7

---

3.4 Experiment
provide experimental evidence supporting the fact that our novel high probability analysis better reflects the influence of regularization than results its adversarial counterpart.
0.001
0.001
0. 14476667730108895
10a
144476482730088365
10
10
Online Regret
Online Regret
10
104
10a
10a
10a
10-4
10
10-²
100
10-
10a
# Observvttoos
# #Observations
(a) Ridge regression
(b) The forward algorithm
Figure 2: Online regret's (Instantaneous loss difference) dependence on A. All axes are logarithmic. Lines are averages over 100 repetitions and shaded areas represent one standard deviation.
In Figures 2a and 2b we observe the effect of regularization on the performance of ridge and forward regressions in 5-dimensional regression setting, vary À E {1/TT, 1/ log(""), , 1, 10). sample zero mean Gaussian noise with a 0.1 and draw features uniformly from the unit ball. The results clearly highlight the robustness of the forward algorithm to X, contrarily to ridge. In particular, for ridge regression, we observe the exact dependence on described by Theorem 3.2 in the first rounds of learning; explained in Remark once the collected features are enough for the design matrix (0) to become non-singular, the 1/A virtually disappears from the first order regret bound and is replaced by the smallest eigenvalue of GO),, making the regret significantly more stable.
Application: linear bandits
The proposed analysis forward regression in the stochastic setting suggests that using it could be useful for revisiting several popular setups that include linear function approximation. We apply this change for stochastic linear bandits hereafter and derive the novel regret bound obtained when using forward regression instead of the standard ridge regression.
Consider the setting of stochastic linear bandits, where at round the reward an action dy (from the action space X' C IRd) is yt (It, (z), + where 0, E Rd is an unknown parameter and is, conditionally on the past, a --sub-Gaussian noise. upper bound on the unknown parameter's norm is provided: ||0,112 I S. The (pscudo) regret in this setting defined:
T
T
T
RT = Σ (at 0.)
Σ (1x, 0.) = Σ f
It, xx, 0m),
where x; arg m (x, 0.). Traditionally, the following additional assumption is made. Assumption 1. for all v, X (x,,0.) [-1,1]]
The "optimism in the face of uncertainty linear bandit" (OFUL) algorithm was introduced in M. OFUL resorts to ridge regression, constructs a confidence ellipsoid for the parameter estimate, and chooses the action that maximizes the upper-confidence bound the reward. Under Assumption I prove that the cumulative regret of OFUL satisfics, for 8 > O with probability at least 1
VT 0 RE & TTllog( + TX2/d) +xx3))
X1/2 + a / log(1/8) d (1 + TX2/(Ad)
where X maxigisT |
8

---

Forward variant [Algorithm33 In second phase, we propose the variant OFUL" in which we replace ridge regression by the forward algorithm. What this means that the parameter estimate is function of actions:
of (z)
arg min
Σ (v. (x,, 1101 + (),
0E
This fits perfectly because the new action be chosen. Implementation details are in Algorithm
Algorithm 3: OFUL* algorithm
Given 6, 0
for t = I....,Tuu do
Zt = arg max (2, (x() + | (v²+ | + + 2 (1+xX7())/Adpu12
where Xx(x) = max ||||||||| 2|2, maxigast- |[ GL-1, = G1-1 xx and
(z)) arg mingeRd Σ (ye - (z,, + ||012 (z,0)²
play Ha and observe yt-
end
Note that OFUL only requires an upper bound on ||0_ ||2- We prove that OFUL enjoys the same regret bound OFUL and doesn't 't require Assumption [ In stark contrast, we cannot show similar bound for standard OFUL without said assumption, it actually suffers a X-dependent scaling factor in this case.
Theorem 4.1. (Bandits with unbounded rewards) Without Assumption 7 for all 5 > 0, OFUL" achieves with probability at least for all T 1,
X2
RT S 4 log(1
(idlog(A+TX//// X²
+ TX
also, we show that for all 8 > 0, OFUL! achieves with probability at least 6, for all T 2 1:
R4. S Tdloo(( + dX2/d) (A + X)S a 2loggl///))) + dlog(1 + TX2/(xd)
Remark 4. we can drop the dependence on X and S by bounding the second term in the index of OFUL and OFUL! (see line 285) by X and then dropping this -constant- term at the expense of looser index. Therefore, knowing the bounds a and is not crucial. Furthermore, while we choose to adopt the pseudo-regret definition like in [T), we could also derive similar bounds for the regret involving rewards Yt (It, (.) instead of their expected value, (yr) 121 are unbounded.
Experiment We provide experimental evi- dence that the OFUL" variant improves OFUL for linear bandits; we find that it is generally as good as the standard OFUL", and in some cases it can prove to be significantly more ro- bust to aberrant regularization parameters. We consider 100-dimensional linear bandit with
OTUL OFUL
10*
Cumulaatie Bandit regret
102F
10*
10 arms, the parameter vector is drawn from
20a
the unit ball, actions are such that ||x,|] || < 200. Noise e E (O, 10-1), A 10-5 8 = 10-3 In Fig. lines are average regret over 100 repeti- tions and shaded areas cover the region between dashed-lines that are the first and third quartiles. We observe that -as predicted by Theorem 4.1 OFUL particularly robust and choosing A= 1/T incurs substantial regret OFUL. Because of this phenomena, and for the same observations in the online stochastic regression setting, we advocate for the use the forward algorithm instead of ridge regression whenever possible, to take advantage of its increased robustness to A.
10a
80000
round
Figure 3: Cumulative regret. y-axis is logarithmic.

---

Remark 5. Regarding the choice X = 1/T: we use this specific regularization for two reasons: 1) to demonstrate the benefits of our stochastic analysis, since previous deterministic bounds suggest this X is best, 2) to showcase the increased robustness of OFUIJ compared to OFUL. In fact, more often than not, OFUL. performs as good as OFUL, except when is small or X large.
Conclusion
We revisited the analysis of online linear regression algorithms in the setup of stochastic, possibly unbounded observations. We proved high probability regret bounds for three popular online regression algorithms (ef. Theorems 3.2 3.3 and E. These bounds provide novel understanding of online regression. particular, Theorem seems to be the first regret bound for ridge regression that does not require bounded predictions or prior knowledge of bound on observations. Our novel bounds seem to correctly capture the nature of dependence with regularization, as indicated by Fig. 2 Moreover, new results from Tirinzoni et al. [21] can be incorporated in the proof mechanism to bring the high probability upper bounds to O log(T) log ITg( which matches the optimal achievable bounds from the excess risk literature up to sub-logarithmic factors.
Furthermore, we argue that replacing ridge regression by the forward algorithm whenever possible in algorithms that require linear approximations can be beneficial, we depict this in case study involving linear bandits: First from a theoretical standpoint our results show that the OFUL algorithm enjoys the classic first order regret bound while dropping Assumption [] Second, we find that empirically, implementing OFUL with the forward algorithm makes the algorithm significantly more robust to extreme values of regularization, which is of practical interest.
More broadly, we believe that the improvement resulting from replacing ridge regression with the forward algorithm could be extended several other settings: For instance, we also provide similar analysis for non-stationary linear bandits in Appendix F Graph bandits are of interest as well: they consider linear function approximations using ridge regression, and make Assumption I for example Theorem of [23]; Meta-learning with linear bandits can also be enhanced using forward regression: see for example Lemma 1 and consequent results in [5]
Societal impact While our findings are purely theoretical, they can be taken advantage of for activities with negative societal impact. For instance, bandit algorithms are mainly used nowadays for advertising which can sometimes be linked with invasion of privacy. We insist however that linear regression in its generality is a very valuable technique, its ubiquitous is scientific domains, and improving our understanding of it even slightly is beneficial.
Acknowledgments and Disclosure of Funding
This work has been supported by the French Ministry of Higher Education and Research, Inria, Scool, the French Agence Nationale de la Recherche (ANR) under grant ANR-16-CEA0-000 (the BADASS project), the MEL,, the I-Site ULNE regarding project R-PILOTE-1 11TE-19-004-APPRENT V. Perchet acknowledges support from the French National Research Agency (ANR) under grant number
as well the support grant, as well from the grant "Investissements d' "'Aeenir" (LabEx Ecodec/ANR- 1IR-11-LAB,, 1--ABX-00477) R. Ouhamma also awknowledges support from Ecole polytechnique under the AMX funding.
References
[1] Abbasi-Yadkon Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances Neural Information Processing Systems, pp. 2312-2320, 2011.
[2] Abbasi-Yadkori, Y., Pal, D., and Szepesvari, C. Online-to-confidence-stt conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1-9. PMLR, 2012.
[3] Azoury, K. S. and Warmuth, M. K. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning. 43(3):211-22) 1-26, 2001
[4] Bartlett, I.., Koolen, W. M., Malek, A., Takimoto, E., and Warmuth, M. Minimax fixed-design linear regression. In Conference on Learning Theory, pp. 226-239, 2015.
10

---

[5] Cella, L., Lazaric, A., and Pontil, M. Meta-lcarning with stochastic linear bandits. In Interna- tional Conference on Machine Learning, Pp. 1360-1370. PMLR, 2020.
[6] Cesa-Bianchi, and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
[7] Cesa-Bianchi, N., Long, P. M., and Warmuth, M. K. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Networks, 7(3):604-619, 1996.
[8] Cortes, C. and Mohri, M. On transductive regression. In Advances in Neural Information Processing Systems, pp. 305-312, 2007.
[9] Foster, D. P. Prediction the worst case. The Annals of Statistics, pp. 1084-1090, 1991.
[10] Freedman, D. A. On tail probabilities for martingales. the Annals of Probability, pp. 100-118, 1975.
[11] Gaillard, P., Gerchinovitz, S., Huard, M., and Stoltz, G. Uniform regret bounds over Rd for the sequential linear regression problem with the square loss. In Algorithmic Learning Theory, pp. 404 432, 2019.
[12] Kamath, G. Bounds on the expectation of the maximum of samples from a gaussian. URL http://www. gautamkamath. com/writiingsgaassien max. pdf. 2015.
[13] Kivinen, J. and Warmuth, M. K. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(1):1 1997.
[14] Littlestone, N., Long, M., and Warmuth, M. K. On-line learning of linear functions. In Proceedings of the twenty-third annual ACM symposium Theory of computing, pp. 465-475, 1991.
[15] Maillard, O.-A. Self-normalization techniques for streaming confident regression. 2016.
[16] Malek, A. and Bartlett, P. Horizon-indepeendet minimax linear regression. Advances in Neural Information Processing Systems, pp. 5259-5268, 2018.
[17] Mourtada, J. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. arXiv preprint arXiv:1912.1075: 2019.
[18] Orabona, F., Cesa- Bianchi, N., and Gentile, C. Beyond logarithmic bounds online learning. In Artificial intelligence and statistics, pp. 823-831. PMLR, 2012.
[19] Russac, Y., Vernade, C., and Cappé, O. Weighted linear bandits for non-stationary environments. arXiv preprint arXiv: 2019.
[20] Sudakov, V. N. Gaussian measures, cauchy measures and s-entropy. In Soviet Math. Dokl, volume 10, pp. 310-313, 1969.
[21] Tirinzoni, A.. Pirotta, M., Restelli, M.. and Lazaric, A. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. arXiv preprint arXiv:2010.122 /2247, 2020.
[22] Tripuraneni, N. and Mackey, L. Single point transductive prediction. arXiv, pp. arXiv-1908. 2019.
[23] Valko, M., Munos, R., Kveton, B., and Koeák, T. Spectral bandits for smooth graph functions.
In International Conference Machine Learning, pp. 46-54. PMLR, 2014.
[24] Vovk, V. Competitive on-line statistics. International Statistical Review, 69(2):213-244 2001.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See $
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either in the supplemental material or as a URL)? [Yes] See Appendix
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they
were chosen)? [Yes] See the description of each experiment
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "t6ucpNiI01", "reviewer": "Reviewer_npqJ", "summary": "This submission provides high-probability bounds for the Ridge and the forward algorithm in the setting of stochastic online linear regression. The advantage of the proposed bounds over previous results established for the adversary setting is that they do not scale with $Y$, the range of the observations. The authors further show that the bound of the forward algorithm has better scaling with the range of the features $X$ and the regularization coefficient $\\\\lambda$. The extension of the forward algorithm to stochastic linear bandit is also studied. The proposed algorithm enjoys better scaling on $X$ and $\\lambda$ than the classical OFUL method with Ridge.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "==Novelty==\nThis paper provides new results for the online linear regression in the stochastic setting, which is free from the scaling of the observation $Y$. This advantage roots in using the self-normalized concentration to analyze the linear regression in the stochastic setting, which has been primarily used in a closely related topic: stochastic linear bandit (Abbasi-Yadkori et al., 2011). So, I do not find the results very surprising, and the technical contribution could be limited. It would be better if the authors could highlight the challenge to obtain the bounds or some new insights.\n\n==Quality&Significance==\nThe theorems seem correct, but I do not check the proofs in detail. The theorems in the paper support authors' claim in most cases. But I still have some questions and concerns.\n\n1) It seems the adversary bound of the forward algorithm (Corollary 2.3.1) implies an $O((\\\\log T)^2)$ bound without the scaling issue of $Y$ when the range of $x_t$ and $\\\\theta^*$ are bounded. One can quickly bound the $\\\\max{\\vert y_t\\vert}$ by $O(\\\\sqrt{\\\\log T})$ with high probability, since $\\\\vert y_t\\\\vert\\\\leq XS + \\\\vert\\\\epsilon_t\\\\vert$ and $\\\\max\\\\vert\\epsilon_t\\\\vert$ grows in the rate of $O(\\\\sqrt{\\\\log T})$. So, the proposed bound might not have very significant advantage over the previous bounds in such a case.\n\n2) I am unsure whether the scaling of the regularization coefficient $\\\\lambda$ matters in the SLB problem. Choosing $\\\\lambda$ as a constant seems good enough to obtain a $O(\\\\sqrt{dT}\\\\log T)$ bound for both Ridge and the forward algorithm. Meanwhile, the choice of $\\\\lambda = 1/T$ in the experiment is unfair for the Ridge algorithm since it would lead to a linear regret as suggested by the bound. So, I think it would be better to compare the algorithms with different $\\\\lambda$ (especially when setting $\\\\lambda$ as a constant).\n\n==Clarify==\nThe paper is well-written and provides background on online linear regression in the adversary setting, preparing the reader well to understand their main arguments. But, I am not very sure is it good to use the word \"unbounded rewards\" for Theorem 4.1. The theorem still requires the upper bound of the range $X$ and the underlying models $S$. Combining the two upper bounds, one can show that Assumption 1 holds with certain scaling. So, the condition of Theorem 4.1 resembles the previous results in  (Abbasi-Yadkori et al., 2011).\n\nMinor points:\nline 306: \"-as\" -->\"as\"\n\nThe authors response has partially address my concern about the setting of $\\lambda$. However, I still find that the paper needs a major revision to better discuss its motivation and contributions. So, I would like to keep my score.\n\n====update post-rebuttal=====\n\nThe authors' response has partially addressed my concern about the setting of $\\lambda$. However, I still find that the paper needs a major revision to discuss its motivation and contributions better. So, I would like to keep my score.\n\nMy original concern is that, for the stochastic setting, there is no need to use $\\lambda = 1/T$ since a constant $\\lambda$ is good enough to achieve the $O((\\log T)^2)$ bound. In the rebuttal, I have just realized that the goal of this paper is to achieve the best-of-both-worlds for both stochastic and adversarial settings. The forward algorithm can achieve the goal with $\\lambda = 1/T$ while the ridge algorithm would fail. I have to admit it is interesting to show the advantage of the forward algorithm in such a scenario. But, I think the author should provide a better discussion to highlight the motivation and contributions. In the current version, even the title \"Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge\" is somewhat misleading, since if we have known that the environments are stochastic, ridge algorithm with constant $\\lambda$ seems good enough. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main review above.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6 hours"}, "extra_text": {}}, {"review_id": "eIMx_LiZ2LB", "reviewer": "Reviewer_jxuz", "summary": "This paper considers the classical online linear regression setting. It revisits the analysis of two important algorithms, ridge regression and the forward algorithm (also known as the Vovk Azoury Warmuth forecaster). First, the adversarial analysis is revisited to argue why and where this analysis falls short in covering the stochastic setting in a satisfactory manner. Then, the authors provide novel high-probability bounds for both algorithms, a lower bound, and an experiment showcasing the performance of both algorithms for several regularization parameters. Finally, the paper contains an application of the new analysis in stochastic linear bandits. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The new high-probability bounds reveal the interesting phenomenon that, contrary to the forward algorithm, for small sample sizes the ridge algorithm is sensitive to the tuning of the regularization. This behavior appears to be confirmed by the experiment in section 4. However, there are some thing unclear to me. First, in Figure 2, the y-label states that it is the regret, but it does not appear to increase over time, contrary to what I would expect based on the theoretical results. Second, for $\\lambda = 0.001$ there is an unexplained bump in the regret of the forward algorithm, which appears to contradict the claims of robustness of the forward algorithm and I would like to know if the authors have an explanation for this bump. \n\nFrom a technical point of view the main novelty appears to be the use of the confidence ellipsoid method of [1] to bound the difference between the true parameters and the parameters of the algorithm.\n\nThe writing is relatively clear in most places, but I do want to urge the authors to include a proof sketch of at least one of the high-probability bounds. While the limitations of the adversarial analysis are clearly written down, I can not guess from the main text alone how one would prove the high-probability bounds. \n\nThe applications of the new analysis to stochastic linear bandits is quite nice. I like the fact that the boundedness assumption can be dropped, which I imagine is helpful to practitioners as choosing an appropriate bound can be quite bothersome. \n\nI find the significance of these results difficult to judge. On one hand, the paper only contains no new algorithm but only a new analysis of classical algorithms. On the other hand, the analysis reveals interesting behavior of these algorithms which I would not have predicted based on the existing adversarial analysis alone. Furthermore, the application reveals that there is also a practical relevance of the new analysis, which could also mean the new analysis could be relevant in other applications of the ridge and forward algorithm.  \n\nAs a final remark, the results of this paper suggest that there is a $O(d)$ gap between the upper and lower bounds. In lines 247 to 252 it is argued that the additional factor $d$ is due to the time-uniformity of the upper bounds. Intuitively this does not makes sense to me and I want to ask the authors for some intuition behind this. Furthermore, the discussion in lines 247 to 252 seems to indicate that if we only want to provide results for some fixed $T$ the dependence on $d$ would improve from $d^2$ to $d$, is this true? \n\nminor comments\n- line 320: First --> first\n- there are some unexpected bold symbols in Theorem 4.1 and equation (5)\n- the Forward2ndTerm in Figure 1 has an unexpected drop off after 200 observations.\n- the caption of Figure 1 should be improved as I do not think the plot shows the online regret. \n- to improve the readability of the plots different line types would help\n\n\n----- Post-rebuttal -----\nThe authors have adequately addressed some of my concerns. However, to address the concerns of the other reviewers I think that a major revision of this paper is required and therefore I will not raise my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "dSbItBzr57x", "reviewer": "Reviewer_FknY", "summary": "This paper proposes a new analysis result on stochastic online ridge regression and its forward version. As an application, the authors propose a new linear bandit algorithm with an improved regret bound (by dropping one common assumption) and show its empirical superiority over existing algorithms. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[main comments]\n\noriginality: 2/5 -- the novelty I found is the lower bound of order log(T)^2 and the empirical validation that an obvious application of VAW to bandits work well.\nquality: 2/5 -- the discussion on existing regret bounds could've been done more carefully and comprehensively (see my comments below)\nclarity: 3/5 -- within the scope of the paper, things are reasonably clear, but Theorem 3.2 does not seem complete (see my comment below)\nsignificance: 2/5 -- besides the lower bound, I was not able to confirm its significance yet.\n\nOverall, I think this paper needs some more work on clarifying their claims and put things in the right context. The main issue I have is that \"stringent regularization limitation\" seems like a madeup problem and the contribution for the linear bandit w.r.t. the theoretical bound is unclear to me, as I describe below. I am willing to raise the score according to the author response.\n\nFirst, I am not sure about the stringent regularization limitation (L144). The standard analysis of the regret bound of VAW gives us \n   Y^2 d log(1 + T) + lambda * \\|\\theta^*\\|^2.\n(see Sec 7.10 of Orabona'19 -- see below for the full reference) \nUsing Y \\lessapprox \\max_t  (x_t^\\top \\|\\theta^*\\|)^2 + log(T) with high probability, the leading term becomes (X\\|\\theta^*\\|) d log(T)^2. Now, this is a factor d better than what was proposed, at the price of \\|\\theta^*\\|^2. Note that the term lambda * \\|\\theta^*\\|^2 is actually in Theorem 3.2 as well -- it is just ignored since it is o(log(T)^2). So, I am really not sure about the actual improvement.\n\nAlso, staring at the regret bound of VAW gives us that the best \\lambda is something like 1/\\|\\theta^*\\|^2, so it does not have to be dependent on $T$. This is why I think the 'stringent regularization limitation' is a madeup problem. I mean, the dependence on the norm of $\\theta^*$ can be considered as stringent regularization limitation, but then the author's new bound also has it, so I don't understand the main point. \n\nTheorem 3.2 is not so convincing.Reading its proof (Section C): I don't see what reasoning was used to conclude that, at L499, \"Eq 11 is a of order ~ O(log(T)^{3/2})\". theta_{t-1} is clearly a random variable, and with low probability, it can blow up very large. I believe a more proper analysis must be done. Please share with us how the authors will address this.\n\nSec 2.3: There is an important discussion that is missing -- Ridge regression enjoys a small loss bound, so its actual regret must be smaller than the standard ones imply; see ``Beyond Logarithmic Bounds in Online Learning'' by Orabona, Cesa-Bianchi, and Gentile. One should translate this into the squared regression loss directly (rather than relying on the exp-concavity) to get a tighter bound (see Sec 7.9 of Orabona'19).\n\nFinally, I am not sure if the linear bandit version makes any advancement from prior work. The book LS'20 has an exercise that lifts up the assumption that \\langle x_t, \\theta_* \\rangle \\in [-1,1]; see the note between Exercise 19.3 and 19.4. Note that the arm set is fixed, so the learner already knows a bound $X$ s.t. $\\max_t \\|x_t\\|\\le X$, so there is not much exciting thing going on about the uniformity over features.\n\n[minor comments and questions]\n\n - p3:84-86: I am not sure if this is a 'real' problem of [10]. Consider that the algorithm always work within the space spaned by x_t so far (say that is d' dimensional), and the same analysis techniques are invoked for dimension d' < d. Would the same theorem statement not work?\n - p4:119: How is Y here defined? Is this a typo of Y^r or something else that was defined in p3:72?\n - Lemma B.2.: TX^2/\\lambda_min(G_{T_0})d => I would clarify it by adding parenthesis regarding (TX^2/\\lambda_min(G_{T_0}))d vs TX^2/(\\lambda_min(G_{T_0})d)\n - Lemma C.2.: wasn't this proved already in Corollary 8 of ``Online-to-Confidence-Set Conversions and Application to Sparse Stochastic Bandits'' by Abbasi-Yadkori, Pal, Szepesvari? I would add a reference.\n - L217: \"no longer involves \\lambda \\|\\theta\\|^2\" => this is misleading; the bound actually has \\lambda \\|\\theta\\|^2 but it is just a lower order term so omitted. There is an actual difference between \"not invovling\" vs \"invoving in a lower order term\".\n - Figure 2: it should be online 'Regret / T', because it is decreasing?\n\n[references]\n\n[Orabona'19] Orabona, a modern introduction to online learning, arxiv, 2019.\n[LS'20] Lattimore and Szepesvari, bandit algorithms, 2020.\n\n----\n\n(after rebuttal)\nI agree that Eq (12) and Lemma C.1 imply that the sum becomes $\\log^2(T)$. Thanks for the explanation and I have raised the score from 4 to 5. It is more interesting than I have initially thought.\n\nOverall, there are interesting pieces. However, to appreciate it, I think the paper needs nontrivial amount of modification. It seems there are lots of discussions that should/can be added, which will clarify the authors' contribution. For example, the fact that we do not want to tune \\lambda = 1/\\|\\theta\\|^2 is that we want to be parameter-free. I recommend that the authors clear up these and resubmit to other conferences.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed those adequately.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aoa2ANE5QzL", "reviewer": "Reviewer_um9E", "summary": "The paper offers a new analysis of the forward algorithm in the setting of stochastic online linear regression. Traditional analysis of this method under adversarial setting suffers from assumptions of boundedness of the output variable. These assumptions are not satisfied in the stochastic setting. The authors consider the case where there exists an unknown true parameter $\\theta$ such that y = \\theta^{T}x + \\eta, where the noise term $\\eta$ is sub-gaussian. They give explicit bounds on regret (in expectation and high probability bounds) and show its application in the specific problem of Linear Bandits.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is its refined analysis of the Forward Algorithm for an alternate setting and in supporting the assertion through experiments. It is very clear to understand and does not claim anything superficial. The work seems to be original.\nAs such there are no new algorithmic techniques or proof techniques that catch my attention or that I find novel. The paper’s significance is hard to estimate, but at present, I find it to be a moderate increment over our understanding of the Forward Algorithm. I am of the opinion that this paper is good, but may not reach the acceptance level of this conference.   1. Apart from Linear Bandits, are there other possible use cases where FA trumps over Ridge?\n2. Is it a correct assertion to make that for sub-gaussian noise, FA will always be better (as just as good) as Ridge?\n\n\nAfter Rebuttal: I would express my gratitude to the authors for their clarifications. I have read the author rebuttal and the other reviews. I tend to keep my original score, since I think that this paper falls marginally short of this conference's acceptance threshold.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have done a great job in addressing the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "None to my knowledge.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper concerns online linear regression algorithm -- ridge regression and the Forward algorithm a.k.a. Vovk-Azoury-Warmuth forecaster -- in the stochastic setting. Both algorithms work in the adversarial setting but require the range of labels to be bounded (additionally, RR needs to know the range in order to clip its predictions). The authors consider a stochastic well-specified model $y = \langle \theta^*,x \rangle + \xi$, with the noise $\xi$ being sub-gaussian. They show that RR and Forward work in this setting (high-probability regret bound) even though labels are potentially unbounded, with a better scaling of the bound with respect to the regularization and the range of inputs. It is also shown that RR is more sensitive than Forward to the right choice of the regularization for small sample sizes. Applications of their results to stochastic linear bandits are given (better regret).

Overall, the reviewers liked the paper and found these results to be novel and interesting. However, they also pointed at two issues, which made most of them to evaluate the paper below the threshold bar:
1. Limited significance. The paper does not introduce any new algorithms, and the proof techniques applied to RR and Forward were not found to be novel or surprising. Two of the reviewers pointed out that due to sub-gaussianity of the noise, the labels are w.h.p. bounded in the range $O(\sqrt{\log T})$ (for bounded comparator), so the proposed bound might not have significant advantage over the existing one. Furthermore the upper bounds have $O(d^2)$ dependence on the dimension as opposed to $O(d)$ for the adversarial case (the authors claim, though, that they can get down to $O(d)$ by an improved analysis in the revision).
2. There were problems with presentation reported, and suggestions that the paper should be improved and more discussion should be added (two of the reviewers were confused about the motivation and the actual contribution, especially around the discussion on tuning the regularization).

This is why I think the paper is not yet ready to be publish. However, I encourage the authors to resubmit their paper, taking into account the reviewers' remarks, in particular: to improve the presentation, extend the discussion of the main results, discuss the missing references to past work, and provide clear motivation around the scaling of the regularization coefficient.

Decision: Accept (Poster)