← All setups

Accelerated Inexact Strongly Convex — Inexact Gradient Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Inexact Gradient Strongly Convex Minimization · Lean proof

Inexact Gradient Strongly Convex Minimization

We consider minimizing a differentiable, μ-strongly convex function f:E→R on a real Hilbert space E, with quadratic upper curvature bound L≥μ>0. A given point x0∈E lies within distance R≥0 of a global minimizer x⋆. At x∈E, the oracle returns a vector g∈E with relative gradient error controlled by α∈[0,1) and additive error controlled by δ≥0. For a tolerance ε>0 compatible with this error, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the joint law of the algorithm’s and oracle’s randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives only E, L, x0, μ, and α; the parameters δ, R, and ε may enter the oracle-call budget but are not algorithm inputs. In addition to the ranges above, the parameters satisfy 136δ2≤μ(1−α)2ε.

Our assumptions:

Assumption 1 (Smoothness and strong convexity). The function f is Fréchet differentiable everywhere on E. For every x,y∈E, f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2,f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2.

Assumption 2 (Inexact gradient oracle). Queries may be made at any point x∈E. Every oracle reply g∈E satisfies ∥g−∇f(x)∥≤α∥∇f(x)∥+δ. This bound holds for every query history and every realization of the oracle randomness. Replies may depend on the history, and the oracle randomness may be dependent across calls. The algorithm’s randomness is independent of the oracle randomness.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Proved result

⌈(8⋅Lμ⋅(1−α)+32⋅α2⋅Lμ⋅(1−α))⋅log⁡(1+2⋅L⋅R2ε)⌉+

OracleTemplate.Convergence LongTails.Setups.InexactGradientStronglyConvex.spec OracleTemplate.InexactGradient.budget

Relevant previous results

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