REGULARIZED LEARNING FOR DOMAIN ADAPTATION UNDER LABEL SHIFTS
We propose Regularized Learning under Label shifts (RLLS), a principled and a practical domain-adaptation algorithm to correct for shifts in the label distribution between a source and a target domain. We first estimate importance weights using labeled source data and unlabeled target data, and then train a classifier on the weighted source samples. We derive a generalization bound for the classifier on the target domain which is independent of the (ambient) data dimensions, and instead only depends on the complexity of the function class. To the best of our knowledge, this is the first generalization bound for the label-shift problem where the labels in the target domain are not available. Based on this bound, we propose a regularized estimator for the small-sample regime which accounts for the uncertainty in the estimated weights. Experiments on the CIFAR-10 and MNIST datasets show that RLLS improves classification accuracy, especially in the low sample and large-shift regimes, compared to previous methods.
This paper presents a new contribution for a largely understudied problem of label shift (also called target shift), a situation occurring when the class proportions vary between the training and test sets. The proposed contribution builds upon a recent work on the subject by Lipton et al., 2018 and addresses several of its weaknesses. The paper also gives several improved generalisation bounds w.r.t. that of Lipton et al. that are further used as guidelines to tune the regularisation parameter based on the size of source and target samples. Finally, the empirical results show that the proposed algorithm outperforms that of Lipton et al. especially in cases where the shift in proportions becomes quite important. 
*Pros: 
   - A work in an area with very view contributions and a certain lack of theoretical results
    -Theoretical results that are actually used in the algorithmic implementation and that allow to define the regularisation parameter based on the size of the available samples
    -Improved empirical results
*Cons: 
    -An incomplete state-of-the-art section that does not cite several important contributions on the subject;
    -Lack of baselines due to the incomplete state-of-the-art section;
    -Lack of clear comparison with Lipton et al. both in terms of the proposed method and the obtained theoretical guarantees.  
*Detailed comments:
This paper is rather interesting and well-written.
I have several major concerns regarding this paper. They can be summarised as follows:
    There is an important part of literature review on target shift that is missing in this paper. Even though, the paper mentioned the work of Chang, 2005 and Zhang, 2013, it completely ignores several other highly relevant methods such as [1,2]. These works also propose algorithms that allow to estimate class proportions that vary between training and test data. This estimation can then be used for cost-sensitive learning to correct the target shift. The paper should mention this work and add the corresponding methods to the baselines for comparison. 
    Several statements that justify the contribution of this paper are unsupported. For instance, the paper states that the estimator obtained with the inverse of the confusion matrix can be arbitrary bad when the sample size and/or the singular values are small. However, this exact dependence can be found in Lemma 1 for the proposed contribution also! This is repeated in the beginning of Section 2.2 to justify the regularised version of the estimator but once again no evidence was provided to support the claim. The obtained bound for the regularised algorithm also has these two terms and thus it is not clear why the regularised algorithm is supposed to work better. 
    The paper may want to clearly state the differences between the proposed algorithm and that of Lipton et al. and also between the obtained error bounds. The paper states that it achieves a k*log(k) improvement over Lipton et al. bounds but as fair as I can see this improvement is achieved only when h_0 is an ideal estimator. Furthermore, Lipton et al.’s bounds are linear in k while the proposed bounds replace this term with log(k/delta) so that when \delta is small, ie the bound holds with high probability, the bound becomes much worse. I would suggest to add a brief discussion on the relationship between the two to better highlight the original contribution of the paper. 
    The proofs are quite badly written with many lacking results used to move from one inequality to another. For instance, Lemma 2 is proved using the theorem 1.4[Matrix Bernstein] and dilation technique from Tropp but it is not clear which results the authors are using in particular; Theorem 1.4 is related to the largest eigenvalue of the sum of matrices while the authors obtain an inequality for the norm of the sum without any further comment on how this transition was made. Also, I do not see why delta is smaller than 1/2 in Lemma 2. 
*Minor comments:
   - p.1: expected have -> expected to have
   - p.4: we are instead only gave access -> given access to 
   - I do not understand Figure 1. Should it be n_q*n_p on the y axis ?
   - The inequality for n_q next to Figure 1 is derived from the bound (6). Why it is independent of k?
   - Why the authors choose to the black box predictor h0 to be a two-layer fully connected neural? Is there any particular reason to use this classification model?
[1] Class Proportion Estimation with Application to Multiclass Anomaly Rejection, AISTATS14
[2] Mixture Proportion Estimation via Kernel Embeddings of Distributions, ICML16