← All setups

Smooth Nonconvex Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Smooth Nonconvex Stationarity

We consider a differentiable, possibly nonconvex function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given starting point x0∈E satisfies f(x0)−ℓ≤Δ for a global lower bound ℓ∈R and Δ≥0. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is a measurable output x¯∈E with integrable squared gradient norm satisfying EP[∥∇f(x¯)∥2]≤ε2, where P is the law of the algorithm’s randomness.

We seek approximate stationarity for the optimization problem infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with a measurable structure. The algorithm receives E, L, Δ, ε, and x0; the objective is accessed through the oracle.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Lower bound and initial gap). There exists ℓ∈R such that ℓ≤f(x)for every x∈E,f(x0)−ℓ≤Δ.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable with respect to the given measurable structure on E, and must satisfy EP[∥∇f(x¯)∥2]<∞,EP[∥∇f(x¯)∥2]≤ε2.

Results

A differentiable f:E→R on a real Hilbert space with a measurable structure has L-Lipschitz gradient, L>0, and a lower bound ℓ satisfying f(x0)−ℓ≤Δ, Δ≥0. The oracle returns exact gradients. For ε>0, the target is ∫∥∇f(x^(ω))∥2dP(ω)≤ε2, where P is the execution law. Result (1) constructs GD with step 1/L and returns the deterministic queried point of smallest gradient norm; the setup does not restrict the algorithm.

Smooth nonconvex stationarity: SmoothNonconvex.
Result Oracle complexity Novelty Limitations
(1) GdNonconvex (Ours) (review) O(1+LΔ/ε2)
(2) Classical GD, η=1/L (Abbaszadehpeivasti et al. 2022, sec. 1) O(1+LΔ/ε2) (1): Matches known rate; machine-checked formalization. Already order-optimal in sufficiently high dimension (Carmon et al. 2020, Thms. 1–2, p=1). (1) needs Δ for its fixed budget; gradient-norm stopping does not.
(3) GD, η=1/L (Abbaszadehpeivasti et al. 2022, Thm. 2, (16))

O(1+LΔ/ε2)

E=Rd, attained minimum.

(1): Matches known rate on this finite-dimensional restriction; no established improvement. (1) has about 1.5 times the leading call constant when LΔ/ε2≫1.
(4) GD, η=4/3/L (Abbaszadehpeivasti et al. 2022, Thm. 2, (15))

O(1+LΔ/ε2)

E=Rd, attained minimum.

(1): Matches known rate on this finite-dimensional restriction; no established improvement. (1) has about 1.54 times the leading call constant when LΔ/ε2≫1.

Abbr: GD: gradient descent; η: step size; L: gradient Lipschitz constant; Δ: initial objective-gap bound; ε: target gradient norm; d: dimension. Costs count exact gradient evaluations, including the terminal gradient used for selection or stopping.

Abbaszadehpeivasti, Hadi, Etienne de Klerk, and Moslem Zamani. 2022. “The Exact Worst-Case Convergence Rate of the Gradient Method with Fixed Step Lengths for L-Smooth Functions.” Optimization Letters 16: 1649–61. https://doi.org/10.1007/s11590-021-01821-1.
Carmon, Yair, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2020. “Lower Bounds for Finding Stationary Points I.” Mathematical Programming 184: 71–120. https://doi.org/10.1007/s10107-019-01406-y.

Lean setup