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
over a bounded
convex set in a real Hilbert
space . Its gradient is -Lipschitz, with , and is -quasar-convex relative to a
minimizer , with . A starting point is given. The oracle returns
at . It also supplies approximate linear
minimizers on calls with an odd number of preceding calls, with summable
errors. For , the
goal is a feasible output
with
almost surely under , the joint
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 ; the set , its diameter bound , the error budget , and the tolerance may enter the
oracle-call budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Feasible set). The set is convex, contains , and satisfies
Assumption 2 (Smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 3 (Quasar convexity). There exists such that, for every ,
Assumption 4 (Amortized linear minimization). There
is a fixed sequence satisfying For any query
history containing preceding
calls and any direction , a
linear minimization query returns a vector satisfying 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 , and linear minimization queries may
use any direction in . 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 The minimizer is fixed independently of the
randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.QuasarAmortizedLMO.spec OracleTemplate.QuasarAmortizedLMO.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.