Venue: NeurIPS 2022 Conference

Reviews:

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: Summary:
The paper addresses the problem of semi-supervised active regression and gives algorithms with instance-optimal query complexity for this problem. Their query complexity results are based on novel notions of complexity parameters introduced in the paper. In particular, they propose an instance dependent parameter, called reduced rank $R_X$. It measures the relative importance of labeled points against the unlabeled ones. This quantity $R_X$ is shown to be equal to statistical dimension $sd_{\lambda} $ (in the active ridge regression setup) and effective dimension $d_{\lambda } $ in the active kernel ridge regression. Thus, leading to query complexity results of $O(sd_{\lambda}/\epsilon$ and $ O(d_{\lambda}/\epsilon) $ for active ridge regression and active kernel ridge regression setups.  Their algorithm is based on randomized BSS spectral sparsification algorithm from [16,4]. It assigns weights on the dataset and depending on these weights a subset of unlabeled data is selected, and its labels are queried. Designing a sampling algorithm which is guaranteed to query labels only for a limited number of unlabeled points is challenging and this paper gives an algorithm to do this.

strengths_and_weaknesses: 
Strengths:
1.	They formalize a notion of reduced rank $R_X$ that is an instance dependent parameter capturing problem complexity. They show that this parameter is equal to previously proposed complexity parameters $sd_{\lambda}$ and $d_{\lambda}$ for the active ridge regression and active kernel ridge regression. I think, it is a good abstraction and helps to connect and understand various problem settings. 
2.	Previously known query complexity guarantees of $O(d/\epsilon)$ are not optimal for active ridge regression, in the sense that the dependence on $d$ is not ideal. The paper gives a query complexity result of $O(sd_{\lambda}/\epsilon)$ and shows that it is optimal in the worst case.
3.	They also improve the query-complexity of active kernel ridge regression from $O(d_{\lambda} log(N))$ to $d_{\lambda}/\epsilon$. Here N is the number of data points so the bound given in paper is free from the number of datapoints which could be large in practice.
 

Weaknesses:
1.	Guarantee is on the loss calculated on the X_un and X_lab. The problem setup is focused on 1+\epsilon factor approximation of the loss function using minimal number of labeled points. However, it doesn’t say much about the generalization error of \hat{\beta}.
2.	It lacks the interpretation of the quantities proposed in the paper, it might be better to give some intuitive understanding of R_X, sd_\lambda, d_\lambda and how should one expect them to behave, are they going to be small or could be very large, are they smaller than d? 
3.	I didn’t see a comparison of query complexity with passive sampling. How do these complexities compare against random i.i.d sampling? 

questions: 1. Could you please include interpretation of the proposed quantities in early in the paper and give some interpretation of the bounds?
2. It might be brief, but its good to see a comparison with the query complexity of passive sampling for this problem.
limitations: Limitations are discussed briefly in section 6. The algorithm is based on SVD of the instance matrix thus it is computationally expensive. They leave design of near-linear time algorithms as future work.
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: This work tackles the problem of semi-supervised active linear regression (SSALR), which generalizes active ridge regression and active kernel ridge regression. The main focus of the paper is to establish instance dependent results on SSALR - in particular, matching upper and lower bounds -, which is done by using the novel notion of reduced rank. In the active ridge regression and active kernel ridge regression this new instance dependent parameter generalizes the key quantities statistical dimension and effective dimension, respectively.

strengths_and_weaknesses: Strengths:
- This problem nicely generalizes well-known frameworks.
- The paper is clearly presented and technically sound.

Weaknesses: 
- No experimental results limit the impact of the work.
- It is surprising that the absence of potential negative societal impacts is not justified. 

questions: - It seems like one connects distributional SSALR to SSALR by stacking an infinite amount of copies of the original dataset with perturbed labels. If so, does Algorithm 1 still apply as is? It seems like it involves an SVD computation.
- Are these algorithms implementable in practice?

limitations: The theoretical limitations are adequately addressed. Although this work is theoretical, it might still be valuable to mention what could go wrong if the suggested algorithms were actually deployed.
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: This paper proposes to study a active semi-supervised least-squares regression problem, where some labelled points are already given and the goal is to minimise the least-squares loss using as few as possible queries to the unlabelled points. 

Interestingly, the minimisation on the labelled points can be used to encode a regularisation term, hence, this problem generalises active ridge regression and even active kernel ridge regression. 

The authors propose to use the instance-dependent parameter "reduced rank" $R_X$, improving previous bounds which only depend on the dimension $d$ of the instances, and give matching lower bounds in the specific case of active ridge regression.

They motivate it by stating that it determines the query complexity of often used leverage sampling as $O(R_X\log d / \epsilon)$ and state a near-matching lower bound. One of the main contributions is a polynomial-time algorithm based on previous results of [6] and [16] to remove the O(log d) term.

In common special cases, $R_X$ reduces to known parameters like the statistical dimension or the effective dimension.
strengths_and_weaknesses: This paper is well-written and tackles an interesting problem. It will probably be appreciated by a theoretical subcommunity of NeurIPS.

The authors provide a strong general bound using the instance-dependent parameter $R_X$, which strengthens previous bounds in known special cases. They show a probabilistic lower bound matching their query upper bound, showing that it is asymptotically optimal. 

Please discuss previous and proposed lower bounds more thoroughly. Without checking [6] it is unclear whether $O(d/\epsilon)$ is optimal, in the sense that there are instances requiring $\Omega(d/\epsilon)$. It is mentioned in line 103 but it's not completely clear that a matching lower bound exists. Maybe an overview table with the different bounds in the different settings helps to get a quick overview?

Minor points:
* "costly' " in the abstract
* line 39: union notation for matrices is not common. They are just stacked row-wise, as in equation (4)?
* Definition 1 seems convoluted.  
* Please formally define "$\preccurlyeq$" (Loewner order?)
* This paper uses the term "agnostic" in a not common sense. In the ML and ML theory literature, agnostic usually refers to the case where we want to PAC learn using an iid training sample and a given hypothesis space, yet, the instances might be labelled arbitrary (i.e., agnostic = not-realizable=ground truth is not necessarily from the hypothesis space), see e.g., Understanding Machine Learning (Shai Shalev-Shwartz and Shai Ben-David, 2014). The authors seem to call the fact that they do not use iid sampling assumptions but rather have worst-case bounds on a given set of points (which do not have to be sampled) "agnostic".

Potential typos:
* What is $X_1$ in line 170. It seems to be $X_{un}$.
* Weird gaps after "Alg" in line 283 and 284. 
* $O(..)$ missing around $R_X/\epsilon$ in line 351.
* line 196: "which decides which points to query the labels of points" sounds not correct.
questions: The lower bound in Theorem 2 seems to not exactly match the upper bound of Theorem 1, in particular, it misses a $1/\epsilon$. What is the reason for that? Shouldn't it be possible to improve the $1/4 R_X \log d$ lower bound with some additional $\epsilon$ term? In particular, for very small $\epsilon$ it seems natural that the lower bound should increase.

By the definition of $R_X$ (and in particular, its equivalence to the sum over $||U(x)||^2$), it seems that $R_X\leq d$. Please discuss this, as otherwise it is not immediately clear whether the achieved bounds using $R_X$ are always better than previous bounds using $d$.

While the semi-supervised setting is very interesting from a practical perspective, it is not clear whether this matters here. All bounds and proofs seem to be mostly concerned with the number of queries and do not take the size or structure of the labelled set into account. E.g., a worst-case could be that the whole matrix $X_{lab}$ consists of the same single instances multiple times, which would provide barely additional information compared to just the active learner (without an additional labelled set). Please comment here.
limitations: The authors focus on the distribution-free transductive case where they bound the error only on the given points $X_{lab}$ and $X_{un}$. Are statistical generalisation bounds possible, i.e., if all $x$ are drawn iid from some (unknonw) distribution, are error guarantees for an unseen $x$ possible?
review_title: null

Meta-review: metareview: This submission studies the problem of active (or query) learning for linear regression. It provides label query bounds in terms of novel parameters.

All reviewers have appreciated novelty and quality of the results. The problem considered is also clearly of interest to the NeurIPS (theory) community.
confidence: Certain
Decision: Accept