Hidden Potential Oracle Complexity — Strongly Monotone Hidden-Potential Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Strongly Monotone Hidden-Potential Root Finding · Lean proof
Strongly Monotone
Hidden-Potential Root Finding
We seek a zero of a map
on a real Hilbert space . The map
is -strongly monotone, where
, and admits a hidden
differentiable potential whose gradient is
-Lipschitz, with , while is -Lipschitz, with . A given point lies within distance of a zero . The oracle returns at . For , the goal is an output
satisfying almost
surely under , the law of the
algorithm’s randomness.
The root-finding problem is Write for the inner
product on and for its induced norm. The
algorithm receives , , , , , , and ; the potential is not supplied.
Our assumptions:
Assumption 1 (Strong monotonicity). For every ,
Assumption 2 (Hidden potential). There exists an
everywhere Fréchet differentiable function such that, for
every ,
Assumption 3 (Initial distance). There exists satisfying
Queries may be made at any point of . Strong monotonicity makes the zero
unique. After the allotted
oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.HiddenPotentialStronglyMonotone.spec OracleTemplate.HiddenPotential.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.