← All setups

Relative Error Generalized Acceleration — Convex Minimization with Relative Errors

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Relative Errors · Lean proof

Convex Minimization with Relative Errors

We consider minimizing a continuously differentiable convex function f:E→R on a real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A given point x0∈E has distance at most R>0 and objective gap at most Δ>0 from a global minimizer x⋆. At x, the oracle returns g∈E with ∥g−∇f(x)∥≤α∥∇f(x)∥, where 0≤α≤1/100; replies may depend on the query history. For ε>0, the goal is 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, L0, L1, R, Δ, x0, α, and ε.

Our assumptions:

Assumption 1 (Convexity and differentiability). The function f is Fréchet differentiable everywhere on E, its gradient ∇f:E→E is continuous, and f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,t∈[0,1].

Assumption 2 (Generalized smoothness). For every x,y∈E and M∈R satisfying ∥∇f(x+θ(y−x))∥≤Mfor all θ∈[0,1], we have ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

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

Assumption 4 (Relative oracle error). Queries may be made at any x∈E. For every finite query–reply history h and every realization z of the oracle randomness used for the reply, the returned vector g(h,x,z)∈E satisfies ∥g(h,x,z)−∇f(x)∥≤α∥∇f(x)∥. The oracle randomness may be dependent across calls and is independent of the algorithm’s randomness.

After the allotted oracle calls, the output x¯∈E must satisfy f(x¯)−f(x⋆)≤εP-a.s. Here x⋆ is a fixed global minimizer, independent of the randomness defining P.

Proved result

⌈260⋅(L0⋅R2ε+α2⋅L0⋅R2ε+(1+L1⋅R)⋅(1+log⁡(2+L0⋅R2ε+L1⋅R+ΔL0⋅R2))+α2⋅(L1⋅R)2⋅(1+log⁡(2+L0⋅R2ε+L1⋅R+ΔL0⋅R2))2)⌉+

OracleTemplate.Convergence LongTails.Setups.RelativeGeneralizedSmoothConvex.spec
  LongTails.Theorems.RelativeErrorGeneralizedAcceleration.budget

Relevant previous results

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