Definition D1
Let f(x) = x², and for a learning rate η > 0 and a starting point x₀, define xₙ₊₁ = xₙ − η f′(xₙ).
Proof.
(1)Since f′(x) = 2x, xₙ₊₁ = xₙ − η·2xₙA1
(2)xₙ − (2η)xₙ = (1 − 2η)xₙ(1), A9, A10, A11, A12
(3)Setting q = 1 − 2η gives xₙ₊₁ = q xₙ. That is, a geometric sequence with ratio q.(2), convention
∎
Definition D2
The sequence (xₙ) diverges when for every M > 0 there is an n with |xₙ| > M.
Proof.
(1)A convergent sequence is bounded, so an unbounded sequence does not converge.A22
∎
Lemma L1
For all n ≥ 0, xₙ = qⁿ x₀.
Proof.
(1)For n = 0: q⁰x₀ = 1·x₀ = x₀A5, A11, A12
(2)Suppose xₙ = qⁿx₀ at n.assumption
(3)xₙ₊₁ = q xₙ = q(qⁿx₀) = (q·qⁿ)x₀ = qⁿ⁺¹x₀(2), D1, A10, A11, A5
(4)By induction the statement holds for all n ≥ 0.(1), (3), A7
∎
Lemma L2
If |q| > 1 and x₀ ≠ 0, then (xₙ) diverges.
Proof.
(1)Since |q| > 1, setting h = |q| − 1 gives h > 0 and |q| = 1 + h.assumption, A13, A18, A19
(2)|xₙ| = |qⁿx₀| = |q|ⁿ|x₀|L1, A6, A7
(3)|q|ⁿ = (1+h)ⁿ ≥ 1 + nh(1), A3
(4)Let M > 0. Since x₀ ≠ 0, |x₀| > 0, and h|x₀| > 0.assumption, A16, A14, A12
(5)By the Archimedean property there is an n with n·(h|x₀|) > M.(1), (4), A4
(6)|xₙ| ≥ (1 + nh)|x₀| = |x₀| + n(h|x₀|) > n(h|x₀|) > M(2), (3), (4), (5), A14, A8, A10, A12, A13, A15
(7)Therefore (xₙ) is not bounded. That is, it diverges.(6), D2
∎
Theorem T1
If η > 1 and x₀ ≠ 0, then (xₙ) diverges.
Proof.
(1)Since η > 1, 2η > 2assumption, A14, N
(2)Adding 1 − 2η − 2 to both sides gives −1 > 1 − 2η, that is, q < −1(1), A13, A18, A19, A20, A21, D1
(3)Since q < −1 < 0, |q| = −q, and adding −q + 1 to both sides of −1 > q gives |q| > 1(2), A17, A13, A18, A19, A20, A21
(4)By L2, (xₙ) diverges.(3), assumption, L2
(5)For η = 1.5, x₀ = 1, we get q = −2 and x₁ = 1 − 1.5·2·1 = −2, x₂ = −2 − 1.5·2·(−2) = 4D1, L1, N
(6)|xₙ| = 2ⁿ, so the values grow without bound. They move away from the minimum at x = 0.(5), L1, A6, N
∎
Theorem T2
If 0 < η < 1, then lim xₙ = 0.
Proof.
(1)Since 0 < η < 1, 0 < 2η < 2assumption, A14, N
(2)Adding 1 to each side and rearranging signs gives −1 < 1 − 2η < 1, that is, |q| < 1(1), A13, A17, A18, A19, A21, D1
(3)Since |q| < 1, lim qⁿ = 0(2), A2
(4)Since xₙ = qⁿx₀, lim xₙ = 0·x₀ = 0(3), L1, A24, A11, A12
(5)For η = 0.25, q = 0.5 and x₁ = 1 − 0.25·2·1 = 0.5, x₂ = 0.25.D1, L1, N
∎
Corollary C
If η = 1 and x₀ ≠ 0, then (xₙ) neither diverges nor converges.
Proof.
(1)If η = 1, then q = 1 − 2 = −1, so xₙ = (−1)ⁿx₀ and xₙ₊₁ = −xₙ.D1, L1, N
(2)|xₙ| = |(−1)ⁿ||x₀| = |x₀|, so (xₙ) is bounded. That is, it does not diverge.(1), A6, A7, A12, D2
(3)xₙ₊₁ − xₙ = −xₙ − xₙ, so |xₙ₊₁ − xₙ| = 2|x₀|(1), (2), A6, A9, A18, N
(4)Since x₀ ≠ 0, 2|x₀| > 0, and this value is constant regardless of n.(3), A16, A14
(5)If the sequence converged, xₙ₊₁ − xₙ would have to tend to 0. Therefore (xₙ) does not converge.(4), A23
(6)η = 1 is the boundary between convergence and divergence. The values neither grow nor shrink; only the sign flips.(2), (5)
∎