Descriptions may be stale. Consult the linked Lean sources.
Interpolated
Generalized Smooth Finite Sums
We consider minimizing on
Euclidean space , where
is the number of components
and is the dimension. Each is convex
and -smooth, with and , and has a differentiable
gradient. The components share a minimizer satisfying and , where and . At a queried pair , the oracle returns . For , the goal is an output
with integrable objective
gap satisfying ,
where is the law of the
algorithm’s randomness.
The optimization problem is We use the
Euclidean norm and its induced operator norms, denoted by and , respectively.
The algorithm receives all parameters ; the
component functions are accessed through the oracle. The parameter
regime is
Our assumptions:
Assumption 1 (Component convexity). For every , , and ,
Assumption 2 (Generalized smoothness). Each is differentiable everywhere, and
is Fréchet differentiable
everywhere. Its Hessian satisfies
Assumption 3 (Interpolation and reference bounds).
There exists
such that The origin is a reference point for these bounds,
rather than a prescribed algorithm initialization.
Each oracle call selects any component and any point and returns the exact
pair . After
the allotted calls, the output must satisfy Here
is a fixed common minimizer of the components; all such minimizers have
the same value of .