Certified Level Brox Unknown Value — Convex Minimization with Local Linear Oracles
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Local Linear Oracles · Lean proof
Convex Minimization
with Local Linear Oracles
We consider minimizing over a closed convex set
in a real Hilbert space . On ,
is differentiable and convex with a quadratic upper model of unknown
curvature . A given point
is within distance and objective gap of a minimizer ; is unknown. The oracle returns
exact values and gradients, or a linear minimizer over a ball
intersected with . For , the goal is a feasible
output with
almost surely under , the law of
algorithm and oracle randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives only , , , and , together with oracle access; and may enter the call budget but are
not algorithm inputs. The optimal objective value is not supplied.
Our assumptions:
Assumption 1 (Feasible set and first-order models).
The set is closed and
convex, and . The function
is Fréchet differentiable at
every point of . For every ,
Assumption 2 (Initial distance and objective gap).
There exists such that
Assumption 3 (Exact value-gradient and local linear
access). At any , a
value-gradient query returns . A local linear query takes a center , a radius , and a direction , and returns a point Such a minimizer exists for every
admissible query. Every reply must satisfy this requirement, even when
the choice among minimizers depends on previous queries and replies or
on oracle randomness.
Both query types count toward a single oracle-call budget, with one
call charged for either type. After the allotted calls, the output must
satisfy The algorithm’s randomness is independent
of the oracle’s randomness, and the minimizer in this requirement is
fixed independently of both.
Proved result
OracleTemplate.Convergence LongTails.Setups.UnknownValueSmoothConvexLocalLinear.spec
OracleTemplate.CertifiedLevelBrox.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.