← All setups

Sparse Certificate Group Dro — Group DRO with Optimum Gaps

Descriptions may be stale. Consult the linked Lean sources.

Group DRO with Optimum Gaps · Lean proof

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.

Proved result

⌈512⋅(d+1)2⋅(log⁡(128⋅K⋅(d+1)ε⋅δ)+d⋅log⁡(8+4096⋅R⋅(d+1)2⋅(1+G)ε))⋅(∑i=0K−11(max{gaps(i),ε})2)⌉+

OracleTemplate.Convergence LongTails.Setups.OptimumGapGroupDro.spec LongTails.Theorems.SparseCertificateGroupDro.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.