Split Brox Known Value — Known-Value Convex Local Linear Optimization
Descriptions may be stale. Consult the linked Lean sources.
Known-Value Convex Local Linear Optimization · Lean proof
Known-Value Convex
Local Linear Optimization
We consider minimizing over a closed convex set
in a real Hilbert space . On , the function is differentiable and
convex with a quadratic upper model of curvature . A given is within distance of a minimizer with known value
. The oracle
returns either a function value and gradient or a local linear minimizer
over a queried ball intersected with . For , the goal is with 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 objective and feasible set are
accessed through the oracle.
Our assumptions:
Assumption 1 (Feasible set). The set is closed and convex, and
.
Assumption 2 (Convexity and quadratic upper model).
The function is Fréchet
differentiable at every point of .
For every ,
Assumption 3 (Known minimum and initial distance).
There exists such that
The oracle supports two types of queries. At , a value–gradient query returns
. A local linear
query specifies , a radius
, and a direction , and returns a point Such a point must exist for every valid
local linear query. The oracle may choose among these minimizers using
the query history and its randomness, but every reply must satisfy the
stated requirement. Both query types count toward a single total
oracle-call budget.
After the allotted calls, the output must satisfy The algorithm’s randomness is independent
of the oracle’s randomness in the joint law .
Proved result
OracleTemplate.Convergence LongTails.Setups.KnownValueSmoothConvexLocalLinear.spec OracleTemplate.SplitBrox.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.