← All setups

Composite Minimization with Gap-Controlled Hessians

Descriptions may be stale. Consult the linked Lean sources.

Composite Minimization with Gap-Controlled Hessians

We consider minimizing F=f+ψ over a convex set Q in a real Hilbert space E, where f,ψ:E→R are convex on Q. At each feasible point, f has a positive semidefinite Hessian satisfying ∥∇2f(x)∥op≤H0+H1(F(x)−F(x⋆)), where H0,H1≥0 and x⋆∈Q minimizes F. A given x0∈Q satisfies ∥x0−x⋆∥≤R and F(x0)−F(x⋆)≤Δ, with R,Δ>0. The oracle returns exact feasible gradients or exact proximal minimizers of ψ. For ε>0, the goal is x¯∈Q with F(x¯)−F(x⋆)≤ε almost surely.

The optimization problem is minx∈QF(x),F(x):=f(x)+ψ(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, H0, H1, R, Δ, ε, and x0; the functions and feasible set are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity). The set Q⊆E is convex. For every x,y∈Q and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y).

Assumption 2 (Minimizer and initialization). There exists x⋆∈Q such that x0∈Q and F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ.

Assumption 3 (Feasible Hessian bound). At every x∈Q, the function f is Fréchet differentiable, and its gradient is Fréchet differentiable at x as a map on E. The Hessian ∇2f(x):E→E is a bounded self-adjoint linear operator satisfying ⟨∇2f(x)h,h⟩≥0for every h∈E,∥∇2f(x)∥op≤H0+H1(F(x)−F(x⋆)). These derivatives are ambient derivatives, including at boundary points of Q.

Assumption 4 (Exact proximal access). There is a map P:R×E×E→E such that, for every a>0 and z,v∈E, P(a,z,v)∈argminu∈Q{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}. In particular, these minimizers exist and the returned point is feasible.

The oracle supports two query types. For a gradient query at x∈Q, the oracle returns ∇f(x) at x. For a proximal query (a,z,v)∈R×E×E, it returns P(a,z,v), with the minimization property above applying when a>0. Both query types count toward one common oracle-call budget.

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

Results

On a real Hilbert space, F=f+ψ with f,ψ convex on convex Q, exact gradients and exact Q-constrained regularizer prox. A minimizer x⋆∈Q exists, x0∈Q, ∥x0−x⋆∥≤R, and F(x0)−F(x⋆)≤Δ. On Q, ∇f is Fréchet differentiable with ∇2f(x)⪰0 and ∥∇2f(x)∥≤H0+H1(F(x)−F(x⋆)). Known H0,H1≥0 and R,Δ,ε>0. Target: feasible x^ with F(x^)−F(x⋆)≤ε deterministically.

Feasible-domain Hessian–gap composite optimization (FeasibleHessianGapComposite).
Result Oracle complexity Novelty Limitations
(1) FeasibleGapAccelerated (Ours) (⋆⋆) (review) O((1+RH0/ε+H1)ℓ2s) gradient plus prox calls.
(2) RCSAG (Lobanov et al. 2026), Thm. 9, zero noise O([s+RH0/ε+RH1j]
⋅[1+log⁡s]) gradient calls; auxiliary ball projections are closed form. Q=Rd, ψ=0, ε<Δ.
(1) Scope: constrained composite objectives; curvature control only at feasible points, without a stationary unconstrained minimizer. (1) Extra logarithmic cost on the overlap; requires Hessian regularity instead of a first-order local model.
(3) APG (Lu and Mei 2023), Thms. 1–2 O([1+(Δ+R2/γ0)max{1,γ0LS^}ε]
⋅[1+log+⁡(γ0LS^)]) gradient, prox and value calls, including backtracking.
(1) No function values; explicit gap-curvature budget instead of an enlarged-ball Lipschitz constant. No established rate comparison in shared parameters. (1) Needs H0,H1,R,Δ in addition. (3) assumes finite-dimensional proper closed convex functions and locally Lipschitz gradient on cl(domP).

Abbr: ℓ=1+log⁡(1+R2(H0/ε+H1)), s=1+log+⁡(Δ/ε), log+⁡t=max{0,log⁡t}. For H0,H1>0, j=min{s,1+log+⁡(H1Δ/H0)}; j=0 if H1=0, and j=s if H0=0<H1. In (2), fixed confidence and an auxiliary ball of diameter 2R. In (3), P=ψ+ιQ, γ0>0 is the initial step, α0=1, fixed backtracking contraction, and LS^ is the gradient Lipschitz constant on the enlarged ball intersected with domP from Lemma 1.

Lobanov, Aleksandr, Darina Dvinskikh, and Alexander Gasnikov. 2026. Accelerated Stochastic Method Under (H0,H1)-Smoothness and Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2609.33415.
Lu, Zhaosong, and Sanyou Mei. 2023. Accelerated First-Order Methods for Convex Optimization with Locally Lipschitz Continuous Gradient. https://doi.org/10.48550/arXiv.2206.01209.

Lean setup