← All setups

Power Geometry Relative Error Acceleration — Power Geometry with Relative Errors

Descriptions may be stale. Consult the linked Lean sources.

Power Geometry with Relative Errors · Lean proof

Power Geometry with Relative Errors

We consider minimizing a differentiable convex function f:E→R on a finite-dimensional real normed space E. Its derivative Df is L-Lipschitz, with L>0. At a given point x0∈E, the squared norm is differentiable and satisfies a power-type curvature bound with exponent p>2 and constant c>0. A global minimizer x⋆ satisfies ∥x0−x⋆∥≤R, where R≥0. The oracle returns a dual vector g with ∥g−Df(x)∥op≤α∥Df(x)∥op at x, where 0≤α≤1/4. For ε>0, the goal is f(x¯)−f(x⋆)≤ε almost surely for an output x¯∈E under the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). Write E∗ for the continuous dual of E and ∥⋅∥op for its induced operator norm. Define ψ(x)=12∥x−x0∥2. The algorithm receives E, L, α, p, c, and x0; the radius R and tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Power geometry). The function ψ is Fréchet differentiable everywhere, and for every x,y∈E, c∥y−x∥p(∥y−x0∥+∥x−x0∥)p−2≤ψ(y)−ψ(x)−Dψ(x)[y−x]. The fraction is defined to be zero when x=y=x0.

Assumption 2 (Convexity and smoothness). The function f is Fréchet differentiable everywhere. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥Df(x)−Df(y)∥op≤L∥x−y∥.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x⋆−x0∥≤R.

Assumption 4 (Relative-error oracle). Queries may be made at any point x∈E. Every oracle reply g∈E∗ satisfies ∥g−Df(x)∥op≤α∥Df(x)∥op. This bound holds for every query history and every realization of the oracle randomness. Replies may depend on the history, and oracle randomness across calls may be dependent. The algorithm’s randomness is independent of the oracle randomness.

After the allotted oracle calls, the output x¯∈E must satisfy f(x¯)−f(x⋆)≤εP-a.s., where P is the joint law of the algorithm and oracle randomness, and x⋆ is a fixed global minimizer.

Proved result

⌈(1536⋅max{1,32p−22c}⋅L⋅R2ε)pp+2+4224⋅L⋅α2⋅R2ε⌉++1

OracleTemplate.Convergence LongTails.Setups.PowerGeometryRelativeErrorConvex.spec
  LongTails.Theorems.PowerGeometryRelativeErrorAcceleration.budget

Relevant previous results

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