Experimental Design for Overparameterized Learning with Application to Single Shot Deep Active Learning
Authors: Neta Shoham
Haim Avron
Venue:  (2021)

Abstract: Abstract The impressive performance exhibited by modern machine learning models hinges on the ability to train such models on a very large amounts of labeled data. However, since access to large volumes of labeled data is often limited or expensive, it is desirable to alleviate this bottleneck by carefully curating the training set. Optimal experimental design is a well-established paradigm for selecting data point to be labeled so to maximally inform the learning process. Unfortunately, classical theory on optimal experimental design focuses on selecting examples in order to learn underparameterized (and thus, non-interpolative) models, while modern machine learning models such as deep neural networks are overparameterized, and oftentimes are trained to be interpolative. As such, classical experimental design methods are not applicable in many modern learning setups. Indeed, the predictive performance of underparameterized models tends to be variance dominated, so classical experimental design focuses on variance reduction, while the predictive performance of overparameterized models can also be, as is shown in this paper, bias dominated or of mixed nature. In this paper we propose a design strategy that is well suited for overparameterized regression and interpolation, and we demonstrate the applicability of our method in the context of deep learning by proposing a new algorithm for single shot deep active learning.

Under review as a conference paper at ICLR 2021
EXPERIMENTAL DESIGN FOR OVERPARAMETERIZED LEARNING WITH APPLICATION TO SINGLE SHOT DEEP ACTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
The impressive performance exhibited by modern machine learning models hinges the ability train such models very large amounts of labeled data. However, since access to large volumes of labeled data is often limited or expensive, it is desirable alleviate this bottleneck by carefully curating the training set. Optimal experimental design is a well-established paradigm for selecting data point to be labeled so to maximally inform the learning process. Unfortunately, classical theory on optimal experimental design focuses on selecting examples in order to learn underparameterized (and thus, non-interpolative) models, while modern machine learning models such as deep neural networks are overparameterized, and oftentimes are trained to be interpolative. As such, classical experimental design methods not applicable in many modern learning setups. Indeed, the predictive performance of underparameterizer models tends to be variance dominated, so classical experimental design focuses on variance reduction, while the predictive performance of overparameterized models can also be, as is shown this paper, bias dominated or of mixed nature. In this paper we propose design strategy that is well suited for overparameterized regression and interpolation, and we demonstrate the applicability of our method in the context of deep learning by proposing a new algorithm for single shot deep active learning.
INTRODUCTION
The impressive performance exhibited by modern machine learning models hinges the ability to train the aforementioned models on a very large amounts of laheled data. In practice, in many real world scenarios, even when raw data exists aplenty, acquiring labels might prove challenging and/or expensive. This severely limits the ability to deploy machine learning capabilities in real world applications. This bottleneck has been recognized early on, and methods to alleviate have been suggested. Most relevant for our work is the large body of research on active learning or optimal experimental design, which aims at selecting data point to be labeled so to maximally inform the learning process. Disappointedly. active learning techniques seem to deliver mostly lukewarm benefits in the context of deep learning.
One possible reason why experimental design has far failed to make an impact in the context of deep learning is that such models are overparameterized, and oftentimes are trained to be interpola- tive (Zhang et al. 2017). i.e., they are trained so that a perfect fit of the training data is found. This raises a conundrum: the classical perspective on statistical learning theory is that overfitting should be avoided since there is tradeoff between the fit and complexity of the model. This conundrum is exemplified by the double descení phenomena (Beikin et al.) 2019b Bartlett et al. 2020), namely when fixing the model size and increasing the amount of training data, the predictive performance initially goes down, and then starts to go up, exploding when the amount of training data approaches the model complexity, and then starts to descend again. This runs counter statistical intuition which says that more data implies better learning. Indeed, when using interpolative models, more data can hurt (Nakkiran et al. [2020a)! This phenomena exemplified in the curve labeled "Random Selection" in Figure]) [ Figure| explores the predictive performance of various designs when learning linear regression model and varying the amount of training data with responses.

---

Under review as a conference paper at ICLR 2021
The fact that more data can hurt further moti- vates experimental design in the interpolative regime. Presumably, if data is carefully rated, more data should never hurt. Unfortu- nately, classical optimal experimental design fo- cuses on the underparameterized (and thus, non- interpolative) case. As such, the theory reported in the literature is often not applicable in the interpolative regime, As our analysis shows (see Section B), the prediction error of interpolative models can either be bias dominated (the first descent phase, i.e., when training size is very small compared to the number of parameters), variance dominated (near equality of size and parameters) or of mixed nature. However, prop- erly trained underparameterizze models tend to have prediction error which is variance domi- nated, classical experimental design focuses on variance reduction. As such, naively using classical optimality criteria, such as V-optimality (the one most relevant for generalization error) or others, in the context of interpolation, tends to produce poor results when prediction error is bias dominated or of mixed nature. This is exemplified in the curve labeled "Classical OED" in Figure
... Clavical DED (variance oriented)
Overparametarioed DED
Rar Rardom dasign
MSE
20
40
60
80
100
120
number
Figure 1: MSE of minimum norm linear inter- polative model. We use synthetic data of dimen- sion 100. The full description is in Appendix E
The goal of this paper is to understand these regimes, and to propose an experimental design strategy that is well suited for overparameterized models. Like many recent work that attempt to understand the double descent phenomena by analyzing underdetermined linear regression, we too use simple linear regression model in our analysis of experimental design in the overparameterized case (however, also consider kernel ridge regression, not only linear interpolative models). We believe that understanding experimental design the overparameterized linear regression case is a prelude to designing effective design algorithms for deep learning. Indeed, recent theoretical results showed a deep connection between deep learning and kernel learning via the so-called Neural Tangent Kernel (Jacot et al.) 2018 Arora al. 2019a Lee al.) (019). Based on this connection, and proof-of-concept, we propose a new algorithm for single shot deep active learning.
Let us now summarize our contributions:
We analyze the prediction error of learning overparameterized linear models for a given fixed design, revealing three possible regimes that call for different design criteria: bias dominated, variance dominated, and mixed nature. We also reveal an interesting connection between overparameterized experimental design and the column subset selection problem (Boutsidis
et al. 2009), transductive experimental design (Yu et al., 2006), and coresets (Sener & Savarese 2018). We also extend our approach kernel ridge regression.
We propose novel greedy algorithm for finding designs for overparameterized linear models. As exemplified in the curve labeled "Overparameterrized OED", our algorithm sometimes able mitigate the double descent phenomena, while still performing better than classical OED (though no formal proof of this fact is provided).
We show how our algorithm can also be applied for kernel ridge regression, and report experiments which show that when the number of parameters in a sense infinite, our algorithm is able to find designs that are better than state of the art.
We propose new algorithm for single shot deep active learning, a scaracly treated problem far, and demonstrate its effectiveness MNIST.
Related Work. The phenomena of benign overfitting and double descent was firstly recognized in
DNNs (Zhang et al. 2017), and later discussed and analyzed in the context of linear models (Zhang
et al. 2017: Belkin et al. 2018 2019a b Bartlett et al., 2020). Recently there is also a growing interest in the related phenomena of "more data can hurt" (Nakkiran et al.) [020aa] Nakkiran 2019 Nakkiran et al. 20206 Loog et al. 2019). A complementary work discussed the need to consider zero negative regularization coefficient for large real life linear models (Kobak et al. 2020).
2

---

Under review as a conference paper at ICLR 2021
Experimental design is well established paradigm in statistics, extensively covered in the literature for the linear case (Pukelsheim) 2006) and the non linear case (Pronzato & Pázman 2013). The application of it to pool based active learning with batch acquisitions was explored by Yu al. (2006)
for linear models and by Hoi et al. (2006) for logistic regression. It was also proposed in the context of deep learning (Sourati al., 2018). Another related line of work is recent work by Haber and Horesh on experimental design for ill-posed inverse problems rroblems(Haber et al. [0088] 2012] Horesh et al. 2010). Active learning in the context of overparameterized learning was explored by Karzand &
Nowak (2020), however their approach differs from ours significantly since it is based on artificially
completing the labels using minimax approach.
I the context of Laplacian regularized Least Squares (LapRLS), which is generalization of ridge regression, Gu et al. (2012) showed rigorously that Yu et al. (2006) criterion justified as a bound for both the bias and variance components of the expected error. We farther show that this bound in some sense tight only if the parameter norm is oneand the noise variance equals the la penalty coefficient. In addition we postulate and show experimentally that in the overparameterized case using a bias dominant criterion is preferable. Another case in which the bias term idoes not vanish is when the model is misspecified. For linear and generalized linear models this case has been tackled with reweighing of the loss function.
A popular modern approach for pool based active learning with batch acquisition is coresets (Sener & Savarese 2018 Geifman & HI- Yaniv [017] Ash et al. 20199) Pinsler et al. 2019). This approach has been used in the context of active learning for DNNs.
2 UNDERPARAMETER V-OPTIMAL EXPERIMENTAL DESIGN
Consider noisy linear response model y = x w + where ~ NN x²) and w E Rd and assume we are given with some data points Xi...., x,, for which we obtained independent responses. y: x w + 6,. Consider the underparameterizee case, i.e. 2 d. and furthermore assume that the set (X1, (XI....,,,) } contains at least independent vectors. The best linear unbiased estimator w arg minw |Xw - yl =
of according to the Gauss-Markov theorem is given by: where X E Randd is a matrix whose rows are X1,..., Xn, = [y (yi...Wu. yn) E R and X* is the Moore-Pensrose pseudoinverse of X. It is well known that w zero mean and covariance matrix o o where M = X X is the Fisher information matrix. This implies that ((x) - y(x) is also a normal variable with zero mean and variance equal to o²x PxTM-'s 'x.
is normal random vector with
Assume also that comes from distribution p. With that can further define the excess risk R( ((W) = Exep [(xT (xTww w - x ]] and its expectation:
E. [R(w)] = Expp [Var, [y(x) - [(x)]] = Ex-p [02xT
Tr (o' 'C,)
(I)
where Cp is the uncentered second moment matrix of p: =p:=EEx [xx]
Eq. motivates the so-called V-optimal design criterion: select the dataset X X,, so that (MM) == Tr (M- is minimized (if we do not have access to C, then it is possible to estimate by drawing samples from p). In doing so, we are trying to minimize the expected (with respect to the noise e) average (with respect to the data x) prediction variance, since the risk is composed solely from it (due to the fact that the estimator is unbiased). As we shall see, this is in contrast with the overparameterized case, in which the estimator is biased.
V-optimality is only one instance of various statistical criteria used in experimental design. In general experimental design, the focus is on minimizing preselected criteria (M) (Pukelsheim) 2006). For example in D-optimal design, (M) = det (et and in A-optimal design (MM) Tr (M-1). However, since minimizing the V-optimality criterion corresponds minimizing the risk, it is more appropriate when assessing the predictive performance of machine learning models.
OVERPARAMETERIZED EXPERIMENTAL DESIGN CRITERIA
In this section we derive an expression for the risk in the overparameterized case, i.c. like Eq. ! but also for the case that n. d (our expressions also hold for n > d). This, in turn, leads to
3

---

Under review as a conference paper at ICLR 2021
experimental design criteria analogous V-optimality, but relevant for overparamterized modeling as well. We design a novel algorithm based on this criteria in subsequent sections.
3.1 OVERPARAMETERIZER REGRESSION AND INTERPOLATION
When n 2 d there is natural candidate for w: the best unbiased linear estimator X* However, when d > n there is no longer a unique minimizer of |Xw - -yl1 212 as there is an infinite amount of interpolating w's, i.. w's such that Xw y (the last statement makes the mild additional assumption that X has full row rank). One natural strategy for dealing with the non-uniqueness is to consider the minimum norm interpolator:
W == arg min || s.t. Xw
is still the case that w X's y. Another option for dealing with non- con-uniqueness of the minimizer is add ridge term, i.e., add and additive penalty A/[w|]3 Let:
W arg min Xw y1l2 + Al/w||
One can show that
WA X
where for we define X (x + holds both for the overparameterized (d 2 n) and underparameterzzed (d 12) case.
(xT++AIX ALa) x (see also Bardow (2008)). Note that Eq. 2
Proposition The function À + X is continuous for all Z
The proof, like all of our proofs, is delegated to the appendix. Thus, also have that the minimum norm interpolator w is equal to wo. and that + WA is continuous. This implies that the various expressions for the expected risk of wa hold also when À = O. So, henceforth analyze the expected risk of w, and the results also apply for w.
3.2 EXPECTED RISK OF WA
The following proposition gives an expression for the expected risk of the regularized estimator Wx- Note that it holds both for the overparameterizee (d 2 n)) and underparameterizeed (d n) case.
Proposition 2. We have
E[R(wA)] = C| (I -I-M M) wIB
2 (c,M M
bias
variance
where MA X FL. M Ala The expectation is with respect to the training noise
The last proposition motivates the following design criterion, which can be viewed as generalization of classical V-optimality:
x x (M) |C (I,M M) w + o (C,M;+M)
For À = 0 the expression simplifies to the following expression:
iPo (M) | (I -I- PM) w 2 (C,M+)
where PM- M'M is the projection the row space of X. Note that when 2 d and X has full column rank, (M) reduces to the variance underparameterized linear regression, so minimizing 4P (M) is indeed generalization of the V-optimality criterion.
Note the bias-variance tradeoff in x (M). When the bias term is much larger than the variance, something should expect for small n, then it make sense for the design algorithm to be bias oriented. When the variance is larger, something we should expect for R d or n 2 d, then the design algorithm should be variance oriented. It is also possible have mixed nature in which both bias and variance are of the same order.
In practice, when is only mildly bigger than is usually better regularize the problem.
4

---

Under review as a conference paper at ICLR 2021
3.3 PRACTICAL CRITERION
As is, ęP is problematic as an experimental design criterion since it depends both on w and on Cp- We discuss how to handle an unknown C, in Subsection 3.5 Here discuss how handle unknown w. Note that obviously w is unknown: it is exactly what we want to approximate! If we have good guess for the true value of w. then we can replace w with in (2x. However, many cases, such an approximation is not available. Instead, we suggest to replace the bias component with an upper bound: ||C* (I M M) w|l < || ||C (I MX M) 1
Let us now define a new design criterion which has an additional parameter / 2 0:
(M)
|C (I
1P &Tr (C,M² M)
bound (divided ||w 12) variance (divided by liwil.)
The parameter& & captures an a-priori assumption on the tradeoff between bias and variance: if we have & o²/l ll. then ępx (M) I /w|B (x. Thus, minimizing (M, corresponds to minimizing an upper bound of Ppx if t is set correctly.
Another interpretation of x (M) is as follows. If assume that AO T then
En x = >2 1 (I 1--M²M 11 o (c,M²* M)
so we set = = /2/ then 2 = E (M)] so minimizing (M. corresponds to minimizing the expected expected risk if set correctly. Again, the parameter captures an a-priori assumption on the tradeoff between bias and variance.
Remark 1. One alternative strategy for dealing with the fact that w is unknown is to consider a sequential setup where batches are acquired incrementally based on increasingly refined approxima- tions of w. Such strategy falls under the heading of Sequential Experimental Design. In this paper, we focus on single shot experimental design. i.c examples are chosen be labeled once. We leave sequential experimental design to future research. Although, we decided to focus on the single shot scenario for simplicity, the single shot scenario actually captures important real-life scenarios.
3.4 COMPARISON OTHER GENERALIZED V-OPTIMALITY CRITERIA
Consider the case of À 0. Note that we can write: ( = | (I PM) + (1+++TT(CC,*))) Recall that the classical V-optimal experimental design criterion is Tr (C,M-)). which only applicable if n 2 d (otherwise, M is not invertible). Indeed, if 2 d and M is invertible, then PM = Ia and (M) is equal to Tr (C,M-) up to a constant factor. However, M is not invertible if n d and the expression Tr (C,M does not make sense.
One naive generalization of classical V-optimality for n < would be to simply replace the inverse with pseudoinverse, i.e. Tr (C,M** This corresponds to minimizing only the variance term, i.e. taking + co. This is consistent with classical experimental design which focuses on variance reduction, and is appropriate when the risk is variance dominated.
Another generalization of V-optimality can be obtained by replacing M with its regularized (and invertible) version M, M + μIl for some chosen μl > 0, obtaining Tr (C,MM.)) This exactly the strategy employed in transductive experimental design (Yu al. (006), and it also emerges in Bayesian setup (Chaloner & Verdinelli] 1993). One can try to eliminate the parameter ju by taking the limit of the minimizers when μ 0. The following proposition shows that this is actually equivalent to taking t = 0.
Proposition 3. For compact domain Ω Raxdd of symmetric positive semidefinite matrices:
lim argmin Tr (C,M,)) C argmin Tr (C, (I-PM)) Men
#0 MEn
We see that the aforementioned generalizations of V-optimality correspond to either disregarding the bias term (t- oo) or disregarding the variance term (t 0). However, using (M) allows much better control over the biri-ner tradeoff (see Figure [)
Let us consider now the case of À > 0. We now show that the regularized criteria Tr (C,M,,)) used in transductive experimental design (See Proposition 3 when μ À corresponds to also using = X.
5

---

Under review as a conference paper at ICLR 2021
Proposition 4. For any matrix space 92 À > 0: argminxen Tr (C,M))) argminxen PA (M)
So, transductive experimental design corresponds to specific choice of bias-variance tradeoff. Another interesting relation with transductive experimental design is given by next proposition which is small modification of Theorem 1 due to Gu et al. (2012).
Proposition 5. For any X > 0 and 1 2 0: (M) S (A (A+1) Tr (C,
In the absence of a decent model of the noise, which is a typical situation in machine learning. Prop. 5 suggests the to perhaps minimize only Tr (C,M,²) without need to set t. However, this approach may be suboptimal in the overparameterized regime. This approach implicitly considers Prop. 4 which in a bias dominated regime can put too much emphasis on minimizing the variance. A sequential approach for experimental design can lead to better modeling of the noise, thereby assisting in dynamically setting during aqquisition-learniing cycles. However, in a single shot regime, noise estimation is difficult. Arguably, there exists better values for t than using default rule-of- t = X. In particular, we conjecture that t = 0 is better rule-of-thumb then / X for severely overparameterized regimes as suppresses the potential damage of choosing a too large À and is reasonale also if' À is small (since anyway we are in a bias dominated regime), so we can focus on minimizing the bias only. In the experiment section we show an experiment that supports this assumption. Notice that t oo corresponds to minimizing the variance, while t = 0 corresponds to minimizing the bias
(see
3.5 APPROXIMATING C,
Our criteria so far depended on Cp. Oftentimes Cp is unknown. However, it can be approximated using unlabeled data. Suppose we have m unlabeled points (i.e. drawn form p), and suppose we write them the rows of V Rmxdd Then E [m V =Cp Thus, we can write
mupx (M) R 4b (M) = IV (La - Mş w 2 + T (VM,'MV'). A20
and use 1 (M) instead of yo (M). For minimum norm interpolation we have
do (M) = IV (Ia - PM) w 1 + T' (VM*v").
Again, let us turn this into practical design criteria by introducing an additional parameter &:
- (1a-MMM) l - (Tr (VM,'MV")
( = IV
(3)
4 POOL-BASED OVERPARAMETERIZE EXPERIMENTAL DESIGN
In the previous section we defined design criteria x and txx, that are appropriate for overparame- terized linear regression. While one envision situation in which such are free to choose X so to minimize the design criteria, in much more realistic pool-based active learning we assume that are given in advance a large pool of unlabeled data XI,..., Xm- The training set is chosen to be a subset of the pool. This subset is then labeled, and learning performed. The goal of pool-based experimental design algorithms is to chose the subset to be labeled.
We formalize the pool-based setup as follows. Recall that to approximate C, we assumed we have pool of unlabeled data written as the rows of V E mxd We assume that V serves also as the pool of samples from which X is selected. For matrix A and index sets S [m], T C [d], let As. be the matrix obtained by restricting to the rows whose index is in S and the columns whose index is in T. If : appears instead of an index set, that denotes the full index set corresponding that dimension. Our goal is to select a subset S of cardinality n such that vx, (V'. Vs.) is minimized (i.e., setting
X = V s.). Formally, we pose following problem:
Problem 1. (Pool-based Overparameterized V-Optimal Design) Given a pool of unlabeled examples V E m regularization parameter À 2 0, bias-variance tradeoff parameter 2 and design
size n, find minimizer of scim),
min
JA ( S.. V..).

---

Under review as a conference paper at ICLR 2021
Problem is generalization of the Column Subset Selection Problem (CSSP) (Boutsidis al. 2009). In the CSSP, we are given matrix E RR and target number of columns n, and our goal is to select subset 7 which is minimizer of
[imm), [7|= |1(Ta U. U,,
min
When À 0 and / 0, Problem reduces to the CSSP for U VT. The = case is also somewhat related to the coresel approach for active learning Sener & Savarese (2018): Pinsler et al. (2019) Ash et al. (019)); Geifman & Yaniv 2017). See Appendix
OPTIMIZATION ALGORITHM
In this section we propose an algorithm for overparameterized experimental design. Our algorithm is based on greedy minimization of a kernalized version of vx.+ Vs..). Thus, before presenting our algorithm, we show how to handle feature spaces defined by a kernel.
Kernelization. If [S] S.s (Vs, V + (lss (v. Vs..) = Tr
< and Vs, has full row rank we have (Vs.)ž =
which allows us to write
I - 2V'. (Vs. + AlIs) Vs. |vr)
+Ir (VV3: (Vs. + (4p1 -1 Vs. Vss.Vo. +1iss) V*..v))
+TT VV (Vs. + Mss) V..V")
Let now K = VVT E Rmxm Then Vs V S. = Ks.s and VV S₁: = K..... Since Tr (K) is constant, minimizing (V Vs.)) is equivalent to minimizing
Jx,((S)= = Tr K (Ks,s + si) (-21 Ks.s (Ks.s + (11s ) )-1 ( (Ks,s (lss) (
KT,s)
(4)
For = we have a simpler form: (o,((S) = Tr S s.s + tK 5.S k..s)
Interestingly, when and minimizing (o, is equivalent to maximizing the trace of the Nystrom approximation of K. Another case for which Eq. (4) simplifies is t = X (this equation was already derived in Yu al. (2066))
JA, Tr (-K,, (Ks,s + (sss -
Eq. 4 allows us, via the kernel trick, to perform experimental design for learning of nonlinear models defined using high dimensional feature maps. Denote our unlabeled pool of data by Zi..... Zm, R and that we are using feature map á : R
where H is some Hilbert space (e.g.. H. Rd),, i.c. the regression function is y(2) = (Ø(z), w) H. We can then envision the pool of data to be defined by x, = -22)), 1, m. we assume we have kernel function k(x, z) (((x), ((z)) x then (S) can be computed without actually forming X Xm since entries in K can be computed via k. is the Reproducing Kernel Hilbert Space then this is exactly the setting that corresponds to kernel ridge regression (possibly with a zero ridge term).
IRD x R - TRD such that
Greedy Algorithm. We now propose our algorithm for overparameterized experimental design, which is based on greedy minimization of (S). Greedy algorithms have already been shown to be effective for classical experimental design (Yu et al. 2006 Avron Boutsidis) 2013 Chamon & Ribeiro 2017). and it is reasonable assume this carries to the overparameterized case.
Our greedy algorithm proceeds as follows. We start with ( 0. and proceed in iteration. At iteration j. given selected samples SU-1) C [m] the greedy algorithm finds the index 200 [m] - 5(i-) that minimizes JA, (S6-1) u fz60p) We set Sú: + s(i u (200}. We continue iterating until 8() reaches its target size and/or (S) is small enough.
7

---

Under review as a conference paper at ICLR 2021
The cost of iteration j in naive implementation is O ((m j) (mj² 2 )))) Through careful matrix
algebra, the cost of iteration can be reduced to O((m - (m( + +))) ( (since j S m). The cost of finding a design of size n is then (mm²(n² + D)) assuming the entire kernel matrix K is
formed at the start and a single evaluation of le takes OD). Details are delegated to Appendix C
SINGLE SHOT DEEP ACTIVE LEARNING
There are few ways in which our proposed experimental design algorithm can be used in the context of deep learning. For example, one can consider sequential setting where current labeled data are used to create linear approximation via the Fisher information matrix at the point of minimum loss (Sourati et al. 2018). However, such a strategy falls under the heading of Sequential Experimental previously stated, in this paper we focus single shot active learning, i.e. no labeled data is given neither before acquisition nor during acquisition (Ynn & 2019).
Design, and,
In order to design algorithm for deep active learning, we leverage recent breakthrough in theoretical analysis of deep learning the Neural Tangent Kernel (NTK) (Jacot et al. 2018 Lee et al. 2019 Arora et al. 22199). A rigorous exposition of the NTK is beyond the scope of this paper, but short and heuristic explanation is sufficient for our needs.
Consider a DNN, and suppose the weights of the various layers can be represented in vector E RR. Given a specific 0, let fe(-) denote the function instantiated by that network when the weights are set to The erucial observation is that when the network is wide (width in convolutional layers refers to the number of output channels) enough, we use a quadratic loss function (i.e., (x)) y) = f/((fo(x)
)) and the initial weights Og are initialized randomly a standard way, then when training the DNN using gradient descent, the vector of parameters 0 stays almost fixed. Thus, when we consider 0, O2.... formed by training, first-order Taylor approximation is:
fo. fo, (x) Volo, (x)=(0, 0o)
Informally speaking, the approximation becomes an equality in the infinite width limit. The Taylor approximation implies that if we further assume that Og is such that fe, (x) O, the learned prediction function of the DNN well approximated by the solution of a kernel regression problem with the (Finite) Neural Tangent Kernel, defined
f (x, 2) = VoJa. (x) (o)o.
We remark that there are few simple tricks to fulfill the requirement that fe, (x) 0.
has also been shown that under certain initialization distribution, when the width goes to infinity, the NTK ky,,, converges in probability sense, instead of training a DNN on a finite width network, we can take the width to infinity and solve kernel regression problem instead.
deterministic kernel ky the infinite NTK. Thus, in
Although, is unclear whether the infinite NTK can be an effective alternative to DNNs in the context of inference, one can postulate that it can be used for deep active learning. That is, in order to select examples to be labeled, use an experimental design algorithm for kernel learning applied to the corresponding NTK. Specifically, for single shot deep active learning, we propose to apply the algorithm presented in the previous section to the infinite NTK. In the next section we present preliminary experiments with this algorithm. We leave theoretical analysis future research.
EMPIRICAL EVALUATION
Transductive vs Tb.0 Criterion (i.e., variance-oriented vs. bias-oriented designs) Tx.o and Ax. simplified version of t i criterion. Our conjecture is that in the overparameterized regime Ux.o is preferable, at least for relatively large X. Table 1 empirically supports our conjecture. In this experiment, we performed an experimental design task on 112 classification datasets from UCI database (similar to the list that was used by Arora et al. (2019b) Learning is performed using kernel ridge regression with standard RBF kernel. We tried different values of À and checked which criterion brings to smaller classification error test set when selecting 50 samples. Each entry in Table counts how many times VA.A won oox, won or the error was the same. We consider an equal error when the difference is less the 5%.
8

---

Under review as a conference paper at ICLR 2021
Table 1: d'x.o vs A on UCI datasets. We generated designs on 112 classification datasets. Each cell details the number of datasets in which that selection of É was clearly superior the other possible choice, or the same (for the "SAME" column).
AA better
Ax is better
SAME
0.001
5
8
99
0.01
7
9
96
0.1
16
16
80
1.0
21
43
48
10.0
19
68
25
Deep Active Learning Here report preliminary experiments with the proposed algorithm for single shot deep active learning (Section 6). Additional experiments are reported in the appendix. We used the MNIST dataset, and used the square loss for training. As for the network architecture, used a version of LeNet5 (LeCun et al. 1998) that widen by factor 8. we refer to this network "Wide-LeNet5".
The setup is as follows. We use Google's open source neural tangents library (Novak et al. 2020) to compute Gram matrix of the infinite NTK using 59,940 training samples (we did not the full 60,000 training samples due to batching related technical issues). We then used the algorithm proposed in Section to incrementally select greedy designs of up 800 samples, where set the parameters to À
O. We now trained the original neural network with different design sizes, each design with five different random initial parameters. Learning was conducted using SGD, with fixed learning rate of 0.1, batch size of 128, and no weight decay. Instead of counting epochs, simply capped the number of SGD iterations to equivalent 20 epochs of the full trainning set. We computed the accuracy of the model predictions on 9963 test-set samples (again, due to technical issues related to batching).
Figure 2 report the mean and standard devia- tion (over parameters initialization) of the final accuracy. We consistent advantage in terms of accuracy for designs selected via algorithm, though expected the advantage shrinks as the training size increase. Notice, that
054
0.88
0a6
n82
comparing the accuracy of our design with 400 training samples, random selection required as many 600 for Wide-LeNet5 achieve the same accuracy!
080
Our design (t= = 0) Corcsct (k centers)
Two remarks are in order. First, to prevent over- fitting and reduce computational load, at each iteration of the greedy algorithm we computed the score for only on subset of 2000 samples from the pool. Second, keep the experiment simple we refrained from using tricks that en-
design
100
training
Figure 2: Single shot active learning with Wide- LeNet5 model on MNIST.
sure fe. =

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, pp. 8141 -8150, 2019a.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Har- nessing the power of infinitely wide deep nets on small-data tasks. arXiv preprint 1rXiv:1910.01663, 2019b. 7
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv: 1906.0367,, 2019. 4
Haim Avron and Christos Boutsidis. Faster subset selection for matrices and applications. SIAM Journal on Matrix Analysis and Applications, 34(4):1464-1499 2013. [
André Bardow. Optimal experimental design of ill-posed problems: The METER approach. Comput- ers Chemical Engineering, (2(1-2): 1::::::1::::: 124, 2008. 3.1
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020. ISSN 0027-8424. doi: 10. 10.1073/pnas. 19073781 19077/77 17. BtLhttps::/ /ttp::///wwww....
www. wtwp//wwwwpppp..p...o..o...a...m https//////cooteeeeeea////////0
22/190737811
G
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to
understand kernel learning. volume 80 of Proceedings of Machine Learning Research, pp.
541-549, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http1
//proceedings. mlr press http://///eeellaa...e html
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 158544 2019a. ISSN 0027-8424. doi: 10.1073/pnas. 193007// 16. URL
https: /twpw//www////////////////// http///wwwp......m.omm.../..a... pnas. org/ wtt.///nntttttccc http://ooonoooe/////////////////
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv
preprint 1xXiv:9903.0757/ 2019b. П
Christos Boutsidis, Michael W. Mahoney, and Petros Drineas. improved approximation algorithm for the column subset selection problem. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pp. 968-977, USA, 2009. Society for Industrial and Applied Mathematics.
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical Science, pp. 273-304, 1995, 3.4
Luiz Chamon and Alejandro Ribeiro. Approximate supermodularity bounds for experimental design. In Advances Neural Information Processing Systems, pp. 5403-5412, 2017. 5
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. arXiv preprint arXiv: 1703.02910, 2017.
G
Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprint
arXiv:1711.00941, 2017. [
Quanquan Gu, Tong Zhang, Jiawei Han, and Chris Ding. Selective labeling via error bound mini-
mization. Advances in neural information processing systems, 25:323-331 2012.
I 3.4
Eldad Haber, Lior Horesh, and Luis Tenorio. Numerical methods for experimental design of large- scale linear ill-posed inverse problems. Inverse Problems, 24(5)055001,, 2008.
[
Eldad Haber, Zhuojun Magnant, Christian Lucero, and Luis Tenorio. Numerical methods for A-optimal designs with a sparsity constraint for ill ill-posed inverse problems. Computational Optimization and Applications, 52(1):93-311, 2012.
10

---

Under review as a conference paper at ICLR 2021
Steven CH Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu. Batch mode active learning and its application to medical image classification. In Proceedings of the 23rd International Conference on Machine Learning, pp. 417-424. ACM, 2006. [
Lior Horesh, Eldad Haber, and Luis Tenorio. Optimal experimental design for the large-scale nonlinear ill-posed problem of impedance imaging. Large-Scale Inverse Problems and Quantification of Uncertainty. pp. 273-290, 2010.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances Neural Information Processing Systems, pp.
8571-8580, 2018.
T 6
Mina Karzand and Robert D Nowak. Maximin active learning in overparameteriized model classes. IEFE Journal on Selected Areas in Information Theory, 2020.
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. Optimal ridge penalty for real-world high- dimensional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Rexearch, to appear, 2020. [
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffnnr. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998. 7
Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online]. Available:
2. 2010. D
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, pp. 8572-8583, 2019.
Marco Loog, Tom Viering, and Alexander Mey. Minimizers of the empirical risk and risk monotonic- ity. In Advances in Neural Information Processing Systems, pp. 7476-7485, 2019.
Preetum Nakkiran. More data hurt for linear regression: Sample-wise double descent. arXiv preprint arXiv:1912.07242 2019. [
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, OpenReview.net, 2020a. BtL/tttts:///peeeeeeee
net wtrtt//orummicim Blg
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint arXiv:2003.01880 2020b. R
Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl- Sib--Dickttein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in Python. In International Conference on Learning Representations, 2020. URL htlttttss//ggthutt com/
google heteeeeneraalll - tangents
7
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-- Bayesian batch active learning as sparse subset approximation. In Advances Neural Information Processing Systems, pp. 6356-6367, 2019.
Luc Pronzato and Andrej Pázman. Design of experiments in nonlinear models. Lecture Notes in Statistics, 212, 2013.
Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006. I
Tyrrlll Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009. I
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https::/openreviiet net wwt.:/wwwwwww..tttiettcoo
wow.forrddoooooo Tuk- Rw
B
D

---

Under review as a conference paper at ICLR 2021
Jamshid Sourati, Ali Gholipour, Jennifer G Dy, Sila Kurugol, and Simon K Warfield. Active deep learning with Fisher information for patch-wise semantic segmentation. In Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support, pp. 83-91. Springer, 2018.
Yazhou Yang and Marco Loog. Single shot active learning using pseudo annotators. Pattern Recognition, 89:22-31, 2019.
Kai Yu, Jinbo Bi. and Volker Tresp. Active learning via transductive experimental design. In Proceedings of the 23rd International Conference on Machine Learning, pp. 1081-1088. ACM, 2006.
5 D
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. /ttp::ttt/////eeeeeeii net wett/forrmi..dd-yyS@oaee
A PROOFS
A.1 PROOF PROPOSITION I
Proof. We prove the case of d 2 (for X E gaxd), The proof for d < is similar. It is enough to show that limx-0 =x* For scalar 7
7 * 0
0
7 0
Let X UEV" be the SVD of X with
0
0
Σ =
E Rdxn
0d
where .,,..., Ja are the singular values of X. We have X V where we have
o
Σ+
On the other hand, simple matrix algebra shows that
(o + 1)+
(o + X) Do
= =
UT
(5)
0
0
Now clearly for i = ,,..,,d
lim (a + A a; = 0, x
So the limit of the diagonal matrix in Eq. 5 when À + 0+ is E Since matrix product a linear, and thus continuous function, the proposition follows.
12

---

Under review as a conference paper at ICLR 2021
A.2 PROOF OF PROPOSITION 2
Proof. Let us write
c]
Cn
so
y Xw +e.
Thus,
WA Xjy x XiE= MjMMM + Xje
and
x w x" =I, M x'
For brevity we denote Pix = La -M,M. Note that this is not really projection, but rather (informally) "soft projection", So:
--'---ww w''' X ) x + " x +
-
Finally,
E [[[W))]
= Ex,6
x w - x wx)
Eg Ex x T w x ww) 2 [c]
Ex w T ppp Xxx' pP P w wxw.xxxxx'xxXxxx e (x,, X c]]
E,
E, PPA
w'Pl C, lxw o (XX3
|| T T (C,x
I [I - M M) w 2/2 Tr (c,M, M
A.3 PROOF OF PROPOSITION 3
Before proving Proposition 3 we need the following definition and theorem.
Definition 1. For a family of sets {Ax A C Rd we write lim Ax A if w E A if and only if there exists sequence X, - > and a sequence w,, large n.
where W, Ax., for sufficiently
Theorem 1. (A restricted version of Theorem 1.17 in RRockafellar & Wets (2009)) Consider f Q V R where Q C Ted and V are compact and f is continuous. Then
lim argmin f (w, A) argmin f (w.X). X
Proof. Suppose w E limx-x argmin (ww,)) A). The implies that there exits An - such that Wn E argmin If (w, >n)) and w, - w. From the continuity of we have that f (w.,, An) -> f (w, Now suppose for the sake of contradiction that & argmin f (w, XX) So there is such that f(u, X) < < <[(w X). From the continuity of À there is no such that for all no f(u, An) < f (w, X). Then from the continuity of f in w, and wn - w, for sufficiently large n, (W 2n) > fl, Xn), which contradicts w,, E argmin f (w, Xn)
We ready prove Proposition 3
13

---

Under review as a conference paper at ICLR 2021
Proof. Consider the function f(M, (b) = 'Tr (C,
J(M 14) = [Tr (,C, (1)=
4>0 0 (T-
==
defined over Ω R20 where Rz0 denotes the set of non-negative real numbers. Note that this function is well-defined since a of positive semidefinite matrices.
We now show that f is continuous. For μ > O it is clearly continuous for every M, so we focus on the case that μ 0 for an arbitrary M. Consider sequence > 3 fbn - (where R50 is
the set of positive reals) and f? M, + M. Since Q is compact, M E Q. Let us write spectral decomposition of M,, (recall that set of symmetric matrices)
M U
where A, is diagonal with non-negative diagonal elements (recall that Q is set of positive definite matrices). Let M UAU be spectral decomposition of M. Without loss of generality we may assume that U, n + and An - A. Now note that
(M, + 1n, -M, M, (A + A
One can easily show that (An + pn I) 1 + sign(A) where sign is taken entry wise, which implies that (M, + InII MM, + U (A) since matrix multiplication is comtinuous. Next, note that M = UA* Usign so (M, + 1n + M The Woodbury formula implies that
Nmn CM,, + pn,1)= C, (I- (M, + pn
so the continuity of the trace operator implies that
Tr (M,, + pnr Tr (C, (I - (M, + (n))- + (C MMM)) which shows that f is continuous.
Theorem now implies the claim since for μ > we have
argmin Tr (C,M,")) argmin Tr (μC,M, MeR
Men
A.4 PROOF OF PROPOSITION 4
Proof. Let A = (I- (M + ML - 'M) + A(M+ M,, (M Tr AC,A. We now
have for À 0:
A
(I (M+AL)) (MM--(MM AL. + A(M+ 1 + -LL)~
X² (M ALA) XM X A
A(M + AIa)=² (M+ x
A X
80:
Tr (C,A) = XTr (M+
Since À > 0 it doesn't affect the minimizer.
B RELATION TO CORESETS
The idea the coreset approach for active learning is to find an S such that
C(S)
-
Σ
m
1xx, Vi (S)
1
Σ
(xx, ys SS)
S
m
14

---

Under review as a conference paper at ICLR 2021
is minimized. In the above l(x. [S) is loss function, and the conditioning S denotes that the parameters of the loss function are the ones obtained when training only using indices selected in S is not relevant (since the parameters do not affect
S. For linear regression the conditioning the loss). The motivation for minimizing ((S) is that the expected test loss can be broken to the generalization loss the entire dataset (which is fixed), the training loss (which is 0 in the presence of overparamettrization)) and the coreset loss.
One popular approach to active learning using coresets is to find coverset. A d-coverset of set of points A is a set of points B such that for every x E A there exists y E B such that ||x yll S (other metrics can be used as well). Sener and Savarese Sener Savarese (2018) showed that under suitable Lipschitz and boundness conditions, if {x hes is d-coverset of [x; [E(m) then
C(S) < O + m //))
which motivates finding a S that minimizes ös, where ós denotes the minimal å for which hies a 8-coverset of [xm]-
Since for a x in the training set (which a row of V) [x( PM) for M V V is the minimal distance from x to the span of {x, hes. and as such is always smaller than the distance between and it's closest point in {xi is easy to show that
Y Vo.o S, Vs.) < 85-
Thus, minimizing 6s can be viewed as minimizing an upper bound on the bias term when = 0.
Under the setup of the experiment in Section 7 we tried replace design with k-centers algorithm, which often used as approximated solution for the problem of finding S that minimizes 6g. How ever the result we got were much worse then random design, probably due the problem of outliers. We did not try more sophisticated versions of the k-center algorithm that tackle the problem of outliers.
C DETAILS ON THE ALGORITHM
We discuss the case of The case of requires some more careful matrix algebra, so we omit the details.
Let us define
A; = K $6) (G) B, = K. (0)) S0)
and note that JA (SU) = - Tr (A, - -)))). We also denote by A, and B, the matrices obtained from A, and B, (respectively) by adding zero row and column.
Our goal efficiently compute (S U (i)) for any E [m] S(i-1) so find j00 and form SU), We assume that at the start of iteration j we already have in memory A₁-1 and Bj-1. We show later how to efficiently update A, and Bj once we have found 20), For brevity, let us denote
sli) = S (0111)10)) u
Az = K
B
KT
K
sin son
SS
Let us also define
Cy-1= BL==BJ-AA-- B
E,-1 = =
Again, we assume that at the start of iteration j we already have in memory C,-1. Dy-1 and E,-1, and show how to efficiently update these.
Let
0j-1
W J4
KT K. S0-1
K
K.
K
and note that
B BB- W ji- Also important the fact that W j has rank 2 and that finding the factors takes O(mj) discounting the cost of computing columns of K. Next, let denote
Tss (Ka KT S0), Aj- K Ks)),)
15

---

Under review as a conference paper at ICLR 2021
and
2₁i Tj
A A K sto K Aj-1
StD
-Aj-
K S0n,5 j-1
1
A well known identity regarding Schur complement implies that
Aj: 1 Q2
Also important is the fact that Q5 has rank 2 and that finding the factors takes O discounting the cost of computing entries of K.
So
(A,( = -T (B): - tA).))
Tr (B,-1 -/
12x Tr. (B,- + WH)(A WA)+ ( W ( + Qr(A5-1)
Tr [C-1++ ( Qz1)
W
+/Tr (B y + 4 Q(1)
+Tr (W. 03 A Qr.A,-1)
Now, Cj-1 is already in memory so Tr (Cj-1) can be computed in O(j), Q2 has rank 2 and By in memory Tr 1 can be compute in O(j²), and W ji has rank and Ay-1 is in memory Tr [W,(A + Q,i)) be computed in O(j²). Using similar rationale, all the other terms of (5 can also be computed in O(j) 0(j"), and overall (x, can be computed in O()²). Thus, scanning for ((i) takes (((m-j))
Once (6] has been identified, we set 86) = sl
(G)) A A Joo A Qjo and B, = B |Do
By-1 + W Wesnn. The last two can be computed in O(j²) once form Q and W Win- Computing the factors of these matrices takes O(mj). As for updating Cj-1, we have
C, C J30 G + W ja A A
jaio 2a0
where Čj-1 is obtained from Cj-1 be adding zero row and column. Since Cj-1 is in memory and both Qjat:: and W (o) have rank O(1), we can compute C, is O(j2). Similar reasoning can be used to show that Dj and E, can also be computed in O(j²).
Overall. the cost of iteration j is O((m ()m )²)) ((m²j) (since j S m). The cost of finding design size is O(m² (n + D)) assuming the entire kernel matrix K is formed the start and a single evaluation of takes O(D).
D EXPERIMENTAL PARAMETERS EXPLORATION AND COMPARISON TO TRANSDUCTIVE EXPERIMENTAL DESIGN
In this subsection we report experiment we set the ridge term to 0, so we are using interpolation). We use the MNIST handwriting dataset (LeCun al., 2010), where the regression target response was computed by applying one-hot function on the labels 0-9. Nevertheless, we still measure the MSE, and do not use the learnt models as classifiers. We use the RBF kernel k(x, z) exp(->lix
of experiments on kernel ridge regression setup (though one
z ( with parameter 7 = 1/784. From the dataset, we used the standard test set of 10000 images and selected randomly another 10000 images from the rest the 60000 images as a pool. We used our proposed greedy algorithm to select training of sizes to 100. We two values of A: À (interpolation), and À 0.752. The optimal À according to cross validation was the smallest we checked so we just used À = However, in some cases having À > 0 is desirable from computational perspective, e.g. it caps the condition
16

---

Under review as a conference paper at ICLR 2021
A- 0.0
0-0.7''
24-
Greasy Alg tmm,
Greacy Algar thn, L 0.75
10-
fandom Dedign
Gready Algz tmn, Lw0.2
3.0
Seaacy Algor thm, r-
fandom Dis
6.7
0.6
5.-
03-
102
40
Figure 3: Kernel regression experiments on MNIST.
number of the kernel matrix, making the linear system easier to solve. Furthermore, in real world scenarios, oftentimes we do not have any data before we start to acquire labels, and if we do, it is not always distributed as in the test data, so computing the optimal À can be challenging.
Results are reported in Figure The left panel show the results for À = O. We report results for t == 0 and = 0.5. The choice of t worked better. Kernel models with the RBF kernel are highly overparameterized (the hypothesis space is infinite dimensional), so we expect the MSE to be bias dominated, in which case small t (or t = 0) might work best. Recall that the option of À = t 0 is equivalent to the Column Subset Selection Problem, is the limit case of transductive experimental design (Yu al. 2006), and can be related the coreset approach (specifically [Sener & Savaresel (2018)
The case of À 0.75. is reported in the right panel of Figure We tried and f À 0.75². Here too, using a purely bias oriented objective (i.c., t = 0) worked better. Note that this is in contrast with classical OED which use variance oriented objectives. The choice of t worked well, but not optimally. In general, in the reported experiments, and other experiments conducted but not reported, it seems that the choice of I X, which is, as we have shown in this paper, equivalent to transductive experimental design, usually works well, but is not optimal.
E EXPERIMENTAL SETUP FOR RESULT REPORTED IN FIGURE
First, w E R 100 was sampled randomly from AN I). Then pool (the set from which we later choose the design) of 500 samples and a test set of 100 samples were randomly generated according to x ~ (0, E), ~ NO0, T) and y = x w + where Σ E IR 100x100 is diagonal with Mi = exp(-2.51110)), and σ = 0.2. We then created three incremental designs (training sets) of size 120 according to three different methods:
Random design at each iteration we randomly choose the next training sample from the remaining pool.
Classical OED (variance oriented)- at each iteration we choose the next training sample from the remaining pool with a greedy step that minimizes the variance term in Eq. (3).
Overparameterized OED at each iteration we chose the next training sample from the remaining pool with greedy step that minimizes Eq. 3 with À 0 and o²
With the addition of each new training sample we computed the new MSE achieved on the test set with minimum norm linear regression.
F EXPERIMENT: SINGLE SHOT ACTIVE LEARNING FOR NARROW NETWORKS
In Figure we compare the result of our method on LeNetS with the result of our method on Wide-L.NNe5.. We see that while the result
17
0.28
0.4

---

Under review as a conference paper at ICLR 2021
the wide version generally better, both for random designs and our design, our method brings consistent advantage over random de- sign. In both the narrow and the wide versions it requires about 600 training samples for the random design to achieve the accuracy achieved using our algorithm with only 400 training sam- ples!
The parameters used by our algorithm to select the design are À = t = 0. For the network train- ing we used SGD with batch size 128, leaning rate 0.1 and regularization. The SGD number iterations equivalent to 20 epochs of the full trainning set.
G SEQUENTIAL VS SINGLE SHOT ACTIVE LEARNING
While in this work focus the single shot active learning, interesting question is how does it compare to sequential active learning. In sequential active learning we alternate between model improving step and step of new labels acquisition, This obviously gives advantage sequential active learning over single shot active learning, as the latter a restricted instance of the former.
As still do not have sequential version of our algorithm to compare with, chose to experimen- tally compare our single shot algorithm with the classical method of uncertainty sampling (Bartlett et al. 2020). This method has proved be relatively efficient for neural networks (Gal et al. (017)) Uncertainty sampling based active learning requires computing the uncertainty of the updated model regarding each sample in the pool. As such, this approach is sequential by nature.
Usually uncertainty sampling derived in connection to the cross entropy since that case the network output after the softmax layer can be interpreted x, which we symbolize as p. (x). The uncertainty score (in one common version) is then given by
probability estimation of y i given
max (x). (E[L]
Because we use the square lose, we need to make some adaptation for the way of (x)x) is computed. Considering the fact that the square loss is an outcome of maximum likelihood model that given assumes y ~ (x)(x), Ir), it make sense to use
ps (x) = (2r) &e 1o-1)y----000
where y; is the onehot vector of i.
Figure 5 shows a comparison between the ac- curacy achieved with our single shot algorithm and the sequential active learning on MNIST with LeNet5. The acquisitions batch size of the sequential active learning were set to 100. Our algorithm ran with
Single aztive koaming Sequantial activw learning
0.90
= 0. For the network training we used SGD with batch size 128, lean- ing rate 0.1 and no 12 regularization. The SGD number iterations is equivalent to 20 epochs of the full train set.
Sccuracy
0.88
0.86
0.84
0.82
Initially, selection procedure shows clear advantage. However, once the training set grows large enough, the benefit of sequential setup starts to kick-in, the sequential algorithm starts show superior results. This experiment moti- vates further development of sequential version of our algorithm.
0.78
180
200
300
-000
500
600
700
8D0
training sel sizw
Figure 5: Single shot active learning vs sequential active learning. MNIST and (standard) LeNet5
18


Reviews:
[{"review_id": "sZ0kXGkTwWo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This authors analyzed the V-optimality criterion of the experimental design for the ridge regression setting, proposed a greedy algorithm to optimize the criterion, and connected with the infinite neural tangent kernel. \n\nThe paper contains a number of interesting results, particularly in connecting the V-optimality criterion with the bias-variance trade-off in predictive modeling. However, the problem setting has some overly strong assumptions, such as prefixed design and iid errors, which can make the solutions trivial and not very useful in practice.\n\nI don't recommend the paper to be accepted in its current form for the following reasons:\n\n1. I think the main results of the paper in Section 3-5 concerns a conventional problem: Experimental design for the ridge regression. They do not provide a solution aligned with the main motivation, bridging experimental design and deep learning.\n2. The theoretical analysis did not provide sufficient new insights. It actually confuses me that it introduces an additional parameter t on page 5, without exploring its relationship with the original regularization parameter lambda. \n3. The connection with deep active learning is not sufficiently explained. Also the evaluation task looks overly simple and uses a trivial baseline; I would expect at least a comparison with another active learning algorithm, for example, using the coreset approach.\n\nOther specific concerns:\n\n-  I find the expression \"single shot active learning\" confusing. Does it mean active learning with a prefixed (hence unsupervised) design?\n- The last sentence of Sec 2, para 1 is incorrect. Actually, it contradicts Eq 1. \n\n\nIn general, I think that the paper can be improved with a more focused contribution statement, and better connecting the results with the claimed contributions. The paper's relevance of deep active learning is unconvincing to me; probably the results are more suitable for a different conference.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kyit56oPyU6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an active learning (AL) strategy that is based on both of variance and bias of the linear model unlike the classical variance-based criteria. The paper claims that, for over-parameterized setting, incorporating the bias information is particularly important, and further, shows a kernelized extension and a greedy calculation strategy.\n\nThe paper focuses on an important problem of active learning, and is written clearly. The approach is reasonable, and the method would be easy to implement. However, technical significance would be somewhat weak. The derived bound of the expected error is quite simple, though it is ok but an important unknown constant is kept and no detailed discussion is provided for that constant. Further, the experimental result is not convincing to show the superiority of the proposed criterion compared with other existing approaches. Detailed comments are as follows.\n\nIn the first section, the authors mentioned about the recent 'double decent' phenomenon in over-parameterized model, and related the proposed approach with it. However, I couldn't find any particular technical procedures or discussions specific to the double decent phenomenon in the main text. Although the authors claimed that the proposed method can mitigate the double descent phenomena, this claim is not so particularly attractive currently because the classical OED also mitigates it in the illustration of Figure 1. If the proposed method can mitigate double decent that classical OED cannot, it would be attractive. \n\nThe derivation of the proposed AL criterion is performed through the classical expected risk. The paper repeatedly claims importance of incorporating bias-dominated or mixed nature, unlike classical variance based approach. However, this idea (considering the bias effect in AL) itself is not novel though it is not clearly described. For example, 'Francis R. Bach, Active learning for misspecified generalized linear models, NeurIPS2007'.\n\nA similar bound analysis to the paper is also shown in 'Gu, et al., Selective Labeling via Error Bound Minimization, NeurIPS2012'. Although this paper is for a manifold based semi-supervised learning, it includes the usual linear model estimation as a special case. They derived a bound for the estimation error of the parameter that reflects both of the bias and variance terms (from which expected error can be derived). Their approach is similar to (Yu et al 2006) that the authors cited, but an important point is that they showed the criterion of (Yu et al 2006) can be seen as a bound of 'both of' bias and variance terms though it is originally shown as a variance-based. This would be important past analysis closely related to the proposed method, and should have been mentioned.\n\nObviously, hyper-parameter t would be a key factor in the proposed criterion. However, no practical discussion on how to set t is provided. In my opinion, as far as this constant remains unknown, the proposed bound is not so particularly innovative. Further the regularization parameter lambda can be problematic because unlike the usual supervised learning scenario, it sometimes should be determined before observing y.\n\nThe experiment in Section 7 is not convincing because the authors only compared with random design, and it only shows results of the bias-dominated setting of the proposed method, though the mixed nature of the expected error was repeatedly emphasized in the paper. Comparison with other state-of-the-art AL or classical OED would be indispensable.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JAgj6Jl0_Q9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a straightforward generalization of v-optimality from linear regression to (kernel) ridge regression. A standard greedy algorithm is used to optimize the v-optimality criterion.  A simple experiment is conducted comparing the proposed method with random sampling on MNIST. \n\nI vote for rejection. This is a simple derivation of the v-optimality of ridge regression (or Bayesian linear regression). The novelty is somewhat limited. For a paper with such limited technical novelty, the empirical studies are too thin; only one experiment is presented, comparing with only a naive random baseline. \n\nThe title “single shot active learning” seems a little inappropriate. As far as I understand, the word “active” in the context of active learning means the model “actively” query labels from some oracle in an __iterative__ fashion, so it already means “sequential” I think. Also, it's easy for people to confuse this with \"one-shot learning\".\n\ntypo: K=VV^t \\in R^{n,n} should be {m,m}? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7fh2Th1CgaM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors develop a data selection scheme aimed to minimize a notion of Bayes excess risk for overparametrized linear models. The excess Bayes risk is the expected squared error between the prediction and the target. The authors note that solutions such as V-optimality exist for the underparametrized cases (linear regression), and offer extensions to ridge regression. After the development of a greedy schemes and a tentative extension to deep learning models, the authors show that their selection scheme can outperform random selection on MNIST with a specific model.\n\nActive learning, both online and batch, is a well-studied problem with real-world applications. The paper does a fair job of developing the new technique but the addition seems incremental, and the algebra even though involved, is largely straightforward. The results are also unconvincing, and the one figure in the main body (Fig 2) only shows comparison with a weak (random selection) baseline. Furthermore, in the deep learning regime, 500-800 data points are somewhat unrealistic and do not cement the value of the method in real-world scenarios. Some other concerns include:\n\n1. Unsubstantiated claims like “As such, the theory reported in the literature is often not applicable in the interpolative regime”. \n\n2. Unconvincing contributions description, “sometimes able to mitigate the double descent phenomena”, “sometimes able to find better design than random selection”.\n\n3. The computational complexity of the method is prohibitive — O(m^2 n^2), where m is the dataset size.\n\n4. Minor formatting issues: “revealing a three possible regimes”, “an interesting connections”, “approach that suggest differs”, “larger then”, “expected expected risk”, etc.\n\nOverall, even though active learning is a highly relevant problem domain, in my opinion, the paper falls short in establishing itself as a strong competitor in the domain for reasons described previously. I would encourage the authors to resubmit with stronger justifications of the contribution and more convincing results.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a method of performing experimental design (one-round active learning) in overparameterized regression. Although the comparison with the coreset method baseline is a nice addition, the reviewers still have concerns in the following aspects:
- The novelty compared to the classical v-optimality design is limited
- The hyperparameter t is hard to choose in practice. This is important because each different hyperparameter setting would induce a different set of examples for label queries. 
- Computational complexity
- It is unclear exactly how the proposed method (or other experimental design method) can mitigate double descent 

We encourage the authors to take these into account in the revision. 

Decision: Reject