We thank the reviewer for raising great points regarding the practicality of our $(\lambda, \beta)$-sparsity definition.

While we acknowledge that our Definition 2.3 requires a strong condition that a non-trivial $(\lambda, \beta)$-sparsity holds globally for all $\theta \in \Theta$, we would like to explain why our work is an important step towards studying the more practical setting in which the $(\lambda, \beta)$-sparsity condition may hold locally in a neighborhood around the optimal $\theta^*$.

• From a practical perspective, our experimental results show that our algorithms, which are developed for the global $(\lambda, \beta)$-sparsity condition, works really well on the real-life Adult dataset where the $(\lambda, \beta)$-sparsity condition holds only locally. This is partially explained in our Equation 27, where we bound the regret of the max-player by the average size of dominant sets $\bar{\beta}\_T = \frac{1}{T}\sum\_{t=1}^T \beta\_t$. This indicates if the sequence of $(\theta\_t)\_t$ in an algorithm converges sufficiently quickly to a neighborhood of $\theta^*$, then the majority of the dominant sets will have small sizes. This turns out to be true for our algorithms as empirically verified in our Figure 2 (left).
• From a theoretical perspective, in order to prove mathematical statements about the performance of an algorithm on the local version of $(\lambda, \beta)$, there must be some robust mechanism to control how quickly the sequence of $(\theta_t)_t$ converges to a neighborhood of $\theta^*$. This requires developing a high-probability last-iterate guarantee for stochastic saddle-point optimization, which is a fundamental problem in optimization. To the best of our knowledge, there are no existing works on this problem that are applicable to our GDRO setting without further (strong) assumptions (e.g. strong convexity). Even with strong convexity, the best known rates of convergence are poor. Without strong convexity, to our knowledge nothing is known. We are excited about future progress on this question, but we emphasize that it would be a major undertaking in its own right.
• In our response to Reviewer K8N8, we proved that $(\lambda, \beta)$-sparsity condition holds globally at every $\theta \in \Theta$ for the problem of linear regression with a linear Gaussian model.
  Together with the examples in our paper, this additional theoretical result further strongly motivate the global version of the $(\lambda, \beta)$-sparsity condition in our work.

We thank the reviewer for their time on our paper. Please let us know if you have any questions.

We thank the reviewer for their critical feedback. Please find our clarifications to your concerns below.

1. The techniques in Algo 1 looks relatively straightforward

We understand that the algorithm may look straightforward because it takes in a given $\lambda$ and thus can focus solely on computing the dominant sets. Even so, we emphasize that the analysis of Algorithm 1 is highly non-trivial as it requires developing two new techniques: one is a high-probability anytime bound for sleeping bandits, and one is a high-probability anytime correctness for the computation of the dominant sets. These two new techniques are then combined by our Lemma 3.3, which is a new result showing that the high-probability sleeping bandits bound based on stochastically sampled losses also implies a regret bound based on the (hidden) expected losses. These new results and their proof techniques are highly nontrivial.

We also point out that Algorithm 1 and its result are only the first of our five main results. In particular, the adaptive algorithms (and their analyses) were major theoretical undertakings. For example, the theory behind Theorem 4.1 required us to put forth new ideas (for space, in the appendix, although there is a brief sketch in Section 4.1), and this result itself was highly surprising to us as we originally were trying to prove a lower bound that shows such adaptivity was impossible.

2. The sparsity definition lacks justification

While we acknowledge that our Definition 2.3 requires a strong condition that a non-trivial $(\lambda, \beta)$-sparsity holds globally for all $\theta \in \Theta$, we would like to explain why our work is an important step towards studying the more practical setting in which the $(\lambda, \beta)$-sparsity condition may hold locally in a neighborhood around the optimal $\theta^*$.

• From a practical perspective, our experimental results show that our algorithms, which are developed for the global $(\lambda, \beta)$-sparsity condition, works really well on a real-world dataset where the $(\lambda, \beta)$-sparsity condition holds only locally. This is partially explained in our Equation 27, where we bound the regret of the max-player by the average size of dominant sets $\bar{\beta}\_T = \frac{1}{T}\sum\_{t=1}^T \beta\_t$. This indicates if the sequence of $(\theta\_t)\_t$ in an algorithm converges sufficiently quickly to a neighborhood of $\theta^*$, then the majority of the dominant sets will have small sizes. This turns out to be true for our algorithms as empirically verified in our Figure 2 (left).
• From a theoretical perspective, in order to prove mathematical statements about the performance of an algorithm on the local version of $(\lambda, \beta)$, there must be some robust mechanism to control how quickly the sequence of $(\theta_t)_t$ converges to a neighborhood of $\theta^*$. This requires developing a high-probability last-iterate guarantee for stochastic saddle-point optimization, which is a fundamental problem in optimization. To the best of our knowledge, there are no existing works on this problem that are applicable to our GDRO setting without further (strong) assumptions (e.g. strong convexity). Even with strong convexity, the best known rates of convergence are poor. Without strong convexity, to our knowledge nothing is known. We are excited about future progress on this question, but we emphasize that it would be a major undertaking in its own right.
• In our response to Reviewer K8N8, we proved that $(\lambda, \beta)$-sparsity condition holds globally at every $\theta \in \Theta$ for the problem of linear regression with a linear Gaussian model.
  Together with the examples in our paper, this additional theoretical result further strongly motivate the global version of the $(\lambda, \beta)$-sparsity condition in our work.

3. This paper only focuses on the convex GDRO setup.

Without any further assumptions, due to the NP-Hardness of non-convex optimization, a general non-convex GDRO setup would require highly problem-specific assumptions and likely a new definition of robustness as well, both of which are not the focus of our work. In addition, the convex setup still has a number of interesting open problems (see e.g. Zhang et. al. 2023). Therefore, while we agree that ultimately the non-convex GDRO problems (with problem-specific constraints) is of great practical interest, works on convex settings such as ours are important in understanding the optimality and sample efficiency of the GDRO framework.

References

Zhang et. al. 2023. Stochastic approximation approaches to group distributionally robust optimization. NeurIPS 2023.

We thank the reviewer for their feedback and interesting questions, especially the one on $(\lambda, \beta)$-sparsity for linear regression. Please find our answers to your questions below.

1. $(\lambda, \beta)$-sparsity for linear regression with linear Gaussian model.

For the linear Gaussian model mentioned by the reviewer, we will show that a non-trivial $(\lambda, \beta)$-sparsity holds with large $\lambda = 0.5$ and small $\beta = 2$, even for an arbitrarily large number of groups $K$. Moreover, we are able to show this for dimension $n = 1$ (everything can extend to higher dimensions). Before continuing with the construction, let us first mention that our algorithms are adaptive to problems both with and without non-trivial $(\lambda, \beta)$-sparsity; therefore, if a problem does not have any non-trivial sparsity, our algorithms will automatically recover the best known worst-case bounds.

We now show our construction. For any group $j$:

• we assume $X \sim \mathcal{N}(\mu_j, I)$, as suggested by the reviewer;
• for $Y$, we assume $Y \sim \mathcal{N}(\langle \theta^*_j, X \rangle, 1)$.

We quickly clarify an important point about the conditional distribution of $Y$ given $X$. While the reviewer may have suggested $Y \sim \mathcal{N}(\langle \mu, X \rangle, 1)$ for all groups $j$, we note that this would imply all groups share a common minimizer, in which case the problem instance is not suited to GDRO (because there is no robustness issue, i.e., minimizing the maximum risk over groups becomes the same as minimizing the risk of any individual group).

Next, taking $K = 3$ and $n = 1$, we show a choice of the $\mu_j$'s and $\theta^*_j$'s for which $(\lambda = 0.5, \beta = 2)$-sparsity holds. We set the parameter space $\Theta = [-1, 1]$. Next, we take $\mu_j = 0$ for all $j$ and set $\theta^*_1 = -1$, $\theta^*_2 = 1$, and $\theta^*_3 = 0$. The model is well-specified since all $\theta_j^*$ are in $\Theta$. Using squared loss, straightforward calculations show that for any $\theta \in \Theta$, its risks on groups 1, 2, and 3 are $R_1(\theta) = (\theta+1)^2 + 1$, $R_2(\theta) = (\theta - 1)^2 + 1$, and $R_3(\theta) = \theta^2 + 1$, respectively. One can easily show that $\max\\{R_1(\theta), R_2(\theta) \\} - R_3(\theta) \geq 1$ holds for all $\theta \in \Theta$. This immediately implies that this GDRO instance is $(0.5, 2)$-sparse, and the $0.5$-dominant set is either {1}, {2} or {1, 2}.

To extend to $K \geq 4$, for $j \geq 4$, we take $\mu_j = 0$ and let $\theta^*_j$ be slightly perturbed from $\theta^*_3$ so that all these groups' risks are always dominated by (the maximum of) groups 1 and 2 with a margin of 1. As a result, it still is the case that $(0.5, 2)$-sparsity holds.

2. Why can the algorithm choose the distribution to sample from?

Our approach, as well as other recent approaches to the GDRO problem that also employ adaptive sampling, is a form of active learning where in each round, the algorithm adaptively decides from which group it will obtain a sample. Theoretically, we show that one can have massive gains in sample complexity via an adaptive approach. For the question on when and why the algorithm designer would be able to actively sample, we point to a popular example from the well-cited paper of Sagawa et al. (2020): when training deep neural networks on unbalanced datasets, it is beneficial to feed a network samples from classes on which the network is struggling the most. Another example would be when a company has a fixed budget for data collection and wants to spend this budget the most efficiently. If groups are visible (for example, collecting samples in different geographic regions, each of which corresponds to a different group), then adaptive sampling as we do here is viable and sensible from a cost standpoint.

3. Intuition on the players' regret bounds and sample complexity.

Intuitively, small regret bounds of the two players imply a small bound on the optimality gap of the final output $\bar{\theta}_T$. The regret bounds of the two players depend on the number of rounds $T$ of the game. Since our algorithm collects one sample in each round of the two-player zero-sum game, the number of rounds $T$ of the game is equal to the number of samples collected for the game.

4. Is it possible to use some kind of meta-algorithm?

Without prior knowledge of $\lambda$, we believe it is not possible to use some meta-algorithm to achieve the same near-optimal sample complexity as our results. By running multiple instances of the same algorithm with different $\lambda$, the total sample complexity will always be dominated by the instance with the smallest $\lambda$. Without a procedure to lower bound the smallest value of $\lambda$ like our Algorithms 8 and 9, any meta-algorithm would end up using a $\lambda$ far below $\lambda^*$, thus incurring a much higher sample complexity.

References

Sagawa et. al., 2020. Distributionally robust neural networks. ICLR 2020