← All setups

Weakly Convex Silver — Gradient Descent for Weakly Convex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent for Weakly Convex Optimization · Lean proof

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.

Proved result

⌈32⋅L⋅(ρL)320⋅Δε2⌉++⌈13⋅(L⋅Δε2)45⌉++3

OracleTemplate.Convergence LongTails.Setups.SmoothWeaklyConvex.spec OracleTemplate.WeaklyConvexSilverGd.budget

Relevant previous results

  • Guanghui Lan and Yu Yang. Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization. 2019 (preprint 2018; version 5 consulted). Complexity: O(1+L/μ(1+μΔ/ε2)log⁡(2+L/μ)) fixed-budget exact-gradient calls, including initialization, for single-component unconstrained RapGrad to obtain E∥∇f(x)∥2≤ε2. Here μ=min{L,max{ρ,ε2/Δ}} is a positive weak-convexity upper bound when Δ>0; Δ=0 requires only returning x0.