Strong Growth Finite Sum Acceleration — Strong Growth Finite-Sum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Strong Growth Finite-Sum Minimization · Lean proof
Strong
Growth Finite-Sum Minimization
We minimize on a finite-dimensional real inner product space , where is an integer. Each component
is convex with
-Lipschitz gradient, and is -strongly convex, with . Strong growth requires for all , where . A given point is within distance of a minimizer . The oracle returns at a queried pair . For , the goal is a
measurable output with
integrable objective gap satisfying ,
where is the law of the
algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , which is equipped with a
measurable structure. The algorithm receives , , , , , , , and .
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each is Fréchet differentiable
everywhere. For every , , and ,
Assumption 2 (Strong convexity). For every and ,
Assumption 3 (Strong growth). The component
gradients satisfy where .
Assumption 4 (Initial distance). There exists such that
Queries may select any component index and any point ; each reply is the exact component
gradient. After the allotted oracle calls, the output must be measurable and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.FiniteSumStrongGrowthStronglyConvex.spec
LongTails.Theorems.StrongGrowthFiniteSumAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.