Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Authors: Quan M. Nguyen
Nishant A Mehta
Cristóbal A Guzmán
Venue: ICML 2025 poster (2025)
Keywords: group distributionally robust optimization
two-player zero-sum games
non-oblivious multi-armed bandits
online convex optimization
Primary area: theory->online_learning_and_bandits
TL;DR: Using adversarial sleeping bandits, we reduce the dependency on K from K*ln(K) to beta*ln(K) in the sample complexity of GDRO problems.

Abstract: The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a $\log(K)$ factor, where $K$ is the number of groups. In this work, we venture beyond the minimax perspective via a novel notion of sparsity that we call $(\lambda, \beta)$-sparsity. In short, this condition means that at any parameter $\theta$, there is a set of at most $\beta$ groups whose risks at $\theta$ are all at least $\lambda$ larger than the risks of the other groups. To find an $\epsilon$-optimal $\theta$, we show via a novel algorithm and analysis that the $\epsilon$-dependent term in the sample complexity can swap a linear dependence on $K$ for a linear dependence on the potentially much smaller $\beta$. 
This improvement leverages recent progress in sleeping bandits, showing a fundamental connection between the two-player zero-sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. 
We next show an adaptive algorithm which, up to logarithmic factors, obtains a sample complexity bound that adapts to the best $(\lambda, \beta)$-sparsity condition that holds. 
We also show how to obtain a dimension-free semi-adaptive sample complexity bound with a computationally efficient method.
Finally, we demonstrate the practicality of the $(\lambda, \beta)$-sparsity condition and the improved sample efficiency of our algorithms on both synthetic and real-life datasets.

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Quan Nguyen Nishant A. Mehta
Cristóbal Guzmán"
Abstract
important goals in building machine learning models (Ben- Tal et al., 2013; Williamson & Menon, 2019; Sagawa et al., 2020). These goals are especially important for models mak- ing decisions that could have socictal and safety impacts. A recently proposed framework for achieving these goals is the group distributionally robust optimization (GDRO) frame- work, in which a learner aims to find a single hypothesis that minimizes the maximum risk over finite number of data distributions. This minimax objective is often considered in the context of faimess (Rawls, 197 1; Williamson & Menon, 2019; Abernethy et al., 2022) when the distributions repre- sent different demographic groups, or as a means to promote robustness when they represent possible shifts in the data distribution (Mohri al., 2019; Sagawa et al., 2020).
The minimax sample complexity of group distri- butionally robust optimization (GDRO) has been determined up to a log(K) (K) factor, where K is the number of groups. In this work, we venture be- yond the minimax perspective via a novel notion of sparsity that we call (A, -ssparsit In short, this condition means that at any parameter 9, there is set of at most 33 groups whose risks at are all at least À larger than the risks of the other groups. To find an e-optimal 0, we show via novel algo- rithm and analysis that the e-dependent term in the sample complexity can swap a linear dependence on K for linear dependence on the potentially much smaller /3. This improvement leverages re- cent progress in sleeping bandits, showing a fun- damental connection between the two-player zero- sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. We next show an adaptive algorithm which, up to logarithmic factors, obtains a sample complexity bound that adapts to the best (X, 9)) -sparsiiy con- dition that holds. We also show how to obtain a dimension-free semi-adaptive sample complexity bound with a computationally efficient method. Finally, we demonstrate the practicality of the (A, B) -spariiiyyy condition and the improved sam- ple efficiency of our algorithms on both synthetic and real-life datasets.
More formally, given n-dimensional hypothesis set O and group of K distributions P., the learner aims to solve the optimization mingge ma. K) R2 (0), where (,) is the risk of the learner with respect to P.. Intuitively. this objective encourages the learner to find a model with good balance in performance with respect to finite number of distributions of data, and avoid models that might perform extremely well on one distribution but have significantly worse performance on others. The GDRO framework as- sumes that the learner has access to a sampling oracle, which returns an i.i.d sample from Pa upon receiving a request E [K]. The sample complexity of the learner is the number of samples needed to find an cooptimal hypothesis 0 such that the optimality gap max; (2( -max; R0*))) is smaller than a target value e, where 0* is an optimal hypothesis.
Throughout the paper, the Ô notation hides logarithmic factors. Existing works (Soma et al., 2022; Zhang et al., 2023) have shown a sample complexity lower bound of or- der Ω @ and a near- mear-matching Ô ( worst- case upper bound, where D is the la diameter of θ and G is the Lipschitz constant of the loss function. While these existing results are useful for understanding worst-case see- narios, practical problems may have additional structure that allows for significantly lower sample complexity. partic- ular, the 22 (² lower bound construction in (Soma et al., 2022) relies on having arbitrarily small gaps (i.e., difference risks) between groups for all E O. This property rarely holds in practice, where most hypotheses
1. Introduction
Performing well across different data subpopulations and be- ing robust to distribution- shift in testing are two of the most
'Department of Computer Science, University of Victoria, Canada "Institute for Mathematical and Computational Engineer- ing, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile. Correspondence to: Quan Nguyen <manhquan233 gmail.com>.
2²
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
can have significant gaps between groups. For example, in car manufacturing, each car model often has noticeably different effects on different surfaces and road conditions.
the time-varying subsets of arms for the max-player is based on a uniform convergence bound for O that uses Ô K2) X samples. The first bound is obtained by an al- gorithm called SB-GDRO that takes À as input and out- puts an c-optimal hypothesis using Ô samples. Letting X be the À that minimizes the sam- ple complexity bound of SB-GDRO, natural question is whether it is possible to nearly obtain this minimum sam- ple complexity without knowing A². Surprisingly, in Sec- tion 4 we show that such adaptivity is possible. A disad- vantage of the fully-adaptive approach is that it is com- putationally expensive due to the explicit computation of covers of the potentially high-dimensional set O. In Sec- tion 4.2, we partially resolve this by proposing a computa- tionally efficient semi-adaptiv algorithm achieving another dimension -inreeiinnnde Ó DPG² +max (K),6)61)))) bound in figh-precision settings where 6 A*
1.1. Contributions and Techniques
0 [nn X2 + +²
We transcend the established minimax bounds by consid- ering problem instances with additional structure. We for- mally define such a structure called (A, -s-spasitty in Sec- tion 2.1. The main idea of (>, B)-sarsstt is that for all 0, the groups can be divided into two sets: one contains groups with large risks and the other contains groups with small risks. The parameter À specifies the disk-difference between these two sets of groups, while B specifies the number of groups with large risks. Let Bx denote the small- est 33 for which (A, -sparstty holds. For problem with (A, -s-spasity we show that the dependence on K in the leading term (here and throughout, the term for which 1/c of the highest order) can be reduced from O(K In K) to O33x In K). Table 1 summarizes our main results, which consist of three high-probability upper bounds and lower bound. The leading terms in the upper bounds grow with Ô +** instead of Ô (DC where 3x could be much smaller than K.! To the best of our knowledge, these are the first bounds that go beyond the established min- imax bound in (Soma et al., 2022; Zhang et al., 2023). The near-matching lower bound is of order ? D2 gen- eralizing the minimax lower bound in (Soma et al., 2022).
For the dimension-free bound, we use the Lipschitzness of the loss function and the stability properties in the strategy of the min-player to compute the time-varying active arms using Ô BAKG//DGG-- KDG)
samples. This leads
to a dimension-free bound that is potentially much smaller than the dimension-depenndent bounds when is large.
In Section 6, we present experimental results showing that not only this (A, B)--pasiityy condition holds for high- dimensional practical setting around the optimal hypothesis 0*, but also our algorithms can efficiently (in both sample and computational complexity) compute an estimate of X* and leverage it to find c-optimal hypotheses with signifi- cantly fewer samples compared to baseline methods.
2²
Technically, our results are based on improving the sample complexity of the two-player zero-sum game framework for GDRO (Nemirovski et al., 2009; Zhang et al., 2023). In this framework, game is played repeatedly as follows: in round the first player (the min-player) plays hypothesis 0g E θ and the second player (the max- max-player) plays group index ie E [K] and draws a sample from distribution P.,,- For the max-player, choosing one of K groups and getting an i.i.d sample from that group is similar to pulling one of K arms and getting feedback from that arm in a multi-armed bandit problem. While existing works (Soma et al., 2022; Zhang et al., 2023) use a fixed set of K arms in every round for the max- playpr to choose from, the (X, spp-ssrttttyyy condition al- lows us to use a smaller, time-varying subset of active arms of size at most B. To handle this time-varying action set, we use the sleeping bandits framework (Kleinberg et al., 2010) to model the learning process of the max-player. Critically, recent progress (Nguyen & Mehta, 2024) in bounding the
1.2. Related Works
We consider the GDRO problem where the loss function is real-valued in [0, 1J and the hypothesis space θ is convex and compact. In this setting, (Nemirovski et al., 2009)² con- verts GDRO to a stochastic saddle point problem and uses stochastic mirror descent methods with O K D² +ln(K)) sample complexity guarantee. (Sagawa al., 2020) adopts the two-player convex-concave game framework from the deterministic min-max optimization literature (Freund & Schapire, 1999; Cesa-Bianchh & Lugosi, 2006) to obtain K3 (2 sample complexity bound, which 2²
was improved to Ō D kK((k) by (Zhang et al., 2023)
e
per-action regret in sleeping bandits (details in Section 3.2) enables to reduce the max player's regret bound and im- prove the dependency on the number of groups from K In K to 3 In Ki in the leading term of the sample complexity.
by refining the approach. An Ω
G²D²+K) information- 2²
theoretic lower bound was shown in (Soma al., 2022).
A related, more constrained setting is the class of multi-
For the dimension-dependeee bounds, the computation of
(Nemirovski et al., 2009) do not impose the bounded loss as- sumption, although (Zhang et al., 2023) do adopt this assumption.
Seee Table for full results.
2

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Table Summary main results. Ā-adapt indicates if bound is adaptive to the hest X possible. Dimension-free indicates whether the hound depends the dimension of e. 5 is the failure probability.
Upper and Lower Bounds
X-adapt?
Dimension-free?
Kn knln( GDK)
(G D2 +Px)+
(Theorem 3.4)
Knin CDK) (A7)²
(G BD (n(
In (t) (Theorem 4.1)
X
DKGV (D* (DDGG + [B[K)66]u In
KDG 138
(D'G +
(Theorem 5.1)
X
x
(D2G2+ (aaa(aa()))aall) (1111//
(Theorem 4.2)
D2G 2
Ω
(Theorem 3.5)
distribution binary classification problems in which has finite VC-dimension d (Haghtalab et al., 2022; Awasthi et al., 2023). Recent works have established tight minimax sample complexity bounds of order K+K for this setting (Zhang et al., 2024; Peng, 2024). Multi-distribution learning with multi-label prediction with offline data was recently ex- plored in (Jang et al., 2024). We refer interested readers to (Haghtalab al., 2022; Zhang et al., 2024) for more comprehensive discussion of related works in min-max fair- ness and federated learning settings.
returns an i.i.d sample the sample complexity of a learner is the number of samples to find c-optimal hypothesis @ such that crr(0)
P. Given a target optimality e,
2.1. (A, 3) JSparssiyyy Structure
First, formally define the notion of X-dominant set.
Definition 2.2. For any À E [0, 1] and 0 E O non-empty set of groups S C [K] is X-dominant at 0 if for all j & S,
min (2(0) Z R2(0) + iES
(2)
2. Problem Setup
Let θ C R" be a compact convex set of hypotheses, Z a sample space and θ 2 + [0, 1] be loss function measuring the performance of hypothesis on data point. Similar previous works in GDRO (Sagawa et al., 2020; Haghtalab et al., 2022), use the following assumption.
Note that S = [K] is dominant set, as there is no in the empty set [K] \ S such that (0) + À > minge[K] (f).
Next, we introduce (A, ()sparstr,,,,t,, our novel condition for GDRO problems.
Assumption 2.1. The diameter of θ is bounded as ||0]| S D for all 0 E O. The loss function E is convex and G- Lipschitz in the first argument, i.e., [e(0,-) E(0',)) x Gil0- 0'112 for all 0,0' 0' E e.
Definition 2.3. For À > 0 | [1, K], a GDRO problem is (A, 3s-arse if for all 0 E O, there exists X-dominant set whose size is at most j3. If A > 0 and 8 < K, we say that (A, 3) is nontrivial.
There are K groups, each associated with distribution (P.)..=.....K over Z. Let [K] f1. K}. Let R2(0) = P, [((0,)) =]] be the risk of 0 with respect to group i. The worst-case risk of a hypothesis 0 is measured by its maximum risk over these distributions:
By definition, a GDRO instance can be (A, B--sraee for multiple (>, B). For example, (0.2, 10)-sparse problem with K = 20 is also (0.2, 11) and (0.1, 10)-sperse. Simi- larly, there can be multiple X-dominant sets at each A. Let Sx,9 be the collection of all X-dominant sets at 0. Since [K] is always a X-dominant set, this collection always contains [K] Let Br,8 = minsess, |S| be the size of the smallest dominant set
(())= = max (0)-
=E[K]
θ Then, we have 3x = maxxee 3x,9 is the smallest value of 3 such that (A, -ssarsstyy holds. Moreover, all GDRO instances which case the 0-dominant set contains one of the groups with maximum expected loss. If (X, B)-sprsitty holds for nontrivial (A, 3), then for every model, there a prominent gap in the outcome (i.e., risks) of applying that model across different groups
The objective is find a hypothesis 6" with minimum L(0):
trivially (0, 1)-sparse, in
8t arg min L(0) arg min max (,))).
(1)
DEG
JEB
(E[K]
The optimality gap of E θ is (+) = ( - L(8").
Similar to previous works, we assume that the learner has access to a sampling oracle that, for every query i E [K].
3

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
2.2. (A, sp-assity for linear regression with linear Gaussian model
et al., 2009), we write the objective function in (1) as
min (()) 0
min max c(0, qq. I gEAx
Figure (Right) illustrates the mathematical plausibility of nontrivial (A, -sparsity in the continuous domain via
The duality gap of 9 E θ and q E Ak is defined as
simple example with θ [o. 1]. In the following, we show that a non-trivial (X, 3)-spariity holds for the problem of lin- ear regression with linear Gaussian model where the number of groups K and the dimensionality n are arbitrarily large. In this problem, each group i E [K] is characterized by two vectors (4;; 0f E IR.. A sample from group by X ~ (N,,, 1) and y ~ -N((0),))) 1).
crr(0, = max (08, q) min Φ(0. g))
geAx
Since ((() 2 @00 for all 0, we have err(0) S err(0, q). To minimize err(O, 7), similar to existing works (Ne- mirovski et al., 2009; Soma et al., 2022), we employ the following two-player zero-sum game approach: a game is run in I" rounds, where in each round, there are two players As and A, corresponding to the min and max operators in the objective function (1). In round t, the min-player Ao first plays a hypothesis 0r, and then the max max-player Ag plays vector qi E ÂK. Then, a random group i, ~ qe is drawn, and the sampling oracle returns a sample Zi,, Pi. The two players compute 0.+1 and q++1 for the next round based on is and Ri,,t- The min- min-player's 's goal is to minimize its regret with respect to the best hypothesis in hindsight:
(X, v) is generated
Next, taking K- = 3 and n = 1, we show a choice of the 11y's and 0s's for which (A- = 0. =2)-sparsity holds. We set the parameter space @ = [-1,1] and use squared loss {(,, :) = (XO- v)². Next, we take 14, = 0 for all j and set 8 = 1, 82 L, and 03- = O. The model is well- specified since all f7 are in G. In Appendix A, we show that for any 0 E O, its risks on groups 1, 2, and 3 are R,(
(0 + 1)² + 1, (0) = (0- - 1)a +1 1. and Rg = - +1, 1, respectively. Moreover, max ( (0), R2
(a (
holds for all 0 E O. This immediately implies that this GDRO instance is (0.5, sspasee, and the 0.5-dominant set either {1), (2). or (1.2).
T
T
RA = Σ ((e. - min ((0,9t).
(3)
lEe t=1
Note that everything extends to higher dimensions n (as higher dimensions only increase the gaps between the groups). To extend to larger K, the idea for j 2 4 is to take Mj = 0 and let the parameter 0 be slightly perturbed from 85 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 the case that (0.5, sysssssitty holds.
The max-player's goal is to minimize its regret with respect to the best weight vector hindsight:
T
T 5l0,, 9) - Σ (lc.))). 1=1
RA, = max
(4)
yEAR
The SB-GDRO algorithm illustrated in Algorithm 1. Be- fore the game starts, SB-GDRO draws set V; of m samples from each group i [K], where is defined in Lemma 3.1. Let V = [Vi.... Vx } be the collection of these sets. The strategies of the two players are as follows:
Next, in Section 3, we begin by presenting algorithm which, for any input À E (0, 1], returns an c-optimal hypoth- esis with sample complexity Ô ( Kn x +
+ For any
24
such X, including trivial choices for which Bx = K, this algorithm (with high probability) provides a valid sample complexity guarantee, but the guarantee is most useful for the unknown, optimal X - call it X that minimizes the sample complexity. The focus of Section 4 is adap- tive algorithms that obtain, without any knowledge of X*, sample complexity whose order is only larger than that of our previous algorithm (were it given X²) by a logarithmic factor.
The min-player As follows the stochastic mirror de- scent framework similar to (Zhang et al., 2023). Specif- ically, given a sample 2i,, ~ Pi, and an existing A,, Ao computes O,1 by
O = arg min Twu (ār, 0.) 110 0.113 BgB
(5)
D is a time-varying learning rate and where Mun GVE
3. Two-Player Zero-Sum Game Approach
Øt Ve(O,, =i,,) is stochastic gradient of Rd (0.). Note that 01 = arg minge ||0||-- We refer to the strategy of the min-player as M nP, whose formal pro- cedure is given in Algorithm 4 in Appendix B.
In this section, we present new algorithm SB-GDRO that, for a given input X E (0, 1]. obtains an O Kum(GDK// X² ity. Let AK be the K dimennsional probability simplex. For any y E Ax, let ()).g) = Σx (0) be the weighted sum of the risks of 0 over K groups Following (Nemirovski
(G +B sample complex-
The max-player A,, uses Og and V to compute a set of "active" groups So.- A group i is active if the empirical risk of 0 with respect to V, sufficiently large. Then, a

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 1 SB-GDRO with known À
Input: Constants K, D. G, X, e, hypothesis set ④ C I="
Draw m (defined in Lemma 3.1) samples from each group into set V
Initialize 0 = arg g ||0|| for each round ( = 1,............... do
Se. Dominant Set (f,, V, V.0.7A) // 0.4X-imminant set at 0g.
Grepp
(t = MaxP (t., So,) // Action of max-player
Goop 2
Draw i, ~ qr. and =i,, Pi.
0++1 = MinP (0,, z,,,)) Action of min-player
Return: = + Ei=1 0
6
Figure 1. (Left) SB 3D-GDRO with known A. (Right) A (A, sp-aase example with K 3, 2.
Algorithm MaxP: the sleeping bandits max-player Pg
Algorithm 3 Domi nant compute dominant set So
Input: Time step > 0, a dominant set Sa, if t = 1 then Initialize 0. = for E [K]
Input: 0, E O, collection of samples V, threshold T 0 Compute (o,) #. プラ E(0,, Vs,s) for E [K] Sort (O.) in decreasing order and let ord(i) be the sorted order of group:
else
Let his,. = 1 E(0,, 21.)) for ,., Compute qt. by Equation (7)
Compute nit(i) by ord(nxt(i)) ord(i) + Let be the first group in ord such that (0,) 2 Ruzu(s) (0:) + T, or -1 if no such groups exist.
S4 P
Return: qe where qi.: = Σイー 11j6 149,
Return: Sq. {i E [K] ord(i) S ord(i) ir -1,
otherwise So. [K].
sleeping bandits algorithm called SB-EXP3 is used to compute a grouppsampliin probability vector q: Ak. where qú,t 0 for i E Se, and qi,t 0 for $ Sa.- We refer to the strategy of the max-player MaxP, whose details are given in Algorithm 2.
empirical risk of with respect to V. To compute a 0.4A- dominant set at 6z, we use the algorithm Dominant (Algorithm 3) which traverses the groups in order of de- creasing (6,)) and returns set Se, of groups up (and including) the first group whose empirical risk exceeds the next group's empirical risk by at least = 0.7A. The fol- lowing lemma shows that if m is sufficiently large, then the set Se, returned by Algorithm 3 is a 0.4))dominant set at 6g whose size does not exceed 8x. This implies that the max-playe max-player only needs to sample the groups in So, in order to maximize the cumulative risks over T rounds.
Compared to existing works (Soma et al., 2022; Zhang et al., 2023; Haghtalab et al., 2022), our two-player zero-sum game procedure has two additional steps: the construction of the collection V and the computation of the set Se.- At the end of round T, the hypothesis 0 = Σi= 0, is returned. As shown (Soma et al., 2022), err(O, g) is bounded by + (RA,, + RA,). The min-player Ag uses a variant of the stochastic online mirror descent algorithm in (Zhang al., 2023) that uses varyyng learning rates instead of fixed learning rates, and obtains the same piebbbbbbayility ODDG / / (n(/5)) regret bound. Our focus is to obtain an improved bound for the max-player Ag with a modified strategy.
384n In 741CDK
With probability at least - 8/2, for any t E [T). Domi nantSet returns a 0. 0.4A-dominant set So, at Or satisfying So. S 3x
Lemma 3.1. Let m
0,01X
3.2. Non-Oblivious Sleeping Bandits
Next, in Section 3.1, we compute the size of V needed to construct the X-dominant sets in each round. Section 3.2 presents the strategy of using V to improve the regret of Ag-
In this section, we discuss the sleeping bandits prob- lem (Kleinberg et al., 2010). Sleeping bandits is a variant of the adversarial multi-armed bandit problem with K arms, where arms can be non-active in each round. Formally, in round = .......T' an adaptive adversary gives the learner a set A,, C [K] of active arms. For each arm i E A,, the adversary also selects a (hidden) loss value h E [0, 1). The learner pulls one active arm é E Pos, observes and in-
3.1. Computing the Dominant Sets
Before the game starts, set of m samples drawn from each of K groups. Let Va, V; be the j-th sample col-
lected from group i. Let (+) m E E(0, Vz.z) be the
5

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
eurs the loss b Let I,, 1 B.). For any a E [K], the per-action regret of the learner with respect arm is the difference in the cumulative loss of the learner and that of arm over the rounds in which a is active:
similar to (Zhang al., 2023), we set h4, = 1 -0(0 21,1) to be the (hidden) stochastic losses of arms for SB-EXP3. A fundamental connection between the two-player zero-sum game approach in GDRO and sleeping bandits is shown in the following lemma, which states that the regret of the max-player RA, is bounded by the per-action regret with Se, being the set of active groups at round t.
Regret(a)
laalbine ha,r).
(6)
Lemma 3.3. With probability at least 1 - 8/2, the regret of the max-player is bounded by
Modified EXP3-IX for sleeping bandits. We use al- gorithm called SB-EXP3 (Nguyen & Mehta, 2024) for sleeping bandits. SB-EXP3 uses the standard IX-loss esti- mate (Neu, 2015) as the loss estimate hi, in round t, i.c., ha.e (im=)) where "/e > 0 is the exploration factor in round For each arm i, over T rounds SB-EXP3 maintains weight vector qt E I defined as
T
RAg S. max KE[K]
Σ
Hii E (R, 6(..
Theorem 3.2 and Lemma 3.3 imply the following sample complexity bound for SB-GDRO.
Theorem 3.4. For any 0,8 (0, 1), with probability
á..1 exp Mud Σ (hi - hio 7s Σ hgge) (7)
1 1- 6, Algorithm 1 has sample complexity
JESo.
(Knn(GDK/0)) @D + Bx) In ln(K/6))
where 17. > O is the learning rate and hiss is the loss estimate of arm in round s. Initially Φi,1 = for E [K]. The sampling probability qi is computed by a filtering step, where inactive arms have qi = and the weights of active arms are normalized as Gi.t = Σズ L.
(8)
X²
e²
In Theorem 3.4, because À is fixed problem-dependent quantity while the required optimality gap can be arbitrar- ily small, the dependency on K in Theorem 3.4 is dominated by O [Ax i ln(K/6) The following lower bound shows that the upper bound in Theorem 3.4 is essentially near-optimal.
15, The following theorem bounds the per-action regret of SB-EXP3.
Theorem 3.2.
With Tg. = 27 =
In(3K/8] SB-EXP3
Eimi [R.1'
guarantees that with probability 5,
Theorem 3.5. For any algorithm A and X 2 0.5, B 3, there exists (2, -Sparse GDRO instance with 0x 8 so that the sample complexity of A is at least Q
(V
T [n(K/6)
max Regret (a) 50 aE(K] K
Σ Ave
D² c²
4. A A--Adaptive Sample Complexity
Our Theorem 3.2 is relatively straightforward but im- portant extension of Nguyen & Mehta (2024. Theorem 3). While the latter requires knowing max( max([A.)). [Ax]]) for tuning " and Yt. we obtain the same bound using adaptive learning rates without knowing anything about future active sets.
Theorem 3.4 suggests that desirable À must be significantly
larger than (so that K x² < {)) but also small enough that B* < K. In this section, we define the notion of an optimal X and present a sample-efficient approach for adapting to this unknown A First, we write the sample complexity in Theorem 3.4 in the form
3.3. Sample Complexity of SB-GDRO
In(K//) (
C X2 x222)
B2 2
D2G² In(K/8)
(9)
In SB-GDRO the max-player uses SB-EXP3 to compute the group-sampling probability qt- For the max- playe,,yer, the set So, in Algorithm is similar to the set A,, in sleeping bandits as the set of "active groups" in round depends on dr, which is decided by a non-oblivious adversary (i.e., the min- player). Furthermore, choosing a group i, qe and then drawing zt,,t ~ P., is mathematically equivalent to having K samples {zi,e ~ P; | i E [K]} (one from each group) but observing only 2i,,-- The hidden stochastic loss of group in round is {(,,, 2, Note that SB-EXP3 is formulated in terms of minimizing losses rather than maximizing gains, so
where C = Kn (npp( ln(K/5) By definition, 83, S Bx for any X S X, and thus + 8x is non-decreasing. Let X be the that minimizes (9). Our goal is to develop sample-efficient method to find X*.
To describe our approach for finding X it will be useful to frame the idea of an optimal more generically. Consider any C > K 2 1 (not necessarily taking the value above), E (0, 1), and in (0, 1). Let g: [0.1] - [1, K] be a
6

---

g(A) Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
nondecreasing function which is unknown. Now, let Xo.g be the minimizer, among all À E [0. 11, of
First Step: Constructing & We first describe a method that, given À E [0. 1] returns estimate A3 for 8x using at most O (ln(k/6) samples. This method constructs a 0.1A
X²
(ODRO) Costc. C.g
(2)
= 12
C + x2
(10)
@ -cover for +, uses Algorithm 3 to compute a 0.4A-
dominant set at each element of the cover, and then returns as its estimate 33 the maximum cardinality among these dominant sets. Now, the function 9 is defined by setting ((>) equal to 1 for A S 2. setting it to Bx for À in the geometric 1 T sequence (1, 5 5 s.....), and then interpolating at other À to form a non-decreasing step function. In Appendix C.2, we prove that with high probability, So.2x S BB S Bx and 9 is non-dccreasing, leading to X2.g being close to A2,8-
Clearly, if C Kn Kn CDX
lm(K/6) and g() Bx, then Xo.g X" In general, 9 (e.g., À + 8A) is unknown. How- ever, g can be evaluated at any X (0, at a cost of Cost (Query) (A) = O(CIn(K/5)/A² samples. The prob- lem OPT(C, is to find Ct using as few samples as possible.
Now, at a high level (our actual approach in Section 4.1 slightly differs), by solving OPT(C, for C as above and g(A) = Sx, we obtain a fully adaptive algorithm for GDRO that adapts to X and has total (including the cost of find- ing X*) sample complexity whose rate (in big-O) is equal to the product of (1(c/) and (9) with replaced by X"; here, In(1/e) is the price paid for adaptivity. We present this algorithm in Section 4.1. However, this algorithm is computationally intractable for large n, and so Section 4.2 introduces computationally efficient semi-adaptive algo- rithm with total sample complexity that, in nigh-precision settings where < X², swaps the Sx in the fully adap- tive algorithm's 's sample complexity with max(In K, 3x-1 }; moreover it entirely avoids the dimension -eeeenden term (Ar)2, making dimension-free.
Second Step: Solving for XO. Our method for solv- ing OPT g) is called sol holveed veOpt. It outputs Ả such that Cost (GDRO) (2) = O(Cost (CDRO) (A*)) while using O (Cost (Cost( (GDRO) (A*) In(1/e)) samples; note that we drop the subscripts C and g. The main idea of so 5elveCpt is to main- tain two variables U and L which specify an interval [L, U] that always contains a good estimate of X². We iteratively evaluate (A) for À E [L, U] and shrink this interval, i.e., U monotonically decreases while L monotonically increases. The shrinking process is based on comparing Cost (GDRO) (A) and Cost (GDRO) (U)) if Cost (aDRO) (A) < Cost (CDRO) (U), then U is set to À and L is increased accordingly. The process stops when À < T., at which point the algorithm return the last value of U as its estimate of X*. The value of is taken from a geometric sequence; this ensures that at most In(1/e) values of g()) are evaluated, leading to the (1/c/) multiplicative factor in the final bound.
C
4.1. Adppivve Sample Complexity for GDRO
We present an algorithm called SB-GDRO-A, A, shown in full in Algorithm 8 in Appendix C.2. The idea of this algo- rithm is to (i) construct a non-decreasing function 9 so that Cost (GDRO) (Ac.a) is sufficiently close to Cost (GDRO) (Ac,s) with high probability; (ii) solve OPT(C. g) to get Xe.ai
4.2. A Semi-Adaptive Bound in High-Precision Settings
While SB-GDRO-A is fully adaptive to X", it relies on build- ing covers for O, which is computationally intensive when is large. We now propose a semi-adaptive, computationally efficient algorithm called SB-GDRO-SA that avoids covers. The main idea is to merge the X A"-estimation process into the two-player zero-sum game: starting with = 1, if the dom- inant sets Sx,e, computed in round of the game is bigger than a threshold (e.g. In(K)), then similar Sol SolveOpt. we decrease À exponentially (e.g. X t- X/2). To avoid too small X, we also set lower threshold L so that À stops decreasing once X < L.. These two thresholds, one for |Sx.,,1 and one for X, determine the trade-off between adaptivity and sample complexity. In SB-CDRO-SA, we use In(K) and L = Ö(ev Kn) as the two thresholds. Let Xmn(K be the largest À such that Bx In(K). In high- precision settings where e < X*, the following theorem states that Algorithm 9 is adaptive to max(Xin(K)) X*).
(iii) input Ao,s into SB-GDRC. Our approach uses at most (GDRR) O(Cost c,3()) (Xc.g) (n) samples for steps (i) and (ii), which, together with Theorem 3.4, gives us the following theorem (proved in Appendix C.2).
Theorem 4.1. For any e > 0, E (0, with probability at least 1 8, SB-GDRR-22 (Algorithm 8) with Th,t Ng and Tt defined in Theorem 3.4 has sample complexity
((
Knnnn GDK)
(D2C²
In (K)
!
(27)2 +
In
2
Compared to Theorem 3.4, the sample complexity bound in Theorem 4.1 contains an additional multiplicative factor of (l1())))) which we consider a small price for not knowing X beforehand. Next, we briefly describe the two main steps above, with the full details in Appendix C.
Theorem 4.2. If VV In(K) < X", then with probability at least 8, SB-GDRO-SS SA (Algorithm 9 in Appendix C.3)
C
7

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
has sample complexity
6. Experimental Results
(D'G* + max(In(K)) 9x-))
In ln(K/8) :
We support our theoretical findings with empirical results in two different GDRO instances: one with the lower bound environment constructed in Theorem 3.5, and another with the Adult dataset (Becker & Kohavi, 1996). On the lower bound environment, we set é = 0.005, K 10, X = 0.2 and 3x- = 2 so that the maximum risks can only be attained by the first two groups for any 0. On the Adult dataset, we use the same setup as (Soma et al., 2022) and divide 48 842 samples into groups based on race x gender with the goal of finding linear classifier that determines whether the annual outcome of person exceeds USD 50 000 based on 5 features: age, years of education, capital gain, capital loss, and number of working hours. Similar to (Soma et al., 2022), Pi is the empirical distribution over samples in group i. One difference from (Soma et al., 2022) is we have K = 10 groups from races and 2 genders instead of 6 groups, so that the difference between In (K) and K is amplified. With 0.001, use hinge loss and normalize the features so that the losses are in [0, 1]. We set T 10th and 8 = 0.01 on both GDRO instances. The results are aggregated from five independent runs with random seeds {0, 1, 2, 3, 4). To compute 0", we run the two-player zero-sum game with ideal players who have access to the underlying distributions P,, More experimental details are in Appendix G.
2
We emphasize that Theorem 4.2 holds without knowing X This bound guarantees that in high-precision settings, Algo- rithm 9 enjoys (on average) dominant sets of small sizes that never exceed max(3x (ir,,In(K) (.) Remarkably, this bound is also dominantly dimension-free although the algorithm still uses the dimension A.
5. A Dimenssion-nndependen Approach
In this section, we present SB-GDRO-DE. modified version of Algorithm 1 that uses +C)
o
samples for comput-
ing the dominant sets over T rounds of the two-player zero-sum game. This bound avoids the dependency n, the dimension of e, which might be preferable in high-dimensional settings. The trade-off for getting rid of n is an additional N multiplicative factor in the non-leading term of the sample complexity bound.
We assume that a pair (A, is known such that Unlike the problem instance is (A, -)sparee fixed set SB-GDRO, SB-GDRO-DE does not of samples V for computing the dominant sets of all A O. Instead, SB-GDRO-DF computes the dominant sets only for the hypotheses 0, that the learner encounters during the game. In particular, the T rounds are divided into episodes, in which each episode has a consecutive rounds that use the same dominant set. By the stability property of the regularized update (5) and the Lipschitzness of the loss function f, if a is sufficiently small then the differences between the risks of the hypotheses within each episode is small. This implies that a dominant set for O, will remain a dominant set (possibly with smaller gaps) and therefore can be reused for the hypotheses 1c+1, O2+2..... Osta- The full procedure is given in Algorithm 10 in Appendix D, and its sample complexity is stated in the following theorem.
On both GDRO instances, we compare SB-GDRC- SA (Algorithm 9) to the Stochastic Mirror Descent for GDRO algorithm (SMD-GDRO) proposed by (Zhang et al., 2023). To the best of our knowledge, SMD-GDRO is the only suitable baseline with a near-optimal high-probability guarantee the minimax regime.
6.1. Discovering non-trivial (A, ---sarssyyyyy
Figure 2 (Left) shows the sizes Se. and the average + E Saa. computed by SB-GDRO-SA in the first 10 000 rounds. On GDRO with Adult dataset, it indicates that SB-GDRO-SA quickly discovers dominant sets of sizes smaller than [In(K) within the first 3000 rounds. This shows that a non-trivial (X, In( (K))- condition in- deed holds for hypotheses around 0 in practical settings. Further inspection reveals this (A, In((K))sppasiit is discov- ered early the game without using too many samples: on the lower bound environment the final 0.125 zs 0.5A* using roughly 3000 samples, while on the Adult dataset the final is ne R E [n(K] using roughly 36 000 samples. Both of these values are much smaller than T, and as T is scaled with /,,, this empirically supports the insight in Theorem 4.2 that the sample complexity is dominated by the number of rounds needed in the two-player zero-sum game.
Theorem 5.1. For any > 0,8 E 1), with probability 2D
1 5, SB-GDRO-DF with Tw, = CVT. Nat and " defined in Theorem 3.4 returns 6-oplimal hypothesis with sample complexity
5,
DKG + 3) lK(/)) (n eAd
KDG
X3e
(D2G2 + ())K(((8)
+
e²
8

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Natural Log the chosen am counts
16-
Lemiiant set swerdiaund firtt Awrrage bamirar sec Luleefooonn lid Avsnago Domement Dut (er dauaett
Number groups
2000
4000
6200
10000
Number of roun
Group Index
Figure 2. (Left) Sizes of the dominant the first 10000 rounds computed by SB-GDRO-SA SA. (Right) The number of times group selected by the max-player, displayed in natural log. The highest group (group 8) is female Amer- Indian-Eskinn people.
7. Conclusion and Future Work
Optimality Gap (Hinge Loss)
SHD-GER0
We introduced a new structure called (A, -)sparstyy into the GDRO problem. We showed a fundamental connection between the per-action regret in sleeping bandits and the optimality gap of the two-player zero-sum game approach for the GDRO problem, and then improved the dependency from O(K In in(K)) to ( In In(K) in the leading term of the sample complexity of (A, 3)s-arss problems, the optimal X is unknown. We also showed a near-matching lower bound, which both extends and generalizes the lower bound construction in minimax settings to the (A, -pparse settings.
3 3.0004
340
2 2.0000
1.001
when
20000
0.0
10
Number of Samples
Figure 3. The optimality gap of SH-GIRR-SSA and SMDD-DDRO on GDRO with the Adult dataset. Lower is better.
Global versus local sparsity. One interesting future direc- tion is relax the (X, (3)-spassity to hold only within some neighborhood of 0", This local sparsity condition is more practical version of Definition 2.3. Our experiments show that our algorithms, which are developed for the global version of (A, B)--prsstty, still work well for a real-world dataset where only the local version holds. rigorously solve the local sparsity version, it seems that developing high-probability last iterate convergence guarantee for the sequence of 0, 's in stochastic games is needed. To our knowledge, this is a still an fundamental open problem for non-strongly convex losses.
6.2. Convergence Properties of SB SB-GDRO-SA
Next, we show results indicating that SB-GDRO-SA finds e-optimal hypothesis using fewer samples than SMD-GDRO. Figure 3 shows the optimality gap err of 02 of SB-GDRO-SS SA and SMD-GDRO as a function of the number of drawn samples on the Adult dataset. Ini- tially, SB GDR-GRRO-TA SA uses more samples than GMD-GDRO because SB-GDRO-SA needs to estimate X" However, as 0, gets closer 0", the optimality gap of SB-GDRO-SA decreases much quicker since it only collects samples from the two groups with the largest risks. While SMD-GDRO struggles to get an optimality gap under 4 x 10 even after nearly T = 10 samples, SB-GDRO-SS manages to do so well below 4 x 10 samples. Figure (Right) shows an interesting observation that more than 60% of the samples drawn by BB-GDRO-B- SA are from the female Amer-Indian- Eskimo group. This is in stark contrast to the fact that this group constitutes only 0.3% of the dataset (186 out of 48 842 samples). This underlines the robustness aspect of GDRO, which different compared to the traditional empirical risk minimization regime where samples from the largest groups contribute more to the optimization process.
Impact Statement
We study the GDRO problem generally; yet, because the GDRO problem setting can capture societally relevant ap- plications like min-max fairness, we acknowledge that our theoretical work could later be applied in settings where min-max faimeess is the goal. Whether or not min-max fair- ness is appropriate can depend on the particular application domain being considered and especially on the particular meaning of the loss function adopted in that domain.
9

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Acknowledgments
Haghtalab, N., Jordan, M., and Zhao, E. On-demand sam- pling: Learning optimally from multiple distributions. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Informa- tion Processing Systems, volume 35, pp. 406-419, Curran Associates, Inc., 2022.
QN and NM were supported by NSERC Discovery Grant RGPIN-2018-03944 CG was partially supported by IN- RIA Associate Teams project, ANID FONDECYT 1210362 grant, ANID Anillo ACT21000S grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
Jang. T., Gao, H.,, Shi, P., and Wang, X. Achieving faimess through separability: a unified framework for fair repre- sentation learning. In Proceedings of The 27th Interna- tional Conference on Artificial Intelligence and Statistics, 2024.
References
Abernethy, J. D., Lee, C., and Tewari, A. Fighting bandits with a new kind of smoothness. In Advances in Neural Information Processing Systems, volume 28, 2015.
Kleinberg, R., Niculescu-Mizzi, A., and Sharma, Y. Re- gret bounds for sleeping experts and bandits. Machine Learning,
Abernethy, J. D., Awasthi, P., Kleindessner, M., Morgen- stern, J. H., Russell, C., and Zhang, J. Active sampling for min-max fairness. In International Conference on Machine Learning, 2022.
272, sep 2010. ISSN 0885-
6125. doi: 10. 10.10007/1109944010-5778--- URL https: //dpi. 1007/ / 510--17877
Awasthi, P., Haghtalab, N., and Zhao, E. Open problem: The sample complexity of multi-dise colti-distribution learning for VC classes. In Proceedings of Thirty Sixth Conference Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 5943-99459999 5949. PMLR, 12-15 Jul 2023.
Liao, R. Notes on Rademacher complexity, May 2020.
cs URL httht:tt///w/e http://wwwwsss.oort.ooeoe toronto.ooooo... twronto..dd/ rrtiitooodddrrrrrrjrii
notes/Notes on Satademacher_Coopeeeseeeeee pdf.
Mohri, M., Sivek, G., and Suresh, A. T. Agnostic federated learning, In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Ma- chine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4615-4625, PMLR, 09-15 Jun 2019.
Becker, B. and Kohavi, R. Adult. chine Learning Repository, 1996. http://dbb.or/1112444//////
UCI Ma- DOI:
Ben-Tal, A., den Hertog, D., De Waegenaere, A., Me-
lenberg. B., and Rennen, G. Robust solutions of op- timization problems affected by uncertain probabili- ties. Management Science, 59(2)334-3357, 2013. doi: 10.1287/mnsc. 11w.mmsc..1........ 164..
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochas- tic programming. SIAM Jourmal on Optimization, 19 (4):1574-1609, 2009.
Carl, and Stephani, I. Entropy, Compactness and the Approximation of Operators. Cambridge Tracts Math- ematies. Cambridge University Press, 1990.
doi: 10.1137/0707042777 URL https: //ooi http:///...ooo.......////1
Neu, G. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems, volume 28, 2015.
Cesa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006. ISBN 978-0- 511-54692-1.
Nguyen, Q. and Mehta, N. A. Near-optimal per-action regret bounds for sleeping bandits. In Proceedings of The 27th International Conference on Artificial Intelligence and Statisties, 2024.
Chang, S.-H., Cosman, P. C., and Milstein, L. B. Chernoff- type bounds for the Gaussian error function. IEEE Trans- actions on Communications, 59(1))2939-29)) 2011. doi: 10. N0.1009/TC0M..001
100049..
Dudley, R. M. The sizes of compact subsets of Hilbert space and continuity of Gaussian pro- cesses. Journal of Functional Analysis, 1:125-165, 1967. URL
Nielsen, and Nock. R. A closed-form expression for the Sharma-Mittal entropy of exponential families. Jour- nal Physics A: Mathematical and Theoretical, 45(3);
http:///aa..semaatscccceeeeeeeee org/CorppsDD:112240000
032003, December 2011. ISSN 1751-8121. doi: 10. 1098//1711-8111345/3333333 URL http: / doi. 10 oxtg:/00.008//7555--611111333310
doi.
Freund, Y. and Schapire, R. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1):79-103, October 1999. ISSN 0899-8256. doi: 10. 10.110///amm.11990 1999.0738.
Orabona, F. A modern introduction to online learning. CoRR, abs/1912. 2019. URL http:://rxiv. org/abs/ /1abbs//99t /9t.. 13213. Version 6 (1912.1321366)
10

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Peng, B. The sample complexity of multi-distribution learning. In Agrawal, S. and Roth, A. (eds.), Proceed- ings of Thirty Seventh Conference on Learning The- ory, volume 247 of Proceedings of Machine Learn- ing Research, pp. 4185-4204. PMLR, 30 Jun-03 Jul 2024. URL https: /pppeeeeeoeegss..cepe mlr.press) 2.47/peng24b.htm html.
Rawls, J. A Theory of Justice. Harvard University Press, 1971.
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang. P. Distributionally robust neural networks. In International Conference on Learning Representations, 2020.
Shalev-Shwartz. S. and Ben-David, Understanding Ma- chine Learning: From Theory Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Soma, T., Gatmiry, K., and Jegelka, Optimal algo- rithms for group distributionally robust optimization and beyond, 2022. URL https: /ttp/vaaiivv//.///////.///a.aa org/ / 2212.13655
Wei, C.-Y. and Luo, More adaptive algorithms for ad- versarial bandits. Conference On Learning Theory, pp. 1263-1291. PMLR, 2018.
Williamson, R. and Menon, A. Fairness risk measures. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp.
PMLR, 09-15 Jun 2019.
Zhang, L., Zhao, P., Zhuang, Z.-H., Yang. T., and Zhou, Z.-H. Stochastic approximation approaches to group distributionally robust optimization. Advances in Neural Information Processing Systemx, 36, 2023.
Zhang, Z., Zhan, W., Chen, Y., Du, S., and Lee, J. D. Optimal multi-distribution learning. In Agrawal, S. and Roth, A. (eds.), Proceedings of Thirty Seventh Confer- ence Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 5220-5223 PMLR, 30 Jun-03 Jul 2024. https:: pttp///rcceednn..... alr.presss / v247 ht/////ang2bbbb..b html.
Zimmert, and Seldin, Y. Tsallis-INF: An optimal algo- rithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-499 2021.

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
A. Proof for the Global Sparsity in Linear Regression in Section 2.2
A.I. Expected Loss of Linear Regression
Let E R. 0' E 1-1, X| X N(,, 1) and ( ~ (X (²)) Consider the linear regression problem where the goal predict 8" Let e B be prediction for d" The loss on example (X, the squared loss
(X, (XxxX))))XXXX)))) -X
(11)
The expected loss of is
- - = + y 20]
(12)
= = + + 20 x].
(13)
We have E[X?] = (E[X])² + Var(X) 112 + 1. Moreover,
E[Y = Ix ( X]] =Ex((Ey [Y] X])² + VVryix(())
=Ex((X0*) + +
(14)
=(0')?(Xx3] + 00
(07)3 + 1) +
In addition,
E[YX] Ex[XEvIx [Y X]]
= =Ex[X201
(15)
= =0-EX[X²
-00 1).
Overall, we have
E((XA- - r) = 03 1) + (0r)² + + -2
220000 (n² +
(1² + 1) + (8") - 208") +
(16)
(4²² + 1)(0 00)
The expected loss of is R(0) = (n² + 1) - 002
A.2. GDRO with 3
Let K = 3. Consider the GDRO problem with K groups, =
0, = = and 07 = -1,0%
1, f3 = 0. For any E R. from the previous section, we have the expected loss of f on these three groups is
(0) = (NÂ + 1)(0 - -0)0-0))--000 - of = (0 + 1)² +1, (2 (1ă + 1)(0 - 03)² - oh (0 1) +1, Ra( (ui + 1)(0 - 00)² o 0 +1.
(17)
Next, we will show that for all 0 E
max (8), R2(0)) Rs(0) 2 1.
(18)
Indeed, we have
m Ra(0) = max 20 + 2 0² 20 + 2} - (20 + +1) max -20) 1.
Obviously, the result holds for E [-1,1] since it holds for 9 R. We conclude that that this GDRO instance is (0.5, -S-spas
12

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
B. Proofs for Section 3
For a mseudo-metric space (F, II-1I), for any <> 0, let (FF, ,, II-I)) be the v-covering number of F; that is (FF, 11-1-11 the minimal number of balls of radius needed cover J..
First, we prove the following lemma uniform convergence bound that holds for sufficiently large value of m.
384n In( &
Lemma B.1. Let
With probability least 1 - 88/2, the event
0.012
= = (1)((0)) R2( - 0.15A}
E,
(19)
holds simultaneously for all i E [K] and 0 E e.
B.1. Proof of Lemma B.1
Our proof for the uniform convergence bound in Lemma B.1 is based on the Rademacher complexity bound of the class of functions Te defined as follows:
Le = [((0,)) : (0, E),00
(20)
which is the set of all possible functions E(0,-) for 0 E O. First, we state the following bound for the empirical Rademacher complexity based on the chaining argument (Dudley, 1967; Liao, 2020).
Lemma B.2. (Dudley's Entropy Integral Bound (Dudley, 1967; Liao, 2020)) Let F (f 2 - R} be class of real-valued functions, S = {21, F2, ... Fm be set of m random i.dd samples. For function f F, let
1
1ffl,,
(f(2z))
(21)
be an S-dependent seminorm of Assuming
sup 11fll2,s S c, SEF
where e is a positive constant, we have
vm Je Vin(NCC u (1.122s)) )d
12
Rad(F, inf cE(0,g)
4
(22)
where Rad(F,S) = 1 " supjer (zf()) is the empirical Rademacher complexity of and N(F, M, (1-)11,ss) is the size of v-cover of F.
A proof of this lemma can be found in (Liao, 2020). We now prove Lemma B.I.
Proof (of Lemma B. I). For i E [K], Theorem 26.5 in (Shalev-Shwartz & Ben- Ben-David, 2014) states that with probability at 5 over the set V; of size m, for all E θ,
least 1 - 4K
32 l2(4//8)
E(O, R2( < 2Rad(Lo, V.) +
Our proof is based on the fact that the covering number of the compact set C R is finite, and hence the empirical Rademacher complexity (Le, V.) is bounded for all i [K]. Because the values of the loss function & [0, 1), we
13

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
have 11 for all Lg. Moreover, the diameter of Le measured in 11-112, is
1
m
max 0,
(E(0, Vi.)) 1(0', ((,)) -
max 0
G
0
m
m
G2D2
m j=1
GD,
where the first incquality is due to the Lipschitzness of the loss function l and the second inequality is due to D being the diameter of θ measured in norrm. Applying Lemma B.2 with 1 and c = 0, we have
12
Le²
Rad(Le, Vi) v
Vm V In (NLLo, Us 11-112 dv
12G
4GG
dv
vm
12
4GG
where the second inequality is due to a result that the size of the smallest v-cover on set F with diameter d is bounded by Ad nd (see e.g. Carl & Stephani, 1990, Equation 1.1.10). To compute this integral, u /In(AGD/v). We then have -" and du 4GDd(e "²), As - 0, co. As u (I).. Hence,
v
(GG V mm
dv 4GD
InGG)D
ud(e =²)
1'
4GD
ue
100
VL(SGDD
In(8GD)
eu du
Vln8GD)
x2
4GD
du
8GD
Mn(8GD)
Vln(8GD)
4GD
In(8GD)
8GD
2 2//88GD + V
where the second equality is integration by parts and the inequality is by Chernoff-type bound the Gaussian error
function 3/t 1 -+² dt S e=² (Chang et al., 2011). Overall, we have
By Vm Rad(Le, V.) < (2VIn(SGD) + VT)
We conclude that the uniform convergence bound is
m Σ E(O. - -2, I
3 (2VIn(8GD) + VT)
32In(4K/0
m 1=1
Vm
m
By setting the right-hand side to 0.15A, solving for m and simplifying, we obtain the following sufficient condition on m:
384n 741GDK
(23)
0.01X
so that with probability at least 5 bound over all K groups leads to the desired statement.
kK we have Σ> E(O, Vi.) Ri(0) < 0.15A for all E O. Taking a union
14

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 4 MinP: the stochastic-OMD min-player Aug
Input: 0r E θ sample Zi,,
Compute 9r Ve( 2s,,t)
Compute 1c+1 = arg mingge (T (āe, 8 - 0z) + -1100- 0ell)) by Equation (5)
Return: 01+1
B.2. Proof of Lemma 3.1
Proof. From Lemma B.1, we immediately have the event & holds simultaneously for all i E [K] and 0 θ with probability at least 2. Thus, it suffices to prove the desired statement assuming that all & hold. Let Ri, = (0,) and
R.,, (O,) be the risk and empirical risk of 0, with respect group respectively. We consider two cases: Bx < K and
3x = =.
When Bx K:
In this case, there exists non-empty set X-dominant set Sx,0, whose size is smaller than .3x < K. This implies that the set [K] \ Sx,9, is also non-empty. For any E Sx,o, and & E [K] \ Sx.... due to εi, εk,o, and by Definition 2.2, we have
Rr, Rr.1 2 (Ri, 0.15A) (Rx,r 0.15A)
Ri RK 0.33
2 X - 0.3X
T > 0.
Thus, at any time t, the sorted sequence of groups can be divided into two non-empty parts: the first contains all groups in Sx.,, and the second contains the rest. Since |Sx.o.1 I 3x. the size of the first part is at most Bx. Let i* arg max,, {ord(j)} be the last group in the first part. Since nxt(i") E [ we have R , 2 Ruxa(s)), +T. This satisfies the condition in Algorithm 3, therefore the resulting set Sp, is non-empty and its size does not exceed Bx. To show that So, is 0.4)-dominant set, for any i' E Se. and k [K] Se,, we have
Rv. R 2 (fe 0.15A) (fRK, + 0.15A)
Rv, RK., 0.30
(24)
> R2g - R 0.3A
r 0.3A = 0.4A,
where the second inequality is from the definition of i and So, = (i E [K] ord(i) S ord(i)}, we have ord(i') s (i) ord( 2 ord(k') and the empirical risks are sorted in decreasing order.
When Bx = K:
In this case, the inequality Se. s 3x holds trivially. To show that So, is a 0.4A-dominant set, we further consider two sub-cases: a -1 and à 1.
+ -1: in this case, the set Sp. (i E [K] ord(i) S ord(1)) has size most K because the group with the largest empirical risk is excluded. Therefore, by the same argument as in (24), the set So, is a 0.42-dominant set.
= 1: in this case, we have So. = [K] is trivially
set by Definition 2.2.
We conclude that the set So, is a 0.4 do.Anntmmnant set at 0, and | S 8x.
15

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 5 FTARLShannon: Follow the regularized and active leader with Shannon entropy regularizer and time-varying learning rates for sleeping bandits
Input: K
for all arms i E [K]. for each round t 1,... do
Initialize T-i.0
The non-oblivious adversary selects and reveals P.,
exp( v k..1)
Compute qt.t Σィ exp( (ncks.))
Compute Pi,t E/= 11,19.1
13,19.1 by Equation (26)
Draw arm & Pt and observe Ee lla, for each arm i E [K] do
If 4, 1, compute E,, Him=s
by Equation (27)
p1,
If Ti 0. compute Ei, = le na Ejer, Eee by Equation (28)
Update F., Tiit1 + Ei,t
B.3. Proof of Theorem 3.2
Let A, = [Asel be the number of active arms in round t. Throughout this section, we write 1) = ny, for the learning rate of the SB-EXP3 algorithm used by the max-player.
The O ( (Vn((K/))ET= Ae
high bigh-probbbility per-action regret bound of the SB-EXP3 algorithm in (Nguyen & Mchta, 2024) was established for a fixed learning rate τ) 17 and fixed exploration factor = In this section, we generalize their result to algorithms with time-varying learning rates and exploration factors defined as follows:
(3(3//8)
= 2T = V E._ A,
(25)
Note that f) and y are chosen after the set of active arms Ar revealed. As pointed out in Nguyen & Mehta (2024, Appendix G). the SB-EXP3 algorithm is equivalent their Bellow-the-Regulle Reat---eularize--aade Seti--Acttv--eeerr (FTARL) algorithm with the Shannon entropy regularizer. Therefore, high-probabille regret bound of FTARL with Shannon entropy regularizer and Ni and "/ defined in (25) would imply Theorem 3.2. For completeness, we provide the full procedure of FTARL with Shannon entropy regularizer in Algorithm 5. For each arm i E [K] and round t E [T']. this algorithm maintains an estimated cumulative loss Li, defined as
Life Σ
#=1
and computes the weight of arm in round t by
m m,Ir,e-1)
cxp
Ui.t
K E/= exp (m((l
where 7/e is the learning rate in round t. Initially, L.o = 0 for all arms E [K]. Upon receiving the set Pu, of active arms,
the sampling probability p: is computed by normalizing Li, as follows:
I,19
Pt.
(26)
Note that Li, lii J, hence Pi, is non-zero only for active arms, An arm i, ~ Pe is drawn according to pt and its loss = li,t is observed. For an active arm E Au, its loss estimate is the IX-loss estimator (Neu, 2015):
Ifis = =ife
i,
(27)
Pi. 7
16

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
where Yt is the exploration factor in round For a non-active arm i Ar, its loss estimate is defined as the difference between the observed loss l, and the weighted sum of estimated losses of active arms (Nguyen & Mehta, 2024):
t, Ex - 7tt Σ
(28)
JEAL
The following theorem states the per-action regret bound of Algorithm 5.
Theorem B.3. Let (Nt)==.... and (7.. be two sequences of non non-increasing learning rates and exploration such that nle S 2--- With probability at least 1 - 8, FTARLShannon (Algorithm 5) guarantees that
max Regret(a) - [
In(K)
ln(3//6)
+ 1n(3/6) +
Σ
T
11 2
+ 71
A,-
(29)
1/r
2
The proof of this theorem is in Appendix E. We are now ready to prove Theorem 3.2
Proof (of Theorem 3.2). By plugging (25) into the bound in Theorem B.3, we obtain
In(K)
ln(3K/0)
max Regret(a) "E K]
+
V/T
1/T
2 2l3(3K/8)
(
In
+
Σ
m
8
1/
t=1
2 2lK3//
(3) 8
T
A
+In
+
Vln(3/00 /))
1/
E As
T Σ
3 (
T
A
2, ln(3K/0)
Ar + In
+ In(3K/8)
E/= A,
1=1
We bound
E 11
A.
as follows: let C. = Exm1
A, and Co = 0. Then,
V A,
T
A
T Σ
C.
C-C1-1
C--1
VCr
1=
Ag
1=1
T
dr
O-1 VC
T
dr
5 Σ
V
1=1
C-1
Cr
dr
Vo
Co
CT,
where the inequality holds because J/2 2 vor for all C-1 S x S C. This implies that
T
2 5
max (agret(a) $2 In(3K/8) <E(K]
Σ (=1
A. + In
+ 2
In(3K/8)
Σ
[=1
T
=0 (1 In(K/8) Σ
A
17

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
B.4. Proof of Lemma 3.3
Proof. Since A is convex, can write
T
T K
mAxX gE
Σ ((r,g))
= max qEAk
Σ
>
q
(O))
t= im1
K
q:
Riçt
gEAR
1=1
max
Ri
K
Thus,
T
T
R. = max
Rig
Σ
(0e, qt).
a group is not included in Se, at time t, then by Lemma 3.1, for any k E So, we have
Ri Ri, + 0.4X S R
By construction, the probability vector qe contains non-zero elements only for groups in Sa,, hence for any i o Se we have
Rs, (00,, q()
Σ
(Ra, Re,e) s 0.
kESa
We conclude that for any i E [K],
T
Σ
Rit - ((0) S Σ fi Sa. - ((0r,4))),
hence
T
max RA, iE[K]
Rit Σ ((0..9))
T'
Σ
fffe E So (R((O.) - (00,, 9:))
max [
B.5. Proof of Theorem 3.4
Let B, = Sa. be the size of S,, Let B7 ET= 3, be the average number of active groups over T rounds. We first state the following bound for the regret of the max-player as a function of 3,, which is obtained directly by combining Theorem 3.2 and Lemma 3.3.
Lemma B.4. With probability at least - 8/4, the regret of the max-player in -DRODR (Algorithm 1) is bounded by
T
RA, 50
Σ
3 In
ln(//))
1=
18

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Proof. The max-player in Algorithm uses the sleeping bandits algorithm SB-EXP3 with the stochastic loss of arm round is
hag = E(0e, 25,1)-
Let Hig Pe [hr,e] be the expected value of hige. We have Hi, 1 - (2)))). Note that both hi and Hat are in [0, 1]. Fix group a E [K] and la, - Ila E S. J. The per-action regret of group a is
T
GroupRegret(a)
Σ
(Rn((())))) (())
T
K Σ i=1
Ra(0.)
the Ro(e)
T
K
Σ
La,t
Σ
qi Hip Ha,e
T
Ila
Ia,
9o.t Hie Mise + hagt ha, + ha,t Ha,
i=1
T
K
Ja,t
Fi.t Hi, nict
Tas(baa Ha,))
Σ
(ai ha,1).
(A)
(13)
(C)
The term C' is exactly the per-action regret of arm a in -DRR-O-----D SA defined in Equation (6) which, by Theorem 3.2, is with probability least t simultaneously for all a E [K]. Next, we bound the
bounded by Vln(K/6) (In(K/6)Ei= (e) terms A and B. Since
Eigag (Ezg, [bs, = Eigwon [Hia
K
Hi
and
K
K
Σ
qi Hig higt
Σ
qi - hicee)
Di. Hife hinl
S 1,
A is a sum of martingale difference sequence in which the absolute values of its elements are bounded by 1. By Azuma-Hoeffding inequality, with probability at least 1 12R we have
A (12K/88))
(30)
For term B, we also have E....r. [ba,t] Ha,e, therefore B is also sum of martingale difference sequence with elements' absolute values bounded by 1. We then have B < 22 In ln12K/0) with probability at least 1 12K By taking
5
union bound twice: once over A and B for each action and once all K actions, obtain with probability at least 1 4
A B
2T 2n
19

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
simultaneously for all E [K]. Furthermore, since
T T
T
1=1
[=1
due to 1 S 3r, obtain that with probability at least 1
5
(1
(1 (n(K/6))
max GroupRogrct(a) S KE|K]
38
(31)
By Lemma 3.3, when Ei holds simultaneously for all i E [K] and 0 E θ we have
RAg S max GroupRegret(a) aE[K]
T
0o In(K/o)
3r
Corollary B.5. For any 2 1, SB-GDRO (Algorithm 1) guarantees that with probability at least 1
5
2
(DG+ v Be) lk(K/)
err(0, 50
(32)
VT
Proof. By (Zhang et al., 2023), the duality gap is bounded by the average regret of the two players:
1 err(0,g) S T (RA, + R.A))
(33)
In Appendix F, we prove that with probability 1 66/4, the regret of the min-player is bounded by
RA. s (DGGT//im11/))
(34)
For the max-pi max-player, Lemma B.4 implies that with probability 1 5/4,
RA, 50
Σ By ln(K/8)
(35)
0
V
T3r In(K/0)
Σ.s T
where the equality is from the definition of 3T
Plugging (34) and (35) into (33) and taking a union bound, we
obtain that with probability at least 1 - 5/22
DGV/n(118) + Br ln(K/5)
arT(F. 50
VT
(DG+ /Br) In(K/8)
50
VT
20

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Ey(e(0, 2)]
top 3 groups with arbitrarily close risks
gap À
bottom K f groups with small risks
θ
Figure 4. The construction for Ω ( lower bound.
0 + is sufficient for target optimality gap e. This is self-bounding
Corollary B.5 implies T
condition on T since the quantity Br is dependent on (and changes with) Nevertheless, represents valid stopping condition because Br is fully observable and bounded above by constant K. We ready to prove Theorem 3.4.
Proof (of Theorem 3.4). In Corollary B.5, by setting the right-hand side and solving for T, obtain that with probability at least 1 - I. the number of samples collected during the game for having err(0,g) S i
(D2G² + Br) ln(K/())))
22
By Lemma B. we collect
n nIn(GDK/8)
X
samples from each group before the game starts so that with probability at least 1 $ we have Br S Bx simultaneously for all t E [T]. This implics that Br < A and thus the bound can be written as
D Ln)/8(()))
By taking union bound, we obtain that with probability least 1 - 6, the total sample complexity is
Kn(In(GDK/8) + (D2G² + 3x) In(K/)))))
X2
2
B.6. Proof Theorem 3.5
Proof. Our lower bound construction directly extends that of (Soma et al., 2022). particular, let Z = [], be the set of samples and @ [0, 1] be the hypothesis The loss of hypothesis 0 sample =
21
22 is
23
((0,2) 5 22 0)) + 23.
21

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
where 8 10 constant defined later.
The distributions of the first 3 groups similar to that of (Soma et al., 2022), where
The first distributions are
0
almost surely
22 almost surely
23 Bernoulli(ps).
where 14 2 for ,
The 8th distribution is
21 almost surely
P3
22 almost surely
23 Bernouli(uaa,
where 14g 2'
The last K distributions are
21 0
almost surely
P. = 0
almost surely
23
almost surely
i = 1, 2, 2...., K. Figure 4 illustrates this construction. The risks of the groups are
A(1 0) 148
(i = 1,2,...,
(0) = E,>P, [c(0,=)]
AO + 14
(i = 3)
-
8 1,8 .
3, we have R2,0) (0) > for any 1 Sis B and B + S S K. It follows that the set [8] = .1. } is X-dominant set, and this GDRO instance is (A, Bs-aare. Because the risk differences between the top 3 groups are upper bounded by
Since A 2 0, 0 E (0, 1) and 14 for ,,..,,
(O) Rx(()) = A1 20)}
which is arbitrarily smaller than A, there can be no X-dominant sets of size smaller than 3. Thus, we have B3 = B. Moreover, for any 0, its maximal risk attained on a group within the set [3] only. Therefore, the sample complexity of algorithm .A lower bounded by total samples drawn from the first 3 groups.
On the other hand, by setting
3
=
where 7' is the expected total number of samples drawn by A, the first 3 groups are identical to the groups that give rise to the minimax lower bound in (Soma et al., 2022). It follows that for any algorithm A, there exists a GDRO instance which requires at least
G² +
?
2
samples to find c-optmall hypothesis.
22

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 6 SolveOpt: algorithm for solving OPT(C,.)
Input: E (0, k2 3 K, function
Evaluate g(1)
Initialize U = 11 C4 C
A 1;
while A 2 I. do Evaluate g(A) if f(A) < {U) then
Assign U + X, L
+ m
Update X = X/5
Return: Ā = U.
C. Proofs for Section 4
Remark C.I. For notational simplicity, we use a short-hand notation fc., for Cost (GDRO) In other words, we will write
C fc.g X 22
a(A)
(36)
We will also drop 9 when it is clear from the context and simply write f()).
Remark C.2. Throughout the proofs for Section 4, some of our bounds contain In (n(n())) factor. While we will always present this term explicitly the first time they appear in the bounds, for case of exposition we generally are not pedantic about this term and will treat it as constant. For example, we will write
K (+t) 5
K
In
In
+
In
In
5
K
= 0
In
8
assuming that in practice, the number of arms > 1 is not too small and the failure probability 5 < 1 is not too large so that K > (+)..
C.1. A Sample-Efficiee Efficient Approach for Estimating X2.g
We present an algorithm called SolveOpt for solving OPT c, g). SolveOpt outputs a Ả such that f(Å) = O(f())) while using at most (f((x*
(n(e samples. The significance of this result in the context of GDRO as follows: by using (f(())) samples to obtain an estimate Î and then using À for GDRO, we guarantee that the total sample complexity is of order Ó()())). This implies that without knowing X*, we can achieve bound with only a logarithmic factor overhead than the bound obtained when X known. Our results and techniques are applicable other trade-off problems similar to (10), and thus they could be of independent interest.
As mentioned in the main text, Sol veOpt maintains two variables U and L which specify an interval [Z, U] that always contains a good estimate for A This [T., U] shrinks over time based on how large f()) is in comparison to fU)): U is set to À and L is increased accordingly if f()) < f(U) holds. A crucial element of this process is choosing the geometric 1 1 ...) .) of common ratio as the sequence of À at which g()) is evaluated. The process stops when X < L, sequence (1, 5. 25.
at which point the algorithm return the value of U as an estimate for A The first key technical insight of this process that L and U can be computed using only readily known quantities such as C, K and evaluated g()). The second key technical insight is after some finite number of steps, is guaranteed that any value in the interval [L, U] a good estimate for X* The full procedure is given in Algorithm 6. The following lemma states the sample complexity of this approach.
Theorem C.3. For any OPT(C,g) g) problem defined in (10), Sol velpt (Algorithmm 6) returns a X such that f(²) < 50f(X*) while using at most O (f(*) In K/5) ln(1/c) samples.
Before proving Theorem C.3, we note that SolveOpt (Algorithm maintains range of values [L, U] that always contains U
at least one good estimate for X", and evaluates g()) elements of the geometric series (U, U 0 5 25"
) to
... Loxo (4))
23

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
compute this estimate. Note that all elements of this series are in [L, UJ. Whenever S(A) is strictly smaller than S(U) for some A, we shrink the range [L, U] by setting
and =
+ We first prove the following lemma
which shows that L is always smaller than or equal to X", thus at least one g(A) for X S X will be evaluated while running SolveOpt.
Lemma C.4. For any U E (0, 1), let
L
2
Then, S min(X*,U) U..
Proof. Since Bu 2 we have L S U. By definition of X", we have
C
g(x))
f(U) = C
9(U)
f(x*) = (X-)2
+
S
+
2
U
Since 2 1, this implies
C
1
C
U
(2+)2
2
T2
+
2
Subtracting 1oz and dividing C on both sides, obtain
C
(A*)²
C
+
-101-1
L
We conclude that L < min(X*,U
The next lemma shows that if À falls into the range [ A-] when f(U) is much larger than f(x),, then the inequality f(A) < f(U) holds.
Lemma C.5. For any U E (0, 1). if
25C
g(X²)
f(U)
+
(2+)2 é
then for any X 1 X*), we have
f(A) f(U).
Proof. For any A E 12/ x²), we have $ <
25C (X-)2
and g(A) S g(>*). Hence,
S(A) = C g(A)
12 +
2
< 25C
+ g(X*)
(20)2
2
< (()).
We need one last lemma, showing that once U is sufficiently close to x such that f(U) = O(f()*)), then any values between [T., U] can be used as an estimate for X*
24

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity Lemma C.6. For any U (0,
25C g(A)) 1(U)
(A*)2 c² +
then with L
- we have for any UL
(A)
Proof. For any U1, we have f S fo and g(A) S g(U). Hence,
C π(
S(A) XX 2
C OU)
ET 62
U2 + ((V)
C
-1
g(U)
C
since L
6
2²
V
c 02
+ g(U)-1
C 20(U)
U 2
21(
+ g(Ar)
s 50
()+)²
50f()²).
Proof (of Theorem C.3), First, we prove that SolveOpt (Algorithm 6) always terminates after a finite number steps. Observe that during the while loop, the sequence of values of À is (1, 25. ...), which is monotonically decreasing. the other hand, L is non-decreasing from the initial value of C+ 211 r.
C
This is because whenever f(A) 2 -(U), the value
of L is
C f(U)
-
I
Once the inequality f(A) < f(U) holds, U is assigned to À and L is assigned new value L', where
C
C
L'=
=
[())
- 2
1 2
follows that the condition À 2 L the while loop must be false after a finite number of steps.
Next, we consider two cases: f(1) <
(x*)² + s(A") and f(1)
25C
25C
((A))
(A*)
Case 1: f(1)
25C 2
o(A*)
In this case, by Lemma C.6, any value the range [L, 1] where L
is good estimate for A* Because these
c+"
values are least I. and there are most log, (+) evaluations, the maximum number of samples needed for testing all
25

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
values of À in the sequence (1, 1. 1 5108st7777] is bounded by
C Cin(K/6)logg logs (1)
g(1) -1 -1)
loss --2 )
=0
[n(K/8)
C
1,2
62
9(1) -
V1+ 9(1)
[n(K/6)
C +
logs
2²
Ce
9(1)
g(1) -
In(K/6)
C+
1 +
2
Ce2
9(1)
1+ 2 )
0
In(K/8)
C+
2
< (((n(K/))(()))((()))
where the first inequality is from logs(V*) = In(x)
=2m((5] & In(x), the second inequality is due to 9(1) - < K < C, and the
third inequality is from +
a(l)
= f(1 S 25²( and in (1 + 1)) s In (2) 2n v2
(?²)
2
Case 2: f(1)
25C 2(A*) (
2
In this case, since f(1)
24C (x-)
+ f(X*) > f(x*), initially, have U 1 > A² By Lemma C.4, have X belongs
V C+ s As repeatedly shrinks by 1 from 1, after at most log, 5 iterations of the while loop, it must fall into the range X X²) Each of these iterations makes one evaluation g( for some À 2 A*/5. Hence, the total number of samples to evaluate (A) for from 1 to ( (i.e., the first element of the geometric series that lies inside the range [X* /5, A*), most
to the range [L, 1), where
o C Cln(K/0)lo%s/ (+) (X₂)2
(37)
Let U. be the largest value of À being tested for which f(A) < 25C
X= + e(A*)
By Lemma C.5, U, 2 X-/5. Note that U.
might be larger than A Because the algorithm starts with f(1) 25C + 2(A"), the inequality f(X) < fT) must be true U.. It follows that U is set to U., and f(U.) < 50f(X*) by Lemma C.6.
Let L.
C be the corresponding value of L after U is assigned to U* In each of the subsequent iterations,
since I. is non-decraaiigg and U non-increasing, the returned value â must be in this range [T.., U.). The number of
26

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
iterations needed until termination starting from U, is most
Ux
Ux
03
C
+
g(U.)-1
-1
logs
logs
L.
VC
U? + g(E.)
< logs
VC
g(U.)U?
= logs
1
Ce
(38)
1
$ logs
1
E²
I ln
1+
2
< ln
where the second inequality from g(U.) S K
< and U. S 1, the third inequality is due to logs = logg(())
In(x) < lnxx) for and the last inequality + + S 2 for S In each of these iterations, SolveOpt evaluates
[m)
g()) once for À 2 I_, In total, the number of samples these iterations is at most
C (m(K/0) logs
L.
U=
= (n((//))
( C g(U.) -1
+
logs
L?
U?
L.
(39)
$ 0 [0 0 (In (O))(K/))
where the first inequality is due to (38) and the second incquality is due to f(X*) $ f(U.) S 50f(>*) and In(1/²2) = (n(/c)). The total number of samples used by Algorithm is the bounded by the sum of the number of samples for testing from U., and then from U. to L,. Combining (37) and (39), we have the total number of samples needed until Algorithm terminates is most
o Cln(K/5) log, X
Cln(K/5) logs L.
(2+)2
L2
O(((A)) ln(K//(//))))) In(e/e)),
where the inequality from f(x*) (2-)2 + ((7) 2 (x-
C
C.2. Proofs for Section 4.1
Let (( (0' θ: ||0 0'112 < r) be a ball of radius r centered at ②. In this section, prove Theorem 4. which specifies the sample complexity of SB-GDRO-A (Algorithm 8) for the setting where no is known beforehand. The most important component of SB-CDRO-A is computing an estimate À for the optimal X using the algorithm So l veopt (Algorithm 6). This computation uses the algorithm EstG (Algorithm 7) to compute an estimate of Bx for in the geometric sequence (1, f .... of common ratio $
First, we prove the following lemma which bounds the number of À tested in Algorithm Lemma C.7. For any OPT(C, g) problem, in Sol veOpt (Algorithm 6), the number of values X whose g()) need to be evaluated is at most
2
N = In
(40)
27

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 7 EstG: estimating ({) for À in the geometric sequence of common ratio
Input: (0,1)
Compute a cover θ of with centers (1)) 8( ..... (())) Let N In
38tn In( z)(ppx
samples from each of the K groups into set VA3 Compute ( Dominantset (00), VA, 0.7A) for = 1,2, θ by Algorithm 3
Draw m. =
01012=
Return: 3x max max,= 111
|
Algorithm 8 SB- SB-GRDRO-A: SB-GDRO without knowing any X
Input: Constants T, K, D, 0, 0, > 0 Compute Ā = SolveOpt K, g) by Algorithm 6 where ğ is defined in Equation (45).
Let è = | 1=_1...11 6
be the 0.1À G
-ovvrr of @ constructed when querying Ả in EstG
Initialize 0, = arg min ||0|| for each round 1,
T do
Let c2 arg | ||| |000
0. be the index of the center in θ closest to O,
Let S3, be the pre-computed 0.4 dominnttt set at g(c))
Compute dt = MaxP So.) by Algorithm qe and sample =i Pi,
Draw group
Compute 0c-1 MinP MinP((,, (0,, z,,1) by Algorithm 4
Return: 0
Proof. In SolveOptt the values of belong to a geometric sequence of common ratio starting at and terminating at a p where C K g(1). Therefore, the number of values in this sequence is at most
value no smaller than
C+ a())
logs
= logs
C
C+ -i1!!
9(1)
logs
Ce
Cea
9(1)
logs
1+
Ce
[V1
1
logs
since g(1) C
2
4
1
logs
since 1
+
<
2
2
2
2
< In
where the last inequality is due to
lag.(ar))
(n() (5)
In(x:) for any x > 0.
Next, we show that any 0.4A-dominant set So at B (0, 0.11) G
θ is also 0.2X-dominan set at any 0' within the Euclidean ball
Lemma C.8. Let and À E [o, 1). For any E B (0, 0.12 set at 6'
any dominnntn set So.1x.0 at @ is also a 0.2A 2o-dinnnant
28

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Proof. The statement holds trivially if 10.42,0 [K]. If So.r + [K]. for any 0' B(0, ()) and any group k [K]
have
[R(00) ({,0)))((0)))))) S G 01
- 0.1A,
where the first inequality is due the Lipschitzness of the loss function, and the second inequality is due to 1|0 0112 0.1A It follows that for any k E Su.ax,9 and k' E [K] ax,o we have
G
(0' Ry (0') 2 R& (0) - 0.1A (0) + 0.1A)
2 0.2x,
where the second inequality due to (+) - Rs (0) 2 0.4X. This implies that So.4x. is also a 0.2X-dominant set at 0'
Using Lemma C.8, we prove the following guarantee of EstG, which is obtained directly from Lemma B.1 and Lemma 3.1 by re-scaling 8 8/N.
Lemma C.9. For any input X E [0, 1}, EstG (Algorithm 7) outputs 3x such that with probability least IN. the following condition hold:
Su.2 S Bx S Bx.
(41)
Moreover, the number of samples needed to compute 3x is
11GGDKlu(3
384Kn In
Kmn =
0.01X2
(42)
Kn In GDK
=0
X2
Proof. In EstG, for each g(A) being evaluated, the number of samples drawn from each of the K groups is
741GDK In(3)
384n In
mn
(43)
0.01
By Lemma B.1 and Lemma 3.1, this value of mN sufficiently large so that with probability at least 1 |(()
4N- for all
i = 1,2,..., o the set 5(1) is a 0.4A--ominant set at ((0) Since
< Bx by Lemma 3.1, we have
max
s(t)
s Bx.
1.1.2....
Moreover, by Lemma C.8, any B((()
C ), st9 also dominnntt set follows that
st0)
80.2x.9
(44)
where we recall the definition of Bo.2x.0 being the size of the smallest 0.2X-dominant set 0. Taking the maximum over i on both sides. we obtain
3 = max
S(1)
1E(1.2.....
0.1A (())
:u.20:: E
max 1E(1.2..... |
max
G
max $0.2x.0
#20
Bo.2A
29

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
where the second equality (third line) is due Ô being cover of θ and the last equality is due the definition of 80.2A- We conclude that 2o.2x
Ax S 3x-
Finally, since my samples are drawn from each of K groups, the total number of samples needed to compute 3x is KmN.
Next, we define a function g: [0, + [K] as follows.
1 if <
((1)
EstG(A) i E (1, 25 ... [
(45)
((x) for = arg max <x:1E
otherwise
25
5 (
In other words, define g(A) 1 for any sufficiently small À that will never be called during Sol SolveOpt, which consists of values smaller than g For any À 2 glnas(?)) if À that belongs to the geometric sequence (1, 5 25. .......). )), then
((A) the output of EstG with input A. Otherwise, (A) is equal to the output 3, of EstG with input x which is the first value in the geometric sequence that is smaller than X. Let
5 go
Knin ln
(46)
In(K/8)
and
C 9(A) f(A) X2 2
(47)
We have ă(A) E [1, K] due to the fact that DominantSet always returns a non-empty subset of [K]. Moreover, Ć > K. The following lemma shows that with high probability, this function g(.) is non non-decreasing.
Lemma C.10. With probability at least & the function defined in (45) is non-decreasing.
5 3 within the range [0, we have O(A) = which is never larger than any possible returned value by EstG. Therefore, we only need show that Í(A) non non-deccag for > 5 To this end, we will prove that 0 - ((A) for any value À in the truncated geometric sequence (1, 5 25 ......... glaes / ). This trivially holds for the last
Proof. Since S
value Aast
this sequence, since by definition ÿ( )سي 1 and the returned value of EstG is always greater
(ox5(())
than or equal to 1. For other in this sequence, let = = 0.2X. Observe that the number of values this truncated
geometric sequence is at most
2 < In
logs
= N,
hence we can apply Lemma C.9 and take union bound (over most N values of the truncated geometric sequence)
to obtain that with probability at least 1 /. we have g(X) Bx I 3x Bo.2x 21 and Bo.2x < B3 simultaneously for
any À Ajast- We conclude that g(X') < 20.2x I B3x = ((A) for any X/5 and À < 1 in the geometric sequence
(1, 5. 25 ..... Furthermore, this implies that for any pair (X, A) where X' S À from this geometric sequence, we have 6(X) (()).
More generally, for any 0 < 1, we have three possibilities:
if y 1. then g(x)= g(v) =
i S 2 < y. then g(x) S g(v)
30

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
if 3 < x, then
g(x) - 5 (1oog((11
S 9
[1
= g(y).
In all cases, g(x) & gly). We conclude that the function is piecewise-constant and non-decreasing.
Lemma C.10 indicates that with high probability, the function defined in (45) satisfies the conditions of the optimization problem (10), thus enabling the use of Solve veOpt (Algorithm 6) and Theorem C.3. From Lemma C.9, taking union bound over all queried À throughout Sol veOpt. and note that there are at most N such À by Lemma C.7, we immediately obtain the following result.
Corollary C.11. Running Solve veOptttt (Algorithm 6) with (()) defined in (45) guarantees that with probability at least 8/2, simultaneously for all X queried in SolveOpt, Est G (Algorithm 7) returns value Bx such that Bo 22 S 33 8x-
We are now ready prove Theorem 4.1.
Proof (of Theorem 4.1). Let
Knln (n(/ee))/))
(D&G² + 3x) In(K/o)
X = arg min xe(0.1]
(48)
X2
2
We run SolveOpt for solving OPT(Ć,)) .) and obtain as an estimate for 2².5 Theorem C.3 and Corollary C.11 implies that with probability at least 1 2. the returned value Å is element of the geometric sequence (1, 5: :.....) and satisfies f(Å) < 50 which is equivalent to
1())
+
X
2
22
2²
< 50
(X2 (28 p
,
(49)
Ô
((A²)
S 50
(A+)2
3x-
< 50
(X+)2
2
where the second inequality is from the definition of C..g and the last inequality due to g(x*) = ((x.) S Br. S Bx,, A² Moreover, the number of samples needed for running Sol veOpt most
where v. Toggs 17
o (f(ee.))
0 () [l((K/0)l((11e))
+ 9(A²)
In (n(K0))mmL//))
(1-ys
2²
(50)
00
+
Bx.
In In(K/))(n(1ee)
(1-y3
31

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 9 SB-GDRO-SA adaptive and computationally efficient approach without knowing any Input: Constants 2 2, D, > 0, Compute constant C K In CDX
> 0,
ln()76)
Initialize A 1, L, = VV [n(
Initialize 8 arg men (18112)
Initialize 81 2. counter C1
384n In 74
Draw set of samples V1 of size Km1, where mi
0.01A
for each round t = l,..., .....,d do
Min-player plays 02 Compute -.4Ai-dmmnaan set St (ominantSet(O,,) Vi, 0.7Aa) Og using Algorithm 3
if |S,] In(K) and d 2 L then
Increase counter C++1 Reduce A4+1 + d
+
Reduce det1 +- =
66.
384n 141GDK 22
Draw a new set of samples Vi+1 of size Km,, where my
0.01 11
else
Set det1 + de, Vi+1 V/, and deti 8,, c++1 Ct.
Compute Qi (1,
Draw is -6 and 24,, Pir
Compute 01-1 MinP zi(.t) Return: ET 8r.
In each round of the two-player zero-sum game in SB-GDRO-2, the dominant set used by the max-player is taken to be the pre-computed 0.42-dominant of the center e closest O,, where {1,2, }:
0 060./.
C = arg min
1,2
As result, the sizes of the dominant sets used by the max- player never exceeds 3x. Together with Corollary B.5, this implies that with probability at least - 6/2, the number of samples used by the two-player zero-sum game in SB RB-GDRO-1 A is
(D&G + (n)
(51)
2
Finally, combining (50) and (51) and taking a union bound, we obtain that with probability least 1 8, SB-GDRO- returns e-optimal hypothesis with sample complexity
Kn In (6)
GD& + (xx))l((K(6)
In(1/0)=
(52)
(X+)2
2
C
DPG² + 3x
In(K/8)ln(1/e)
(53)
(2t)2
Kn In GDK [n(K/o]
where C'
and we dropped the In(In(1/e)) term in the final bound for case of exposition.
C.3. Proof's for Section 4.2
The detailed procedure the computationally efficient approach SB SB-GDRO-S2 given in Algorithm 9. Similar to SB-GDRO (Algorithm 1), SB-GDRO-SS SA uses the two-player zero-sum game framework. The main difference
32

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
that SB-GDRO SA does assume any input A. Instead, it uses À from the geometrie sequence (1, 3 J.......... A new value of A in this sequence is used for computing the dominant set in round 1 if both of the following conditions hold:
The size [St] of the dominant set in round / is larger than In(K)
The value of X used in round is not smaller than I. = <V In(K)
C
If at least of the conditions does not hold, set de+1 Ar- Whenever new value of X is used, i.e., either & 1 or X + Ac-1, new set of samples of size m is drawn from each of K groups. The value of m is set by Lemma B.1 and Lemma 3.1, that is m, In Z41GDK
Here, the failure probability 6, is set by geometric sequence of the form (recall that å is the global failure probability of the algorithm)
0.01A7
36
(54)
EE 1(,
)
so that the total failure probability of computing the dominant sets is bounded by
2
36
20
6 2
Σ
8,1 X
(55)
Note that we define Ào 1 by convention, so that A A--1 holds for 1. We will prove the following theorem, which is more general than Theorem 4.2
Theorem C.12. Let C Kn (_ax) and L V
miky For any c 0,5 (0, 1), with probability at least
8,
(n(K)6)
SB 2D-GDRO-SAL SA (Algorithm 9) returns an e-optimal hypothesis with sample complexity
o ( (D'C + mmxx(I((K))))))
In lm(K/5) B1)) 2)
(56)
2
Obviously, Theorem C. immediately implies Theorem 4.2 since By S 3x- for all L < X
Before proving Theorem C.12, we first prove a lemma showing that the sets S, in all 1,2,... . rounds are indeed 0.4X--domiant sets with probability 6/2.
Lemma C.13. With probability at least 1 5 domiinntt set at 9r.
2' SB-GDRO-SA (Algorithm 9) guarantees that for all t 2 1, the set S, is
Proof. Fix a À in the geometric sequence (1, 1, .... Let and t' be the first and last rounds in which À is used for computing the dominant sets, respectively. By Lemma B.1 and Lemma 3.1, m, is sufficiently large so that with probability least & for all the rounds from to 1', the set S₁ for h = 1, 1,.... l' is 0.4A-dominant set of 0,, By construction, Taking union bound over all À in the geometric sequence (1, 2 4....) and using L.
2 35
6; 1
Σ
1
n²
52
6
s=1
obtain with probability at least Exe 8,111, X=-1) 2
2. the set S, is 4.4A-ddmmnnnt set at 0g for all
t t 1.
The next technical lemma helps bounding the sum Σ m, # A
and C Kn In CDK
Lemma C.14, Let 8
For any xf E (0, 1), we have
ln(K/8)
[- logg(z)) (x)
GDK
1
1 In
Kn
In
π
< 22C'nn(K8))n In
+ 0 Kn In
In
36
#=1
33

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Proof. Without loss of generality, assume 1/2 is power of We have
(x))
In(a)
GDK
GDK
π
In
In
+
In
+
In
(22)
30
3
==1
Infa))
- 2l
GDK 8
In
1
+
In
II s=1
s²
(57)
1
= =2In(K/00
+
0
In
In
In
where the inequalities are from (1/a(1/)) < ln(1/x) and in(n)) On In (n)).. Multiplying Kn to both sides leads to the
desired statement.
We are now ready prove Theorem C.12.
Proof (of Theorem 12).). Let Aun x be the largest such that 3x II((K). no such À exists, we set Am K = 0. Let
A max(L, (m)) Note that X L ====c CV ln(K) > since C' K > In(K).
In the worst case, Algorithm 9 draw new set of samples until 1 2 < A S X. Without loss of generality, we can assume
< 1. Otherwise, Algorithm 9 draws only three sets of samples and stops doing so immediately after some X 2 3. which
trivially leads to sample complexity of O G (='D++l((K)
With Ā < 1. the total number of samples of used for computing the dominant sets in Algorithm 9 are
log (*)
Σ 11> + A-13
384Kn In (711GDK/6)
0O
Kn
Σ In
(2GKK)
0.01X;
81
C
(58)
<0
ln(K/0) In (110)_n((1//) 1m(1/x)
x2
0
ln(K/o) (n(K/))ln(L/e)) In(1/e)) x2
where the second inequality is from Lemma C. and the last inequality is from À > 6. Note that we dropped the In (nnnn)) for ease of exposition.
Next, we bound the regret bound of the max-player. Let 3 max(In(K), We show the average Br = 7 ET | not much larger than B.
T
T
|SA
[1[8/]] > 3) +11811
|Sa
T
t=1
t=1
1[1::] > 3}K 11s1 < β3B
$ T
(59)
1 -
$ T
K logg
+ 31
(2BT) loga logg (1/X)
< T
< 29 In(e))),
where the first inequality is from [S,] < K for all f, the second incquality is because there are at most log2( (+) rounds where
|S&| B. the third inequality is from < 3T as / 1, and the last inequality is from (1/2( S (1 as Ā > e.
34

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 10 SB-GDRC-DF: Dimension-Fin freee SB-GDRO Algorithm with known (A, 3) Input: Constants K, D. G, The, A.B, 0, hypothesis set θ C R" Compute O (DAG* + (
Compute the maximum length of each episode o
0. Ga
Initialize episode counter /
Compute m' 24 487
X²
Draw m' samples from each K groups into set V1 Initialize 81 arg me |00|2
Compute a dominant set 5t = Dominantset(01 V at 0, by Algorithm 3 Let Sg, S
Compute = (0,, Sw,) by Algorithm for each round t = ,...., do
Draw group ~ 9t and sample s,,t Pi. Compute 0c-1 MinP =,,,t) by Algorithm if è is divisible by then
Increase episode counter + p ++1
Draw new m' samples from each of K groups into VO, Compute dominant set 5 = Domi namiinttttet:r:: VP, A) at 0,41 by Algorithm 3
Let S0 =
Compute qt+1 MaxP Maxp(01+1) (0t+1, Se.4.) by Algorithm 2 using the last computed S
Return: Σi= 8, and q = Ei=1
Combining this with (35), the regret of the max-player is bounded by
RA, 00
T3r (n(
(60)
=0 (T3
Plugging (60) into (33) and combining with (58), we have the total amount of samples to get an c-optimal hypothesis is
o ( (x)
In(1/e)²) +0
(G=D* + ln(K/))
Im(1/e)
(61)
2
o ((min [n(K) C (D2G² + max(In(K))Bi))) ( In(K//)) (mn) 1 -)) 2 Xm((K)
(62)
where the inequality is from Ā max()In(K)) L) and
C
In(K)
thus
1/
sc
c min
C
In(K) C
< min
(1)²
12
XB(K)
X2
II(K))
Since
min
lu(K)
X
la(K)
max(lu(K).9r)
the final
bound
can
simplified to
GD mmx K),8.)
ln(K/)) In
D. A Completely Dinension-Inneepedeer Approach
First, we give a detailed description of SB-GDRO-DE (Algorithm 10) and prove its sample complexity bound in Theorem 5.1. Essentially, GB-GDRO-DF also uses the two-player zero-sum game framework similar to SB-GDRO. Note that since
35

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
known, we can compute the number of rounds T = O D( D" before the game starts. Unlike the previous
algorithms, knowing T' before the game starts allows us to use a fixed learning rate
2D
qu, = 7) GVT
(63)
for the min-pian player in Algorithm 10. Another difference that SB-GDRO-DE proceeds in episodes, each consists of multiple consecutive rounds, and the max-player uses the same dominant set for the rounds within each episode. More concretely, in SB-GDRO-DE, the T rounds of the game are divided into I episodes, each is of length o, except for the last episode which may have fewer than rounds if T is not divisible by a. The value is defined as follows:
0.1A
(64)
The
By this construction, the first episode contains rounds 21. σ), the second episode contains rounds (or + 1..... 20r) and so on, until the last episode which contains rounds (1 o + 1..... T). Let p 1.2...., a the episodes. Within an episode p.
[ be the running index of
Before the first round of this episode, a set VP of Km' samples are drawn from the K groups, where m' i.i.d samples are drawn from each group. The value of m' is In( 48T)
Let 12 be the index of the first round in episode p and 0P = Oer be either the initial hypothesis (if p 1) or the hypothesis played by the min-player using the algorithm ni np (Algorithm 4) (if p 1) in round 1P, A 0.4X-dominant set SP is computed using Dominant (Algorithm 3) with input OP and VP.
In rounds L. E (1P, 10 + 1,.... min + a, T)) of this episode, the max- max-player plays q: using the algorithm MaxP (Algorithm 2) with the same input SP. Then, a group i, qr is drawn and sample Zi.,t ~ Pi, is drawn from group i, The min-player then follows the MinP strategy (Algorithm 4) with input 8, and 2i, to compute B,+1.
The algorithm returns 0 = Et Og after T rounds. The following lemma shows that for any episode p. with high probability, So is a 0.4X-dominant set at 0P.
the set S is a dominnnmn Lemma D.1. At the beginning of episode p in SB-GDRO-DE, with probability at least 1 - ab 27 set at 6'.
24 4KT
Proof. In each episode p. we draw m' we have
samples from each group. By Hoeffding's 's inequality, for each group
X2
m!
Pr V
{OP, V2,)) - (PP)
2 0.15A
S 2exp ( mm0.44X2mm))
m
4KT
= 2xxp
-1.08 In
σō
[KK
2exp
In
σō
a5 2KT
By taking a union bound over K groups, we have
m'
110 V2,) - RR((P) S 0.15A
(65)
j=1
holds simultaneously for all & [K] with probability least 1 Ex in (19) of V in Lemma B. Hence, we can apply Lemma 3.1 and conclude that with probability at least set S is a 0.4X-nominant set at AP.
g8
The condition (65) of VP is the same as the event
27'
27 the
gg
36

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
The next lemma shows that the set SP is dominant set not only 0P but also at the hypotheses within the episode p. Lemma D.2. SB-GDRO-DE guarantees that if is a O.4X-dominant
fu some [T], then for any non-negative
integer o' S min
{
0.1A G=
T -t t... S is also a 0.2X-dominant set at Oz40"
Proof. SB-GDRO-DF uses the update rule (5) to compute Oc+1- This update rule can be written as follows:
0++1
arg min 2 (Wh.t. 0 0z) + 110 0.11 + n |l
lice
arg min { 0e - Bwett - 0113}
which is equivalent to projecting 02 - 9w onto the convex set Q By properties of projection onto convex sets (see e.g.
Orabona, 2019, Proposition 2.11), for any 1 S T, we have
|0++1 - 0.ll - 11( - mhatt) 0ell
The 19
(66)
S G,
where the last inequality is |gell < G by the Lipschitzness of the loss function f. Combining (66) and triangle inequality, we obtain
10:+o' - 0z1 < 110+0 - Octor-110 |1 + 00+0r-1 - 0zll
Outoo 0 1 + 00tto 02to' 211 + ||0+11 0g
of elements
S G'moG
0.1A
G
where the last inequality due to o' that if set is 0.4X-dominant at 9r, then it also 0.2A-dominant set at the hypotheses 0141, .... ................................ Octo played in subsequent rounds of the game.
<
0.
0.1A This implies that Octar E B(,,, (dA). By Lemma C.8, it follows
G=
GT
Finally, show the proof of Theorem 5.1.
Proof (of Theorem 5.1). Since the maximum number of rounds in each episode is S Combining Lemma D.1, Lemma D.2 and taking a union bound over T episodes, in total we draw
Th Gr there are at most T episodes.
0.1A
o (
Ya KTG In
KT 08
(67)
samples over I episodes to guarantee that with probability at least 1 all the computed sets over I episodes are dominant sets at (,,)..1, with sizes no larger than Bo.4x. Plugging Yur CVT obtain a sample complexity of order
2n and a 0.1A
0.1AvT
into (67), we
Cr
2DC
KDGVT DKG/Tm
o MoKTG In
KT
(68)
A3
From Corollary B.5, we have - 0 (D2 (000=G*+))n(KK)))) (m(//6) is sufficient for obtaining an coptimal hypothesis with probability at least 1 6
2- By plugging T 0 (D' (D (0)0+))(//))))))) ln(K/8) into (68), we obtain the number of samples collected for computing
the dominant sets over T episodes is
DKGV (D + B) In (K///) In KDG
(69)
Ale
37

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Algorithm 11 FTARL: Follow the regularized and active leader with a-Tsallis entropy regularizer and time-varying learning rates for sleeping bandits
Input: K 2 2. a-slllis entropy function (b))) Dis
Initialize Iı,0 = for all arms E [K]. for each round = I,..., do
The non-oblivious adversary selects and reveals Pa. Compute qt arg ae (2e(9) + (q, Lt-1)
Compute Pitt = 1,, by Equation (26)
Draw arm i ~ and observe &, = -i,,
for each arm E [K] do
If 1, 1, compute Es,t = lih=ij
P.,tte by Equation (27)
If 4.+ = 0, compute l,, = le Ejen, Eoe by Equation (28)
Update L,, Li + E1,
In addition, each of the rounds uses exactly one sample to compute the outputs of the two players in the next round. Hence, with probability least 1 6, the total sample complexity of the two-player zero-sum game needed return an e-optimal hypothesis is of order
O DKGV ()))k((8)))
In
KDG EAM
(D + BB) B)) ()(K///))
A
2
E. FTARL with Time-Varyinn Learning Rates
We consider variant of the FTARL algorithm in (Nguyen & Mehta, 2024) with time-varying learning rates. The procedure is given in Algorithm 11. The only difference between this algorithm and the FTARLSharnon algorithm (Algorithm 5) is that Algorithm 1l uses the a-Tsallis entropy regularizer compute the weight & follows:
q: arg min (2((g) + (q. L,-1), ςε
(70)
where ()(4)) = (k()) mii)mmin st(e) for (q)) = レーΣ of and a E (0, 1) is constant. The computation of the sampling I-a
probability and the loss estimates of active and non-active arms Es,t are identical to that of FTARLShannon. Since the a-Tsallis entropy tends to Shannon entropy when a - 1 (see c.g. Nielsen Nock, 201 1), we will prove the following high-probability per-action regret bound of Algorithm 11 and then take the limit a > to obtain Theorem B.3.
Theorem E.1. Let (M.))=.... and (=,.)= be sequences of non non- increasing learning rates and exploration factors such that < 2nh With probability at least 1 - 8, FTARL (Algorithm 11) guarantees that
max Regret(a) kE|K]
K
ln(3//8)
( (1+8 (1+1)
In(3/8) +
1)t +
70
At
1T - a)
2yT
2a 2
2a
Before proving Theorem E. similar (Nguyen Mchta, 2024), we state the following results on the concentration bound of the IX-loss estimator. These results are adapted from Neu (2015, Lemma and Corollary 1) in the non-sleeping bandits setting to the sleeping bandits setting with nearly identical proofs.
Lemma E.2 (Lemma of (Neu, 2015)), Let (Vr,)) be non-negative random variables satisfying Vi, S 2n for all i E [K] and / 2 1. With probability at least 8',
T
K
ΣΣ tl
Mellllie > 0](,, lx,)) S Im(1/8)..
38

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Since the sequence (1..= is non-increasing, have "Yr S Tt for all i T. Hence, for any fixed E [K]. can apply Lemma E.2 with Vi,t 2 (i a) I 27, and take union bound over K arms obtain the following corollary. Corollary E.3. With probability least 8', simultaneously for all a E [K]
T Σ
In K//))
Ja,lEa.t S
2/r
We turn to the proof of Theorem E.I.
E1,1
l,,
Proof (of Theorem E.1). Fix an arm a E [K] and let ea be the a-th standard basis vector of R Let &
be the
[
vector of estimated losses of K arms in round t. Since the sequence of learning rates is non-increasing and positive, we have (x(xr) 2 and 1 (x) 2 (x) for x E Åx. Hence, we can invoke the standard local-norm analysis of FTRL with Tsallis entropy regularizer (e.g. Orabona, 2019, Lemma 7.14) on non-negative loss estimates (L,)t= obtain
T Σ
T
K
(,a ea) S (eat)(ea) min (x) SEAR
+
2-a
(71)
20
t=1
Following the proof of Nguyen & Mehta (2024, Lemma 26) and by definition of &o we obtain
(Ee, 96) = Σ ts,e +
Σ
iERn
igtte
-ly + Σ
igRs
= -ii +
-
Ea
Σ
Ejjt
Σ qiet
JEAL
iET
Σ Gitt
la 12-7 7t Σ
Egjt
Σ ti
iERs
jER,
igeTae
Σ E3.t
7t
Vi.t
JERL
l
E5.00
JER,
where the second equality is due to l., 0 for i Pa,, i + in the third equality is due lu, = lo 7/t Ejes, Eg for all non-active arms & A,, the second-to-last equality is due
Ph = le
= le - -llene = -1--- - Eig nile Pta,t +
Pia,t + 7
JER
and the last equality is due to g Ak. Plugging this into (71) and using (ée, ca) = Lu,t implies that
K
i - 7t El4
la,t
S
min (x) +
7/
1
zEAx
2a
JEAn
39

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
By the definition of the loss estimate for non-active arms in (28), in the rounds where a.. O, we have 4e-7 EyER, lj
ta O. It follows that
T
Ia
4-
l
Ebee
E5.0 Eaie = =
4- 71
Σ
Eai
JERL
JEa,
(72)
T
1
S SiT+I(ea)
min 121(2)
1/t
k.
2a
1=1
i=1
By the non non-tegativity of the regularizer function, we have
(ea)
min (2)))) = (T+i( #EAx
1
(((a))
min vi(o) "EAx
Kl K1-a-1
7T
where the third equality is from (eea) 0 and milleedg v0()) -
1-K1 I-a by properties of Tsallis entropy function (Aber-
nethy et al., 2015). Since the round T + does not contribute to the total regret, we can set M/++1 = and obtain Furthermore, by Lemma 10 in (Nguyen & Mehta, 2024), for all t 1,
(T+i(ee) m 1i (x)) z
K" k'---1 hr(1-a)
K Σ
Pip 2-a I DBpPP
jEa,
It follows that the right-hand side in (72) can be further bounded by
T
Kl-a -
Σ 1a.t
-
la
Eait
1/t
j, Jit.
1/7(1 (k)
jER,
JEN
Kt-a
Σ
8
1 j.t
1-a
1/
mr 0))
20
JEAL
K
Σ 1/1
(r 0x)
where the second inequality is due Eg.1P5,1 ba(1=//pss < for j A, and the last inequality is due to p/.-" < Pstt
for Pj. E [0, 1] and a E (0, 1). Moving Σt= Ia, Ejer,
E to the right-hand side and using Ia,t S 1, we obtain
T
K1-a la. Raat) S 1)((1 a.)
T
Σ
+
The
To
Σ
(73)
2
jER,
We then apply Lemma E.2 twice and Corollary E.3 once, each of them with 8' uses Vie S 2% and obtains with probability at least 1 - 8/3,
3. The first application of Lemma E.2
Σ m ΣE
S In
7
Σ
7t
(74)
jER,
JER,
The second application of Lemma E.2 uses Vi,t 27, and obtains with probability at least - 8/3,
T
T
2%
Σ 10 <
In
3
2
lie-
(75)
8
1=1
jERs
1=1
JE
40

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
An application of Corollary E.3 leads
ln(3K/6)
T
Σ Ialut S
+
Σ
Ialott
(76)
2/T
t=1
with probability at least 8/3. Plugging (74), (75) and (76) into (73) and taking a union bound, we obtain that with probability at least 1 - 6,
T
Kl-a In(3K/6)
T
(ee - ka,1)
+
+
In
(m30/)
+
1Jt
+ 71
Σ
Ege
(1 ())
2Tr
2xx
2
2a
t=1
JEZL
S 1T (1 - -x)
K In(3K/6)
+
+
1
In(3/8) + Σ
T
1/t
+ 71
Ac:
2yr
2xx
2
2a
1=1
holds for simultaneously for all E [K], where the last inequality is Ejez, Ess S EjeR, 1 = Ar.
Finally, we prove Theorem B.3.
Proof (of Theorem B.3). Since Theorem E. holds for any a arbitrarily close to 1, we can take the limit of a to on the right-hand side of its bound and obtain the desired bound in Theorem B.3:
max Regret(a) S
In(K)
In (3K//)
+ In(3/8)
+
Σ
T
Th Ar.
+
7e)
(77)
[E[K]
1/r
2
2
t=1
F. Stochastic OMD with non-increasing, time-varying learning rate
(Zhang et al., 2023) lamented that they could not find analysis of stochastic mirror descent for non-oblivious online convex optimization with stochastic gradients, and they therefore proved their own high probability result. Their result uses fixed learning rate, whereas we would like to avoid needing knowledge of the time horizon T and therefore will describe how one can trivially (in light of known results) extend their derivation to the case of a non-increasing learning rate. All that is needed to extend their upper bounds in equations (40) and (44) in their work to the case of a non non-increasing learning rate Tw (so that 7w,t+1 S Te for E [T). Such an extension is for free using, e.g., Theorem 10 of (Orabona, 2019). All other steps of the proof of Theorem (Zhang al., 2023) can proceed without any important modifications, including the application of the HoeffdinggAzummn inequality. Here, we just highlight few keyframes of the proof.
Using notation and with non-increasing learning rate sequence (Nw,))22 and applying Theorem 6.10 of (Orabona, 2019), the bound in equation (40) of (Zhang et al., 2023) becomes, for any 0 E O,
D2
G2
Σ (g 0, 8)
nw,t-
T
Fastforwarding to our analogue of equation (42) of (Zhang et al., 2023), we now get
D
G
max
gr) -(00 <
Nunt + max BE0
Tr. - 01
V Vod(O,,
Setting
1
0. arg min aee
Mw.t Vop(Or, ge. 0
0z)
0 0,
2

---

The optimality gap of hypothesis is Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
again apply Theorem 6.10 of (Orabona, 2019) to get the following analogue of equation (44) of (Zhang et al., 2023):
D2
(o)(B,. Tr. 0, -0) -
2G
nw
T,,T
t=1
All the remaining steps the analysis of (Zhang et al., 2023) go through without any interesting modification, giving the result that with probability least 6,
D
G 2
D
T
Σ cl 9
min lEB
@ (1)
nw.t
2G
nw + 8DG Tin 8'
n
Tw,T
where the last term is from applying the Hoeffding- Azuma inequality in precisely the same way in (Zhang et al., 2023). D
Using learning rate schedule of "hutt No avi gives the upper bound
+ 4mo + vnn 1 )) = DGVT
2
DGVT
+ 110 +
+ 5nj + v In
700
17u
which, letting 7/ = 1, gives
DGVT 7+ 7+ =o (((D (DC
desired.
G. Details of the Experiments
In this section, we provide the full setup details of the experiments presented in Section 6.
G.1. The Lower Bound Environment
For the GDRO problem instance constructed based on the lower bound construction in the proof of Theorem 3.5, we scale the loss by: to ensure that the losses are in [0, 1). This implies that for hypothesis E [0, 1]. its maximum risk over K groups is
L()) max A0 2. 4.1 -0) +0}+)
We set A 0.1. The optimal hypothesis is 0" 0.5 with L((") 11 0..27..
err(0) [()) _()')
0.05
With the desired optimality gap of e 0.005, the acceptable range the risk of 0r is [0.27, 0.28.. The set of e-optimal hypotheses is obtained by solving 0.05| 1 0 < 0.005, which implies that 0 [0.4, 0.6] is the set of c-optimal hypotheses.
G.2. The Adult Dataset
Loss function and data normalization. Similar (Soma et al., 2022), train linear classifier with hinge loss 2(0, y) max(0, y(0, 2)),
where E 1R5 is feature vector of a sample and E 1, is the label.
On the Adult dataset, the default value of the features could be much larger than 1, leading to loss values larger than 1. To avoid exceedingly large losses, we compute the maximum norm of all feature vectors in the dataset and then divide all features by this maximum norm. Note that the same maximum norm value used for all 10 groups
42

---

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
UCI Adult Dataset As mentioned in the main text, construction K 10 groups from five races White, Black, imo, Other and two genders ma 1 e, female. The dataset of 48 842 samples is heavily imbalanced. The largest group is (White, male) having 28 736 samples while the smallest group is (Other, Eemale) having 156 samples.
As an-aaa--sssss lnnder,,,
No batch processing. Our results in Section 6 are generated by the exact algorithms described in Sections 3 and 4 without adding any batch processing. This different from (Soma et al., 2022), who used a batch of 10 samples to stabilize the gradients. We find that as the dominant sets quickly converge to just one or two groups, especially the groups with small amount of samples such as (Amer Indi an Lon-Eskimo, female), , the gradients computed from just one random sample sufficiently stable with the long horizon of T 10
Computing (an estimate of) 0*. In order to obtain the optimality gap of SB SB-GDRO- SA and SMD-GDRO, we compute an estimate of ((0)) using the following algorithm: we run a deterministic two-player zero-sum game in which both players have full knowledge of (P.))=1,2....KK- In each round f, the max- max-player is able to compute a dominant set consisting of just one group - that is, the group with maximum risk on 0,. Similarly, the min-player given the expected value of the gradient Elge] instead of the stochastic gradients. We run the game for T 107 rounds and record the final maximum risk of 0r to be (((*) 0.49945. This final maximum risk of is observed be on group (i.e., female Amer-Indian-Eskimon
H. Discussion of the Competing Approach in Stochastically Constrained Adversarial Regime
Our approach to going beyond minimax bounds in GDRO is based on the (A, (A,3)-sparsity condition and, algorithmically. based on the sleeping bandits framework. The expert bandit reader may wonder about the viability of the following competing approach: suppose that after some unknown time horizon т, all 0₂ fall within a radius-p ball of 0*, and within such a ball, further suppose for simplicity that unique group obtains the maximum risk in all subsequent rounds by margin of at least A. This setup generalizes the previously studied stochastically constrained adversarial (SCA) regime (Wei & Luo, 2018; Zimmert& & Seldin, 2021) wherein the best arm's mean is separated with a gap from the other arms' means for all rounds. In this generalized SCA regime, one might hope for better regret bounds for the max player than we achieve using our sleeping bandits-based approach. However, there are at least three major challenges: first, to our knowledge, it is not known how to get high probability regret bounds in the SCA regime even when т = 1; second, we are not aware of results that provide last iterate convergence so that, eventually, all iterates O, are within distance p of 0 (SCA requires such convergence); third, there could well be multiple best arms or multiple nearly best arms, which recently has been addressed in some different regimes but adds another layer of complexity for the generalized SCA regime.
As mentioned in Section 7, if we had last iterate convergence, then our (A, -spaarsity condition could be relaxed to hold only within some proximity of 6* However, our condition is more flexible as compared to SCA since it is not known how the latter can be analyzed when the best arm (or set of best arms) changes throughout the game, whereas such a changing set of approximate (within gap X) maximizers fits naturally with sleeping bandits.
43


Reviews:
[{"review_id": "HMxK912u7d", "reviewer": "Reviewer_K8N8", "summary": "In this paper, the authors revisit the problem of an optimization framework where a single hypothesis is chosen to handle a group of K risks associated with K data distributions - this framework is known as GDRO. While minimax rates have been established for this problem already, the authors provide a finer-grained analysis of this problem in terms of a characteristic feature of the K groups at hand known as $(\\lambda,\\beta)$ sparsity. The authors provide novel algorithms based on sleeping bandits to provide improved problem dependent rates.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n# 1. $(\\lambda, \\beta)$-sparsity for linear regression with linear Gaussian model.\nFor 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.\n\nWe now show our construction. For any group $j$:\n+ we assume $X \\sim \\mathcal{N}(\\mu_j, I)$, as suggested by the reviewer;\n+ for $Y$, we assume $Y \\sim \\mathcal{N}(\\langle \\theta^*_j, X \\rangle, 1)$.\n\nWe 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).\n\nNext, 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. \nWe 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}.\n\nTo 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.\n\n# 2. Why can the algorithm choose the distribution to sample from?\nOur 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.\n\n# 3. Intuition on the players' regret bounds and sample complexity.\nIntuitively, small regret bounds of the two players imply a small bound on the optimality gap of the final output $\\bar{\\theta}_T$. \nThe regret bounds of the two players depend on the number of rounds $T$ of the game. \nSince 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. \n\n# 4. Is it possible to use some kind of meta-algorithm?\nWithout 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.\n\n**References**\n\nSagawa et. al., 2020. Distributionally robust neural networks. ICLR 2020", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No, I did not through the proof details carefully", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The literature has already been covered well in the paper", "essential_references_not_discussed": "None to best of my knowledge", "other_strengths_and_weaknesses": "The paper has strength but there are certain weaknesses outlined in the questions section", "other_comments_or_suggestions": "See below", "questions_for_authors": "While the paper was very interesting to read I have some questions and most likely, better explanations can help the flow of the paper. \n\n1. My first question is how can we characterize the non-triviality of a group (Definition 2.3) given a set of K distributions and a set of parameters $\\Theta$. Can we design an efficient algorithm for the same? For instance, I can think of the linear regression problem in n dimensions where the prior distribution of covariates has K possibilities N(\\mu_1, I), N(\\mu_2, I), N(\\mu_K, I). For a feature vector x, the output y is simply N( < \\mu, x>, 1). How can we know the $\\lambda,\\beta$ for this setting given \\{\\mu_i\\}? I am worried that in most situations, $\\lambda,\\beta$ is trivial. Please convince me otherwise.\n\n2. Why is it that the algorithm designer can choose the distribution from which the data can be generated at each round? When is this applicable? I understand that this allows usage of bandit techniques but I am failing to see a real world situation when this is applicable. \n\n3. In L103, what does two dimension-dependent bounds mean? \n\n4. Can the authors provide intuition on how the individual regret bounds (eqs 3 and 4) relate to the final sample complexity? it is not immediately clear. \n\n5. For unknown $\\lambda$, is it possible to use some kind of meta-algorithm? For instance, perhaps we can use corralling algorithms outlined in \n\nAlekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pp. 12–38. PMLR, 2017.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mn6aBhob2O", "reviewer": "Reviewer_4vrz", "summary": "This paper considers a practical setting of the group DRO problem called (lambda,beta)-sparisty, which means for any parameter there is a set of at most beta groups whose risks are all at least lambda larger than the risks of other group. By taking this condition into account, the authors can derive sharper complexity bounds for this problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time on our paper. Please let us know if you have any questions.", "claims_and_evidence": "Yes. The authors provide rigouosu theoretical justification and provide intuition by drawing the connection with sleeping bandits problem.", "methods_and_evaluation_criteria": "Experiments are conducted on a synthetic dataset and the real-world Adult dataset with fairness applications.", "theoretical_claims": "I do not check the technical proofs in detail, but it seems that the theoretical claims do not contain mistakes.", "experimental_designs_or_analyses": "Yes. The experiment designs follow existing literature and make sense.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7zuYoT8XFH", "reviewer": "Reviewer_6PQC", "summary": "This paper studies the GDRO problem where a special structural assumption called $(\\lambda,\\beta)$-sparsity is satisfied. This assumption requires that for any hypothesis $\\theta\\in \\Theta$, only $\\le \\beta$ distributions have a \"large\" risk, which is quantified by the parameter $\\lambda$.\n\n1. Given any $\\lambda$, let $\\beta_\\lambda$ be the smallest $\\beta$ s.t. $(\\lambda,\\beta)$-sparsity is true. Then an algorithm with SC $\\tilde{\\mathcal O}(\\frac{Kd}{\\lambda^2}+\\frac{\\beta_\\lambda}{\\epsilon^2})$ (omitting a bunch of factors) is prosed.\n2. Without knowing $\\lambda$, a fully adaptive algorithm that automatically finds the \"optimal\" $\\lambda^\\ast$ is derived. Resolving the computational efficiency issue, a semi-adaptive algorithm that attains asymptotically best SC is derived.\n3. Finally, an $\\Omega(\\frac{\\beta}{\\epsilon^2})$ LB is given.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their critical feedback. Please find our clarifications to your concerns below.\n\n# 1. The techniques in Algo 1 looks relatively straightforward\n\nWe 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.\n\nWe 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.\n\n# 2. The sparsity definition lacks justification\nWhile 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^*$.\n\n+ 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. \n    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$. \n    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).\n+ 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). \n    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.\n+ 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.  \n    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.\n\n# 3. This paper only focuses on the convex GDRO setup.\nWithout 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.\nIn 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.\n\n**References**\n\nZhang et. al. 2023. Stochastic approximation approaches to group distributionally robust optimization. NeurIPS 2023.", "claims_and_evidence": "Yes, the proofs are sketched clearly", "methods_and_evaluation_criteria": "I'm not sure whether the $(\\lambda,\\beta)$-sparsity notion is well-justified. But other than that, every comparison with previous work is fair.", "theoretical_claims": "I only went through the sketches.", "experimental_designs_or_analyses": "The two experiments look good from a theoretical perspective.", "relation_to_broader_scientific_literature": "It could be of interest to the more general VC dimension case", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:\n\n1. The organization of this paper is pretty clear. Motivations and overviews are well-written.\n2. The adaptivity to $\\lambda^\\ast$ is pretty good.\n\nWeakness:\n\n1. The techniques in Algo 1 looks relatively straightforward given the $(\\lambda,\\beta)$-sparsity definition (basically what people do for sparse linear bandits). The two-player max-min game framework is standard in GDRO, and the sleeping bandit part is a direct application of a recent paper.\n2. The sparsity definition lacks justification. I understand that the bound is always tighter than $\\mathcal O(\\frac{K}{\\epsilon^2})$ as $[K]$ is $(1,K)$-sparse, but it doesn't really infer that $(\\lambda,\\beta)$-sparsity is the \"correct\" notion.\n3. This paper only focuses on the convex GDRO setup.", "other_comments_or_suggestions": "No", "questions_for_authors": "See Weaknesses. My overall concern is that, while $(\\lambda,\\beta)$-sparsity is a valid notion, it is unknown whether it is the \"right\" one.\n\n---\n\nScore updated based on authors' clarification.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lYbit0Lh9N", "reviewer": "Reviewer_S1YD", "summary": "The paper discusses the group distributionally robust optimization framework. They propose a new sparsity measurement of the distributions called $(\\lambda,\\beta)$-sparsity, and show that the dependence on K (the number of distributions) can be reduced to log K.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for raising great points regarding the practicality of our $(\\lambda, \\beta)$-sparsity definition.\n\nWhile 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^*$.\n\n+ 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. \n    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$. \n    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).\n+ 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). \n    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.\n+ 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.  \n    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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I don't check the details of the proof in the appendix, and I don't find any issues in the general framework of the proof .", "experimental_designs_or_analyses": "The setting of the experimental is reasonable. But, the author shows that $(\\lambda,\\beta)$-sparsity condition holds for parameters around the optimal parameter in Adult dataset. Is it possible to show the sparsity condition holds for all parameters in this case? Or, in the other hand, if the sparsity condition only holds for the parameters around the optimal parameter $\\theta^*$, does the theoretical result still hold?", "relation_to_broader_scientific_literature": "The results theoretically prove that when there is significant ''gap'' between the distributions, the sample complexity to find a good parameter can be largely reduced w.r.t K. This is an interesting finding.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths\n1.\tThe technique shows that there exists interesting relationships between the problem and the sleeping bandits framework.\n\nWeaknesses\n1.\tIs there any motivation to show that $(\\lambda,\\beta)$-sparsity is reasonable in the practical problems? Especially, $(\\lambda,\\beta)$-sparsity requires that for ''arbitrary'' parameter, there exists a small set of distributions whose risk are much larger than the risks of the other distributions. This seems a very strong assumption.", "other_comments_or_suggestions": "None", "questions_for_authors": "The main question I have is to what extent, the $(\\lambda,\\beta)$-sparsity assumption holds for the practical case. See \"Experimental Designs Or Analyses\" and \"Other weaknesses\" for the detailed questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies Group DRO in the form of minimizing the worst group loss. It considers a new notation of $\lambda, \beta$ sparsity structure. The authors have established several upper bounds, including when $\lambda$ is know and when the optimal $\lambda$ is unknown. While the paper has made some theoretical contributions, there are some minor concerns about the assumption, especially it requires the  $\lambda, \beta$ sparsity  holds for any model parameter. It would be great to only assume this assumption at the optimal model parameter. In addition, the considered formulation does not cover the top-k average group loss, which is more general. The authors are encouraged to cite and discuss some related work for optimizing the top-k average group DRO loss, e.g., Hu et al., Wang &Yang. 

Given the overall contributions of this paper, I will recommend acceptance. 

Hu et al. Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization.
Wang & Yang. ALEXR: Optimal Single-Loop Algorithms for Convex Finite-Sum Coupled Compositional Stochastic Optimization.
Decision: Accept (poster)