Accelerated Interpolated Generalized Finite Sum — Interpolated Generalized Smooth Finite Sums
Descriptions may be stale. Consult the linked Lean sources.
Interpolated Generalized Smooth Finite Sums · Lean proof
Interpolated
Generalized Smooth Finite Sums
We consider minimizing on a
finite-dimensional real inner product space , where is an integer. Each component
is convex,
continuously differentiable, and -smooth, with and . The components share a global
minimizer , with for a given and . The oracle returns at a queried pair . Given , the goal is an output
satisfying with
probability at least over the
algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , , , , , and .
Our assumptions:
Assumption 1 (Component convexity and
differentiability). Each is
differentiable everywhere on with
continuous gradient . For every , , and ,
Assumption 2 (Generalized smoothness). For every
, , and , the segment bound implies
Assumption 3 (Interpolation and initial distance).
There exists such that
Queries may select any component and any point , with each call returning its
exact component gradient. After the allotted oracle calls, the output
must satisfy where
is the law of the algorithm’s randomness and is a fixed common global
minimizer.
Proved result
OracleTemplate.Convergence LongTails.Setups.InterpolatedGeneralizedFiniteSum.spec
OracleTemplate.AcceleratedInterpolatedGeneralizedFiniteSum.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.