Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the sparse linear regression problem with an application to experimental design in linear bandits. They propose a new sparse linear estimator of the true model based on Catoni's estimator assuming the knowledge of the population covariance.
The authors bound the error of the proposed estimator in terms of the spectral properties of the covariance matrix. They also propose a warm start estimator and improve the error bound further. Using the error bound of this estimator, the authors then propose a criterion for designing sampling distribution in the linear bandits problem. Using this sampling distribution, they propose an explore-then-commit algorithm for experimental design in linear bandits. The authors then bound the regret of this strategy and further provides a matching lower bound. Finally, under an additional assumption on the minimum signal of the unknown model, they design a phase-based algorithm using the estimator and provide its regret bound.
strengths_and_weaknesses: Strengths:
1. The authors provide a novel estimator for sparse linear regression and prove a tighter error bound for it compared to well-known Lasso estimator.

2. The tighter error bound for the estimator also leads to a tighter regret bound for linear bandits.

3. They also improve the lower bound for experimental design in linear bandits compared to prior work and establish that it is near to minimax optimal.

4. The results are well-positioned compared to the existing work and the paper is well-written.

Weakness:

The bandit algorithm for experimental design needs to solve an optimization problem to find the sampling distribution. I find the implementation details and complexity of that procedure missing from the paper.
questions: It would be great if a discussion on implementation of the convex optimization problem is presented.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies multi-armed linear bandits in high dimensions under sparsity
assumptions. This problem has been studied before (notably by Hao et al '20), but the
paper presents newer (tighter) upper and lower bounds. Key to the algorithm is a novel
estimator for sparse linear regression which allows us to design a sampling distribution
so as to minimize the estimation error. While a s^(2/3) T^(2/3) regret (where s is the
sparsity and T is the time horizon) seems unavoidable in general, the authors show that
\sqrt{sT} rate is possible with a modified version of the algorithm if there is enough
signal from the non-zero coefficients. Finally the authors present some simple
simulations to corroborate their experimental results.

While the results are not earth-shattering, the paper makes solid progress on a
well-established and useful problem. While I didn't have the time to read the proofs in
detail (hence the lower confidence score), the results appear believable and the
intuitions are presented clearly. Hence, I would like to see this paper accepted.

strengths_and_weaknesses: I don't have any major comments/criticisms about the paper. But here are some suggestions
which might help improve the presentation.
1. There were too many in-line equations, and generally, the presentation was somewhat
equation-driven. While I appreciate that this may be unavoidable for a paper such as this,
I felt that the authors could have done a better job of making the material easier to
read.
2. Please try and use words to describe symbols/notation when they are being introduced
(e.g: Explain what R0 is in assumption 1 ).
3. Maybe introduce the compatibility condition (equation 2) closer to the discussion
around Theorem 2. Right now, it doesn't directly relate to the results in the paper and I
was left confused as to what it's purpose was.
4. Instead of using large equations in the algorithm (e.g. line 6), consider defining the
quantities in the text and referring to them in the algorithm pseudo-code.
5. Please explain why knowledge of the signal strenght is necessary for an algorithm to
achieve \sqrt{T} regret around Theorem 4.
questions: See above.
limitations: See above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper revisited the analysis of the sparse regression and the sparse linear bandit problem. 
Firstly, they presented the improved linear regression algorithm POPART by combining the idea of Catoni's estimator and the thresholding.
Then, they showed that using POPART, a simple explore then commit type algorithm improves the regret bound of Hao et al in the data-poor regime.
Thirdly, they showed that by using the POPART for the support estimate and running a linear bandit algorithm, they presented an improved regret upper bound for the data-rich regime.
Moreover, a tighter lower bound for the data-poor regime is presented.

strengths_and_weaknesses: The main contribution of this paper is in its theoretical aspect.
Novel algorithm/analysis of the linear regression and it's consequence is significant.
Their guarantee has tighter dependence than the classical Lasso guarantee by focusing on the different quantities (especially Q^{-1}_{ii}). 

With the help of the novel offline regression analysis, the regret bounds for the sparse linear bandit literature are further improved. For the bandit upper bound part, the algorithmic part may not be so novel but the resulting tighter analysis is significant.
They further presented a tighter lower bound for the data-poor regime with the novel application of the change of measure technique with the symmetrization approach, this technique is noteworthy.

Although there may be some parts of the paper that can be improved, I think the paper is worth accepted for Neurips.

questions: 

### general questions

(Although the same is true of Hao et al.) the action set has to span the entire high dimension so the requirement for the action set can be a bit strict for the high dimensional setting.
The compatibility constant is, in this sense, a much weaker assumption as it does not require the lower bound on the minimum eigenvalue. 
In the results, the lower bound condition in Hao et al is removed but the terms with the diagonal components of Q are used. Does this mean that the lower bound on the eigenvalue condition can be eliminated? Or do you still need to assume that the action set has to span R^d? My impression was the algorithm utilized the idea of Hao et al, but thanks to the improvement with POPART, the requirement on the action set can be further relaxed.


 ### minor, typo
line 53, which can is

I think subgaussian random variable should have zero-mean and no need to state "zero-mean \sigma-subgaussian".


Eq. (3) I think \lambda is not defined so far.

Algorithm 2, Samples are indexed until n, but should be n_0.

Algorithms 1-4,  \sigma is also an input.

Algorithm 4, the phased elimination algorithm is not defined in the main paper. Should cite reference or write pointers.

Eq. (6) I think \lambda_min is not defined. 

line 228 and and

 



limitations: See Questions.
review_title: null

Meta-review: metareview: The paper is motivated by the design of low-regret algorithms for high-dimensional sparse linear bandit problems. The challenge is to obtain regret guarantees even in the data-poor regime where the number of samples the learner can gather may be smaller than the dimension. 

This challenge had been investigated in [12] with a regret scaling as $(sn/C_{min})^{2/3}$ ($s$ is the sparsity of the problem, $n$ the number of samples, $C_{min}$ is the maximum over all possible arm distribution of the resulting average variance. The authors propose a scheme whose regret scales at most as  $(sn H)^{2/3}$ where $H$ is a new (minimax) constant, proven to be smaller than $1/C_{min})$. The paper also presents a matching minimax regret lower bound. 

To achieve this improved regret upper bound, the authors develop a new parameter estimation procedure, based notably on Catoni’s estimator (this kind of estimator has been recently advocated in RL with linear function approximation, see “Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes”, Wagenmaker et al., ICML 2022, and the authors could mention this paper and stress the differences in the use of this estimator). The derivation of the lower bound also relies on new techniques (as mentioned by one of the reviewers).
Overall, this is a solid contribution, even though compared to [12], the improvement is not that spectacular. 

confidence: Certain
Decision: Accept