← All setups

Gradient Descent for Weakly Convex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent for Weakly Convex Optimization

We consider minimizing a differentiable function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and x↦f(x)+(ρ/2)∥x∥2 is convex, with ρ≥0. 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 ε>0, gradient descent must return a queried point x¯ of smallest gradient norm satisfying EP[∥∇f(x¯)∥2]≤ε2, where P is the law of the algorithm’s randomness; with no calls, it returns x0.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which is also equipped with a measurable structure. The algorithm receives E, L, ρ, Δ, ε, and x0.

Our assumptions:

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

Assumption 2 (Weak convexity). The function h:E→R defined by h(x)=f(x)+ρ2∥x∥2 is convex: for every x,y∈E and t∈[0,1], h((1−t)x+ty)≤(1−t)h(x)+th(y).

Assumption 3 (Initial objective gap). There exists ℓ∈R such that ℓ≤f(x)for every x∈E,f(x0)−ℓ≤Δ.

Our result is algorithm-specific: we analyze gradient descent with positive, iteration-dependent step sizes and an output selected by gradient norm. The algorithm chooses a sequence (ηt)t≥0 with ηt>0, fixed independently of oracle replies and algorithm randomness. Starting from the given x0, it queries and updates according to gt=∇f(xt),xt+1=xt−ηtgt,t=0,1,…. Queries may be made at any point of E. After K≥1 oracle calls, the output is jK=max{j∈{0,…,K−1}:∥gj∥2=min0≤i<K∥gi∥2},x¯=xjK. Thus ties are resolved in favor of the most recent query. For K=0, set x¯=x0.

The output must be measurable, its squared gradient norm must be integrable under P, and the required accuracy is EP[∥∇f(x¯)∥2]≤ε2.

Results

On a real Hilbert space, f has an L-Lipschitz gradient, f+(ρ/2)∥⋅∥2 is convex, and f(x0)−inff≤Δ, with L,ε>0 and ρ,Δ≥0. Access is to exact gradients. The setup requires positive predetermined GD steps and the best-gradient queried iterate. The deterministic output satisfies ∥∇f(xout)∥≤ε, hence the setup’s expected squared-gradient target.

Smooth weakly convex optimization: SmoothWeaklyConvex.
Result Oracle complexity Novelty Limitations
(1) WeaklyConvexSilver (Ours) (review) O(1+(ρ/L)3/20T+T4/5)
(2) Constant-step GD, h=1/L (Rotaru et al. 2026, Eq. (12)) O(1+LΔ/ε2) (1): Method-specific speedup factor min{(L/ρ)3/20,T1/5} for 0<ρ≪L, T≫1; at ρ=0, O(1+T4/5) instead of O(1+T). (1) needs ρ,T for scheduling. Large constants: savings require roughly ρ/L≲10−8 and T≳4⋅105 (not sufficient jointly). For ρ>L, its curvature term exceeds T.
(3) Almost-convex-AGD (Carmon et al. 2017, Lemma 3.1)
Derived bound; Rd, 0≤ρ≤L, T≥1
O((LρΔε2+LΔε)log⁡(1+T))
Choose γ=max{ρ,ε2/Δ}. Includes inner gradient calls and stopping checks.
(1): Predetermined GD analysis; (3) uses momentum and gradient-solved regularized subproblems. Same gradient oracle; no established problem-class improvement. (1) has term ratios (L/ρ)7/20/log⁡(1+T) (ρ>0) and T3/10/log⁡(1+T); each loses when its ratio grows. Fixed budget replaces gradient-based stopping.
(4) Long-step GD (Grimmer et al. 2024, Theorem 1)
Special case: Rd, ρ=0, minimizer exists
O(1+(LΔ/ε2)log1+2⁡2) (1): Scope extends to ρ>0 and bounded-below functions without an attained minimum. (1): On the convex overlap, T4/5 instead of T0.7864…; best queried iterate instead of last iterate.

Abbr: L: gradient Lipschitz constant; ρ: weak-convexity modulus; Δ: initial objective-gap bound; ε: gradient-norm accuracy; T=LΔ/ε2; GD: gradient descent; AGD: accelerated gradient descent. All costs count exact gradient calls.

Carmon, Yair, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2017. Accelerated Methods for Non-Convex Optimization. https://doi.org/10.48550/arXiv.1611.00756.
Grimmer, Benjamin, Kevin Shu, and Alex L. Wang. 2024. Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps. https://doi.org/10.48550/arXiv.2403.14045.
Rotaru, Teodor, François Glineur, and Panagiotis Patrinos. 2026. Exact Worst-Case Convergence Rates of Gradient Descent: A Complete Analysis for All Constant Stepsizes over Nonconvex and Convex Functions. https://doi.org/10.48550/arXiv.2406.17506.

Lean setup