Homework 1
Stat 154/254: Statistical Machine Learning
Due Sunday September 27th (9pm)
1 Regressing on linear transformations
Consider two linear regressions,
\[ \boldsymbol{Y}\sim \boldsymbol{X}\boldsymbol{\beta} \quad\textrm{and}\quad \boldsymbol{Y}\sim \boldsymbol{Z}\boldsymbol{\gamma}, \]
where \(\boldsymbol{z}_n = \boldsymbol{A}\boldsymbol{x}_n\) for an invertible linear transformation \(\boldsymbol{A}\). Show that these two models produce the same predictions, i.e. that, for any \(\boldsymbol{x}_\mathrm{new}\) and \(\boldsymbol{z}_\mathrm{new}= \boldsymbol{A}\boldsymbol{x}_\mathrm{new}\),
\[ \hat{y}_\mathrm{new}= \hat{\boldsymbol{\beta}}^\intercal\boldsymbol{x}_\mathrm{new}= \hat{\boldsymbol{\gamma}}^\intercal\boldsymbol{z}_\mathrm{new}. \]
2 One-hot encodings
Consider a one–hot encoding of a variable \(z_n\) that takes three distinct values, “a”, “b”, and “c”. That is, let
\[ \boldsymbol{x}_n = \begin{cases} \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} & \textrm{ when }z_n = a \\ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} & \textrm{ when }z_n = b \\ \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} & \textrm{ when }z_n = c \\ \end{cases} \]
Let \(\boldsymbol{X}\) be the regressor matrix with \(\boldsymbol{x}_n^\intercal\) in row \(n\).
(a)
Let \(N_a\) be the number of observations with \(z_n\) = a, and let \(\sum_{n:z_n = a}\) denote a sum over rows with \(z_n\) = a, with analogous definitions for b and c. In terms of these quantities, write expressions for \(\boldsymbol{X}^\intercal\boldsymbol{X}\) and \(\boldsymbol{X}^\intercal\boldsymbol{Y}\).
(b)
When is \(\boldsymbol{X}^\intercal\boldsymbol{X}\) invertible? Explain intuitively why the regression problem cannot be solved when \(\boldsymbol{X}^\intercal\boldsymbol{X}\) is not invertible. Write an explicit expression for \((\boldsymbol{X}^\intercal\boldsymbol{X})^{-1}\) when it is invertible.
(c)
Using your previous answer, show that the least squares vector \(\hat{\boldsymbol{\beta}}\) is the mean of \(y_n\) within distinct values of \(z_n\).
(d)
Suppose now you include a constant in the regression, so that
\[ y_n = \alpha + \boldsymbol{\beta}^\intercal\boldsymbol{x}_n + \varepsilon_n, \]
and let \(\boldsymbol{X}'\) denote the regressor matrix for this regression with coefficient vector \((\alpha, \boldsymbol{\beta}^\intercal)^\intercal\). Write an expression for \(\boldsymbol{X}'^\intercal\boldsymbol{X}'\) and show that it is not invertible.
(e)
Find three distinct values of \((\alpha, \boldsymbol{\beta}^\intercal)\) that all give the exact same fit \(\alpha + \boldsymbol{\beta}^\intercal\boldsymbol{x}_n\).
3 Partitioning the regression space and the curse of dimensionality
For this problem, assume we are running linear regression with regressors \(\boldsymbol{x}\in [0,1]^P\). That is, \(\boldsymbol{x}= (x_{1}, \ldots, x_{P})^\intercal\) and each entry \(x_{p} \in [0,1]\). Note that for the generic vector \(\boldsymbol{x}\), I’ll write the \(p\)–th entry as \(x_p\) — don’t confuse this with the subscript \(\boldsymbol{x}_n\), which would be the \(n\)–th observed vector.
For a each \(k=1, \ldots, K\), define the partition function \(\phi_k(x) = \mathrm{I}\left(x\in \left[ (k-1)/ K, k/K \right)\right)\). That is, \(\phi_k(x)\) takes in a scalar \(x\) and returns a \(1\) if \(x\) is in the \(k\)-th partition of the unit interval. We will be applying \(\phi_k(x)\) to the components of the vector \(\boldsymbol{x}\).
(a) Let \(K=5\). Draw the graphs of the following functions for \(x\in [0,1]\), with \(x\) on the x-axis and the function on the y-axis:
- \(\phi_1(x)\)
- \(\phi_2(x)\)
- \(\phi_5(x)\)
- \(3 \phi_2(x)\)
- \(0.3 \phi_1(x) + 0.7 \phi_2(x) - 1.2 \phi_3(x) + 2 \phi_4(x) + 1.5 \phi_5(x)\)
(b) Now, suppose that \(P=1\) and \(K=5\). Describe in ordinary language what kinds of functions you can fit with a regression of the form \(f(\boldsymbol{x}; \boldsymbol{\beta}) = \sum_{k=1}^K \beta_k \phi_k(x_{1})\). If you run OLS to choose \(\hat{\boldsymbol{\beta}}\) in this regression, what will the fit \(f(\boldsymbol{x}_n; \hat{\boldsymbol{\beta}})\) be in the \(k\)–th interval in terms of the observed responses, \(y_n\)? (Hint: Express your answer in terms of the average of the \(y_n\) in the intervals.)
(c) Now, suppose that \(P=2\) and \(K=3\), and consider the regression function of the form \[ f(\boldsymbol{x}; \boldsymbol{\beta}) = \sum_{i=1}^K \sum_{j=1}^K \beta_{ij} \phi_i(x_{1}) \phi_j(x_{2}). \]
Start by making a picture of the following functions:
- \(\phi_1(x_{1}) \phi_2(x_{2})\)
- \(\phi_3(x_{1}) \phi_2(x_{2})\)
- \(2 \phi_3(x_{1}) \phi_2(x_{2})\)
To make this picture, you will need to put \(x_1\) on the x-axis, \(x_2\) on the y-axis, and indicate the height of the function with shading or coloring. To get full credit on the homework you only need to sketch it. There’s no need to do a high quality graphic, this is only to prompt you to think about what the function looks like.
Describe in ordinary language what kinds of functions you can fit with \(f(\boldsymbol{x}; \boldsymbol{\beta})\). Suppose a point \(\boldsymbol{x}\) lands in the \(i\)–th partition in its first coordinate and the \(j\)–th partition in its second coordinate. What will the fit \(f(\boldsymbol{x}_n; \hat{\boldsymbol{\beta}})\) be in terms of the observed response, \(y_n\)?
(d) In the setting of (c), contrast \(f(\boldsymbol{x}_n; \hat{\boldsymbol{\beta}})\) with the regression function \[ g(\boldsymbol{x}; \boldsymbol{\gamma}) = \sum_{i=1}^K \sum_{p=1}^P \gamma_{ip} \phi_i(x_{p}). \] Are there any functions you can estimate with \(f\) but not with \(g\)? Support your argument with a proof or a counter example.
(e) Let’s generalize the previous results for arbitrary dimension \(P\) and partition size \(K\). Let \(I_{k_1 k_2 \ldots k_P}\) denote the “cell” in \(\mathbb{R}^{P}\) where \(x_{1}\) is in the \(k_1\)–th interval, \(x_{2}\) is in the \(k_2\)–th interval, and so on. Write a regression function that can take on a different value for every cell \(I_{k_1 k_2 \ldots k_P}\). How many coefficients do you have to estimate to fit this regression function? Express your answer as a function of \(P\) and \(K\).
(f) Suppose that each component of \(\boldsymbol{x}\) is drawn independently and uniformly in \([0,1]\). In the setting of (e), for a given cell \(I_{k_1 k_2 \ldots k_P}\), what is \(p(\boldsymbol{x}\in I_{k_1 k_2 \ldots k_P})\)? In a sample of size \(N\), use the union bound to upper bound the probability that each cell has a datapoint.
Express your answers in terms of \(N\), \(P\), and \(K\), and then plug in a few typical values. You should find that you are very unlikely to have an observation in every cell, or in any particular cell, even in moderate dimensions.
(g) Given (e) and (f), it is common practice to only include interactions up to a certain order. That is, for some \(R \le P\), one might regress on the “first order” terms \(\phi_k(x_{p})\), the “second order” terms \(\phi_{k_1}(x_{p_1})\phi_{k_2}(x_{p_2})\), the “third order” terms \(\phi_{k_1}(x_{p_1})\phi_{k_2}(x_{p_2})\phi_{k_3}(x_{p_3})\), and so on, up to the \(R\)–th order terms that are a product of \(R\) indicators. Let \(\mathcal{F}_R\) denote functions that include interactions only up to order \(R\). Which is more expressive, \(\mathcal{F}_R\) or your class of regression functions from (e)?
4 Ridge regression
Recall the ridge regression estimator
\[ \hat{\boldsymbol{\beta}}(\lambda) := \left( \boldsymbol{X}^\intercal\boldsymbol{X}+ \lambda {\boldsymbol{I}_{\,}}\right)^{-1} \boldsymbol{X}^\intercal\boldsymbol{Y}, \]
for \(\lambda > 0\). We will not assume that \(\boldsymbol{X}\) is full–column rank. By writing this expression, we are implicitly assuming that \(\left( \boldsymbol{X}^\intercal\boldsymbol{X}+ \lambda {\boldsymbol{I}_{\,}}\right)\) is invertible. In this problem, we will show that it is always invertible, and so \(\hat{\boldsymbol{\beta}}_{ridge}\) always exists, even if \(\boldsymbol{X}\) is not full–column rank.
For each problem, carefully justify your answer.
(a)
What is the smallest possible eigenvalue for \(\boldsymbol{X}^\intercal\boldsymbol{X}\)?
(b)
What is the smallest possible eigenvalue for \(\boldsymbol{X}^\intercal\boldsymbol{X}+ \lambda {\boldsymbol{I}_{\,}}\)?
(c)
Using (b), conclude that \(\boldsymbol{X}^\intercal\boldsymbol{X}+ \lambda {\boldsymbol{I}_{\,}}\) is always invertible.
(d)
For any given \(\boldsymbol{X}\) and \(\boldsymbol{Y}\), can you find a \(\lambda_0 > 0\) such that \(\hat{\boldsymbol{\beta}}(\lambda_0) = \boldsymbol{0}\)?
5 Lasso regularization
(Based on Buchweitz (2025))
Recall the Lasso estimator,
\[ \begin{aligned} \hat{\boldsymbol{\beta}}(\lambda) :={}& \underset{\boldsymbol{\beta}}{\mathrm{argmin}}\, \hat{\mathscr{R}}(\boldsymbol{\beta}; \lambda) \\ \quad\textrm{where}\quad \hat{\mathscr{R}}(\boldsymbol{\beta}; \lambda) :={}& \sum_{n=1}^N(y_n - \boldsymbol{x}_n^\intercal\boldsymbol{\beta})^2 + \lambda \sum_{k=1}^K \left|\beta_k\right|. \end{aligned} \]
(a)
Where is \(\hat{\mathscr{R}}(\boldsymbol{\beta}; \lambda)\) differentiable as a function of \(\boldsymbol{\beta}\)? At the points of differentiability, evaluate \(\partial \hat{\mathscr{R}}(\boldsymbol{\beta}; \lambda) / \partial \boldsymbol{\beta}\).
(b)
For any given \(\boldsymbol{X}\) and \(\boldsymbol{Y}\), show that there is \(\lambda_0 \geq 0\) such that for all \(\lambda{\geq}\lambda_0\), it holds that \(\hat{\boldsymbol{\beta}}(\lambda) = \boldsymbol{0}\).
(c)
Show that, as \(\lambda\) decreases from the \(\lambda_0\) defined in (b), eventually a regressor will have a nonzero coefficient when \(\lambda\) crosses some threshold, \(\lambda_1\).
(d)
For simplicity, assume that the entries of \(\boldsymbol{X}^\intercal\boldsymbol{Y}\) are all distinct, so there are no “ties” in the sample absolute value of the second moment between the regressors and the responses.
Let \[ k^* = \underset{k}{\mathrm{argmax}}\, \left|\boldsymbol{X}^\intercal_{\cdot k} \boldsymbol{Y}\right| = \underset{k}{\mathrm{argmax}}\, \left|\sum_{n=1}^Nx_{nk} y_n\right| \] denote the index of the regressor with the largest sample second moment with \(\boldsymbol{Y}\).
Show that:
- The first entry of \(\hat{\boldsymbol{\beta}}(\lambda)\) to be nonzero will be \(k^*\),
- The \(\lambda_1\) given in (c) is \(\lambda_1 = 2 \left|\sum_{n=1}^Nx_{nk^*} y_n\right|\).
(e)
Suppose you define an linear transformation of regressor \(k\):
\[ z_{nk} := a x_{nk}, \]
and then perform Lasso using \(z_{nk}\) in place of \(x_{nk}\). Recall that the unregularized linear regression predictions are invariant to linear transformations of this sort.
Assume that \(\sum_{n=1}^Nx_{nk} y_n \ne 0\). Using (d), show that you can always choose \(a\) large enough that the regressor \(z_{nk}\) is selected as the first non–zero coefficient.
(f)
Now suppose that \(\frac{1}{N} \sum_{n=1}^Ny_n \ne 0\), and define a re–centering transformation of regressor \(k\):
\[ z_{nk} := x_{nk} + b, \]
and then perform Lasso using \(z_{nk}\) in place of \(x_{nk}\). Recall that the unregularized linear regression predictions are invariant to linear transformations of this sort if a constant is included in the regression.
Assume that \(y_n \ne 0\) for at least one \(n\). Show that you can always choose \(b\) so that \(z_{nk}\) is selected as the first non–zero coefficient.
(g)
Using (e) and (f), argue why it is standard practice to center and standardize regressors so that \(\frac{1}{N} \sum_{n=1}^Nx_{nk}^2 = 1\) and \(\frac{1}{N} \sum_{n=1}^Nx_{nk} = 0\) when using the lasso.
6 Regularization and equivalent parameterizations
Let \(\zeta_0 < \ldots < \zeta_K\) denote \(K+1\) partition boundaries in \(\mathbb{R}^{}\), let \(x\in [\zeta_0, \zeta_K]\), and define two different sets of regressors:
\[ \begin{aligned} s_{k}(x) :={}& \mathrm{I}\left(\zeta_{k - 1} < x\right) \quad\textrm{for}\quad k=1,\ldots,K \\ r_{k}(x) :={}& \mathrm{I}\left(\zeta_{k - 1} < x\le \zeta_{k} \right) \quad\textrm{for}\quad k=1,\ldots,K. \end{aligned} \]
Let \(\boldsymbol{s}_n = (s_{1}(x_n), \ldots, s_{K}(x_n))^\intercal\), and \(\boldsymbol{r}_n = (r_{1}(x_n), \ldots, r_{K}(x_n))^\intercal\). (You might say “s” is for “step” and “r” is for “region.”)
(a)
Show that \(\boldsymbol{s}_n\) is an invertible linear transformation of \(\boldsymbol{r}_n\). As a consequence, OLS predictions using \(\boldsymbol{s}_n\) and \(\boldsymbol{r}_n\) are equivalent if there is no regularization.
(b)
Consider running Lasso regression with \(\boldsymbol{s}_n\). Sketch an example of what the approximating function \(\sum_{k=1}^K \beta_k s_{k}(x)\) would look like if \(\boldsymbol{\beta}\) is sparse.
(c)
Consider running Lasso regression with \(\boldsymbol{r}_n\). Sketch an example of what the approximating function \(\sum_{k=1}^K \beta_k r_{k}(x)\) would look like if \(\boldsymbol{\beta}\) is sparse.
(d)
Between (b) and (c), which would you expect to be more useful in a typical regression situation?
(e)
Is regularized regression invariant under invertible linear transformations of the regressors?
7 Incorrectly specified linear regression
Assume that \(y_n = \boldsymbol{x}_n^\intercal\boldsymbol{\alpha}^{*}+ \boldsymbol{z}_n^\intercal\boldsymbol{\gamma}^{*}+ \varepsilon_n\), for some \(\boldsymbol{\alpha}^{*}\) and \(\boldsymbol{\gamma}^{*}\), where \(\varepsilon_n\) is mean zero, has finite variance \(\sigma^2\), and is independent of \(\boldsymbol{x}_n\) and \(\boldsymbol{z}_n\). It follows that the optimal regression function is
\[ f^{\star}(\boldsymbol{x}, \boldsymbol{z}) = \mathbb{E}_{\vphantom{}}\left[y\vert \boldsymbol{x}, \boldsymbol{z}\right] = \boldsymbol{x}^\intercal\boldsymbol{\alpha}^{*}+ \boldsymbol{z}^\intercal\boldsymbol{\gamma}^{*}. \]
Assume further that \(\boldsymbol{x}_n\) and \(\boldsymbol{z}_n\) are IID across \(n\), but possibly correlated for a particular \(n\), and have finite covariances, and zero mean. Let \(\boldsymbol{X}\) and \(\boldsymbol{Z}\) denote the matrices with \(\boldsymbol{x}_n^\intercal\) and \(\boldsymbol{z}_n^\intercal\) in row \(n\), respectively.
Denote
\[ \begin{aligned} M_{xx} :={}& \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}_n \boldsymbol{x}_n^\intercal\right] \\ M_{zz} :={}& \mathbb{E}_{\vphantom{}}\left[\boldsymbol{z}_n \boldsymbol{z}_n^\intercal\right] \\ M_{xz} :={}& \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}_n \boldsymbol{z}_n^\intercal\right] =: M_{zx}^\intercal, \end{aligned} \]
and assume that \(M_{xx}\) and \(M_{zz}\) are invertible. Note that, since \(\mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}_n\right] = \boldsymbol{0}\) and \(\mathbb{E}_{\vphantom{}}\left[\boldsymbol{z}_n\right] = \boldsymbol{0}\), that the matrices \(M\) are covariances.
We will consider the misspecified regression \(y_n \sim \boldsymbol{x}_n^\intercal\boldsymbol{\beta}\), letting \(\boldsymbol{\beta}^{*}:= \lim_{N \rightarrow \infty} \hat{\boldsymbol{\beta}}\) (in the sense that \(\hat{\boldsymbol{\beta}}\rightarrow \boldsymbol{\beta}^{*}\) in probability).
(a)
Write an expression for \(\boldsymbol{\beta}^{*}\) in terms of the quantities defined above.
(b)
Suppose we are using our linear regression for causal inference, and want to know \(\boldsymbol{\alpha}^{*}\), which we take as the causal effect of \(\boldsymbol{x}\) on \(y\).
Suppose \(M_{xz} \ne \boldsymbol{0}\). Does \(\boldsymbol{\beta}^{*}= \boldsymbol{\alpha}^{*}\)? Interpret this result in terms of unobserved confounders.
(c)
Suppose we are using linear regression for prediction, so we do not care about estimating \(\boldsymbol{\alpha}^{*}\), but rather care about the asymptotic quality of our estimates \(\hat{y}^*_\mathrm{new}= {\boldsymbol{\beta}^{*}}^\intercal\boldsymbol{x}_\mathrm{new}\). Write an expression for the expected squared limiting bias,
\[ \mathbb{E}_{\vphantom{}}\left[ \left(f^{\star}(\boldsymbol{x}_\mathrm{new}, \boldsymbol{z}_\mathrm{new}) - \hat{y}^{*}_\mathrm{new}\right)^2 \right]. \]
(d)
Compare (c) with the bias of the “correct” prediction based on \(\boldsymbol{x}\) alone: \[ \mathbb{E}_{\vphantom{}}\left[ \left(f^{\star}(\boldsymbol{x}_\mathrm{new}, \boldsymbol{z}_\mathrm{new}) - {\boldsymbol{\alpha}^{*}}^\intercal\boldsymbol{x}_\mathrm{new}\right)^2 \right]. \]
In particular, show that the expected squared limiting bias of the “incorrect” regression is possibly smaller, and never larger, than the expected squared bias of the prediction \({\boldsymbol{\alpha}^{*}}^\intercal\boldsymbol{x}\).
(e)
Unobserved confounders are severely problematic for causal inference. Is the same true for prediction problems? Justify your answer in terms of the results from this question.
8 Maximum likelihood estimator (254 only \(\star\) \(\star\) \(\star\))
(a)
Show that the OLS estimator is the maximum likelihood estimator (MLE) of the model
\[ \begin{aligned} \mathbb{P}_{\,}\left(y_n | \boldsymbol{x}_n\right) ={}& \mathcal{N}\left(\boldsymbol{\beta}^\intercal\boldsymbol{x}_n, \sigma^2\right) \\ \mathbb{P}_{\,}\left(\boldsymbol{x}_n\right) ={}& \textrm{Some unspecified distribution} \\ (\boldsymbol{x}_n, y_n) \overset{\mathrm{IID}}{\sim}{}& \mathbb{P}_{\,}\left(\boldsymbol{x}_n\right) \mathbb{P}_{\,}\left(y_n \vert \boldsymbol{x}_n\right). \end{aligned} \]
(b)
For two different densities, \(p(\boldsymbol{x}, y)\) and \(q(\boldsymbol{x}, y)\), defined with respect to the same dominating measure, the KL divergence is defined as
\[ \mathrm{KL}(p(\boldsymbol{x}, y) || q(\boldsymbol{x}, y)) := \mathbb{E}_{p(\boldsymbol{x}, y)}\left[\log \frac{p(\boldsymbol{x}, y)}{q(\boldsymbol{x}, y)}\right], \]
where \(\mathbb{E}_{p(\boldsymbol{x}, y)}\left[\cdot\right]\) means the expectation is with respect to draws from \(p(\boldsymbol{x}, y)\).
Suppose that we have a parameterized family of conditional distributions, \(q(y| \boldsymbol{x}, \theta)\), some guess for the regressor distribution \(q(\boldsymbol{x})\) and define the risk function
\[ \mathscr{L}(\theta) := \mathrm{KL}(p(\boldsymbol{x}, y) || q(y| \boldsymbol{x}, \theta) q(\boldsymbol{x})). \]
Show that the classical maximum likelihood estimator
\[ \underset{\theta}{\mathrm{argmax}}\, \sum_{n=1}^N\log q(y_n \vert \boldsymbol{x}_n, \theta) \]
is the empirical risk minimizer for \(\mathscr{L}(\theta)\).
This means that the MLE can also be written as an ML-style risk minimization, where the loss is measured by KL divergence between the true and modeled distributions.
9 Uniform laws for linear regression (254 only \(\star\) \(\star\) \(\star\))
Consider special case of linear regression loss for \(\boldsymbol{\beta}\in \mathbb{R}^{P}\),
\[ \begin{aligned} \mathscr{R}(\boldsymbol{\beta}) :={}& \mathbb{E}_{\vphantom{}}\left[(y_\mathrm{new}- \boldsymbol{\beta}^\intercal\boldsymbol{x}_\mathrm{new})^2\right] \\ \hat{\mathscr{R}}(\boldsymbol{\beta}) :={}& \frac{1}{N} \sum_{n=1}^N(y_n - \boldsymbol{\beta}^\intercal\boldsymbol{x}_n)^2 \\ \end{aligned} \]
and let \(K\) be a bounded subset of \(\mathbb{R}^{P}\). Show directly that regression loss obeys a uniform law of large numbers, in the sense that
\[ \sup_{\boldsymbol{\beta}\in K} \left|\hat{\mathscr{R}}(\boldsymbol{\beta}) - \mathscr{R}(\boldsymbol{\beta})\right| \rightarrow 0, \]
where the limit is in probability. You may assume that \(\mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right]\) and \(\mathbb{E}_{\vphantom{}}\left[y^2\right]\) are finite and the observations are IID.