← All setups

Generalized Smoothness in Polynomial Dimension

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smoothness in Polynomial Dimension

We consider minimizing a convex function f:Rd→R in a dimension d∈N subject to a polynomial lower bound. The function f is (L0,L1)-smooth, with L0,L1>0: its differentiable gradient satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥ at every x∈Rd. A given point x0 lies within distance R>0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯ with 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 ∥⋅∥op denotes the induced operator norm. The algorithm receives d, L0, L1, x0, R, and ε.

Our assumptions:

Assumption 1 (Parameter regime). The positive parameters satisfy L1R≥1048576,L0L12≤ε≤L0R216,d≥⌈17592186044416(1+L1R)5⌉.

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

Assumption 3 (Generalized smoothness). The function f is Fréchet differentiable everywhere, its gradient is Fréchet differentiable everywhere, and ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈Rd. Here ∇2f(x) is a linear operator from Rd to Rd.

Assumption 4 (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 x¯∈Rd must have an integrable objective gap and satisfy EP[|f(x¯)−f(x⋆)|]<∞,EP[f(x¯)−f(x⋆)]≤ε. The minimizer is fixed independently of the algorithm’s randomness; all global minimizers have the same objective value.

Results

Convex twice differentiable f:Rd→R satisfies ∥∇2f(x)∥≤L0+L1∥∇f(x)∥ and has a minimizer x⋆ with ∥x0−x⋆∥≤R; no initial-gap bound. Parameters are positive, q=L1R≥220, L0/L12≤ε≤L0R2/16, and d≥⌈244(1+q)5⌉. Algorithms may be arbitrary randomized adaptive exact-gradient algorithms. The target is an integrable objective gap with ∫[f(x^(ω))−f(x⋆)]dP(ω)≤ε, where P is the algorithm’s probability law.

Necessary oracle budgets for GeneralizedSmoothConvexPolynomialDimension.
Result Oracle complexity Novelty Limitations
(1) PolynomialDimensionGeneralizedSmoothLowerBound (Ours) (⋆⋆) (review) Lower bound (necessary): N=Ω(q/ℓ) exact-gradient calls; fixed-budget failure on a seed-independent instance.
(2) (Rudomanov et al. 2026a), Thms. 4.8, 4.10 Lower bound (necessary): N=Ω(1+L0R2/ε+q/ℓ) value-and-gradient calls. Deterministic algorithms; ε≤L0R2. (1): Scope: hardness extends from deterministic to arbitrary randomized algorithms, with expected-gap accuracy. (1): Weaker q term by ℓ; no separate L0R2/ε term. Gradient-only hardness; d≥⌈244(1+q)5⌉ versus O(q) in the shared regime. Requires q≥220 and ε≥L0/L12.
(3) (LongTails 2026), repository result, commit 0ed1e4a6 Lower bound (necessary): N=Ω(q/ℓ) exact-gradient calls. Randomized, fixed-budget expected-gap hardness; d≥⌈220(1+q)8e2q⌉; same parameter regime. (1): Scope: required dimension decreases from ⌈220(1+q)8e2q⌉ to ⌈244(1+q)5⌉. Matches the necessary budget and randomized expected-gap criterion.
(4) (Rudomanov et al. 2026b), Thm. 7.1; different finite-sum class Lower bound (necessary expected calls): Ω([n(1+q2/3)+n(L0+L12δ)R2/ε+nq2]/Λ2). Component value-and-gradient oracle; convex bounded-below C2 components, ∥∇2fi∥≤L0,i+L1∥∇fi∥, n−1∑iL0,i≤L0; n≥2, arbitrary dimension, Δ≥2ε, q2δ/ε≥3. (1): Single-objective hardness in polynomial dimension. Finite-sum classes are incomparable: their average need not satisfy the single-function curvature bound. Rates are not comparable; n=1 is excluded. (1): Gradient-only, fixed-budget failure; (4) permits component values and gradients and bounds expected stopping cost.

Abbr: N: necessary calls; q=L1R; ℓ=1+max{0,log⁡q}. For (4), f=n−1∑i=1nfi denotes the finite-sum objective; Δ bounds f(x0)−f⋆, δ bounds f⋆−n−1∑iinffi, and Λ=1+log(n+(L0+L12δ)R2/ε+q2). Ω denotes a necessary budget up to universal factors; larger lower bounds are stronger.

LongTails: RandomizedGeneralizedSmoothTransientLowerBound. 2026. Repository theorem, commit 0ed1e4a6, pull request 166. https://github.com/k3nfalt/longtails/blob/0ed1e4a6/LongTails/Theorems/RandomizedGeneralizedSmoothTransientLowerBound.lean.
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