TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck passjudge 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.

Zero-initialized gradient descent selects minimum-norm least squares

Statement

Let $n, d \geq 1$ , $X \in R^{n \times d}$ , $y \in R^{n}$ , and $F (w) = \frac{1}{2} ∥ X w - y ∥_{2}^{2}$ . Define the full-batch fixed-step gradient iterates by $w_{0} = 0$ and $w_{k + 1} = w_{k} - η X^{T} (X w_{k} - y)$ for every integer $k \geq 0$ . Here $λ_{\max} (X^{T} X)$ is the largest eigenvalue of the symmetric matrix $X^{T} X$ . If $X \neq 0$ and $0 < η \leq 1 / λ_{\max} (X^{T} X)$ , then $w_{k}$ converges to the unique least-squares minimizer of smallest Euclidean norm. If $X = 0$ , then every $η > 0$ gives the constant iterate $w_{k} = 0$ , which is the unique least-squares minimizer of smallest Euclidean norm.

Statement references

Trevor Hastie et al., Surprises in High-Dimensional Ridgeless Least Squares Interpolation, §2.2, Proposition 1

Cornell CS 3780, Linear Regression, Lecture 12

Facts & Assumptions

Given: A finite real matrix $X \in R^{n \times d}$ , a vector $y \in R^{n}$ , the quadratic objective $F (w) = \frac{1}{2} ∥ X w - y ∥_{2}^{2}$ , and the stated fixed-step iteration from $w_{0} = 0$ .

[F1]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: every self-adjoint endomorphism of a finite-dimensional real inner-product space has an orthonormal eigenbasis.

[F2]

For a linear map $T : V \to W$ between finite-dimensional inner-product spaces, $x$ minimises $∥ T x - b ∥$ if and only if $T^{*} (T x - b) = 0$ , equivalently $T^{*} T x = T^{*} b$ ; minimisers exist and any two differ by an element of $\ker T$ : the least-squares minimizers of a finite-dimensional linear map are exactly the solutions of its normal equation, and any two minimizers differ by a vector in the map's kernel.

[F3]

For every right-hand side $b$ , $A^{+} b$ is the unique least-squares solution of minimum Euclidean norm: for every finite real matrix $A$ and right-hand side $b$ , $A^{+} b$ is the unique least-squares minimizer of minimum Euclidean norm.

[F4]

Gradient descent: fixed-step Euclidean gradient descent uses the update $x_{k + 1} = x_{k} - t_{k} \nabla f (x_{k})$ when the iterate is not stationary.

Proof

technique · diagonalize the positive-semidefinite normal matrix and solve each scalar recurrence

1.1givenalgebra

If $X = 0$ , then $F (w) = \frac{1}{2} ∥ y ∥_{2}^{2}$ for every $w$ , and the displayed update leaves $w_{0} = 0$ fixed. Since $∥ w ∥_{2} \geq 0$ with equality only at $w = 0$ , this is the unique least-squares minimizer of minimum norm.

1.2F1givenalgebrachoose

Suppose $X \neq 0$ and set $A = X^{T} X$ . The matrix $A$ is symmetric, and $⟨ u, A u ⟩ = ∥ X u ∥_{2}^{2} \geq 0$ , so its eigenvalues are nonnegative. By [F1], choose an orthonormal eigenbasis $u_{1}, \dots, u_{d}$ with $A u_{j} = λ_{j} u_{j}$ and $0 \leq λ_{j} \leq λ_{\max}$ . If $λ_{j} = 0$ , then $X u_{j} = 0$ and $⟨ X^{T} y, u_{j} ⟩ = ⟨ y, X u_{j} ⟩ = 0$ ; conversely, $X z = 0$ implies $A z = 0$ , so the zero-eigenvalue space is exactly $\ker X$ .

2.1F4givenstep 1.2algebrainduction

For any increment $h$ , expansion of the square gives $F (w + h) = F (w) + ⟨ X^{T} (X w - y), h ⟩ + \frac{1}{2} ∥ X h ∥_{2}^{2}$ ; since the last term is $O (∥ h ∥_{2}^{2})$ , $\nabla F (w) = A w - X^{T} y$ . Thus the iteration is $w_{k + 1} = (I - η A) w_{k} + η X^{T} y$ , the fixed-step update in [F4]. Writing $c_{j, k} = ⟨ w_{k}, u_{j} ⟩$ and $b_{j} = ⟨ X^{T} y, u_{j} ⟩$ , for $λ_{j} > 0$ induction on $k$ gives $c_{j, k} = \frac{1 - (1 - η λ_{j})^{k}}{λ_{j}} b_{j}$ ; for $λ_{j} = 0$ , $c_{j, k} = 0$ for all $k$ .

3.1givenF1step 1.2step 2.1algebra

The step bound gives $0 \leq 1 - η λ_{j} < 1$ for every positive eigenvalue, including the endpoint $η = 1 / λ_{\max}$ where the largest-eigenvalue factor is zero. Hence $c_{j, k} \to b_{j} / λ_{j}$ when $λ_{j} > 0$ , and the zero-eigenvalue coordinates remain zero. There are finitely many coordinates, so $w_{k}$ converges to a vector $w_{\infty}$ satisfying $A w_{\infty} = X^{T} y$ and $w_{\infty} ⊥ \ker X$ .

4.1F2F3step 3.1algebra∎

By [F2], the normal equation $A w_{\infty} = X^{T} y$ makes $w_{\infty}$ a least-squares minimizer, and every least-squares minimizer is $w_{\infty} + z$ for some $z \in \ker X$ . The orthogonality in step 3.1 yields $∥ w_{\infty} + z ∥_{2}^{2} = ∥ w_{\infty} ∥_{2}^{2} + ∥ z ∥_{2}^{2}$ , with equality to $∥ w_{\infty} ∥_{2}^{2}$ only for $z = 0$ . Thus $w_{\infty}$ is the unique minimum-norm least-squares minimizer, in agreement with [F3].

Depends on

Used by

Zero-initialized descent on an underdetermined system Example

Dependency tree · two levels

14 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

Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani, Surprises in High-Dimensional Ridgeless Least Squares Interpolation, §2.2, Proposition 1 (standard reference, not scraped)
Cornell CS 3780, Linear Regression, Lecture 12, pp. 1–2 (standard reference, not scraped)