Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

The 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).

It 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.

In 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.

The 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.
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_.

I 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.

I 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

\frac{X^2}{\lambda\log(1+X^2/\lambda)} \approx 1.

What about small lambdas?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

The paper is fairly well written and was easy to follow.
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.
limitations_and_societal_impact: Look above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

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.

1. 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}$?

2. 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.  

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: # Significance

The 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. 

# Strengths

The 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).

# Weaknesses

In my opinion the major weakness of the paper is that the provided experimental studies are not overall convincing to confirm the theoretical contribution:

1. 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.
2. 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.
3. 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.
 

# Justification of the score

As 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.
However, the authors should address the questions below.

# Suggestions to improve readability

1. 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.
2. 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.

**Some questions:**

1. 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.
2. How does the cumulative regret of OFUL for both variants (ridge and forward) vary with the choice of the regularization parameter?
3. 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. 

**Minor things**

0. There are some odd formulations (regarding language). Here are some examples: 
Line 69 “In contrast with …” -> In contrast to
Line 120 “… to this next result.” -> the next result
Line 198 “… in high probability” -> holding with high probability

1. The noise term in line 47 needs a time-index.
2. Line 145: the order of both regret upper bounds depend logarithmically on the time horizon T. Similarly, in line 149.
3. Line 283: The sum should go from 1 to t-1.
4. In the proof section G the time horizon is denoted by n instead of T.
5. 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.

# Post Rebuttal

After 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.

limitations_and_societal_impact: Yes
review_title: null

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)