← All setups

Recursive Relative Error Convex — Small Relative Error Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Small Relative Error Convex Minimization · Lean proof

Small Relative Error Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E. The function is L-smooth, with L>0, and a given point x0∈E lies within distance R≥0 of a global minimizer x⋆. At x, the oracle returns a vector g satisfying ∥g−∇f(x)∥≤α∥∇f(x)∥, where 0≤α<1 and α≤exp⁡(−8(1+log⁡(2+LR2/ε)))/100. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, L, x0, α, R, and ε.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E, f(y)≥f(x)+⟨∇f(x),y−x⟩,f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2.

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

Assumption 3 (Uniform relative oracle error). Queries may be made at any point of E. The relative error bound stated above holds for every query, every finite query–reply history, and every realization of the oracle randomness. The reply may depend on that history, and oracle randomness may be dependent across calls. Algorithm randomness is independent of oracle randomness.

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. The minimizer x⋆ is fixed independently of the randomness.

Proved result

⌈4⋅2+L⋅R2ε⋅exp⁡(32⋅(1+log⁡(2+L⋅R2ε))⋅log⁡(32+log⁡(2+L⋅R2ε)))⌉+

OracleTemplate.Convergence LongTails.Setups.RecursiveRelativeErrorSmoothConvex.spec
  LongTails.Theorems.RecursiveRelativeErrorConvex.budget

Relevant previous results

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