← All setups

Radius-Constrained Composite Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Radius-Constrained Composite Convex Minimization

We minimize F=f+ψ over a convex set Q in a real Hilbert space E, where f:E→R is differentiable and convex and ψ:E→R is convex on Q. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A given x0∈Q satisfies ∥x0−x⋆∥≤R and ∥∇f(x⋆)∥≤G for some minimizer x⋆, where R>0 and G≥0. The oracle returns exact gradients and constrained proximal minimizers. For ε>0, the goal is a feasible output x¯∈Q with F(x¯)−F(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

Writing F(x)=f(x)+ψ(x), the optimization problem is minx∈QF(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The algorithm receives E, L0, L1, R, ε, and x0; the bound G may enter only the oracle-call budget.

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),x,y∈E,ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y),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, ∥∇f(x+θ(y−x))∥≤Mfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

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∈Q{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}.

Assumption 4 (Initial distance and minimizer gradient). 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(x⋆)∥≤G.

The oracle returns ∇f(x) at x. It also returns T(a,z,v) on a proximal query (a,z,v). Gradient queries may use any x∈E, and proximal queries may use any a∈R and z,v∈E; the proximal minimization requirement applies only for a>0. Both query types 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. Here P is the law of the algorithm’s randomness, and x⋆ is a fixed minimizer independent of that randomness.

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+L1supz∈[x,y]∥∇f(z)∥)∥x−y∥; ψ is convex on Q. Exact gradients and an exact joint prox of ψ+ιQ are available. Here L0,R,ε>0, L1,G≥0, x0∈Q, and some minimizer x⋆∈Q satisfies ∥x0−x⋆∥≤R and ∥∇f(x⋆)∥≤G. Target: feasible x with F(x)−F(x⋆)≤ε, deterministically.

Sufficient oracle budgets for RadiusCompositeGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) RadiusCompositeAccelerated (Ours) (⋆⋆⋆) (review) O(((1+a)4/3+T)ℓ2) gradient and joint-prox calls, including initialization and rejected trials.
(2) AGLS (Deng and Gao 2026), Thm. 6.1, Prop. 6.2. O(1+ea/2T+log+⁡(L⋆/Linit)) gradient, prox and value calls; worst-ball substitution upper bound. Applies in Rd with closed ψ+ιQ. (1): polynomial dependence on a replaces the exponential substitution bound; no function values. For a≤1, matches the accuracy term up to ℓ2. (1) needs L0,L1,R,ε in updates and G for stopping. (2) allows general continuous local curvature.
(3) Derived bound (LongTails 2026): prox initialization and gap certificate. O(T+(1+a)(1+a+log⁡(1+L1G/L0))) gradient and prox calls, conditional on the initialized certificate Δ≲(L0+L1G)eO(a)R2. (1): gain when a≫1 and Tℓ2≪a2. At T=a2, log⁡(1+L1G/L0)=O(a): O(a4/3log2⁡a) instead of O(a2). (1) adds ℓ2 to the T term.
(4) Gap-based acceleration (LongTails 2026). O(1+T+(1+a)⋅log(2+(1+a)ΔL0R2)) gradient and prox calls; supplied Δ≥F(x0)−F(x⋆). (1): no initial objective-gap bound is needed. Small known Δ can make (4) cheaper; (1) adds ℓ2 to the T term.
(5) (Rudomanov et al. 2026), Thm. 3.7. O(L0R2/ε+(1+a)log⁡(2+a)) gradient calls. Special case: E=Rd, Q=E, ψ=0, G=0; L1>0. (1): scope extends to constrained composite objectives and minimizers with nonzero smooth-part gradient. On the overlap, (1) has a4/3 rather than a transient dependence, with additional logarithmic factors; its prox becomes a closed-form update.

Abbr: a=L1R, T=(L0+L1G)R2/ε, ℓ=log⁡(2+a+T); Δ is an initial gap bound at the indicated starting point; ιQ is the convex indicator of Q. In (2), L⋆=2supx,y∈BR(x⋆)L(x,y)≲(L0+L1G)ea, where L is the local gradient Lipschitz coefficient; Linit>0 is the initial line-search estimate; log+⁡t=max{0,log⁡t}. Each primitive gradient, prox or value evaluation counts as one call; all budgets are sufficient upper bounds.

Deng, Qi, and Wenzhi Gao. 2026. A Smooth Approximation Framework for Weakly Convex Optimization. https://doi.org/10.48550/arXiv.2512.09720.
LongTails: CompositeGeneralizedAccelerated. 2026. Repository theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/CompositeGeneralizedAccelerated.lean.
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