Power Geometry Relative Error Acceleration — Power Geometry with Relative Errors
Descriptions may be stale. Consult the linked Lean sources.
Power Geometry with Relative Errors · Lean proof
Power
Geometry with Relative Errors
We consider minimizing a differentiable convex function on a finite-dimensional
real normed space . Its derivative
is -Lipschitz, with . At a given point , the squared norm is
differentiable and satisfies a power-type curvature bound with exponent
and constant . A global minimizer satisfies , where . The oracle returns a dual vector
with
at , where . For , the goal is
almost surely for an output under the joint law of algorithm and oracle randomness.
The optimization problem is Write for the
continuous dual of and for its induced
operator norm. Define The
algorithm receives , , , , , and ; the radius and tolerance may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Power geometry). The function is Fréchet differentiable
everywhere, and for every ,
The fraction is defined to
be zero when .
Assumption 2 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere. For every and ,
Assumption 3 (Initial distance). There exists such that
Assumption 4 (Relative-error oracle). Queries may be
made at any point . Every
oracle reply satisfies
This bound holds for every
query history and every realization of the oracle randomness. Replies
may depend on the history, and oracle randomness across calls may be
dependent. The algorithm’s randomness is independent of the oracle
randomness.
After the allotted oracle calls, the output must satisfy where is the joint law of the algorithm and
oracle randomness, and is a
fixed global minimizer.
Proved result
OracleTemplate.Convergence LongTails.Setups.PowerGeometryRelativeErrorConvex.spec
LongTails.Theorems.PowerGeometryRelativeErrorAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.