Descriptions may be stale. Consult the linked Lean sources.
Chi-Square Constrained
Robust Optimization
We minimize a robust objective
over a closed convex set in a
separable real Hilbert space .
Here is the worst expected
sample loss under nonnegative densities relative to a probability law
, with mean one and chi-square
divergence at most .
Sample losses are jointly measurable, convex and bounded on , with jointly measurable bounded
subgradients. Each oracle call returns the projection of the query onto
, together with its loss and
subgradient evaluated using one fresh independent sample from . Given , the goal is a
measurable feasible output
with ,
where minimizes on and expectation includes sampling and
algorithm randomness.
Let be a measurable sample
space carrying the probability measure . Write for the
sample loss and
for its supplied subgradient. Define the density class The objective and optimization problem are The norm is induced by the inner product
on . The algorithm receives , , , , , , , and a given point ; the instance consists of , , , and , accessed through the oracle described
below.
Our assumptions:
Assumption 1 (Feasible set and projection). The set
is closed and convex,
and . There is a measurable
map satisfying
Assumption 2 (Sample losses and subgradients). The
maps and are jointly measurable. For every and ,
Assumption 3 (Initial distance). There exists such that
Queries may be made at any . At call , the
oracle returns The sample variables are measurable, mutually
independent, and each has law .
The loss and subgradient in a reply use the same sample. Any algorithm
randomness is independent of the entire sample sequence.
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
samples and the algorithm’s randomness.