← All setups

Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Convex Minimization

We consider minimizing a convex function f:E→R on a real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0, and has an everywhere differentiable gradient. A given point x0∈E satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆, where R,Δ>0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, L0, L1, R, Δ, and x0; the tolerance ε may enter the oracle-call budget but is not an algorithm input.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Generalized smoothness). The function f is Fréchet differentiable everywhere on E, and its gradient ∇f:E→E is Fréchet differentiable everywhere. Its Hessian ∇2f(x):E→E satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈E.

Assumption 3 (Minimizer and initialization). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

Convex f:E→R on a real Hilbert space has a differentiable gradient satisfying ∥∇2f(x)∥≤L0+L1∥∇f(x)∥ everywhere. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ, with L0,R,Δ,ε>0 and L1≥0. Exact gradients are available; L0,L1,R,Δ are public inputs. The target is f(xout)−f(x⋆)≤ε almost surely; our constructions guarantee it for every seed. The setup imposes no algorithm restriction.

Oracle-complexity upper bounds for GeneralizedSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) GeneralizedSelfNormalizedConvex (Ours) (⋆⋆⋆) (review) O(1+L0R2/ε+min{⌈q2/3⌉ℓ,ℓ+(qℓ)2/3}) gradients
(2) GeneralizedAcceleratedConvex (Ours) (⋆⋆⋆) (review) O(1+L0R2/ε+⌈q2/3⌉ℓ) gradients

(3) AGD (Tyurin 2026, Theorem 4.3, v2)

E=Rd; derived bound

O(1+L0R2/ε+qlog(1+min{L12ΔL0,Δε})+log(1+ΔL0R2)) gradients.

R¯=R, Γ0=2Δ/R2, using a flat-coordinate extension.

(1): for q→∞, Δ=L0R2, ε=L0R2q−4/3, total O(qlog⁡q)→O((qlog⁡q)2/3).

(2): O(q2/3log⁡q) in that regime. Matches the leading ε−1/2 rate.

(2): startup can be worse when ε<L0/L12 and q2/3ℓ>L0R2/ε; its logarithm does not saturate.

(1), (2): two gradients per iteration instead of one; restricted to full domains.

(4) AGMsDR (Vankov et al. 2025, Theorem 6.2, v3)

E=Rd, f∈C2

O((1+ν)[1+L0R2/ε+⌈q2/3⌉ℓ]) gradient/value calls, including exact segment searches; ν has no parameter bound.

(1): startup q2/3ℓ→(qℓ)2/3 for q≥ℓ.

(2): matches iteration rate.

(1), (2): bounded gradient-only cost; no values or exact search. Total-call rates are not comparable with unbounded ν.

(1), (2): need R,Δ in addition.

(5) Accelerated GRAAL (Borodich and Kovalev 2025, Corollary 3, v2)

E=Rd, f∈C2, L1>0

O(1+L0R2/ε+q3+(1+q2)log⁡1η0L0) gradient/value calls, for 0<η0≤e−q/L0.

(1), (2): no values. For q→∞, η0=e−q/L0, Δ=L0R2, ε=L0R2q−4, total O(q3)→O(q2).

(2): startup q3→q2/3ℓ when ℓ≪q7/3.

(1), (2): need L0,L1,R,Δ; (5) updates need only an admissible η0. Our startup depends on accuracy.

Abbr: q=L1R; ℓ=1+log⁡(1+Δ/ε); ∇2f=D∇f; η0 is the initial stepsize; ν is the maximum gradient/value call cost of one exact segment minimization. Costs count all gradient evaluations, including trials, and values where used.

Borodich, Ekaterina, and Dmitry Kovalev. 2025. Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization. https://doi.org/10.48550/arXiv.2507.09823.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.
Vankov, Daniil, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U. Stich. 2025. Optimizing (L0,L1)-Smooth Functions by Gradient Methods. https://doi.org/10.48550/arXiv.2410.10800.

Lean setup