Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies distributionally robust optimization, with a SGD method and sampling without replacement for the inner problem. 
main_review: The paper is well-written, clearly organized and easy to follow. The results seem to be correct though I didn't check all the proof details. The convergence analysis using sampling without replacement is novel and interesting, which is also more practical and efficient. Therefore I incline to accept the paper.

1. Can the author add more explanations to what is exactly the total computational effort? And how taking a small $\nu$ decreases computational effort.
2. Since $M_{t}$ are integers, it's not clear to me what does it mean by saying $\nu$ is a constant (it might be more problematic when $\nu \to 1+$). Can the author explain more?
3. The convergence rate $O(1/\epsilon)$ seems asymptotic in terms of $\nu$. Is it possible to derive this rate for a fixed $\nu$, with possibly rebooting sampling?)
limitations_and_societal_impact: The $O(1/\epsilon)$ convergence rate is asymptotic.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies a stochastic gradient descent algorithm to solve DRO problems with phi-divergence based ambiguity set, where the gradient estimate is computed from an increasing mini-batch size. The proposed algorithm is then tested numerically to demonstrate its efficiency.
main_review: The paper makes valuable contributions, and the numerical section is extensive. A few comments about the paper:

- The authors develops an efficient algorithm to solve DRO problem. However, it is unclear to me why the proposed approach leads to better generalizations. I am a bit confused because different algorithms solving the same DRO problem should not give different results or lower misclassification error. 

- How does Table 1 change if the misclassification error is replaced with averaged logloss on test samples?

- What is the stopping criteria for all algorithms reported in Table 1?
limitations_and_societal_impact: By moving procedure 1 to the main text and having a more in-depth literature review, the authors could improve the readability of the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develop and analyze an efficient double-loop-based stochastic algorithms for solving DRO problems. 
main_review: This paper is mainly an extension of Namkoong and Duchi [21]. The authors utilize Danskin's theorem to ensure the existence and form of subgradient of the inner function, thus can avoid solving the min-max problem directly. As the algorithm scheme mimics "bilevel optimization", the author significantly reduces the expense of solving the inner maximization over the full training dataset by subsampling technique in the iterates of the algorithm and estimating the robust loss via a sample average approximation. Moreover, the authors can control the inherent bias from the subsampling by progressively increasing the subsample size with the iterates up to the maximum size N. This doubling trick has been widely used in the stochastic second-order methods, which is nothing new and in expection. 


Overall, the paper is well-written and easy to follow. However, the author didn't submit the supplementary material. Thus, I cannot check the correctness of the technical results and quantify the technical contributions. 
limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper gives a new method for solving the distributed robust learning problem. The new method uses a subsampling technique for the inner maximization problem which lead to faster convergence. The paper also demonstrates the effectiveness of the new method in practical settings. The reviewers have raised several concerns initially about novelty and theoretical guarantees, but they were addressed in the response period. Now the reviewers believe that the paper is technically sound and the empirical results are convincing.
Decision: Accept (Poster)