Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Disclaimer: I was able to read the other reviews and the author’s responses before finalizing this review.

The paper proposes an easy-to-implement algorithm for DRO on example weights, with the same computational cost as SGD.  The algorithm is based on hardness weighted sampling and links are shown to hard example mining.  Convergence results are shown for (finitely) wide networks.  Additionally, the paper claims to demonstrate the usefulness of the algorithm in deep learning.

I am unable to assess how the convergence results place in the literature, but I believe they motivate the algorithm.  The claims of practical usefulness in deep learning do not seem supported by the provided empirical evidence.
For the CIFAR experiments, the ERM baseline does not seem to train - probably due to the choice of learning rate.  This makes it unclear how the proposed algorithm compares.  They claim the algorithm is more robust to the learning rate, so is it possible to train with the original learning rate used for the ERM baseline?  Why was a different learning rate chosen?

If the experimental results showed an improvement over a properly trained ERM baseline on CIFAR I would lean toward weak accept.

Many state-of-the-art deep learning pipelines do not use plain SGD - for example, the WideResNet you used on CIFAR. How is Algorithm 1 used on these? Do we only make changes to the update on line 24?  Using momentum with nested optimization can introduce instabilities. Perhaps combining momentum with nested optimization of loss weights and parameters is why the baseline does not train?  Maybe you could try an architecture that trained using vanilla SGD, so you can better leverage your theoretical results?

It would provide evidence of the usefulness of the algorithm if we could take various pipelines and just drop their optimizer updates into algorithm 1 - hopefully without having to spend time re-tuning their optimizer parameters. It would also be nice to see the training loss/accuracy - perhaps over all classes and just cats - in the appendix.


Things to improve that did not impact the score:

(Page 1) “in term” -> “in terms”
(Page 1 & 2) “an history” -> “a history”
(Page 2) “Optmization” -> “Optimization”
(Page 5) “allows to link” -> “allows us to link”
(Page 7) “we focus at” -> “we focus on”
(Page 8) “allows to guarantee” -> “allows us to guarantee”
(Page 19) “continous” -> “continuous
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper studies the Distributionally Robust Optimization (DRO), in the sense that the weights assigned to the training data can change, but the training data itself remains unchanged. They demonstrate that SGD with hardness weighted sampling is a principled and efficient optimization method for DRO in machine learning and is particularly suited in the context of deep learning. On the theoretical side, they prove the convergence of our DRO algorithm for over-parameterized
deep learning networks with ReLU activation and finite number of layers and parameters.

The DRO problem studied in this paper is relatively easy, in the sense that the inner maximization has close form solution (at least for KL divergence). Therefore, the proposed method is straightforward. All the derivations in Section 3 and 4 are strainghtforward and sensible. I do not know any paper that has proposed Algorithm 1 (or something similar) before, but I will be surprised there is not. I do not check the derivations in Section 5, but I suppose that it is a small modification of the proof in Allen-Zhu et al., 2019. I suppose that the theorem is correct, but it provides nearly no practical guidance.

In Algorithm 1 Line 18-19, the algorithm proposes to do sampling with replacement using the softmax probability \hat{p}. How about directly multipling the weights \hat{p} to the current minibatch of samples. (i.e., re-weighting the samples instead of re-sampling the samples). What's the difference between these two choices?

Second, both experiments are not convincing enough. In the CIFAR10 experiment (Figure 1), the baseline method ERM is too low. I guess that this low number is due to the large initial learning rate 1. The authors should provide the best performance IRM can achieve, and compare with the best performance DRO can achieve. Although the authors are claiming that the proposed DRO works with larger learning rate, Figure 1 (Left) simply gives readers the wrong information that ERM does not work. "Figure 2 suggests that if we train ERM long enough it will converge to the same accuracy as DRO." The objectives of ERM and DRO are different. Their accuracy may become closer to each other, but I'm not sure they will finally achieve the same accuracy (the same optimum). Can the authors elaborate on this?

Finally, the focal loss has achieved good empirical results in object detection. I feel that it can be formulated as a special case of the Equation (2) and Algorithm 1, by picking up some proper \phi-divergence and using the (un-normalized) re-weighting scheme. It will good if the authors can provide a principled view of focal loss through the lens of DRO. 

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposes a method for Distributionally Robust Optimization (DRO). DRO has recently been proposed (Namkoong and Duchi 2016 and others) as a robust learning framework compared to Empirical Risk Minimization (ERM).  My analysis of this work in short is that the problem that this paper addresses is interesting and not yet solved. This paper proposes a simple and efficient method for DRO. However, convergence guarantees are weak which is reflected in their weak experimental results. And for a 10-page paper, the writing has to improve quite a lot.

Summary of contributions:
The phi-divergence variation of DRO introduces a min-max objective that minimizes a maximally reweighted empirical risk. The main contribution of this work is as follows:
- Show that for two common phi-divergences (KL-divergence and Pearson-chi2 divergence), the inner maximization has a simple solution for the weights that depends on the value of the loss on the training set.
- Use the above algorithm and modify SGD by changing the sampling of data according to the weights.
- Convergence proofs for the above algorithm for wide networks (not necessarily infinite-width).


Cons:
- Fig 1, ERM should not be so bad as if predicting randomly. This suggests a problem in the experimental setting. At least more ablation study is needed, e.g. try varying the percentage of data kept and show the final test accuracy as a function of this percentage for ERM. In the worst case, the accuracy for ERM should be ~90% on 9 classes and zero on 10th which is ~80% for uniform test accuracy. Another point, what is the train accuracy on cats? ERM should be overfitting to those few cats in the training set and achieve some non-zero accuracy at test. But it seems the test accuracy is almost exactly 0 at test time.
- In Theorem 5.1 that provides convergence proofs, the learning rate eta_exact has a dependence on 1/beta, which means much smaller learning rates should be used for the proposed method. However, in the experiments it seems that the same learning rate is used for all methods. This seems to trouble the convergence very clearly as the curves start to fluctuate considerably by increasing for larger betas. There is no bounds on beta which in practice can force us to use orders of magnitude smaller learning rates.
- Section 4.3 aims at linking hard negative mining to the proposed method. What they actually do is propose a new definition for hard-negative mining which is satisfied by the proposed method. There is little basis for suggesting this definition. There are myriads of work on hard-negative mining and suggesting a new definition needs a more thorough study of related works.
- Section A.1.1 argues we would stop ERM when it plateaus, but it doesn't look like it has plateaued in fig 2 left.
- Section A.3, I'm not sure lr=1 would be stable wide resnet. Maybe there is a problem with the experimental setting.
- There is such much non-crucial details in the main body that increased the main text to 10 pages. At least 2 pages could be saved by moving details of theorems and convergence results to the appendix.

After rebuttal:
I'm keeping more score. The manuscript has been improved quite a lot.  My main concern remains the experiments. Both texts and mathematical statements still need more edits.

The authors have completely removed experiments on cifar10. Paper now has only one set of experiments on MNIST with little ablation study. I still think my suggested ablation study is interesting. As a minimal sanity check, I'd like to see the performance of DRO on the original MNIST dataset. Basically, how much do we lose by using a robust method on a balanced dataset? Even with full ablation studies, I don't think MNIST is not enough for testing methods based on hard-negative mining.
review_title: Official Blind Review #4

Meta-review: This paper proposes a modification of SGD to do distributionally-robust optimization of deep networks.  The main idea is sensible enough, however, the inadequate handling of baselines and relatively toy nature of the experiments means that this paper needs more work to be accepted.
Decision: Reject