Optimal algorithms for group distributionally robust optimization and beyond

Theoretical results: while the theoretical results are interesting, they seem to be poorly presented. Their novelty is questionable as well. Details are below.

• Section 1 mentions that the most challenging part of the algorithm design is balancing the variance of the gradient estimators and the diameter. However, throughout the paper I could not find any part that explicitly deals with this variance. Does this "most challenging part" essentially boil down to tuning the learning rate $\eta_{\theta,t}$ based on $G, D, m$ and $t$?
• The results are reported in the expectation of the optimality gap, but the main paper never mentions what the expectation is over. It is in fact crucial to be specific early on what the expectation is over, because in the two-player zero-sum game, one player is an adaptive adversary to the other player, so the expected regret and pseudo-regret of the players have different interpretations.
• There are two different notions of optimality gap: $\epsilon_T$ and $\epsilon_T(q^*)$, however it was not discussed which one is more suitable and/or significant for GDRO. In particular, it is not clear which notion the lower bound in Theorem 5 applies to.
• The paper claims that by definition $\epsilon_T(q^*) \leq \epsilon_T$ for any $q^* \in Q$. This seems non-trivial and needs further clarification, because $\max_{q \in Q}L({\bar{\theta}}, q) \geq L({\bar{\theta}}, q)$ but $\max_{q \in Q}L(\theta^*, q) \geq L(\theta^*, q^*)$, so it is not immediate why $\max_{q \in Q}L({\bar{\theta}}, q) - \max_{q \in Q}L(\theta^*, q) \geq L({\bar{\theta}}, q^*) - L(\theta^*, q^*)$?
• Is the result of Theorem 2 really novel compared to the work of [2]? I know [2] uses EXP3-IX instead of EXP3.P, but they are just two different ways to get a high-probability regret bound for adversarial bandits.

[2] Stochastic Approximation Approaches to Group Distributionally Robust Optimization. Zhang et al. 2023.

Experiments:

• The number of groups in the majority of the experiments, including the one reported in the main paper, is less than 10. This is too small given that the point of the experiments was to show the improvement from $O(m\sqrt{\dots})$ to $O(\sqrt{m}\sqrt{\dots})$. Is there any inherent difficulty to run the experiments on a synthetic dataset with large $m$, say $m \in [1000, 5000]$?

• Even in the one experiment with $m = 100$ (Figure 2 in the appendix), at $T = 10^6$ the objective value of Sagawa et al. (the green line) is smaller than that of GDRO-INF, so I do not find the empirical evidence convincing. Can the authors comment on this?

Minor:

• Page 5: "In o" is not a sentence.
• Algorithm 1: the definition of the Bregman divergence is incorrect. The dot product should have $\nabla \Psi(y)$, not $\nabla \Psi(x)$.
• Theorem 1: What is $\mathbb{E}_{i_t}$? Again, this is the issue with unclear definition of the expectation.
• Throughout the proofs in the appendix, the paper makes use of existing results in Appendix A.1 that were stated for deterministic setting in which the actual gradients are available. However, in GDRO we only have the stochastic gradients, so it is important to be explicit on why the lemmas in A.1 were applied straightforwardly in the proofs.

See below.

1. The proposed algorithms seem simple and straightforward. It seems that the algorithm follows the structure of OMD and other existing online learning methods. It would be better if the authors could highlight the challenge and the novelty of the analyses.

2. The authors should discuss and compare more about other works of Group DRO, such as "On-demand sampling: Learning optimally from multiple distributions"