← All setups

Group DRO with Optimum Gaps

Descriptions may be stale. Consult the linked Lean sources.

Group DRO with Optimum Gaps

We minimize the worst-group risk F(x)=max1≤i≤KEZ∼νi[ℓ(x,Z)] over a compact convex set X⊆Rd, where K≥1 is the number of groups, νi is group i’s sample law, and ℓ is a jointly measurable, bounded, convex, Lipschitz loss on X. Hidden lower bounds describe group-risk gaps at a common minimizer. The oracle returns a fresh sample from a queried group, with independent sample streams across groups. For accuracy ε>0 and failure probability δ>0, the goal is a measurable output x¯ always in X with F(x¯)−minx∈XF(x)≤ε with probability at least 1−δ.

Let d≥0 be an integer, let Z be a measurable sample space, and let ℓ:Rd×Z→R denote the loss. The norm ∥⋅∥ is Euclidean. An unknown probability measure ν on ZK has coordinate marginals ν1,…,νK. Define the group risks and objective by fi(x)=EZ∼νi[ℓ(x,Z)], F(x)=max1≤i≤Kfi(x), and consider the problem minx∈XF(x). The algorithm receives d, K, Z, X, a given point x0, the loss ℓ, and parameters R,G,ε,δ satisfying R≥0,G≥0,0<ε≤1,0<δ≤14. The group laws are accessible through sampling; the gap parameters γ1,…,γK are not algorithm inputs and may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Feasible set and loss). The set X is compact and convex, x0∈X, and ∥x−x0∥≤Rfor every x∈X. The loss ℓ is jointly measurable. For every z∈Z, x,y∈X, and t∈[0,1], 0≤ℓ(x,z)≤1,ℓ((1−t)x+ty,z)≤(1−t)ℓ(x,z)+tℓ(y,z),|ℓ(x,z)−ℓ(y,z)|≤G∥x−y∥.

Assumption 2 (Independent group reservoirs). The coordinate maps on ZK are mutually independent under ν. There is a probability law Q on reservoirs (Zn)n≥0∈(ZK)N such that the row variables Zn are measurable, mutually independent, and each has law ν. Writing Zn=(Zn,1,…,Zn,K), a query to group i returns Zm,i, where m is the number of previous queries to that group. The algorithm’s randomness is independent of the reservoir.

Assumption 3 (Optimum gaps). The parameters satisfy 0≤γi≤1 for every group i. There exists a common point x⋆∈X such that F(x⋆)≤F(x)for every x∈X,γi≤F(x⋆)−fi(x⋆)for i=1,…,K.

Each oracle call selects one group and returns one sample in Z; the budget counts the total number of such calls across all groups. After these calls, the output x¯ must be measurable and belong to X for every realization. Its required accuracy is P(F(x¯)−F(x⋆)>ε)≤δ, where P is the joint law of the algorithm’s randomness and the independent reservoir with law Q.

Results

Compact convex Q⊂Rd, x0∈Q, ∥x−x0∥≤R, R,G≥0; jointly measurable sample losses are convex, G-Lipschitz and [0,1]-valued on Q. Each call returns one fresh sample from a chosen group, with independence across groups and draws; stored samples may be reused. For K≥1, 0<ε≤1, 0<δ≤1/4, the target is Y∈Q with Pr{F(Y)−F(x⋆)>ε}≤δ. At some minimizer x⋆, 0≤gi≤Δi:=F(x⋆)−fi(x⋆). Gaps and x⋆ are not algorithm inputs; the setup imposes no method restriction.

Group DRO with gaps at a minimizer: OptimumGapGroupDro.
Result Oracle complexity Novelty Limitations
(1) SparseCertificateGroupDro (Ours) (⋆⋆⋆) (review) O((d+1)2L∑i=1Kmax(gi,ε)−2)
(2) SB-GDRO-A (Nguyen et al. 2025, Thm. 4.1) O([Kdlog+⁡(GRK/δ)(λ∗)2
+(R2G2+βλ∗)log⁡(K/δ)ε2]log+⁡(1/ε))
(1): Optimum-only gaps replace all-point sparsity for savings. For d=2, fixed RG, two active groups, remaining gaps Δ>ε, and βλ≥K−1: O((ε−2+KΔ−2)log⁡(K/(εδ))) instead of O(Kε−2log⁡(K/δ)log+⁡(1/ε)). No R2G2/ε2 term. (1): Polynomial dimension overhead, up to order (d+1)3 ignoring logarithms.
(3) SB-GDRO-SA (Nguyen et al. 2025, Thm. 4.2) O(R2G2+max{log⁡K,βλ∗}ε2
⋅log⁡(K/δ)log+⁡(1/ε))
K>1, εC/log⁡K<λ∗.
(1): Optimum-only savings; lower cost when (d+1)2L∑imax(gi,ε)−2≪(R2G2+max{log⁡K,βλ∗})/ε2, within (3)’s admissible regime. Removes polynomial RG dependence. (1) loses dimension-free sample complexity and polynomial runtime.

Abbr: fi(x)=E[ℓ(x,Zi)], F(x)=maxifi(x); Pr is the execution law. L=log⁡(K(d+1)/(εδ))+dlog⁡(2+R(d+1)2(1+G)/ε); log+⁡t=1+max{0,log⁡t}. βλ is the maximum over x∈Q of the smallest nonempty group set whose risks all exceed every excluded risk by at least λ. C=Kdlog⁡(GRK/δ)/log⁡(K/δ) and λ∗∈(0,1] minimizes C/λ2+βλ/ε2 in the cited parameter range. Costs count group samples, including adaptation. Taking gi=Δi gives the sharpest bound.

Nguyen, Quan, Nishant A. Mehta, and Cristóbal Guzmán. 2025. Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity. https://doi.org/10.48550/arXiv.2410.00690.

Lean setup