Sequences, Limits & Convergence

Overview & Motivation

You’ve watched a training loss curve drop toward zero and level off. You’ve seen gradient descent “converge.” You’ve tuned a learning rate schedule until the optimizer “settles down.” But what do any of these phrases actually mean?

When we say a sequence of iterates $\theta_1, \theta_2, \theta_3, \ldots$ converges, we’re making a precise mathematical claim: no matter how tight a tolerance you specify — a billionth, a trillionth, any positive number at all — there is some point in the sequence past which every single term stays within that tolerance of the limit. This is the $\varepsilon$-$N$ definition, and it is where calculus becomes rigorous.

In this topic, we build the complete machinery of sequence convergence from scratch. We start with what a sequence is, move to the $\varepsilon$-$N$ definition that makes “arbitrarily close” precise, prove the core convergence theorems that let us establish limits without computing them directly, and develop the Cauchy criterion that lets us detect convergence without even knowing the limit. Every theorem here has a direct application to machine learning — gradient descent convergence, optimizer guarantees, and the learning rate conditions that make stochastic methods work.

Sequences in ℝ

We begin with the most basic object in analysis: a sequence.

The notation is important: $(a_n)$ with parentheses denotes the entire sequence as an object, while $a_n$ without parentheses denotes a single term. We’ll be careful about this distinction throughout.

Here are four sequences that appear constantly in machine learning:

• $a_n = 1/n$ — the simplest decaying sequence. Learning rate schedules like $\eta_t = c/t$ produce sublinear convergence rates for SGD.
• $a_n = (1 + 1/n)^n$ — converges to Euler’s number $e \approx 2.718$. The natural exponential shows up in softmax, cross-entropy loss, and the exponential family of distributions.
• $a_n = 0.9^n$ — geometric (exponential) decay. This is the momentum coefficient in Adam ($\beta_1 = 0.9$), the discount factor in reinforcement learning, and the convergence rate of gradient descent on strongly convex functions.
• $a_n = (-1)^n / n$ — oscillates but converges to $0$. SGD with noisy gradients exhibits exactly this kind of oscillating convergence.

Sequence:a_n = 1/na_n = (1+1/n)^na_n = 0.9^na_n = (-1)^n / na_n = n²/(n²+1)Max n: 50

Learning rate schedule: η_t = c/t gives O(1/√t) SGD convergence

Among our examples: $(1/n)$ is decreasing, $(1 + 1/n)^n$ is increasing (a non-trivial fact we’ll use later), $(0.9^n)$ is decreasing, and $((-1)^n/n)$ is neither increasing nor decreasing — it oscillates. Monotonicity is a powerful structural property: as we’ll prove shortly, any bounded monotone sequence must converge.

The ε-N Definition of Convergence

We now make the informal idea of “getting arbitrarily close” fully rigorous. This is the definition that separates calculus from hand-waving.

Building the intuition

Consider the sequence $a_n = 1/n$. Intuitively, the terms $1, 1/2, 1/3, 1/4, \ldots$ are “approaching $0$.” But what does “approaching” mean precisely?

Here’s the key idea: pick any tolerance — say $\varepsilon = 0.1$. Then past $n = 10$, every term satisfies $|a_n - 0| = 1/n < 0.1$. Pick a tighter tolerance, $\varepsilon = 0.01$. Then past $n = 100$, every term satisfies $|a_n - 0| < 0.01$. No matter how small a positive $\varepsilon$ you choose, there is always some index $N$ past which all terms lie within $\varepsilon$ of $0$.

The formal definition

Read it carefully: the quantifier structure is $\forall \varepsilon > 0,\ \exists N \in \mathbb{N}:\ n \geq N \Rightarrow |a_n - L| < \varepsilon$. The order matters: $\varepsilon$ is chosen first (by an adversary, if you like), and then we must produce an $N$ that works for that $\varepsilon$. Different values of $\varepsilon$ may require different values of $N$ — and smaller $\varepsilon$ generally requires larger $N$.

Sequence:a_n = 1/na_n = (1+1/n)^na_n = 0.9^na_n = (-1)^n / na_n = n²/(n²+1)ε = 0.10Zoom to ε-band

● Inside band (n ≥ N)● Outside band● Inside band (n < N)N = 11 for ε = 0.100

A complete proof from the definition

Notice the structure: let $\varepsilon > 0$ be given, choose $N$ in terms of $\varepsilon$, verify the bound. Every $\varepsilon$-$N$ proof follows this template. The creative part is choosing $N$ — often this requires algebraic manipulation of the target inequality $|a_n - L| < \varepsilon$ to isolate $n$.

Two fundamental properties of convergent sequences

This proof uses a technique you’ll see throughout analysis: to show a non-negative quantity equals zero, show it’s less than every positive number. The triangle inequality $|x + y| \leq |x| + |y|$ is the workhorse — it lets us split a distance into two pieces we can control separately.

The converse is false — the sequence $(-1)^n$ is bounded (by $M = 1$) but not convergent. Boundedness is necessary for convergence, but not sufficient. We need additional structure (like monotonicity) to guarantee convergence.

Convergence Theorems

With the definition established, we now prove three theorems that are the main tools for establishing that a sequence converges. In practice, very few limits are proved directly from the $\varepsilon$-$N$ definition — instead, we use these theorems.

This proof reveals something deep: the Monotone Convergence Theorem is really a theorem about the completeness of $\mathbb{R}$. In the rational numbers $\mathbb{Q}$, the sequence $1, 1.4, 1.41, 1.414, \ldots$ (decimal approximations to $\sqrt{2}$) is increasing and bounded above, but it does not converge in $\mathbb{Q}$ — the limit $\sqrt{2}$ is irrational. The real numbers were constructed to fill these gaps.

Why this matters for ML: Most gradient descent convergence proofs follow this pattern. If you can show that the loss sequence $f(\theta_1), f(\theta_2), \ldots$ is decreasing (which requires a sufficiently small step size) and bounded below (e.g., $f \geq 0$), the Monotone Convergence Theorem guarantees that the loss converges to some value. Whether that value is the global minimum is a separate question.

The Squeeze Theorem is how we prove convergence rates: if we can trap the error $|a_n - L|$ between zero and a sequence that decays at a known rate, the Squeeze Theorem tells us $|a_n - L|$ decays at least that fast.

Monotone ConvergenceSqueeze TheoremAlgebra of Limits

Subsequences & Bolzano-Weierstrass

Sometimes a sequence doesn’t converge, but parts of it do. This observation leads to one of the most important theorems in analysis.

For example, the even-indexed terms $a_2, a_4, a_6, \ldots$ form a subsequence. So do the terms at prime indices $a_2, a_3, a_5, a_7, a_{11}, \ldots$. The key constraint is that the indices $n_k$ must be strictly increasing — we must move forward through the original sequence.

The contrapositive gives a powerful divergence test: if two subsequences converge to different limits, the original sequence diverges. For $(-1)^n$, the even terms $(a_{2k}) = (1, 1, 1, \ldots) \to 1$ and the odd terms $(a_{2k+1}) = (-1, -1, -1, \ldots) \to -1$. Since the subsequential limits disagree, $(-1)^n$ diverges.

Cauchy Sequences & Completeness

The $\varepsilon$-$N$ definition requires us to know the limit $L$ in advance. But in practice, we often want to prove convergence without knowing the limit — for instance, we want to show that gradient descent converges to some critical point without identifying which one. The Cauchy criterion solves this problem.

Compare with the convergence definition: convergence says terms get close to $L$; Cauchy says terms get close to each other. The Cauchy condition is intrinsic — it refers only to the sequence itself.

The deep question is the converse: is every Cauchy sequence convergent? In $\mathbb{Q}$, the answer is no — the decimal approximations to $\sqrt{2}$ form a Cauchy sequence in $\mathbb{Q}$ that does not converge in $\mathbb{Q}$. But in $\mathbb{R}$, the answer is yes, and this is the whole point of the real number system.

Threshold N: 20

max |a_m − a_n| for m,n ≥ 20: 0.0320

max |a_m − a_n| for m,n ≥ 20: 1.0655

Rates of Convergence

Knowing that a sequence converges is important, but often not enough. In practice, we need to know how fast it converges — the difference between $O(1/n)$ and $O(r^n)$ convergence is the difference between an algorithm that takes hours and one that takes seconds.

These rates form a strict hierarchy: quadratic $\Rightarrow$ superlinear $\Rightarrow$ linear $\Rightarrow$ sublinear (in terms of speed). The practical implications are dramatic:

Connections to ML

Everything we’ve developed — the $\varepsilon$-$N$ definition, the convergence theorems, the Cauchy criterion, convergence rates — is the mathematical engine behind optimization and learning theory in machine learning.

Gradient descent as a convergent sequence

Consider minimizing $f(x) = x^2$. Gradient descent with step size $\eta$ produces the update $x_{t+1} = x_t - \eta \cdot 2x_t = (1 - 2\eta) x_t$. This is a geometric sequence:

$x_t = (1 - 2\eta)^t \cdot x_0.$

For $0 < \eta < 1$, we have $|1 - 2\eta| < 1$, so $x_t \to 0$ by the geometric series argument — the errors decay linearly with rate $r = |1 - 2\eta|$. For $\eta = 1$ or $\eta > 1$, the sequence diverges. Try it below:

η = 0.30x₀ = 3.0▶ Play

Step: 50xₜ = 0.0000|xₜ| = 0.0000Converges (r = 0.40)

This is why the learning rate matters: too small and convergence is glacially slow ($r$ close to $1$), too large and the sequence diverges, and there’s an optimal $\eta$ that minimizes $r$. For $f(x) = x^2$, the optimal is $\eta = 1/2$, giving $r = 0$ — convergence in one step.

Learning rate schedules & Robbins-Monro

For stochastic gradient descent, a fixed learning rate doesn’t work — the noise prevents convergence to a point. Instead, we need a decaying schedule $\eta_1, \eta_2, \eta_3, \ldots$ satisfying the Robbins-Monro conditions:

$\sum_{t=1}^{\infty} \eta_t = \infty \quad \text{and} \quad \sum_{t=1}^{\infty} \eta_t^2 < \infty.$

The first condition ($\sum \eta_t = \infty$) ensures the steps are large enough to reach the optimum from any starting point. The second ($\sum \eta_t^2 < \infty$) ensures the accumulated noise variance is finite, so the iterates settle down. Common schedules satisfying both: $\eta_t = c/t$ and $\eta_t = c/\sqrt{t}$.

These are series convergence conditions — statements about infinite sums. We’ll formalize series in Series Convergence & Tests (coming soon), but the key point is that learning rate theory rests on the sequence and series machinery we’ve built here.

MCMC mixing

Markov chain Monte Carlo (MCMC) sampling produces a sequence of states $X_1, X_2, X_3, \ldots$ that converges in distribution to a target distribution $\pi$. The mixing time — how many steps until the chain is “$\varepsilon$-close” to $\pi$ — is a convergence rate question. Fast-mixing chains have geometric (linear) convergence, while slowly-mixing chains may need $O(n^2)$ or worse steps. The formal framework of sequence convergence underlies the entire theory. See formalML for the full treatment.

Empirical risk convergence

Given $n$ training examples, the empirical risk $\hat{R}_n(h) = \frac{1}{n} \sum_{i=1}^{n} \ell(h(x_i), y_i)$ defines a sequence indexed by $n$. The law of large numbers tells us $\hat{R}_n(h) \to R(h)$ (the true risk) as $n \to \infty$ — this is a sequence convergence result. The uniform version — $\sup_{h \in \mathcal{H}} |\hat{R}_n(h) - R(h)| \to 0$ — is the Glivenko-Cantelli theorem, which is the foundation of PAC learning. See formalML for how this generalizes to function classes and VC dimension.

Computational Notes

Here are the key computational patterns for working with sequences numerically.

Generating and testing sequences with NumPy:

import numpy as np

# Generate sequence terms
n = np.arange(1, 201)
a_n = 1 / n                          # decaying
b_n = (1 + 1/n)**n                   # approaching e
c_n = np.cumprod(np.full(200, 0.9))  # geometric decay

Numerical Cauchy criterion check:

def check_cauchy(seq, N, window=50):
    """Check max |a_m - a_n| for m, n >= N."""
    tail = seq[N:N+window]
    max_gap = np.max(np.abs(tail[:, None] - tail[None, :]))
    return max_gap

# Cauchy: partial sums of 1/k^2
partial_sums = np.cumsum(1 / n**2)
print(f"Cauchy gap at N=100: {check_cauchy(partial_sums, 100):.6f}")

# Not Cauchy: harmonic series
harmonic = np.cumsum(1 / n)
print(f"Harmonic gap at N=100: {check_cauchy(harmonic, 100):.4f}")

Estimating convergence rate from iterates:

def estimate_rate(errors):
    """Estimate convergence rate from error sequence."""
    ratios = errors[1:] / errors[:-1]
    avg_ratio = np.mean(ratios[-10:])  # use tail for stability
    if avg_ratio < 0.01:
        return 'superlinear'
    elif avg_ratio < 0.95:
        return f'linear (r ≈ {avg_ratio:.3f})'
    else:
        return 'sublinear'

# GD on f(x) = x^2 with eta = 0.3
x = 4.0
errors = []
for _ in range(50):
    x = x - 0.3 * 2 * x  # GD update
    errors.append(abs(x))

print(estimate_rate(np.array(errors)))
# → "linear (r ≈ 0.400)"

Extracting iteration sequences from SciPy:

from scipy.optimize import minimize

iterates = []
def callback(xk):
    iterates.append(xk.copy())

result = minimize(lambda x: x[0]**2 + x[1]**2, x0=[3.0, 4.0],
                  method='CG', callback=callback)
# iterates now contains the full optimization path

Connections & Further Reading

Where this leads within formalCalculus

• Epsilon-Delta & Continuity (coming soon) extends the $\varepsilon$-$N$ framework to function limits and continuity. The $\varepsilon$-$\delta$ definition is the function-level analogue of what we did here for sequences.
• The Riemann Integral & FTC (coming soon) defines the integral as a limit of Riemann sums — each sum is a term in a sequence, and convergence of that sequence is the integral.
• Series Convergence & Tests (coming soon) treats partial sums of infinite series as sequences. The Robbins-Monro conditions from §8 are formalized as series convergence criteria.
• Completeness & Compactness (coming soon) generalizes the Bolzano-Weierstrass theorem from $\mathbb{R}$ to $\mathbb{R}^n$ and introduces the Heine-Borel theorem — the compactness machinery that guarantees the existence of minimizers on closed bounded sets.

Where this leads in machine learning

The convergence theory developed here is the direct foundation for:

• formalML Gradient Descent — convergence rates, step size conditions, and strong convexity.
• formalML PAC Learning — uniform convergence of empirical processes.
• formalML Random Walks & MCMC — mixing time as a convergence rate.
• formalML Concentration Inequalities — quantitative convergence bounds.
• formalML Measure-Theoretic Probability — modes of convergence (a.s., in probability, in distribution).

References

• Abbott (2015). Understanding Analysis. Chapters 2–3. The gold standard for rigorous-but-accessible treatment of sequences and limits.
• Rudin (1976). Principles of Mathematical Analysis. Chapter 3. The definitive reference, terse but complete.
• Tao (2016). Analysis I. Chapters 5–6. Builds the real numbers from Cauchy sequences — ideal for seeing the foundations from scratch.
• Boyd & Vandenberghe (2004). Convex Optimization. Sections 9.2–9.3. Gradient descent convergence rates as direct applications.
• Robbins & Monro (1951). “A Stochastic Approximation Method.” The original learning rate conditions for SGD convergence.