← All setups

Generalized Smooth Composite Minimization

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Composite Minimization

We minimize F=f+ψ on a real Hilbert space E, where f:E→R is convex and continuously differentiable, and ψ:E→R is convex and M-Lipschitz, with M≥0. The function f is (L0,L1)-smooth, with L0,L1>0. A given point x0∈E satisfies ∥x0−x⋆∥≤R for some global minimizer x⋆ of F, where R>0. The oracle returns exact gradients, regularizer values, and proximal points. 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. The algorithm receives only E, L0, L1, M, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convexity and Lipschitz regularizer). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y). Moreover, for all x,y∈E, |ψ(x)−ψ(y)|≤M∥x−y∥.

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 S∈R, the implication ∥∇f(x+θ(y−x))∥≤Sfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1S)∥x−y∥ holds.

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

Assumption 4 (Initial distance). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R.

The oracle returns ∇f(x) at x. It also returns ψ(x) for a value query at x, and T(a,z,v) for a proximal query (a,z,v)∈R×E×E. Each query counts as one call toward a shared oracle-call budget. All point queries may be made anywhere in E.

After the allotted calls, the output must satisfy F(x¯)−F(x⋆)≤εP-a.s. The minimizer in this requirement is fixed independently of the algorithm’s randomness.

Results

On a real Hilbert space, minimize F=f+ψ over the whole space. The function f is convex with continuous gradient and satisfies ∥∇f(x)−∇f(y)∥≤(L0+L1S)∥x−y∥ whenever ∥∇f∥≤S along [x,y]. The function ψ is convex and M-Lipschitz. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R; L0,L1,R,ε>0, M≥0. Exact gradient, composite-proximal and ψ-value queries are available. The target is F(x^)−F(x⋆)≤ε, deterministically (hence almost surely).

Sufficient oracle budgets for LipschitzCompositeGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) LipschitzCompositeGeneralizedAccelerated (Ours) (⋆⋆⋆) (review) O((L0+L1M)R2/ε+(1+q)log⁡(2+q)) total gradient, prox and ψ-value calls.
(2) (Li et al. 2026), v3, Theorem 8 (upper bound) O((L0+L1M)R2/ε+(1+q)⋅[q+log(2+((L0+L1M)/L12+MR)/ε)]) gradient/prox calls, using τ=M and a radius-derived gap bound; f twice differentiable on Rd. (1): transient qlog⁡q instead of q2 when q≥2, (L0+L1M)/(L14R2)≪ε≤(L0+L1M)/L12. For L0=L1=M=ε=1, R=q: O(qlog⁡q) versus O(q2). Matches the leading order as ε→0 at fixed remaining parameters. Adaptivity: no R or gap bound in updates. Scope: Hilbert, C1. (1) needs ψ values; excludes constraints and non-Lipschitz ψ. With known τ≪M, (2) has leading term (L0+L1τ)R2/ε.
(3) Derived bound: Moreau smoothing and regularization, then (Rudomanov et al. 2026), Theorem 3.7 O((L0+L1M)R2/ε+MR/ε+(1+q)log⁡(2+q)) gradient/prox calls; on Rd, M>0, smoothing μ=ε/M2 and regularizer ε∥x−x0∥2/(4R2). (1) removes MR/ε; unbounded total-cost gain when ε≪M2/(L0+L1M) and ε≪MR/[(1+q)log⁡(2+q)]. Updates need neither R nor ε. (1) additionally needs ψ values.
(4) (Rudomanov et al. 2026), v2, Theorem 3.7 O(L0R2/ε+(1+q)log⁡(2+q)) gradient calls; special case ψ≡0, M=0, on Rd. (1): Scope: Lipschitz-composite objectives. Matches known rate on the overlap; updates need neither R nor ε.

Abbr: q=L1R; log is natural. Prox denotes the exact minimizer of ∥u−z∥2/(2a)+⟨v,u−z⟩+ψ(u) for a>0. In (2), τ≥∥∇f(x⋆)∥ and the warm-start scale satisfies Γ0R2≥2(F(x0)−F(x⋆)); the displayed bound uses Γ0R2=2[(L0+L1M)L1−2(eq−1−q)+2MR].

Li, Chenyi, Zhijian Lai, Dong An, Jiang Hu, and Zaiwen Wen. 2026. A Human-AI Collaborative Workflow for Mathematical Discovery: A Case Study in Grover-Compatible Riemannian Optimization. https://doi.org/10.48550/arXiv.2512.09443.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest, Part i: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2610.21461.

Lean setup