Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies a generalized notion of distributionally robust optimization (DRO). In particular, the mixing weights for different data distributions ($m$ groups) can belong to arbitrary subsets $Q$ of the simplex $\Delta_m$ as long as $Q$ also contains uniform mixing weights $\frac{1}{M}\cdot \mathbb{1}$. Thus, popular DRO objectives such as group-DRO, etc., are special cases of this objective. 

The paper casts this objective as a two-player game and uses stochastic gradient methods to obtain convergence guarantees for the optimality gap. The players' algorithms are simple online gradient and mirror descent algorithms with appropriate regularization. For the particular case of group-DRO, their rates improve upon the best-known rate by $\sqrt{m}$. The paper also presents a novel lower bound, showing that their algorithm has an optimal convergence under their assumptions.  
strengths_and_weaknesses: I like the presentation of the paper: discussion of the related work and their connections in section two, review of current convergence rates, and discussion of algorithm design and results. The result is clean and also shown to be optimal for group DRO. 

My main concern is that the algorithmic insight here is just casting the objective as a two-player game and using the correct regularizer for OMD. On the one hand, the simplicity is excellent (and OCO theory itself is known to be clean and simple), but on the other, I feel that the techniques and analysis used are not novel. This is apparent in the proof of the upper bounds, which immediately follow from known convergence lemmas. The lower bound is more interesting, and the analysis idea looks more novel. This is why I give the paper a weak acceptance. 
questions: 1) The authors use mini-batching in the experiments, but the theory doesn't have any mini-batching. I would guess that under the assumptions of $G$-lipschitzness and compact parameter space, it is hard to show such a benefit theoretically? If this is true, could some other assumptions show an improvement (such as smooth, non-Lipschitz functions)? I understand this might is a more fundamental question for online convex optimization.

2)  I believe a much more extensive empirical evaluation is possible here, particularly on data sets widely used in the fairness/robustness community. Since the theoretical results are not very hard to attain and are positive, it would be good to see that the simple algorithms outperform known algorithms on a broad range of tasks. It would also be good to see these experiments on data sets where the general objective proposed in the paper makes more sense than group DRO, etc.  
limitations: No apparent negative societal impacts.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper the authors introduce new algorithms to solve a set of DRO problems consisting of Group DRO, Empirical CVar and Weighted Ranking problems. Their algorithms treats the problems as a two player game between players of the minimization and maximization problems. They leverage Online Gradient Descent and Online mirror descent for each of these respectively.  
They also develop DRO instances which show a lower bound the queries required for objective performance. The bound the best possible performance of any algorithm for the Group DRO problem. 

strengths_and_weaknesses: Originality: I feel the paper is original as it provides new and innovative algorithms for existing problems. 

Quality: I feel the paper is technically sound. The novel algorithms provided in the paper improve upon existing methods and these aspects are illustrated through theoretical and numerical results. However, I feel that the numerical section is quite limited with only 1 real data set. Expanding this section will significantly improve the quality of the paper. 

Clarity: I think the paper is well written and clearly communicates the various assumptions, results, numerical experiments etc. 

Significance: I feel the paper is important as it takes a step forward in solve practical DRO problems by identifying new algorithms for the DRO problems. 
questions: What is the evaluation of the methods of this paper on other real world data sets. 
What is the comparison to other methods to solve DRO problems beyond those introduced in Sagawa et al. 
What are practical applications of the Group DRO, Empirical CVaR and other mentioned problems. How is the performance of the algorithm on the real world instances of these problems. 
limitations: The authors do not discuss any limitations of their work. Though I doubt the existence of negative societal impact, it would be interesting to see any differences in the solutions obtained by their method as compared to Sagawa. Do this focus on different aspects etc.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a general class of DRO that includes Group DRO, subpopulation fairness, empirical conditional value at risk optimization and others, and the stochastic gradient learning algorithms under these frameworks. As the convergence rates shown in the previous studies are improved, the proposed algorithms are efficient, and especially, it is theoretically shown that the optimal convergence rate is achieved under the Group DRO framework. This allows to superior performance over a baseline in the Adult and synthetic datasets, which are aligned with theoretical results.
strengths_and_weaknesses: [Strengths]
* This paper is clearly written in overall.
* It is interesting to combine online learning algorithms and appropriate gradient estimators in the scenario, where the group distributions are given by the stochastic oracles.
* It differs from previous studies in that it derives algorithms and theoretical results for online learning scenarios with stochastic functions.
* The introduction of the weighted ranking of group losses (general DRO) seems natural after Group DRO and empirical CVaR optimization.
* This paper shows several theoretical results including improvement of convergence rate compared to existing studies through the proposed algorithms and corresponding convergence analysis.

[Weaknesses]
* Compared to the theoretical results, experimental analysis and setting seem to be insufficient. (e.g., Accuracy, the number of random seeds, corresponding standard deviations can also be reported in the Appendix.)
* Line 129: ‘p=m/k’ → ‘p=k/m’
questions: * Due to its methodological simplicity, it seems that the proposed algorithms have the advantage of being applicable to a variety of datasets.
* The background for adopting the synthetic dataset was to confirm the performance of the proposed algorithm in the high-dimensional model scenario. For the readers, it seems better to utilize natural network architectures rather than only linear models. (e.g., [1] used ResNet50 for image datasets and BERT for language dataset.)
* The introduction of oracle makes a difference in terms of the setting in consideration from the existing methods, so it would be good to add a discussion on this.

[1]: (Sagawa et al.) Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization.
limitations: Limitations (e.g., some consideration in practice) are not specified, as mentioned in the checklist.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes an algorithm for a two-player zero-sum game based on stochastic no-regret dynamics which achieves a faster convergence rate than existing algorithms for group DRO problems. They further show that their bound is tight for group DRO. 

strengths_and_weaknesses: The paper is well-written.

The idea seems original, however, I am not entirely sure if there is an algorithm in the multi-arm bandits that has the same convergence rate. If not this result can be seen as a contribution to the two-player stochastic online learning problems. 
I highlight the need for a comprehensive literature review. Please see my comments below.

I appreciate that the authors put a separate section about the algorithm that is the most related to their work and provide a simple proof for the convergence of the competitive algorithm. 


questions: # Major Comments

1) Throughout the paper formulation of "distributionally robust optimization" and "group distributionally robust optimization" terms are used interchangeably, which I find very confusing.
For example, in Line 21, the reference to general DRO problems is not precise. This paper studies the general formulation of group DRO problems because the problem introduced in (1) is already a group distributionally robust optimization problem, which is different from than traditionally studied distributionally robust optimization problem.
A similar problem occurs in Line 148, Line 143, in the title of  Algorithm 1, and so on.

To avoid confusion, the problem formulated in (1) could be called a general formulation for group distributionally robust optimization. 

2) I am not entirely sure why $q_t$ is removed from the objective in the gradient update of $\theta_t$.
Is it common to apply such a technique in two-player games?
I am not sure if the unbiasedness of the gradient estimates goes through in that case.

3) I do not think the related literature for online stochastic games is covered fully. I suggest the authors to extend this part. 


4) It is not clear what is $f$ in Section A.1.

5) I cannot follow the correctness of proofs because of a couple of reasons.
		- I could not see proofs for Lemma 1, 2, 3, and 4. If these lemmas are proved in a reference, please indicate them. 
		- The proofs of the theorems are dependent on these lemmas.  

## Minor Comments: 

1) The sentence in Line 125 is neither rigorous nor clear. Please clarify this sentence.

limitations: The authors did not study the limitations of their work.
review_title: null

Meta-review: metareview: The main criticism raised by the reviewers was the unconvincing experiments. The reviewers generally liked the simplicity of the method presented the paper, but were unconvinced by the impact/utility of the results. Even though the paper focuses on the convex regime, the paper may benefit from some DL experiments. This is not an uncommon paradigm in research (e.g. Adam and other convex optimization methods with DL experiments, etc.) 

There were some other comments that are worth addressing in a future version of the paper. (e.g. adding the discussion mini-batching, improved exposition).




confidence: Certain
Decision: Reject