← All setups

Smooth Nonconvex Banach-Space Optimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Nonconvex Banach-Space Optimization

We consider minimizing a possibly nonconvex function f:E→R on a real Banach space E. Its Fréchet derivative f′(x)∈E∗, where E∗ is the continuous dual of E, is L-Lipschitz in the induced operator norm ∥⋅∥op, with L>0. A given point x0∈E has objective gap at most Δ≥0 above a global lower bound. The oracle returns f′(x) at x. For ε>0, the goal is a measurable output x¯∈E satisfying EP[∥f′(x¯)∥op2]≤ε2, where P is the law of the algorithm’s randomness.

The optimization problem is infx∈Ef(x). The space E is equipped with a specified measurable structure. We write ∥⋅∥ for its norm and use the induced operator norm on E∗. The algorithm receives E, L, Δ, ε, and x0.

Our assumptions:

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

Assumption 2 (Initial objective gap). There exists ℓ∈R such that ℓ≤f(x)for every x∈E,f(x0)−ℓ≤Δ.

Queries may be made at any point of E, with exact derivative replies in E∗. After the allotted oracle calls, the output x¯ must be measurable, its squared derivative norm must be integrable under P, and it must satisfy EP[∥f′(x¯)∥op2]≤ε2.

Results

    Lean setup