← All setups

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 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.

Results

On a real Hilbert space, f is differentiable with globally L-Lipschitz gradient. The convex set C contains x0, has diameter at most D, and admits a minimizer x⋆ satisfying τ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for every x∈C. Here L,D,Γ≥0, 0<τ≤1, and ε>0. Gradients are exact; the LMO returns vk∈C with ⟨v,vk⟩≤⟨v,u⟩+δk for every direction v, u∈C, and seed, where δk≥0 and ∑k<nδk≤Γ for every n. The target is a feasible output with f(xK)−f(x⋆)≤ε almost surely under the execution measure P. The constructed Frank–Wolfe method uses ηk=2/(τk+2); the setup does not restrict the algorithm.

Smooth quasar-convex optimization with amortized LMO errors: QuasarAmortizedLMO.
Result Oracle complexity Novelty Limitations
(1) QuasarAmortizedLMO (Ours) (review) O(1+LD2τ2ε+Γτε)
(2) Frank–Wolfe (Martínez-Rubio 2026, Thm. 9, Alg. 3, line 6) O(1+LD2τ2ε)
Exact LMO; compact C⊂Rd.
(1): Summably inexact LMO; bounded Hilbert-space domains without closedness. Matches known rate at Γ=0, including its constant. Lean formalization.
(3) Short-step Frank–Wolfe (Martínez-Rubio 2026, Prop. 12) O(1+LD2τ2ε)
Exact LMO; compact C⊂Rd.
(1): Matches known rate at Γ=0; extends to summable LMO errors and Hilbert-space domains. Updates need no L. (1) needs τ in updates; (3) does not.
(4) Derived bound (Freund and Grigas 2016, Thm. 5.1, Rem. 5.1) O(1+LD2+Γε)
Convex f, τ=1, compact C⊂Rd; ∑kδk≤Γ.
(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; L: gradient Lipschitz constant; D: diameter bound; τ: quasar parameter; Γ: cumulative additive LMO-error bound; ε: objective accuracy; xK: returned iterate. Costs count gradient plus LMO calls, including initialization; each iteration uses one of each.

Freund, Robert M., and Paul Grigas. 2016. “New Analysis and Results for the Frank–Wolfe Method.” Mathematical Programming 155: 199–230. https://doi.org/10.1007/s10107-014-0841-6.
Martínez-Rubio, David. 2026. Smooth Quasar-Convex Optimization with Constraints. https://doi.org/10.48550/arXiv.2510.01943.

Lean setup