Relative Error Generalized Acceleration — Convex Minimization with Relative Errors
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Relative Errors · Lean proof
Convex Minimization with
Relative Errors
We consider minimizing a continuously differentiable convex function
on a real Hilbert
space . The function is -smooth, with and . A given point has distance at most and objective gap at most from a global minimizer . At , the oracle returns with , where ; replies may depend
on the query history. For , the goal is satisfying
almost surely under , the joint
law of algorithm and oracle randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , , , , , , and .
Our assumptions:
Assumption 1 (Convexity and differentiability). The
function is Fréchet
differentiable everywhere on , its
gradient is
continuous, and
Assumption 2 (Generalized smoothness). For every
and satisfying we have
Assumption 3 (Initial distance and objective gap).
There exists such that
Assumption 4 (Relative oracle error). Queries may be
made at any . For every
finite query–reply history and
every realization of the oracle
randomness used for the reply, the returned vector satisfies The oracle randomness may be
dependent across calls and is independent of the algorithm’s
randomness.
After the allotted oracle calls, the output must satisfy Here is a fixed global minimizer,
independent of the randomness defining .
Proved result
OracleTemplate.Convergence LongTails.Setups.RelativeGeneralizedSmoothConvex.spec
LongTails.Theorems.RelativeErrorGeneralizedAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.