Pipeline-generated

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.

✓ 3 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Implicit bias of gradient-based learning — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Zero-initialized descent on an underdetermined system

Example

Take $X = [1 1] \in R^{1 \times 2}$ , $y = 1$ , and $F (w) = \frac{1}{2} (w_{1} + w_{2} - 1)^{2}$ . Starting from $w_{0} = (0, 0)$ , use fixed step $η = \frac{1}{4}$ . The iterates are $w_{k} = \frac{1}{2} (1 - 2^{- k}) (1, 1)$ and converge to $(\frac{1}{2}, \frac{1}{2})$ , the unique minimum-Euclidean-norm least-squares solution among the nonunique minimizers $w_{1} + w_{2} = 1$ .

Facts & Assumptions

Given: The stated matrix, response, objective, initial vector, and fixed step.

[F1]

Zero-initialized gradient descent selects minimum-norm least squares: when $X \neq 0$ and $0 < η \leq 1 / λ_{\max} (X^{T} X)$ , zero-initialized gradient descent converges to the unique minimum-norm least-squares minimizer.

Verification

1.1givenF1algebra

Here $X^{T} X = (\begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array})$ has eigenvalues $2$ and $0$ , so $λ_{\max} = 2$ and $0 < η = \frac{1}{4} \leq \frac{1}{2}$ . Thus the general selector theorem [F1] applies.

2.1givenstep 1.1algebrainduction

If $w_{k} = (a_{k}, a_{k})$ , then $\nabla F (w_{k}) = (2 a_{k} - 1) (1, 1)$ and the update gives $a_{k + 1} = a_{k} - \frac{1}{4} (2 a_{k} - 1) = \frac{1}{2} a_{k} + \frac{1}{4}$ . Starting with $a_{0} = 0$ , induction yields $a_{k} = \frac{1}{2} (1 - 2^{- k})$ , so $w_{k} \to (\frac{1}{2}, \frac{1}{2})$ .

3.1givenstep 2.1algebra∎

The least-squares minimum is zero, attained exactly when $w_{1} + w_{2} = 1$ . For every such vector, $w_{1}^{2} + w_{2}^{2} = \frac{1}{2} + \frac{1}{2} (w_{1} - w_{2})^{2} \geq \frac{1}{2}$ , with equality exactly when $w_{1} = w_{2} = \frac{1}{2}$ . Hence $(\frac{1}{2}, \frac{1}{2})$ is the unique minimum-norm solution reached in step 2.1.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A redundant active margin with zero KKT multiplier

Example

Consider the two positive examples $x_{1} = (1, 0)$ and $x_{2} = (1, 1)$ in $R^{2}$ with bias-free score $w \mapsto ⟨ w, x ⟩$ . Their hard-margin constraints are $w_{1} \geq 1$ and $w_{1} + w_{2} \geq 1$ . The unique minimum-norm feasible vector is $w_{*} = (1, 0)$ ; both constraints are active, but the second active constraint has a KKT multiplier equal to zero.

Example references

Bias-free margins and hard-margin problem

Margin-form Clarke KKT conditions

Daniel Soudry et al., The Implicit Bias of Gradient Descent on Separable Data, Appendix B discussion of support vectors

Matus Telgarsky, Deep Learning Theory lecture notes, §10.1

Facts & Assumptions

Given: The two-point positive sample, its bias-free linear score, and the hard-margin and Clarke-KKT definitions.

[F1]

Bias-free linear margins and the hard-margin SVM: the signed margin is $m_{i} (w) = ⟨ w, x_{i} ⟩$ for a positive label, and the hard-margin problem minimizes $\frac{1}{2} ∥ w ∥_{2}^{2}$ subject to every margin being at least one.

[F2]

A strictly separable finite sample has a unique hard-margin vector: a finite strictly separable sample has a unique feasible minimum-norm hard-margin vector.

[F3]

KKT conditions and MFCQ for margin constraints: KKT stationarity represents $w_{*}$ as a nonnegative combination of active margin subgradients, with zero multipliers allowed for active constraints.

[F4]

Clarke subdifferential and gradient-flow trajectory: for a differentiable linear margin, its Clarke subdifferential is the singleton containing its ordinary gradient.

Proof

technique · verify strict separability, solve the two scalar inequalities, and exhibit a valid multiplier vector with a zero coordinate

1.1F1F2givenalgebra

The vector $(1, 0)$ gives both margins equal to one, so the sample is strictly separable. Feasibility forces $w_{1} \geq 1$ , hence $∥ w ∥_{2}^{2} = w_{1}^{2} + w_{2}^{2} \geq 1$ , with equality only for $w = (1, 0)$ . Thus $w_{*} = (1, 0)$ is the unique hard-margin minimizer, consistent with [F2].

2.1F1F3F4step 1.1algebra∎

Both margins at $w_{*}$ equal one. Their ordinary gradients, and hence their Clarke subgradients by [F4], are $(1, 0)$ and $(1, 1)$ . The multipliers $λ_{1} = 1$ and $λ_{2} = 0$ are nonnegative and satisfy $λ_{1} (1 - 1) = λ_{2} (1 - 1) = 0$ and $λ_{1} (1, 0) + λ_{2} (1, 1) = w_{*}$ . These are the KKT conditions in [F3], while the second constraint is active with zero multiplier.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A homogeneous-network KKT point that is not globally optimal

Example

For the single training example $x_{0} = 1$ with label $y_{0} = + 1$ , take two hidden units with square activation, trainable input weights $θ_{1}, θ_{2}$ , zero biases, and fixed output weights $1, 4$ . The resulting degree-two homogeneous score is $q (θ) = θ_{1}^{2} + 4 θ_{2}^{2}$ . The feasible point $θ_{*} = (1, 0)$ is a Clarke KKT point of minimizing $\frac{1}{2} ∥ θ ∥_{2}^{2}$ subject to $q (θ) \geq 1$ , but it is not a global minimizer: $(0, \frac{1}{2})$ is feasible and has strictly smaller norm.

Example references

Finite feedforward graph evaluation convention

Parameter homogeneity and margin convention

Margin-form Clarke KKT conditions

Kaifeng Lyu and Jian Li, Gradient Descent Maximizes the Margin of Homogeneous Neural Networks, discussion following Theorem 4.4

Matus Telgarsky, Deep Learning Theory lecture notes, §10.2

Facts & Assumptions

Given: The degree-two homogeneous margin and the margin-form Clarke KKT definition.

[F1]

Homogeneous classifier margins and exponential training risk: a margin of degree $L$ satisfies $q (c θ) = c^{L} q (θ)$ .

[F2]

KKT conditions and MFCQ for margin constraints: a feasible point is Clarke KKT if nonnegative multipliers and Clarke subgradients satisfy stationarity and complementary slackness.

[F3]

Finite feedforward computation graphs and layered MLPs: each non-input node evaluates an activation at a weighted sum of earlier node values and a bias.

Proof

technique · compute the gradient, the KKT multiplier, and the objective values at the two feasible points

1.1F1F2F3givenalgebra

The stated two-node graph evaluates the hidden values $θ_{1}^{2}$ and $θ_{2}^{2}$ and combines them with its fixed output weights, so its score is $q (θ) = θ_{1}^{2} + 4 θ_{2}^{2}$ and $q (c θ) = c^{2} q (θ)$ for every $c > 0$ . At $θ_{*} = (1, 0)$ , $q (θ_{*}) = 1$ and $\nabla q (θ_{*}) = (2, 0)$ , so $\nabla q (θ_{*}) \in \partial^{\circ} q (θ_{*})$ and the multiplier $λ = \frac{1}{2}$ gives $θ_{*} = λ \nabla q (θ_{*})$ . Complementary slackness holds because the sole constraint is active. Thus [F2] gives the KKT property.

2.1F2step 1.1algebra∎

The point $(0, \frac{1}{2})$ satisfies $q (0, \frac{1}{2}) = 1$ and is feasible. The objective at $θ_{*}$ is $\frac{1}{2}$ , whereas at $(0, \frac{1}{2})$ it is $\frac{1}{2} (\frac{1}{4}) = \frac{1}{8} < \frac{1}{2}$ . Therefore $θ_{*}$ is not a global minimizer.

Implicit bias of gradient-based learning — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

Zero-initialized descent on an underdetermined system

Example

Facts & Assumptions

Verification

A redundant active margin with zero KKT multiplier

Example

Example references

Facts & Assumptions

Proof

A homogeneous-network KKT point that is not globally optimal

Example

Example references

Facts & Assumptions

Proof

Sources