Exercises — Lesson 7: Gradients for Machine Learning
Exercise 7.1. [Hand] Compute \(\nabla f\) for: (a) \(f(w) = \langle (1,-2,3), w \rangle\); (b) \(f(w) = \lVert w \rVert^2\); (c) \(f(w) = (w \cdot \phi - y)^2\) for fixed \(\phi \in \mathbb{R}^n\), \(y \in \mathbb{R}\) (answer in terms of the residual).
Solution.
(a). \(\nabla_w \langle a, w \rangle = a\), so
\[ \nabla_w f(w) = (1, -2, 3). \]
(b).
\[ \nabla_w f(w) = \nabla_w \langle w, w \rangle = \nabla_w \sum_{i=1}^{n} w_i^2 = (2w_1, \dots, 2w_n) = 2w . \]
(c). Let \(r = w \cdot \phi - y\), so \(f(w) = r^2(w)\). Then
\[ \frac{\partial r}{\partial w_i} = \phi_i, \qquad \nabla_w r = (\phi_1, \dots, \phi_n) = \phi, \]
\[ \boxed{\; \nabla_w f = 2r\, \nabla_w r = 2r\phi \;} \]
Exercise 7.2. [Hand] Run two iterations of gradient descent on \(f(w) = (2w_1 + w_2 - 3)^2\) from \(w^{(0)} = (0,0)\) with \(\eta = 0.1\), by hand. Does the loss decrease at each step? (Compute it.)
Solution. With \(f(w) = (2w_1 + w_2 - 3)^2\) and \(r = 2w_1 + w_2 - 3\):
\[ \nabla_w f = \big( 2r(2),\; 2r(1) \big) = \begin{pmatrix} 8w_1 + 4w_2 - 12 \\ 4w_1 + 2w_2 - 6 \end{pmatrix} \]
Starting from \(w^{(0)} = (0,0)\) with \(\eta = 0.1\):
\[ \begin{aligned} \nabla f(w^{(0)}) &= (-12, -6) && \Longrightarrow \quad w^{(1)} = (0,0) - (0.1)(-12,-6) = (1.2,\, 0.6) \\[6pt] \nabla f(w^{(1)}) &= (0, 0) && \Longrightarrow \quad w^{(2)} = (1.2,\, 0.6) \end{aligned} \]
\[ f(w^{(0)}) = 9, \qquad f(w^{(1)}) = 0, \qquad f(w^{(2)}) = 0 \]
The loss goes to zero after one iteration. The first step lands directly on the set of minimizers, which is where the gradient vanishes:
\[ \left[\begin{array}{cc|c} 4 & 2 & 6 \\ 8 & 4 & 12 \end{array}\right] \Longrightarrow \left[\begin{array}{cc|c} 1 & 1/2 & 3/2 \\ 8 & 4 & 12 \end{array}\right] \Longrightarrow \left[\begin{array}{cc|c} 1 & 1/2 & 3/2 \\ 0 & 0 & 0 \end{array}\right] \]
\[ w_1 + 0.5 w_2 - 1.5 = 0 \qquad \Longrightarrow \qquad w_2 \text{ free}, \quad w_1 = 1.5 - 0.5 w_2 . \]
Exercise 7.3. [Proof, \(\star\)] Prove Corollary 7.4 a second way, without Proposition 7.3: expand \(f(x+h) = \lVert A(x+h) - b \rVert^2\) into \(f(x) + \langle g, h \rangle + \lVert Ah \rVert^2\) for an explicit vector \(g\), and identify \(\nabla f(x) = g\) from the first-order approximation. (This perturbation technique is how gradients are computed cleanly in general.)
Proof.
\[ \begin{aligned} f(x+h) &= \lVert A(x+h) - b \rVert^2 = \langle A(x+h) - b,\; A(x+h) - b \rangle \\[4pt] &= \langle A(x+h), A(x+h) \rangle - \langle A(x+h), b \rangle - \langle b, A(x+h) \rangle + \langle b, b \rangle \\[4pt] &= \langle A(x+h), A(x+h) \rangle - 2 \langle A(x+h), b \rangle + \lVert b \rVert^2 \\[4pt] &= \langle A(x+h), Ax \rangle + \langle A(x+h), Ah \rangle - 2 \big[ \langle Ax, b \rangle + \langle Ah, b \rangle \big] + \lVert b \rVert^2 \\[4pt] &= \langle Ax, Ax \rangle + \langle Ah, Ax \rangle + \langle Ax, Ah \rangle + \langle Ah, Ah \rangle - 2 \big[ \langle Ax, b \rangle + \langle Ah, b \rangle \big] + \lVert b \rVert^2 \\[4pt] &= \langle Ax, Ax \rangle - 2 \langle Ax, b \rangle + \lVert b \rVert^2 + 2 \langle Ax, Ah \rangle - 2 \langle Ah, b \rangle + \langle Ah, Ah \rangle \\[4pt] &= f(x) + 2 \big[ \langle Ax, Ah \rangle - \langle Ah, b \rangle \big] + \lVert Ah \rVert^2 \\[4pt] &= f(x) + 2 \big[ \langle A^\mathsf{T} A x, h \rangle - \langle A^\mathsf{T} b, h \rangle \big] + \lVert Ah \rVert^2 \\[4pt] &= f(x) + 2 \langle A^\mathsf{T}(Ax - b),\, h \rangle + \lVert Ah \rVert^2 \\[4pt] &= f(x) + \langle g, h \rangle + \lVert Ah \rVert^2, && \text{where $g = 2A^\mathsf{T}(Ax-b)$, and note $\nabla f(x) = 2A^\mathsf{T}(Ax-b)$} \\[4pt] &= f(x) + \langle \nabla f(x), h \rangle + \lVert Ah \rVert^2, && \text{note $\lVert Ah \rVert^2 \le \lVert A \rVert^2 \lVert h \rVert^2 = O(\lVert h \rVert^2)$} \\[4pt] &\approx f(x) + \langle g, h \rangle + O(\lVert h \rVert^2) \end{aligned} \]
\(\square\)
Exercise 7.4. [Proof] Show that for symmetric \(M\), the function \(g(x) = x^\mathsf{T} M x\) satisfies \(g(x+h) - g(x) - \langle 2Mx, h \rangle = h^\mathsf{T} M h\) exactly (no approximation), and explain how this re-proves Proposition 7.3(ii).
Proof. Note \(g(x) = \langle x, Mx \rangle\). Then
\[ \begin{aligned} g(x+h) &= \langle x+h,\; M(x+h) \rangle = \langle x,\; Mx + Mh \rangle + \langle h,\; Mx + Mh \rangle \\[4pt] &= \langle x, Mx \rangle + \langle x, Mh \rangle + \langle h, Mx \rangle + \langle h, Mh \rangle \\[4pt] &= g(x) + \langle M^\mathsf{T} x, h \rangle + \langle h, Mx \rangle + \langle h, Mh \rangle \\[4pt] &= g(x) + 2 \langle Mx, h \rangle + h^\mathsf{T} M h \end{aligned} \]
\[ \Longrightarrow \quad h^\mathsf{T} M h = g(x+h) - g(x) - 2 \langle Mx, h \rangle \qquad \square \]
Note these:
\[ \begin{aligned} \nabla_h \, h^\mathsf{T} M h &= 2Mh \\[4pt] \nabla_h \, {-2} \langle Mx, h \rangle &= -2Mx \\[4pt] \nabla_h \, g(x) &= 0 \end{aligned} \]
Taking gradients on both sides with respect to \(h\) and rearranging:
\[ \nabla g(x+h) - 2Mx = 2Mh . \]
Set \(h = 0\):
\[ \nabla g(x) - 2Mx = 0 \qquad \Longrightarrow \qquad \nabla g(x) = 2Mx . \qquad \square \]