Gradient descent: how a model learns

Let d ∈ ℕ, d ≥ 1, and let J : ℝ^d → ℝ be a differentiable loss function with the gradient ∇J : ℝ^d → ℝ^d, ∇J(θ) = (∂J/∂θ₁(θ), …, ∂J/∂θ_d(θ)) (see the part on derivatives and the gradient).

Gradient descent is the algorithm:

• input: initial parameters θ₀ ∈ ℝ^d, a learning rate η ∈ ℝ, η > 0, a tolerance ε > 0 and a maximum number of steps T ∈ ℕ;
• output: the parameters θ_t ∈ ℝ^d at the moment it stops.

1. Set t = 0.
2. If ‖∇J(θ_t)‖ < ε or t = T, stop and return θ_t.
3. Set θ_t+1 = θ_t − η ∇J(θ_t), increase t by 1 and continue with step 2.

So the algorithm repeatedly moves the parameters by η times the gradient against its direction, until the gradient is almost zero or the steps run out.

Let G = (U, H) be a directed acyclic graph with a finite set of nodes U and a set of edges H ⊆ U × U; we write an edge (u, v) ∈ H as u → v. For v ∈ U let par(v) = {u ∈ U : u → v} denote the set of its parents. G is a computation graph if and only if

1. each node v carries a real value, which we denote by the same letter v;
2. the nodes with par(v) = ∅ are inputs (data and parameters) and their values are given;
3. each node v with par(v) ≠ ∅ has a differentiable function f_v, and its value is v = f_v((u)_{u ∈ par(v)});
4. one marked node L ∈ U is the loss.

A topological order is a numbering U = {v₁, …, v_N} such that v_i → v_j ⇒ i < j (it always exists in an acyclic graph).

The forward pass computes the values v₁, …, v_N in this order according to item 3 — each node only after all its parents.

The backward pass computes for each node u ∈ U its adjoint ū = ∂L/∂u in the reverse order v_N, …, v₁: it sets L̄ = 1 and for u ≠ L uses the multivariable chain rule

ū = ∑_{v : u → v} v̄ · ∂f_v/∂u

(an empty sum is 0). So for each node the backward pass adds up the contributions from all the nodes that u feeds into; each edge is used exactly once in the process.

All quantities are real numbers: p₁, p₂, b, w, x, z ∈ ℝ, the target t ∈ {0, 1} and the output ŷ ∈ (0, 1).

Sum z = p₁ + p₂ + b: ∂z/∂p₁ = ∂z/∂p₂ = ∂z/∂b = 1 — a sum passes the gradient to all its inputs unchanged.

Product p = wx: ∂p/∂w = x and ∂p/∂x = w — the gradient is multiplied by the other factor.

Logistic function σ : ℝ → (0, 1), σ(z) = 1/1 + e^−z: σ′(z) = e^−z/(1 + e^−z)² = σ(z)(1 − σ(z)) = ŷ(1 − ŷ), where ŷ = σ(z).

Cross-entropy L = −t ln ŷ − (1 − t) ln(1 − ŷ): ∂L/∂ŷ = −t/ŷ + 1 − t/1 − ŷ.

Let t ∈ {0, 1}, z ∈ ℝ, let ŷ = σ(z) be the logistic function and L = −t ln ŷ − (1 − t) ln(1 − ŷ) the cross-entropy. Then

∂L/∂z = ŷ − t.

Proof. The chain rule through ŷ: ∂L/∂z = ∂L/∂ŷ · ∂ŷ/∂z = (−t/ŷ + 1 − t/1 − ŷ) · ŷ(1 − ŷ) = −t(1 − ŷ) + (1 − t)ŷ = ŷ − t. ∎

In the figure: ∂L/∂z = 0.500 − 1 = −0.500. Dividing by ŷ and multiplying by ŷ(1 − ŷ) cancel each other out — that is why cross-entropy is paired with the logistic function (and, as you will see, with softmax too).

Let G = (U, H) be a computation graph with E = |H| edges in which every node affects the loss (from every node there is a path to L), and let each value f_v and each local derivative ∂f_v/∂u be computable in constant time. Then the backward pass computes all the adjoints ū, u ∈ U — among them all the derivatives ∂L/∂θ_i with respect to the parameters — in time O(E), that is, of the same order as the forward pass and independently of the number of parameters.

Proof. In the formula for ū each edge u → v appears in a sum exactly once, so all the sums together have E terms. Every node except L has at least one outgoing edge, so |U| ≤ E + 1 and the work on the individual nodes is also O(E). ∎

The numerical derivative L(θ + he_i) − L(θ − he_i)/2h (e_i is the i-th unit vector, h > 0 a small number) would need two forward passes per parameter — for a network with a billion parameters, two billion passes instead of one backward pass.

For m ∈ ℕ, m ≥ 1, softmax is the function softmax : ℝ^m → (0, 1)^m given component-wise by (see the part on softmax)

softmax(z)_i = e^z_i/∑_k=1^m e^z_k,   i = 1, …, m.

Let n ∈ ℕ, n ≥ 1, be the number of layers, d₀, d₁, …, d_n ≥ 1 the widths of the layers, x ∈ ℝ^d₀ the input, and for ℓ = 1, …, n let W^(ℓ) ∈ ℝ^{d_ℓ×d_ℓ−1} be the weights and b^(ℓ) ∈ ℝ^d_ℓ the biases of layer ℓ. A network with softmax in every layer computes a⁽⁰⁾ = x and for ℓ = 1, …, n

z^(ℓ) = W^(ℓ)a^(ℓ−1) + b^(ℓ) ∈ ℝ^d_ℓ,   a^(ℓ) = softmax(z^(ℓ)) ∈ (0, 1)^d_ℓ,

component-wise z_i^(ℓ) = ∑_j=1^d_ℓ−1 W_ij^(ℓ)a_j^(ℓ−1) + b_i^(ℓ) for i = 1, …, d_ℓ (the weighted-sum basis function).

The target is a vector t ∈ {0, 1}^d_n with ∑_k t_k = 1 (a single one at the position of the correct class) and the loss is the cross-entropy

L = −∑_k=1^d_n t_k ln a_k⁽ⁿ⁾.

The error of layer ℓ ∈ {1, …, n} is the vector

δ^(ℓ) = ∂L/∂z^(ℓ) ∈ ℝ^d_ℓ,   i.e. δ_i^(ℓ) = ∂L/∂z_i^(ℓ).

So the error of a layer says how the loss depends on the input of the activation; the gradients of the weights and biases can then be read off from it.

Let m ∈ ℕ, m ≥ 1, z ∈ ℝ^m and a = softmax(z). For i, j ∈ {1, …, m} let δ_ij denote the Kronecker delta (δ_ij = 1 for i = j, otherwise 0). Then for all i, j ∈ {1, …, m}

∂a_i/∂z_j = a_i(δ_ij − a_j),

in matrix form

J = ∂a/∂z = diag(a) − aa^T ∈ ℝ^m×m.

Proof. Let S = ∑_k=1^m e^z_k, so that ∂S/∂z_j = e^z_j. By the quotient rule

for i = j: ∂a_i/∂z_i = e^z_iS − e^z_ie^z_i/S² = a_i − a_i²,

for i ≠ j: ∂a_i/∂z_j = −e^z_ie^z_j/S² = −a_ia_j. ∎

We will need two properties: J is symmetric and each of its rows (and columns) has sum zero, because ∑_j a_i(δ_ij − a_j) = a_i − a_i∑_ja_j = 0.

Let the network, the target t and the loss L be as in the definition above. Then

δ⁽ⁿ⁾ = a⁽ⁿ⁾ − t.

Proof. We write a = a⁽ⁿ⁾, z = z⁽ⁿ⁾. The loss depends on a as ∂L/∂a_i = −t_i/a_i. Each z_j affects all the a_i, so we sum over i and use Lemma 1:

δ_j⁽ⁿ⁾ = ∑_i ∂L/∂a_i · ∂a_i/∂z_j = ∑_i (−t_i/a_i) · a_i(δ_ij − a_j) = −t_j + a_j ∑_i t_i = a_j − t_j,

because ∑_i t_i = 1. ∎

It has the same form as ŷ − t for a single neuron: the logarithm in the loss cancels the exponential in softmax, and of the whole Jacobian matrix only the difference “what the network said” minus “what it should have said” remains.

Let n ≥ 2, let the network, the target and the loss be as in the definition above, and let J⁽ⁿ⁻¹⁾ = diag(a⁽ⁿ⁻¹⁾) − a⁽ⁿ⁻¹⁾(a⁽ⁿ⁻¹⁾)^T be the Jacobian matrix of the softmax of layer n − 1 (Lemma 1). Let g⁽ⁿ⁻¹⁾ = ∂L/∂a⁽ⁿ⁻¹⁾ ∈ ℝ^d_n−1. Then

1. g⁽ⁿ⁻¹⁾ = (W⁽ⁿ⁾)^T δ⁽ⁿ⁾,   component-wise g_j = ∑_i W_ij⁽ⁿ⁾ δ_i⁽ⁿ⁾;
2. δ⁽ⁿ⁻¹⁾ = J⁽ⁿ⁻¹⁾ g⁽ⁿ⁻¹⁾,   component-wise δ_j⁽ⁿ⁻¹⁾ = a_j (g_j − a·g),

where a = a⁽ⁿ⁻¹⁾, g = g⁽ⁿ⁻¹⁾ and a·g = ∑_i a_ig_i is the average of g weighted by the activations of the layer (the weights a_i are positive and sum to 1).

Proof. First the gradient with respect to the outputs of layer n − 1. Since z_i⁽ⁿ⁾ = ∑_j W_ij⁽ⁿ⁾a_j⁽ⁿ⁻¹⁾ + b_i⁽ⁿ⁾, we have ∂z_i⁽ⁿ⁾/∂a_j⁽ⁿ⁻¹⁾ = W_ij⁽ⁿ⁾, and by the chain rule g_j = ∑_i ∂L/∂z_i⁽ⁿ⁾ · W_ij⁽ⁿ⁾ = ∑_i W_ij⁽ⁿ⁾ δ_i⁽ⁿ⁾, which is item 1.

So the error goes back along the same weights the signal took forward, only in the opposite direction — hence the transpose. Then it passes back through the softmax of layer n − 1; by Lemma 1 and thanks to the symmetry of J:

δ_j⁽ⁿ⁻¹⁾ = ∑_i g_i ∂a_i/∂z_j = ∑_i a_i(δ_ij − a_j)g_i = a_jg_j − a_j ∑_i a_ig_i = a_j (g_j − a·g),

which is item 2. ∎

Interpretation: a neuron gets an error proportional to how far “its” gradient g_j is above the weighted average of the whole layer, and multiplied by its activation as well. Softmax does not distinguish the absolute level, only the ratios — that is why the average is subtracted.

Let the network, the target and the loss be as in the definition above, let J^(ℓ) be the Jacobian matrix of the softmax of layer ℓ (Lemma 1), ⊙ denote component-wise multiplication and 1 the vector of ones. Then

1. (recursion) for ℓ = n − 1, n − 2, …, 1 g^(ℓ) = (W^(ℓ+1))^T δ^(ℓ+1),   δ^(ℓ) = J^(ℓ)g^(ℓ) = a^(ℓ) ⊙ (g^(ℓ) − (a^(ℓ)·g^(ℓ)) 1), where g^(ℓ) = ∂L/∂a^(ℓ);
2. (gradients of the parameters) for ℓ = 1, …, n, i = 1, …, d_ℓ and j = 1, …, d_ℓ−1 ∂L/∂W_ij^(ℓ) = δ_i^(ℓ) a_j^(ℓ−1),   i.e. ∂L/∂W^(ℓ) = δ^(ℓ)(a^(ℓ−1))^T,   ∂L/∂b^(ℓ) = δ^(ℓ).

Proof. (1) The argument of Theorem 3 nowhere used that layer n is the last one — only that z^(ℓ+1) depends on a^(ℓ) linearly with the matrix W^(ℓ+1) and that a^(ℓ) = softmax(z^(ℓ)). Written out over all the layers:

δ^(ℓ) = J^(ℓ)(W^(ℓ+1))^T J^(ℓ+1)(W^(ℓ+2))^T ⋯ J⁽ⁿ⁻¹⁾(W⁽ⁿ⁾)^T (a⁽ⁿ⁾ − t).

(2) The weight W_ij^(ℓ) affects only z_i^(ℓ), with the derivative ∂z_i^(ℓ)/∂W_ij^(ℓ) = a_j^(ℓ−1); the bias b_i^(ℓ) with the derivative 1. The chain rule gives ∂L/∂W_ij^(ℓ) = δ_i^(ℓ) · a_j^(ℓ−1) and ∂L/∂b_i^(ℓ) = δ_i^(ℓ). ∎

So the gradient of a weight is “the error of the neuron the weight leads into, times the activity of the neuron it leads from”. A weight from an inactive neuron does not learn.

Let the network, the target and the loss be as in the definition above. Then for every layer ℓ ∈ {1, …, n}

∑_j=1^d_ℓ δ_j^(ℓ) = 0,   and therefore also   ∑_j=1^d_ℓ ∂L/∂b_j^(ℓ) = 0.

Proof. For ℓ = n: ∑(a_j − t_j) = 1 − 1 = 0. For the hidden layers: 1^Tδ^(ℓ) = 1^TJ^(ℓ)g^(ℓ) = 0, because the columns of J sum to zero (Lemma 1). ∎

The reason goes deeper: softmax does not change when you add the same number to all the z_i in a layer. In the direction (1, 1, …, 1) the loss is therefore flat and the gradient cannot point into it.

Let m ≥ 1, a ∈ (0, 1)^m with ∑_i a_i = 1 (an output of softmax) and J = diag(a) − aa^T. Then all eigenvalues of J lie in the interval [0, 1/2], and therefore for every g ∈ ℝ^m

‖Jg‖ ≤ 1/2 ‖g‖.

Proof. J is symmetric, so it has real eigenvalues. Row i has a_i(1 − a_i) on the diagonal and off it the numbers −a_ia_j, whose absolute values add up to a_i(1 − a_i). By the Gershgorin circle theorem every eigenvalue lies in one of the intervals [0, 2a_i(1 − a_i)], and 2a(1 − a) ≤ 1/2 for every a ∈ ℝ. For a symmetric matrix, ‖Jg‖ ≤ max |λ| · ‖g‖, where the maximum is over the eigenvalues λ. ∎

So on the way back each softmax layer at least halves the error (unless the weights amplify it). That is one of the reasons softmax is not put into hidden layers: in a deep network the gradient would hardly reach the first layers. You will see it in the example too.

Let J : ℝ → ℝ, J(x) = x², a start x₀ ∈ ℝ, x₀ ≠ 0, a learning rate η > 0 and x_t+1 = x_t − ηJ′(x_t) for t = 0, 1, 2, … Then

1. x_t = (1 − 2η)^t x₀ for all t ∈ ℕ₀;
2. x_t → 0 (descent converges to the minimum) if and only if |1 − 2η| < 1, i.e. if and only if η < 1;
3. for η = 0.5, x₁ = 0 — descent ends in the minimum in a single step.

Proof. One step is x_t+1 = x_t − η · 2x_t = (1 − 2η)x_t; by induction we get the power. The sequence q^t tends to zero exactly for |q| < 1. ∎

(1) Let a > 0, J : ℝ → ℝ, J(x) = ax²/2 (the second derivative is a), η > 0 and x₀ ≠ 0. Then a descent step is x ← (1 − ηa)x, and descent converges to the minimum 0 if and only if

0 < η < 2/a.

The parabola x² has a = 2, hence the bound 1.

(2) In general: let J : ℝ^d → ℝ be differentiable with a gradient that has a Lipschitz constant L > 0, i.e. ‖∇J(u) − ∇J(v)‖ ≤ L‖u − v‖ for all u, v ∈ ℝ^d (the curvature nowhere exceeds L), and let 0 < η ≤ 1/L. Then J(θ_t+1) ≤ J(θ_t) for every t — the loss does not increase in any step (a standard result, see e.g. Nesterov: Introductory Lectures on Convex Optimization, 2004, sec. 1.2.3). So the learning rate must be governed by the steepest curvature of the landscape.

Let d ≥ 1 and let A ∈ ℝ^d×d be a symmetric positive definite matrix; its eigenvalues are real and positive; let λ_min > 0 be the smallest and λ_max the largest of them. The condition number of the matrix A is

κ = λ_max/λ_min ≥ 1,

the ratio of the largest and the smallest eigenvalue. For a quadratic loss J : ℝ^d → ℝ, J(θ) = 1/2 θ^TAθ, the eigenvalues of A are the curvatures in the principal directions, and the condition number of the loss is the condition number of A. Our valley has A = diag(1, 20), so κ = 20.

For this loss the following holds (a standard result): gradient descent with learning rate η converges from every start if and only if 0 < η < 2/λ_max. Even with the best fixed choice η = 2/λ_min + λ_max we only have ‖θ_t+1‖ ≤ κ − 1/κ + 1 ‖θ_t‖ (the minimum is at θ = 0) — for us 19/21 ≈ 0.905. The larger κ, the closer this coefficient is to 1 and the slower the descent.

Let J : ℝ^d → ℝ be a differentiable loss function, θ₀ ∈ ℝ^d the initial parameters, η > 0 the learning rate and β ∈ [0, 1) the momentum coefficient. Descent with momentum sets v₀ = 0 ∈ ℝ^d and for t = 0, 1, 2, … computes

v_t+1 = β v_t − η ∇J(θ_t),   θ_t+1 = θ_t + v_t+1;

it stops in the same way as gradient descent (a small gradient or the number of steps used up). The vector v_t ∈ ℝ^d is the “velocity”, and β says how much of it carries over to the next step (typically 0.9; in our valley 0.6 works best). For β = 0 it is plain gradient descent.

Let η > 0, β ∈ [0, 1), g ∈ ℝ^d, let the gradient stay the same throughout the descent, ∇J(θ_t) = g for all t (an even slope), and v₀ = 0. Then for every t ≥ 1

v_t = −ηg(1 + β + … + β^t−1) = −ηg 1 − β^t/1 − β   and   v_t → −η/1 − β g   for t → ∞.

Proof. By induction from v_t+1 = βv_t − ηg; the sum of a geometric series, and β^t → 0 because 0 ≤ β < 1. ∎

On an even slope the step therefore settles at η/1 − β times the gradient: for β = 0.6 that is a 2.5 times longer step, for the usual β = 0.9 ten times. When the sign of the gradient alternates, the sum of the series, on the contrary, almost cancels out.

In the x direction the step lengthened from 0.4 to 0.6 (the gradient keeps the same sign); in the y direction the velocity −2.4 and the new pull +2.4 almost cancelled out, and the ball is near the bottom of the valley (y = −0.24). After two steps plain descent is only at (−3.31, 0.77).

Let J : ℝ^d → ℝ be a differentiable loss function. Adam is the algorithm:

• input: initial parameters θ₀ ∈ ℝ^d, a learning rate η > 0, coefficients β₁, β₂ ∈ [0, 1), a small number ε > 0 and a number of steps T ∈ ℕ;
• output: the parameters θ_T ∈ ℝ^d.

Set m₀ = s₀ = 0 ∈ ℝ^d and for t = 1, 2, …, T do (all operations on vectors — square, square root, division — are element-wise):

1. g_t = ∇J(θ_t−1);
2. m_t = β₁m_t−1 + (1 − β₁)g_t (average of the gradients);
3. s_t = β₂s_t−1 + (1 − β₂)g_t² (average of the squares of the gradients);
4. m̂_t = m_t/1 − β₁^t,   ŝ_t = s_t/1 − β₂^t (bias correction, see the next definition);
5. θ_t = θ_t−1 − η m̂_t/√ŝ_t + ε.

Usual values: β₁ = 0.9, β₂ = 0.999, ε = 10⁻⁸. So Adam takes a step in the direction of the average gradient, divided in each component by the typical size of the gradient in that component.

Let g₁, g₂, … be a sequence of real numbers (or vectors in ℝ^d) and β ∈ [0, 1). The exponential moving average of this sequence is the sequence (m_t)_{t ≥ 0} given by the recursion

m₀ = 0,   m_t = βm_t−1 + (1 − β)g_t   for t ≥ 1,

written out m_t = (1 − β) ∑_k=1^t β^t−kg_k. For t ≥ 1 and β > 0 its bias correction is

m̂_t = m_t/1 − β^t.

The weights (1 − β)β^t−k, k = 1, …, t, add up to only 1 − β^t, not 1 — the missing part falls on the initial zero. That is why m_t is biased towards zero at the beginning, and the correction turns it into a true weighted average (after the correction the weights sum to 1; with a constant g_k = g, exactly m̂_t = g).

The gradient in the y direction is six times larger than in the x direction, and yet both parameters moved by the same 0.5. Plain descent would have moved six times further in the y direction than in the x direction.

Let n ≥ 1 be the number of examples in the data, let L₁, …, L_n : ℝ^d → ℝ be the differentiable losses of the individual examples, and let the total loss be their average

J(θ) = 1/n ∑_i=1ⁿ L_i(θ).

Stochastic gradient descent is gradient descent (with the inputs θ₀, η and a number of steps as above) in which at each step t, instead of ∇J(θ_t), the estimate

g_t = 1/|B_t| ∑_{i ∈ Bt} ∇L_i(θ_t),   θ_t+1 = θ_t − ηg_t

is used, where the mini-batch B_t ⊆ {1, …, n} is a non-empty set of indices chosen anew at random at each step (typically of a fixed size |B_t| ≪ n). An epoch is a stretch of steps during which each of the n examples is used exactly once (when the data are shuffled and gone through in batches of size b, that is n/b steps, if n is divisible by b).

Let J = 1/n ∑_i=1ⁿ L_i be as in the definition of SGD, θ ∈ ℝ^d fixed and b ≥ 1. Let I₁, …, I_b be independent random indices, each uniformly distributed on {1, …, n} (sampling with replacement), and

g = 1/b ∑_k=1^b ∇L_Ik(θ).

Then

1. E[g] = ∇J(θ) — the estimate is unbiased;
2. for each component j = 1, …, d, var(g_j) = 1/b var(∂L_I1/∂θ_j(θ)), so the standard deviation (typical error) of the estimate decreases as 1/√b.

Proof. (1) For one random index I, E[∇L_I(θ)] = ∑_i=1ⁿ 1/n ∇L_i(θ) = ∇J(θ); the average of b such estimates has the same expected value. (2) The variance of the average of b independent identically distributed quantities is the variance of one divided by b. ∎

In practice (and in our program) the data are shuffled instead of sampled independently and taken in batches one after another — each example is used exactly once per epoch. That hardly changes the shape of the conclusion.

Let n ≥ 1 and let (x_i, y_i) ∈ ℝ², i = 1, …, n, be the data. For the parameters (a, b) ∈ ℝ² of the line ŷ = ax + b, the mean squared error is the function J : ℝ² → ℝ,

J(a, b) = 1/n ∑_i=1ⁿ (ax_i + b − y_i)².

Let e_i = ax_i + b − y_i denote the error on the i-th example. Then (derivative of a composite function)

∂J/∂a = 2/n ∑_i=1ⁿ e_ix_i,   ∂J/∂b = 2/n ∑_i=1ⁿ e_i.

SGD computes the same sums, only over the batch B and with 2/|B| instead of 2/n.

Let J : ℝ^d → ℝ and θ* ∈ ℝ^d.

1. θ* is a global minimum of J if and only if ∀θ ∈ ℝ^d : J(θ*) ≤ J(θ).
2. θ* is a local minimum of J if and only if ∃r > 0 ∀θ ∈ ℝ^d : ‖θ − θ*‖ < r ⇒ J(θ*) ≤ J(θ). A local maximum is defined in the same way with ≥ instead of ≤.
3. If J is differentiable, θ* is a stationary point if and only if ∇J(θ*) = 0.
4. θ* is a saddle point if and only if it is a stationary point and neither a local minimum nor a local maximum.

Gradient descent stops at a stationary point, whatever it is. If J is twice continuously differentiable, the type of a stationary point is distinguished by the Hessian matrix H ∈ ℝ^d×d, H_ij = ∂²J/∂θ_i ∂θ_j(θ*): if all its eigenvalues are positive, θ* is a local minimum; all negative — a local maximum; both positive and negative — a saddle point. If some eigenvalue is zero and the others have the same sign, the test does not decide.

The maximum near 0.17 is the “ridge” between the two valleys: a ball starting to the right of it rolls into the local minimum, to the left into the global one. A saddle point cannot arise in one variable — it needs at least two directions. The simplest is J(x, y) = x² − y²: at the origin ∇J = (2x, −2y) = 0, and H = diag(2, −2) has eigenvalues of both signs.

Definition. Let J : ℝ^d → ℝ. The function J is convex if and only if

∀u, v ∈ ℝ^d ∀λ ∈ [0, 1] : J(λu + (1 − λ)v) ≤ λJ(u) + (1 − λ)J(v)

— the segment between two points of the graph nowhere lies below the graph.

Theorem. Let J : ℝ^d → ℝ be convex and θ* ∈ ℝ^d a local minimum of J. Then θ* is a global minimum of J.

Proof. Suppose for contradiction that there is u ∈ ℝ^d with J(u) < J(θ*). For the points θ_λ = λu + (1 − λ)θ* we have J(θ_λ) ≤ λJ(u) + (1 − λ)J(θ*) < J(θ*) for every λ ∈ (0, 1]. For small λ, θ_λ lies arbitrarily close to θ* — a contradiction with local minimality. ∎

The parabola and the valley from the previous sections are convex; the loss of a neural network with nonlinear activations in general is not — that is why the start matters for networks.