← All setups

Nonlinear Temporal Acceleration — Minimization with Bounded Temporal Discrepancy

Descriptions may be stale. Consult the linked Lean sources.

Minimization with Bounded Temporal Discrepancy · Lean proof

Minimization with Bounded Temporal Discrepancy

We consider minimizing a twice continuously differentiable function f:E→R on a finite-dimensional real Hilbert space E. The function is μ-strongly convex with L-Lipschitz gradient and M-Lipschitz Hessian, where 0<μ≤L and M≥0. A given starting point x0∈E has objective gap at most Δ≥0 above a global minimizer x⋆. The oracle returns the gradient plus a fixed deterministic error sequence whose partial sums have norm at most D≥0. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, μ, L, M, D, Δ, and ε.

Our assumptions:

Assumption 1 (Strong convexity and smoothness). The function f is twice continuously Fréchet differentiable. For every x,y∈E, f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2,∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 2 (Lipschitz Hessian). The Hessian ∇2f(x):E→E satisfies ∥∇2f(x)−∇2f(y)∥op≤M∥x−y∥,x,y∈E.

Assumption 3 (Bounded temporal discrepancy). There is a fixed deterministic sequence (ek)k≥0 in E. At the kth call, indexed from zero, a query x∈E returns gk(x)=∇f(x)+ek. The cumulative errors satisfy ‖∑k=0n−1ek‖≤D,n=0,1,2,….

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

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Proved result

{0Δ≤ε⌈109⋅(Lμ⋅(1+M⋅Dμ2)+Dμ⋅ε+1)⋅log⁡(2+Δε+M2⋅Δμ3)⌉+otherwise

OracleTemplate.Convergence LongTails.Setups.HessianLipschitzTemporalDiscrepancy.spec
  OracleTemplate.NonlinearTemporalDiscrepancy.budget

Relevant previous results

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