Descriptions may be stale. Consult the linked Lean sources.
Group DRO with
Optimum Gaps
We minimize the worst-group risk over a compact convex set
, where is the number of groups, is group ’s sample law, and is a jointly measurable, bounded,
convex, Lipschitz loss on . 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 and failure probability
, the goal is a
measurable output always in
with with probability at least .
Let be an integer, let
be a measurable sample
space, and let
denote the loss. The norm
is Euclidean. An unknown probability measure on has coordinate marginals
. Define the
group risks and objective by and consider the problem The algorithm
receives , , , , a given point , the loss , and parameters satisfying The group
laws are accessible through sampling; the gap parameters are not
algorithm inputs and may enter only the oracle-call budget.
Our assumptions:
Assumption 1 (Feasible set and loss). The set is compact and convex, , and The loss is
jointly measurable. For every , , and ,
Assumption 2 (Independent group reservoirs). The
coordinate maps on
are mutually independent under .
There is a probability law on
reservoirs
such that the row variables are
measurable, mutually independent, and each has law . Writing , a query to
group returns , where 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
for every group
. There exists a common point
such that
Each oracle call selects one group and returns one sample in ; the budget counts the total
number of such calls across all groups. After these calls, the output
must be measurable and
belong to for every realization.
Its required accuracy is
where is the joint law of the
algorithm’s randomness and the independent reservoir with law .