Understanding the role of importance weighting for deep learning
Authors: Da Xu
Yuting Ye
Chuanwei Ruan
Venue: ICLR 2021 Spotlight (2021)
Keywords: Importance Weighting
Deep Learning
Implicit Bias
Gradient Descent
Learning Theory

Abstract: The recent paper by Byrd & Lipton (2019), based on empirical observations, raises a major concern on the impact of importance weighting for the over-parameterized deep learning models. They observe that as long as the model can separate the training data, the impact of importance weighting diminishes as the training proceeds. Nevertheless, there lacks a rigorous characterization of this phenomenon. In this paper, we provide formal characterizations and theoretical justifications on the role of importance weighting with respect to the implicit bias of gradient descent and margin-based learning theory. We reveal both the optimization dynamics and generalization performance under deep learning models. Our work not only explains the various novel phenomenons observed for importance weighting in deep learning, but also extends to the studies where the weights are being optimized as part of the model, which applies to a number of topics under active research.

Published as a conference paper at ICLR 2021
UNDERSTANDING THE ROLE OF IMPORTANCE WEIGHT- ING FOR DEEP LEARNING
Da Xu
Walmart Labs
Sunnyvale, CA 94086, USA DaXu51 808 gma i 1. com
Yuting Ye
Division of Biostatisties University of California, Berkeley Berkeley, CA 94720, USA yeyt&berkelley. edu
Chuanwei Ruan
Instacart
San Francisco, CA 94107. USA Ruanchuanwe gma com
ABSTRACT
The recent paper by Byrd & Lipton (2019), based on empirical observations, raises major concern on the impact of importance weighting for the over-parameterized deep learning models. They observe that as long as the model can separate the training data, the impact of importance weighting diminishes as the training pro- ceeds. Nevertheless, there lacks rigorous characterization of this phenomenon. In this paper, we provide formal characterizations and theoretical justifications on the role of importance weighting with respect to the implicit bias of gradient descent and margin-basee learning theory. We reveal both the optimization dynamics and generalization performance under deep learning models. Our work not only ex- plains the various novel phenomenons observed for importance weighting deep learning, but also extends to the studies where the weights are being optimized part of the model, which applics to a number of topics under active research.
INTRODUCTION
Importance weighting is standard tool for estimating quantity under target distribution while only the samples from some source distribution is accessible. has been drawing extensive attention the communities of statistics and machine learning. Causal inference for deep learning investigates heavily on the propensity score weighting method that applies the off-policy optimization with counterfactual estimator (Gilotte al., 2018 Diang & Li, 2016), modelling with observational feedback (Schnabell ct al. 2016,[Xu et al. 2020) and learning from controlled intervention (Swaminathan & Joachims/ 2015). The importance weighting methods
also applied characterize distribution shifts for deep learning models (Fang et al. 2020), with modern applications in such as the domain adaptation
(Azizzadenesheli al. [019]] Lipton al.) (008)) and learning from noisy labels (Song et al., 2020).
Other usages include curriculum learning (Bengio et al. 2009) and knowledge distillation (Hinton
al. 2015), where the weights characterize the model confidence on each sample.
To reduce the discrepancy between the source and target distribution for model training, a standard routine to minimize a weighted risk (Rubinstein & Kroese (016). Many techniques have been developed to this end, and the common strategy is re-weighting the classes proportionally to the inverse of their frequencies (Huang et al. 2016 2019: Wang et al. 2017). For example, Cui et al.
"The work done when the author was with Walmart Labs.

---

Published as a conference paper at ICLR 2021
(2019) proposes re-weighting by the inverse of effective number of samples. The focal loss (Lin et al. 2017) down-weights the well-classifedd examples, and the work by Li et al. (2019) suggests an improved technique which down- fown-weights examples based on the magnitude of the gradients.
Despite the empirical successes of various re- re-weighting methods, it is ultimately not clear how importance weighting lays influence from the theoretical standpoint. The recent study of Byrd & Lipton (2019) observes from experiments that there is little impact of importance weights on the converged deep neural network, if the data can be separated by the model using gradient descent. They connect this phenomenon to the implicit bias of gradient descent (Soudry et al., 2018 a novel topic that studies why over- aver-parameterizee models trained on separable data is biased toward solutions that generalize well. Implicit bias of gradient descent has been observed and studied for linear model (Soudry et af., 2018 Ji & Telgarsky, 2018b), linear neural network (Ji & Telgarsky, 2018a
Gunasekar
et al. 2018D, two-layer neural network with homogeneous activation (Chizat & Bach 2020) and
smooth neural networks (Nacson et al.) 2019 [yu & Li 2019). To summarize, those work reveals that the direction of the parameters (for linear predictor) and the normalized margin (for nonlinear predictor), regardless of the initialization, respectively converge to those of max-margin solution. The pivotal role of margin for deep learning models has been explored actively after the long journey of understanding the generalization of over- perr-aaramtteizeed neural networks (Bartlett et al., 2017] Golowich et al., 2018: Neyshabur al., 2018). For instance, Wei et al. (2019) studies the margin of the neural networks for separable data under weak regularization. They show that the normalized margin also converges to the max-margin solution, and provide a generalization bound for a neural network that hinges on its margin.
Although there are rich understandings for the implicit bias of gradient descent and the margin- based generalization, very few efforts are dedicated to studying how they adjust to the weighted empirical- risk minimization (ERM) setting. The established results do not directly transfer since importance weighting can change both the optimization geometry and how the generalization is measured. In this paper, we fill in the gap by showing the impact of importance weighting on the implicit bias of gradient descent as well as the generalization performance. By studying the optimization dynamics of linear models, we first reveal the effect of importance weighting on the convergence speed under linearly separable data. When the data is not linearly separable. we characterize the unique role of importance weighting on defining the intercept term upon the implicit bias. We then investigate the non-linear neural network under weak regularization as Wei et al. (2019). We provide novel generalization bound that reflects how importance weighting leads to the interplay between the empirical risk and a compounding term that consists of the model complexity as well as the deviation between the source target distribution. Based on our theoretical results, we discuss several exploratory developments on importance weighting that are worthy of further investigations.
A good set of weights for learning can be inversely proportional to the hard-to-classify extent. For example, sample that is close to (far from) the oracle decision boundary should have a large (small) weight.
If the importance weights are jointly trained according to a weighting model, the impact of the weighting model eventually diminishes after showing strong correlation with the hard-to-classsffy extent such as margin.
The usefulness of explicit regularization on weighted ERM can be studied, via their impac on the margin, on balancing the empirical loss and the distribution divergence.
In summary, our contribution are three folds.
We characterize the impact of importance weighting on the implicit bias of gradient descent.
We find generalization bound that hinges on the importance weights. For finite-step training, the role of importance weighting on the generalization bound is reflected in how the margin is affected, and how it balances the source and target distribution.
We propose several exploratory topics for importance weighting that worth further investi- gating from both the application and theoretical perspective.
The rest of the paper is organized as follows. In Section 2 we introduce the background, preliminary results and the experimental setup. In DectionBJand]3 we demonstrate the influence of the importance weighting for linear and non-lincar models in terms of the implicit bias of gradient descent and the generalization performance. We then discuss the extended investigations in Section 5
2

---

Published as a conference paper at ICLR 2021
2 PRELIMINARIES
We use bold-font letters for vectors and matrices, upperease letters for random variables and dis- tributions, and || to denote &g norm when confusion arises. We denote the training data by D = ( x,, Yi Ti where X; E X' denotes the features, yi is binary or categorical, and the impor- tance weight is bounded such that: wi E [1/M, M] for some M > 1. We mention that the importance weights are often defined with respect to the source distribution P. from which the training data is drawn, and the largel distribution Pt. We do not make this assumption here because importance weighting is often applied for more general purposes. Therefore, wy can be defined arbitrarily.
We use f(0, x) to denote the predictor and define F {f(0.-) 1) E O C Rd.. For the sake of notation, we focus on the binary setting: yi E +1] with f(0, x) E R. However, it will become clear later that our results can be easily extended to the multi-class setting. Consider the weighted empirical risk minimization (ERM) task with the risk given by L(0; w) = 1/n _ w;e [ x:)) for some non-negnenn negative loss function (()) The weight-agnostie counterpart is denoted by: L( = 1/n (0 x) We focus particularly on the exponential loss {(u) exp(-2) and log loss {(u)= = log + (x)) For the multi-class problem where y; E [k]]. we extend our setup using the softmax function where the logits are now given by (0,x)) For optimization, we consider using gradient descent to minimize the total loss: ((++1)(w) (w) = ((+) (w) 7). V ((0 w) (0=))(ww)
where the learning rate 7) can be constant or step-dependent.
From parameter norm divergence to support vectors.
Suppose D is separated by s(0(1, x) after some point during training. The key factor that contributes to the implicit bias for both linear and non-linear predictor under a weak regularization is that the norm of the parameters diverges after separation, i.c. limy->oc [ = 00, as a consequence of using gradient descent. Now we examine (1(())(w ll2. The heuristic is that if E(-) is exponential multiplying by w, only changes its tail property up to constant while the asymptotic behavior is not affected. In particular, the necessary conditions for norm divergence under gradient descent can be summarized by:
C1. The loss function E(.) has a exponential tail behavior (that we formalize in Appendix A.1 such that lim,,-poc (--u) = lim Ve(-u)= = 0;
. C2. The predictor /(0,, x) is a-homogeneous such that f(c 0, ca 5(0, Ve 0.
In addition, we need certain regularities from x)) to ensure the existence of critical points and the convergence of gradient descent:
C3. for any x E X, f(,xx) is 3-smooth and I-Lipschitz on Rd
C1 can be satisfied by the exponential loss, log loss and cross entropy loss under the multi-class setting. For standard deep learning models such as multilayer perceptron (MLP), C2 implies that the activation functions are homogeneous such as ReLU and LeakyReLU, and bias terms are disallowed. C3 is a common technical assumptions whose practical implications are discussed in Appendix I Among the three necessary conditions, importance weighting only affects C1 up to constant, so its impact on the norm divergence diminishes in the asymptotic regime. The formal statement is provided as below.
Claim 1. There exists a constant learning rate for gradient descent, such that for any w e [1/M, M]", with a weak regularization, lim, ((0)) [w] = oo under C1-C3.
Compared with the previous work, we extend the norm divergence result not only to weighted ERM but more general setting where weak regularization is considered. We defer the proof to Appendix A. A direct consequence of parameter norm divergence is that both the risk and the gradient are dominated by the terms with the smallest margin, i.e. arg min, ff, x;), which are also referred to as the "support vectors". To make sense of this point, notice that both the risk and the gradient have the form of: Σ, C. exp (0 x:)), where C, are low-order terms. Since f0, x;) = ||0| | f (0/ 0|), xx) due to the homogeneous assumption in C2, it holds that:
'The regularized loss is given by TA (0: w) T.(0: w) + x||0|| for fixed r > 0. The weak regularization refers to the case where - 0.
3

---

Published as a conference paper at ICLR 2021
(a)
(b)
(c) (d)
2-
2
0-
0
-2
Figure 1: (a). Linearly separable data; (b). Non-separable data; (c): Balanced moon-shaped non- linear separable data; (d). Unbalance moon-shaped data after down-sampling both classes (20% for the blue class, and 80% for the orange class). We use solid line to denote the separating hyperplane of the trained linear model and shades to represent the decision boundary of trained nonlinear model.
lim; exp (
xw). (x)( O. Therefore, the decision boundaries may share certain characteristics with the support vector machine (SVM) since they rely on the same support vectors. As matter of fact, the current understandings the implicit bias of gradient descent mostly established on the connection with hard-margin SVM:
min 6E
1012
s.t. y.f(0, x.) 2 Vi 1,2......
whose optimization path coincides with the max-margin problem: maxie S1 min;=1..... f x,). as shown by Nacson et al. 2019). Define -(0) == min; fi,, x.). We use 0" to denote the optimal solution and 7 (0") min; f x,) denote the corresponding margin.
Implicit bias of gradient descent.
We start by considering the weight-agnostic setting. When D is linear separable, is reasonable to conjecture that the separating hyperplane under a linear 1(0.-) overlaps with the solution of hard-margin SVM. Soudry et al. (2018) and Ji Telgarsky 8b) first show that [|@((]]] converges in direction to 0", i.e. lim ((())
0" For nonlinear predictors, however, the parameter direction less meaningful. Instead, it has been pointed that neural networks often achieve perfect separation of the training data (Zhang et al., (2166). Therefore, we are more interested in the margin neural networks studied extensively (Neyshabur et al.) 2017, Bartlett et al.) 2017] Golowich et al.) 2018). Specifically, it has been show in Nacson et al. (019 and Lyu & Li (2019) that the normalized margin, defined by (((())) = 7 (0 /10()))). Converges the maximum margin 7 without regularization.
whose pivoting role for the generalization
It becomes clear at this point that to understand the role of importance weighting for deep learning, we must characterize the impact of weights on the implicit bias since they reveal the optimization geometry and generalization performance. Formally, we address the following critical questions.
Q1. Does importance weighting modify the convergence results (convergence in direction for linear predictor and in normalized margin for nonlinear predictor)?
If the convergence results remain unchanged, then:
Q2. in what way is importance weighting affecting the optimization process;
-33. how does importance weighting influence the generalization from the source distribution to the target distribution?
Experiment setup.
Throughout this paper, use the regular regression model as linear predictor. The nonlinear predictor a two-layer MLP with five hidden units and ReLU as the activation function. All the models are trained with gradient descent using 0.1 as learning rate. We use the exponential loss and the standard normal initialization. The generated datasets for our illustrative experiments are shown in Figure] which correspond the different settings of our major topics.
4

---

Published as a conference paper at ICLR 2021
3 IMPORTANCE WEIGHTING FOR LINEAR PREDICTOR
We begin with the linear predictors which allows more refined analysis on the gradient dynamics. Without loss of generality, we assume using the exponential loss. Also, we do not consider the weak regularization here since its practical impact on linear model trivial when À + 0 (Rosset et al. 2004a b). but it is not the case for nonlinear predictors. One sophistication with linear predictor is that the data may not be perfectly separated, as opposed to the nonlinear case where neural networks can in theory separate any non-degenerate data. With this kept mind, we first assume D is linear separable and characterize the new convergence result in the following proposition.
Proposition 1. With a constant learning rale Tt S 3 we consider normalizing the weights w E 1 M)" such that >; W; = 1 without loss of generality, it holds that:
(2) (w)
0- -01 log n -KL ((])pp/))>)r + M
1000 w
log 7-
where p" = -ipi..... .. .P,] characterizes the dual optimal for the hard-margin SVM such that 0 Ex=1 y:X, P. and satisfies: pt 2 0 0nd Ei=15 = Here, DRL is the Lulbbeck-Leibler divergence.
We leave the proof to Appendix A.2 We find that importance weighting does not change the convergence result well as the 1/ log convergence rate. However, it does affect the convergence speed under the finite-step optimization. In particular, we show that the extra constant term induced by importance weighting is given by the KL-divergence between the (normalized) weights and the dual optimal of the margin SVM, where samples with smaller margins usually have larger values. Therefore, importance weighting may accelerate gradient descent in finite-step optimization by matching weights with the inverse margin. As we show in Figure 2h and Zb, this type of "inverse- margin weighted" design is able accelerate the convergence and bring better performance under finite-step optimization.
Cosine distance optimal
Margins
loss
Margins
normal
14
weiight 1-4
soight 3164
040
05
0.4
200
epochs
3,5
100
150
250
Tiverse marg weigttd
40g3 weightdd
#baalaced Class weighte 0.2)
opachs
(a)
(b)
(c)
(d)
Figure (a): Epoch-wise training performances measured by the angle between the decision
boundary (at that epoch) and the max-margin solution, using linear predictor on the linear separable
data of Figure Th: (b): Epoch-wise training performances measured by the average margin in the same setting (a); (c). The generalization eтгоr testing data (the remaining 80% of the orange class and 20% of the blue class that are not part of the down-sampling in Figure TTi) when the nonlinear model is trained under different class weights, the training progresses; (d). The average margin for the nonlinear model on the non- -ineally separable training data shown in Figure TD. under different class weights, the training progresses.
When D is not linearly separable, the key insight is that we can always partition D into D Doop U Duuon--sp-- where Deep is the maximal linear separable subset defined in Di & Telgarsky (2018b). Let I sep be the (orthogonal) projection onto the subspace S spanned by the x; 's in Dumn-sep- and let IT be the projection onto the orthogonal complement S-. The partition allows us to study the two projected parts independently since by the construction, we have g(t) (w) = -mnon-scp (((((() is intuitive that the optimization path of O(tp)))) (w) behaves similarly to the linear separable case as in Proposition follow proposition.
(w)) (w) + (()) (w). ). It
| so we can focus on the properties of Hnon-sop (1)) (w)), which we summarize in the
Proposition 2 (Informal). Let Lnon-sep ( w) be the weighted risk defined on the non-separable subset, then with the constant learning rate:
((w) arg ming T cp w) is uniquely defined and [[((w]l2 0(1)
5

---

Published as a conference paper at ICLR 2021
() - x c(1((())12) + log t/ where "Isep the maximum margin on sep and ( O(1)
IT [ sep (10) 1ep
t
The formal statement, which involves how Dee is defined, deferred to Appendix A.2 together with the proof. P informs
informms that importance weighting uniquely defines the solution O on the non-separable subset of the data, to which Honn-sop (w) converges. Hence, we expect lim, ( ww ((w) 0 where Peep is the solution the separable subset seep and thus its direction does not depend on w as implied by Proposition We can therefore think of ((w) as the intercept term where the weight controls how the intercept shifts the subspace of the non-separable data. We also illustrate this finding in Figure 3 By far, we provide an in-depth understanding and our theoretical results fully explain the observations made in [yrd Lipton (2019) on how importance weighting affects the implicit bias of gradient descent using linear predictors.
Epoch
Epoch 25
Epoch 50
Epoch 100
Epoch 200
orange Muge 2.1
Mupe 13
Muee
Figure 3: The role of importance weighting on defining the intercept term in addition to the implicit bias for the linearly separable case, where the hyperplane shifts in the non-separable subspace depending on the class weights.
4 IMPORTANCE WEIGHTING FOR NONLINEAR PREDICTOR
Now we investigate the influence of importance weighting on non-linear predictors, e.g, the neural network. Here
interested in the regularized setting:
min (0: w) == L(O, w) + A|
where O fixed, À the regularization coefficient. We use the notation: (x(w) arg min Lx (0, w). Recall that y" max]øo}s1 min, (0,x,) Unlike the linear case, charac- terizing the gradient dynamics for nonlinear predictor is often insurmountable. Therefore, we mainly consider the asymptotic regime or the regime with sufficiently large We omit the superscript (()) when there is no confusion. The only assumption need to make is that:
A1. the data separated by f at some point during gradient descent, i.e. y/ H= x;) 0, = .,....,.. n. In addition, ys (0" x;) 2 7" > 0 for each
3t > 0 s.t.
In Section 4.1
show that by solving the equation with infinitesimal (weak) regularizer, gradient descent leads to the optimal margin 7", regardless the choice of the importance weights. In Section 4.2] show that the the importance weighting affects the generalization bound via multiplication factor as well as the margin in the finite-sample scenario.
4.1 MARGIN IS INVARIANT TO IMPORTANCE WEIGHTING UNDER WEAK REGULARIZATION
We show that for any bounded w. ((0x
(0x (w) (w) ( (w) converges to 7 decreases to zero. In practice, however, we might not obtain 0x (w) in limited time. It is shown that as long as equation is close enough finite-step optimization) is lower bounded by y" multiplied by a non-trivial factor. Formally,
optimum, the normalized margin of the associated 0' (w) (under
Proposition 3. Suppose CI-C3, Al hold. For any w e [1/M, M)", it follows that
(Asymptotic) limx-1 ((0x(w)) + 7²

---

Published as a conference paper at ICLR 2021
(Finite steps) There exists À a(r,a,"', w. such that for ('(w) with (w): I (0x(0x())) w) and T 2, the associated normalized margin (0'(w) satisfies ((0((w) 2 c pa/es where se<l.
This result is adapted from Wei al. (219)) which relies on Claim The proof is relegated to Appendix [ We see that importance weighting does not affect the asymptotic margin when is is large enough and À is small enough to be ignored, (0x (w), w) R exp ( (w))))))))) which favors large margin. In addition, even if Lx (0' (w). w) has not yet converged but close enough to its optimum, the corresponding normalized margin has reasonable lower bound. We point out that this result does not rely on the choice of A. The assumption (x(0((w) w) S TLa (w): w) has already accounted for the major influence of importance weighting in terms of the optimization. That is, with a "good" set of importance weights, we can achieve this criteria (by approaching global optimum) faster. We leave detailed discussions to Section 5 Figure 2 also demonstrates that the choice of the importance weights has a significant influence on the convergence speed for the non-linear predictor.
sufficiently small. To get the intuition, note that when [0x(w)]] I||
4.2 IMPORTANCE WEIGHTING AFFECTS THE GENERALIZATION BOUND
the behavior of the margin corresponding to the optimum of LA (0; w), which does not rely on the sample size. To bridge the connection between importance weighting and the behavior of f(O,.) -) in the finite-sample setting, investigate the generalization bound of f when the training sample distribution deviates from the testing sample distribution.
Proposition 3 conjectures
Let P. be the source distribution and P. be the target distribution with the corresponding densities (.(.) and (.).. Assume that P, and Pe have the same support. We consider the Pearson x -iiveegeence to measure the difference between P. and Pt, i.e., ( training covariates XI,..., X, are generated from P.. and the testing covariates are generated from Pe. Denote by Puain and Prett the joint distribution of (x, y) for the training data and the testing data, respectively.
= [dPP:/dP.) - 1]dP.. The
We minimize equation over the H-layer feedforward neural network given by (NN x) ==
WHo ""Ho(WH-orr (Wix)... .), where = [W WHl are the parameter matrices and (--) the element- wise activation function such as ReLU. Denote by n)x) = Pt (x)/p.(x). We show that the generalization performance is affected by importance weighting via the interplay between the empirical risk that hinges on 7,, as well as a term that depends on the model complexity and the deviation of the target distribution from the source distribution.
Theorem (1), Assume is 1-Lipschitz and 1-positive homogeneous. Then with probability least 1 8, we have
P ((x.o)><mo (U x) 50)
C. (Dp((P)lP.) +1 ?. H 11/2 /n
n(x;) I (0()) <7)+
tc(,,n5))
n
(1)
(1)
where (I) is the empirical risk, (II) reflects the compounding effect of the model complexity of the class of Hlayyer neural networks and the deviation between larget distribution and source distribution c(7,, n. = V
llg loga ac.
[log(1/6) a small quantity compared to (I) and (II).
Here, := := ||x|| and can take any positive value.
The proof is deferred to Appendix A.4.2 Compared to Wei et al. 2019), the empirical risk (I) hinges
on and there is an additional multiplier factor / D xx (P, Pa) + on (II). In the two discussions below, argue that the role of importance weighting on the generalization bound in Theorem is not only reflected in how the margin is affected, but also how it balances source and target distribution:
1. Suppose 0(w) enables NN to separate the data. Let Let ((o(w) := min, y:f NN (0(w)/l|et //]](([)]] x.). In the generalization bound Theorem [T if we let 7 "o(w), then (I) vanishes and only (II) remains. In this case, the importance weights affects the generalization bound via re(w) in finite steps as
7

---

Published as a conference paper at ICLR 2021
discussed in Section 4.1 That is, within finite training steps, a good set of weights w approach closer to (0()] than a bad set, and thus giving a better generalization performance. Also note that Theorem holds for the non-separable cases as well.
2. We point out that (II) is a strictly decreasing function, while (I) is a non-decreasing step function with respect to 7. Therefore, there must exists trade-off 7 that minimizes the sum of (I) and (II), which is usually attained at some 7 > (0(w)- When fy grows, certain samples will activate If (P((O(() [[:(()]) < 7) and inflate (I). The hope is that an initially activated sample (indicator term) in (I) corresponds
small 17(x)), while one with large 17(x,) has large value of ye /NN (f (w) | [|)] I|. x and thus will be activated later. This can be achieved by aligning w with n because a large weight on sample forces the decision boundary to drift away from this data point and gives a larger value of (0(w)) w//l/(l(ww))))))
(((w) |I. x,). Therefore, the generalization bound with w aligning with r) can be smaller than that with w deviating from v).
The empirical results in Figure 2 provides the numerical evidence that reflects the strong effects of importance weighting on the generalization behavior.
EXTENSION
What makes a good set of weights for learning?
We show in both Section and that importance weighting can affect how fast the classifier separates the data and converges to the max-margin solution. We also justify how the small-margin support vectors, who can think of as the hard-to-classify data points, are of significant importance. Imagine that we have access an oracle that outputs the distance of each sample the max-margin decision boundary. It is intuitive that by putting more weights on the small-margin samples, we "inform" gradient descent of their importance from the beginning and therefore accelerates the optimization. We also provide a rigorous result for linear predictor in Proposition [] Our high-level intuition justifies a number of methodologies where people use various methods to measure the hardness of classifying sample and use that as the weight, explicitly or implicitly. Examples include the curriculum learning (Bengio et al. 2009). mentor net (Jiang et al. 2018), co-teaching (Han et al. (2018) and knowledge distillation (Li et al. 2017 Hinton et al. 2015), where auxiliary models are employed (replacing the oracle) to represent the hardness of each data point.
The effect of jointly optimizing weighting model
is not unusual that the importance weights, when depending on another model, is jointly trained with the classifier to achieve better overall performance, such as the counterfactual modelling
(Schnabel et al. 2016 Xu et al. 2020) and learning from noisy labels (Song et al. 2020). For the
illustration purpose, we consider the following setup:
1 Σ g(bb,xi) (v: s.t. M x((b, < M,
1
minimize 0
(4)
where g(b,, x;) is the weighting model. By our main results, it is not difficult to conjecture that if the data is separable by f. the convergence of ff to the max- max-margin solution will still hold and the weighting model g x.) will concentrate to a constant for all i general convergence results are agnostic to the weights, so the weighting model will eventually be nullified. Also, during the beginning phase of training, the learned weights may correlate negatively to the margin (as it helps to speed up the convergence), and the correlation will diminish eventually as the weights converge to the same constant. The above conjectures are supported by the empirical evidence that we discuss in Figure 4 Therefore, jointll optimizing the weighting model may not change the convergence result but the speed of convergence is affected.
.......... n. This is because the
Interaction with explicit regularizations
Deep learning models are often trained with explicit regularization. To see how they interact with importance weighting, we first check weather they alter the norm divergence in Claim It is obvious that both the early stopping and strong regularization on ||@]] prohibits the norm divergence, so f(e..) -) will not achieve the margin solution even separate the training data. In such cases, as it has been observed by Byrd & Lipton| (2019), the impact of importance weighting on (w(w) and (0x (w)) will be significant. However, this may not help generalization according to arguments
8

---

Published as a conference paper at ICLR 2021
Linear
Woight oxtput
1900
popp
stape: 150,
ztape
staps: 0.3322
staas: hast
corrly") (g0))
500
Nonlinear predictor
012
01
110
0/0
0/5 180
1.5
320
The left-five figures show that the distribution of the Iearned weights concentrates constant as the training progresses. The rightmost figure indicates the correlation pattern between margin and the learned weights: the correlation increases rapidly the beginning. and then slowly decreases to zero (the process is much slower for nonlinear predictor so we only show the first part). Here, gxx)) = (1b TyTTx x; + b) + where o(.) is the sigmoid function, the constant one is added to avoid numerical issues.
Figure 4:
in Section 4.2 since the margins will be altered well. Indeed, Zhang al. (2016) shows that explicit regularizations may not lead to better generalization for neural networks. For the weighted ERM, Theorem provides a powerful tool characterize the trade-off induced by explicit regularizations via the margin size. Dropout, as an counter example, does not prohibit norm divergence and may not interfere with our main conclusions.
6 DISCUSSION
In this paper, study the impact of importance weighting the implicit bias of gradient descent as well as the generalization performance. Based on our theoretical findings, we propose the following future directions that are worth investigating from both the application and theoretical perspective: 1) Is there an optimal way to construct importance weights using such as the oracle margin? 2) How to correctly understand and utilize the role of jointly-trained weighting model? 3) What the combined effect of importance weighting and explicit regularizations for deep learning models?
REFERENCES
Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, and Animashree Anandkumar. Regularized learning for domain adaptation under label shifts. arXiv preprint arXiv: 1903.09744 2019.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-normalie margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Currieulum learning. In
Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: 1405.4980. 2014.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pp. 872-881, 2019.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04486, 2020.

---

Published as a conference paper at ICLR 2021
Yin Cui, Menglin Jia, Tsung-Y- Lin, Yang Song, and Serge Belongie. Class- balssebllanedd loss based on effective number of samples. In Proceedings of the IEEE Conference on Computer Vision and Pattem Recognition, pp. 9268-9277, 2019.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. Advances in Neural Information Processing Systems, 33, 2020.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, pp. 11427-11433 1438, 2019.
Alexandre Gilotte, Clément Calauzênes, Thomas Nedelec, Alexandre Abraham, and Simon Dollé. Offline a/b testing for recommender systems. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 198 206, 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018
Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information processing systems, pp. 8527-8537, 2018.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint 1xXiv:1503.02531 2015.
Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5375 5375-5384, 2016.
Chen Huang, Yining Li, Change Loy Chen, and Xiaoou Tang. Deep imbalanced learning for face recognition and attribute prediction. IEEE transactions pattern analysis and machine intelligence, 2019.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 018..00.00022 2018a.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300, 2018b.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data- driven curriculum for very deep neural networks on corrupted labels. In International Conference on Machine Learning, pp. 2304-2313, 2018.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661. PMLR, 2016.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in neural information processing systems, pp. 793-800, 2009.
Vladimir Koltchinskii, Dmitry Panchenko, et al. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Buyu Li, Yu Liu, and Xiaogang Wang- Gradient harmonized single-stage detector. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 8577-8584, 2019.
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1910-1918, 2017.
10

---

Published as a conference paper at ICLR 2021
Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pp. 2980-2988, 2017.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning, pp. 3122-3130, 2018.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: /9066 906900890, 2019.
Mor Shpigel Nacson, Suriya Gunasckar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depthh-ensitivve margins in homogeneous and non-homogeneous deep models. arXiv 2019.
preprint
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of pverpearametiization in generalization of neural networks. arXiv preprint arXiv: 2076, 2018.
Saharon Rosset, Zhu, and Trevor Hastie. Boosting as regularized path to a maximum margin classifier. Journal of Machine Learning Research, (Auu):9411997 2004a.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. In Advances in neural information processing systems, pp. 1237-1244, 2004b.
Reuven Y. Rubinstein and Dirk P. Kroese. Simulation and the Monte Carlo Method. Wiley Publishing. 3rd edition, 2016. ISBN 1118632168.
Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. Kybernetes, 2013.
Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Rec- ommendations treatments: Debiasing learning and evaluation. arXiv preprint arXiv: 1622:06022 2016.
Hwanjun Song, Minseok Kim, Dongmin Park, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey, arXiv preprint arXiv:2007.08/ 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pp. 814-823, 2015.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems, pp. 3835-3844, 2018.
Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning model the tail. In Advances in Neural Information Processing Systems, pp. 7029-7039, 2017.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pp. 9712-9724, 2019.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Adversarial counterfactual learning and evaluation for recommender system. Advances Neural Information Processing Systems, 33, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16 2016.
11

---

Published as a conference paper at ICLR 2021
A APPENDIX
We provide the omitted discussions, proofs, and extra numerical results in the appendix.
A.1 SUPPLEMENTARY MATERIAL FOR SECTION 2
We discuss the exponential-tail behavior for loss functions, the piratical implication condition C3 and the proof of Claim
A.1.1 LOSS FUNCTION WITH EXPONENTIAL BEHAVIOR
Having exponential decay the tail of the loss function is essential for realizing the implicit bias of gradient descent, since we need f(u) behave like exp( uu) as - oc. Soudry et al. (2018) first propose the notion of tight exponential tail, where the negative loss derivative - (((u) behave like:
- (u) S (1+ exp( exp(-cuu)e=" and (u) 2 exp((cxp))u
for sufficiently large u, where e₁ and C2 are positive constants. There is also a smoothness assumption on f(-). It is obvious that under this definition, the tail behavior of the loss function is constraint from both sides by exponential-type functions.
There is more general (and perhaps more direct) definition of exponential-tail loss function Lyu & Li 2211), where {u)) = exp( ff()),, such that:
f is smooth and f'(u) 2 0, Vu;
there exists e 0 such that f(())u is non-decreasing for > and f((u) + oo as u 00.
It is easy to verify that the exponential loss, log loss and cross-entropy loss satisfy both definitions. Since focus is not study the implicit bias of gradient descent, it suffice work with the above loss functions.
A.1.2 PRACTICAL IMPLICATIONS OF CONDITION C3
C3 asserts the Lipschitz and smoothness properties. The Lipschitz condition is rather mild assumption for neural networks, and several recent paper are dedicated obtaining the Lipschitz constant of certain deep learning models (Fazlyab et al. 2019 Virmaux & Scaman 2018).
The 3-smooth condition, on the other hand, more technical-driven such that we can analyze the gradient descent. In practice, neural networks with ReLU activation do not satisfy the smoothness condition. However, there are smooth homogeneous activation functions, such as the quadratic activation or (Ix) = z² and higher-order ReLU activation (xx) ReLU(z)) for c > 2. Still, in our experiments, we use ReLU as the activation function for its convenience.
A.1.3 PROOF FOR CLAIM
Soudry et al. 2018) and Ji & Telgarsky (2088)) show norm divergence for linear predictors, and the follow-up work by Ji & Telgarsky (2018a): Gunasekar et al. (2018) extend the result to linear neural networks. For nonlinear predictors such as multi-layer neural network with homogeneous activation, Nacson et al. (2019) and Lyu & Li 2019) prove the norm divergence for gradient descent in the absence of explicit regularization. Rosset et al. (2004a) and Wei et al. (2019) considers the weak regularization for linear and nonlinear predictors, however, they only study the property of the critical points instead of the gradient descent sequence.
Proof. We first state technical lemma that characterizes the dynamics of gradient descent.
Lemma A.1 (Theorem E. 10 of Lyu & Li 2019).. Under the conditions that:
E(-) is given by the exponential loss, and f f(.x) smooth function on Rd for all x E X;
12

---

Published as a conference paper at ICLR 2021
f(0.x) is a-homogeneous in C2:
the data is separated by during gradient descent at some point to:
the learning rate satisfy nu : njo S (L(((); w) log (1/)(0((); w))
for all t,
then under exponential loss we have:
(C)
2 a (22(((())
2/0
L(OW;; (() (log L(00):))
2 2/a
2
imfo
To use the results of Lemma A.1 we simply need to show two things for weak regularization:
the total risk is still smooth and we still can achieve zero risk;
there exists a critical (stationary) point such that lim- Lx w) 0.
Notice that the risk without regularization a smooth function terms of 0 for all x, since the composition of smooth functions is still smooth. It is easy to see that adding a weak regularization, e.g. 0 for r > 1, does not alter the smoothness condition as À - O. However, the weak ε regularization will make the total risk non-smooth, and therefore we have excluded it from our discussion.
For the second point, is obvious that ||01|2 is critical point under exponential loss when + Recall that:
(0; w)
Σ wi exp 0./(0/11012.xx) -10112)) >1101|z.
and
(0: w) = Σ wi exp y: f: -10012 ys V. + AV
Therefore, for both the loss function and gradient, the main term decreases exponentially fast as ||||2 increases, while the remainder terms only polynomial in ||0||2
always find small enough À that satisfy: limx-so lim -1 (0(;; w) = and limx-so lim 01 VLx w) = 0, in the same fashion
show in the A.1 below.
From a standard result of gradient descent on smooth function, which we summarize Lemma A.2 gradient descent will always converge to critical (stationary) point for the weighted ERM problem.
2018)). Let LA (0; w) be a B(w))-mooth non-negative objective. With constant learning rate 7jo B(w)- -1, the gradient descent sequence satisfies:
Lemma A.2 (Lemma 10 of Soudry et al.
lim Eien V (O())) w)]l <o;
lim (0(() w) O.
Now we need show that under appropriate learning rate, which specified Lemma A. gradient descent converges the stationary point that corresponds to the zero risk under weak regularization. Using the result from Lemma A.1 notice that if L (0()); w) does not decrease to 0, then the
denominator (x 2)2 (log (x(00(::)
2/a is bounded from below.
However, there exists a constant learning rate such that Σi 7i contradiction. Therefore, for weighted ERM with weak regularization, gradient descent converges the stationary point where L, (0(t), w) 0.
xo as f + xc, which leads to
Finally, we show to make (0(0); w) 0, we must have (g((((w) We show by contra-
diction. Suppose |10(); w)ll is bounded from above by constant C > 0, for all X < À that
13

---

Published as a conference paper at ICLR 2021
choose later. So the loss function for each sample i is bounded below by positive value that depends on C: w, exp(-9.f x)) ((C) 0. Hence, let K := X-1/(r+1), then
I(C) < LA (xx (w); w) LA (2(K";;
(A.1)
- exp ( (- 1- 7*) + X
and it easy obvious that RHS + for sufficiently small Å, which contradicts ((C) > Hence, we have ||0(0) (w)ll + so for all all À < X, which completes the proof.
A.2 SUPPLEMENTARY MATERIAL FOR SECTION 3
We provide the proofs for Proposition and 2 in this part of the appendix.
A.2.1 PROOF FOR PROPOSITION
Proof. We first characterize the 1/ log rate using asymptotic arguments similar to that of Soudry ct al. (2018). The key purpose here is to rigorously show that importance weighting plays negligible role the asymptotic regime. Let (t) be the residual term at step t:
(t, w) == ((0()) (w) 0" log t.
(A.2)
To show the 1/ log t rate, we simply need to prove that ||ō(t, w) is bounded for any w E [1/M, M)". Notice that
[]8(1 1, w)ll = 110(1 + 1, - 5(1, w)]l 2 1,, w) 8(1, w)) w) + (|8(1, w)ll?
For the first term, we have:
| w) 5(t, w)ll
=|| - () 0- (log(1 + 1) - log(()) |
, - V w]]] 1| log (1 1/t) + (2000 w) log(1 + 1/t)
S 2 ( (w): w) 100
where in the last line we use:
Vu 0, log(1 + u;
(0')TV(((()(() w) E: -w; -., xxpp=-)00x:)).00- < 0 because 0 separates the data.
Also, from the first conclusion of Lemma A.2 we see that V (w): w)ll = o(1/t), so
|8(1 1, 8(1, w)ll o(1/1) and the running sum converges to some finite number:
Σ +1, -
w)]l= 5
Co < <c.
We see that the role of the weights is totally negligible because 0" separates the data (the second bullet point above). The same argument applies to the second term 2 w) ö(t, w)) 8(t, w). where w plays no part as long as 0' separates the data. The detailed proof technical, and we refer to Lemma 6 of Soudry et al. (2018), which states that:
(8(t+1, + 1, w) 5(t, T
5tt, () w) o(1/t).
Therefore, by applying tensorization, it holds that:
|tt, w) 2 |0 = 0, w) Co + (5(t w) -5((, (() T w) < 0o,
14

---

Published as a conference paper at ICLR 2021
hence |ō(t, w)ll is bounded and
O (w) 1 (w)ll 0-
[|ō(t, w) log O11/
0
(A.3)
log
is now obvious that under the asymptotic characterization of A..2) the weights only play negligible role since 0 separate the data. However, the definition of ò under (A.2) also prohibits us from studying the finite-step behavior since it absorbs all the constant factors.
Now we use the Fenchel-Young inequality to give a more precise characterization of the convergence speed. First of all, recall the max margin problem for linear predictor has dual representation for separable data according to the KKT condition for separable problem:
0" Y; P./T",
(A.4)
where p. is the dual optimal such that
X" = - --min max - yxx 0 s.t. ||0]| = =1] = min {IlEX, pall s.t. Pi 2 Σ Pt = =1]
Now, we directly work with
(w)
0+|:
(w)l
0- 2 =
2(0", 0(0)) (w)))w))
ll
(g(')())
and from (A.4) and Fenchel- Mounhel-Youngggo Young inequality we have:
000 0 (w)) (,x ( (w) 1 (w)ll2
9" (p") g( yox, ( (()) (w)) (w))
(A.5)
7" 1=]0 w)ll
70110(0) (w)))(w) )ll
where g is a convex function with it conjugate function given by g- To build the connections with the loss function and risk, we choose such that g(u) log >, w; exp(u.). As consequence,
by letting u, x (T) (t)) and u [u....., Un), we have g(u) L(O();:)
With simple algebraic computations, the conjugate function g² (p) given by:
g (p) = logn + Σ ps log Pt = DKu(pllw) + log
Plugging the above results to A.5
(w))
log ((O(!) (w); (((())(w):)) + logn + (Kl(pll)) ((t)) (w) ||,"
go $ 1 +
(A.6)
2 [()
(0()) (w) ||
According the convergence analysis of Adaboost, we have the following technical lemma.
Lemma A.3 (Schapire & Freund (2013)). Suppose is convex, fl < E, and t" S l, with a linear predictor and sufficiently small learning rate such that Th (((()) S 1, then:
[V(000)1222 )))
L(00+1) < (1000
(A.7)
T(((.))
and thus
(1 ?)
I(g(++1)) < I(((0)) exp
ne I((()) (1-1)1000))1) ((00))
(A.8)
jat
Also, ||(++)||| Eyer E)ce))(((U)) ((00)) [VL(06))]2
L(O
15

---

Published as a conference paper at ICLR 2021
To use the results in Lemma A.3 define the following shorthand notations. Let (e(w) :=
| (VI((((t) ((((((()))))))))))))))))))) (w); w))l Now, (A6 can be further given by:
n LL w) and be (w)
L( (w);
(w) 0r I1+ log T(O(0); w)
2 [w](
| |1
0 0i (w) ai a:(w)/2)bb
logn + Dx (pllw)
+
110(0117* 1|7
|
$ E a (w))f((w)
2 2 at (w)b?(w) |000017"
+ log + DxL (pll))))
+
|000/17
(w))ll?
(A.9)
Notice that Lemma A.3 also imply:
[d((w) 7h VILOO w)ll 2 (w): w) ((((:-1(())
(w): wi).
which is bounded from above by 2MM Finally, it easy to verify that (w(w) (w)
7", and Lemma A.3
also implies that ||00) (w)ll S Σ Eiet as (w))b:()). Finally, we simplify A.9 to:
0 (w)
0. 1 2
log n + Dx [p]]]] + M
| (w)llp
1|2
0 w
?
and obtain the desired result.
A.3 PROOF FOR PROPOSITION
We first present greedy approach for the construction of the maximal separable subset Paep. which is proposed by Ji & Telgarsky (2018b).
For each sample (x;, v. if there exists a 0, such that y x, > O and minj=1,.... O, X; O, we add it to D Duep Otherwise, we add it to D Paon-sep. To see why this approach work, first notice that by choosing 2rp EiED 0,, Sep separates the data in Dsep- Then we check it is indeed maximal: for any 0 that is correct on any (x4, y:) in D Pnon-sop. there must also exist another (Xj, M3) in D Pnon-sop so y.O.x, x; < O, or otherwise (x,, y:) would have been in Deep.
It has been shown in Ji & Telgarsky (2018b) that the risk is strongly convex on D Dmonssep under conditions that are satisfied by our setting.
Lemma A.4 (Theorem 2.1 Ji & Telgarsky (2018b). If f twice differentiable, l" 0, 1 0 and lim ((u) = 0, then L(0) E. R [1, 0T x;) is strongly convex on D Duon-sop-
Now we provide the proof for Proposition 2
Proof. The first part is a direct consequence of Lemma A.4 that L(0:w)= u. 0xx is strongly convex on D Daca-sep. Therefore, the optimum 0 (w) is uniquely defined and [lθ(w) O(1). To show the second part, we leverage a standard argument for gradient descent with smoothness condition.
Lemma A.5 (Bubeck (2014). Suppose L(0) is convex and 8-smooth. Then with learning rate Th < 3/2, the sequence of gradient descent satisfies;
L(g(++1)) < ((0()) ne(1 1x/32) 10(0))1
Then for any z E Rdd:
1-1
t-1
Σ Th (L(0(0) - I(z))= < 0)(00) 2||2 [0(()
2||2
+
Σ
T
(L(O L(z)).
1
- 3n./2
0=0
0
16

---

Published as a conference paper at ICLR 2021
It is immediately clear that may choose the in Lemma A.5 such that it combines the optimal from D seop and D Don-sep- In particular, we have shown that the optimal on nonn-sop is uniquely given by ((w). For Deep we assume the max-margin linear predictor is given by 0 (so ||0 = 1).
Therefore, according Proposition |
the optimum given by log 0 Sep.
Now define
((w) + sep l
where we add the extra constant Yeep. which is the maximum margin the separable subset of the data, to simplify the following bound. Without loss of generality, we assume the features are bounded in || ||2 norm such that ||x:||2 1. As consequence:
L(O; w) Lon--sep (0(w); w) + Laep(2 (z) inf L(O; w) + nexp((](()))II]
(A.10)
where Lnon-sep and Lsep to denote the risk associated with D Doon-sep and Dsop- To invoke Lemma
A.5 first note that the required smoothness condition guaranteed by Lemma A.3 i.e. in each
step, the risk L(O()) -smooth. Without loss of generality, we assume γ7 (((()) according to Lemma
S T)- Therefore,
A.5
we have:
2
no) (L w) L(z:w)
1<t
$ Ti (L((0)) w) L(z;)) (10l))++(((0)) (L((0))))) ) -(0())
ist
(A.11)
$ Σ (L()(t) w) L(z:w))
Σ
11i
(L(( w) - L(O((t)))))
1 1//2
i<t
iC
< <10 2|1² (10(t) 2 < ||2||
Therefore, by our choice of z as well as the result in (A.10), we obtain the bound in terms of the risk:
L(0 w) inf L(0:w) + exp(O(w))
0 (w)) |1 + log" t/r
2i'ce %
Since we assume constant learning rate, when Eier 17 (O) we can simplify the above result to:
L( w) S inf L(0; w) C(I@(w)]I) + log" t/
Finally, from Lemma A.4 we known L(O0; w) is strongly convex (which we assume be w-strongly-
convex). So the convergence in terms of the risk be transformed to parameters:
sonoo-scp (() Ō(w)l 2
Lnon-sop (0()) w) -Lnon-sop (Ō(w); w)
3
2
(( (w): - inf ((0:
In
which leads to our desired results.
A.4 SUPPLEMENTARY MATERIAL FOR SECTION
In this section, we establish the detailed proofs of Proposition 3 and Theorem Recall that the loss function interested in is:
min (0 w) = L(e, w) + A||0||,
(A.12)
Denote (x(w) arg min (x w), 0" = arg maxo::00|s1 max; (0)))) Let 7x(w) = max; y/ (w) x:), 7"h max; (0'
A.4.1 PROOF PROPOSITION
We first restate the proposition.
Proposition A.I. Suppose CI, C2, Al hold. For any E (1/M, MJ", it follow that
17

---

Published as a conference paper at ICLR 2021
(Asymptotic) limx-0 72(w) -y
(Finite steps) There exists X X(r a,," w. such that for ('(w) with (w):: w) S ( w) and T I 2, the associated margin (6'(w)) satisfies 7(0'(w) c. 7070, where 10 S <1
Proof of the Asymptotic part:
Proof. We first take consider the exponential loss E(u) exp(-u). The log loss E(u) log(1 exp(-u)) can be shown in similar fashion. Suppose the weights w (wi,... wx) are normalized so that > We and w, 2 Consider
(A0:; w) = Σ exp(- (0)(x(xx))) + AA"
exp(- A max (0; x.))) + XA"
(A.13)
where A > 0, and we disregard the 1/n term in LA for the sake of notation. In addition, we have the lower bound
Lx(AO:w) 2 wy exp( A +
w)] exp(- A max(y.f((: |01"",
(A.14)
where /' = arg min; (0; x:)), wpx) = min, By taking A [w)]] 0 = 0 in the upper
bound and A = 1, 1,0- (w) in the lower bound. it follows that
WIn (0xp(-10xx(w]1])) (w)) (w))
(Bx
Lx (w(W)([0((W))]1e) (w)-=11xxww]19- -7") (W)1X
implies that
"Mx) cxp(pl10x(wx))) (1 cxp((=10x())] ,7),
or
"[n] exp( exp(-110x(w)) (7" 7x (w))) 1.
By Claim that [[0((w)] > 00 as A (or Lemma C.4 in Wei et al. (001))), the above inequality implies that (x(w) 7" as A - O.
Proof of the Finite steps part
Proof. Consider A = 1/2- /1)l//)/////////////////))/ it follows that
Lx(O'(w), s 7 L1 LLx(A0)) (AO")
s exp(-AA -7") TTA
[Upper Bound A.4.I
A.4.1
(7*)r/a (1+ (1<(o((()>)////)))))
Ar
(A.15)
Then by the lower bound A.4. it follows that
W[n] exp(pppi0 (1((0((()))))))))))))))))))))( [[)((()[[[ S (x(00(w) w)
A.15
where 7'(w) max; vif (w' /|| x.). Note (w)]l A.15
implies that
loog 15 w()))
7(w) 2
10' ((((w)) (w)
-log( angee (7* yoaa (log((7))////)))//))
A=
(1oe((+))//4//)))//og))
18

---

Published as a conference paper at ICLR 2021
Note that the numerator is at the scale log( / / log })) and the denominator is at the scale log' 1 So for sufficiently small = Xrr, a; Y" w).), we have (w) 2 c 7a/es the details of finding out the dependency A(r, a, y", w, c) on c to the readers, which is simply the basic analysis.
Y where 10 - < 1. We leave
A.4.2 PROOF OF THEOREM
When the training distribution Pirin deviates from the testing distribution Pieas we develop the generalization bound that characterizes this deviation. Denote by Ps and pr the respective densities of from the training data and the testing data. Let Ps) (())) ())r(r)dr and pe(x.)
(x,) (x(),) We first restate Theorem
Theorem A.1. Assume is 1-Lipschitz and 1-positive homogeneous. Then with probability at least
1 8, we have
m (N (((w),)) =0)
((x,))>-pe
V((..IP.) +I H 1)/2 +e(7,n,6).
n(x;)
<7)
(1)
(1)
where (I) is the empirical risk, (II) reflects the compounding effect of the model complexity of the class of Hllayer neural networks and the deviation of the target distribution from the source distribution, c(7y, n, /
log loggogg aeT
loga
/oo((1/0) is small quantity compared (I) and (II).
n
Here C' == supx |>||; y is any positive value.
To prove Theorem A.I we first establish few lemmas.
Lemma A.6. Consider an arbitrary function class F such that Vf we have Exe If(x) C. Then, with probability at least 1 6 over the sample, for all margins > 0 and all J E F we have,
P
P(xxa)) Findt (v](x) 50)
log(log2 10) 7
(A.16)
n(x) <7) RF,n(F)
log (gg(1/0) 2n
n
where (F) sup sup E 7xxi) is the weighted Rademacher complexity (e;
i.i.d Rademacher variables).
Proof. This lemma is adapted from Theorem 1 of Koltchinskii et al. (2022) by considering the deviation of the testing distribution from the training distribution. Then it is obtained following Theorem of Kakade al. (2009).
Lemma A.7. Let FH be the class of real-valued networks of depth H over the domain where each parameter matrix Wt. has Frobenius norm at most Mp (h), and with an activation that is 1 1-Lipschitz, heative-homogeneous. Then,
C ((P. +1 o (1) (V2 2H 1) h
Rn,((H)
Mr(h),
Vn
where C. := ==supeex |||||
Proof. From Theorem I of Golowich et al, (2018), arrive at
nR(n, (FFu) log 2 E.
[M
Σ cxn(x,)
T=1
19

---

Published as a conference paper at ICLR 2021
where M - (h).). Consider Z == M. E== (,7]xx))x])) that is random function of the n Rademacher variables. Then
log f2" Eex=)))(22) H log 2)
log A(Z E2)] + BZ.
A
By Jensen's s inequality, we have
E 7 S M
E.
(n(x,)x;111 M Σ |xx111
In addition, we note that
( ........ ..... 6n)
61 ..... cn, S 2M1
By the bounded-differemn condition [Boucheron al.
2013).
Z is sub-Gaussian with variance
factor (2M (2M) M2M >i= (T.;)
X
2. So
1
-i=1 (x(;) ) | XM E
E Eexp A(Z EZ))
À
2 H
Taking X
follows that
M MV2
2 n(x
(2 H E Exx \Z}
a
SM(v2 22og + 1)
Σ nxxx) VTCM((22lg(2)FH +1)
Σ mxx,)?
(A.17)
By law of large number, 1 n nxx)) D(P.)P.) +1 7z The desired result follows.
Lemma A.8. Suppose fNN -) is H-layer neural network and C suPzex ||=||12. Then, There exists another parameter s.t. n (P*(0/100)) x) = - x), for any x E and that
the parameter matrix of each layer of foM (v)) has a Frobenius norm no larger than 1/ L/VH. H.
suPaex (0) S.
Proof. This lemma are obtained by reorganizing the proof of Lemma D3 and the proof of Proposition D.1 of Wei et al. (201)).
Proof of Theorem A.1
Proof. Theorem A. follows by Lemma A.6 A.7 and A.8
20


Reviews:
[{"review_id": "y14gOftjhT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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 proposes a theoretical explanation of the role of importance weighting with regards to the implicit bias of gradient descent (convergence to the same direction as the maximum-margin solution) and the generalization ability of the model. \n\nThe authors first extend the norm divergence result to a general setting where weak regularization is used. \n\nFor linear predictor and separable data, they show that importance weighting affects the convergence speed during gradient descent but not the convergence result or the $1 / log(t)$  rate. In particular, they find an expression of the constant term resulting from the importance weighting. Thus, using an “inverse margin weighted” method, the authors are able to accelerate gradient descent in a finite-step optimization setting. \n\nFor linear predictor and non-separable data, the authors show that importance weighting uniquely defines the solution on the non-separable subset, which can be seen as an intercept/constant term. The weights only control how the constant shifts on the non-separable data subset. \n\nFor non-linear predictor, they show that the optimal margin is reached regardless of the importance weighting choice under the infinitesimal weak regularization setting. They also show that in a finite-sample setting, importance weighting affects the generalization bound via the empirical risk and a term depending on the model complexity and the deviation between target and source distributions. The impact of importance weighting on the generalization ability of the model is also shown empirically. \n\nOverall, the authors show that importance weighting can affect how fast the model separates the data and how fast the model converges to the max-margin solution for linear and non-linear predictor in some settings. They also deduce that giving more weights to the hard-to-classify points, corresponding to the small-margin samples, when used in importance weighting, is very important for the acceleration of the optimization. The authors conjecture and show empirically that the results still holds if the importance weights are jointly learned with the model\n\n\nPros:\nThe paper seems to offer important theoretical results and empirical validations regarding the role of importance weighting on the implicit bias of gradient descent and the generalization ability of linear and non-linear models in some settings.\nThe paper is clear and well written. There is a good balance of theoretical findings and empirical validations.\n\nCons: \nThis paper does not seem to have any major weaknesses. \n\n\nMinor Comments:\n-\tThere seems to be a typo in the 3rd sentence of the 2nd section: “from the which” should probably be \"from which\"\n-\tThere seems to be a typo in the 2nd paragraph of page 4: “to understand the role of importance weighting” (\"of\" is probably missing)\n-\tThere seems to be a typo at the top of page 5: “is able to accelerate” (\"to\" is probably missing)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "v4xWZR4rFyu", "reviewer": "AnonReviewer1", "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": "The paper studies the effect of importance weighting schemes in deep learning models. A deep learning setting is considered where the empirical loss of labeled training data is weighted with importance weights and regularization on the network parameters is also included in the objective, which is optimized with gradient descent. \n\nTwo main results are presented in the paper. The first result focuses on a linear prediction scheme, in which case the convergence is shown to be faster if the weights of the samples are matched with the inverse of their SVM margin. An extension of this result is also proposed for the case where the data is not linearly separable.\n\nThe other main result considers multiple-layer feedforward networks in a covariate shift setting. A generalization bound is presented, which relates the probability of error to the agreement between the importance weights and the deviation between the source and the target distributions. The interesting takeaway message from this analysis is that aligning the weights with the distribution deviation reduces the error.\n\nOverall, the paper is clear and well written, and it provides some interesting insights into several common learning settings from the perspective of importance weighting. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rg68wP-ai3V", "reviewer": "AnonReviewer4", "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": "It is now well-understood that when the data are linearly separable,  gradient descent over the linear class of functions converges toward the hard margin solution. It highlights the implicit bias of gradient descent. Among all solutions interpolating the dataset, gradient descent selects the one with larger margin, partly explaining why over-parametrized models may generalize.  The picture for non-linear class is a little bit more complicated. \nIn this paper, the authors study the impact of importance weighting on the implicit bias of gradient descent for both linear and non linear predictors. The problem is interesting and non trivial because importance weighting may affect the geometry of the gradient descent. In particular, a natural question is the following: does the importance weighting affect the margin of the solution (and thus change its generalization properties ?). Note that the authors does not clearly define what is the goal of the paper and to which problem there are trying to answer\n\n\nHere are some questions and remarks about the paper:\n\n- You study importance weighting for neural-networks: is it used in practice for these class of functions ? Could you give some references ? \n\n- The introduction is not clear. For example the first paragraph aims to define importance sampling. Introduce a formal definition. You sentence \"Importance weighting is a standard tool used to estimate a quantity under a target distribution while\nonly the source distribution is accessible\" is not clear at all.  Then, you present exploratory ideas before clearly presenting the contributions of the paper. We are completely lost ... You should clearly define what is the goal of the paper and how you achieve it. I had to read 3 times before understanding what you really wanted to do \n\n- Do you focus only on the binary case ? It is one again not clear \"For the sake of notation, we mostly study the binary setting\", if so just say it. \n\n- You use concepts that you do not define clearly: what does mean that $\\mathcal D$ is separated by $f(\\theta^{t},x)$ at some point $x$ ? Do you mean that there exists $\\theta^{t}$ such that  $y_if(\\theta^{t},x_i) \\geq 0$ ? \n\n- The paragraph after claim 1 is not clear at all (and you forgot the exponent $\\alpha$ on the norm of $\\theta$). I really don't get what you are trying to say here ... \n\n- There are problems with your bibliography (page 3 paragraph beginning section 3, page 12 paragraph beginning A.1.3 for examples)\n\n- Sometimes you write $\\|\\cdot \\|$ and sometimes $\\|\\cdot \\|_2$. Keep the same notation along the paper \n\n\nThe proofs of the paper are a little bit hard to follow but seem to be correct. I also have an other question. Would you be able to generalize the analysis without the condition $w_i \\in [1/M,M]$ ? This condition is restrictive and we cannot use $w_i = 0$ which can be very useful for robust purposes. So is it possible to look at the condition $w_i \\leq M$ instead ? It is, in my opinion, an interesting question.\n\n\nTo summarize, the paper tackles an interesting problem (but in the restrictive setting $w_i \\in [1/M,M]$)? However it paper is poorly written and not clear at all. I had the feeling that the authors were completely in a rush and did not organize the paper. Instead they put ideas together, without a clear common thread. I think you should focus on the form of the paper and then resubmit it for publication. There are too many problems right now. Work on the clarity of your ideas. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GohpxQSVEHd", "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": "\n### Summary\n\nThis paper studies the inductive bias of gradient descent (GD) on smooth non-linear models when optimizing a weighted ERM. The authors provide several novel results for the linear and non-linear model cases. For linear models and linearly separable data, they show that GD converges to the hard-margin SVM solution and the convergence rate upper bound is lower for weighted ERMs that have higher weight on low margin points. They further characterize the inductive bias for non-linearly separable data, on a unique non-linearly separable subspace defined by Ji and Telgarsky (2018). For nonlinear models they consider a weak regularization setup. They show that asymptotically GD converges to a max margin predictor, which is similar to the non-weighted ERM case. They prove a generalization bound for weighted ERM and together with experiments provide insights on the generalization performance of GD in this case.\n\n### Reason for score\n\nThe paper provides several novel theoretical results in a practical setting. The proof techniques might be useful for analyzing non-linear models in other settings. Although the writing and main \"take-home\" messages of the paper can be improved, overall I recommend for acceptance.\n\n### Pros\n1.\tNovel theoretical results in several challenging settings (linear models with non-separable data and non-linear models).\n2.\tAnalysis in a practical setting of weighted ERM.\n3.\tNovel theoretical insights that are corroborated with experiments.\n\n\n### Cons\n\n1.\tAlthough the authors provide several insights on weighted ERMs, it is difficult to understand the main takeaways from the analysis. Specifically, under which conditions is it better to use weighted ERM and not ERM. How can this be derived from the analysis?\n2.\tThe discussion of the generalization results in Section 4 is not clear. The first result shows that asymptotically GD obtains the same margin in the case of non-weighted and weighted ERMS. Therefore, this *may* hint that they have the same generalization performance. In contrast, the discussion after Theorem 1 suggests that weighted ERM can have better generalization performance. This should be clarified. I think that Figure 2c and Figure 2d are very interesting because they show the following: for unbalanced data, GD on weighted ERM and ERM obtains roughly the same margin, but it has different generalization performance in these cases. I think that the authors should discuss this and it may strengthen the insights provided by the analysis.\n3.\tIn the introduction, the contribution of the paper is not so clear. For example, \"characterize the impact of importance weighting…\" is not clear. \"We propose several exploratory topics…\" – this seems like a minor contribution. I think that the authors should summarize the theoretical results and say how they relate to the observations of Byrd et al. (2019).\n4.\tIn Section 3, it is claimed that the exponential loss is used WLOG. Does this mean that the results also hold for other losses? This is not clear.\n5.\tIt is claimed that Figure (b) shows better performance but this figure only shows the margin. Is the test loss also better?\n6.\tIn some cases, it seems that the informal claims made by the authors are too strong. For example, in page 5 it is said that \" we provide a complete understanding\", but the inductive bias of GD is not shown on the separable space in the case of non-linearly separable data (only for the non-separable space). In page 5, it is said that theta_sep in the separable region does not depend on w, although this is not shown formally. In page 4, it is said that the pivotal role of the margin for generalization of NNs is well understood. However, we are currently far from understanding generalization in NNs and the cited papers provide only *upper* bounds on the generalization error and might be very loose.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the effect of importance weighting schemes on the implicit bias of gradient descent in deep learning models. It provides several theoretical results which give important insights on the effect of the importance weighting scheme on the limit of the convergence, as well as convergence rates. Results are presented for linear separators and deep learning models. A covariate shift setting is also studied. The theoretical results are supported with empirical demonstrations, and also lead to useful insights regarding which weighting schemes are expected to be more helpful. They also explain some previously observed empirical phenomena. 


Pros:
- New theoretical results which provide important insights on an important topic
- Empirical demonstrations which support the theoretical results


Cons:
- No significant issues. 

Decision: Accept (Spotlight)