← All setups

Quasar Amortized LMO — Quasar Minimization with Amortized LMO

Descriptions may be stale. Consult the linked Lean sources.

Quasar Minimization with Amortized LMO · Lean proof

Quasar Minimization with Amortized LMO

We consider minimizing a differentiable, possibly nonconvex function f:E→R over a bounded convex set C in a real Hilbert space E. Its gradient is L-Lipschitz, with L≥0, and f is τ-quasar-convex relative to a minimizer x⋆∈C, with 0<τ≤1. A starting point x0∈C is given. The oracle returns ∇f(x) at x. It also supplies approximate linear minimizers on calls with an odd number of preceding calls, with summable errors. For ε>0, the goal is a feasible output x¯ with f(x¯)−f(x⋆)≤ε almost surely under P, the joint 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, L, x0, and τ; the set C, its diameter bound D≥0, the error budget Γ≥0, and the tolerance ε>0 may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Feasible set). The set C⊆E is convex, contains x0, and satisfies ∥x−y∥≤D,x,y∈C.

Assumption 2 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 3 (Quasar convexity). There exists x⋆∈C such that, for every x∈C, f(x⋆)≤f(x),τ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩.

Assumption 4 (Amortized linear minimization). There is a fixed sequence (δk)k≥0 satisfying δk≥0(k≥0),∑k=0n−1δk≤Γ(n≥0). For any query history containing 2k+1 preceding calls and any direction v∈E, a linear minimization query returns a vector s∈E satisfying s∈C,⟨v,s⟩≤⟨v,u⟩+δk,u∈C. These conditions hold for every such history and every realization of the oracle randomness. The linear minimization guarantee applies only at these history lengths.

Gradient queries may be made at any point of E, and linear minimization queries may use any direction in E. Both query types count toward a single total oracle-call budget; the history length counts both types. Oracle replies to linear minimization queries may depend on the preceding history. Algorithm randomness is independent of oracle randomness.

After the allotted calls, the output must satisfy x¯∈C,f(x¯)−f(x⋆)≤εP-a.s. The minimizer x⋆ is fixed independently of the randomness.

Proved result

2⋅max{1,⌈6⋅L⋅D2τ2+2⋅Γτε⌉+}

OracleTemplate.Convergence LongTails.Setups.QuasarAmortizedLMO.spec OracleTemplate.QuasarAmortizedLMO.budget

Relevant previous results

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