← All setups

Composite Minimization with Lipschitz Hessian

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

In a finite-dimensional real inner-product space E, f∈C2(E) is convex and ∥∇2f(x)−∇2f(y)∥≤H∥x−y∥ globally. The function ψ is convex on C with closed epigraph over C; x0,x⋆∈C, x⋆ minimizes F=f+ψ on C, and ∥x0−x⋆∥≤R. Parameters H,R,ε>0 and integer m≥1 are supplied. Oracles provide exact gradients, Hessians, and exact convex cubic/positive-definite quadratic composite model solves. Target: a feasible x with F(x)−F(x⋆)≤ε almost surely.

Composite optimization with a Lipschitz Hessian: CompositeLipschitzHessian.
Result Oracle complexity Novelty Limitations
(1) CompositeLazyCubicAcceleration (Ours) (⋆⋆⋆) (review) O(log4⁡(2+m)log⁡(2+T/m3)⋅(m+m1/7T2/7))
(2) A-NPE (Monteiro and Svaiter 2013), Thms. 6.4, 7.15 (2012 revision) O(m(1+T2/7)ℓ) (1): at m=T1/3→∞, O(T1/3log4⁡(2+T)) instead of O(T13/21ℓ). Requires gradients/model solves costing 1/m of Hessians; no gain at m=1. (1) needs global smoothness, exact cubic solves rather than inexact quadratic solves; up to m1/7+m/T2/7 more solves, ignoring logs (T≥1).
(3) (Zhang et al. 2026), Thm. 4.1, v1 (preprint) O((m+m1/7T2/7)log11/3⁡(2+m)) (1) extends (3) from ψ=0, C=E to closed convex composite objectives using exact composite model solves; matches polynomial dependence on the overlap. (1) loses a factor log1/3⁡(2+m)log⁡(2+T/m3) on the overlap, with much larger explicit constants.
(4) CALEN (Chen et al. 2026), Thm. 5.1, v3 O((m+m13/21T2/7)log⁡(2+m)), m≥2 (1) extends (4) from ψ=0, C=E to composite objectives. On the overlap: m1/7 instead of m13/21 in the accuracy term, before logarithms; (3) already attains this power. (1) adds logarithmic overhead and much larger explicit constants; the improved power does not imply uniform total-cost dominance.

Abbr: T=HR3/ε; ℓ=1+|log⁡ε|+|log⁡H|+|log⁡R|. Costs are G+M+mH, where G,M,H count gradient, composite model, and Hessian calls, including inner iterations and search trials. For ψ=0, C=E, model solutions use only query data and are internal computation, so oracle cost is G+mH. Logarithms are natural.

Chen, Lesi, Chengchang Liu, Luo Luo, and Jingzhao Zhang. 2026. Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity. https://doi.org/10.48550/arXiv.2501.17488.
Monteiro, Renato D. C., and B. F. Svaiter. 2013. “An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order Methods.” SIAM Journal on Optimization 23 (2): 1092–125. https://doi.org/10.1137/110833786.
Zhang, Xinliang, Lesi Chen, Chengchang Liu, and Jingzhao Zhang. 2026. Near-Optimal Convex Optimization with Lazy Second-Order Oracles. https://doi.org/10.48550/arXiv.2610.03222.

Lean setup