← 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:Rd→R in dimension d∈N. The function f is (L0,L1)-smooth, meaning its differentiable gradient satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥ everywhere, with L0>0 and L1≥0. A given point x0∈Rd lies within distance R>0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is an output x¯∈Rd with integrable objective gap and EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean norm and its induced operator norm. The parameters obey L0>0,L1≥0,R>0,0<ε≤L0R216,d≥⌈17592186044416(1+L1R+L0R2ε)5⌉. The algorithm receives d, L0, L1, x0, R, and ε.

Our assumptions:

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

Assumption 2 (Generalized smoothness). The function f is differentiable everywhere, its gradient is Fréchet differentiable everywhere, and ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈Rd. Here ∇2f(x):Rd→Rd is the derivative of the gradient.

Assumption 3 (Initial distance). There exists x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R.

Queries may be made at any point of Rd. After the allotted oracle calls, the output must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Results

Convex f:Rd→R has a differentiable gradient with ∥∇2f(x)∥≤L0+L1∥∇f(x)∥ and a minimizer x⋆ satisfying ∥x0−x⋆∥≤R. Public parameters satisfy L0,R,ε>0, L1≥0, ε≤L0R2/16, and d≥⌈244(1+L1R+L0R2/ε)5⌉. Arbitrary adaptive randomized algorithms receive exact gradients. The target is integrable expected objective error ∫[f(x^(ω))−f(x⋆)]dP(ω)≤ε, where P is the algorithm’s seed law.

Lower bounds (necessary oracle budgets) for GeneralizedSmoothConvexFull.
Result Oracle complexity Novelty Limitations
(1) FullGeneralizedSmoothConvexLowerBound (Ours) (⋆⋆) (review) Lower bound: 1+N=Ω(1+L0R2/ε+L1Rlog⁡(2+L1R)) gradient calls; randomized, fixed budgets.
(2) (Rudomanov et al. 2026a), Thm. 4.10 Lower bound: 1+N=Ω(1+L0R2/ε+L1Rlog⁡(2+L1R)) value–gradient calls; deterministic; ε≤L0R2. (1): Scope: randomized instead of deterministic hardness for expected accuracy, retaining arbitrary queries and outputs. (1): Initialization term is weaker by log⁡(2+L1R) when L0R2/ε≤L1R/log⁡(2+L1R). Gradient-only hardness; larger dimension requirement and worse constant.
(3) Classical smooth lower bound (Garg et al. 2021), Secs. 1–2; L1=0, ball-domain model Lower bound: N=Ω(L0R2/ε) value–gradient calls; randomized, high dimension. (1): Scope: extends to L1>0, adding L1R/log⁡(2+L1R); matches classical smooth accuracy scaling at L1=0. (1): Gradient-only hardness. Ball-domain and unrestricted-query models differ; full oracle-complexity bounds are not directly comparable.
(4) (Rudomanov et al. 2026b), Thm. 7.1; finite sums Lower bound: Ω(T0/log2⁡N0) expected component value–gradient calls. Requires n≥2, δ>0, L12R2δ/ε≥3, Δ≥2ε; convex C2 components bounded below, ∥∇2fi∥≤L0,i+L1∥∇fi∥, n−1∑iL0,i≤L0. (1): Single-function randomized hardness at fixed budgets. Rates not comparable: no established n=1 reduction; identical components have δ=0, outside (4)’s range.

Abbr: N: oracle-call budget; Ω: necessary-budget lower bound, with universal constants suppressed. In (4), f=n−1∑ifi, Δ≥f(x0)−f(x⋆), δ≥f(x⋆)−n−1∑iinffi; T0=n(1+(L1R)2/3)+n(L0+L12δ)R2/ε+n(L1R)2 and N0=4+n+(L0+L12δ)R2/ε+(L1R)2.

Garg, Ankit, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. 2021. “Near-Optimal Lower Bounds for Convex Optimization for All Orders of Smoothness.” Advances in Neural Information Processing Systems 34: 29874–84. https://proceedings.neurips.cc/paper_files/paper/2021/file/fa6c94460e902005a0b660266190c8ba-Paper.pdf.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026a. Descending Everest, Part i: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2610.21461.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026b. Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-Smooth Functions. https://doi.org/10.48550/arXiv.2611.04171.

Lean setup