Variance Based Sample Weighting for Supervised Deep Learning
Authors: Paul Novello
Gaël Poëtte
David Lugato
Pietro Congedo
Venue:  (2021)
Keywords: supervised learning
sample distribution
statistical methods
sample weighting
approximation theory
Taylor expansion

Abstract: In the context of supervised learning of a function by a Neural Network (NN), we claim and empirically justify that a NN yields better results when the distribution of the data set focuses on regions where the function to learn is steeper. We first traduce this assumption in a mathematically workable way using Taylor expansion. Then, theoretical derivations allow to construct a methodology that we call Variance Based Samples Weighting (VBSW). VBSW uses local variance of the labels to weight the training points. This methodology is general, scalable, cost effective, and significantly increases the performances of a large class of models for various classification and regression tasks on image, text and multivariate data.  We highlight its benefits with experiments involving NNs from shallow linear NN to ResNet or Bert.

Under review as a conference paper at ICLR 2021
VARIANCE BASED SAMPLE WEIGHTING FOR SUPERVISED DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In the context of supervised learning of a function by a Neural Network (NN), we claim and empirically justify that NN yields better results when the distribution of the data set focuses on regions where the function to learn is steeper. We first traduce this assumption in mathematically workable way using Taylor expan- sion. Then, theoretical derivations allow to construct methodology that we call Variance Based Samples Weighting (VBSW). VBSW uses local variance the labels to weight the training points. This methodology is general, scalable, cost effective, and significantly increases the performances of a large class of NNs for various classification and regression tasks image, text and multivariate data. We highlight its benefits with experiments involving NNs from shallow linear NN to ResNet (He al. 2015) or Bert (Devlin et al., 2019).
INTRODUCTION
When a Machine Learning (ML) model is used to learn from data, the distribution of the training data set can have strong impact on its performances. More specifically, in the context of Deep Learning (DL), several works have hinted at the importance of the training set. In [Bnngio et al.] (2009); Matiisen al. (017), the authors exploit the observation that human will benefit more from easy examples than from harder ones at the beginning of a learning task. They construct a curriculum, inducing change in the distribution of the training data set that makes Neural Network (NN) achieve better results in an ML problem. With a different approach, Active Learning (Settles) 2012) modifies dynamically the distribution of the training data, by selecting the data points that will make the training more efficient. Finally. in Reinforcement Learning, the distribution of experiments is crucial for the agent learn efficiently. Nonetheless, the challenge of finding a good distribution is not specific to ML. Indeed, in the context of Monte Carlo estimation of quantity of interest based on random variable X dlPx x, Importance Sampling owes its efficiency to the construction of second random variable, X ~ dP,, that will be used instead of X improve the estimation of this quantity. Jie & Abbeel (2010) even make a connection between the success of likelihood ratio policy gradients and importance sampling, which shows that MI. and Monte Carlo estimation, both distribution based methods, are closely linked.
In this paper, we leverage the importance of the training set distribution to improve performances of NNs in supervised DL. This task can be formalized as approximating a function f with a model fa parametrized by 0. We build new distribution from the training points and their labels, based on the observation that fa needs more data points to approximate ʃ on the regions where it is steep. We use Taylor expansion of function f. which links the local behaviour of f its derivatives. to build this distribution. We show that up to a certain order and locally. variance is an estimator of Taylor expansion. It allows constructing methodology called Variance Based Sample Weighting (VBSW) that weights each training data points using the local variance of their neighbor labels to simulate the new distribution. Sample weighting has already been explored in many works and for various goals. Kumar et al. (2010); Jiang et al. (2015) use it to prioritize easier samples for the training, Shrivastava et al. (2016) for hard example mining, Cui et al. (2019) to avoid class imbalance, or (Liu & T (016) to solve noisy label problem. In this work, the weights' construction relies on more general claim that can be applied to any data set and whose goal is to improve the performances of the model.

---

Under review as a conference paper at ICLR 2021
VBSW is general, because it can be applied to any supervised ML problem based on loss function. In this work we specifically investigate VBSW application to DL. In that case, VBSW is applied within the feature space of pre-trainn pre-trained NN. We validate VBSW for DL by obtaining performance improvement on various tasks like classification and regression of text, from Glue benchmark (Wang) et al. 2019), image, from MNIST (LeCun & Cortes) 2010) and Cifar10 (Krizhevsky al.) and multivariate data, from UCI ML repository (Dua & Graffi 2017). for several models ranging from linear regression Bert (Devlin et al., 2019) or ResNer20 (He et al., 2015). As highlight, we obtain up to 1.65% classification improvement on Cifar with ResNet. Finally, we conduct analyses on the complementarity of VBSW with other weighting techniques and its robustness.
Contributions: (i) We present and investigate a new approach of the learning problem, based on the variations of the function f to learn. (ii) We construct a new simple, scalable, versatile and cost effective methodology. VBSW, that exploits these findings in order to boost the performances of NN. (iii) We validate VBSW on various MI. tasks.
RELATED WORKS
Active Learning Our methodology is based on the consideration that not every sample bring the same amount of information. Active learning (AL) exploits the same idea, in the sense that adapts the training strategy to the problem by introducing a data point selection rule. In (Gal et al. (017). the authors introduce methodology based on Bayesian Neural Networks (BNN) to adapt the selection of points used for the training. Using the variational properties of BNN, they design rule to focus the training on points that will reduce the prediction uncertainty of the NN. In (Konyushkova et al. 2017). the construction of the selection rule is taken as a ML problem itself. See (Settles 2012) for review of more classical AL methods. While AL selects the data points, so modifies the distribution of the initial training data set, VBSW is applied independently of the not change throughout the training.
training so the distribution of the weights
Examples Weighting VBSW can be categorized as an example weighting algorithm. The idea of weighting the data set has already been explored in different ways and for different purposes. While curriculum learning (Bengio et al.| [2099] Matüienn et al. 2017) starts the training with easier examples, Self paced learning (Kumar et al.) 2010; Jiang et al. 2015 downscales harder examples. However, some works have proven that focusing on harder examples at the beginning of the learning could accelerate it. In (Shrivastava et al.) 2016), hard example mining is performed to give more importance to harder examples by selecting them primarily. Example weighting is used in (Cui et al., 2019) to tackle the class imbalance problem by weighting rarer, so harder examples. At the contrary, in (Liu & Tao 2016) it is used to solve the noisy label problem by focusing on cleaner, so easier examples. All these ideas show that depending on the application, example weighting can be performed in opposed manner. Some works aim at going beyond this opposition by proposing more general methodologies. In (Chang et al.] 2017). the authors use the variance of the prediction of each point throughout the training to decide whether it should be weighted or not. A meta learning approach is proposed in (Ren et al. 2018), where the authors choose the weights after an optimization loop included in the training. VBSW stands out from the previously mentioned example weighting methods because it is built on more general assumption that a model would simply need more points learn more complicated functions. Its effect is improve the performances of a NN, without solving data set specific problems like class imbalance or noisy labels.
Importance Sampling- Some of the previously mentioned methods use importance sampling to de- sign the weights of the data set or to correct the bias induced by the sample selection (Katharopoulos & Fleuret 2018). Here, we construct new distribution that could be interpreted as an importance distribution. However, we weight the data points to simulate this distribution, not to correct a bias induced by this distribution.
Generalization Bound- - Generalization bound for the learning theory of NN have motivated many works, most of which are reviewed in (Jakubovitz et 2018). In Bartlett et al. (1998). Bartlett et al. (001), the authors focus on VC-dimension, a measure which depends on the number of parameters of NNs. Arora et al. 2018) introduces compression approach that aims at reducing the number of model parameters to investigate its generalization capacities. PAC-Bayes analysis constructs generalization bounds using a priori and posteriori distributions over the possible models. It is
2

---

Under review as a conference paper at ICLR 2021
investigated for example in Neyshabur et al. 2018): Bartlett al. (2017). and Neyshabur et al. (0177; Xu & Mannor (2012) links PAC-Bayes theory to the notion of sharpness of NN, i.c. its robustness to small perturbation. While sharpness of the model is often mentioned in the previous works, our bound includes the derivatives of /, which can be seen as an indicator of the sharpness of the function to learn. Even if it uses elements of previous works, like the Lipschitz constant of fe. our work does not pretend to tighten and improve the already existing generalization bounds, but only emphasizes the intuition that the NN would need more points to capture sharper functions. In sense, it investigates the robustness to perturbations in the input space, not in the parameter space.
A NEW TRAINING DISTRIBUTION BASED ON TAYLOR EXPANSION
In this section, we first illustrate why a NN may need more points where steep by deriving generalization bound that involves the derivatives of f. Then, using Taylor expansion, we build new training distribution that improves the performances of NN on simple functions.
3.1 PROBLEM FORMULATION
We formalize the supervised ML task as approximating a function f S R R with an ML model fo parametrized by 0, where is measured sub-space of Th depending on the application. To this end, we are given a training data set of N points, (X1, Xx} E S, drawn from ~ dPx and their point-wise values, labels {f(X)), f(Xx). Parameters 0 have be found in order with L the loss function, L : R R RR. The data allow estimating (O) by (x) N I ((x,
to minimize an integrated loss function (0)
(X),
Then, an optimization algorithm is used to find minimum of Jx (0) w.r.t. 6.
3.2 INTUITION BEHIND TAYLOR EXPANSION
In the following, we illustrate the intuition with Generalization Bound (GB) that include the derivatives of f, provided that these derivatives exist. The goal of the approximation prob- lem is to be able to generalize to points not seen during the training. The generalization error (0) (x( Jx (0) thus needs be as small possible. Let S,, i E (1,..., N} be some sub-spaces of S such that $ U S., Di S, = Ø, and X; E S,. Suppose that L the squared La error, n, 1, f is differentiable and fe is Ko-Lipschitz. Provided that [S,] < 1, we show that
S 1S11 + O((S,(*)
(0) Σ (( K₂)²
where [S,] is the volume S.. The proof can be found in Appendix We see that on the regions where (X)) is higher, quantity [.,] has stronger impact on the GB. This idea is illustrated on Figure Since |S,] can be seen as a metric for the local density of the data set (the smaller |S,] is,
Best order apprex. off
maximum variations of
delimitation ofS.
traiiig points
'/. taak ganeral zation enze (GB)
15
15
654
88.1
860
X1
32
Figure 1: Illustration the GB. The maximum error (the GB), at order O(IS. (*) is obtained by comparing the maximum variations of fa. and the first order approximation of f. whose trends are given by Ko and f'(X.). We understand visually that because f'(X1) and f f'() are higher than f'(X2), the GB is improved more efficiently by reducing S and S3 than S2-
3

---

Under review as a conference paper at ICLR 2021
the denser the data set is), the GB be reduced more efficiently by adding more points around X; in these regions. This bound also involves Kg. the Lipschitz constant of the NN, which has the same impact than (X)). It also illustrates the link between the Lipschitz constant and the generalization error which has been pointed out by several works like (Gouk et al. (018), (Bartlett et al., (017) and (Qian & Wegman 2019). Note that equation Tonly gives indications about GB only has illustration purposes. Its goal is to motivate the metric described in the next section, which is based on Taylor expansion and therefore involves derivatives of order n 1.
1. Indeed, this
3.3 TAYLOR EXPANSION BASED METRIC
In this paragraph, we build metric involving the derivatives of f. Using Taylor expansion order n on f and supposing that f is n times differentiable (multi index notation):
to tt f(x) k!
|e|| Vect f(x))
f(x
Σ USIkISn
+O(E"),
(12(2) = Σ
[|e] +0
k!
Quantity f(r + + c) gives an indication on how much f changes around x. By neglecting the orders above e", it is then possible find the regions of interest by focusing D given by equation 2 where (Xct(X) denotes the vectorization of a tensor X and ||-I| the squared L2 norm. Note that DS is evaluated using ||@ [(x)] instead of O² fxx for derivatives not to cancel each other. ʃ will be steeper and more irregular in the regions where æ - DJ (a) is higher.
To focus the training set these regions, can (X) probability density function (pdf) and sample new data points from it. This sampling is evaluated and validated in Appendix for conciseness. Based on these experiments, we choose n 2, i.c. we use (X)) .... (X.))...Dff(( (xx(( The good results obtained, presented in Appendix A confirm
(X1)
(Xx)) construct
(X1),....
our observation and motivate its application to complex DL problems.
4
VARIANCE BASED SAMPLES WEIGHTING (VBSW)
4.1 PRELIMINARIES
The new distribution cannot always be applied as is, because we do not have access f. Problem 1: (D1) (Xx)x cannot be evaluated since it requires to compute the derivatives of
f. Moreover, it assumes that differentiable, which is often not true. Problem 2: even (D12(X1),, ..., DX2(xx) could be computed and new points sampled, we could not obtain their labels to complete the training data set.
metric based on statistical estimation. In this paragraph, n4 > 1 but n, = 1. The following derivations be extended n, by applying it to element-wise and then taking the across the no dimensions. Let E ~ (O, (I,,) with E R and I, the identity matrix of dimension n4- We claim that
Problem 1: Unavailability of derivatives To overcome problem 1, construct
Var(f(z + c)) =
The demonstration can be found in Appendix B Using the unbiased estimator of variance, we thus define indices (x) by
Df2(x) = k- Σ -fzz))))(())
(3)
with {E1,...,Ex) Ex} k samples of e. The metric D)2 k Var(f(# + 6)) and Var(ʃ(x + E)) Df²(z) + O(
Df2 is biased estimator of D with bias (()E)1)). Hence, when e + 0, Df (x) becomes an unbiased estimator of Dz2 is possi- ble to compute (z) from any set of points centered around a. Therefore, compute for each ė E (V} using the set (X) of k-nearest neighbors of X,. We obtain (X,, using
4

---

Under review as a conference paper at ICLR 2021
1 &
(F) = k-1
E (F(X)) XxES,(X,)
Σ fxi))
(4)
The advantages of this formulation are twofold. First, Dj2 can even be applied to non-differentiable functions. Second, all we need {f()),.... f(Xx)} In other words, the points used by (X,) are those used for the training of the NN. Finally, while the definition of Dz² is local, the definition of (z) holds for any E. Note that equation 4 can even applied when the data points are too sparse for the nearest neighbors of X; to be considered as close to X, It can thus be seen as a generalization of (z), which tends towards (x) locally.
Problem 2: Unavailability of new labels To tackle problem 2, recall that the goal the training to find 0 argminJx((0 (0), with Jx (0) N E. (x(((x),, fo(x)) With the new distribution based on previous derivations, the procedure is different. Since the training points are sampled using D e we no longer minimize Jx (0), but (x) N E. LU((X) fo(X.)), with X ~ dlp, the new distribution. However, (0) estimates
&
(0) = f(f(w)
Let px = dF -alydd=dxxxPppiee dPx be the pdfs of X and X (note that D x P&). Then, (x LL((s),
(x(x) dFx.
px
The straightforward Monte Carlo estimator for this expression of Jx (0)
Σ (o(..) xx) = N
1
Px (x() (x( x Σ (U((X))
D)((X.)
(5)
(x(),)
Thus, (0) can be estimated with the same points as Jx (0) by weighting them with w; DP(())
px(X,)
4.2 HYPERPARAMETERS OF VBSW
The expression of w, involves (X,,,,), whose estimation has been the goal of the previous sec- tions. However, it also involves Px, the distribution of the data. Just like for f, we do not have access px- The estimation of px is challenging task by itself, and standard density estimation techniques such as K-nearest neighbors or Gaussian Mixture density estimation led to extreme esti- mated values of px (X;) in experiments. Therefore, as a first order approximation. In practice, we re-scale the weighting points to be between and m, a hyperparameter. As result, VBSW has two hyperparameters: m and k. Their effects and interactions are studied and discussed in (cctions[5.I]am 5.4]
decided only apply w; (X,)
4.3 VBSW FOR DEEP LEARNING
We specified that local variance could be computed using already existing points. This statement implies to find the nearest neighbors of each point. In extremely high dimension spaces like image spaces the curse of dimensionality makes nearest neighbors spurious. In addition, the structure of the data may highly irregular, and the concept of nearest neighbor misleading. Thus, it may be irrelevant to evaluate D2 fe directly this data.
One of the strength of DL is to construct good representations of the data, embedded in lower dimen- sional latent spaces. For instance, in Computer Vision, Convolutional Neural Networks (CNN)'s deeper layers represent more abstract features. We could leverage this representational power of NNs, and simply apply our methodology within this latent feature space.
5

---

Under review as a conference paper at ICLR 2021
Algorithm Variance Based Samples Weighting (VBSW) for Deep lcarning
1: Inputs: k, m, MM
2: Train M on the training set (i); ( Xx)): ((+) ((Xi)) (xx
3: Construct M by removing its last layer
4: Compute [Df2(M" (X1)). (M² using equation
5: Construct a new training data set M(()) (WN, M (M(X)))
6: Train Ja on ((X)),, O M
and add it to M The final model Mr
Variance Based Samples Weighting (VBSW) for DL is recapitulated in Algorithm Here, M is the initial NN whose feature space will be used to project the training data set and apply VBSW. Line 1: m and are hyperparameters that can be chosen jointly with all other hyperparameters, e.g. using random search. Line 2: The initial NN, M, is trained as usual. Notations {( (1). (x. Xx)] is equivalent to {X1..., ).). because all the weights are the same (*). Line 3: The last fully connected layer is discarded, resulting in a new model M and the training data set is projected in the feature space. Line 4-5: equation 4 is applied to compute the weights w; that are used weight the projected data set. To perform nearest neighbors search, we use KD-Tree (Bentley 1975). Line 6: The last layer is re-trained (which is often equivalent fitting linear model) using the weighted data set and added to M to obtain the final model M,. As a result, My is a composition of the already trained model M and trained using the weighted data set.
5 EXPERIMENTS
We first this methodology on toy datasets with linear models and small NNs. Then, to illustrate how general VBSW can be, we consider various tasks in image classification, text regression and classification. Finally, we study the robustmess of VBSW and its complementarity with other sample weighting techniques.
TOY EXPERIMENTS
VBSW is studied on a Double Moon (DM) classification, in the Boston Housing (BH) regression and Breast Cancer (BC) classification data sets.
Figure 2: From left to right: (a) Double Moon (DM) data set. (b) Decision boundary with the baseline method.
(c) Heat map of the value of for each X; (red is high and blue is low) and (d) Decision boundary with VBSW method
For DM, Figure (c) shows that the points with highest (in red) are close to the boundary between the two classes. Indeed, in classifica- tion, VBSW can be interpreted as local label agreement. We train a Multi Layer Perceptron of 1 layer of 4 units, using Stochastic Gradient Descent (SGD) and binary cross-entropy loss function, 300 points training data set for 50 random seeds. this experiment, VBSW, i.c. weighting the data set with w, is compared to baseline where weights applied. Figure 2 (b) and (d) displays the decision boundary of best
VBSW
baseline
DM
99.4,
94.44 0.78 13.31, 13.38 + 0.01
99, 92.06 + 0.66 14.05, 14.06 + 0.01 98.25 97.5 0.11
BH
BC
99.12, 97.6 + 0.34
Table best, mean + se for each method. The metric used is accuracy for DM and BC and Mean Squared Error for BH.

---

Under review as a conference paper at ICLR 2021
fit for each method. VBSW provides cleaner decision boundary than baseline. These pictures as well as the results of Table [ show the improvement obtained with VBSW.
For BH data a train-validation split of 80% - 20%. Both models are trained with ADAM (Kingma & Ba 2014).
linear model is trained and for BC data set, MLP of 1 layer and 30 units, with
Since these data sets small and the models are light, we study the effects of the choice of m and & on the performances. Moreover, BH is a regression task and BC a classification task, so allows studying the effect of hyperparameters more extensively. We train the models for a grid of 20 x 20 different values of m and k. These hyperparameters seem to have different impact on performances for classification and regression. In both cases, low values for m yields better results, but in classification, low values of k are better, unlike in regression. Details and visualization of this experiment can found Appendiix C The best results obtained with this study are compared to the best result of the same models trained without VBSW in Table 1
5.2 MNIST AND CIFAR10
For MNIST, we train 40 LeNet 5, i.c. with 40 different random seeds, and then apply VBSW for 10 different random seeds, with ADAM optimizer and categorical cross-entropy loss. Note that in the following, ADAM is used with the default parameters of its keras implementation. We record the best value obtained from the 10 VBSW training. The same procedure is followed for Cifar10, except that we train a ResNet20 for 50 random seeds and with data augmentation and learning rate decay. The networks have been trained on 4 Nvidia K80 GPUs. The values of the hyperparameters used can be found in Appendix C We compare the test accuracy between LeNet 5 + VBSW, ResNer20 VBSW and the initial test accuracies of LeNet 5 and ResNet20 (baseline) for each of the initial networks.
VBSW
baseline 98.99, 98.84 + 0.01
gain per model
MNIST Cifar10
99.09, 98.87 + 0.01
0.15, 0.03 + 0.01
91.30, 90.64 0.07
91.01, 90.46 0.10
1.65, 0.15 + 0.04
Table 2: best, mean + se for each method. The metric used is accuracy. For a model M, the gain g for this model is given by g = max (aco(M)) acc(M) with acc the accuracy and My the VBSW model trained at the i-th random seed.
154510
The results statisties are gathered in Table 2 which also displays statistics about the gain due to VBSW for each model. The results on MNIST, for all statistics and for the gain significantly better than VBSW than for baseline. For Cifar10, we get a 0.3% accuracy improvement for the best model and up 1.65% accuracy gain, meaning that among the 50 ResNet20s, there one whose accuracy has been improved by 1.65% by VBSW. Note that applying VBSW took less than 15 minutes on a laptop with 17-7700HQ CPU. visualization of the samples that were weighted by the highest W/ is given in Figure
Samples from Cifarl0 and MNIST with high w;. Those pictures are either unusual difficult classify, even for human (especially for MNIST).
Figure 3:
5.3 RTE, STS-B AND MRPC
For this application, we do not pre-train Bert NN, like in the previous experiments, since it has been originally built for Transfer Learning purposes. Therefore, its purpose is to be used as is and then fine-tuned on any NLP data set see (Devlin et al. 2019). However, because of the small size of the dataset and the high number model parameters we chose not to linettue the Bert model, and only to use the representations of the data sets in its feature space to apply VBSW. More specifically, use kiny-bert (Ture et al. 2019), which is lighter version of the initial Bert NN. We train the linear model with tensorflow, be able add the trained model top of the Bert model and obtain
7

---

Under review as a conference paper at ICLR 2021
unified model. RTE and MRPC classification tasks, use binary cross-entropy loss function to train our model. STS-B B is a regression task so the model is trained with Mean Squared Error. All the models are trained with ADAM optimizer. For each task, compare the training of the linear model with VBSW, and without VBSW (baseline). The results obtained with VBSW are better overall, except for Pearson Correlation in STS-B, which is slightly worse than baseline (Table baseline
VBSW
ml
m2
ml
m2
RTE
61.73, 58.46 = 0.15
61.01, 58.09 0.13
STS-B
62.31, 62.20 +: 0.01
60.99, 60.88 + 0.01
61.88, 61.87 + 0.01
60.98, 60.92 + 0.01 81.41, 80.02 0.07
MRPC
72.30, 71.71 + 0.03
82.64, 80.72 + 0.05
71.56, 70.92 + 0.03
Table 3: best, mean + se each method. For RTE the metric used is accuracy (ml). For MRPC, metric (ml) is accuracy and metric (m2) is F1 score. For STS-B, metric (ml) is Spearman correlation and metric 2 (m2) is Pearson correlation.
5.4 ROBUSTNESS OF VBSW
VBSW relies on statistical estimation: the weights are based on local empirical variance, evaluated using k points. In addition, they are rescaled using hyperparameter
Section [.1 and Appendix show that many different combinations of m and & and therefore many different values for the weights improve the error. This behavior suggests that VBSW is quite robust to weights approxima- tion error.
We also assess the robustness of VBSW to label noise. To that end, we train ResNet20 on Cifar with four different noise levels. We randomly change the label of p% training points for four differ- ent values of p (10, 20, 30 and 40). We then apply VBSW 30 times and evaluate the performances of the obtained NNs on a clean test set. The results are gathered in Table
noise
10%
20%
30%
40%
original error 87.43
85.75
84.05
81.79
VBSW
87.76, 87.63 0.01
86.03,
85.89 + 0.01
84.35,
84.18 0.02
82.48, 82.32 + 0.02
Table 4: best, mean se of the training of a ResNet20 on Cifar10 for different label noise levels. These results illustrate the robustness of VBSW to labels noise.
The results show that VBSW is still effective despite label noise, which could be explained by two observations. First, the weights VBSW rely on statistical estimation, so perturbations in the labels might have limited impact weights' value. Second, mentioned previously, VBSW is robust to weights approximation error. so perturbation of the weights due to label noise may not critically hurt the method. Although VBSW is robust to label noise, note that the goal of VBSW is not to address noisy label problem, like discussed in Section 2 It may be more effective to use a sampling technique specifically tailored for this situation possibly jointly with VBSW, like in Section 5.5
5.5 COMPLEMENTARITY OF VBSW
Existing sample weighting techniques can be used jointly with VBSW by training the initial NN M with the first sample weighting algorithm, and then applying VBSW on its feature space. To illustrate this feature, we compare VBSW with the recently introduced Active Bias (AB) (Chang et al. 2017). AB dynamically weights the samples based on the variance of the probability of prediction of each points throughout the training. Here, we study the combined effects of AB and VBSW for the training of ResNer20 on Ci Table 5 gathers the results of experiments for different baselines: vanilla, for a regular training with Adam optimizer, AB for a training with AB, VBSW for the application of VBSW top of regular training and VBSW AB for training with AB and the application of VBSW. Unlike section 5.22 we do not use data augmentation or learning rate decay, to simplify the experiments (which explains the accuracy loss compared to previous experiments).
These results demonstrate the competitiveness of VBSW compared with AB and their complemen- tarity. Indeed, the accuracy obtained with VBSW is quite similar to AB and the best mean and max accuracy is obtained for NN trained with AB VBSW. Note that in this experiment, the gain
8

---

Under review as a conference paper at ICLR 2021
accuracy (%)
VBSW gain per model
vanilla
75.88, 74.55 0.11
AB
76.33. 75.14 0.09
VBSW
76.57, 74.94 + 0.10
0.94, 0.40 + 0.03
AB + VBSW
76.60, 75.33 + 0.09
0.40, 0.014 + 0.02
Table best, mean se of the training 60 ResNet20s on Cifar for vanilla, VBSW, AB and AB VBSW. Gain per model 9 is defined by g max (ace(My) acc(M)) with ace the accuracy
15
and My the VBSW model trained at the i-th random seed.
per model is lower for AB + VBSW than for VBSW alone. An explanation might be that AB is already improving the NN performances compared to vanilla, so there is less room for accuracy improvement by VBSW in that case.
6 DISCUSSION & FUTURE WORK
Previous experiments demonstrate the performances improvement that VBSW can bring in practice. In addition to these results, several advantages can be pointed out.
VBSW is validated on several different tasks, which makes it quite versatile. Moreover, the prob- lem of high dimensionality and irregularity of f. which often arises in DL problems, is alleviated by focusing on the latent space of NNs. This makes VBSW scalable. As result, VBSW can be applied to complex NNs such as ResNet, a complex CNN or Bert, for various ML tasks. Its application to more diverse ML models is a perspective for future works.
The validation presented in this paper supports an original view of the learning problem, that involves the local variations of f. The studies of Appendix A] that use the derivatives of the function to learn to sample more efficient training data set, support this approach as well.
VBSW allows to extend this original view to problems where the derivatives of f are not accessi- ble, and sometimes not defined. Indeed, VBSW comes from Taylor expansion, which specific to derivable functions, but in the end can be applied regardless of the properties of f.
Finally, this method is cost effective. In most cases, it allows to quickly improve the performances of NN using a regular CPU. In terms of energy consumption, it is better than carrying on a whole new training with a wider and deeper NN.
We first approximated px be uniform, because we could not approximate it correctly. This ap- proximation still led to an efficient methodology, but VBSW may benefit from finer approxima- tion of Px- Improving the approximation of Px is among our perspectives. Finally, the KD-tree and even Approximate Nearest Neighbors algorithms struggle when the data set is too big. One possibility to overcome this problem would be to parallelize their execution.
We only considered the cases where we have no access to f. However, there are ML applica- tions where we do. For instance, in numerical simulations, for physical sciences, computational economics climatology. ML can be used for various reasons, e.g. sensitivity analysis, inverse problems or to speed up computer codes (Zhu et al.) 2019); Winovich et al. 2019 Feng et al.) 2018). In this context data comes from numerical models, the derivatives of f are accessible and could be directly used. Appendix A contains examples of such possible applications.
7 CONCLUSION
Our work is based on the observation that, in supervised learning, a function f is more difficult to approximate by NN in the regions where it is steeper. We mathematically traduced this intuition and derived a generalization bound to illustrate it. Then, we constructed an original method, Vari- ance Based Samples Weighting (VBSW), that uses the variance the training samples to weight the training data set and boosts the model's performances. VBSW is simple to use and to implement, because it only requires to compute statisties on the input space. In Deep Learning, applying VBSW on the data set projected in the feature space of an already trained NN allows reduce its error by simply training its last layer. Although specifically investigated in Deep Learning, this method is applicable to any loss function based supervised learning problem, scalable, cost effective, robust and versatile. It is validated on several applications such as glue benchmark with Bert, for text classification and regression and Cifar with ResNet20, for image classification.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Watten- berg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. tensorflow.org.
org/ Software available from
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Ma- chine Learning Research, pp. 254-263, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Peter L. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. In Proceedings of the I 1ith International Conference on Neural Information Processing Systems, NIPS'98, '9, pp. 190-196, Cambridge, MA, USA, 1998. MIT Press.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally normalized margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6240-6249. Curran Associates, Inc., 2017.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research. 20(63):1 2019.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning. ICML '09, pp. 41-48, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-516-11 doi: 10.1145/1553374. 1553380.
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):009-55) -17, September 1975. ISSN 0001-0782. doi: 10.1145/261002.331007.
Haw-Shiuan Chang, Erik Learned-Miller and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1002-1012. Curran Associates, Inc., 2017.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song. and Serge Belongie. Class-balanced loss based on effeectie number of samples. In The IEEE Conference on Computer Vision and Pattern Recogni- tion (CVPR), June 2019.
Jacob Devlin, Ming-Wai Wei Chang, Kenton Lec, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers). pp. 4171-4186, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics. doi: 10.18653/v1/N199
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive. ics. www..ed/mm
Feng, Q. Teng, X. He, and X. Wu. Accelerating multi-point statisties reconstruction method for porous media via deep learning. Acta Materialia, 159:296-308, 2018.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 1183-1192, JML..org. 2017.
10

---

Under review as a conference paper at ICLR 2021
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. 04 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770- 778, 2015.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural Networks, 2(5):359 366, 1989. ISSN 0893-6080. doi: https://doi.org/10. http:///orrr//..1111110999990900 100006000000--000099999000060
Daniel Jakubovitz, Raja Giryes, and Miguel R. D. Rodrigues. Generalization error in deep learning. CoRR, abs/1808.00 088801174, 174, 2018.
Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G. Hauptmann. Self-paced cur- riculum learning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AA pp. 2694 2700. AAAI Press, 2015. ISBN 0262511290.
Tang Jie and Pieter Abbeel. On a connection between importance sampling and the likelihood ratio policy gradient. In J. D. Lafferty. C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 1000-1008. Curran Associates, Inc., 2010.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In ICML, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Ksenia Konyushkova, Raphael Sznitman, and Pascal Fua. Learning active learning from data. In Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. ciates, Inc., 2017.
Curran Asso-
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced re- search).
M. P. Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In J. D. Lafferty, C. I. Williams, J. ShylorTaylor, R. S. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 1189-1197. Curran Associates, Inc., 2010.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Trans. Pattern Anal. Mach. Intell., 38(3):447-461, March 2016. ISSN 0162- doi: 10.1109)
IPAMM.2015.2456880
Tambet Matiisen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learn- ing, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring general- ization in deep learning. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp- 5947-5956. Curran Associates, Inc., 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally-normaaizzed margin bounds for neural networks. In International Conference on Leam- ing Representations, 2018.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Coumapeaau, M. Brucher, M. Perrot. and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2828 2011.
11

---

Under review as a conference paper at ICLR 2021
Haifeng Qian and Mark N. Wegman. L2- nonexpansive neural networks. In International Conference on Learning Representations, 2019.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. CoRR, hts/1803.09050 2018.
Burr Settles. Active Learning- Synthesis Lectures on Artificial Intelligence and Machine Learning- Morgan & Claypool Publishers, 2012.
Abhinav Shrivastava, Abhinav Gupta, and Ross B. Girshick. Training region based object detectors with online hard example mining. CoRR, abs/1604.03540, 2016.
Iulia Ture, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Well-read students learn better: On the importance of pre-training compact models. arXiv preprini arXiv: 1:XXv:/908.08000 089.2.22222 2019.
Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding, In International Conference on Learning Representations, 2019.
Nick Winovich, Karthik Ramani, and Guang Lin. Convpde-uq: Convolutional neural networks with quantified uncertainty for heterogeneous elliptic partial differential equations varied domains. Journal of Computational Physics, 394:263 279, 2019. ISSN 0021-9991. doi: https://doi.or//
10.19..6..
Huan Xu and Shie Mannor. Robustness and generalization. Machine Learning, 86(3):391-423, Mar 2012. ISSN 1573-0565. doi: 10. 10.11077/119944-1--55666
Yinhao Zhu, Nicholas Zabaras, Phaedon-Stelion Koutsourelakis, and Paris Perdikaris. Physics- constrained deep learning for high-dimensional surrogate modeling and uncertainty quantification without labeled data. Journal of Computational Physics, 394:56 81, 2019. ISSN 0021-9991. doi: https://doi.org/10/ 10. 101 :op.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX A TAYLOR BASED SAMPLING
In this part, we empirically verify that using Taylor expansion to construct a new training distribution has beneficial impact the performances of a NN. To this end, construct methodology, that we call Taylor Based Sampling (TBS), that generates a new training data set based on the metric introduced in Section 3.3. First, we recall the formula for (XI"(Xi),... Dfe((N)) (Xv)).
||]|
Vect f()))
(x) = Σ
(6)
k!
To focus the training set on the regions of interest, i.e. regions of high DIx"
we use this metric to construct probability density function (pdf). This is possible since Df 2 O for all x S. It remains to normalize but in practice is enough considering a distribution d x DSC. Here, to approximate d we use a Gaussian Mixture Model (GMM) with pdf daMM that we fit to (Dfa(X)
(EM) algorithm. N' new data points 1X..... X ), can be sampled, with X ~ dGMM- Finally, we obtain (f. ((X add it to (f(X))..... f(X.). f()x) and train our NN on the whole data set.
DJ (Xw)) using the Expectation-Maxxiizzaa
TAYLOR BASED SAMPLING (TBS)
TBS is described in Algorithm Line 1: The choice criterion of e, the number of Gaussian dis- tribution 7GMM and N' to avoid sparsity of (X1,...,N, X over S. Line 2: Without a priori
information f. sample the first points uniformly in a subspace S. Line 3-7: We construct (XI) Df (XN)). and then d to be able to sample points accordingly. Line 8: Because the support of GMM not bounded, some points can be sampled outside S. We discard these points and sample until all points are inside S. This rejection method is equivalent to sampling points from truncated GMM. Line 9-10: We construct the labels and add the new points to the initial data set.
Algorithm 2 Taylor Based Sampling (TBS)
1: Inputs: 6, N, N' RGMM.
2: Sample [X,,..., XN). with X ~ ((())
3: for 0 I h Σ do
4: Compute ( f(Xi), ..., 8 [Xx)}
5: Compute ( (X1) ()),,., (XN) using equation 2
De with a GMM using EM algorithm to obtain a density daMm 6: Approximate
7: Sample {X1, X using rejection method to sample inside S
8: Compute (f( f(Xx.))
9: Add (f(X),,., (i,,,((X [(Xx))) to (S(x))
APPLICATION TO SIMPLE FUNCTIONS
In order to illustrate the benefits of TBS com-
Sampling
L2 eгror
Lo
pared uniform, basic sampling (BS), we ap-
f: Runge
(x10-
ply it to two simple functions: hyperbolic tan- gent and Runge function. We chose these func- tions because they are differentiable and have clear distinction between flat and steep regions.
BS
1.45 + 0.62
5.31 5.31 0.86
TBS
1.13 + 0.73
3.47
f: tanh
(x10-1)
BS
1.39
0.67
2.75 0.78
These functions are displayed in Figure as
well as the map x > (x).
TBS
0.95 + 0.50
2.25 - 0.61
All NN have been implemented in Python, with Tensorfl ow Abadi et al. (2015). We use the Python package scikit- -it--eeann Pe-
Table 6: Comparison between BS and TBS. The metrics used the L2 and L.0 errors, displayed with 95% confidence interval.
dregosa et al. (201T), and more specifically the Gaussi anMixture class to construct doMAs- The network chosen for this experiment is a Multi Layer Perceptron (MLP) with one layer of 8 neurons, with Relu activation function, that we trained alternatively with BS and TBS using
13

---

Under review as a conference paper at ICLR 2021
1..
2.00
-016
-05
-014
1.50
004
0.32
1.28
-0.
3 0.6
0.10
-0.08
0.75
-0.2
-0.06
-0.
0.25
0.2
1977 0010000119 FHIE --SHIE---- 01
0.00
0.0
0.0
0.2
0.6
0.6
0.6
Figure 4: Left: (left axis) Runge function w.r. x and (right axis) x - (x). Points sampled using TBS are plotted on the x-axis and projected f. Right: Same left, with hyperbolic tangent function.
Adam optimizer Kingma Ba 2014) with the defaults tensorflow implementation hyperparame- ters, and Mean Squared Error loss function. We first sample (X1,..., XN} according to regular grid. To compare the two methods, we add N' additional points sampled using BS to create the BS data set, and then N' other points sampled with TBS to construct the TBS data set. As result, each data set have the same number of points (N + N*). We repeated the method for several values n, 2, 7GGMM and 10-3
nGMM and c, and finally selected
T summarizes the L2 and the Loc norm of the error of fa. obtained at the end of the training phase for N + N' 16, with N 8. Those norms estimated using same test data set of 1000 points. The values are the means of the 40 independent experiments displayed with a 95% confidence interval. These results illustrate the benefits of TBS over BS. Table 6 shows that TBS slightly degrades the L2 error of the NN, but improves its Loe eπror. This may explain the good results of VBSW for classification. Indeed, for a classification task, the accuracy will not be very sensitive to small output variations, since the output is rounded to 0 or 1. However, a high error can induce misclassification, and the reduction in Lo norm limits this risk.
APPLICATION TO AN ODE SYSTEM
We apply TBS to more realistic case: the approximation of the resolution of the Bateman equations, which is ODE system:
{ (ru(()) = vo (())((), (a.(()) = =.E, (EE,n(())(())) with initial conditions
Su(0) to:
(n(0)) 170-
with u E I n E (R+)M of R. E, E R M Here, f: (wo, no. t) + (u(t), (()).
For physical applications, M ranges from tens to thousands. We consider the particular case M = so that f R + R²,, with f(u, N/, () (u(t), sf()). The advantage of M 1 is that we have access to an analytic, cheap to compute solution for f. Of course, this particular case can also be solved using a classical ODE solver, which allows us test it end to end. It can thus be generalized to higher dimensions (M >> 1).
All NN trainings have been performed Python, with Tensorfl ow Abadi et al. (2015). We used fully connected NN with hyperparameters chosen using a simple grid search. The final values are: 2 hidden layers, "ReLU" activation function, and 32 units for each layer, trained with the Mean Squared Error (MSE) loss function using Adam optimization algorithm with batch size of 50000, for 40000 epochs and on N + N' = 50000 points, with N = N'. We first trained the model uniform sampling (BS) (N' 0), and then with TBS for several values of n, RGMM and e = e(1, 1, 1). to be able to find good values. We finally select e = x 10-4, 2 and MGMM 10. The data points used in this case have been sampled with explicit Fuler
for (u(t), nt)) E R. with
14

---

Under review as a conference paper at ICLR 2021
scheme. This experiment has been repeated 50 times to ensure statistical significance of the results.
Table 7 summarizes the MSE, i.c. the Le norm of the error of fe and Loo norm, with (0) max [X)) - fo(X))) obtained at the end of the training phase. This last metric is important XES
because the goal in computational physics is not only to he averagely accurate, which is measured with MSE, but to be accurate over the whole imput space S. Those norms are estimated using same test data set of Ntest- 50000 points. The values are the means of the 50 independent experiments displayed with a 95% confidence interval. These results reflect an error reduction of 6.6% for L2 and of 45.3% for L which means that TBS mostly improves the Lee error of fe. Moreover, the Los error confidence intervals do not intersect so the gain is statistically significant for this norm.
Table 7: Comparison between BS and TBS
Sampling
L error (x10-1)
I. (x10-)
AEG(X10-2)
AEL((X0-33
BS
1.22 = 0.13
5.28 + 0.47
TBS
1.14
2.96 + 0.37
2.51 +
0.42 = 0.008
Figure la
Figure 1b
20-
30-
25-
14-
Jetoiii (n with 115
1.0
Jaba, f with BS
1.5
folo, 0o. TBS
1.0
65-
00-
Figure
Figure 2b
1.0
1100
:5 es-
-0,000
0.00
7
Figure 5: 1a: t - fo(uu, No. t) for randomly chosen (uu, no). for fo obtained with the two sam- plings. 1b: t folus, no. t) for (ug, resulting in the highest wisnt-wise error with the two samplings. 2a: un, no + max D (uo: No, !) w.r.. (uo, 2b: uo, 1o + gogs (uo, 7n)
o51510
gerss (uo, (ur TTO)
Figure 1a shows how the NN can perform for average prediction. Figure 1b illustrates the benefits of TBS relative to BS on the Lo error (Figure 2b). These 2 figures confirm the previous observation about the gain in Loo error. Finally, Figure 2a displays ug. 0grs10
max D To. t)
w.r.t (uo: no) and shows that D increases when Uo + O. TBS hence focuses on this region. Note that for the readability of these plots, the values are capped to 0.10. Otherwise only few points with high D are visible. Figure 2b displays up, 70 + g0 (wo, To) 99res (uo, no), with 90 up. Uu + max (f, 1j. t) fo(wo, no. t)l where fBs and f Bs denote the parameters ost$10
obtained after a training with BS and TBS, respectively. It can be interpreted as the error reduction achieved with TBS.
15

---

Under review as a conference paper at ICLR 2021
The highest error reduction occurs in the expected region. Indeed, more points sampled where De is higher. The error is slightly increased in the rest of S, which could be explained by a sparser sampling this region. However, summarized in Table 1, the average error loss (AEL) of TBS around six times lower than the average error gain (AEG), with AEG AFT. Ru <ol)<o) where (no, 176) g0ss (uo; 1/0) grrss (Nog To)- In practice, AEG and AEL are estimated using uniform grid integration, and averaged on the 50 experiments.
Eu [ 12)))) and
APPENDIX B: DEMONSTRATIONS
INTUITION BEHIND TAYLOR EXPANSION (SECTION 3.2
We want to approximate f x - f(x). I E R". f(z) R with NN fe. The goal of the approximation problem be scen as being able generalize points not seen during the training. We thus want the generalization error Jx(O) to be as small as possible. Given an initial data set (X1...., XN) drawn from X dl'x and {f(X)), f(Xx)), and the loss function L being the squared L2 error, recall that the integrated error J [x( estimation Jx(0) and the generalization error Jx (0) can be written:
(x( = / [lf(z) fo(x)]ldXx.
1 N
(x) = Σ
l1f((x)) s(xi))
N
i=1
(x(0) = Jx -x))
where ||-|| denotes the squared Le norm. the following, we find an upper bound for Jx [x(O). We start by finding an upper bound for Jx (0) and then for Jx using equation] 7
Let St, i [1.....N} N} be some sub-spaces of bounded space S such that S = U S, 0 N S, Ø, and X2 E S, Then,
N (+) = Σ/
- ff(=))d(
iml S.
(x) = Σ
IIf(X, +x xx) (x
S.
Suppose that n, n. and twice differentiable. Let |S| S (s dIP The volume |S| 1 since dP is probability measure, and therefore |Sp| < 1 for all E [1...., N} Using Taylor expansion at order 2, and since |SS| < for all i [I,
(0) = Σ ((Xx)ff(XX)) xX,) x,)+ x - X1) 1=1
To find an upper bound for J(0), we can first find an upper bound for [A;(x)], with A+(x) = f(X)) (x, X,) f (X,) X,)² fz) + +0(z= - x2)
NN fo is K₂ Lipschitz, so since S is bounded (so are Si), for all r E S, (f(()) - fo(Xi) S
Kg l X²). Hence,
16

---

Under review as a conference paper at ICLR 2021
fx(x)) - s f6(X,) + Kolar X,l,
(o(()) Ko|x- $ + Kolæ Xil,
1 - - x1)9) - fo(())) -Kol - X,| + O((x - X1) 1
f(x)+ + (xx)((= - x1) +
A.)))) S f(X)) + (x, Xi) + 2 fx
x,)² -o((x))))))) + Kolz X11 + O((x x,)
A(x) f(x.) - fx(),) + (xx)
- x.) + 7 f x,)² Kof X2 + O((x X.))).
1
And finally, using triangular inequality,
A((x) s 1s(.)) -
Xil + (x,) - X,12 Kolæ X, + O(I2 X.1
Now, ||-|| being the squared L2 norm:
(0) Σ1
[lf(x.) + (xx X.) + (x -o)== O(1x IdIx)
i=1 S;
(0) - Σ
(1X(x))(((x3)) F6(x)))) + (15(x))1=== x,1+ 1 1 1 x,12 Kolp Xi)
s.
2
+ +0[ -xiP)
dPx.
Σ s.
/
[((x)) fo()))
+215(X,) so(x)) ( (x)()))) X x ((x:)]l - x,12+ + Kolæ x:1)
+ +[(r(()))l - x.1) (511((xx))l== - x,, Kol: [ol]=xx))]= O11x -x113) xx1))|lr dlxx
Σ5 (
((x)) 16(x))
S.
+2]f(X)) fo(x.)) (x) X11+ 1 (xx X,12 + Kolæ - xx1)
+ [1r(x))) x 2 x,I²+ K3 [}1²]] +0 -x19) dlx,
Σ / ((x,) 1o(x))p
S.
+ +2)((X)) fo(x))) (1(x))((((()))) (x))) -xil+ 1 f" (xxx)lx-xx, Kelæ X.I)
2 x x +0[x= xi13) dFx. + (17(X,)) + Ko)
Hornik's theorem (Horikk et al. 1989 states that given a norm I1-1 = such that If Is (dx))) with du probability measure, for any e. there exists 0 such that for a Multi Layer Perceptron, fe. (l) - fe(x)]p pau < c,
17

---

Under review as a conference paper at ICLR 2021
This theorem grants that for any with du Ei=1 2o Xi), there exists such that
N
[1((x) s0(x))11,
- - sox())
N
(8)
I1(xx) 10(1))1, Σ N ( Se.
Let's introduce such that argmin |S.]. Note that for anv E (I...,,N..... 0(1S)()))))) (((((t).
Now, let's choose such that e = O ()). Then, equation implies that
f(X,) - fx(),)) O(IS:
(J(X))- - -x(x))) O(IS,(t)
(x) = =11f(x) - -f,(x))2,, = O(SS:)). Thus, we have [x(0)= = (0) - ]x(0)= = =xx(0) + +(((Si(*) and therefore,
(x(0) Σ /
s. [(r(X))] + Ko) 1001x,PPPxx + +(Ss)))
==1
Finally,
S.13 (x(0)= S Σ - 1 + O(1s)*).
We see that on the regions where f'(,,) + Kg is higher, quantity |S,| (the volume of S;) has stronger impact on the GB. Then, since [S;] can seen as metric for the local density of the data set (the smaller |S:] is, the denser the data set is), the Generalization Bound (GB) can be reduced more efficiently by adding more points around X; in these regions. This bound also involves Ko, the Lipschitz constant of the NN, which has the same impact f'(X)). It also illustrates the link between the Lipschitz constant and the generalization error, which has been pointed out by several works like, for instance, Gouk al. (0018) Bartlett et al. (007) and Qian & Wegman 2019).
PROBLEM 1: UNAVAILABILITY OF DERIVATIVES (SECTION 4.1
In this paragraph, we consider n, > 1 but n, = The following derivations can be extended to no > by applying it f element-wise. Let ~ A/00, eln,) with E R+ and (E1, ... Cny); ie.. ~ N10, e). Using Taylor expansion on f at order gives
f(r + c) f(x) + Vaf(x) + _ _TT Hz,f(r) E + + O(14)))
2
With .. and H. (x) the gradient and the Hessian of f w.r.t. æ. We now compute Var(f(2) + E)) and make (x)) <l V=)(())) 1| + [ & appear in its expression to establish link between these two quantities:
Var(f(I +c)(((+)))= = Var ((x) + V2f(x) - z (.T.(.(()))) e e 0(1l(13)
= =Var ~Var(Vellz) e e Hef(z) . e) O(1e)1))
Since e (N((0,),
and with 0z.2,
0 (X) the cross derivatives of f w.r.t. i, and aj.
1 T. Hef(z) Vzf(z)- E TT.
Σ
n
E 0f
(x)
+
1 B4 Wi
EGEK
Ou (z),
8 f
Dr,
2
j=
18

---

Under review as a conference paper at ICLR 2021
Var (v)(()))) et _et H.f(()) -e) =Var
E
Of
+
EE D0r (x)
8
Oz
j=
Th
05
05 (1))
Cou
in dzn
(x)) 6n 0ziz
R4
74
R4
Ri
021
02
Cov Ejs cki jz.z Dk
(x), 6j2 ck2
jo (2)
12=1
R4
R2
Of (x), cjch 0r, (1))
0
Cov
(i 0z:
05 (x)
0s (x) (t1.
Ozg
diis
O (x)
8 Cor Eli E
Jzn Tkg
Dz Fk2
k==1
R1 Ri
05
0 (z) (t, c...)
Or.
0zyzk
In this expression, we have assess three quantities: Cou(ej fhy Ebg)
Coulci, and
First, since (e1,..,, Cn are i.d.d
[Var(e)== = if = i2 = i,
Cov Cou(ens (Ei, (iz) 10 otherwise.
To assess Cov(es, ejex), three cases have to be considered.
if j k, because Blei] O,
Cou(e,, Cov(c, e²), Ele B[e.]
0.
if = or = k (we consider k, and the result holds for i = j by commutativity).
Coo(ei EyEx. = Cov(e, Eze;),
Elc/c, - E[c]][/,)
E[c])
= 0.
If + j and i # h. and ejes are independent and so Cov(es, (zex) 0.
Finally, to assess Cou(C, Chy Cjz (2), four cases have to be considered:
If = j2 ki hi2
Coulen Chi (p2 Var(<?),
2
If ji = k = and j2 = ko = j. CoulC, Et, e (x2) = CoulE, e7) = since ef and e? are independent.
19

---

Under review as a conference paper at ICLR 2021
If f1 1/2 and 1 l2 k
Cou(es, Ehi Ek2 = Var(esea),
Var(e))Var(es),
= 2.
If j1 # 32 and k2,
Coules, Eki E2 = Eleg, Eki Ek2 - -Ble, ck2 [[(
E(eg, 5/2 Ble,, B[ek, Blee Ckal,
O.
All other possible cases can be assessed using the previous results, commutativity and symmetry of Cou operator. Hence,
Var (=f(x) ct 2 _ H.f(s)
Σ
as
(x)
os
(z)
Cisy Cia)
Ori
74
8 S
85 (z) Chi (32
(x)
Dzy Ikk
052
1
14 12
8 fz (z),
(x)
dz,
2
dzyzz
j=
k=1
1
= V.,o(> 2
=Df((x)
And finally,
Var(S(# + +)) +
(10)
If we consider Df2. as defined in equation on section
3.3 of the main document, Var(f(# + c)) Since Var(f(# c)) Df2(x) + O(Ilel)), 2 is a bi-
(z) 1-+00
ased estimator of (x), with bias O( Hence, when - 0, (x) becomes an unbiased estimator of f
20

---

Under review as a conference paper at ICLR 2021
APPENDIX C: HYPERPARAMETERS
This appendix Section is split in two parts. First, we describe the results of the experiments on the hyperparameters search of Boston Housing (BH) and Breast Cancer (BC) data sets (Section [5.]) The second part is a list of final hyperparameters values chosen for the experiments of the main paper.
EXPERIMENTS ON BOSTON HOUSING AND BREAST CANCER DATA SETS
For BH and BC experiments, we conduct grid search for VBSW on the values of and k. As reminder, m is the ratio between the highest and the lowest weights, and & is the number of neighbor points used to compute the local variance. We train linear model for BH and MLP with 30 units for BC with VBSW on a grid of values of m equally distributed between and 100 and 20 values of & equally distributed between 10 and 50. As result, train the model 400 pairs of (m, k) values, and with 10 different random seeds for each pair.
50
40
40
30
30
25
20
20
15
10
m
Figure 6: Color map of the error, with respect to m and Left: BH data set, for the mean of the MSE accross 10 different seeds and right: BC data set, for the mean of acc across these seeds. Blue lower.
These experiments, illustrated in Figure 6 shows that the influence of m and the performances of the model can be different. For BH data set, low values of & clearly lead to poorer performances. Hyperparameter m seems to have less impact, although should be chosen not too far from its lowest value, 2. For BC data set, at the contrary, the best performances are obtained for low values of k; while m could be chosen in high values. These experiments highlight that impact of m and k can be different between classification and regression, but it could also be different depending on the data set. Hence, we recommend considering these hyperparameters like many other involved in DL, and to select their values using classical hyperparameters optimization techniques.
This also shows that many different (m, k) pairs lead to error improvement. This suggests that the weights approximation does not have to be exact in order for VBSW to be effective, like stated in Section [544
21

---

Under review as a conference paper at ICLR 2021
PAPER HYPERPARAMETTRS VALUES
The values chosen for the hyperparameters of the paper experiments are gathered in Table g For
ADAM optimizer hyperparameters, kept the default values of Keras implementation. We chose these hyperparameters after simple grid searches.
Experiment
k
learning rate
batch size
epochs
optimizer
random seeds
double moon
100
20
1 x 10-3
100
10000
SGD
50
Boston housing
35
5 x 10-4
404
50000
ADAM
Breast Cancer
50
35
5 x 10-2
455
250000
ADAM
10
MNIST
40
20
x 10-3
25
25
ADAM
40
Cifarl0
40
20
1x 10-3
25
25
ADAM
50
RTE
20
10
3 10-4
8
10000
ADAM
50
STS-B
30
30
3 X 10-4
8
10000
ADAM
50
MRPC
75
25
3 X 10
16
10000
ADAM
50
Table 8: Paper experiments hyperparameters values
22


Reviews:
[{"review_id": "Z3FWTPHXzSr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 manuscript follows an intuitively straightforward conclusion: data should focus on the region where the function to learning is steeper. Based on that, a non-trivial method is proposed to improve the performance of NN. Empirical results are provided to support the performance of the proposed method.\n\nAccording to my understanding, the performance gain from the proposed sampling method mainly comes from the sample complexity part, or in other words, the variance part. Is this correct? The weight approximation method proposed method relies on the derivative of the estimated NN. Will this cause much randomness or error to the approximated weights, since making sure the derivative of the estimation is accurate is more challenging than making the estimation itself is accurate? \n\nSince provided analysis is mostly on the asymptotic level, it is quite unclear that how much noise/error the proposed sampling method may have, how much these noise will hurt the final NN estimation. So, is there any cases where the proposed sampling method will even hurt the performance of the NN? (For example, what will happen if the weights are poorly approximated?) If not, what are the key conditions to make sure that the sampling method really provides significant performance gains? \n\nAlso, can we iteratively implement the weight approximation and sampling method many times in Algorithm 1? If the proposed sampling method really helps the performance, we can have more accurate weight approximations, and further improve the performance....\n\nIn all, the method is interesting with improved performance supported by experiments. However, I believe more analysis on the constraints and potential error of the method will benefit the manuscript. \n\n  \n\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "FD6HRhuxTJP", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "A method for computing sample learning weights based on variance is proposed. The method is model independent and a simple k-NN based estimator for the weights is derived. The authors justify their work by appealing to a novel generalisation bound. Overall the idea is interesting but the exposition needs to be significantly improved as proofs are difficult to follow as it currently stands.\n\n# positives\n\n- The idea is interesting and intuitive: essentially concentrate more weight on points that are ambiguous and less on points that are easily learnt\n- The approach is potentially quite general covering a large range of learning tasks, though this needs to be carefully evaluated\n\n# cons\n\n- The exposition is very unclear, there are numerous typos and lack of detail in key sections of the proofs\n- Though the authors make statements that the method is very general, the empirical evaluation does not validate this. There is no attempt to apply their method to anything other than a NN. Furthermore, many tasks cited by the authors (e.g., class imbalance & noisy labels in the intro) are implied to be covered by this framework, yet are not evaluated. It's difficult to see how this weighting strategy will improve the noisy label scenario in particular.\n- The benchmark in experiments is an unweighted NN. While this is a good benchmark, it would be good to see some alternative sample weighting methods since according to the authors \"Sample weighting has already been explored in many works and for various goals.\"\n\n# some examples of confusing sections\n\n- figure 1 lacks axis labels, and panel labels. It takes far too long to read as a result\n- page 16: each line states (Jx(theta) <= ...) even though equality holds between the steps. This makes it difficult to see where bounds have been used. Most of this section is simple algebra and could be shortened.\n- page 17: The section invoking Hornik's theorem is unclear and need to be expanded with more detail. \n\n# update\n\nThe authors have addressed a number of issues and strengthened their submission.", "extra_scores": {}, "extra_text": {}}, {"review_id": "EpWm4yBroiW", "reviewer": "AnonReviewer4", "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": "**Summary of paper**\n\nThe authors introduce an algorithm called VBSW to re-weight a training data set in order to improve generalization. In summary, VBSW sets the weight of each example to be the sample variance of the labels of its k nearest neighbors. The nearest neighbors are chosen in the embedding space from the second-to-last layer of a pre-trained neural network. The last layer of the pre-trained model is then trained with these new weights.\n\nThis approach is quite simple in practice and seems to be theoretically justified.\n\nThe authors demonstrate that VBSW achieves better test accuracy than not using VBSW on 3 toy datasets and 5 real-world datasets.\n\n**Conclusions**\n\nQuality: The authors did not experimentally compare VBSW to any alternative algorithms. I find this omission inexcusable. The problem of re-weighting examples to achieve better accuracy has been studied for decades; there are many other algorithms to compare against.\n\nClarity: The paper is generally well-structured and well-written, although with a few typos and grammatical errors.\n\nOriginality: I am not familiar enough with the related work to say whether this idea is novel. However, seems quite simple and potentially very similar to existing published techniques.\n\n**Comments**\n\nSection 3.1 seems to assume that the labels have no noise. For example, if two examples have the same input features, their labels seem to be generated by the same function f, which would always produce the same label for both examples. This seems unrealistic.\n\nSection 2 describes the author's VBSW algorithm as being applied \"prior to the training\", but the algorithm actually requires a neural network to be pre-trained before the reweighting procedure. I felt the beginning of the paper was misleading in this regard.\n\n**Minor comments**\n\nTable 1: The difference between the mean accuracies of VBSW vs. basline on the BC dataset seems statistically insignificant; I believe VBSW should not be bolded.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0lXmejARo_N", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 is well written and very well structured. I think this paper can be interesting for ICLR community. The authors presented experimental results that show marginal improvement using VBSW in both regression and classification applications. The experimental improvement is limited; however, it makes sense since the proposed approach is a preprocessing stage that can not be dynamically tuned during the learning process. \nI am interested to see experiments (for synthetic and real datasets) wherein the steep region is noisy, demonstrating how well the proposed strategy works in the presence of noise.  \nOne can expect that focusing too much on the noisy steep regions can be harmful to the learning process. \n\nIn my opinion, the investigated problem has been described and motivated properly. It is interesting to formally show (via the presented generalization bound) why NN needs more points in the steep regions and how the steep regions can be formally approximated. The study has proposed reasonable approximations for the cases where the derivations are not available and computing new labels. The theory that backs the statements made in this study seems correct. However, I am concerned about their experimental results that do not seem significant (gain per model is limited). Also, it would be interesting to see a noise robustness investigation in the steep regions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: # Paper Summary

This paper proposes "variance based sample weighting" (VBSW). The key observation is that, in areas where the labeling function is changing rapidly, more samples may be required to achieve a good fit. In Section 3, they justify this intuition by showing that areas in which the label gradient is higher disproportionately impact the generalization performance, and go on to propose upweighting examples proportionately to the local label variance.

This label variance is approximated, for each training example, by finding its k-nearest-neighbors (either in the feature space, or a latent space--they use the latter in their experiments), and calculating the sample variance of the labels. There's a bit of a leap here: the authors started advocating for drawing more samples from rapidly-changing regions, but ended up upweighting the existing samples. These are not the same thing, but this issue is not discussed.

The experiments are well-thought out and comprehensive (although Reviewer 4 complained about a lack of nontrivial baselines, and I agree). The first and fourth set of experiments are particularly impressive. The first uses toy datasets to enable easy visualization, while the fourth (added during the response based on a comment of Reviewer 1) explores how robust VBSW is to hyperparameter choices and label noise. The second and third sets of experiments are on "realistic" problems, and while the gains are arguably marginal, VBSW does show consistently positive results.

# Pros

1. The reviewers agreed that the fundamental idea was intuitive and well-explained
1. The algorithm is general, and easy to implement
1. Reviewer 1 asked how robust VBSW was to hyperparameter choices and label noise, and the authors added a new section that I think does an excellent job alleviating such concerns
1. Experiments are comprehensive, including both toy datasets on which the behavior of the algorithm can be easily visualized, and more realistic experiments on MNIST, CIFAR 10,  RTE, STS-B AND MRPC. They show consistently positive results (although not especially large ones)

# Cons

1. The reviewers had mixed opinions on the writing quality, although they generally agreed that it was well-organized. There are a large number of typos, grammatical errors, and awkward phrases
1. Reviewer 4 noted that Section 3 assumes that there is no label noise, which seems unrealistic
1. Reviewers 2 and 4 complained about a lack of nontrivial baselines in the experiments (reviewer 4 called this "inexcusable"). In response, the authors added a new experiment comparing with active bias, on which the results were arguably positive, but not convincingly so. Regardless, this is only one experiment--there should be baselines for all experiments (except perhaps for the ones on UCI datasets), ideally multiple baselines (would a curriculum learning approach be appropriate on any of these tasks?)

# Conclusion

Three of the four reviewers recommended acceptance, but reviewer 4 gave a very negative score (3: clear rejection). Most of this reviewer's criticisms were fairly minor, with the two major ones being (i) that Section 3 unrealistically assumes that there is no label noise, and (ii) that the experiments have no nontrivial baselines. This first criticism is, I think, not a *huge* deal: Section 3 is only intended to provide intuition. The authors attempted to address the second criticism by adding one experiment comparing to "active bias", but I think that this is insufficient. In addition, while the paper is well-structured, I agree with the reviewers who complained about the paper's lack of polish.

All reviewers praised the fundamental idea, and said that the authors gave good intuition for their approach. The experimental results are also fairly comprehensive (aside from the lack of nontrivial baselines), and show positive results. The new section on robustness (in response to Reviewer 1) is a great addition that, I think, fills in most of the remaining "gaps" in this work. The major outstanding issues, in my opinion, are the writing quality, and the lack of nontrivial experimental baselines. These are very fixable, but I think that they're too significant for the paper to be accepted. Overall, I think that this is a borderline paper, but it's on the rejection side of the boundary.
Decision: Reject