← All setups

Universal Silver Quadratic Growth — Gradient Descent with Quadratic Growth

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent with Quadratic Growth · Lean proof

Gradient Descent with Quadratic Growth

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E with norm ∥⋅∥. Its gradient is L-Lipschitz, with L>0. At each point, the objective gap is at least μ/2 times the squared distance to some global minimizer, where μ>0. A given starting point x0∈E lies within distance R≥0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For ε>0, gradient descent with positive predetermined step sizes must return a last iterate x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely.

The optimization problem is minx∈Ef(x). The norm is induced by the inner product on E. The algorithm receives only E, L, and x0; the parameters μ, R, and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

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

Assumption 2 (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 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 4 (Quadratic growth). For every x∈E, there exists a global minimizer z∈E, possibly depending on x, such that μ2∥x−z∥2≤f(x)−f(z).

Our result is algorithm-specific: we analyze gradient descent. The step-size sequence (ηt)t≥0 is chosen from the algorithm inputs and satisfies ηt>0 for every t. Starting from the given x0, the iterates obey xt+1=xt−ηt∇f(xt),t=0,1,2,…. After K≥0 oracle calls, where K is an integer, the output is the last iterate x¯=xK. The required accuracy is f(x¯)−f(x⋆)≤εP-a.s., where P is the law of the algorithm’s randomness; the specified gradient descent method is deterministic.

Proved result

⌈2⋅(1+2⋅Lμ)log⁡(2)log⁡(1+2)⋅(log2⁡(1+L⋅R2ε)+1)⋅(log2⁡(1+2⋅Lμ)+log2⁡(log2⁡(1+L⋅R2ε)+1)+3)⌉+

OracleTemplate.Convergence LongTails.Setups.SmoothConvexQuadraticGrowth.spec
  LongTails.Theorems.UniversalSilverQuadraticGrowth.budget

Relevant previous results