← All setups

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 f:E→R over a closed convex set C in a real Hilbert space E. On C, f is differentiable and convex with a quadratic upper model of unknown curvature L≥0. A given point x0∈C is within distance R≥0 and objective gap Δ≥0 of a minimizer x⋆∈C; Δ is unknown. The oracle returns exact values and gradients, or a linear minimizer over a ball intersected with C. For ε>0, the goal is a feasible output x¯ with f(x¯)−f(x⋆)≤ε almost surely under P, the law of algorithm and oracle randomness.

The optimization problem is minx∈Cf(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives only E, R, ε, and x0, together with oracle access; L 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 C⊆E is closed and convex, and x0∈C. 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 2 (Initial distance and objective gap). There exists x⋆∈C such that f(x⋆)≤f(x)for every x∈C,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 3 (Exact value-gradient and local linear access). At any x∈C, a value-gradient query returns (f(x),∇f(x)). A local linear query takes a center 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 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 x¯∈C,f(x¯)−f(x⋆)≤εP-a.s. The algorithm’s randomness is independent of the oracle’s randomness, and the minimizer in this requirement is fixed independently of both.

Proved result

⌈400⋅L⋅R2ε+40⋅log2⁡(2+Δ+L⋅R2ε)⌉++300

OracleTemplate.Convergence LongTails.Setups.UnknownValueSmoothConvexLocalLinear.spec
  OracleTemplate.CertifiedLevelBrox.budget

Relevant previous results

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