Regression gradients: linear, logistic and softmax

Worked solutions

Problem 1

1. Let $r = Xw - y \in \mathbb{R}^N$, the residuals, so $L = \tfrac1N r^\top r = \tfrac1N\sum_n r_n^2$ with $r_n = x^{(n)\top}w - y_n$.Naming the residual separates the square from the affine map inside it, so each can be differentiated on its own.
2. $\nabla_r L = \tfrac2N r$, $N \times 1$.Only the $n$-th term of the sum contains $r_n$, and $r_n^2$ differentiates to $2r_n$.
3. $\partial r/\partial w = X$, $N \times d$.$r$ is $X$ times $w$ minus a constant, and the Jacobian of $Ax$ is $A$ (the matrix-calculus page, Problem 2).
4. $\nabla_w L = (\partial r/\partial w)^\top\nabla_r L = X^\top\,\tfrac2N r$.$L$ depends on $w$ only through $r$, so the chain rule for gradients applies.
5. $\nabla_w L = \tfrac2N X^\top(Xw - y)$$(d \times N)(N \times 1) = d \times 1$, the shape of $w$. Entry $j$ is $\tfrac2N\sum_n X_{nj} r_n$: every example's residual, weighted by its feature $j$, averaged over the data.

Problem 2

1. $\tfrac2N X^\top(Xw - y) = 0 \iff X^\top X\,w = X^\top y$.Multiply both sides by $N/2 \neq 0$. Scaling a loss by a positive constant does not move its minimiser, so the $1/N$ changes the size of gradient steps, never where they lead.
2. $\nabla_w^2 L = \tfrac2N X^\top X$, $d \times d$.The gradient $\tfrac2N X^\top X w - \tfrac2N X^\top y$ is affine in $w$, so its Jacobian is the matrix that multiplies $w$.
3. $v^\top X^\top X v = (Xv)^\top(Xv) = \|Xv\|^2 \ge 0$ for every $v \in \mathbb{R}^d$.Associativity groups the product into a vector with itself, and a squared norm cannot be negative.
4. If the columns of $X$ are independent, $Xv = 0$ only for $v = 0$, so $v^\top X^\top X v > 0$ for $v \neq 0$ and $X^\top X$ is invertible.$Xv$ is the combination of the columns of $X$ with coefficients $v$; independence means only the zero combination vanishes. A positive definite matrix has no null space.
5. $X^\top X\,w = X^\top y$; when the columns of $X$ are independent, $w^* = (X^\top X)^{-1}X^\top y$, the unique minimiser, because the Hessian $\tfrac2N X^\top X$ is positive definiteA function whose Hessian is positive definite everywhere is strictly convex, so its one stationary point is the global minimum. With dependent columns (fewer examples than features, or a repeated feature) $X^\top X$ is singular and the minimisers form a whole affine set; Problem 3 removes that.

Problem 3

1. $\nabla_w\big(\lambda\|w\|^2\big) = 2\lambda w$.$\lambda\|w\|^2 = \lambda\sum_j w_j^2$, and only the $j$-th term contains $w_j$.
2. $\nabla_w L_\lambda = \tfrac2N X^\top(Xw - y) + 2\lambda w$.The gradient of a sum is the sum of the gradients; the first term is Problem 1.
3. Setting it to zero and multiplying by $N/2$: $X^\top X\,w - X^\top y + N\lambda\,w = 0$, so $(X^\top X + N\lambda I)\,w = X^\top y$.The data term carries the $1/N$ of the mean and the penalty does not, so clearing the $1/N$ leaves an $N$ on the penalty.
4. $v^\top(X^\top X + N\lambda I)\,v = \|Xv\|^2 + N\lambda\|v\|^2 > 0$ for every $v \neq 0$.The first term is $\ge 0$ (Problem 2, step 3) and the second is $> 0$ because $N\lambda > 0$, whatever $X$ is; so the matrix is positive definite and invertible.
5. $\nabla_w L_\lambda = \tfrac2N X^\top(Xw - y) + 2\lambda w$; $w^* = (X^\top X + N\lambda I)^{-1}X^\top y$Step 4 holds for every $X$, including $N < d$, so the solution always exists and is unique. For the summed loss $\|Xw - y\|^2 + \lambda'\|w\|^2$ the same steps give the familiar $(X^\top X + \lambda' I)^{-1}X^\top y$; the two agree when $\lambda' = N\lambda$.

Problem 4

1. $\sigma(t) = (1 + e^{-t})^{-1}$, so $\sigma'(t) = \dfrac{e^{-t}}{(1 + e^{-t})^2}$.Chain rule: $u^{-1}$ differentiates to $-u^{-2}$, and $1 + e^{-t}$ to $-e^{-t}$; the two minus signs cancel.
2. $1 - \sigma(t) = \dfrac{1 + e^{-t} - 1}{1 + e^{-t}} = \dfrac{e^{-t}}{1 + e^{-t}}$.Put $1$ over the common denominator.
3. $\sigma'(t) = \dfrac{1}{1 + e^{-t}}\cdot\dfrac{e^{-t}}{1 + e^{-t}} = \sigma(t)(1 - \sigma(t))$.Split the square in step 1's denominator; the second factor is step 2.
4. $\dfrac{e^{-t}}{1 + e^{-t}} = \dfrac{1}{e^{t} + 1} = \sigma(-t)$.Multiply the numerator and denominator by $e^{t}$; the result is the definition of $\sigma$ at $-t$.
5. $\sigma'(t) = \sigma(t)(1 - \sigma(t))$; $1 - \sigma(t) = \sigma(-t)$Both factors lie in $(0, 1)$ and sum to $1$, so $\sigma'(t) \le \tfrac14$, with equality at $t = 0$. The second identity says the probability of class $0$ is the sigmoid of the negated logit, so the two classes are treated symmetrically.

Problem 5

1. Let $t = x^\top w$, the logit, so $p = \sigma(t)$.$\ell$ depends on $w$ only through the scalar $t$, so the chain rule has one link per variable.
2. $\partial\ell/\partial p = -\dfrac yp + \dfrac{1 - y}{1 - p} = \dfrac{p - y}{p(1 - p)}$.$\log u$ differentiates to $1/u$, and $\log(1 - p)$ to $-1/(1 - p)$; over the common denominator the numerator is $-y(1 - p) + (1 - y)p = p - y$.
3. $\partial p/\partial t = p(1 - p)$.Problem 4 at $t$.
4. $\partial\ell/\partial t = p - y$.Chain rule, steps 2 and 3. The $p(1 - p)$ cancels, which is allowed because $0 < p < 1$ for every finite $t$.
5. $\nabla_w t = x$.$t = x^\top w$ is linear in $w$, and $\nabla_w(a^\top w) = a$ (the matrix-calculus page, Problem 3).
6. $\nabla_w \ell = (\sigma(x^\top w) - y)\,x$$\nabla_w\ell = (\partial\ell/\partial t)\,\nabla_w t$, because $t$ is a scalar. The shape is $d \times 1$. It is the prediction error times the input, the same form as linear regression's residual times input.

Problem 6

1. $\nabla_w L = \tfrac1N\sum_n (p_n - y_n)\,x^{(n)}$ with $p_n = \sigma(x^{(n)\top}w)$.The gradient of a mean is the mean of the gradients; each term is Problem 5 for example $n$.
2. For any $c \in \mathbb{R}^N$, $\sum_n c_n\,x^{(n)} = X^\top c$.The columns of $X^\top$ are the $x^{(n)}$, and a matrix times a vector combines its columns with the vector's entries as weights.
3. $p = \sigma(Xw)$ has entries $p_n$.Entry $n$ of $Xw$ is row $n$ of $X$ times $w$, that is $x^{(n)\top}w$, and $\sigma$ acts entry by entry.
4. $\nabla_w L = \tfrac1N X^\top(\sigma(Xw) - y)$Step 2 with $c = p - y$. The shape is $(d \times N)(N \times 1) = d \times 1$. It is Problem 1's gradient with the prediction $Xw$ replaced by $\sigma(Xw)$ and without the $2$, which came from the square. Because $\sigma$ is nonlinear, setting it to zero has no closed-form solution, so the weights are found iteratively (Problem 10).

Problem 7

1. $\nabla_w L = \tfrac1N\sum_n (p_n - y_n)\,x^{(n)}$.Problem 6, step 1.
2. $\nabla_w p_n = p_n(1 - p_n)\,x^{(n)}$.$p_n = \sigma(t_n)$ with $t_n = x^{(n)\top}w$: Problem 4 for $\partial p_n/\partial t_n$ and Problem 5, step 5 for $\nabla_w t_n$.
3. $\dfrac{\partial}{\partial w}\big[(p_n - y_n)\,x^{(n)}\big] = x^{(n)}\,(\nabla_w p_n)^\top = p_n(1 - p_n)\,x^{(n)}x^{(n)\top}$, $d \times d$.$x^{(n)}$ and $y_n$ do not depend on $w$; for a scalar $c(w)$ times a constant vector $a$, entry $(i,j)$ of the Jacobian is $a_i\,\partial c/\partial w_j$, which is $a(\nabla_w c)^\top$.
4. $\sum_n D_{nn}\,x^{(n)}x^{(n)\top} = X^\top D X$, with $D_{nn} = p_n(1 - p_n)$.$(X^\top D X)_{ij} = \sum_n X_{ni}\,D_{nn}\,X_{nj}$, which is entry $(i,j)$ of the weighted sum of outer products, because $X_{ni} = x^{(n)}_i$.
5. $v^\top X^\top D X\,v = \sum_n p_n(1 - p_n)\,(x^{(n)\top}v)^2 \ge 0$ for every $v \in \mathbb{R}^d$.Entry $n$ of $Xv$ is $x^{(n)\top}v$, $D$ weights its square by $p_n(1 - p_n)$, and every weight is positive because $0 < p_n < 1$.
6. $\nabla_w^2 L = \tfrac1N X^\top D X$ with $D = \operatorname{diag}(p\odot(1 - p))$, $p = \sigma(Xw)$; it is positive semidefinite, so $L$ is convexA function whose Hessian is positive semidefinite everywhere is convex, so every stationary point is a global minimum and gradient descent cannot be trapped in a worse one. With independent columns the inequality in step 5 is strict for $v \neq 0$ and $L$ is strictly convex. Unlike Problem 2's Hessian, this one changes with $w$ through $D$.

Problem 8

1. For one example with logits $z \in \mathbb{R}^k$, softmax $s$ and one-hot target $y$ at class $c$: $\ell = -z_c + \log\sum_i e^{z_i}$, so $\nabla_z\ell = s - y$.$\log s_c = z_c - \log\sum_i e^{z_i}$; the log-sum-exp differentiates to $e^{z_j}/\sum_i e^{z_i} = s_j$, and $z_c$ to $1$ exactly at $j = c$, which is $y_j$. The next page derives this result three ways.
2. $\nabla_Z L = \tfrac1N(S - Y)$, $N \times k$.Row $n$ of $Z$ feeds only $\ell_n$, through its own row of the softmax, and the mean puts $\tfrac1N$ on each $\ell_n$; row $n$ is step 1 for example $n$.
3. $Z_{ni} = \sum_j X_{nj}W_{ji} + b_i$, so $\dfrac{\partial L}{\partial W_{ji}} = \sum_n \dfrac{\partial L}{\partial Z_{ni}}\,X_{nj}$.$W_{ji}$ sits in column $i$ of $Z$, in every row $n$, with coefficient $X_{nj}$: the loss reaches it through all $N$ examples, so their contributions add.
4. $\sum_n X_{nj}\,(\nabla_Z L)_{ni} = (X^\top\nabla_Z L)_{ji}$.$(X^\top)_{jn} = X_{nj}$, and the sum over $n$ is the definition of the matrix product.
5. $\partial L/\partial b_i = \sum_n (\nabla_Z L)_{ni}$, so $\nabla_b L = (\nabla_Z L)^\top\mathbf{1}$.$\mathbf{1}b^\top$ adds $b_i$ to every row of column $i$ with coefficient $1$, and $(\nabla_Z L)^\top\mathbf{1}$ sums each column of $\nabla_Z L$.
6. $\nabla_W L = \tfrac1N X^\top(S - Y)$ ($d\times k$); $\nabla_b L = \tfrac1N(S - Y)^\top\mathbf{1}$ ($k$)$(d \times N)(N \times k) = d \times k$ and $(k \times N)(N \times 1) = k \times 1$, the shapes of $W$ and $b$. Column $i$ of $\nabla_W L$ is $\tfrac1N X^\top(S_{:,i} - Y_{:,i})$, Problem 6's form once per class, with the softmax column in place of $\sigma(Xw)$.

Problem 9

1. For $z \in \mathbb{R}^2$, $\operatorname{softmax}(z)_1 = \dfrac{e^{z_1}}{e^{z_1} + e^{z_2}} = \dfrac{1}{1 + e^{-(z_1 - z_2)}} = \sigma(z_1 - z_2)$.Divide the numerator and the denominator by $e^{z_1}$.
2. $\operatorname{softmax}(z)_2 = 1 - \sigma(z_1 - z_2)$.The two entries of a softmax sum to $1$.
3. Row $n$ of $XW$ is $\big(x^{(n)\top}w_1,\ x^{(n)\top}w_2\big)$, so $z_1 - z_2 = x^{(n)\top}(w_1 - w_2)$.Column $i$ of $XW$ is $Xw_i$, and $x^{(n)\top}$ distributes over the difference.
4. With $y_n = Y_{n1}$ and $Y_{n2} = 1 - y_n$, $-\sum_i Y_{ni}\log S_{ni} = -\big[y_n\log p_n + (1 - y_n)\log(1 - p_n)\big]$ with $p_n = \sigma(x^{(n)\top}w)$, $w = w_1 - w_2$.A one-hot row with two classes is $(y_n, 1 - y_n)$; steps 1 to 3 give $S_{n1} = p_n$ and $S_{n2} = 1 - p_n$.
5. $S_{n1} = \sigma\big(x^{(n)\top}(w_1 - w_2)\big)$, so two-class softmax regression is logistic regression with $w = w_1 - w_2$Only the difference $w_1 - w_2$ is determined by the data: adding the same vector to both columns leaves every probability, and so the loss, unchanged. Two-class softmax regression therefore has a whole set of minimisers where logistic regression may have one; a ridge penalty on $W$ picks the one with $w_2 = -w_1$. The next page meets the same shift invariance in the logits.

Problem 10

1. $\nabla_w L = \tfrac1N X^\top(p - y)$ and $\nabla_w^2 L = \tfrac1N X^\top D X$, with $p = \sigma(Xw)$.Problems 6 and 7.
2. $(\nabla_w^2 L)^{-1}\nabla_w L = N\,(X^\top D X)^{-1}\,\tfrac1N X^\top(p - y)$.$(cA)^{-1} = c^{-1}A^{-1}$ for a scalar $c \neq 0$. The inverse exists when the columns of $X$ are independent, because then $X^\top D X$ is positive definite (Problem 7).
3. $w_{\text{new}} = w - (X^\top D X)^{-1}X^\top(p - y)$The $N$ and the $\tfrac1N$ cancel, so Newton's step is the same for the mean loss and the summed loss, while a gradient step changes by a factor of $N$ between them. Each step solves a weighted least-squares problem with weights $D$, recomputed from the new $p$: this is why the method is called iteratively reweighted least squares.