← All setups

Polynomial Dimension Generalized Smooth Lower Bound — Generalized Smoothness in Polynomial Dimension

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smoothness in Polynomial Dimension · Lean proof

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.

Proved result

⌊L1⋅R4096⋅log⁡(2+L1⋅R)⌋+

OracleTemplate.NonConvergence LongTails.Setups.GeneralizedSmoothConvexPolynomialDimension.spec
  LongTails.Theorems.PolynomialDimensionGeneralizedSmoothLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.