Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
Authors: Reda Ouhamma
Odalric-Ambrym Maillard
Vianney Perchet
Venue: NeurIPS 2021 Poster (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) - -t= (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 ER 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 T 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 (u 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, (11)SSEST IR. (M))sesT [-Y,Y] such that || S,
TX²
A (Y
for A {r. f}
5 1 Ad
AeT (GT(O))
where rr rank and Xry 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. (Л6]) 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
144476482730188365
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/T,, 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 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,, +1) 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-CE40-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-Yadkond 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": "iz0iXqLpHy9", "reviewer": "Reviewer_WQsZ", "summary": "The paper studies the well-known ridge and forward regression in online linear regression problems with stochastic feedback.  A high probability bound for both algorithms is shown for Gaussian noise variables, respectively. Furthermore, the new insights are applied to improve theoretical guarantees of algorithms for stochastic linear bandits (stationary and non-stationary in the appendix) showing a significant difference regarding the role of the regularization parameter and the range of the context vectors in the regret bounds between the two approaches. The theoretical findings are investigated in an experimental study.", "questions": "", "limitations": "", "rating": 7, "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": "# Significance\n\nThe ridge and forward regression are well-known approaches in the literature, so the paper's main contribution of giving more insights into the understanding of their theoretical properties is of special interest. Especially, due to their numerous fields of application such as linear bandits, which are considered in the paper as well. \n\n# Strengths\n\nThe main strength of the paper is that it shows theoretically that forward regression approaches enjoy better regret upper bounds than approaches based on ridge regression. This is indeed interesting from a theoretical point of view. I have also checked the proofs to a large extent and they seem to be sound, as mostly standard proof techniques are used. However, there are some soft spots which the authors hopefully can clarify in their response (see questions below).\n\n# Weaknesses\n\nIn my opinion the major weakness of the paper is that the provided experimental studies are not overall convincing to confirm the theoretical contribution:\n\n1. In Figure 1 it is hard to tell what the difference of the first and the second term of the forward will be. However, the difference is exactly the interesting term, as it corresponds to the regret upper bound of forward regression.\n2. Although Figure 2 demonstrates the dependence of the regularization parameter for both algorithms, it is once again hard to compare the regret of the two algorithms, as the y-axes are different.\n3. Figure 3 considers only one choice for the regularization parameter, namely \\lambda=1/T, but regarding Theorem 4.1 (and also Figure 2) why should one use this choice for \\lambda for OFUL with ridge-regression? In Figure 2 for instance we see that using a \\lambda of 1 is much better and this is also what would be expected regarding the result in Theorem 4.1.\n \n\n# Justification of the score\n\nAs I am really sympathizing with the content of the paper and as I believe that modifying the experiments to illustrate the advantage of forward regression over ridge regression should be quite manageable during the rebuttal phase, I am currently leaning towards accepting the paper.\nHowever, the authors should address the questions below.\n\n# Suggestions to improve readability\n\n1. It would be a good idea to include the difference of the first and the second term coming from the forward regression in the plot of Figure 1 as well, so that it can be better compared with the first term of the ridge regression. By the way, it is a bit odd to call the only term in the bound of ridge-regression ''first term'', as there is only one term.\n2. The proofs in the appendix can be made more compact, as all the ''Tail inequality'' Lemmas are shown in a similar way and the \"Technical inequalities'' as well. Thus, one could introduce a general lemma covering all the variants as special cases. In this way, the proofs of the main theorems could be stated in a clearer way without constantly interposing lemmas.\n\n**Some questions:**\n\n1. Is it possible to consider the supremum over all feature vectors having Euclidean norm bounded by X in Theorem 2.3, such that X also appears in the \\log(T) term? In this way, the result is more comparable to Theorem 2.1 and 2.2.\n2. How does the cumulative regret of OFUL for both variants (ridge and forward) vary with the choice of the regularization parameter?\n3. Somehow the argumentation to infer the last inequality in the proof of Lemma C.1 seems to be insufficient:  The ratio of the log-terms is smaller than 1, while the squared weighted norms of the context vectors are all smaller than X^2/\\lambda. Thus, the right-hand side seems to be larger than the left-hand side or am I missing something? In particular, I do not see how the concavity of the logarithm comes into play here. This point needs to be clarified as it is a crucial inequality affecting all main results related to the ridge regression. \n\n**Minor things**\n\n0. There are some odd formulations (regarding language). Here are some examples: \nLine 69 “In contrast with …” -> In contrast to\nLine 120 “… to this next result.” -> the next result\nLine 198 “… in high probability” -> holding with high probability\n\n1. The noise term in line 47 needs a time-index.\n2. Line 145: the order of both regret upper bounds depend logarithmically on the time horizon T. Similarly, in line 149.\n3. Line 283: The sum should go from 1 to t-1.\n4. In the proof section G the time horizon is denoted by n instead of T.\n5. In line 459 you would get instead of a 1 rather \\lambda/\\lambda_{min}(G_{T_0}}. Also, on the left-hand side it should be rather the squared weighted norm of the context vectors instead of the logarithm.\n\n# Post Rebuttal\n\nAfter reading the other reviews as well as the authors' response,  I will increase my score to 7, as basically all my concerns have been addressed.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this paper", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Zj1PDHY4RUt", "reviewer": "Reviewer_XAWf", "summary": "This paper revisits the analysis of online linear regression algorithms in the setup of stochastic and possibly unbounded observations. In theory, high probability regret bounds for online ridge regression and online forward algorithm are developed, without assuming bounded predictors or bounded observations. As a by-product, the authors apply the forward algorithm to the linear bandit problem and show promising results in both theoretical regret bound and the numerical performance when compared to the traditional ridge-regression based OFUL algorithm. Importantly, the idea of replacing ridge regression by the forward algorithm  is very general and could be extended to several other settings. Overall, this paper is very well written and is easy to follow. \n", "questions": "", "limitations": "", "rating": 7, "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": "I enjoy reading this paper and think it makes an important contribution to stochastic online learning. My comments for clarification are as follows.\n\n1. In Figure 3, the comparison between OFUL and OFUL$^{f}$, $\\lambda$ was fixed at $10^{-5}$. It could be possible that OFUL performs bad mainly due to this bad choice of $\\lambda$. Is that possible to explore different $\\lambda's$ for OFUL to see if its performance could be improved or comparable to OFUL$^{f}$?\n\n2. In Corollary 3.3.1, the lower bound is derived for $T\\rightarrow \\infty$, instead of uniform over time in the upper bound of Theorem 3.2 - 3.3. Is that possible to close the gap by deriving the lower bound under the uniform over time setting? It would be helpful to add some discussion if there is any technical difficulty.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "BhipsoB60tK", "reviewer": "Reviewer_4n5Q", "summary": "The paper analyse the performance of on-line ridge regression and Vovk-Azoury-Warmuth predictor (aka aggregating algorithm regression) referred to as forward regression (due to an optimisation formula involving the regression prediction) under stochastic settings.\n\nThe analysis assumes the model y_t = x'_ t\\theta_* + \\epsilon_t, where the error \\epsilon_t has a sub-Gaussian distribution (i.e., is Gaussian or has some other light-tailed distribution). The paper aims to get asymptotic results in the following sense: some inequality with o(T) should hold with probability 1-\\delta (presumably, o depends on \\delta).\n\nIt is shown that competing against the true \\theta_* under these settings is (nearly) the same as competing against the retrospectively best predictor and hence the results are related to the competitive regression framework.\n\nIn the theory of ridge regression there is a well-known regret upper bound (Theorem 2.1 in the paper) that is not matched by lower bounds. The authors cite a recent lower bound getting a much better multiplicative coefficient.\n\nThe paper shows that under the given stochastic setup both on-line ridge regression and Vovk-Azoury-Warmuth have upper bounds that match (to some extent) a lower bound.", "questions": "", "limitations": "", "rating": 8, "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": "I think this is a very interesting observation on properties of on-line regression and advances a well-researched area. I would say this motivates a conclusion that RR and Vovk-Azoury-Warmuth are not that different _most of the time_.\n\nI would like to point out an older lower bound by Vovk (Competitive on-line statistics, 2001). It is matched by Vovk-Azoury-Warmuth, but not ridge regression.\n\nI have a question to the authors. The match between Theorem 3.2 and Corollary 3.3.1 seem to be true only for large \\lambda when\n\n\\frac{X^2}{\\lambda\\log(1+X^2/\\lambda)} \\approx 1.\n\nWhat about small lambdas?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "22P68L8EDvl", "reviewer": "Reviewer_YH9r", "summary": "The authors consider the problem of online linear regression in the stochastic setting. The key contribution is the introduction of a new algorithm called the forward algorithm that enables the authors to remove boundedness assumptions on the observations and predictions. The algorithm simply uses the next observation to update the parameter vector and predicts using the updated parameter vector. High prob bounds are established for both the ridge and forward regression algorithms. Lower bounds are established assuming gaussian noise. The ideas are then used to design algorithms for linear bandit problems. The bandit algorithm achieves the same regret guarantee as the OFUL algorithm, but w/o the need for some assumptions that are made for the OFUL algorithm.\n\nThe paper is fairly well written and was easy to follow.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 paper is fairly solid and the proposed algorithm is nice and simple. Given that online linear regression is an important building block for several online algorithms, this paper is a nice contribution. I did not go through all the proofs.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Look above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider ridge regression and the "forward" algorithm for l2-penalized regression in the stochastic setting.  High-probability  regret bounds were given.  A significant feature of this setting over the adversarial setting was the possibility to remove the usual boundless assumption on the inputs. 

The reviewers are in consensus that this paper should be accepted.
Decision: Accept (Poster)