← All setups

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 f:E→R over a closed convex set C in a real Hilbert space E. On C, the function is differentiable and convex with a quadratic upper model of curvature L>0. A given x0∈C is within distance R≥0 of a minimizer with known value f⋆∈R. The oracle returns either a function value and gradient or a local linear minimizer over a queried ball intersected with C. For ε>0, the goal is x¯∈C with f(x¯)−f⋆≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Cf(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The algorithm receives E, L, R, ε, f⋆, and x0; the objective and feasible set are accessed through the oracle.

Our assumptions:

Assumption 1 (Feasible set). The set C⊆E is closed and convex, and x0∈C.

Assumption 2 (Convexity and quadratic upper model). The function f is Fréchet differentiable at every point of C. For every x,y∈C, f(y)≥f(x)+⟨∇f(x),y−x⟩,f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2.

Assumption 3 (Known minimum and initial distance). There exists x⋆∈C such that f(x⋆)=f⋆,f(x⋆)≤f(x)for every x∈C,∥x0−x⋆∥≤R.

The oracle supports two types of queries. At x∈C, a value–gradient query returns (f(x),∇f(x)). A local linear query specifies x∈C, a radius r≥0, and a direction g∈E, and returns a point v∈argminz∈C, ∥z−x∥≤r⁡⟨g,z⟩. 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 x¯∈C,f(x¯)−f(x⋆)≤εP-a.s. The algorithm’s randomness is independent of the oracle’s randomness in the joint law P.

Proved result

3⋅(⌈10⋅L⋅R2ε⌉++1)

OracleTemplate.Convergence LongTails.Setups.KnownValueSmoothConvexLocalLinear.spec OracleTemplate.SplitBrox.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.