← All setups

Convex Minimization with Hidden Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Hidden Smoothness

We consider minimizing a convex function f:E→R on a real Hilbert space E. The function f is (L0,L1)-smooth with hidden constants L0>0 and L1≥0, and has a differentiable gradient. A given point x0∈E satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆ and hidden bounds 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 only E, x0, and a scalar h0>0; the parameters L0,L1,R,Δ, and ε may enter the oracle-call budget but are not algorithm inputs.

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 (Initial distance and objective gap). 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. The minimizer x⋆ is fixed independently of the algorithm’s randomness.

Results

Convex f:E→R on a real Hilbert space, with differentiable gradient and ∥∇2f(x)∥≤L0+L1∥∇f(x)∥ everywhere. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ, where L0,R,Δ,ε,h0>0 and L1≥0. Exact gradients are available. Target: f(x^)−f(x⋆)≤ε. In (1), updates receive only x0,h0; the sufficient stopping budget depends on the problem parameters and ε.

Comparison for GeneralizedSmoothParameterFree.
Result Oracle complexity Novelty Limitations
(1) BacktrackingGeneralizedAccelerated (Ours) (⋆⋆⋆) (review) O(L0R2/ε+(1+s)log⁡(2+s+1L0h0+L0h0+L12ΔL0+L12Δh0)) gradient calls, including two per trial and all rejected trials.
(2) Accelerated GRAAL (Borodich and Kovalev 2025, Cor. 3, v2). Restriction: E=Rd, f∈C2, L1>0. O(1+L0R2/ε+s3+(1+s2)log⁡1L0η0) gradient and value calls; requires L0η0es≤1.

(1): for s≫1, h0=η0, Δ=f(x0)−f(x⋆), proved start-up improves by a factor of order s; total gain when ε≳L0R2/s6. Allows any h0>0; removes values. Matches order for s≲1 or accuracy-dominated costs.

Example: f(x)=ex−x, L0=L1=1, x0=R≫1, h0=η0=e−R: (1) O(R/ε+R2) versus (2) O(R/ε+R3).

(1): backtracking incurs constant-factor overhead.
(3) AGD (Tyurin 2026, Thm. 4.3, v2). Restriction: E=Rd; R=∥x0−x⋆∥ for the displayed tuning. O(1+L0R2/ε+slog⁡(2+min{L12ΔL0,Δε})+log⁡(2+ΔL0R2)) gradient calls; supplied L0,L1, R¯=R, Γ0=2Δ/R2. (1): removes L0,L1,R,Δ from updates; matches the leading ε−1/2 term. No established rate improvement. (1): possible (1+s)log⁡(L0h0+1/(L0h0)) and (1+s)log⁡(2+s) overhead; loses the shortcut when Δ/ε<L12Δ/L0. Backtracking constant factor.
(4) AGMsDR (Vankov et al. 2025, Thm. 6.2, v3). Restriction: E=Rd, f∈C2. O((ν+1)[1+L0R2/ε+⌈s2/3⌉(1+log⁡(Δ/ε))]) gradient/value calls; 0<ε≤Δ=f(x0)−f(x⋆). Requires L0,L1 and exact one-dimensional minimization. (1): no L0,L1, values, or exact line search; start-up logarithm is independent of ε. Total rates are not comparable: ν has no parameter bound. (1) loses the s2/3 start-up power, ignoring the unbounded search factor ν.

Abbr: s=L1R; h0 and η0 are initial step sizes; R¯ is a supplied distance bound; Γ0 is AGD’s initial potential parameter; ν bounds the gradient/value calls per exact one-dimensional search. log denotes the natural logarithm.

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