Strong Growth Convex Finite Sum Acceleration — Finite-Sum Convex Strong Growth
Descriptions may be stale. Consult the linked Lean sources.
Finite-Sum Convex Strong Growth · Lean proof
Finite-Sum
Convex Strong Growth
We minimize on a finite-dimensional real inner product space , where is an integer. Each is differentiable and
convex with -Lipschitz gradient,
. Strong growth requires
for every , with . A given satisfies , where and minimizes . The oracle returns at a queried pair . For , the goal is a
measurable output with
integrable 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 on . For every , , and ,
Assumption 2 (Strong growth). For every ,
Assumption 3 (Initial distance). There exists such that
The algorithm may query any component index at any point ; each query returns the exact
component gradient. After the allotted component-gradient calls, its
output must be measurable
and satisfy The gap must be integrable under . Here is a fixed global minimizer; all
global minimizers have the same objective value.
Proved result
OracleTemplate.Convergence LongTails.Setups.FiniteSumStrongGrowthConvex.spec
LongTails.Theorems.StrongGrowthConvexFiniteSumAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.