Descriptions may be stale. Consult the linked Lean sources.
Compositional Entropic
Risk Minimization
We minimize
over a nonempty closed convex set
in a separable real Hilbert space , where , are probability laws, and are bounded convex sample scores.
Measurable score subgradients satisfy second-moment and exponentially
weighted moment bounds, and a given starting point lies near a minimizer
. The oracle returns
two independent score–subgradient pairs for one uniformly sampled
component, or an exact projection onto . For , the goal is a
measurable, everywhere feasible output with integrable gap and ,
averaging over independent algorithm and oracle randomness.
Let be a measurable sample
space, and write The optimization problem is The norm is induced
by the inner product on . The
parameters satisfy The algorithm receives , , , , , , , , , , , and the starting point ; the scores, subgradients, laws, and
feasible set are accessed through the oracle.
Our assumptions:
Assumption 1 (Feasible set and initial distance).
The set is closed and
convex, and . There exists
such that
Assumption 2 (Bounded scores and subgradients). For
each , the maps
and are jointly measurable. For every
and , Thus is a subgradient of the sample
score on .
Assumption 3 (Moment bounds). For each and , the function is integrable
under , and
Queries may be made at any point of . At a sampling query , a component is drawn uniformly from . Conditional on , two samples and are drawn independently from
. The reply is Each score and its
subgradient use the same sample, and the two pairs share the component
index. The draws used at successive calls are independent and
identically distributed, and independent of the algorithm’s
randomness.
At a projection query , the
oracle returns . The map
is measurable and
satisfies Sampling and projection queries share one total
call budget; a sampling call returns both pairs above.
After the allotted calls, the output must be measurable and belong to
for every realization. Its
objective gap must be integrable and satisfy
where is the joint law of the
independent algorithm and oracle randomness, and is a fixed minimizer on .