Homework 0 (Notation and review)
Stat 154/254: Statistical Machine Learning
\[ \def\gv{\boldsymbol{g}} \]
Due Sunday September 6th (9pm)
1 Post on ED
There is a thread on ED about learning objectives. Please post three (or more) learning goals for yourself. Ideally, these learning objectives will be specific, achievable, and evaluable.
You can find the offical course objectives in the Course Policies webpage. Feel free to select a few that are most important to you, or write your own.
2 Extreme values of functions
Let \(C\) be some set, and \(f(x)\) a function defined on \(x \in C\). The expression \(\inf_{x \in C} f(x)\) means “the largest lower bound for \(f(x)\) over \(x \in C\)”. The symbol “inf” is pronounced “infimum.” Analogously, \(\sup_{x \in C} f(x)\) means “the smallest upper bound for \(f(x)\) over \(x \in C\)” and is pronounced “supremum.”
The infimum is like the minimum and the supremum is like the maximum, with the important difference that the infimum and supremum always exist, whereas the minimum and maximum might not. (For this to be true, we must allow for the supremum and infimum to be infinite, which we will in this class.)
The notation \(\underset{x \in C}{\mathrm{argmin}}\, f(x)\) means “the set of \(x\) at which \(f(x)\) achieves its minimum in \(C\)”, with an analogous meaning for \(\underset{x \in C}{\mathrm{argmax}}\, f(x)\). If there are no such \(x\), the \(\underset{}{\mathrm{argmin}}\,\) (or \(\underset{}{\mathrm{argmax}}\,\)) returns the empty set, \(\emptyset\).
(a) Suppose \(f(x)\) achieves its minimum in \(C\), meaning there exists some \(x_0 \in C\) such that \(f(x_0) \le f(x)\) for all \(x \in C\). When this happens, show that the infimum is the same as the minimum, i.e. \(\inf_{x \in C} f(x) = \min_{x \in C} f(x)\).
(b) Suppose that \(\underset{x \in C}{\mathrm{argmax}}\, f(x)\) is non-empty. When this happens, show that the supremum is the same as the maximum, i.e. \(\sup_{x \in C} f(x) = \max_{x \in C} f(x)\).
(c) Let \(f(x) = \exp(x)\), and let \(C = \mathbb{R}^{}\) be the whole real line. Find \(\inf_{x} \exp(x)\). Show that there is no \(x_0\) such that \(f(x_0) = \inf_{x} \exp(x)\), so \(\min_{x} \exp(x)\) does not exist.
(d) Let \(f(x) = x\) and let \(C = (0,1)\) denote the open unit interval. Find \(\sup_{x} f(x)\), and show that \(\max_{x} f(x)\) does not exist.
(e) Let \(f(x) = 1\) be a constant, and find \(\underset{x \in (0,1)}{\mathrm{argmin}}\, f(x)\).
(f) (254 only \(\star\) \(\star\) \(\star\)) Identify a function defined on all of \([0,1]\) for which \(\sup_{x\in [0,1]} f(x) = 1\) but for which the maximum does not exist.
(g) (254 only \(\star\) \(\star\) \(\star\)) Let \(A = \begin{pmatrix}1 & 0 \\ 0 & 0\end{pmatrix}\) and find \(\underset{x\in \mathbb{R}^{2}}{\mathrm{argmin}}\, x^\intercal A x\).
3 Multivariate normal exercises
Let \(\boldsymbol{x}\sim \mathcal{N}\left(0, \Sigma\right)\) be a \(P\)–dimensional multivariate normal random vector with invertible covariance matrix \(\Sigma\). Let \(\varepsilon\sim \mathcal{N}\left(0, \sigma^2\right)\) denote a univariate normal random variable which is independent of \(\boldsymbol{x}\). Finally, for a given \(\boldsymbol{\beta}\), let \(y= \boldsymbol{x}^\intercal\boldsymbol{\beta}+ \varepsilon\).
(a) Give explicit expressions for the distributions of the following quantities in terms of the fixed quantities \(\sigma\), \(\Sigma\), and \(\boldsymbol{\beta}\). You do not need to specify the density explicitly, just fully characterize the distribution. For example, it is an acceptable answer to write \(\mathbb{P}_{\,}\left(\boldsymbol{x}\right) = \mathcal{N}\left(0, \Sigma\right)\).
Note that \((y, \boldsymbol{x}^\intercal)^\intercal\) is a \(P + 1\)—dimensional vector consisting of \(y\) stacked on top of \(\boldsymbol{x}\).
- \(\mathbb{P}_{\,}\left((y, \boldsymbol{x}^\intercal)^\intercal\right)\)
- \(\mathbb{P}_{\,}\left(\boldsymbol{x}^\intercal\boldsymbol{\beta}\right)\)
- \(\mathbb{P}_{\,}\left(y| \boldsymbol{x}\right)\)
- \(\mathbb{P}_{\,}\left(y\right)\)
- \(\mathbb{P}_{\,}\left(\varepsilon\vert \boldsymbol{x}\right)\)
(b) When \(\boldsymbol{\beta}\ne \boldsymbol{0}\), how is \(\mathrm{Var}_{\,}\left(y\vert \boldsymbol{x}\right)\) different from \(\mathrm{Var}_{\,}\left(y\right)\)? Explain this result in intuitive terms.
(c) What is the “distribution” of \(\mathbb{P}_{\,}\left(\varepsilon\vert \boldsymbol{x}, y\right)\)?
(d) (254 only \(\star\) \(\star\) \(\star\))
Now, additionally assume that \(\boldsymbol{\beta}\sim \mathcal{N}\left(\boldsymbol{0}, \boldsymbol{V}\right)\) independently of \(\boldsymbol{x}\), and that \(y= \boldsymbol{x}^\intercal\boldsymbol{\beta}+ \varepsilon\) holds conditionally on \(\boldsymbol{x}\), \(\boldsymbol{\beta}\), and \(\varepsilon\). Give explicit expressions for the following distributions in terms of \(\Sigma\), \(\sigma\), and \(\boldsymbol{V}\).
- \(\mathbb{P}_{\,}\left((y, \boldsymbol{\beta}^\intercal)^\intercal\vert \boldsymbol{x}\right)\)
- \(\mathbb{P}_{\,}\left(\boldsymbol{\beta}^\intercal\boldsymbol{x}\vert \boldsymbol{x}\right)\)
- \(\mathbb{P}_{\,}\left(\boldsymbol{\beta}\vert y, \boldsymbol{x}\right)\)
4 LLNs and CLTs
For this problem, you may use without proof the Law of Large Numbers (LLN) and Central Limit Theorem (CLT) for IID random variables with finite variance. (See, e.g., Pitman (2012) section 3.3.)
For \(n=1,\ldots N \ldots \infty\), let \(x_n\) denote IID variables uniformly distributed on the interval \([0,1]\). Let \(a_n\) denote a deterministic sequence satisfying \(\frac{1}{N} \sum_{n=1}^Na_n \rightarrow 0\) and \(\frac{1}{N} \sum_{n=1}^Na_n^2 \rightarrow 1\), each as \(N \rightarrow \infty\).
(a)
Compute \(\mathbb{E}_{\vphantom{}}\left[\frac{1}{N} \sum_{n=1}^Nx_n\right]\) and \(\mathrm{Var}_{\,}\left(\frac{1}{N} \sum_{n=1}^Nx_n\right)\).
(b)
What is \(\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^Nx_n\)? Explain your answer in terms of your result from (a).
(c)
Let \(z_n = x_n - 0.5\). What is \(\mathbb{E}_{\vphantom{}}\left[\frac{1}{\sqrt{N}} \sum_{n=1}^Nz_n\right]\) and \(\mathrm{Var}_{\,}\left(\frac{1}{\sqrt{N}} \sum_{n=1}^Nz_n\right)\)?
(d)
What is \(\lim_{N \rightarrow \infty} \frac{1}{\sqrt{N}} \sum_{n=1}^N(x_n - 0.5)\)? Explain how your answer relates to your result from (c).
(e)
What is \(\lim_{N \rightarrow \infty} \frac{1}{\sqrt{N}} \sum_{n=1}^Nx_n\)? Explain how your answer relates to your result from (d).
(f) (254 only \(\star\) \(\star\) \(\star\))
Compute \(\mathbb{E}_{\vphantom{}}\left[\frac{1}{N} \sum_{n=1}^Na_n x_n\right]\) and \(\mathrm{Var}_{\,}\left(\frac{1}{N} \sum_{n=1}^Na_n x_n\right)\).
(g) (254 only \(\star\) \(\star\) \(\star\))
What is \(\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^Na_n x_n\)? Explain your answer in terms of your result from (f).
(h) (254 only \(\star\) \(\star\) \(\star\))
Let \(s_N := \frac{1}{\sqrt{N}} \sum_{n=1}^N(a_n x_n - 0.5 \frac{1}{N} \sum_{n=1}^Na_n)\). Compute \(\mathbb{E}_{\vphantom{}}\left[s_N\right]\) and \(\mathrm{Var}_{\,}\left(s_N\right)\).
Advanced note: As you might guess from these computations, a result known as the Lindeberg–Feller central limit theorem (e.g., Van der Vaart (2000) 2.27) gives conditions under which
\[ \lim_{N \rightarrow \infty} s_N \rightarrow \mathcal{N}\left(0, \lim_{N\rightarrow \infty} \mathrm{Var}_{\,}\left(s_N\right)\right). \]
5 Multivariate calculus
Consider the logistic loss function \(\mathcal{L}(\boldsymbol{\beta})\) given by
\[ \begin{aligned} \phi(\zeta) :={}& \frac{\exp(\zeta)}{1 + \exp(\zeta)} \\ \ell(y| p) :={}& -y\log p- (1 - y) \log(1 - p) = - y\log \frac{p}{1-p} - \log(1 - p)\\ \mathcal{L}(\boldsymbol{\beta}) ={}& \sum_{n=1}^N\ell(y_n | \phi(\boldsymbol{\beta}^\intercal\boldsymbol{x}_n)). \end{aligned} \]
Let \(\boldsymbol{x}_n\) and \(\boldsymbol{\beta}\) be \(P\)–dimensional vectors.
(a)
Compute \(\partial \phi(\boldsymbol{\beta}^\intercal\boldsymbol{x}_n) / \partial \boldsymbol{\beta}\) and \(\partial^2 \phi(\boldsymbol{\beta}^\intercal\boldsymbol{x}_n) / \partial \boldsymbol{\beta}\partial \boldsymbol{\beta}^\intercal\).
(b)
Using (a), compute \(\partial \mathcal{L}(\boldsymbol{\beta}) / \partial \boldsymbol{\beta}\). (It helps to observe that \(\log \frac{\phi(\boldsymbol{x}_n^\intercal\boldsymbol{\beta})}{1-\phi(\boldsymbol{x}_n^\intercal\boldsymbol{\beta})} = \boldsymbol{\beta}^\intercal\boldsymbol{x}_n\).)
(c)
Using (a), compute \(\partial^2 \mathcal{L}(\boldsymbol{\beta}) / \partial \boldsymbol{\beta}\partial \boldsymbol{\beta}^\intercal\).
(d)
Let \(\boldsymbol{X}\) denote the \(N \times P\) matrix whose \(n\)–th row is \(\boldsymbol{x}_n^\intercal\), and let \(\boldsymbol{\varepsilon}\) denote the \(N \times 1\) column vector whose \(n\)–th entry is \(y_n - \phi(\boldsymbol{x}_n^\intercal\boldsymbol{\beta})\). Write \(\partial \mathcal{L}(\boldsymbol{\beta}) / \partial \boldsymbol{\beta}\) using \(\boldsymbol{X}\) and \(\boldsymbol{\varepsilon}\) using only matrix multiplication (i.e., without explicit summation of the form \(\sum_{n=1}^N(\cdot)\)).
(e) (254 only \(\star\) \(\star\) \(\star\))
Sketch pseudocode for an iterative computer program to approximately find a \(\hat{\boldsymbol{\beta}}\) satisfying \(\left. \frac{\partial \mathcal{L}(\boldsymbol{\beta})}{\partial \boldsymbol{\beta}} \right|_{\hat{\boldsymbol{\beta}}} = \boldsymbol{0}\).
(f) (254 only \(\star\) \(\star\) \(\star\))
Using your result from (c), argue that \(\hat{\boldsymbol{\beta}}\) from (e) is (up to numerical error) a minimizer of \(\mathcal{L}(\beta)\).
6 Projections (Yu (2022) HW 1.3)
(a)
For any vector \(\boldsymbol{x}=\left(x_{1}, x_{2}, x_{3}\right)^{\intercal} \in \mathbb{R}^{3}\), what is its projection on the vector \((1,0,0)^{\intercal}\) ?
(b)
What is the orthogonal projection of \(\boldsymbol{x}=\left[x_{1}, x_{2}, x_{3}\right]^{\intercal} \in \mathbb{R}^{3}\) on the subspace spanned by the vectors \([1,0,0]^{\intercal}\) and \([0,1,0]^{\intercal}\) ?
(c)
Write the projection matrices in the previous two cases.
(d)
Write the expression for the orthogonal projection of a vector \(\boldsymbol{x}\in \mathbb{R}^{D}\) along any given vector \(\boldsymbol{a}\in \mathbb{R}^{D}\). What is the projection matrix in this case?
(e)
Given two orthogonal vectors \(\boldsymbol{a}_{1}\) and \(\boldsymbol{a}_{2}\) in \(\mathbb{R}^{D}\), what is the orthognal projection of a generic vector \(\boldsymbol{x}\) on to the subspace spanned by these two vectors?
(f)
Suppose that the two vectors \(\boldsymbol{a}_{1}\) and \(\boldsymbol{a}_{2}\) are not orthogonal. How will you compute the orthogonal projection of \(\boldsymbol{x}\) in this case? It may be useful to revise Gram Schmidt Orthogonalization.
(g)
Generalize the answer from (f) to the case to compute the orthogonal projection along a \(K\)-dimensional subspace spanned by the vectors \(\boldsymbol{a}_{1}, \ldots, \boldsymbol{a}_{K}\) which need not be orthogonal.
(h)
Define the matrix
\[ \boldsymbol{A}=\left[\boldsymbol{a}_{1}, \ldots, \boldsymbol{a}_{k}\right] \in \mathbb{R}^{D \times K} \]
such that the columns are linearly independent. Prove that the orthogonal projection of any vector \(\boldsymbol{x}\in \mathbb{R}^{d}\) onto the k -dimensional subspace spanned by the vectors \(\boldsymbol{a}_{1}, \ldots, \boldsymbol{a}_{k}\) is given by
\[ \begin{equation*} \mathbf{A}\left(\mathbf{A}^{\intercal} \mathbf{A}\right)^{-1} \mathbf{A}^{\intercal} \boldsymbol{x}. \tag{1} \end{equation*} \]
Hint: Consider the least squares problem \(\min_{\boldsymbol{\beta}}\|\mathbf{A \boldsymbol{\beta}}-\boldsymbol{x}\|_{2}^{2}\).
(i)
How does the expression \(\mathbf{A}\left(\mathbf{A}^{\intercal} \mathbf{A}\right)^{-1} \mathbf{A}^{\intercal}\) simplify if the vectors \(\mathbf{a}_{1}, \ldots, \mathbf{a}_{k}\) are orthogonal?
7 Regression on an indicator
For this problem, let \(z_n \in \{0, 1\}\) be a binary regressor and let \(y_n \in \mathbb{R}^{}\) be a bounded, continuous random variable. You may assume that the pairs \((z_n, y_n)\) are independent and identically distributed for \(n=1,\ldots,N\).
Let \(\boldsymbol{\beta}= (\beta_0, \beta_1)^\intercal\in \mathbb{R}^{2}\). For a fixed \(\lambda > 0\), let \(\hat{\mathscr{R}}(\boldsymbol{\beta}) = \frac{1}{N} \sum_{n=1}^N(y_n - \beta_0 - \beta_1 z_n)^2 + \lambda \beta_1^2\).
(a) Let \(\boldsymbol{X}\) denote an \(N \times 2\) matrix, whose first column is all ones, and whose second column contains \(z_1, \ldots, z_N\):
\[ \boldsymbol{X}= \begin{pmatrix} 1 & z_1 \\ 1 & z_2 \\ \vdots \\ 1 & z_N \\ \end{pmatrix}. \]
Let \(\boldsymbol{Y}\) denote the \(N \times 1\) vector containing \(y_1, \ldots, y_N\). Write the squared error, \(\frac{1}{N} \sum_{n=1}^N(y_n - \beta_0 - \beta_1 z_n)^2\), in terms of \(\boldsymbol{X}\), \(\boldsymbol{Y}\), \(\boldsymbol{\beta}\), and \(N\) only.
(b) Write an explicit expression for the gradient \(\nabla \hat{\mathscr{R}}(\boldsymbol{\beta}) := \partial \hat{\mathscr{R}}(\boldsymbol{\beta}) / \partial \boldsymbol{\beta}\).
(c) Write an expression for \(\hat{\boldsymbol{\beta}}(\lambda)\), the unique minimum of \(\hat{\mathscr{R}}(\boldsymbol{\beta})\), assuming it exists.
(d) (254 only \(\star\) \(\star\) \(\star\)) Under what conditions is \(\hat{\boldsymbol{\beta}}(\lambda)\), defined in 1(c), unique?
(e) (254 only \(\star\) \(\star\) \(\star\)) Fix a dataset \(\boldsymbol{X}\) and \(\boldsymbol{Y}\). For this dataset, what is \(\lim_{\lambda \rightarrow \infty} \hat{\boldsymbol{\beta}}(\lambda)\)? Note: For this question, the limit is with respect to \(\lambda\), with \(N\) and the data fixed.
(f) (254 only \(\star\) \(\star\) \(\star\)) Fix \(\lambda > 0\). Write an expression for \(\lim_{N\rightarrow \infty} \hat{\boldsymbol{\beta}}(\lambda)\) in terms of expectations over the random variable \(x,y\). Note: For this question, the limit is with respect to \(N\), with \(\lambda\) fixed.
8 Constrained optimization (254 only \(\star\) \(\star\) \(\star\))
The purpose of this exercise is to justify the method of Lagrange multipliers in a special case that will come up a lot in this class. You should have seen Lagrange multipliers for constrained optimization in multivariate calculus before, though in this problem we will be particularly careful to carefully justify the method.
Consider the objective function \[ \mathscr{L}(\boldsymbol{\theta}) = \frac{1}{2}\boldsymbol{\theta}^\intercal\boldsymbol{A}\boldsymbol{\theta}+ \boldsymbol{b}^\intercal\boldsymbol{\theta}+ c \] for \(\boldsymbol{\theta}\in \mathbb{R}^{P}\), a symmetric, positive definite matrix \(\boldsymbol{A}\), a given vector \(\boldsymbol{b}\in \mathbb{R}^{P}\), and a constant \(c\). We want to find the minimum of \(\mathscr{L}(\theta)\) among vectors with squared norm less than some fixed, known \(t\). Let \(D = \{\boldsymbol{\theta}: \left\Vert\boldsymbol{\theta}\right\Vert_2^2 \le t\}\) where \(\left\Vert\boldsymbol{\theta}\right\Vert_2^2 := \boldsymbol{\theta}^\intercal\boldsymbol{\theta}\). We want to find the solution to the “primal problem”
\[ M_p := \inf_{\boldsymbol{\theta}\in D} \mathscr{L}(\boldsymbol{\theta}). \]
We will also consider the “dual problem” \[ \begin{aligned} \mathscr{L}(\boldsymbol{\theta}, \lambda) :={}& \mathscr{L}(\boldsymbol{\theta}) + \lambda(\left\Vert\boldsymbol{\theta}\right\Vert_2^2 - t) \\ M_d :={}& \sup_{\lambda \ge 0} \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \mathscr{L}(\boldsymbol{\theta}, \lambda). \end{aligned} \]
The dual problem is easier than the primal problem because it involves an infimum over all \(\theta\) rather than a constrained set. The term \(\lambda\) is called the “Lagrange multiplier.” Note that, in the dual problem, \(\lambda\) is constrained to be positive.
The goal of this exercise is to show carefully that \(M_p = M_d\) in this case, so we can safely solve the dual problem instead of the primal problem.
(a) Find a closed–form expression for the unconstrained optimization problem \(\hat{\boldsymbol{\theta}}^{UC} := \underset{\boldsymbol{\theta}\in \mathbb{R}^{P}}{\mathrm{argmin}}\, \mathscr{L}(\boldsymbol{\theta})\) in terms of \(\boldsymbol{A}\), \(\boldsymbol{b}\), and \(c\).
(b) Assuming that \(\lambda > 0\), find a closed–form expression for \(\hat{\boldsymbol{\theta}}(\lambda) := \underset{\boldsymbol{\theta}\in \mathbb{R}^{P}}{\mathrm{argmin}}\, \mathscr{L}(\boldsymbol{\theta}, \lambda)\). In particular, show carefully that we can safely write \(\hat{\boldsymbol{\theta}}(\lambda)\) instead of \(\hat{\boldsymbol{\theta}}(\lambda, t)\) since the optimum does not depend on \(t\).
(c) Show that the following two problems are equivalent:
\[ \inf_{\boldsymbol{\theta}\in D} \mathscr{L}(\theta) = \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \sup_{\lambda \ge 0} \mathscr{L}(\boldsymbol{\theta}, \lambda). \]
Hint: Find an explicit expression for \(\sup_{\lambda \ge 0} \mathscr{L}(\boldsymbol{\theta}, \lambda)\) in the case where when the constraint \(\left\Vert\boldsymbol{\theta}\right\Vert_2^2 \le t\) is violated and in the case when it is satisfied. You should find that, in the latter problem, you pay “infinite cost” for violating the constraint. Then consider what happens when \(\boldsymbol{\theta}\) does not violate the constraint, and show that at least one such \(\boldsymbol{\theta}\) exists.
(d) Using (c), show that
\[ M_d = \sup_{\lambda \ge 0} \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \mathscr{L}(\boldsymbol{\theta}, \lambda) \le \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \sup_{\lambda \ge 0} \mathscr{L}(\boldsymbol{\theta}, \lambda) = \inf_{\boldsymbol{\theta}\in D} \mathscr{L}(\theta) = M_p. \]
The difference between \(\sup_{\lambda \ge 0} \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \mathscr{L}(\boldsymbol{\theta}, \lambda)\) and \(\inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \sup_{\lambda \ge 0} \mathscr{L}(\boldsymbol{\theta}, \lambda)\) is called the “duality gap.” In order to show that \(M_d = M_p\), we need to show that the duality gap is zero. In other words, we need to show that we can safely exchange the order of the supremum and infimum in this problem.
(e) To show that the duality gap is zero, we will use part of an optimization result called the “saddle point theorem.” We now reproduce part of the proof of the saddle point theorem. Suppose we have \(\hat{\boldsymbol{\theta}}\) and \(\hat{\lambda}\) such that \[ \mathscr{L}(\hat{\boldsymbol{\theta}}, \lambda) \le \mathscr{L}(\hat{\boldsymbol{\theta}}, \hat{\lambda}) \le \mathscr{L}(\boldsymbol{\theta}, \hat{\lambda}) \] for all \(\boldsymbol{\theta}\in \mathbb{R}^{P}\) and all \(\lambda \ge 0\). Such a pair \(\hat{\boldsymbol{\theta}}, \hat{\lambda}\) is called a “saddle point.” When a saddle point exists, the duality gap is zero, since
\[ M_p = \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \sup_{\lambda \ge 0} \mathscr{L}(\boldsymbol{\theta}, \lambda) \le \sup_{\lambda \ge 0} \mathscr{L}(\hat{\boldsymbol{\theta}}, \lambda) \le \mathscr{L}(\hat{\boldsymbol{\theta}}, \hat{\lambda}) \le \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \mathscr{L}(\boldsymbol{\theta}, \hat{\lambda}) \le \sup_{\lambda \ge 0} \inf_{\boldsymbol{\theta}\in \mathbb{R}^{P}} \mathscr{L}(\boldsymbol{\theta}, \lambda) = M_d. \]
For this exercise, verify each inequality in the preceding expression.
The remainder of the problem is showing that there exists a saddle point for this problem, and so \(M_p = M_d\).
(f) By (e) it suffices to find a saddle point. We will split the problem into two cases. First, show that if \(\hat{\boldsymbol{\theta}}^{UC}\) from (a) has squared norm less than \(t\), then \(\hat{\theta}= \hat{\boldsymbol{\theta}}^{UC}\) and \(\hat{\lambda}= 0\) is a saddle point.
(g) Now, suppose that \(\hat{\boldsymbol{\theta}}^{UC}\) from (a) has squared norm greater than \(t\). Assume that there exists a \(\hat{\lambda}\) such that \(\hat{\boldsymbol{\theta}}(\hat{\lambda})\) from (b) satisfies \(\left\Vert\hat{\boldsymbol{\theta}}(\hat{\lambda})\right\Vert_2^2 = t\). Under this assumption, show that \(\hat{\boldsymbol{\theta}}= \hat{\boldsymbol{\theta}}(\hat{\lambda})\) and \(\hat{\lambda}\) are a saddle point.
(h) Show carefully that there exists a \(\hat{\lambda}\) such that \(\hat{\boldsymbol{\theta}}(\hat{\lambda})\) from (b) satisfies \(\left\Vert\hat{\boldsymbol{\theta}}(\hat{\lambda})\right\Vert_2^2 = t\). Hint: You may argue by continuity of the matrix inverse, or you may get a more precise result by considering the eigenvalue decomposition of \(A\).
(i) Conclude that, whether we are in case (g) or (h), that \(\hat{\boldsymbol{\theta}}(\hat{\lambda}) \in \underset{\boldsymbol{\theta}\in D}{\mathrm{argmin}}\, \mathscr{L}(\boldsymbol{\theta})\), so \(\hat{\boldsymbol{\theta}}(\hat{\lambda})\) is a solution to the primal problem. (For 154 students, you may take the conclusions of the 254 questions for granted.)
(j) (Extra) Find an explicit expression for \(\hat{\lambda}\) in case (h). Hint: Use the first–order condition for \(\underset{\boldsymbol{\theta}}{\mathrm{argmin}}\, \mathscr{L}(\boldsymbol{\theta}, \hat{\lambda})\), together with the fact that \(\left\Vert\hat{\boldsymbol{\theta}}(\hat{\lambda})\right\Vert_2^2 = t\). In light of this expression, interpret the constraint \(\hat{\lambda}\ge 0\).