Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 

Two 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.

The 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.

Overall, the paper is clear and well written, and it provides some interesting insights into several common learning settings from the perspective of importance weighting. 
review_title: Useful insights into importance weighting 

final_score: rating: 7: Good paper, accept
review_content: Summary:

This 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. 

The authors first extend the norm divergence result to a general setting where weak regularization is used. 

For 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. 

For 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. 

For 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. 

Overall, 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


Pros:
The 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.
The paper is clear and well written. There is a good balance of theoretical findings and empirical validations.

Cons: 
This paper does not seem to have any major weaknesses. 


Minor Comments:
-	There seems to be a typo in the 3rd sentence of the 2nd section: “from the which” should probably be "from which"
-	There seems to be a typo in the 2nd paragraph of page 4: “to understand the role of importance weighting” ("of" is probably missing)
-	There seems to be a typo at the top of page 5: “is able to accelerate” ("to" is probably missing)

review_title: Theoretical and empirical explanations of the role of importance weighting for (deep) learning models

final_score: rating: 7: Good paper, accept
review_content: 
### Summary

This 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.

### Reason for score

The 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.

### Pros
1.	Novel theoretical results in several challenging settings (linear models with non-separable data and non-linear models).
2.	Analysis in a practical setting of weighted ERM.
3.	Novel theoretical insights that are corroborated with experiments.


### Cons

1.	Although 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?
2.	The 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.
3.	In 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).
4.	In 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.
5.	It is claimed that Figure (b) shows better performance but this figure only shows the margin. Is the test loss also better?
6.	In 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.

review_title: Novel results for weighted ERM and nonlinear models. The main messages of the paper can be improved.

final_score: rating: 7: Good paper, accept
review_content: 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. 
In 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


Here are some questions and remarks about the paper:

- You study importance weighting for neural-networks: is it used in practice for these class of functions ? Could you give some references ? 

- 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
only 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 

- 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. 

- 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$ ? 

- 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 ... 

- There are problems with your bibliography (page 3 paragraph beginning section 3, page 12 paragraph beginning A.1.3 for examples)

- Sometimes you write $\|\cdot \|$ and sometimes $\|\cdot \|_2$. Keep the same notation along the paper 


The 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.


To 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. 
review_title: Interesting problem but the paper is not clea

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)