← All setups

Polylog Precision Relative Error Convex — Sharp Relative-Error Convex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Sharp Relative-Error Convex Optimization · Lean proof

Sharp Relative-Error Convex Optimization

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 is within distance R≥0 of a global minimizer x⋆. At x∈E, the oracle returns a vector g∈E satisfying ∥g−∇f(x)∥≤α∥∇f(x)∥, where α≥0 obeys a stringent accuracy-dependent bound. For tolerance ε>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 ε. The parameters satisfy L>0,R≥0,ε>0,0≤α<1,α≤1100[33(1+log⁡(2+LR2/ε))]12, where log denotes the natural logarithm.

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 error). Queries may be made at any point of E. The relative-error inequality stated above holds for every query history, every query point, and every realization of the oracle randomness. Oracle replies may depend on the preceding queries and replies, and the 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. Here x⋆ is a fixed global minimizer, independent of the randomness.

Proved result

⌈8⋅(33⋅(1+log⁡(2+L⋅R2ε)))20⋅(2+L⋅R2ε)58⌉+

OracleTemplate.Convergence LongTails.Setups.SharpRelativeErrorSmoothConvex.spec
  LongTails.Theorems.PolylogPrecisionRelativeErrorConvex.budget

Relevant previous results

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