Let \(\displaystyle f(\vec x) = \frac{1}{2} \vec x^T S \vec x - \vec b^T \vec x\), where \(S\) is a symmetric \(n \times n\) matrix and \(\vec b \in \mathbb{R}^n\).
a)
4 pts Find \(\nabla f(\vec x)\), the gradient of \(f(\vec x)\). Show your work, and \(\boxed{\text{circle}}\) your final answer, which should be an expression in terms of \(\vec x\), \(S\), \(\vec b\), and/or constants. Hint: There’s no need to re-prove gradient rules from class.
2 pts True or False: As long as \(S\) is invertible, if \(\nabla f(\vec a) = \vec 0\), then \(\vec a\) is a global minimum of \(f(\vec x)\).
True False
Solution
True False
In general, this is false. Even if \(S\) is invertible, \(\nabla f(\vec a) = \vec 0\) could mean that \(\vec a\) is at a local maxima, local minima, or saddle point.
For example, let \(\vec x = \begin{bmatrix} x \\ y \end{bmatrix}\), \(\vec b = \begin{bmatrix} 0 \\ 0 \end{bmatrix}\), and \(S = \begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix}\), which is an invertible matrix. Then,
$$ f(\vec x) = \frac{1}{2} \begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} 2 & 0 \\\\ 0 & -2 \end{bmatrix} \begin{bmatrix} x \\\\ y \end{bmatrix} - \begin{bmatrix} 0 \\\\ 0 \end{bmatrix} \cdot \begin{bmatrix} x \\\\ y \end{bmatrix} = x^2 - y^2 $$
but \(f(\vec x) = x^2 - y^2\) has no global minimum, since you can make \(f(\vec x)\) arbitrarily negative by setting \(x = 0\) and \(y = -\text{large number}\).
c)
2 pts True or False: As long as all of the components of \(S\) are positive real numbers, if
\(\nabla f(\vec a) = \vec 0\), then \(\vec a\) is a global minimum of \(f(\vec x)\).
True False
Solution
True False
This is also false. Even if all of the components of \(S\) are positive real numbers, \(f(\vec x)\) may not have a global minimum. As we saw later in the semester, the convexity of \(f\) has to do with whether or not \(S\) is positive semidefinite. But, this was not a concept we knew about on the midterm, so the problem is answerable without that concept.
Instead, the way to think through this is through counterexamples. For example, let \(\vec x = \begin{bmatrix} x \\ y \end{bmatrix}\), \(\vec b = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\), and \(S = \begin{bmatrix} 2 & 4 \\ 4 & 8 \end{bmatrix}\), which is a symmetric matrix with all positive real components. Then,
$$ f(\vec x) = \frac{1}{2} \begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} 2 & 4 \\\\ 4 & 8 \end{bmatrix} \begin{bmatrix} x \\\\ y \end{bmatrix} - \begin{bmatrix} 1 \\\\ 0 \end{bmatrix} \cdot \begin{bmatrix} x \\\\ y \end{bmatrix} = x^2 + 4xy + 4y^2 - x = (x + 2y)^2 - x $$
\(f(\vec x)\) has no global minimum, since you can keep decreasing the output by picking a really large positive value of \(x\) and set \(y = -\frac{x}{2}\), which makes
$$ f(\vec x) = (x + 2 \cdot -\frac{x}{2})^2 - x = 0 - x = -x $$
d)
6 pts We’d like to use gradient descent to minimize \(f(\vec x)\). Suppose \(S = \begin{bmatrix} 2 & 0 \\ 0 & 6 \end{bmatrix}\), \(\vec b = \begin{bmatrix} 1 \\ -4 \end{bmatrix}\), and we use a learning rate of \(\alpha = 1\). After one iteration of gradient descent, we have \(\vec x^{(1)} = \begin{bmatrix} - 2 \\ -4 \end{bmatrix}\). What was our initial guess, \(\vec x^{(0)}\)? Show your work, and \(\boxed{\text{circle}}\) your final answer, which should be a vector with two entries and no variables.
Solution
The gradient update rule is \(\vec x^{(t+1)} = \vec x^{(t)} - \alpha \nabla f(\vec x^{(t)})\). Plugging in \(\alpha = 1\) and \(t = 0\) simplifies our problem to
Now, all we need to do is substitute our known vector \(\vec x^{(1)} = \begin{bmatrix} - 2 \\ -4 \end{bmatrix}\) and matrix \(S\) into the above equation and solve for \(\vec x^{(0)}\).
Suppose \(f: \mathbb{R} \to \mathbb{R}\) is a convex function.
a)
4 pts Find scalars \(a\) and \(b\) such that \(f(3) \leq a f(2) + b f(6)\). Show your work and \(\boxed{\text{circle}}\) your final answer, which should be a pair of scalars.
Solution
Recall the definition of convexity (which is relevant, since \(f\) is told to us to be convex):
$$ f((1-t) x + ty) \leq (1-t) f(x) + t f(y) $$
Matching the right-side of the inequality above to the right-side of the inequality given, we see that \(a = 1-t\) and \(b = t\).
So, our job is to find \(1-t\) and \(t\) such that
$$ 3 = (1-t) \cdot 2 + t \cdot 6 $$
i.e. \(\textbf{to write 3 as a linear combination of 2 and 6}\).
Since there’s an \(f(5)\) in the left side of expression we want to prove, we need to find an inequality for \(f(5)\) in terms of \(f(2)\) and \(f(6)\).
Trying to match the pattern, let \(t = \frac{3}{4}\), and keep \(x = 2\) and \(y = 6\). Where did \(t = \frac{3}{4}\) come from? You could have found it from solving \((1-t) \cdot 2 + t \cdot 6 = 5\), or by guessing/observing that no other value of \(t\) would eventually allow us to add the two inequalities together to get \(f(2) + f(6)\) on the right.
Consider the function \(f: \mathbb{R} \to \mathbb{R}\) graphed below.
Note that \(f\) is a piecewise linear function, with slopes of \(0\), \(4\), and \(-4\). The slope changes at the following values of \(x\): \(-6, -5, -2, -1, 1, 2, 5, 6\).
Suppose we want to minimize \(f(x)\) using gradient descent. There are several values of \(x\) such that \(f\) is not differentiable at \(x\); if any of our guesses \(x^{(0)}, x^{(1)}, x^{(2)}, \ldots\) ever evaluate to one of these values, we say that gradient descent crashes.
a)
2 pts True or False: \(f(x)\) is convex on the domain \(x \in [-9, 9]\).
True False
Solution
True False
This is false. In order for a function to be convex, it must be the case that we can draw a line segment between any two points on the function and the line segment never passes below the function, but this is not the case for this \(f\). For example, connect \((-3, 1)\) to \((-1, -3)\); the line segment is entirely beneath the function.
b)
4 pts Suppose we choose a learning rate/step size of \(\alpha = 0.1\).
Among the options below, which value of \(x^{(0)}\) will allow gradient descent to converge to the global minimum of \(f(x)\)without crashing?
If multiple values of \(x^{(0)}\) are possible, select the value that converges the quickest (i.e. in the fewest number of iterations).
\(1.4\)\(1.6\)\(1.8\)\(1.9\)\(2.0\)
Solution
\(1.4\)\(1.6\)\(1.8\)\(1.9\)\(2.0\)
When \(x\) is between \(1\) and \(2\), the slope is 4, so with learning rate \(\alpha = 0.1\), gradient descent updates by
6 pts Suppose \(A\) is a \(4 \times 4\) matrix and \(\vec x \in \mathbb{R}^4\). Furthermore, suppose that the gradient of the function \(f(\vec x) = \vec x^T A \vec x\) is given by
Let \(\vec x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\). Consider the function
$$ f(\vec x) = (x_1 + x_2 - 4)^2 $$
a)
3 pts Fill in the blanks: The set of all vectors \(\vec x^{\ast}\) that minimize \(f(\vec x)\) form a __(i)__ in \(\mathbb{R}^2\). This set __(ii)__ a subspace of \(\mathbb{R}^2\).
point line plane
is not is
Solution
is not is
We have
$$ f(\vec x) = (x_1 + x_2 - 4)^2 $$
so the minimum value is 0, which happens exactly when
$$ x_1 + x_2 - 4 = 0 \iff x_1 + x_2 = 4 $$
The equation
$$ x_1 + x_2 = 4 $$
describes a line in \(\mathbb{R}^2\).
This line is not a subspace, because it does not pass through the origin. For example,
$$ \begin{bmatrix} 0 \\\\ 0 \end{bmatrix} $$
is not a minimizer. Therefore, this set is not a subspace.
b)
8 pts Suppose we use gradient descent to minimize \(f(\vec x)\) using an initial guess of \(\vec x^{(0)} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\).
Find the learning rate/step size \(\alpha\) that will cause gradient descent to converge to a global minimum of \(f(\vec x)\)in one iteration, i.e. such that \(\vec x^{(1)}\) is a minimizer of \(f(\vec x)\).
Show your work in the space provided, and write your final answer in the bottom-right corner of the box. Your answer should be a number with no variables.
$$ \alpha = \_\_\_\_\_\_ $$
Solution
First, we need to compute the gradient of \(f(\vec x)\):
Consider the function \(g: \mathbb{R}^3 \to \mathbb{R}\). We’d like to minimize \(g\) using gradient descent.
a)
(6 pts) Suppose two separate runs of gradient descent are started from the same initial guess\(\vec x^{(0)}\), but with different learning rates (step sizes), \(\alpha\).
If \(\alpha = 1/2\), then \(\vec x^{(1)} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\), and if \(\alpha = 1/4\), then \(\vec x^{(1)} = \begin{bmatrix} 2 \\ 3 \\ 2 \end{bmatrix}\).
Find \(\nabla g(\vec x^{(0)})\), the gradient of \(g\) at \(\vec x^{(0)}\). Show your work, and write your final answer in the box provided. Your answer should be a vector with no variables.
$$ \nabla g(\vec x^{(0)}) = \_\_\_\_\_\_ $$
Solution
Let \(\vec d = \nabla g(\vec x^{(0)})\). The gradient descent update rule is
We applied the chain rule above by writing \(\left( x_1 + 2x_2 - 6 \right)^2 = (\begin{bmatrix} 1 \\ 2 \end{bmatrix} \cdot \vec x - 6)^2\). If this feels foreign, we can instead take partial derivatives with respect to \(x_1\) and \(x_2\) separately.
Suppose \(A\) is an \(n \times d\) matrix and \(\vec x \in \mathbb{R}^d\). Consider the function \(f: \mathbb{R}^d \to \mathbb{R}\) given by
$$ f(\vec x) = \left\|A\vec x\right\| $$
a)
2 pts True or False: \(f(\vec x)\) is a linear transformation.
True False
Solution
True False
This is false. Recall, a linear transformation must satisfy \(f(c \vec x) = c f(\vec x)\) for any scalar \(c\). But, suppose we pick \(n = d = 1\), and let \(A = [1]\) (here we’re thinking of a \(1 \times 1\) matrix as a scalar). Then, \(f(x)\) is just the absolute value of the scalar \(x\).
$$ f(x) = |x| $$
But, \(f(-2) = 2\) is not the same as \(-2 f(1) = -2\). So, this \(f(x)\) is not a linear transformation, and thus in general \(f(\vec x) = \lVert A \vec x \rVert\) is not a linear transformation.
Another way to think about why \(f(\vec x)\) is not linear is to use the fact that \(\lVert A \vec x \rVert^2 = \vec x^T A^T A \vec x\):
$$ f(\vec x) = \sqrt{\vec x^T A^T A \vec x} $$
\(f(\vec x)\) is the square root of a quadratic form, which is not linear.
b)
10 pts Find \(\nabla f(\vec x)\). Assume that \(A \vec x \neq \vec 0\). Show your work, and write your final answer in the bottom-right corner of the box. Your answer should be an expression in terms of \(A\), \(\vec x\), and/or constants. Hint: Start by taking the gradient of \(\lVert A \vec x \rVert^2\), then apply the chain rule.
$$ \nabla f(\vec x) = \_\_\_\_\_\_ $$
Solution
As the hint suggests, let’s start by writing
$$ \left\|A\vec x\right\|^2 = (A\vec x)^T(A\vec x) = \vec x^T A^T A \vec x $$
Using the quadratic-form gradient rule,
$$ \nabla \left\|A\vec x\right\|^2 = 2A^TA\vec x $$
The chain rule from Chapter 8.2 states that if \(f(\vec x) = h(g(\vec x))\), where \(h: \mathbb{R} \to \mathbb{R}\) and \(g: \mathbb{R}^d \to \mathbb{R}\) are both differentiable, then \(\nabla f(\vec x) = h’(g(\vec x)) \nabla g(\vec x)\).
Here, \(h(x) = \sqrt{x}\) (so \(h’(x) = \displaystyle \frac{1}{2\sqrt{x}}\)) and \(g(\vec x) = \left|A\vec x\right|^2\), so
Let \(\vec x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\). Consider the function \(f: \mathbb{R}^2 \to \mathbb{R}\) given by
$$ f(\vec x) = c x_1^2 + d x_2^2 $$
where \(c\) and \(d\) are constants. We’d like to use gradient descent to minimize \(f(\vec x)\). For some values of \(c\) and \(d\), and some initial guess \(\vec x^{(0)}\) and learning rate/step size \(\alpha\), we find that
5 pts Find the value of \(\alpha\). Show your work, and write your final answer in the bottom-right corner of the box. Your answer should be a number with no variables.
5 pts Find the value of \(d\) (not\(c\)). Show your work, and write your final answer in the bottom-right corner of the boxes. Your answer should be a number with no variables.
5 pts Your friend claims that gradient descent always converges to a minimum because each iteration moves in the direction of steepest decrease. Based on the information in this problem, is your friend correct? State “yes” or “no”, and briefly explain your reasoning.
Solution
No. From part b), \(d=-1\), so
$$ f(\vec x) = cx_1^2 - x_2^2 $$
This function does not have a minimum, because we can make \(f(\vec x)\) arbitrarily negative by making \(|x_2|\) arbitrarily large. So, in this problem, gradient descent cannot converge to a minimum.
Since \(f\) is defined at \(\begin{bmatrix}2\\1\end{bmatrix}\), this must mean that \(\vec a \cdot \vec x\), which is equal to \(2a_1 + a_2\), is positive. Multiplying both sides by this positive denominator gives
This says \(\vec{a}\) must be a positive scalar multiple of \(\begin{bmatrix}1\\3\end{bmatrix}\). Among the answer choices, the vectors with that form are \(\begin{bmatrix}1\\3\end{bmatrix}\) and \(\begin{bmatrix}2\\6\end{bmatrix}\).
Another way to approach this would be to take the equation
from above, and realize the expression on the right is also equal to \(\frac{1}{2a_1+a_2} \begin{bmatrix}a_1\\a_2\end{bmatrix}\), which allows us to set up a system of equations directly for \(a_1\) and \(a_2\):
Both equations say the same thing: \(a_2 = 3a_1\), i.e. that \(a_2\) must be triple \(a_1\), so \(\vec a\) is a scalar multiple of \(\begin{bmatrix}1\\3\end{bmatrix}\). But, don’t forget the added constraint that \(2a_1 + a_2\) must be positive.
b)
4 pts Suppose we use gradient descent to minimize \(f(\vec x)\) using an initial guess of \(\vec x^{(0)} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}\) and a learning rate of \(\alpha = 1/2\). Find \(\vec x^{(1)}\). Show your work, and write your answer in the box provided. Your answer should be a vector with no variables.
