← All setups

Composite Lazy Cubic Acceleration — Composite Minimization with Lipschitz Hessian

Descriptions may be stale. Consult the linked Lean sources.

Composite Minimization with Lipschitz Hessian · Lean proof

Composite Minimization with Lipschitz Hessian

We consider minimizing F=f+ψ over a convex set D in a finite-dimensional real inner product space E. The function f:E→R is convex and twice continuously differentiable, with H-Lipschitz Hessian, where H>0; ψ:E→R is convex on D and has a closed epigraph restricted to D. A given point x0∈D satisfies ∥x0−x⋆∥≤R for a minimizer x⋆∈D and R>0. Three oracles return exact gradients, exact Hessians, and exact composite model solutions. For ε>0, the goal is x¯∈D with F(x¯)−F(x⋆)≤ε almost surely under P, the joint law of algorithm and oracle randomness.

Write F(x)=f(x)+ψ(x). The optimization problem is minx∈DF(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, H>0, R>0, ε>0, and an integer m≥1.

Our assumptions:

Assumption 1 (Convex composite objective). The function f is convex on E, the set D⊆E is convex, and ψ is convex on D. In particular, for t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y),x,y∈D. The restricted epigraph {(x,r)∈E×R:x∈D, ψ(x)≤r} is closed in E×R.

Assumption 2 (Lipschitz Hessian). The function f is twice continuously Fréchet differentiable on E. Its Hessian, viewed as a linear operator from E to E, satisfies ∥∇2f(x)−∇2f(y)∥op≤H∥x−y∥,x,y∈E.

Assumption 3 (Minimizer and initial distance). The given starting point x0 and a minimizer x⋆ belong to D, with F(x⋆)≤F(x)for every x∈D,∥x0−x⋆∥≤R.

Gradient and Hessian queries may be made at any x∈E. The gradient oracle returns ∇f(x) at x, and the Hessian oracle returns ∇2f(x) at x.

The third oracle solves composite models. A model query consists of a center c∈E, a vector a∈E, a linear operator B:E→E, a cubic coefficient γ≥0, and a scale s>0. The operator must satisfy ⟨u,Bv⟩=⟨Bu,v⟩for all u,v∈E,⟨u,Bu⟩≥0for all u∈E. In addition, either γ>0, or there exists μ>0 such that ⟨u,Bu⟩≥μ∥u∥2,u∈E. For every such query, the model oracle returns a point z∈D satisfying the exact variational inequality d(z)=a+B(z−c)+γ∥z−c∥(z−c),0≤⟨d(z),u−z⟩+s(ψ(u)−ψ(z)),u∈D. Equivalently, z minimizes over D the model M(x)=⟨a,x−c⟩+12⟨x−c,B(x−c)⟩+γ3∥x−c∥3+sψ(x). The model guarantee holds for every valid query and every oracle reply, including queries chosen using previous replies. Gradient, Hessian, and model-solution calls are counted separately.

After the allotted calls, the output must satisfy x¯∈D,F(x¯)−F(x⋆)≤εP-a.s. Under the joint law P, the algorithm’s randomness is independent of the oracle’s randomness.

Proved result

Oracle 0:549755813888⋅m⋅(3+log2(m3+4))4⋅(3+log2(2+⌈(H⋅R3m3⋅ε)47⌉+))⋅(1+⌈(H⋅R3m3⋅ε)27⌉+) Oracle 1:4160⋅(3+log2(m3+4))⋅(3+log2(2+⌈(H⋅R3m3⋅ε)47⌉+))⋅(1+⌈(H⋅R3m3⋅ε)27⌉+) Oracle 2:549755813888⋅m⋅(3+log2(m3+4))4⋅(3+log2(2+⌈(H⋅R3m3⋅ε)47⌉+))⋅(1+⌈(H⋅R3m3⋅ε)27⌉+)

OracleTemplate.Convergence LongTails.Setups.CompositeLipschitzHessian.spec
  LongTails.Theorems.CompositeLazyCubicAcceleration.budget

Relevant previous results

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