← All setups

Parameter-Free Composite Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Parameter-Free Composite Convex Minimization

We consider minimizing F=f+ψ over a convex set Q in a real Hilbert space E, where f:E→R is convex and continuously differentiable and ψ:E→R is convex on Q. The function f is (L0,L1)-smooth with hidden constants L0>0 and L1≥0. A given point x0∈Q has bounded distance and objective gap to a minimizer x⋆, whose smooth gradient is bounded. The oracle returns exact gradients and 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.

Write 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 only E, x0, and a scalar h0>0; the parameters L0>0, L1≥0, R>0, Δ>0, G≥0, and ε>0 may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Convexity). The set Q⊆E is convex, f is convex on E, and ψ is convex on Q. Thus, for 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, the segment bound ∥∇f(x+t(y−x))∥≤Mfor every t∈[0,1] implies ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Exact proximal minimization). 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)}.

Assumption 4 (Initial point and minimizer). The given 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. A proximal query (a,z,v) returns P(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 condition applies when 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. The minimizer x⋆ is fixed independently of the algorithm’s randomness.

Results

Minimize F=f+ψ over convex Q in a real Hilbert space. The function f is convex with continuous gradient and satisfies ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥ whenever ∥∇f(z)∥≤M on [x,y]; ψ is finite-valued and convex on Q. Exact gradients and minimizers of ψ(u)+⟨v,u−z⟩+∥u−z∥2/(2a) over u∈Q are available for every a>0,z,v. There is a minimizer x⋆∈Q with x0∈Q, ∥x0−x⋆∥≤R, F(x0)−F(x⋆)≤Δ, and ∥∇f(x⋆)∥≤G. Here L0,R,Δ,h0,ε>0 and L1,G≥0. Target: deterministic x^∈Q with F(x^)−F(x⋆)≤ε. The constructed method receives only (x0,h0); its stopping budget depends on all setup parameters.

Composite optimization with parameter-free updates: CompositeGeneralizedParameterFree.
Result Oracle complexity Novelty Limitations
(1) BacktrackingCompositeGeneralized (Ours) (⋆⋆⋆) (review)

O(L⋆R2/ε+(1+s)log(2+s+1L⋆h0+L12ΔL⋆)+log⁡(2+L⋆h0+L12Δh0))

Gradient and prox calls; all rejected trials included.

(2) Accelerated proximal gradient (Li et al. 2026, Thm. B.1)

Twice-differentiable f on Rd, ∥∇2f∥≤L0+L1∥∇f∥; proper closed convex proximable h=ψ+ιQ.

O(L⋆R2/ε+log(2+ΔL⋆R2)+(1+s)log⁡(2+Δ/ε))

Gradient and prox calls; Γ0=2Δ/R2.

(1): Updates need no L0,L1,G,R,Δ; matched leading rate. Hilbert-space, first-order smoothness scope. With h0≍L⋆−1, logarithmic overhead improves for L1>0, ε≪min{L⋆/L12,Δ/(1+s)}. (1): Roughly threefold call overhead per accepted step; h0-mismatch logs. For h0≍L⋆−1, ε≳L⋆/L12 can lose a logarithm. Finite-valued ψ rather than general extended-valued h.

(3) Accelerated GRAAL (Borodich and Kovalev 2025, Cor. 3)

Special case: Q=Rd, ψ=0, G=0; C2 Hessian condition as in (2).

O(1+L0R2/ε+s3+(1+s2)log1η0L0)

Gradient and value calls; requires η0L0es≤1.

(1): Composite scope; no values (prox is closed form here); arbitrary h0. On the overlap, s≫1, h0≍L0−1, η0=e−s/L0, L12Δ/L0≲es: O(1+L0R2/ε+s2) versus O(1+L0R2/ε+s3); total gain when ε≫L0R2/s6. (1): Constant-factor backtracking overhead.

(4) AC-FGM (Li and Lan 2024, Cor. 1 and subsequent remark)

Initial-search variant; closed convex Q⊆Rd, closed convex ψ; local Lipschitz bound L¯ covering search points and trials.

O(1+L¯R2/ε+log+L¯ℓ)

Value, gradient and prox calls, including initialization; initial curvature estimate 0<ℓ≤L¯.

(1): No function values; explicit polynomial parameter dependence. Rates are not comparable: no polynomial bound on L¯ in L0,L1,G,R,Δ is established here. (1): Repeated backtracking instead of initial search only.

Abbr: L⋆=L0+L1G; s=L1R; log+⁡t=max{0,log⁡t}. η0 is the initial step in (3); L¯ bounds the local Lipschitz estimates and initial trials in (4), and ℓ is its initial curvature estimate. ιQ is 0 on Q and +∞ outside. Costs count individual exact oracle calls; ≍ and ≲ suppress universal factors.

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

Lean setup