Coupled Cubic Strong Growth — Strong-Growth Second-Order Finite-Sum Optimization
Descriptions may be stale. Consult the linked Lean sources.
Strong-Growth Second-Order Finite-Sum Optimization · Lean proof
Strong-Growth
Second-Order Finite-Sum Optimization
We consider minimizing on a
finite-dimensional real inner product space , with components . The twice
continuously differentiable components satisfy strong growth and a
mean-square Hessian Lipschitz bound with constant . The objective may be
nonconvex, and a given point has bounded objective gap. The oracle returns at a
queried index and point . For , the goal is an output
satisfying both and
for every , with probability
at least under , the law of the algorithm’s
randomness.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. Hessians are linear operators from to . The algorithm receives , , , and the parameters
Our assumptions:
Assumption 1 (Second-order regularity). Each
component is twice continuously
differentiable. For every ,
Assumption 2 (Strong growth). For every ,
Assumption 3 (Initial objective gap). The given
point satisfies
Queries may use any index and any point . Each oracle call returns the
exact component gradient and Hessian together; this pair counts as one
call.
After the allotted oracle calls, the required simultaneous accuracy
criterion is The event displayed here must be
measurable under .
Proved result
OracleTemplate.Convergence LongTails.Setups.StrongGrowthFiniteSumSecondOrder.spec
LongTails.Theorems.CoupledCubicStrongGrowth.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.