← All setups

Composite Minimization with Gap Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Composite Minimization with Gap Smoothness

We consider minimizing F=f+ψ over a convex set Q in a real Hilbert space E, where f,ψ:E→R, f is differentiable and convex, and ψ is convex on Q. A local quadratic upper model for f depends on the objective gap to a minimizer x⋆∈Q. A given feasible starting point has bounded distance and objective gap to x⋆. The oracle returns exact gradients and proximal minimizers. For ε>0, the goal is a feasible output x¯ with F(x¯)−F(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈QF(x),F(x)=f(x)+ψ(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, the starting point x0∈E, and the parameters H0,H1≥0,R,Δ,ε>0.

Our assumptions:

Assumption 1 (Convexity and differentiability). The function f is convex and Fréchet differentiable on E. The set Q⊆E is convex, and ψ is convex on Q.

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 (Gap-dependent upper model). For every x∈Q and y∈E satisfying H1∥y−x∥≤1, f(y)≤f(x)+⟨∇f(x),y−x⟩+(H0+H1(F(x)−F(x⋆)))∥y−x∥2.

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)}.

The oracle returns ∇f(x) at x. Gradient queries may use any x∈E. A proximal query (a,z,v)∈R×E×E returns P(a,z,v), with the minimization property above required for positive a. Gradient and proximal calls count toward a single total oracle-call budget.

After the allotted calls, the output must satisfy x¯∈Q,F(x¯)−F(x⋆)≤εP-a.s.

Results

In a real Hilbert space E, minimize F=f+ψ over convex Q, with globally convex differentiable f and real-valued ψ convex on Q. Exact gradients and exact minimizers of ψ(u)+⟨v,u−z⟩+∥u−z∥2/(2a) over Q are available for every a>0,z,v. For x0,x⋆∈Q, assume x⋆∈arg⁡minQF, ∥x0−x⋆∥≤R, and F(x0)−F(x⋆)≤Δ, with H0,H1≥0 and R,Δ,ε>0. For every x∈Q and ambient y∈E with H1∥y−x∥≤1, assume f(y)≤f(x)+⟨∇f(x),y−x⟩+[H0+H1(F(x)−F(x⋆))]∥y−x∥2. Target: a deterministic x^∈Q with F(x^)−F(x⋆)≤ε.

Composite gap-curvature acceleration: CompositeGapSmooth.
Result Oracle complexity Novelty Limitations
(1) CompositeGapAccelerated (Ours) (⋆⋆⋆) (review) O([1+RH0/ε+H1]ℓ⋅[1+log⁡(1+R2(H0/ε+H1))]) gradient plus prox calls.
(2) RCSAG (Lobanov et al. 2026), Thm. 9, noise-free specialization O([ℓ+RH0/ε+RH1ℓ](1+log⁡ℓ)) gradient calls; closed-form ball projections. Special case: Q=E=Rd, ψ=0, ε≤Δ. (1): Scope extends to nonsmooth composite objectives and constraints, including ∇f(x⋆)≠0, using ordinary prox calls. (1): Extra logarithmic factors on the smooth overlap, including the restart logarithm on RH0/ε.
(3) (LongTails 2026), repository result O(R(L0+L1G)/ε+(1+L1R)[1+log⁡(1+(1+L1R)Δ/(L0R2))]) gradient plus prox calls. Requires composite (L0,L1)-smoothness, L0>0, and ∥∇f(x⋆)∥≤G. (1): Total-gap curvature replaces gradient-norm curvature; no G needed to stop. For the δ-family, ε=δ↓0: O(δ−3/2log2⁡(1/δ)) versus a startup term at least δ−2.
(4) Derived bound: Moreau smoothing + (Lobanov et al. 2026), Thm. 9 O([ℓ+R′H0/ε+R′Gψ/ε+R′H1ℓ](1+log⁡ℓ)) gradient plus prox calls. Requires Q=E=Rd, globally Gψ-Lipschitz ψ, Gψ>0, ε≤Δ, and a smoothed minimizer within known radius R′. (1): Removes R′Gψ/ε and the Lipschitz restriction. For R′=O(R), polynomial gain when Gψ/H0ε dominates logarithmic overhead and remaining terms; also covers constraints. (1): Extra logarithms. General total rates are not comparable without control of R′/R.
(5) (Lobanov 2026), Thm. 5 O(ℓ+R~H0/ε+R~H1ℓ) gradient, value, and exact segment-minimization calls, counting each segment solve once. Requires Q=E=Rd, ψ=0, finite R~, and ε≤F(x0)−F(x⋆). (1): Extends to composite constraints; needs only initial-distance radius R, no exact line search or function values. On this smooth restriction, prox updates are closed form. (1): Extra logarithmic factors when R~=O(R).

Abbr: ℓ=1+log⁡(1+Δ/ε). L0,L1 are gradient-norm smoothness constants; G bounds ∥∇f(x⋆)∥. Gψ is the Lipschitz constant of ψ; R′ bounds initial distance to a minimizer of f+ψλ, where ψλ is the Moreau envelope and λ=ε/Gψ2. R~=supf(x)≤f(x0)∥x−x⋆∥. The δ-family is f(x,y)=2eδycosh⁡x, ψ(x,y)=|x|+2δ|y|, Q=R2, x0=(0,1/δ), 0<δ≤1, with R=1/δ, Δ=2e, H0=2e, H1=e and L1≥1/δ.

Lobanov, Aleksandr. 2026. A Few Accelerated Algorithms for Convex Optimization Under (H0,H1)-Smoothness. https://doi.org/10.48550/arXiv.2608.04884.
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.
LongTails: CompositeGeneralizedAccelerated. 2026. Repository theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/CompositeGeneralizedAccelerated.lean.

Lean setup