Quasar Minimization with Amortized LMO
Descriptions may be stale. Consult the linked Lean sources.
Quasar Minimization with Amortized LMO
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Feasible set). The set
Assumption 2 (Smoothness). The function
Assumption 3 (Quasar convexity). There exists
Assumption 4 (Amortized linear minimization). There
is a fixed sequence
Gradient queries may be made at any point of
After the allotted calls, the output must satisfy
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) QuasarAmortizedLMO (Ours) (review) | |||
| (2) Frank–Wolfe (Martínez-Rubio 2026, Thm. 9, Alg. 3, line 6) | Exact LMO; compact |
(1): Summably inexact
LMO; bounded Hilbert-space domains without closedness. Matches known
rate at |
|
| (3) Short-step Frank–Wolfe (Martínez-Rubio 2026, Prop. 12) | Exact LMO; compact |
(1): Matches known rate
at |
(1) needs |
| (4) Derived bound (Freund and Grigas 2016, Thm. 5.1, Rem. 5.1) | Convex |
(1): Scope extends from convex to quasar-convex objectives. Matches known rate on the convex overlap. | (1) requires summable errors; (4) also handles constant errors with an accuracy floor. No smaller convex leading constant. |
Abbr: LMO: linear minimization oracle;