Nonlinear Temporal Acceleration — Minimization with Bounded Temporal Discrepancy
Descriptions may be stale. Consult the linked Lean sources.
Minimization with Bounded Temporal Discrepancy · Lean proof
Minimization with
Bounded Temporal Discrepancy
We consider minimizing a twice continuously differentiable function
on a
finite-dimensional real Hilbert space . The function is -strongly convex with -Lipschitz gradient and -Lipschitz Hessian, where and . A given starting point has objective gap at most above a global minimizer
. The oracle returns the
gradient plus a fixed deterministic error sequence whose partial sums
have norm at most . For , the goal is an output
satisfying
almost surely 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. The algorithm receives , , , , , , , and .
Our assumptions:
Assumption 1 (Strong convexity and smoothness). The
function is twice continuously
Fréchet differentiable. For every ,
Assumption 2 (Lipschitz Hessian). The Hessian satisfies
Assumption 3 (Bounded temporal discrepancy). There
is a fixed deterministic sequence in . At the th call, indexed from zero, a query
returns The cumulative
errors satisfy
Assumption 4 (Initial objective gap). There exists
such that
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.HessianLipschitzTemporalDiscrepancy.spec
OracleTemplate.NonlinearTemporalDiscrepancy.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.