Semi-supervised Active Linear Regression
Authors: Nived Rajaraman
Fnu Devvrit
Pranjal Awasthi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Active Learning
Semi-supervised Learning
Ridge Regression
Kernel Ridge Regression

Abstract: Labeled data often comes at a high cost as it may require recruiting human labelers or running costly experiments. At the same time, in many practical scenarios, one already has access to a partially labeled, potentially biased dataset that can help with the learning task at hand. Motivated by such settings, we formally initiate a study of ``semi-supervised active learning'' through the frame of linear regression. Here, the learner has access to a dataset $X \in \mathbb{R}^{(n_{\text{un}}+n_{\text{lab}}) \times d}$ composed of $n_{\text{un}}$ unlabeled examples that a learner can actively query, and $n_{\text{lab}}$ examples labeled a priori. Denoting the true labels by $Y \in \mathbb{R}^{n_{\text{un}} + n_{\text{lab}}}$, the learner's objective is to find $\widehat{\beta} \in \mathbb{R}^d$ such that,
$$
\| X \widehat{\beta} - Y \|_2^2 \le (1 + \epsilon) \min_{\beta \in \mathbb{R}^d} \| X \beta - Y \|_2^2
$$
while querying the labels of as few unlabeled points as possible. In this paper, we introduce an instance dependent parameter called the reduced rank, denoted $\text{R}_X$, and propose an efficient algorithm with query complexity $O(\text{R}_X/\epsilon)$. This result directly implies improved upper bounds for two important special cases: $(i)$ active ridge regression, and $(ii)$ active kernel ridge regression, where the reduced-rank equates to the ``statistical dimension'', $\textsf{sd}_\lambda$ and ``effective dimension'', $d_\lambda$ of the problem respectively, where $\lambda \ge 0$ denotes the regularization parameter. Finally, we introduce a distributional version of the problem as a special case of the agnostic formulation we consider earlier; here, for every $X$, we prove a matching instance-wise lower bound of $\Omega (\text{R}_X / \epsilon)$ on the query complexity of any algorithm.

Semi-supervised Active Linear Regression
Fnu Devvrit"
Department of Computer Science University of Texas at Austin devvritêcs utexas.
Nived Rajaraman
Department of Electrical Engineering and Computer Sciences University of California, Berkeley ni nived. raj nived.rajaraman wwwaaaaraaabbbereeeee..... edu
Pranjal Awasthi
Google Research & Department of Computer Science Rutgers University
pranjal www.wwwittttttrrrs.eee
Abstract
Labeled data often comes at a high cost as it may require recruiting human labelers runming costly' experiments. At the same time, in many practical scenarios, already has access to a partially labeled, potentially biased dataset that can help with the learning task at hand. Motivated by such settings, formally initiate study semi-supervised active learning through the frame linear regression. Here, the learner has access to dataset X toan) composed of Yun unlabeled examples that learner actively query, and Raa examples labeled a priori. Denoting the true labels by Y E tua the learner's objective to find 3 E Rdd such that,
X 1 S (1 (1+)) min |X3 Y
(1)
BER"
while querying the labels of as few unlabeled points as possible. In this paper, we introduce an instance dependent parameter called the reduced rank, denoted Rx, and propose an efficient algorithm with query complexity O(Rx/e). This result directly implies improved upper bounds for two important special cases: (i) active ridge regression, and (ii) active kernel ridge regression, where the reduced- rank equates to the statistical dimension, sd,, and effective dimension, d2 of the problem respectively, where
denotes the regularization parameter. Finally, we introduce distributional version of the problem as special case of the agnostic formulation we consider earlier; here, for every X, we prove matching instance- wise lower bound of {(Rx //) on the query complexity of any algorithm.
Introduction
Classification and regression are the cornerstone of machine learning. Often these tasks are carried in supervised learning manner learner collects many examples and their labels, and then runs an optimization algorithm to minimize a loss function and learn model. However, the process
equul contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of collecting labeled data comes at cost, for instance when human labeler is required. or if an expensive experiment needs be run for the same. Motivated by such scenarios, two popular approaches have been proposed to mitigate these issues in practice: Active Learning [24] and Semi-Supervised Learning [30] In Active Learning, the learner carries out the task by adaptively querying the labels of small subset of characteristic data points. On the other hand, semi-supervised learning is motivated by the fact that learners often have access to massive amounts of unlabeled data in addition to some labeled data, and algorithms leverage both to carry out the learning task. Active learning and Semi-supervised learning have found numerous applications in areas such as text classification [6], visual recognition [77 and foregroumd--acckgruudd segmentation [15].
In practice. learners often have access smaller labeled datasets and larger unlabeled datasets, chosen points of which can be submitted for manual labeling. This motivates the semi sunni--upeeised active regression (SSAR) formulation here, the learner is provided an priori labeled data Xjah E Roax as well as an unlabeled dataset Xum R points of which can be iteratively submitted to an external agent to be labeled at unit cost. In the linear regression framework, the objective of the learner is to then minimize the squared-loss || - Y12 while making as few label queries (of points in X mm as possible. Here X is the overall dataset, Xiab U Xun represented as matrix in R + + while Y E Ru denotes the corresponding labels. The learner seeks to find a regression function E Rd such that,
| - x11 s (1+ min |X3 - --
(2)
BER"
Likewise, the e-query complexity of an algorithm is defined as the number of unlabeled points in Xun that must be queried in order to return a such that eq. (2) is satisfied with constant probability.
In the special case when no labeled data is provided (i.e. Xiab is empty), SSAR reduces to active linear regression, which has been studied in several prior works D S. 7 6).
SSAR includes several other important problems special cases. For some À >> 0, consider the setting where the labeled dataset Xlab is the set of standard basis vectors scaled by a factor of vÀ, with corresponding labels as O. The loss of a learner 3 on this dataset exactly corresponds to the ridge regression loss the unlabeled dataset, X| 3 Y un! 1/2 + 2| where Y.n. are the labels of points in Xun- Thus, active ridge regression is captured as a special case of SSAR.
On the other hand, it turns out that active kernel ridge regression is also captured special case of SSAR. Here, data points lie in a reproducing kernel hilbert space (RKHS) P1 25 20] that is potentially infinite dimensional, but the learner has access to a kernel representation of the N data points. Denoting the kernel matrix by K E R x N and the labels of the points as Y E R the objective in kernel ridge regression is to minimize the loss ||3 - 1'112 + +| B1lk This can be viewed as special case of the SSAR framework by choosing the labeled dataset as Xubb = vXVK VVN with each point labeled by 0, and the unlabeled dataset X... = K E R NxN with labels Y' E ERN. In this work, the main question we ask is,
Can we design algorithms for SSAR with instance-wise optimal query complexities?
Our first main contribution is to propose an instance dependent parameter called the reduced rank, denoted Rx, that be used to upper bound the worst-case optimal query complexity of SSAR. Intuitively, Rxx measures the relative importance of the points at which labels are known, Xlab, in the context of the overall dataset. Formally, the reduced rank is defined as:
Rx = Tr (xx"* + lub X1ah)
X un
We propose an efficient polynomial time algorithm for SSAR with e-query complexity bounded by O(Rx /c). In the special cases of active ridge regression and kernel ridge regression, Rx is shown to be the equal to the statistical dimension sd, [3] and the effective dimension d, (28) of the problem
respectively, which directly implies query complexity guarantees for the two special cases. These parameters are formally defined in Section g
Optimal algorithms for active ridge regression. The recent work of 6 studies the problem of active regression and following a long line of work (see (9]) provides a near optimal (up to constant factors) algorithm for active regression querying labels of at most (dd/e) points. The algorithm of [6]

---

can be used for active ridge regression too, where À * O, resulting in a query complexity guarantee of O(d/e). However, the dependence on is not ideal in this setting and an instance-dependent parameter of the data known as statistical dimensions sdx is the right measure of the complexity of the problem. As a consequence of our general algorithm and guarantee, we obtaín an algorithm for active ridge regression with query complexity upper bounded by O(sdx/c), which we show is in fact optimal in the worst case. As a result we resolve complexity of ridge regression in the active setting.
Improved guarantees for active kernel ridge regression. In the context of kernel ridge regression, the work of [1] analyzed kernel leverage score sampling (and general Nyström approximation based methods), showing that these sampling approaches query O(d, log( labels to find a constant factor approximation to the optimal loss. In contrast, our algorithm when applied in the kernel ridge regression setting achieves query complexity guarantee of O(dx/c) bearing no dependence on the number of datapoints, N, which is often large practice.
Techniques. Our algorithm is based on a novel variant of the Randomized BSS spectral sparsi- fication algorithm of [16] 4 that returns a small weighted subset of the dataset, queries its labels, and subsequently carries out weighted least-squares regression on this dataset. The key technical contribution of this work is to construct a sampling algorithm which guaranteed to query the labels of only a limited number of unlabeled points. We discuss the algorithm and its guarantees in more detail in Section 4
The rest of the paper is organized as follows. We cover related work in Section 1.1 and introduce relevant preliminaries in Section 2 We motivate and present the new parameter R in Section 3 and present our algorithm for SSAR and proof sketch in Section In Section S we introduce the distributional SSAR problem, and show matching instance-dependent lower bound for the problem.
1.1
Related Work
Several prior works use active learning to augment semi-supervised learning based approaches 23 The key in several of these works to use active learning methods to decide which labels to sample, and then use semi-supervised learning to finally learn the model.
12
29
10
22
In the context of active learning for linear regression, 9 127 analyze the leverage score sampling
algorithm showing sample complexity upper bound of O log(d//)). Subsequently for the case of
e 2 d ++ 1, 7 shows that volume sampling achieves an (dd) sample complexity. Later, ( shows that rescaled volume sampling matches the sample complexity of (ddlog(d)//) achieved by leverage score sampling. Finally, (6] shows that a spectral sparsification based approach using the Randomized
BSS algorithm [16] achieves the optimal sample complexity of Od//e).
study the problem of reducing the runtime and number of kernel evaluations to approximately solve the problem. These results show that the number of kernel evaluations be made to scale only linearly with the effective dimension of the problem. (K) up to log factors. Recently, [1] prove a statistical guarantee showing that any optimal Nystrom approximation based approach samples most d, (K) log(n) labels to find constant factor approximation to the kernel regression loss, where n is the dimension of the kernel.
In the context of kernel ridge regression, the works of [1] 28 19
A closely related problem to active learning is the coreset (and weak coreset) problem 2 18 where the objective is to find a low-memory data structure that can be used to approximately reconstruct the loss function which naively requires storing all the training examples to compute. 1 study the weak coreset problem for ridge regression and propose an algorithm that returns a weak coreset of O(sd,/e /c) points which can approximately recover the optimal loss. A drawback of their algorithm is that the labels of all the points in the dataset are required, which may come at a very high cost in practice, As we discuss in Section 4 our algorithm also returns weighted subset of O(sdx/e) points in Rd and set of d additional weights that can be used to reconstruct (1 + apparoxximationn for the original ridge regression instance. In terms of memory requirement, this matches the result of 13: however it suffices for our algorithm query at most O(sds/e /e) labels.
2 Preliminaries
In this section, we formally define Sepi-super Active Regression (SSAR) under squared- in the linear setting. The learner is provided datasets Xun E Ri (comprised of Ten points in R&4) and
3

---

Setting
Upper bounds
Lower bounds
Agnostic SSAR
Rx loglo
(LSS* Theorem
Rx (ASURA: Theorem
Distributional SSAR it
(ASURA: Corollary
(Theorem 5)
Table Table of guarantees for SSAR
The agnostic SSAR problem assumes no distribution on the input, and assumes no label noise. it The distributional SSAR problem (Section 5 assumes that the input follows a known distribution and queried labels are corrupted by Gaussian noise. LSS stands for Leverage Score Sampling.
Setting
Upper bounds
Lower bounds
Active Ridge Regression
d-logíd) (LSS*
(Linear Sparsification
sdx
(ASURA: Theorem
sd (Theorem 5
Active Kernel Ridge Regression
dy (og)))
(Nystrom Approximation
(ASURA: Corollary
1
(Theorem
Table 2: Table of guarantees for special cases of SSAR
LSS stands for Leverage Score Sampling.
Xiah E RR The labels of the points respectively Yu Ri and Yib Ruah, Define,
X
Xum Xlab
um
In the agnostic setting, the labels of the points are not assumed to be generated from unknown underlying linear function and can be arbitrary. We study the problem in the overconstrained setting with Aun 7aab 2 d. Furthermore, in the active setting, it is typically the case that 7un d. When clear from the context, we use X, Xiab and Xm to represent the datasets in set notation.
We assume that the learner is priori provided Yiah and hence knows the labels of all points in X but the labels of points in Xun are not known. However, the learner can probe an oracle to return the label of any queried point in Xun and incurs a unit cost for each label returned. The learner's objective is to return linear function 3 Rd which approximately minimizes the squared lg loss,
X 3
Y < (1 + x3 YII,,
where, 8 - arg min |X - Y
(5)
BER"
SSAR has the following two important problems subcases.
Active ridge regression: In the active ridge regression problem, the learner is provided an unlabeled oracle which can be actively queried to
dataset Xun E IRaxd of points. The learner has access label points in Xmm- Representing the labels by Yun E Ik"" the objective the learner is to minimize
(B) A 1 Yum l2 + A11.112 Defining X X
E R (n+ddxxd and [Ym
RR*d
VXI
0
observe that | - Y = I| Yun I + |||lI|e Thus, active ridge regression a special case of the SSAR objective in eq.
Active kernel ridge regression: In the kernel ridge regression problem, the learner operates in reproducing kernel Hilbert space H and is provided an unlabeled dataset X of n points with (implicit) feature representations ((x) for x: E X. The objective learn a linear function F(x), in the feature representations of points in X that minimizes the squared & norm with regularization. Namely,

---

(F -Y) + By the Representer Theorem [4]. it turns out the optimal regression
function (.) can be expressed as Ei=1 (,((1s;)) where k(:s)) .) is the kernel function. The kernel
ridge regression objective can be expressed in terms of the kernel matrix K - [k(2;, x. } Ixxx* In other words, denoting the labels by Yu R and ||3 = 3 K 3, the learner's objective to minimize over B E IR".
K Yu 12 1||31l
(6)
while minimizing the number of label queries of points in Xun- The objective can be represented as,
[
K [AVK
Yum 0
min
3 -
BER
where Z = V is defined as the unique solution to K = Z Z. Yet again, it is special case of the linear regression objective in eq. with Xum = K, Xlab = K and Y 0.
3 Motivating the reduced rank Rx
natural algorithm for SSAR to use the popular approach of leverage score sampling 9 This approach uses the entire dataset X (both labeled and unlabeled) to construct a diagonal weight matrix Ws: here S represents the support of the diagonal and [|S 2 m (ddlo)(d)))) The learner subsequently solves the problem: 3 arg ming (Ws((3 Y) which is weighted linear regression problem on |S| examples. The works of 993 show that resulting linear function produces (1 + c) multiplicative approximation to the optimal squared-loss:
| 112 < 61+ inf ||x Y12
BERd
with constant probability. The weight matrix Wss returned by leverage score sampling is constructed as follows: Letting UVVT denote the singular value decomposition of X, the algorithm iterates over all the points in X and includes point in S with probability p(x) 2 min { a |IU (x) proportional its leverage score (=))2 where U(x) is the row in U corresponding to the point E X. The corresponding diagonal entry of Ws is set as Vp(z)* Since the points in Xlab are
labeled, the number of times the algorithm queries the oracle to label point is equal to |S X By definition of the sampling probabilities, this is proportional to the sum of the leverage scores across the points in Xun:
[10())1 log(d)
E E X
Σ ZEX
Σ
[1(x))
x
In Lemma 5 we prove that the term Σxex.. [1(()) equals the reduced rank, Rx defined as Tr (X XT
XT X.m) Combining with eq.
(9 results in the equation,
[[SX Xunl Rx log(d)
(10)
In particular, by Markov's inequality, with large enough constant probability, leverage score sampling makes at most O xxx log(d) label queries (of points in X1). Combining with the guarantee on the quality of the solution returned by leverage score sampling in eq. 8 results the following guarantee.
Theorem 1. For 0 < < 1, the e-query complexity of leverage score sampling for SSAR is upper bounded by O Rx log(d)))))
In order to further motivate Rx we next turn to the ridge regression problem: Here, it turns out that Rx equals the statistical dimension of Xmn. defined
(d,(X A Σ 2
rank(X
(II)
1 Nof((u)
5

---

where 0z (XXu) is the 1th largest singular value of Xun This can be seen by plugging in Xlab as VAI eq. 3 and expanding xm using its singular value decomposition as U,
In comparison, in kernel ridge regression, Rxx evaluates to the effective dimension, defined as:
rank(K)
dx (K)
(12)
1=1
where the o, 's are the eigenvalues of K. This yet again follows by plugging the choice of Xun and Xlab in the kernel ridge regression setting from eq. 77)
The common theme in the prior sampling based approaches []] for kernel ridge regression, as well the bound leverage score sampling established for SSAR (Theorem 1 is that they face logarithmic dependence in the dimension parameter d or N (in the case of kernel ridge regression) which are often large in practice. Indeed, we show that this logarithmic dependence is unavoidable in the worst case for leverage score sampling.
Theorem 2. There exists an instance of SSAR such that the e-query complexity of leverage score sampling for any constant is 2 R log(d).
In this paper, we subsume previous results and show an algorithm with an e-query complexity of O [Rx] ) for SSAR. This shows that it is possible to derive statistical guarantees for active ridge / kernel ridge regression that respectively depend only the statistical dimension/ effective dimension.
4 Algorithm
In this section, we design a polynomial time algorithm (Algorithm D for SSAR and prove that the e-query complexity of the algorithm is O( Rxx).
The core construction of the algorithm is based on an iterative mechanism known as an e-well balanced sampling procedure, which decides which points query the labels of points. At an intuitive level, an e-well balanced sampling procedure guarantees that the points sampled so far are well representative of the overall dataset (in weighted sense), while at the same time guarantceing that a certain weighted condition number, related to the error incurred by least squares regression is small.
Our main algorithm, Algorithm follows the template of 6 which (i) repeatedly queries the labels of points in adaptive manner using an e-well balanced sampling procedure Alg, and (it) solves weighted linear regression problem on the set of points sampled step (i).
Algorithm 1: ASURA (Active semi-SUpervised Regression Algorithm)
Input: X E IR ("w accuracy parameter any well-balanced sampling procedure Alg (cf.
Definition D or Algorithm 2):
Run el)(X,e) to return subset of points {x), .mm) and weights (wi," Wm
// m determined internally by Alg Query the labels y1 of T1,... IIm for 2; Xun-
// the label query cost of the algorithm
Output: 3 t- arg mingge E w. 2, 3.
We first begin by defining the notion of well-balanced sampling procedure.
Definition 1 (well-balancee balanced sampling procedure). 16 Def 2.1] A well-balanced sampling proce- dure is randomized algorithm Alg(X, that outputs set of points {21, , _m,} and weights {w,, ... wm. } as follows: in each iteration = 1.... m, the algorithm chooses a distribution D; over points in X to sample I; D,. Let D be the uniform distribution over all points in X. Then, Alg is said to be an c-well-balanced sampling procedure if it satisfies the following two properties with probability 2 3/4,
1. The matrix Z = diag( (wil (ee.:m.. E R.xd where UEVT is the SVD of X and
U Upzcam) are the rows of corresponding to the points (21, .. Im satisfies:
n 5 3 1
(13)
4
4

---

51 Equivalently, For every B E R Ei= w/ 2;, E [ AAAA BEND [[3,2]]]
2. For each E [m], define
D(a.) Wi. Then, Alg must satisfy E 0z O(1) and 0gKD, O()), where KD; is the re-weighted condition number:
D.(a.)
(2(2)
(3,x) D(x) E [13, x²)
KD. = sup
sup BER
(14)
In [6] it is shown that any sampling procedure in step (i) of Algorithm
I which is well-
(Definition] [ guarantees that the resulting solution is approximately optimal.
Theorem 3. 66 Theorem 2.3] For any 0 < < 1, instantiate Algorithm
7
with any e-well balanced with constant probability
sampling procedure Alg(X, Denoting 3 as the output of Algorithm 1
| - 21 & (1 + O())) min BER"
|X3 - -Y
(15)
Theorem shows that to solve the SSAR problem, it suffices to design well-balanced sampling procedure which queries minimal number of labels of datapoints in the unlabeled set, Xun- We now present Algorithm 2 and show that indeed satisfies both of these criteria. The algorithm is
parameterized by 7, chosen to - Ve/Co for a sufficiently large constant Co > 0.
Theorem 4. Algorithm is an -wwel-balancee sampling procedure, where 0 < < 1. Furthermore,
Algorithm samples the labels of most O (xx) points X
Algorithm 2: e-well balanced sampling procedure for SSAR
Input: X E R=xd:
Initialization: j = 0; Ve/Co: un = 2d/7; lo = -22//7: Ao 0.;
2 while (u, 12) 1- TTd < 8d do
Define L Tr ((ug A (Aj 1,1))
Set coefficient a'; 7/a/t: Sample point from the multinomial distribution on X which assigns probability to x as,
P2 Ulz)² ((u/1 - AA) (A, 1,1)
(16)
Tld
// Define the cempled point as Iÿ and Ps as Pj v
Update Aj+1 <- Aj + æu p: (Z,))(((,))
Define the weight wn/ 3.
8
Update Uj+1 + Uj + 1-27 कह and 1,+1 + l/ + 1+27 of
j
+ j +
10 end
Assign =j
Define mid & tme and for each j. set the coefficient a, mid and the weight wy mid Output: {-1,.... Fm (wi,... Wm)- }.i
Algorithm is variant of the Randomized BSS algorithm of [16 for spectral sparsification (eq. with an updated stopping criterion, which we discuss in Remark [ each iteration, the algorithm maintains a matrix A which up to scaling factor is the same as the matrix Z Z in Definition and an upper and lower threshold u and which are updated in an iterative manner. The update rule is guaranteed maintain the invariant 17 A < uT in every iteration, which is ensured by the adaptive sampling distribution in eq. (16). Over iterations, the algorithm shows that the upper and lower thresholds and I can be brought closer to each other which sandwich Z Z (equal to A up to scaling) until eq. (13) is finally satisfied. It turns out that the desirable quality for is that and progressively become larger (which dictates the scaling factor relating A and 2H Z), while the same time gap between the two, u I, remains small. The proof of correctness of Algorithm requires two ingredients:
(3)
7

---

1. Algorithm is indeed an e-well balanced sampling procedure. (Section 4. and
2. The number of label queries made by Algorithm i bounded by O (Rx (Section 4.2
Remark 1. Notice the important difference in the stopping criterion of Algorithm 2 compared to that of the Randomized BSS Algorithm of [16] which just the condition U, - < 8d/7, The more aggressive stopping criterion can be used to show that Algorithm terminates within 20/a² iterations Serrrittmmeeemmintttes
the while loop Step almost surely, while the Randomized BSS algorithm [T6] terminates within
2d/-² iterations only with constant probability. This behavior is critical in bounding the number of label queries made by Algorithm 2
4.1 Algorithm 2 is an c-well-balanced sampling procedure
We first address the question of showing that Algorithm 2 is an e-well balanced sampling procedure. We provide brief sketch which addresses the first condition, eq.
(13)
First observe that the stopping
criterion of the algorithm is the first time j when Σi= 4. 4y
47"
EED T >
8d Note that
each term in the summation, (1(1)))2) + D is at least 2
44²
x T 2 4y by the AM-GM @1 (1-4))
44
inequality. Therefore, if the number of terms in the summation is at least dd x In 7
2d
the stopping
7
criterion must certainly be violated. This results in bound the number of iterations before the while loop is terminated Algorithm [ defined as m.
Lemma 1. Almost surely, m S 2d/72.
While m is upper bounded by 2d/72, the key result of this section is that the number of iterations of by the algorithm also satisfies m 2 ed/-" with constant probability, for sufficiently small constant c. The implication of the algorithm not terminating too soon is that in the upper and lower boundaries maintained in the algorithm are updated over a large number of iterations and therefore the eigenvalues of the matrix A are very tightly sandwiched, proving the eigenvalue condition in eq. (3). We flesh out the details below.
Note that in each iteration, the upper boundary uy increments by 1-27 T.. As we show in the
7 T is 2 7/2 almost surely and therefore uy increments by at least a 2 2 2 in each iteration of Algorithm 2 Since the algorithm does not terminate soon and m 2 ed/-" with constant probability, in the final iteration, um is also > ed/;² 2 with constant probability. More precisely, we have the following result.
Appendix A.3 (Lemma
constant x
Lemma 2. For < 1/4 and any p 1, with probubility least 1 p. Um d/
We next relate the matrix A maintained in the algorithm and the matrix 2 Z in Definition 1 When Algorithm? terminates, the matrix Am stored is equal to Σy=
7 1 U (z))) From the T
definition of mid and wy in Algorithm it is a quick calculation to show that nT 7 mid 4
2 Am Furthermore, since the invariant of Algorithm 2 guarantees that L,,/ 3 Am I un L, we Men TT
have that
21m tm < ZTZ 2um +lm
Thus to prove eq. (13) it suffices to show that 2m 1mm is small.
um
By the stopping criterion of the algorithm, we are guaranteed that the gap. Um -mm RJ um --- S 8d/n; formally we show that Umm - IIm < 9d// in Appendix (A.4 (Lemma (9. implying that um and 4m are close to each other. Moreover from Lemma 2, with constant probability, In Rs um = ((d/r?). Thus, the ratio sem Fim
O(7) and satisfies eq. (13) for sufficiently small 7.
Lemma 3. With probability at least 3/4, (1 T A (1 +1+ O(r)).
We defer the proof of the fact that Algorithm 2 satisfies the second condition in Definition D to Appendix A (Lemma 12) since it largely follows from the analysis in 6
4.2 Bounding the number of label queries made by Algorithm 2
Finally, we upper bound the number of times Algorithm D queries the labels of points in the unlabeled set, X.n. We denote this quantity by (q().).
First observe that the number of label queries, (X(,),,, is at most the number of iterations in which the well-balanced sampling procedure Alg in Line of Algorithm I samples a point in Xmn. The
8

---

former is smaller if a point is sampled more than once by Alg Indeed,
II (X)))) S E
Σ x I(
(17)
where is the total number of iterations the algorithm runs for, and T is an indicator capturing which is if x: is sampled in Step 5 of Algorithm 2 in iteration j and 0 otherwise. Note that
B
E Epp is the probability of sampling the point x as defined in eq. (16). Recall that in 2d almost surely. By linearity of expectation, 77
Lemma we show that is upper bounded by
E (X - > j=0
20/.8-1
E P
(18)
Remark 2. Note that the bound on the expected number of label queries in eq. 17 is the sum of non-negative random variables (I(2) which are correlated with the number of terms in the summation (m). The almost sure upper bound on m enables this correlation to be decoupled, which is not easily possible with a constant or even high probability upper bound on m, as guaranteed by the Randomized BSS algorithm [16] (discussed in Remark] 7
Before studying Ez=0
[ we first introduce some relevant notation.
Definition 2. For a PSD matrix M, define the potential function $ TMM 111-1
M(Aj - 11,))-))) uj. 1j and A2 are as defined in Algorithm
Simplifying from definition of pa results in the following lemma. Lemma 4. In iteration j = 0,.,,,,1,, EvEx., pe
P
qut where D = E (())(
As we show in Appendix A (Lemma 7b, the term in the denominator, 1/ is at least Tb/ 2 7/2 almost surely. By plugging in Lemma into eq. (18), the expected number of labels of points Xun queried by Algorithm 2 is upper bounded by,
2
24/221
Ellq(Xunn) S
E|
(19)
1=
Over the course of the time, one expects the gap between uj and ly to grow apart (from the update rule on line 8 of Algorithm ( while Aj remains tightly sandwiched in between the two bounds. It turns out that consequence of this fact, the expectation of the potential, E [ is decreasing
function in j. We formally prove this result in Appendix AA.3 (Lemma B). From eq. (T9). this results in the following upper bound the number of label queries,
4d E
4Tr(D) 72
E[lq(Xum)]
(20)
73
where the last equation, E[ = B[Tr(D(uol Ao) + D(An (11) = =Tr is a short
calculation from its definition using the fact that ug -10 and Ao 0. The final lemma relates Tr(D) to the reduced rank Rx- Lemma 5 (Relating D to Rx). With D= D= (z)) T(D) = Rx.
Putting together Lemma 5 with eq. (0)) and noting the definition 7 /e/Co results in the final bound on the number of label queries made by Algorithm 2
(llq(Xxn)] S 4Rx
(21)
In the case of ridge regression, Algorithm 7 can used to construct weak-coreset for 3 The advantage of the algorithm over A13Y is that the weak coreset can be constructed without having oracle access to the set of all labels. particular, our algorithm returns coreset which uses O (dsds/ /e) bits of memory: up to log factors the weight matrix Ws requires bits of memory to store and the sdy/c / points queried in Xmm require dsd,, bits of memory to store. Solving: arg min || W.s X33 W returns (1 + approximate optimizer of the loss. The memory requirement of our algorithm matches that proposed in (13), while only querying a few labels.
Remark 3.

---

Instance-dependent lower bound for distributional SSAR
In this section we introduce a distributional or inductive 66 formulation of semi-supervised active regression as special case of the agnostic formulation discussed earlier.
Definition 3 (Distributional SSAR). The setup here is identical to the agnostic setting, but with the labels revealed to the learner corrupted by independent stochastic noise. In particular, at training time, each time the label of x E X is observed (either in the labeled dataset, or by explicitly querying)
noisy version of the ground-truth label, f(x), revealed. Namely, y = f(x) Z is observed,
where the training time noise Z ~ (N0 o The objective is to minimize the generalization error,
E
Σ FEX ((3,x)- f(x) - -xx))=z))²
(22)
where for each x E X, Zz ~ (0, is sampled independent of the noise at training time.
Note that the distributional SSAR problem a special case of the agnostic formulation. This just corresponds to having infinitely many copies of the labeled and unlabeled datasets, where the label in each copy is the ground truth corrupted by a different realization of the stochastic noise. Therefore, may be easily verified that the guarantee of ASURA (Theorem 3) carries over here.
Corollary 1. The ASURA algorithm for the distributional SSAR can be implemented efficiently (polynomial in d, the support size of X for the distributional SSAR problem, requiring to compute SVDs over single copy of the matrix X. Furthermore, the guarantee of ASURA still carries over: the algorithm queries the labels of at most O(Rx/e /e) points, and guaruntees to achieve (1 +) approximation to the best achievable generalization loss (eq. (22)
turns out that in the distributional setting, one may also come up with an instance instance-depender dependent sample complexity lower bound, where the imput design X is fixed, but the adversary has the power control the ground truth labels f(-) as well as the noise variances of in designing the instance.
Theorem For any 0 < e < 1, d and any
O. Suppose X satisfies the condition, 2 T In the inductive setting, for each X and learner there ex-
mmin (x(x lab
ists an instance of SSAR where if 3 returned by the learner satisfies E [[IX3 - Y11 S (1
e) mingeR" E [||X [| must query the labels of at least D1 (xxx points.
The proof of this lower bound is quite complicated because of both the adaptive nature of the problem, as well the requirement for an instance-depended bound. At high level, we use an hypothesis testing based construction (Assouad's lemma) with careful choice of hypothesis space. The main challenge is choosing the underlying instance in a way to recover the reduced rank as the measure of complexity, which has very delicate dependence on (the spectrum of) Xlab and X In the interest of space, we defer the details of th proof to Appendix A.5 This result also shows that there is no need to have any sort of commutation structure between the labelled and unlabelled data matrices Xlab and Xun for the reduced rank to remain as the right instance dependent lower bound.
6 Conclusion
We introduce the semi-supervised active learning problem and prove a query complexity upper bound of Rx/c for linear regression. In the special case of active ridge regression, this implies sample complexity upper bound of (sdx/c) labels which we prove is optimal. The problem also generalizes active kernel ridge regression, where show a query complexity upper bound of O(dx/e) improving the results of [.. an open question to extend these results to other loss functions and to design near-linear time algorithms for the problem.
7 Acknolwedgements
NR was partially supported by NSF Grants 1901120 and CCF-1909499.
2 onne may instead assume that the noise is subgaussian with variance o². For ease of exposition we stick to Gaussian noise.
10

---

References
[14] George Kimeldorf and Grace Wahba. Some results on tchehycheffian spline functions. Journal of [1] Ahmed Alaoui and Michael W. Mahoney. Fast randomized kernel methods with statistical guarantees, 2015.
[2] Alexandr Andoni, Collin Burns, Yi Li. Sepideh Mahabadi, and David Woodruff. Streaming complexity of svms, 2020.
[3] Haim Avron, Kenneth L. Clarkson, and David P. Woodruff. Sharper bounds for regularized data fitting, 2017.
[4] Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava, Twice-ramanujan sparsifiers, 2009.
[5] Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal coresets for least-squares regression. IEEE Transactions on Information Theory, 59 (0))6880 6892, Oct 2013. ISSN 1557-9654. doi: 10.1 10:1
URL http::t/p///ddoo wttp:/......gg/..111//11111 2013. 2272457
[6] Xue Chen and Eric Price. Active regression via linear-sample sparsification, 2019.
[7] Michal Derezinski and Manfred K. Warmuth, Unhiased estimates for linear regression via volume sampling, 2018.
[8] Michal Dereziński, Manfred K. Warmuth, and Daniel Hsu. Leveraged volume sampling for linear regression, 2018.
[9] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Relative-error cur matrix decompositions, 2007.
[10] Thomas Drugman, Janne Pylkkonen, and Reinhard Kneser. Active and semi-supervised learning in asr: Benefits on the acoustic and language models, 2019.
[11] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning, volume of Springer series in statistics New York. Springer, 2001. Jtttttss:://web stanf
ElemStatLearn/
[12] Mingfei Gao, Zizhao Zhang, Guo Yu, Sercan O. Arik, Larry S. Davis, and Tomas Pfister. Consisteney- -upervupee active learning: Towards minimizing labeling cost, 2020.
[13] Pranecth Kacham and David Woodruff. Optimal deterministic corescts for ridge regression. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4141-4150, Online, 26-28 Aug 2020. PMLR.
mathematical analysis and applications, 33(1):82-9)) 95, 1971.
[15] Ksenia Konyushkova. Raphael Sznitman, and Pascal Fua. Introducing geometry in active learning for image segmentation, 2015.
[16] Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost- linear time, 2015.
[17] Tong Luo, K. Kramer, S. Samson, A. Remsen, D.B. Goldgof, L.O. Hall, and T. Hopkins. Active learning to recognize multiple types plankton. Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004., volume 3, pages 478-481 Vol.3, 2004. doi: 10. 1099CCPR. 1334570.
[18] Alexander Muntcanu, Chris Schwicgelshohn. Christian Sohler, and David P. Woodruff. On coresets for logistic regression, 2018.
[19] Cameron Musco and Christopher Musco. Recursive sampling for the nyström method, 2017.
[20] Arti Patle and Deepak Singh Chouhan. Svm kemeel functions for classification. In 2013 International Conference on Advances in Technology and Engineering (ICATE), pages 1-9, 2013. doi: 10.1 109/CAdTE. 201 3.652743.
[21] Vern I. Paulsen and Mrinal Raghupathi. An Introduction the Theory of Reproducing Kernel Hilbert Spaces. Cambridge Studies Advanced Mathematics. Cambridge University Press, 2016. doi: 10.1017/ CBO97813162192222
[22] Phill Kyu Rhee, Enkhbayar Erdenee, Shin Dong Kyun. Minhaz Uddin Ahmed, and Songguo Jin. Active and semi-supervised learning for object detection with imperfect data. Cognitive Systems Research, 45:109-123, 2017. ISSN 1389-0417. doi: http://wwwaneaattaaaaaaa///////.
URL https
www..scienceirret. ctm/ www.//cciencaaooooooccccccccocce htt/ssciiinccccreeeeeeee
[23] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach, 2018.
[24] Burr Settles. Active learning literature survey. 2009.

---

[25]
Hiroyuki Takeda, Sina Farsiu, and Peyman Milanfar. Kernel regression for image processing and recon- struction. IEEE Trunsactions Image Processing, 16(2):39--66, 2007. doi: N0.1109/1P22000.888833 888330.
[26] Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classifica- tion. J. Mach. Learn. Res., 2:45 66, March 2002. ISSN 4432. doi: 10. 10.1162/153223300766113333
URL/https /ttppp:://oo..oo org/ 10. 01111///1152443077711822222
[27] David P. Woodruff. Computational advertising: Techniques for targeting relevant ads. Foundations and Trends in Theoretical Computer Science, 10 10(1-2)11157, 2014. ISSN 1551-3068. doi: 10.1561/ 0400000060. URL http:///:/ doi. worooo///// 1561/04000000660
[28] Taisuke Yasuda, David Woodruff, and Manuel Fernandez. Tight kernel query complexity kernel ridge regression and kernel k-means clustering. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7055 7063. PMLR, 09 15 Jun 2019. URL UtL/htttp//prroceediig
mlr. www.pprsss/eeee /97 yasdda/yssaalla.... .html
[29] Xiaojin Zhu, John Lafferty. and Zoubin Ghahramani. Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. In ICML 2003 workshop on The Continuum from Labeled to Unlabeled Data Machine Learning and Data Mining, pages 58 38-65, 2003.
[30] Xiaojin Jerry Zhu. Semi-supervised learning literature survey, 2005.
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] We describe some future
directions in Section which we do not address
(c) Did you discuss any potential negative societal impacts of your work? [No]
(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] All proofs are deferred to the supplementary material
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
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 're using/curating? [N/A]
(c) 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, applicable? [N/A]
12

---

(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]
13


Reviews:
[{"review_id": "fhx3YApbo9W", "reviewer": "Reviewer_jxU1", "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. \n\nInterestingly, 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. \n\nThe 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.\n\nThey 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.\n\nIn common special cases, $R_X$ reduces to known parameters like the statistical dimension or the effective dimension.", "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.\n\nBy 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$.\n\nWhile 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? ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-written and tackles an interesting problem. It will probably be appreciated by a theoretical subcommunity of NeurIPS.\n\nThe 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. \n\nPlease 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?\n\nMinor points:\n* \"costly' \" in the abstract\n* line 39: union notation for matrices is not common. They are just stacked row-wise, as in equation (4)?\n* Definition 1 seems convoluted.  \n* Please formally define \"$\\preccurlyeq$\" (Loewner order?)\n* 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\".\n\nPotential typos:\n* What is $X_1$ in line 170. It seems to be $X_{un}$.\n* Weird gaps after \"Alg\" in line 283 and 284. \n* $O(..)$ missing around $R_X/\\epsilon$ in line 351.\n* line 196: \"which decides which points to query the labels of points\" sounds not correct.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JAZbIDz-OvF", "reviewer": "Reviewer_MhgG", "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.\n", "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.\n- Are these algorithms implementable in practice?\n", "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.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This problem nicely generalizes well-known frameworks.\n- The paper is clearly presented and technically sound.\n\nWeaknesses: \n- No experimental results limit the impact of the work.\n- It is surprising that the absence of potential negative societal impacts is not justified. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CXj5SrleI88", "reviewer": "Reviewer_qdqB", "summary": "Summary:\nThe 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.\n", "questions": "1. Could you please include interpretation of the proposed quantities in early in the paper and give some interpretation of the bounds?\n2. 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. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n1.\tThey 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. \n2.\tPreviously 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.\n3.\tThey 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.\n \n\nWeaknesses:\n1.\tGuarantee 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}.\n2.\tIt 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? \n3.\tI didn’t see a comparison of query complexity with passive sampling. How do these complexities compare against random i.i.d sampling? \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept