Polylog Precision Relative Error Convex — Sharp Relative-Error Convex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Sharp Relative-Error Convex Optimization · Lean proof
Sharp Relative-Error
Convex Optimization
We consider minimizing a differentiable convex function on a real Hilbert space
. The function is -smooth, with , and a given point is within distance of a global minimizer . At , the oracle returns a vector satisfying , where
obeys a stringent accuracy-dependent bound. For tolerance , 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 . The parameters satisfy where
denotes the natural logarithm.
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 error). Queries may
be made at any point of . The
relative-error inequality stated above holds for every query history,
every query point, and every realization of the oracle randomness.
Oracle replies may depend on the preceding queries and replies, and the
oracle randomness may be dependent across calls. Algorithm randomness is
independent of oracle randomness.
After the allotted oracle calls, the output must satisfy Here is a fixed global minimizer,
independent of the randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.SharpRelativeErrorSmoothConvex.spec
LongTails.Theorems.PolylogPrecisionRelativeErrorConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.