Descriptions may be stale. Consult the linked Lean sources.
Composite Generalized
Smooth Minimization
We minimize over a convex
set in a real Hilbert space , where . The function is convex and -smooth, with and ; admits bounded supporting subgradients
on . A given point has bounded distance and
objective gap to a minimizer , where the gradient of is bounded. Oracles return exact
gradients of , bounded
subgradients of , and exact
projections onto . For , the goal is with
almost surely under , the joint
law of algorithm and oracle randomness.
More precisely, define and consider The norm is induced by the inner product
on . The algorithm receives , , and all parameters , whose
ranges are The functions and feasible set are
accessed through the three oracles described below.
Our assumptions:
Assumption 1 (Convexity and feasibility). The set
is convex and . For every and ,
Assumption 2 (Generalized smoothness). The function
is Fréchet differentiable
everywhere on , with continuous
gradient. Its -smoothness
means that, for every and
,
Assumption 3 (Solution and initial bounds). There
exists such that
Assumption 4 (Oracle access). The gradient oracle
returns at . At each , every reply of the subgradient oracle
satisfies These conditions hold for every query history and
every realization of oracle randomness. Subgradient queries outside
carry no guarantee. At any , the projection oracle returns a
point satisfying
Gradient, subgradient, and projection calls are counted separately.
Oracle randomness may be dependent across calls, and subgradient replies
may depend on the query history; the algorithm’s randomness is
independent of the oracle’s randomness. After the allotted calls, the
output must satisfy