Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper attacks the issue of mismatch in distribution of labels between train and test samples. The authors propose a DRO-based approach which amounts to solving a modified ERM problem. Compared to classical approaches, the proposed method doesn’t entail fitting many different models: just a single model. The method builds on recent progress on solving nonconvex-concave games for approximate stationary points. The resulting algorithm is a mirror-descent scheme with explicit convergence rates, under Setting : train and test label distribution do not match

The general approach is:
Learn a classifier robust to arbitrary label shifts (from a family) -> doing this by using DRO approach because it allows them to train a model that performs well on all label distributions sufficiently close to the training data label distribution.
The paper proposes the DRO approach with KL-divergence for the label shift problem, an analysis of the proposed algorithm (optimization techniques and convergence analysis) and experiments on Imagenet (ResNet50)

Good points
      - It paper is well-written and asy to follow paper. The problem and the algorithm are clearly described and well analyzed. The experiments are also quite well done. 
The label shift pb is clearly explained and described
The analysis of the proposed algorithm (more or less all section 3) is quite thorough.
The experiment section is clearly described (and the additional experiments in Appendix are useful).

Bad points:
The experiments are not really convincing in the sense that the improvement is either really limited on the test set by comparisons to the baseline (on Imagenet), or similar to that of the Agnostic method (on CIFAR-100, Appendix)
It would have been nice to have a more detailed explanation of the complexity of the algorithm in practice, and more explanation on the choices of hyper-parameters (Appendix B). There are many hyper-parameters that were set to a fixed value, and only one parameter is tuned (how?), so how/why do you choose these fixed values? 

Recommendations:
      -  Contrary to what the authors say, inner problem in (4) does indeed have a closed-form solution. It is the Fenchel-Legendre transform of KL divergence, which equals log-sum-exp(...). Also, this max is attained at Boltzman distribution which is proportional to exp(loss / temperature). See Lemma 4 of Faury et al. (AAAI 2020) Distributionally Robust Counterfactual Risk Minimization. BTW, its would be interesting to contrast this result with the result of Lemma 2, I. Equation (7),  of the current manuscript.

Errors:
      -  Equation (2) and previous equation (unlabeled): yi should be replaced with y
      - First equation  (unlabeled) in section 3.1: missing pi(y) in importance weight 

Questions
It is mentioned that the Agnostic method faces many challenges during training, but these challenges are not explained afterwards (computation time? Difficult parameters tuning? Etc.)

I’ll happily revise my score upward if my concerns are addressed.
review_title: Coping with Label Shift via Distributionally Robust Optimisation 

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper tackles label shift in supervised learning via distributionally robust optimization. The main idea is to train by solving a min-max problem, where the max problem searches for the worst-case label shift in an Kullback-Leibler divergence ambiguity set. The KL ambiguity set will generate some form of adversarial reweighing of the sample training points, which gives us hope that the learned parameters will perform better in the test data (with shift). The paper proposes to solve the Lagrangian version instead of the constrained version of the DRO problem, and proposes a gradient descent-ascent type of algorithm.

The main contributions of this paper is condensed in Section 3:
- From the mathematical viewpoint, the DRO problem (3) and the mini batch gradient estimator are not new.
- In Section 3.2, the authors proposed the Lagrangian problem. However, the difficulty of this problem lies in choosing the "right" value of gamma_c. Indeed, finding gamma_c is not trivial, and simply saying that a bisection search can be employed (as suggested by the authors) is not sufficient. To use bisection search, the authors should argue that the optimal value of problem (4) is at least convex in gamma_c, and this result has not been established. 
- The authors relax the 2-norm to a KL-divergence in equation (6). This relaxation makes the complaint (2) in page 4 become invalid. Indeed, complaint (2) says that projection is difficult under 2-norm, however, we can also relax to the projection using KL-divergence to alleviate this difficulty.
- Problem (3) and (4) are equivalent only if gamma_c is optimally tuned. The algorithm analyzed in Section 3.4 is has guaranteed only for problem (4). It is still not clear what guarantee we can have on the original problem (3), which is the main problem of interest.

Getting back to the main contributions that are listed in page 2: I can only partially agree with contribution (2). However, I do not think that contribution (1) about the formulation and contribution (3) about the numerical results can really be justified as the main contributions of this paper.

Minor comment:
1. In algorithm 1, line 1 should be \pi_0. In line 2, the for loop should start with t = 0
2. I don't understand why p_emp should not be on the boundary of the simplex. If p_emp is on the boundary, we can simply drop the samples (x_i, y_i) with p_emp(y_i) = 0, and that should not affect the problem.
review_title: Good submission but lacks some coherency

final_score: rating: 6: Marginally above acceptance threshold
review_content: Weighting each class differently during model training is a common technique to deal with label imbalance and label shift. In this paper, the authors propose AdvShift, a method for learning these weights in a data- and model-dependent way through distributionally robust optimization (DRO). 

I found the paper especially well-written and clear, from the problem setup and contextualization within related work, to the description and intuition behind the method and the results, as well as the candid discussion of potential limitations of the method. Thank you to the authors for the enjoyable read. 

Overall, the method and results seemed promising. However, I had two general areas of concern that prevented me from giving a higher rating; the first with the comparison to prior work, and the second about the experimental details.

**Prior work**
The authors identify Mohri et al. (2019) and Sagawa et al. (2020) as their closest work, so I primarily read up on and referred to those papers. 

[1a] Compared to Mohri et al. (2019), the differences here seems to be that (a) Mohri et al. use a chi-squared regularizer vs. the KL divergence term used in AdvShift; (b) Mohri et al. use (computationally expensive) projections whereas AdvShift uses proximal updates; and (c) AdvShift also includes a couple of optimization tricks, loss clipping and gradient stabilization, as detailed in the appendix. The argument that the authors make is that (b) is the important ingredient; that is, it is a question of optimization. Is this a fair characterization?

[1b] If so, the tricks used in (c) seem to be critical to the performance of AdvShift, so they might perhaps explain the gap between Mohri et al. and AdvShift. The authors write that the proximal mirror ascent updates solve the optimization instability (compared to the projection operator), but do not elaborate. 

[1c] Moreover, if the superiority of the method hinges on optimization, then the phenomenon discussed in the last paragraph is especially striking: it seems like AdvShift is not optimizing properly with regard to the algorithm threshold r, as the authors point out. This suggests that there could be fundamentally something wrong with the algorithm and its optimization.

[2] Compared to Sagawa et al. (2020), the authors write that the method in Sagawa et al. requires the ability to sample data from a given group. This does not appear to be true: Sagawa et al. describe their method as using standard minibatching and SGD. The authors also write that Sagawa et al. only test their method on a small number of labels, which is true, so it seems plausible that AdvShift will perform better on a large number of labels, but this would need to be empirically determined.

[3] Both Mohri et al. and Sagawa et al.’s methods were originally tested on a small number of labels. How does AdvShift compare to these when there are a small number of labels? In the Appendix, it appears that Mohri et al. performs comparably to AdvShift on CIFAR-100. Is the pitch that one should use AdvShift when there are a large number of labels, but that it does not matter otherwise?

**Experimental details**
[4] Fig 2(a) and 2(c): Why is there no difference in training error at tau = 0 even when training for a very conservative model (e.g., AdvShift 1.0, or Fixed 3)? This would make sense if train errors are close to 0 but they are not: Fig 6 in the appendix shows that the training errors are >20% at tau = 0. The models used seem very underparameterized, presumably as a result of hyperparameter tuning; do they actually beat a normal ResNet with standard hyperparameters in the adversarial setting? I couldn’t find hyperparameter tuning details in the appendix.

[5] Figs 2 and 3: Are the authors reporting test or validation accuracies? The figure captions all say validation, but the text all says test. 

[6] Fig 2(d): I am confused by why the fixed baseline does so badly. To clarify, for each value of tau, does each model have its own adversarial shift? Specifically, for the fixed model, is it still being evaluated against the fixed distribution? If not, could we plot it as an oracle? If it is, that seems very strange to me that optimizing for exactly that distribution would get higher train error. The authors cite Byrd and Lipton (2019) but I wasn’t able to figure out how that paper addressed this case, since Byrd and Lipton seem to be operating in the separable data setting. This suggests that there are some optimization issues?

**Minor**
[7] It is reasonable to focus on the adversarial setting, but the adversarial test error is still exceedingly high despite some improvements from AdvShift, so from the point of view of providing guarantees, this is only marginally better. I’m curious if AdvShift helps on non-worst-case settings. Other work on label imbalance, for example, https://arxiv.org/abs/1901.05555 show that their reweighting techniques can improve accuracy on the standard test set for ImageNet. 

Typos: 
S4.1, “has a largely balanced training label distributions”
S4.2, “compre”

**Update**
Thank you to the authors for the detailed response. Overall, I'll leave my rating as a 6. The paper is clear and proposes a promising optimization method, with moderate comparisons to prior approaches and reasonable results on ImageNet (but not CIFAR-100). The impact of these results are somewhat diluted by the overall absolute low scores in the adversarial setting, but as a general DRO optimization method, the result is interesting. Thank you for all the discussion.

Comments to the latest author response (posting this as an edit since public comments are now disabled):

[1] Thanks, the updated version is clearer.

[2] I agree with this characterization (for example, the unconstrained perturbation might cause optimization instability). The paper still seems to contain the language about the Sagawa paper requiring a custom sampler. Overall, I agree that there are reasons to believe that the proposed optimization method is more stable, but I think the authors should be clear that they only compared to Mohri et al. experimentally (in your response to Reviewer 3, you mentioned that you extensively discussed and compared to both Mohri and Sagawa).

[6] Thanks. I also agree with this. I had two points: first, the differences between your proposed algorithm and the standard algorithm might be more stark when the training is not balanced. Second, in imbalanced settings, it is more likely that the test distribution will be skewed (e.g., rare animals in iNaturalist).

review_title: Review

Meta-review: 
This paper considers the problem of training neural networks to be robust to label shifts. To do so, it proposes to use a distributionally robust optimization (DRO): instead of minimizing the expected error with respect to the empirical data distribution, the worse case expected error is minimized over a KL-divergence "ball" of distributions centered at the empirical distribution with a given radius. The main contribution of the paper is an efficient algorithm for achieving this optimization, that avoids the need to project onto the uncertainty set or to sample in non-standard ways from the training set. The paper provides evidence on the ImageNet data set and the ResNet-50 architecture that the proposed AdvShift algorithm outperforms reasonable baselines.

Reviewers raised concerns about the novelty of the algorithm, and claims the paper makes about the infeasibility of the sampling required by one of the competing baselines, and the need for the Lagrangian parameter used in the algorithm to be well-tuned. The rebuttals addresses the concerns suitably; in particular, the novelty of the algorithm lies it it being the first DRO-based solution for the label shift problem and its efficiency obtained by using KL uncertainty set and the Lagrangian formulation of the problem, which allows a closed form solution. 

Due to the strong empirical and theoretical performance of the proposed AdvShift algorithm, it is recommended that this paper be accepted.
Decision: Accept (Poster)