Why resampling outperforms reweighting for correcting sampling bias with stochastic gradients
Authors: Jing An
Lexing Ying
Yuhua Zhu
Venue: ICLR 2021 Poster (2021)
Keywords: biased sampling
reweighting
resampling
stability
stochastic asymptotics

Abstract: A data set sampled from a certain population is biased if the subgroups of the population are sampled at proportions that are significantly different from their underlying proportions. Training machine learning models on biased data sets requires correction techniques to compensate for the bias. We consider two commonly-used techniques, resampling and reweighting, that rebalance the proportions of the subgroups to maintain the desired objective function. Though statistically equivalent, it has been observed that resampling outperforms reweighting when combined with stochastic gradient algorithms. By analyzing illustrative examples, we explain the reason behind this phenomenon using tools from dynamical stability and stochastic asymptotics. We also present experiments from regression, classification, and off-policy prediction to demonstrate that this is a general phenomenon. We argue that it is imperative to consider the objective function design and the optimization algorithm together while addressing the sampling bias.


Published as a conference paper at ICLR 2021
WHY RESAMPLING OUTPERFORMS REWEIGHTING FOR CORRECTING SAMPLING BIAS WITH STOCHASTIC GRA- DIENTS
Jing An, Lexing Ying and Yuhua Zhu
Stanford University
{jingan, lexing, yubuazhu
ABSTRACT
A data set sampled from certain population is biased if the subgroups of the pop- ulation are sampled at proportions that are significantly different from their under- lying proportions. Training machine learning models on biased data sets requires correction techniques to compensate for the bias. We consider two commonly- used techniques, resampling and reweighting, that rebalance the proportions of the subgroups to maintain the desired objective function. Though statistically equivalent, it has been observed that resampling outperforms reweighting when combined with stochastic gradient algorithms. By analyzing illustrative exam- ples, we explain the reason behind this phenomenon using tools from dynamical stability and stochastic asymptotics. We also present experiments from regression, classification, and off- off-policy prediction to demonstrate that this a general phe- nomenon. We argue that it is imperative to consider the objective function design and the optimization algorithm together while addressing the sampling bias.
INTRODUCTION
A data set sampled from a certain population is called biased if the subgroups of the population are sampled at proportions that significantly different from their underlying population proportions. Applying machine learning algorithms naively to biased training data can raise serious concerns and lead to controversial results (Sweeney 2013) Kay al., 2015) Menon et al. (020). In many domains such as demographic surveys, fraud detection, identification of rare diseases, and natural disasters prediction, model trained from biased data tends favor oversampled subgroups by achieving high accuracy there while sacrificing the performance on undersampled subgroups. Although one can improve by diversifying and balancing during the data collection process, is often hard or impossible to eliminate the sampling bias due to historical and operational issues.
In order to mitigate the biases and discriminations against the undersampled subgroups, common technique is to preprocess the data set by compensating the mismatch between population pro- portion and the sampling proportion. Among various approaches, two commonly-used choices are reweighling and resampling. In reweighting. one multiplies each sample with a ratio equal to its pop- ulation proportion over its sampling proportion. In resampling, on the other hand, one corrects the proportion mismatch by either generating new samples for the undersampled subgroups or selecting a subset of samples for the oversampled subgroups. Both methods result in statistically equivalent models in terms of the loss function (see details in Section 2}. However, it has been observed in practice that resampling often outperforms reweighting significantly, such as boosting algorithms in classification (Galar et al. 201 I Seiffert al. 2008), off-policy prediction in reinforcement learning (chlegel et al. 2019) and so on. The obvious question is why.
Main contributions. Our main contribution is to provide answer this question: resampling outperforms reweighting because of the stochastic gradient-type algorithms used for training. To the best of our knowledge, our explanation is the first theoretical quantitative analysis for this phe- nomenon. With stochastic gradient descent (SGD) being the dominant method for model training, analysis is based on some recent developments for understanding SGD. We show via simple and

---

Published as a conference paper at ICLR 2021
explicitly analyzable examples why resampling generates expected results while reweighting per- forms undesirably. Our theoretical amalysis is based on two points of view, one from the dynamical stability perspective and the other from stochastic asymptoties.
In addition to the theoretical analysis, we present experimental examples from three distinct cat- egories (classification, regression, and off-policy prediction) to demonstrate that resampling out- performs reweighting in practice. This empirical study illustrates that this is a quite general phe- nomenon when models are trained using stochastic gradient type algorithms.
Our theoretical analysis and experiments show clearly that adjusting only the loss functions is not sufficient for fixing the biased data problem. The output can be disastrous if one overlooks the optimization algorithm used in the training. In fact, recent understanding has shown that objective function design and optimization algorithm are closely related, for example optimization algorithms such as SGD play a key role in the generalizability of deep neural networks. Therefore in order to address the biased data issue, we advocate for considering data, model, and optimization as an integrated system.
Related work. In broader scope, resampling and reweighting can be considered as instances of preprocessing the training data to tackle biases of machine learning algorithms. Though there many well-developed resampling (Mani & Zhang 2003 He & Garcial 2009; MMciijewsski & Stefanowski] 2011) and reweighting (Kumar et al. 2010; Malisiewicz et al. [01 Chang et al.)
2017) techniques, we only focus the reweighting approaches that do not change the optimization problem. It has been well-known that training algorithms using disparate data can lead to algorithmic discrimination (Bolukbasi
al., 2016 Caliskan et al., (017). and over the years there have been growing efforts to mitigate such biases, for example see (Amini et al. 2019) Kamiran & Calders 2012 Calmon et al. 2017 Zhao et al., 2019; López et al., 2013). We also refer to (Guo al. 2017 He & Ma 2013 Krawczyk] (016) for a comprehensive review of this growing research field.
Our approaches for understanding the dynamics of resampling and reweighting under SGD are based on tools from numerical analysis for stochastic systems. Connections between numerical analysis and stochastic algorithms have been rapidly developing in recent years. The dynamical stability perspective has been used in (Wu et al. (0188) to show the impact of learning rate and batch size in minima selection. The stochastic differential equations (SDE) approach for approximating stochas- tic optimization methods can be traced in the line of work (Li ct al. 2017 2019 Rotskoff & Vanden-
Eijnden 2018 Shi et al. 2019). just to mention a few.
2 PROBLEM SETUP
Let us consider population that is comprised of two different groups, where a proportion an of the population belongs to the first group, and the rest with the proportion 02 = to the second (i.e., a1, 02 > and 01 + 02 =)) In what follows, we shall call d1 and 02 the population proportions. Consider an optimization problem for this population over parameter For simplicity, we assume that each individual from the first group experiences a loss function (9), while each individual from the second group has loss function of type (2)) Here the loss function (0) is assumed to be identical across all members of the first group and the same for (f) across the second group, however it is possible extend the formulation to allow for loss function variation within each group. Based on this setup, a minimization problem over the whole population is to find
belongs
0" = arg arg min V(0), where V(0) = a Vi( + (0).
For a given set Ω of N individuals sampled uniformly from the population, the empirical minimiza- tion problem is
8* = arg min
1 N
Σ (O), PEN
where i, E 21 denotes which group individual belongs to. When N grows, the empirical loss in (2) is consistent with the population loss in ( as there are approximately a fraction of samples from the first group and dg fraction of samples from the second.
2

---

Published as a conference paper at ICLR 2021
However, the sampling can be far from uniformly random in reality. Let ny and ny with n1 tn N denote the number of samples from the first and the second group, respectively. It is convenient to define fa. i 1, 2 as the sampling proportions for each group, i.c., fi = ny /N and f2 n2/N with fi + f2 = 1. The data set is biased when the sampling proportions fi and fz are different from the population proportions a and 02. In such case, the empirical loss is Vi (2), which is clearly wrong when compared with (T.
Let us consider two basic strategies to adjust the model: reweighting and resampling. In reweighting, one assigns to each sample E Ω a weight oi,/ fi, and the reweighting loss function is
1 Σ air v., = 01 (0) + (2(). R
1
V (0)
N
In resampling, one either adds samples the minority group (i.e., oversampling) or removing sam- ples from the majority group (i.e., undersampling). Although the actual implementation of over- sampling and undersampling could be quite sophisticated in order to avoid overfitting or loss of information, mathematically we interpret the resampling as constructing new set of samples of size M. among which a samples are of the first group and a samples of the second. The resampling loss function is
1 E = Vo( = M
- (0) v2)))
(4)
Notice that both (0) and VO) are consistent with the population loss function V(0). This means that, under mild conditions on Vi (0) and V2( deterministic gradient descent algorithm from generic initial condition converges to similar solutions for (0) and (²( J. For a stochastic gradient descent algorithm, the expectations of the stochastic gradients of V. (0) and V2(0) also agree at any value. However, as we shall explain below, the training behavior can be drastically different for a stochastic gradient algorithm. The key reason is that the variances experienced for (w) and (+) can drastically different: computing the variances of gradients for resampling and reweighting reveals that
(V) = al VV(())VV + +22 - (0])
Vi (6) = at fi VV(())VV(())) + ab f2
(5)
VV2())VV2()) - (E]V
These formulas indicate that, when fi/ is significantly misaligned with a /22, the variance of reweighting can be much larger. Without knowing the optimal learning rates a priori, it is difficult to select an efficient learning rate for reliable and stable performance for stiff problems, when only reweighting is used. In comparison, resampling is more favorable especially when the choice of learning rates is restrictive.
STABILITY ANALYSIS
Let us use a simple example to illustrate why resampling outperforms reweighting under SGD, from the viewpoint of stability. Consider two loss functions Ví and V/2 with disjoint supports,
(0 + 1)2 2 0 P<0 0>00 0,
0. (0 1)2 3 >> 0,
0
Vi (0)
V3(0)
(6)
0,
each which is quadratic on its support. The population loss function is V(0) = a1 V1(()) + (2)), with two local minima 0 -1 and
1. The gradients for V1 and V/2 are
0 050
(0
050
VVi
VV2(0)
0,
0>0. 0.
0
0 > 0.
Suppose that the population proportions satisfy d2 > a1, then 0 = 1 is the global minimizer and it is desired that SGD should be stable near it. However, shown in Figure when the sampling proportion f2 is significantly less than the population proportion a2, for reweighting become unstable: even if one starts near the global minimizer 0 1, the trajectories for reweighting
can easily
3

---

Published as a conference paper at ICLR 2021
0.6
0.6
V(6)
V(0)
0.2
0.2
0.2
-32
2
8 -2
(1) Reweighting
(2) Resampling
Figure I: Comparison of reweighting and resampling with 01 0 0.4/0.6 and f1/f2 = 0.9/0.1 the learning rate 7) = 0.5. The resampling strategy here is to randomly select the sub-population with the probability with replacement in each iteration. (1) For reweighting, the trajectory starting from 0p- = 1.1 can end up at -1 after few iterations, but = is not the global minimizer. (2) For resampling. the trajectory starting from 0o 2.0 stays close to the desired minimizer 0 1. Hence resampling is more reliable than reweighting. We include more comparisons with various learning rates in Appendix to show that resampling is stable for wider range of 17.
always gear towards = 1 after a few steps (see Figure 1)). On the other hand, for resampling is quite stable (see Figure (2)).
The expectations of the stochastic gradient are the same for both methods. It is the difference in the second moment that explains why trajectories near the two minima exhibit different behaviors. Our explanation is based on the stability analysis framework used in (Wu et al. 2018). By definition, stationary point 6" is stochastically stable if there exists uniform constant O C 1 such that E][[0, 0- [|²] < ClI00 112, where 0₂ is the k-th iterate of SGD. The stability conditions for resampling and reweighting are stated in the following two lemmas, in which we use rj to denote learning rate.
Lemma 1. For resampling, the conditions for the SGD be stochastically stable around -1
and 0 = 1 are respectively
(1-na1)² a2aa22 $,, (1-102)) n02)2 + a2 $1.
Lemma 2. For reweighting, the condition for the SGD to be stochastically stable around 0 = -1 and f are respectively
(1 na1) +1 f1.2
a1
S1,
(1- +
1
Note that the stability conditions for resampling are independent of the sampling proportions (2), while the ones for reweighting clearly depend on (21, We defer the detailed com- putations Appendix(A)
Lemma 2 shows that reweighting can incur a more stringent stability criterion. Let us consider the 0 and fe/ fi < 1. For reweighting, the with small constant global minimum 0 = is stochastically stable only if 17(1 + fi/ f2) < 4 + O(c). This condition becomes rather stringent in terms of the learning rate 7) since f1/f2 > 1. On the other hand, the local minimizer 0 1 is stable if 17(1 f2/ < 4+ O which could be satisfied for a broader range of yy because f2/ fi < 1. In other words, for fixed learning rate y, when the ratio f2/ fi between the sampling proportions is sufficiently small, the desired minimizer 0 1 is longer statistically stable with respect to SGD.
case a1
E, a2
SDE ANALYSIS
The stability analysis can only be carried for learning rate 77 of a finite size. However, for small learning rate 77, one can show that the reweighting method is still unreliable from a different perspective. This section applies stochastic differential equation analysis to demonstrate it.
4

---

Published as a conference paper at ICLR 2021
Let again simple example illustrate the main idea. Consider the following two loss functions,
Vi(0)= { 1 c8,
0 0>0 (2 [ - -
0 e
8>01 0>0%
with 0 < c < The population loss function ( = a1 (1 + (2) with local minimizers Note that the O(e) terms are necessary. Without it, if the SGD starts in (-oo, 0), all iterates will stay in this region because there is no drift from V2(0). Similarly, if the SGD starts in (0, 00), no iterates will move to (-o,,), 0). That means the result of SGD only depends on the initialization when (e) term is absent.
= -1 and
In Figure we present numerical simulations of the resampling and reweighting methods for the designed loss function V@)). If 02 d1, then the global minimizer of V(0) is = (see the Figure 1)) Consider setup with population proportions 01 /az 0.4/0.6 along sampling proportions f1/f2 = 0.9/0.1, which are quite different. Figures 2 and (3) show the dynamics under the reweighting and resampling methods, respectively. The plots show that, while the trajectory for resampling is stable across time, the trajectory for reweighting quickly escapes to the (non-global) local minimizer& = -1 even when it starts near the global minimizer !
04
iteration
iteration
044
(1) Loss function ((0)
(2) Reweighting
(3) Resampling
Figure 2: Comparison of reweighting and resampling with learning rate = 0.12. We set ai 01/02 = 0.4/0.6, f1/22 0.9/0.1 and 0.1. Both experiments start at On 0.9. The resampling strategy here is to randomly select the sub-population with the probability a, with replacement in each iteration. In (2) where reweighting is used, the trajectory skips to the local minimizer 0 = -1 later. (3) where resampling used, it stabilizes at the global minimizer & = all the time. We include comparisons with various learning rates in Appendix D to show that resampling is more reliable for a wider range of n7.
When the learning rate is sufficiently small, one can approximate the SGD by an SDE, which in this piece-wise linear loss example is approximately Langevin dynamics with a piecewise constant mobility. In particular when dynamics reaches equilibrium, the stationary distribution of the stochastic process is approximated by Gibbs distribution, which gives the probability densities the stationary points. Let us denote (f) and (0) as the stationary distribution over under resampling and reweighting, respectively. Following lemmas quantitatively summarize the results.
Lemma 3. When > an V(1) < (--1). The stationary distribution for resampling satisfies the relationship
(1) = exp (-ay (V(1) ((1))v(-1)) +0( (-(1
2
Lemma 4. With as > a. V(1) V(-1) < Under the condition f2 <
V
for the
f1 sampling proportions, the stationary distribution for reweighting satisfies the relationship
v(1)
(1) / exp (w a
2/2/ V(1) + 2/1/2v((1) 0(s) <1. az
079
The proofs of the above two lemmas can be found in Appendix B Lemma shows that for re- sampling is always more likely to find 9 the global minimizer than the local minimizer -1. Lemma 4 states that for reweighting it is more likely to find at the local minimizer - when
fa < V(1) Together, they explain the phenomenon shown in Figure
fi
5

---

Published as a conference paper at ICLR 2021
To better understand the condition in Lemma let consider the case a1 = with a small constant é > O. Under this setup, ((-1)/V(11 = 1. Whenever the ratio of the sampling proportions f2/ fi is significantly less than the ratio of the population proportions 0z/01 s 1, reweighting will lead to the undesired behavior. The smaller the ratio f2/ f1 is, the less likely the global minimizer will be visited.
+ c, -,
The reason for constructing the above piecewise linear loss function is to obtain an approximately explicitly solvable SDE with constant coefficient for the noise. One can further extend the re- sults in ID for piecewise strictly convex function with two local minima (See Lemmas 9 and TT in Appendix B.3). Here we present the most general results in ID. that is, piecewise strictly con- vex function with finite number of local minima. One may consider the population loss function V(0) Ex=1 a, (i))) with (0) h.(0) for 0,-1 < 0 S Og and (0) O(e) otherwise, where (0) are strictly convex functions and continuously differentiable, (c)) term is sufficiently small and smooth. Here {0.)/=] are k - 1 disjoint points, and 0g = -oo, 02 = Do. We assume that V(0) has & local minimizers 07 for 0- E (0:-1, 0.). We present the following two lemmas with suitable assumptions (See Appendix for details of assumptions, the proof and follow-up discussions).
Lemma 5. The stationary distribution for resampling at any two local minizers 87. 07 with p 9 satisfies the relationship
Pe (77) Pe (e,)
2
0, (2)
1
+0()=
>1, 1, as > agi <1, af < ag:
exp
d8 ap 1
71 Jez
Lemma 6. The stationary distribution for reweighting at any two local minizers fg 0g with > satisfies the relationship
Pw (10
2
0p 1 d0 oz 12(0)
Sp (p)-pp) 5p)
a f4) )
Sa
+(e))
Pio (0)
exp
ap(1 ap(1-5p)
Multi-dimennional results. Let us now consider the minimization of (0) a. +22))) for more general Vi, 1/2 and also in high dimensions. is in fact not clear how to extend the above stochastic analysis to more general functions (0)). Instead we focus the transition time from one stationary point to another in order to understand the behavior of resampling and reweighting. For this purpose, we again resort the SDE approximation of the SGD in the continuous time limit.
Such a SDE approximation, first introduced in (Li et al. 2017). involves a data-dependent covariance coefficient for the diffusion term and is justified in the weak sense with an error of order (( More specifically, the dynamics can be approximated by
de = - VVV( (VTO))d-VVE(())22
where O(t = kn) z 0g for the step l parameter 0g. 17 isis the learning rate, and E(O) is the covariance of the stochastic gradient at location θ. In the SDE theory, the drift term VV(.) is usually assumed to be Lipschitz. However, in machine learning (for example neural network training with non-smooth activation functions), it is common to encounter non-Lipschitz gradients of loss functions (as in the example presented in Section 3). To fill this gap. we provide in Appendix Cla justification of SDE approximation for the drift with jump discontinuities, based on the proof presented in (Müller-
Gronbach et al. 2020). The following two lemmas summarize the transition times between the two local minimizers.
Lemma 7. Assume that there are only two local minimizers 07. 03 for the objective function V()).
Let T8 -0z be the transition time for O(t) in i from the e-neighborhood of 0 (a closed ball of radius e centered at 05) to the e-neighborhood of 0 and Toz-00 be the transition time in the opposite direction. Then
El -87] E Tog - V dct(V22((1))
(et(V)))))))
exp (2
(VV (V
)) + O(V2).
E(O1)
E(0;)
Here L(0))) and ded ((0))) are the determinants of the Hessians 0 and 0z respec- tively. (Bt) = V(0P) - ((2) ( for k = 1,2 where 6 is the saddle point between 8 8:
'The formal definition of 0% Let 0(t) be a path with 0(0) = 07,0(1) = 05. then 0(t) arg ming(1) suPreju.aj ((((t)) is the path with minimal saddle point height among all continuous paths. 0o = sUPre(O..) O(t) the saddle point of this path.

---

Published as a conference paper at ICLR 2021
This lemma is known in the diffusion process literature the Eyring- Eyring-Kramers Kramers formula; see, e.g., [Berglund 2011 Bovier et al. 2004| 2005). Using the above lemma, we obtain the following result for the transition times for resampling and reweighting.
Lemma 8. Assume that there are only two local minimizers 87 B3 for the objective function V(0). Also assume that the loss function Vi(+) for the first group is O(e) in the e-neighborhood of 0 and the loss function V2(-) for the second group is O(e) in the e-neighborhood of 0i. In addition, assume that the determinants of the Hessian two local minimizers are the same. Then the ratio of the transition times between the two local minimizers for resampling is
- exp
2
(V))
8V 5V(05)
)) +O(VE)
E T0z -00 and the ratio for reweighting is
77 ai (VVVVVV)))))
a2 (O))
00
(
(0) Of (VVI(OT)V
a (VV2())) )) +0(V))
(25V(0))
f2vV (0)
exp
0 O07
See Appendix B for the proof. When the ratio is larger than 1, it means that 07 is more stable than 02. This result shows that for reweighting the relative stability of the two minimizers highly depends on the sampling proportions (2), On the other hand, for resampling it is independent of (f1. fz), which is precisely the desired result for bias correction procedure. To see how the sampling proportions affect the behavior of reweighting, let us consider a simple case where Of is the global minimizer, VVi (0T) VV, (01)
VV2))) an 1 + 6, 1 e, and fi < f2. This ensures that (01) > (V(6%) and the above ratio for resampling is larger than 1, which is the desired result. However, f1 < fa implies that 4 < 1, fa > 1, and the above ratio for reweighting much smaller than 1, which means that the local minimizer 0% is more stable than the global minimizer 0j.
oz
5 EXPERIMENTS
This section examines the empirical performance of resampling and reweighting for problems from classification, regression, and reinforcement learning. As mentioned in the previous sections, the noise of stochastic gradient algorithms makes optimal learning rate selections much more restric- tive for reweighting, when the data sampling is highly biased. In order to achieve good learning efficiency and reasonable performance in a neural network training, adaptive stochastic gradient methods such as Adam (Kingma & Ba. 2014) are applied in the first two experiments. We observe that resampling consistently outperforms reweighting with various sampling ratios when combined with these adaptive learning methods.
Classification. This experiment uses the Bank Marketing data set from (Moro et al., 2014) to predict if client will subscribe term deposit. After preprocessing, the provided data distribu- tion over the variable "y" that indicates the subscription, is highly skewed: the ratio of "yes" and 4640/36548 se 1/7.88. We assume that the underlying population distribution is a1/02 = 1. We setup 3-layer neural network with the binary cross- cross-entropy loss function and train with the default Adam optimizer. The training and testing data set is obtained using train test split provided in skleam?" The training takes 5 epochs with the batch-size equal to 100. The performance compared among the baseline (i.e. trained without using either resampling or reweighting). re- sampling (oversample the minority group uses the sample with replacement), and reweighting. We run the experiments 10 times for each case, and then compute and plot results by averaging.
"no" is fi/f2
To estimate the performance, rather than using the classification accuracy that can be misleading for biased data, we use the metric that computes the area under the receiver operating characteristic curve (ROC-AUC) from the prediction scores. The ROC curves plots the true positive rate on the y-axis versus the false positive rate on the æ--axis. As a result, larger area under the curve indicates a better performance of classifier. From both Table and Figure we see that the oversampling has the best performance compared to others. We choose oversampling rather than undersampling for the resampling method, because if we naively down sample the majority group, we throw away many information that could be useful for the prediction.
hhttps:/ssciii Tearn. ort.stableleeeeeeeeeoeooegegg
stable

---

Published as a conference paper at ICLR 2021
Baseline
Resampling
Reweighting
training loss
0.3221
0.2602
0.2831
roc auc score
0.9277
0.9516
0.9312
Table 1:
The loss takes the binary cross-entropy with a 3-layer neural network. We see that in average of 10 trials, the resampling method (oversampling) achieves the lowest training loss and highest ROC-AUC score over testing data among all tested cases.
Nonlinear Regression. This experiment uses the California Housing Prices data se to pre- dict the median house values. The target me- dian house values, ranging from 15k 500k,
Receiver operating characteristic curve
0.8
are distributed quite non-uniformly. We select subgroups with median house values 400k (1726 in total) and < 200k (11767 in total) and combine them make processing step, we drop the "ocean proximity" feature and randomly set 30% of the data to be the test data. The remaining training data set with 8 features is fed into 3-layer neural net- work. The population proportion of two sub- groups is assumed to ai/as 1, while re- sampling and reweighting are tested with var- ious sampling ratios fi/f2 near 11767/ /1726. Their performance of is compared also with the baseline. In each test, the mean squared error (MSE) is chosen the loss function and Adam used as the optimizer the model. The batch-size is 32 and the number of epochs 400 for each case. As shown Table 2 resampling significantly outperforms reweighting for all sampling ratios in terms of a lower averaged MSE, and its good stability is reflected in its lowest standard deviation for multiple runs.
True Rositive Rate
0.6
dataset. In the pre-
0.4
0.2
Baseline
Resampling
Reweighting
0.0
0.2
0.4
0.6
0.8
1.0
False Positive Rate
Figure 3: The ROC curve comparisons show that the resampling has the largest area under the curve.
MSE
Baseline
RS
RW (fi/22 7)
RW (fi/2e =
RW (fi/f2 12)
1.0386e+05
7.9679e+04
9.3567e+00
9.0436c+04
9.1949c+04
std
8.037Ie+03 1.8620e+03
3.8044c+03
2.4692c+03
3.0341c+03
Table 2: Mean squared errors (MSE) for nonlinear regression problems. RS stands for resampling and RW for reweighting. The weights used in reweighting are d) and da respectively. For each fz
case, run experiments for 10 times and compute the corresponding mean and standard deviation. Resampling (oversampling the minor group) achieves the lowest mean and standard deviation of MSE among all tested cases.
Off-policy prediction. In the off-policy prediction problem in reinforcement learning, the objec- tive is to find the value function of policy チ using the trajectory {(ar, 8t, 9t+1))7 generated by behavior policy μ. To achieve this, the standard approach is to update the value function based on behavior policy's temporal difference (TD) error d(x;) = R(s;) + (V(++11 - V(s,) with an p(als) E[ő]s; = = a))s(a)s), where the summation is taken over the action space A. The resulting reweighting TD learning for policy is
importance weight [= = = EaEa
=(als)
T(ae(s)) Vi+1(s)) Vi(s.) (((a)s)))
(R(st) + VVi(544) V((ss)).
where 7 is the learning rate. This update rule an example of reweighting. the other hand, the expected TD enror can also be written in the resampling form, [, s] MaEA E[o]s,
httpp::/ /ww::///wwwww/..m kaggle. http://wwwggg.aooooo/////ooaaaaa
8

---

Published as a conference paper at ICLR 2021
ae alx(als) Enea 2-=1 B| s,d, a), where N is the total number of samples for 5t s. This results to resampling TD learning algorithm: at step
[(a)s)
(st)($;) (i((s) ()((s)) + +Vi((s++1) Vi(ss)), where (aks Sk: Sk+1) is randomly chosen from the data set {(ay, S3. 81+1) with probability (ax]se).
Consider simple example with discrete state space $
action space A {+1). discount factor y = 0.9 and transition dynamics $141 = mod (2 + de. n). where the operator mod (m, n) gives the remainder of divided by n. Figure 4 shows the results of the off-policy TD learning by these two approaches, with the choice of n = 32 and r(s) = + sin(2rs/n) and learning rate while the behavior policy is (((as(s)
? 0.1. The target policy is (aa difference between the two policies becomes larger as the constant c E [0, 1/2] increases. From the previous analysis, if one group has much fewer samples as it should have, then the minimizer of the reweighting method is highly affected by the sampling bias. This is verified in the plots: as c becomes larger, the performance of reweighting deteriorates, while resampling is rather stable and almost experiences no difference with the on-policy prediction in this example.
cO.- The
Decay
Rothowll1
RWicod
Rib Ged
0.5
PR5 1/5 RSsteei
HS5 1/5
-15
2-
state 25
x10*
Figure 4: The left plot shows the approximate value function obtained by the two methods. The right plot is the evolution of the relative error log( [)), where the absolute error e, = [[V[(s) - (*) RW and RS in the upright corner represent reweighting and resampling, respectively. e determines the behavior policy (sa;(s) 2 + cag, The value function trained trajectory with length 105 generated by the behavior policy. The value function obtained from resampling is fairly close to the exact value function, while the results of reweighting gets worse the behavior policy gets further from the target policy.
DISCUSSIONS
This paper examines the different behaviors of reweighting and resampling for training on biasedly sampled data with the stochastic gradient descent. From both the dynamical stability and stochastic asymptotics viewpoints, we explain why resampling is numerically more stable and robust than reweighting. Based on this theoretical understanding, we advocate for considering data, model, and optimization integrated system, while addressing the bias.
An immediate direction for future work to apply the analysis to more sophisticated stochastic training algorithms and understand their impact resampling and reweighting. Another direction to extend our analysis to unsupervised learning problems. For example, in the principal component analysis one computes the dominant eigenvectors of the covariance matrix of data set. When the data set consists of multiple subgroups sampled with biases and a stochastic algorithm is applied compute the eigenvectors, then interesting question is how resampling or reweighting would affect the result.
ACKNOW
The work of L.Y. and Y.Z. is partially supported by the U.S. Department of Energy via Scien- tific Discovery through Advanced Computing (SciDAC) program and also by the National Science Foundation under award DMS-18 1818449. J.A. is supported by Joe Oliger Fellowship from Stanford University.

---

Published as a conference paper at ICLR 2021
REFERENCES
Alexander Amini, Ava Soleimany, Wilko Schwarting, Sangeeta Bhatia, and Daniela Rus. Un- covering and mitigating algorithmic bias through learned latent structure. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 289-295, 2019.
Nils Berglund. Kramers' law: Validity, derivations and generalisations. Markov Processes Relat. Fields, 19(3):459-499)) 2011.
Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 4349-434 4357, 2016.
Anton Bovier, Michael Eckhoff, Véronique Gayrard, and Markus Klein. Metastability in reversible diffusion processes i. sharp asymptotics for capcities and exit times. Journal of the European Mathematical Society, 6(4):399 2004.
Anton Bovier, Véronique Gayrard, and Markus Klein. Metastability in reversible diffusion processes ii: Precise asymptotics for small eigenvalues. Journal of the European Mathematical Society, 7 (1):69-99) 2005.
Aylin Caliskan, Joanna Bryson, and Arvind Narayanan. Semantics derived automatically from language corpora contain human-like biases. Science, (056666634):833--111 2017.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. Advances in Neural Infor-
mation Processing Systems, pp. 3992-4001, 2017.
Haw-Shiuan Chang, Erik Learned-Mill and Andrew McCallum. Active bias: rate neural networks by emphasizing high variance samples. Advances in Neural Information Processing Systems, pp. 1002-1012, 2017.
Training more accu-
Mikel Galar, Alberto Fernandez, Edurne Barrenechea, Humberto Bustince, and Francisco Herrera. A review on ensembles for the class imbalance problem: bagging-, boosting-, and hybrid-based approaches. IEEE Transactions Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(4):463 484, 2011.
Haixiang Guo, Yijing Li, Jennifer Shang, Mingyun Gu, Yuanyue Huang, and Bing Gong. Learning from class-imbalanced data: Review of methods and applications. Expert Systems with Applica- tions, 73:220-234 2220022,,22220 2017.
Haibo He and Edwardo A Garcia. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9):1263-1288 2009.
Haibo He and Yunqian Ma. Imbalanced learning: foundations, algorithms,, and applications. John Wiley & Sons, 2013.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrim- ination. Knowledge and Information Systems, 33(1):1-33 2012.
Matthew Kay, Cynthia Matuszek, and Scan A Munson. Unequal representation and gender stereo- types in image search results for occupations. Proceedings of the 33rd Annual ACM Conference Human Factors in Computing Systems, pp. 3819-3828, 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Bartosz Krawezyk. Learning from imbalanced data: open challenges and future directions. Progress in Artificial Intelligence, 5(4):221-232 2016.
M Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In Advances in neural information processing systems, pp. 1 1189-1197, 2010.
Qianxiao Li, Cheng Tai, and Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pp. 2101-2110, 10, 2017.
10

---

Published as a conference paper at ICLR 2021
Qianxiao Li, Cheng Tai, and Weinan. Stochastic modified equations and dynamics of stochastic gradient algorithms Mathematical foundations. J. Mach. Learn. Res., 20:40-1, 2019.
Victoria López, Alberto Fernández, Salvador García, Vasile Palade, and Francisco Herrera. An insight into classification with imbalanced data: Empirical results and current trends on using data intrinsic characteristics. Information sciences, 100:113-141, 2013.
Tomasz Maciejewski and Jerzy Stefanowski. Local neighbourhood extension of smote for min- ing imbalanced data. In 2011 IEEE symposium on computational intelligence and data mining (CIDM), pp. 104-111. IEEE, 2011.
Tomasz Malisiewicz, Abhinav Gupta, and Alexei A Efros. Ensemble of exemplar-svms for object detection and beyond. In 2011 International conference on computer vision, pp. 89-96. IEEE, 2011.
Inderjeet Mani and I Zhang. knn approach unbalanced data distributions: study involv- ing information extraction. In Proceedings of workshop on learning from imbalanced datasets, volume 126, 2003.
Sachit Menon, Alexandru Damian, Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Self- supervised photo upsampling via latent space exploration of generative models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2447-2445, 2020.
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
Thomas
Larisa Yaroslavtseva, et al. On the performance of the galer-maruyama scheme for sdes with discontinuous drift coefficient. In Annales de l'Inttittt Henri Poincaré, Probabilités et Statistiques, volume 56, pp. 1 1162-1178. Institut Henri Poincaré, 2020.
Grant Rotskoff and Bric Vanden-Eijnden. Parameters interacting particles: long time convergence and asymptotic error scaling of neural networks. In Advances in neural information processing systems, pp. 7146-7155, 2018.
Matthew Schlegel, Wesley Chung, Daniel Graves, Jian Qian, and Martha White. Importance re- sampling for off-policy prediction. In Advances in Neural Information Processing Systems, pp- 1799-1809, 2019.
Chris Seiffert, Taghi M Khoshgoftaar, Jason Van Hulse, and Amri Napolitano. Resampling or reweighting: A comparison of boosting implementations. In 2008 20th IEEE International Con- ference Tools with Artificial Intelligence, volume pp. 445 451. IEEE, 2008
Bin Shi, Simon Du, Weijie Su, and Michael Jordan. Acceleration via symplectic discretization of high-resolution differential equations. In Advances in Neural Information Processing Systems, pp. 5744-5752, 2019.
Latanya Sweeney. Discrimination in online ad delivery. Queue, 11(3):10-22 201..
Lei Wu, Chao Ma, and Weinan E. How sgd selects the global minima in over parameterize learning: A dynamical stability perspective. In Advances in Neural Information Processing Systems, pp. 8279-8288, 2018.
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey Gordon. Conditional learning fair representations. In International Conference Learning Representations, 2019.
A PROOFS IN SECTION 3
A. PROOF OF LEMMA
Proof. In resampling, near = -1 the gradient is 0 + with probability a, and 0 with probability 02. Let denote the random gradient each step by W(O + 1), where W is Bernoulli random
11

---

Published as a conference paper at ICLR 2021
variable with mean B(W) a1 and variance V(W) a1dg. At the learning rate 7, the iteration can be written as
(0k+1 + 1) = (0x 1).
The first and second moments of the iterates are
R = (1 - (ea1) ( + 1); [(00 + 1) = ((1 - nja) + + + 1)2.
(8)
According to the definition the stochastic stability, SGD is stable around = -1 the multi- plicative factor of the second equation is bounded by i..
- n01)² v/ 02 1.
Consider now the stability around 1, the iteration can be written as
(0x+1 1) = (1 --) - 1),
where W is again Bernoulli random variable with E(W) 02 and V(W) 0142. The same computation shows that the second moment follows
(+ - 1) = ((1 na2)² + n a102) ((6 1)²
Therefore, the condition for the SGD to be stable around 0 = 1
na2)² +1/201y 02a S
(10) n
A.2 PROOF OF LEMMA 2
Proof. In reweighting, near 0 = -1 the gradient is f1 (0 + 1) with probability fi and O with prob- ability f2. Let us denote the random gradient each step by W(0 1), where W is Bernoulli random variable with E(W) = a1 and V(W) = fife (1L
At the learning rate 7), the iteration
can be written
(0++1 + 1) + (1 - (0 + 1).
Hence the second moments of the iterates are given by
E( + 1)² ((1 -a,, + n² fi 22 + 1)2.
Therefore, the condition for the SGD to be stable around 0 is
- (1-7a,)2 + + fife
a1 f1
1
Consider now the stability around 0 = 1, the gradient is with probability fi and 22 (0 1) with probability f2. An analysis similar to the case 0 = -1 shows that the condition for the SGD to be stable around
02 2
(1-naz) 1/ fifz
S1. 1.
B PROOFS IN SECTION 4
B. PROOF OF LEMMA 3
Proof. In resampling, with probability 61 the gradients over the four intervals (-00,-1) (-1,0), (0, 1), and (1, oo) -1, 1, and With probability az, they -c, -c, -1, and across these four intervals. The variances of the gradients are a az e)2, aıa2(1 + a) e)² a1a2(1 e)2, respectively, across the same intervals.
12

---

Published as a conference paper at ICLR 2021
Since e < 1, the variance can be written (1(z+O(c) across all intervals. Then the SGD dynamics with learning rate 7 can be approximated by
Dk+1 - 02 - (v'(0)) + Vala² +(e)))
where W 1). is normal random variable. When 1) is small, approximate the dynamics by stochastic differential equation of form
de -V)(d) VT + O(c)dB
by identifying 0% (t km) (see Appendix C for details). The stationary distribution of this stochastic process
Z exp (aaaa + O(e))n v(0))
2
Pa (0)
where a normalization constant. Plugging in 0 1,, results in
(1) Ps( (-1) exp
2 (ala2 + O(e))n (V(1) (V(1)-V(-1) (V(1))((11))) = exp (-
2
a102n (-ajazn
- VV-))
(V(1) (V(1)- O(t).
= exp
a1027
Under the assumption that c < 1. the last term is negligible. When 02 > 01 V(0) is minimized at 0 which implies (VV(1) (1) 0. Hence, this ratio is larger than 1,
B.2 PROOF OF LEMMA
Proof. reweighting, with probability f1 the gradients are
21, 01 T. -T. J. J. e, and J. over the four in-
tervals (-20, -1), (-1,0), (0, 1), and (1, 0o), respectively. With probability fz. they are -22, e,
eac, _2 and 42
t fe The variances of the gradients are S1/2( F x/ =e) f152 a
=2c)2
h fr
f1 7. + 2² and f1/2( )2 respectively, across the same intervals.
Since 1, the variance be written f1/22 }3
o² + O(c) for 0 0 and f1 + O(() for 0 0.
With 02 x (kr)), the approximate SDE for 0 < 0 is given by
de - V'(e)d vin J1l2 at
+ +O())BB
while the one for 0 0
af do ('()d Vin f1 +Oed)
T3
(see Appendix C for the SDE derivations). The stationary distributions for 0 0 and 0 0 are, respectively,
2 (fif2 of + +0()))
V(0)
([ (-(r.b
V(0)
Zi exp
exp
Zz
a + +O(e))
Plugging in 0 = 11,1 results in
(w
Zi
2
2
exp
V(1)
V(-1)
Pw
(1))
Zz
[11 + +(d))
(1 of + +((c)
(1I)
Z₁
2f2/f1 ((1) + 2f1/22 1 +0()))
exp
Zn
azn
din
13

---

Published as a conference paper at ICLR 2021
The next step is to figure out the relationship between Z1 and Zz. Consider SDE with non-smooth diffusion dO = (²) dt + odB. The Kolmogorov equation for the stationary distribution is
0 P/: (''(0p' +
0² 2
(12)
This suggests that ppp is continuous at the discontinuity = 0. our setting, since V(0) = 0, this simplifies to
11 +0(s)
of
fi +0(e)) "
1
R
" 71
7
This simplifies
Z1 f1 + +(())
of 0(c).
Z2
fifzf, +0(e)
03/12
Inserting this into
results in
Pw (1)
ag//2
+ O(()
2 V(1) 2 V
((1)+(++++
Pwl (-1)
0./
exp
02211
of/s?
f1 v(1) + 2 2/ v(1) + Occ).
0
exp
asr
By the assumption
4/ < 41
V(-l) and V(1) < (--1) < 0, one has V(I)
2
f2
<
V(-1)
a2
h1
V(1)
and
fe/f
05 V(1)
< f1/f V 1). Hence the above ratio is less than 1.
B.3 EXTENDED RESULTS FOR I-DIMENSION
Let us consider the population loss function V(0) a, (0) + a2V22(2) with,
hi (0), 050 0>0'
-e0,
o 0
(0)
V2(0)
e0,
(2)) 0 0
where h1, l22 are strictly convex functions and continuously differentiable. We assume V()) has two local minimizers 0₃ < 0, 02 > and the values negative at local minima. Therefore, when a2 > 41, O2 should be the global minimizer, In addition, we assume that the geometries of h1 h2 two local minimizers are similar, i.c., (01) h2 (02). hí (01) h2 (02); if we set (0) to be the anti-derivative of (0), then 91 (81) G2 (02). Moreover, we assume that the two disjoint convex functions are smooth at the disjoint point, i.e., h' (0) (2) and 91 g2 g2( The following two lemmas extend Lemmas 3 and t to piecewise strictly convex function based on the above assumptions.
Lemma 9, When a2 > a1, V( V(1).. The stationary distribution for resampling satisfies the relationship
(02) (02)
2 (1 a1 a2
1) 100 Je, (0) 11)0000 d0 + +0(c) > 1.
exp
17
Proof. In resampling, with probability aj the gradients in the two intervals (-oo, 0), (0, oo) are M4 (0), e respectively; with probability 02 the gradients are -e, (/)(0) respectively. Therefore, the expectation of the gradients (u()) is az ar (0) + O(c) in (-o0, 0) and (0) Oc)) in oo). The variance of the gradients (0) is a Mia2h (0) + O(e) in (-o0,) and a1azh/ O(c) in (0, oo).
The p.d.f (t, 0) satisfies
o,p, = Og (pp= 3 (op())
therefore, the stationary distribution (0) satisfies
(1+ + 7/2
7 )000) p. + n00 Oop.- = 0, or equivalently,
24 no
+ Ogo
P.
+ Sep=
= O.
2
14

---

Published as a conference paper at ICLR 2021
which implies (0) = = with normalization constant Z =f=x e where
F(0) /
2
(5) { [F((0) F((-00) 0 0,
de
(13)
(5((5)
(5)
F2(00) - F2(0) + (0) Fi (-00), 8>0.
By inserting H4, a in different intervals, one has
Fi = 2
d0
1/2
h
2
F2(0) 701
d0
log(a O(c).
l12
Hence, the ratio of the stationary probabiliy at two local minimizers 0 < 0, 02 > 0
Po(Oi)
exp( -F(0)) + F(O2)) = exp(-Fi(()) + F2(0,) + (F) F2(0)))
(02)
[1((02)²
exp
(01) +
(2( ) + log
(1(0))
1J02
2
(O)
exp
91 (0) (0) + log
+ +0(c,,
1/22
1ja1
where (0) f +े d0, 1,2. By the assumption that 91 (01) 92 (02) and (((0)) 12(02),
(0) (0) and h (0) (0) one has,
(01)
exp 2 (9) (1x)) Ps (02)
[
) O(c).
02
Since 02 > 01 0, 1 1 < 0. Because of the strictly convexity of h1, 14(0) > 0 in (01, 0).
02
therefore, one has (0)
91
(02) = -So प.
d0 > 0. Therefore
Ps (01)
exp (((1(0)) 91 (Bx)) (1
02 a1 )) + +((c) <1,
pa (02)
Lemma 10. When a2 > a1 V(02) < V(O.). Under the condition
#12
the stationary
distribution for resampling satisfies the relationship
Pw (02)
(2 ( f2
f1
1000 d0 + +((e) < ()(
Pw (01)
exp
()
(102
S102
fear)
One sufficient condition such that the sense that f1 f2 when the actually population proportion a₁ 02.
f T2
is when fi, fo is significantly different from 0 ag in
Proof. In reweighting, with probability f1 the gradients over the two intervals (-o0, 0), (0, oo)
are (0), ft respectively; with probability f2 the gradients are e, 7- h2((0) respectively. 42
Therefore, the expectation of the gradients μ²() is a (0)+0(e) in (-oc, 0) and a2th (O()) oo). The variance of the gradients (()) is fa a (0) (0)2+(ee) in (-oo, 0) and f. (1)
in (0, oc). From the similar analysis as in Lemma the stationary distribution is pw (f) = 1 F())
with the same F()) defined in equation 13 but Fi, F2 are defined follows
2f1
/
1
fza? (M1)²
Fi(0)
dl + log
+ +O(e):
qfza1
h1
fi
2fz
1
f1a2
F2(0) = 7fi0g
d0 + log
(12)2)
+ +(().
h/
f2
15

---

Published as a conference paper at ICLR 2021
Hence, the ratio of the stationary probabiliy at two local minimizers 01 < <0,0g > is
Pw. (wn
Pw (02) = exp( (xp((=F(())) + F2(02) + (Fi(0) - F2(0)))
nf2a1 91 (01) + 2/2
2/1
fz M4 (0,)) )) [Bat h1 (0)2
[Pa8115022 12(02)2
= exp
92 92(02) + log
nfia2 02
2
2f2 (0) + log
exp
112211 91 (0)
7/102
[9 112 (22
+ O(e),
where (:) = S j. d0, i = 1.2. By the assumption that 91 g1(01) = (2((2) and hy (01) = h22(22,
(0) = (2) and h/ (0) = (0) one has, Pu (01)
2 (9)(0) (11)) ( 17
fi
flaz )(az) )) + +0())
f2
exp
(02)
f2a1
Because of the strictly convexity of h1, one has 91 (0) (0,) > 0. By the assumption 4.
then Toon
fz
0, which gives (=(01) > (P2)
fia2
Proof of Lemmas 5 and We can further extend the results in ID for a finite number of local minima as presented in Lemmas 5 and 6 In the same way as in the two local minima case, we assume that h, (0) has similar geometry at the minimizers and h,) 16) are smooth enough at the disjoint point 8g. In order to obtain the ratio of the stationary distribution at two arbitrary local minimizes, we take additional assumption that (6;0-1)) (+,)) for all i, where 9i (:) is the anti- derivative of 1 10),(0). Intuitively, this assumption requires that each local minimum has an equal barrier both sides. To be more specific, the assumptions we mentioned above are the following: at all the local minimizers, h,())) = hy(} < O, (,;) = h1 (6)), let (:) = S kí d0, then ge go())) 9, (07) for any i f j: at all the disjoint points, kç(O,) = (0.). g (0,) for all i. Lemmas and 6 are under the above assumptions.
(0.)
Proof of Lemma 5 For resampling, with probability a, the gradient is Kç(0) for 0 E (0:-1, 0,), and (()) for & (0,-1, 0,). Therefore, the expectation and variance in (0,-1,0.) are μt = (0)+)))+((() and a1 (0) + O(e). The stationary solution is
(0) 7 -(0) with F(0) = F. F.(0.-) + E
for 0 E (0.-1, 0.),
J=1
where Z = 1_ e F(0) is a normalization constant and
F1 = 2 /
dl + log (a,(1 - -.)))(())))))))))))))))) + O(e).
7) (,(0)
Therefore, the ratio of the stationary probability at any two local minimizers 07. 0g is
Pa (0()))
(F((7)) 12(0,-1) -1,000))),,0000101110 Σ -,(0,))
(0()
exp
==1
+
F7 - F2(00-1) + Σ F2(0,) - F5(05-1)
P0(0)) + E,(00) + Σ
Pj(0,) - 10a)
exp
J=P
2
2
aa ag My
exp
(1 ap)
(0%)) +
1
0g)
Iq 0g(0,) + +log
ag(l a (6b
(1+1(1 (0,)² ))
9-1
2
2
a-(1-a))Me an)
exp
(0))
17(1 ) 9)+1(07) + log
+ +0(e).
17(1 a;)
16

---

Published as a conference paper at ICLR 2021
By the assumption that gp(0;) 9r (z))) ,9()7) and (:(0--1) (O+)().),(((0))) 11/4((,))) for all i, then the above ratio can be simplified to
ga(Ot)
P. (67)
2 (0,) gT((g)) (1- -1-
+ + -
1,
if up > Oqi
exp
P. (0()
1,
if ap < ag.
where the last inequality can be easily derived from that -pp00))-p(1p) = Joz ( of the strictly convexity of hpp
d8 > because
Proof of Lemma 6 For reweighting, with probability fi the gradient is j: )(0 for A E (8,-1, 0z), and (cc) for 0 E (0--1, 0t). Therefore, the expectation and variance in (0i-1, are (0)
(()) and o = (1-1)aa k(0)² - O()) The stationary solution
h
Pw (0) 1 F(0), with F(0) = (())= + Σ
for 0 1,)-
j=1
where Z -0000 e -F() is normalization constant and
2f P((0) na,(1 - -i)
(1 f.)a (1- m((0)) + O(+)
d0 log
K((O)
Therefore, the ratio of the stationary probability at any two local minimizers 07. 07 is
Pw (0))
9-1
exp
(p)( Fg(0g)
Fy(0,) Fs+2(03)
Pw
J=p
25p
25n
fr(1 - fa) M,
exp
n0p (1 fp) (p(0%) +
na fg) Og (0() loog
fg fr) fp)
J3 - 11) J5+1(1 - 1 ( 1/) (0,}² )) +
2
2
exp
97 (0₂)
9i+1 (07) + log
11(1 a.))
1)(1 0j+1)
j=p
By the assumption that (p)) = g, (0)) ). M1 (8)) = (2()7) and ge(B:-1) = (.,)) =
(O,,, 1441((5)) for all i, then the above ratio can be simplified to Pw (0)) = exp
2 (gp(Op) (p(6))) ( (1p11-p fp) a,(1- fa) -
Sp
fq
(1)) O(c).
Pw (0;) n
Follow-up discussions of Lemma and
We first note that 1og ोदा d0 > due to the strictly convexity of hp. Therefore, one can see from Lemma that for resampling, the stationary solution always has the highest probability at the global minimizer. On the other hand, for the stationary solution of reweighting in Lemma 6 let us consider the case when ap > Qy. In this case, V(6;)) < V(7)), therefore, one expects the above ratio larger than 1, which implies that fr
a, (1) a,(1-14) 0. Note that if fp ap. fg = =ag. then this term is always larger than O, but when fp: Sa are significantly different from Op, ag in the sense that
Sq
fp < Sg and fp < ap: Jq > ags then (1,, higher probability of converging to 0z. which is not desirable. To sum up, Lemma 6 shows that for
fr
-لاس < 0, which will lead p_(0.)
f.
< 1, i.e.,
p_(0.]
reweighting, the stationary solution won't 't have the highest probability at the global minimizer if the empirical proportion is significantly different fron the population proportion.
B.4 PROOF OF LEMMA g
Proof. By the variance of the gradients for resampling and reweighting in (5. and given that at the stationary point ( E[VV((;)) 0, one omit the last term in the variance. In addition, since (0;), (V) = O(c) & VV, (ft), VV2(0)) by assumption, all the higher
order terms are included in ((ve) term. One then derive Lemma & from Lemma 7 1
17

---

Published as a conference paper at ICLR 2021
C A JUSTIHICATION OF THE SDE APPROXIMATION
The stochastic differential equation approximation of SGD involving data-dependent covariance coefficient Gaussian noise was first introduced in (Li et al. 2017) and justified in the weak sense. Consider the SDE
d0 b())dt + (
(14)
The Euler-Maruyama discretization with time step y results in
k+1 = O2 + r)b(O)) ()x) Z ~ ~0(0 1), O₂ = On-
(15)
In our case, b(.) = -V -V'(.) When satisfies Lipschitz continuity and some technical smoothness conditions, according to (Li al. 2017) for any function 9 from smooth class M, there exists
C>> 0 and a > 0 such that for all h = 0, 2, NN
[(n)) - [[g(Ow)] S Cn)"
However, as the loss function considered in this paper has jump discontinuous in the first derivative, the classical approximation eгror results for SDE do not apply. In fact, the problem V & C' (RR) common issue in machine learning and deep neural networks. many loss functions involves non-smooth activation functions such as ReLU and leaky ReLU. In our case, we need to justify the SDE approximation adopted in Section It turns out that strong approximation error can be obtained if
the noise coefficient a is Lipschitz continuous and non-degenerate, and
the drift coefficient b is piece-wise Lipschitz continuous, in the sense that b has finitely Em & < .... <...<<... Em < Em+1 = oo and in each interval
many discontinuity points -00 = to <
(.). b is Lipschitz continuous.
Under these conditions, the following approximation result holds: for all k = 0, 0,1,2,-.. ,N, there exists C > such that
O - 0x1] I SCV-.
(16)
Here Kky is the solution to SDE at time kn. The proof strategy closely follows from (Müller
Gronbach et al. 2020).. The key is to construct a bijective mapping G R + R that transforms (4)
to SDE with Lipschitz continuous coefficients. With such bijection G, one can define a stochastic
process Z [0, T x Ω2 + R by Z, = G((,) and the transformed SDE is
dZ, = b(Z,)dt + adB,, t EE (0 [0, Zo G(
(17)
1 6 with = (G' b+ 2
. G-1 and ā = oG)
(18)
As the SGD updates can essentially be viewed as data from the Fuler- Maruy-ma scheme, consider- ing Z as updates from Mluler-Maryyamn scheme leads to
Bl[Okn Am 0l
E Am
G 0 c, E Zum
Zz G 0x
< C + ea E| - G o G
To control the second item, we introduce
8, = 0% + b(0x) (t - kn)) + Vt knnjor (0x) Zk.
where t E [0, kn). Then as shown in Müller- Gronbachh et al. 2020).
ElIZ - G 0all c/T cE [ Am
1 (f., 0x)
with B being the set of pairs (11 322 ) R² where the joint Lipschitz estimate (b()1) ( does not apply due to at least one discontinuity. In (Miller-Gronbel et al. 2020). is estimated by
km
E
1 (0,, 0c)dt
S sevn.
which leads us (6)
18

---

Published as a conference paper at ICLR 2021
D NUMERICAL COMPARISONS WITH DIFFERENT LEARNING RATES
In this section, we present extensive numerical results to show the effect learning rates in our toy examples. The Figure 5 corresponds the example in Section and Figure 66 corresponds the example in Section
(a) 17 = 0.3
(b) 17 0.4
(c) 17 0.5
(d) 1 0.6
Figure comparison reweighting (upper row) and resampling (lower row) with 01 /02 0.4/0.6 and f//22 0.9/0.1 various learning rates y, All experiments start at 0g 1.6. We can see that unless the learning rate 1) < 0.4, resampling more stable near the minimizer 0
fordion
Fanditon
Randiton
Rendioo
ferallon
Renalion
Renalion
Renalion
(a) 10007=0.m 0.10
(b) 10 0.11
(c) 0.122
(d) 10 =0133
Figure comparison reweighting (upper row) and resampling (lower row) with 01 02 0.4/0.6, fi/fz f2 = 0.9/0.1 0.1 and 0.1 at various learning rates 1). All experiments start at 0 = 0.9. We can see that unless the learning rate 7) < 0. 12, resampling is more reliable in the sense that its trajectory stays around the desired minimizer.
19


Reviews:
[{"review_id": "gbZHyRIWVDa", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 paper provides a theoretical investigation into, and comparison between, two forms of correcting biased data: reweighting, and resampling. In particular, since previous empirical analyses have suggested that reweighting performs better in practice, the author(s) provide several theoretical explanations for this discrepancy. This is a very interesting problem to consider, and I applaud the authors on their general approach and conclusions, which are novel to the best of my knowledge. The paper is also reasonably well-written too.\n\nUnfortunately, as it is presented here, I find the paper underwhelming for two reasons.\n\n1. Currently, the results (aside from Lemma 6, a quick corollary of a known result) are stated to hold only for very specific toy examples. This is nice enough for illustrative purposes, but I don't see why, with a little more effort, these cannot be extended to a much larger class of objectives. In particular:\n(a) Why does the stability analysis in section 3 not extend readily to combinations of strongly convex functions with disjoint supports? \n(b) What difficulty does it pose to have more general bimodal functions in Lemmas 3 and 4? To me it seems that the main obstacle is the non-constant diffusion coefficient in the SDE approximation. However, in one dimension at least, the Lamperti transform (which is used in Appendix C) can be used to convert this SDE into one with a constant diffusion coefficient, and the rest of the argument should go through. Am I missing something?\n\n2. A more minor point: some of the discussion (and the title) seems to suggest that resampling is always a better choice, which is certainly not true in general. There are settings, particularly outside of deep learning, where reweighting is superior since it typically yields lower variance. More specific language is needed throughout --- this is a phenomenon that pertains primarily to stochastic gradient methods where stability/robustness is key and weights can be small. Further on this point, the author(s) briefly mention under eqn. (4) that the key reason for the discrepancy is that the variances are quite different. I think more discussion is probably needed about these differences in variance. \n\nI enjoyed reading the paper, but these two issues (the former in particular) prevent me from recommending acceptance, as it seems it can be greatly improved for theoretical audiences with comparatively little effort. With these improvements, or some good reasoning as to why they are infeasible, I would be happy to boost my score to a 7.\n\nSome other minor comments:\n\n- I am somewhat confused at the value of the numerical experiments presented. I agree that they add to the paper, but my understanding from the introduction is that it was already known that resampling methods work better in these applications than reweighting. Is this not true? If experiments of this form have not been conducted in the literature previously, this is certainly worth mentioning. Otherwise, some of these could be moved to supplementary material in favour of further discussion on the theoretical results.\n- Can more than two subpopulations be considered? It seems to me that the general case involving more than two subpopulations could be reduced to successive two-subpopulation problems. Is it possible to extend some of the consequences of these results, especially Lemma 6, to this setting?\n- Very minor, but I'm not especially fond of the use of f_1, f_2 for the sampling proportions. Other papers discussing Langevin approximations sometimes use f to denote the potential function, which makes things a little confusing here. Can a different letter be used instead? \n- Two sentences before eqn. (4): \"{s}\" should just be \"s\".\n- Figures 1 and 2: Can (a),(b),(c) be used instead of (1),(2),(3), so as not to confuse with equation numbers?\n- First sentence on pg. 4: \"We refer...\" -> \"We defer...\". Also \"...shows that reweighting makes problems stiffer in terms of the stability criterion\": maybe \"reweighting can incur a more stringent stability criterion\"?\n- Can the size of the axis labels (not tick labels) in Figures 1 and 2 be increased?\n- Last line of pg. 5: \"not-Lipschitz\" -> \"non-Lipschitz\"\n- Last line on pg. 8: \"extend our analysis to unsupervised learning problems\": since the previous discussion has implied these results hold very generally (point 2), it might be good to provide a little more detail on what is meant by this.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fkSb0XL3IY", "reviewer": "AnonReviewer1", "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": "Summary:\n\nThis paper delves into a stability analysis of reweighting and resampling for overcoming imbalanced data in supervised learning. Reweighting employs the use of importance ratios to modify a samples weight to the training in turn changing the effective distribution. There are several resampling procedures which all have a similar effect in the analysis, and the authors consider several algorithms for resampling in their experiments.  The reweighting approach, while convenient, leads to poorer stability under simplifying assumptions. While this is interesting in its own right, they show that under certain distributions of the data reweighting will actually not converge to the optimal minima, while resampling will. This is motivated by a large collection of work developing resampling methods for imbalanced data, which all come to similar conclusions (i.e. that following a resampling procedure outperforms a reweighting procedure in many, but not all, settings). They follow up with a SDE analysis in another toy problem, which they then extend to more realistic assumptions.\n\n\nThoughts:\n\nThis paper is a good start at trying to understand the behavior of resampling and reweighting in the wild. It is also well written, and contains some interesting discussion on their analysis. The proofs also seem straightforward for the most part and well explained. Unfortunately, I have a few concerns (see below) which have lowered my score. I'm recommending reject at this time, but would be happy to increase my score as we go through the rebuttal phase.\n\n\nConcerns/suggestions/questions:\n\n1. My first concern has to do with how general we can expect the analysis of these problems to be. I understand that the analysis for larger problems is often harder if not impossible given our current theory, but if we simplify too much the results aren't indicative of the larger picture. Some assumptions which I have some issues with\n   - Our problem can be decomposed into several discrete loss functions (i.e. $V_1(\\theta)$ and $V_2(\\theta)$). I can see how this works for classification where each loss function is for each label, but when moving to regression and RL prediction, this becomes less clear. For the case of learning a value function off-policy, it feels more like the importance weights are shifting the space, rather than reweighting a discrete set of loss functions.\n   - For the general results you still only consider the case where there are two minimizers. (Q1-1) Are you only considering the case where the weights only shift within some local ball and only encounters these minima? (Q1-2) Can this be guaranteed in the larger problem you motivate (i.e. using NNs)? Maybe this is close to Lazy training, or results when the NN is overparameterized and the weights don't shift much. (Q1-3) Could these results be extended to a finite number of minimizers within a ball? This seems more reasonable.\n\nThese are the main assumptions I'm concerned with. They both are hinting at the larger question of (Q1-4) \"how reasonable are these assumptions to the larger motivating problem?\" I think it would make the paper much better if there was some examples that were less toy-like.\n\n\n2. The results in the toy examples for the stability and SDE analysis are really nice. But I'm a bit concerned with the conclusions drawn. Both analysis results in bounds on a notion of \"stability\" which includes the learning rate as a factor. When testing the result empirically, only a single learning rate is used for both the resampling and reweighting. This gives a facade of a results that reweighting is always unstable, which is not true. When selecting a stepsize in the correct range reweighting should indeed be stable. I think what the authors are wanting to say is that selecting learning rates will be much easier for resampling as they do not rely on the sampling proportions. I agree with the sentiment, but I think this needs to be made more clear. One way is to give effective ranges for the learning rate in which we expect the two approaches to be stable, and observe that in practice we can't always know $(f_1, f_2)$ so selecting in the prober range is an empirical exercise.  You can also show this through uniformly selecting learning rates in the range $(0,1)$ and showing how many result in a stable system around the global minimizer. With these experiments, I would also suggest starting both procedures at the same initial weights and indicate through a color gradient or arrows the temporal direction of the training (right now it is quite ambiguous).\n\n3. Experiments:\n\n   I'm q bit concerned with the lack of details provided for the experimental design. I understand that in theory papers empirical results are not the focus, but the goal should still be to provide enough details to reproduce independent of any accompanying code base. Even with these missing details I'm a bit concerned with the results as well, and how many conclusions we can draw from what is presented.\n\n   Q3-1. How many runs were performed? (all)\n   Q3-2. What is the statistical significance of the provided results? (regression and off-policy prediction)\n   Q3-3. What were the hyperparameters chosen, how were the parameters chosen? (all)\n   Q3-4. What loss functions were used for the classification and regression experiments?\n   Q3-5. Why not choose another type of regression problem, rather than another classification problem?\n   Q3-6. What optimizer was used for training?\n\n   On top of these missing details, some more general concerns:\n   C3-1. I'm assuming we are only using a constant learning rate for all the experiments. Is this reasonable. Could we expect the results to change if the learning rate is able to take the variance of updates into account (i.e. using RMSProp). These experiments could be worthwhile pursuing, because the analysis only covers static learning rates. This would also help elucidate more about the interaction between resampling and reweighting in systems that are closer to what is being used in practice.\n   C3-2. For the off-policy prediction setting. What is the discount parameter for the problem you are considering? How are you calculating the error? Only through online data? Or through sampling from the sampling a set of states from the state distribution of the behavior policy? Does this environment relate back to something in the real world that is of interest to make predictions on? What is the motivation for this problem? What are the x and y axis in the left plot of figure 5? Did you mean to calculate error using $V_\\pi$? The current notation is often used for the optimal value function, which is a different concept.\n\n\nSome minor corrections:\n - Page 7 \"...objective is to find the value function of police \\pi...\"\n - Abstract \"reweighting outperforms resampling when ...\", you draw the opposite conclusions in the paper.\n\n--- Updated score ---\nThe authors did a nice job of addressing many of my concerns. But there are still some lingering issues with the experimental design (especially with the reinforcement learning experiments). The main concern I have is why the variance for your results is so low from run to run. This could suggest the problem is too easy, or that there is a bug somewhere. While I don't think it is enough to outright reject the paper, it still puts me on the fence about a strong accept.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VyTXTtaY3WG", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "Biased datasets are ubiquitous and therefore addressing bias in datasets is a relevant issue for building good ML applications and products. The paper makes a significant contribution by providing a theoretical explanation to the observation that resampling is generally more effective than reweighing as a debiasing tool. This paper does not introduce a novel way to address bias and therefore its originality and impact is limited. It does however provide good proof that the resampling approach is more efficient than reweighing, which will help ML developers to make a more informed choice between the two approaches. The ubiquity of the sampling problem, makes the impact of this work significant despite not being very original. In addition, to the results, the approach used in the paper, namely, the use of numerical methods borrowed from stability analysis of dynamical systems and stochastic differential equations continues an interesting line of research that is helping to understand optimization processes and how to use them efficiently to train unsupervised algorithms. The theoretical results look solid and I cannot see any issue with them to the best of my knowledge. The authors provide and array of numerical results which convincingly demonstrate their theory. The manuscript could be improved by exploring the limitations of their approach, but I do not see this is needed for the paper to be accepted. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GTehZmLCIc1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nSummary:\nWhen training data comes from a sampling distribution that is different from the target test distribution, there are two commonly-used machine learning techniques to correct the distribution difference --- re-sampling and re-weighting. This paper investigates why re-sampling outperforms re-weighting when using stochastic gradient descent for optimization. The paper provides two explanations. \n(1) Resampling with SGD is more stable. By stability, the authors mean that the expected L2 distance between the parameter during optimization and the true parameter is small. \n(2) Reweighting with SGD can converge to a worse local minimum with larger probability. \n\n\nThey also conduct experiments to show that re-sampling outperforms re-weighting. \n\nStrengths:\n\n1. The problem to compare re-sampling and re-weighting during optimization with stochastic gradient descent is very interesting and important. Machine learning from biased data (e.g. selection bias) is very prevalent and stochastic gradient descent is a popular optimizer. \n\n2. The paper is clearly written and easy to follow. \n\n3. The stability analysis and SDE analysis provide two alternatives to explain the difference between re-sampling and re-weighting. \n\nWeakness\n\n1 The theoretical analysis does not provide strong evidence that re-sampling is better than re-weighting. \n\n1.1 It would be great if the authors could explain more why Lemma 1 and Lemma 2 show that resampling is better. To me, it just shows that, if we want to achieve stability, we have to use smaller learning rate for reweighting. It makes no sense to me to compare resampling and reweighting with a fixed learning rate. \n\n1.2 SDE analysis shows that re-weighting sometimes tends to converge to a worse local minimum. But it did not sate re-sampling always tends to converge to a good local minimum. It would be great if authors explain when re-weighting and re-sampling tend to converge to good and bad local minimum. \n\n\n\n\n2. The experiments details are not clear and I did not see how these experiments reflect the theoretical analysis. \n\n\n2.1 It would be great to mention whether the results are performed on the training set. I assume the results presented are for the training set since this paper investigates how the optimization with SGD works instead of focusing on generalization. \n\n2.2 It would be great to report the final training objective. Since the main theoretical result of the paper is that optimization with SGD using re-sampling tends to be more stable around a better local minimum. \n\n2.3 In the classification experiments, the ROC-AUC of reweighting method is only around 0.53, that is just 0.03 better than random guess. A large neural network typically can overfit a classification dataset with just two classes. I am wondering why the ROC-AUC is so low. It would be great if the authors could provide the experiment details, e.g. the learning rate. \n\n2.4 In the nonlinear regression experiment, logistic regression is used. Logistic regression objective is a convex objective. There is no local minimum. So the experiments do not validate the SDE analysis. The authors claimed that they do this experiment to show that ``performance of SGD deteriorates when reweighting is used''. I did not see any previous analysis indicating this. It would be great if the authors could explain more about why they conduct this experiment and how this relates to their theoretical analysis. \n\n\n\n\n\n\nAdditional feedback\n\nIn the abstract ''reweighting outperforms resampling'' -> ''resampling outperforms reweighting''\n\nWhy in equation (3), there is an approximate equal? It seems to me that it is just equal. Same for equation (4). \n\nlearning rate \\eta first appears in Lemma 1 without explanation. Also, Lemma 1 uses C= 1 which is not explained in the main paper. \n\n\nIn SDE analysis: The statement \"all iterates will stay in this region'' confuses me. If the learning rate is large enough, I think it can get out of the the region. Say when \\hat{\\theta}_t is at -2 and we encounter an example from V_1, then the gradient is positive. If the learning rate is large enough, it can get to (0,\\infty). \n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9unU7bksW8X", "reviewer": "AnonReviewer2", "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": "This paper provides an analysis of why resampling can be better than reweighting in some cases. By observing the behaviour of resampling and reweighting in simple optimizations with SGD, the theoretical results show that resampling tends to be more stable. The general analysis is based on SDE approximation. Experiments on classification and off-policy evaluation show that resampling can be better in some cases.\n\nStrength:\n- Simple examples and analysis showing the instability of reweighting and the possible reasons\n\nWeakness:\n- The theory is fairly restricted\n- Some details are missing\n- Experiments are unclear\n\nDetail comments:\n1. The assumptions of Lemma 5 and 6 are strong. In most cases, the optimization landscape is likely to have more than two local minimas. Moreover, Lemma 6 assumes that the relative error is bounded by epsilon, which is difficult to verify in practice.\n\n2. The effect of the learning rate is not sufficiently demonstrated. The learning rate \\eta plays a role in Lemma 1 and 2. Fig.1 only shows a specific eta=0.5 without explanation. It would be interesting to see how resampling and reweighting behave with different learning rates. The same applies to the example in Sec.4.\n\n3. There are not enough details about how Fig.1(2) and Fig.2(3) are produced. Specifically, how is the resampling conducted?\n\n4. The regression experiment is actually binary classification.\n\n5. The TD(0) update on page 8 is wrong. The minus sign should be plus. Additionally, using \\delta_\\pi and \\delta_\\mu can be misleading as the TD error only depends on the functional form of V instead of the policies. The setting and the results are very unclear. There are n=32 states, but the x-axis of Fig.5(left) ranges from 0 to 6. All the curves are using C=1/10, so it is not clear how they differ. What do W and S stand for in the legends?\n\nMinor\n- In the proofs of Lemma 3, Z is used as a standard Gaussian RV and partition function.\n- The \\theta^* in Lemma 5 should be \\theta^\\circ.\n\n==== Update ====\nIncreased score according to the revision and discussion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
The paper theoretically investigates two bias-correction methods, reweighting and resampling. It considers a very interesting problem and presents illuminating results. The paper could benefit substantially from improving the experiments so that they clearly validate the theoretical results presented.
Decision: Accept (Poster)