AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Gradient descent

Definition

Let $U \subseteq R^{d}$ be open and let $f : U \to R$ be continuously Fréchet differentiable. The gradient $\nabla f (x)$ is the vector of partial derivatives in the Euclidean coordinates, with the convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case; differentiability is the Fréchet condition of The real Frechet derivative on real and complex matrix spaces with the Frobenius norm.

Inputs: an initial point $x_{0} \in U$ ; either a positive fixed-step sequence $(t_{k})_{k \geq 0}$ or backtracking parameters $α \in (0, 1)$ and $β \in (0, 1)$ ; and an optional caller stopping predicate $S (k, x, g) \in {f a l s e, t r u e}$ , with $S : {0, 1, 2, \dots} \times U \times R^{d} \to {f a l s e, t r u e}$ . If no predicate is supplied, use $S \equiv f a l s e$ . Output: when the procedure stops, return the last valid iterate $x_{k}$ and the status stationary, caller-stop, or domain-failure. If no stopping status occurs, the sequence continues and there is no finite return. For example, an outer procedure's at-most- $M$ -updates limit, for finite real $M \geq 0$ , is implemented by $S (k, x, g) : = (k + 1 > M)$ .

At iteration $k$ , where $k$ is the number of accepted updates so far and the current iterate is $x_{k}$ :

Compute $g_{k} : = \nabla f (x_{k})$ and set $p_{k} : = - g_{k}$ . If $g_{k} = 0$ , return $(x_{k}, stationary)$ .
If $S (k, x_{k}, g_{k})$ is true, return $(x_{k}, caller-stop)$ . Check this predicate at the current iterate after its gradient is computed and before any step is selected.
In fixed-step mode, set $t = t_{k}$ . If $x_{k} + t p_{k} \notin U$ , return $(x_{k}, domain-failure)$ without accepting that candidate.
In backtracking mode, start with $t = 1$ and repeatedly replace $t$ by $β t$ until $x_{k} + t p_{k} \in U$ and $f (x_{k} + t p_{k}) \leq f (x_{k}) + α t ⟨ g_{k}, p_{k} ⟩$ .
Set $x_{k + 1} : = x_{k} + t p_{k}$ and continue at iteration $k + 1$ .

The fixed-step update map is $x \mapsto x - t_{k} \nabla f (x)$ ; at a stationary point its value is $x$ , which is the returned iterate. A backtracking search that is reached at a nonstationary iterate is well-defined by Armijo backtracking terminates for strict descent directions ↗. The procedure asserts no convergence or global-minimization property for an arbitrary objective.

Depends on

Used by

Ideal exact gradient line-search step Algorithm
Strong- and weak-constraint 4DVAR with a finite gradient run Algorithm
Unadjusted Langevin algorithm (ULA) Algorithm
Hamiltonian Monte Carlo Definition
A multimodal nonconvex objective Example
Exact and Armijo rates on an anisotropic quadratic Example
Armijo backtracking terminates for strict descent directions Lemma
Armijo gradient descent has an explicit global linear rate Theorem
Gradient descent rate under strong convexity and smoothness Theorem

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Stephen Boyd and Lieven Vandenberghe, Convex Optimization (standard reference, not scraped)