Recursive Relative Error Convex — Small Relative Error Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Small Relative Error Convex Minimization · Lean proof
Small Relative Error
Convex Minimization
We consider minimizing a differentiable convex function on a real Hilbert space
. The function is -smooth, with , and a given point lies within distance of a global minimizer . At , the oracle returns a vector satisfying , where and .
For , the goal is
an output 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 smoothness). The
function is Fréchet
differentiable everywhere on . For
every ,
Assumption 2 (Initial distance). There exists such that
Assumption 3 (Uniform relative oracle error).
Queries may be made at any point of . The relative error bound stated above
holds for every query, every finite query–reply history, and every
realization of the oracle randomness. The reply may depend on that
history, and oracle randomness may be dependent across calls. Algorithm
randomness is independent of oracle randomness.
After the allotted oracle calls, the output must satisfy The minimizer is fixed independently of the
randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.RecursiveRelativeErrorSmoothConvex.spec
LongTails.Theorems.RecursiveRelativeErrorConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.