← All setups

Composite Generalized Smooth Minimization

Descriptions may be stale. Consult the linked Lean sources.

Composite Generalized Smooth Minimization

We consider minimizing F=f+ψ over a convex set Q in a real Hilbert space E, where f,ψ:E→R. The function f is convex and continuously differentiable, ψ is convex on Q, and f is (L0,L1)-smooth with L0>0 and L1≥0. A given point x0∈Q has bounded distance and objective gap to a minimizer x⋆, whose gradient norm is bounded. The oracle returns ∇f(x) at x and exact constrained proximal minimizers. For ε>0, the goal is x¯∈Q 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). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The parameters satisfy L0>0,L1≥0,R>0,Δ>0,G≥0,ε>0. The algorithm receives only E,L0,L1,R,Δ, and x0; G and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

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

Assumption 2 (Generalized smoothness). The function f is Fréchet differentiable everywhere on E, and ∇f:E→E is continuous. For every x,y∈E and M∈R, the implication ∥∇f(x+θ(y−x))∥≤Mfor every θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥ holds.

Assumption 3 (Exact proximal access). There is a map T:R×E×E→E such that, for every a>0 and z,v∈E, T(a,z,v)∈argminu∈Q{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}.

Assumption 4 (Initialization and minimizer bounds). The given starting point satisfies x0∈Q. There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,∥∇f(x⋆)∥≤G.

The oracle returns ∇f(x) at x. It also accepts a proximal query (a,z,v)∈R×E×E and returns T(a,z,v); the minimization property is required for a>0. Gradient queries may be made at any x∈E. Gradient and proximal queries each count as one call toward a shared oracle-call budget.

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

Results

Minimize F=f+ψ over convex Q in a real Hilbert space. The function f is convex and continuously differentiable on the whole space, with ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥ whenever ∥∇f∥≤M on [x,y]; ψ is convex on Q, and exact gradient and proximal queries are available. Here L0,R,Δ,ε>0, L1,G≥0, x0∈Q, and some minimizer x⋆∈Q satisfies ∥x0−x⋆∥≤R, F(x0)−F(x⋆)≤Δ, and ∥∇f(x⋆)∥≤G. Target: a feasible output x with F(x)−F(x⋆)≤ε, deterministically.

Accelerated composite optimization under generalized smoothness: CompositeGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) CompositeGeneralizedAccelerated (Ours) (⋆⋆⋆) (review) O((L0+L1G)R2ε+(1+L1R)log(2+(1+L1R)ΔL0R2)) gradient/prox calls (3K total).
(2) (Tyurin 2026), Thm. 4.3. Special case: Q=Rd, ψ=0, G=0; twice differentiable f; R=∥x0−x⋆∥. O(1+L0R2ε+L1Rlog+(min{L12ΔL0,Δε})+log+ΔL0R2) gradient calls; R¯=R, Γ0=2Δ/R2. (1): Scope extends acceleration to constrained/composite objectives with ∇f(x⋆)≠0. Matches the leading rate on the overlap, up to logarithmic terms. (1): Larger logarithmic term can occur when L1>0, ε>L0/L12; worse leading constant on the overlap.
(3) AC-FGM (Li and Lan 2024), Cor. 1 and local-smoothness remark. Finite-dimensional, closed Q and closed convex ψ. O(1+L¯(R2+d12)ε) gradient, value and prox calls in total; arbitrary initial η1>0, fixed β=1/10. (1): No function values; explicit accelerated composite bound in setup parameters. Rates are not comparable through an unspecified trajectory curvature L¯. (1): Needs L0,L1,R,Δ for updates and G for its stopping budget; (3) has parameter-free updates.

Abbr: Each gradient, value or prox evaluation counts as one call. A prox query minimizes ∥u−z∥2/(2a)+⟨v,u−z⟩+ψ(u) over u∈Q, a>0. log+⁡t=max{0,log⁡t} for t>0, with log+⁡0=0. In (3), z0=x0, d1=∥z1−z0∥, and L¯=supt≥1max{[4(1−β)η1]−1,ℓ1,…,ℓt}; ℓt are the curvature estimates in Eqs. (2.12)–(2.13), distinct from L0,L1.

Li, Tianjiao, and Guanghui Lan. 2024. A Simple Uniformly Optimal Method Without Line Search for Convex Optimization. https://doi.org/10.48550/arXiv.2310.10082.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.

Lean setup