Short version: given a linear regression dataset and an integer $K$, what data subset of size $K$ results in linear parameters with the lowest mean squared error on the entire dataset?

Long version: Suppose I have a supervised dataset $D_n := \{x_n, y_n\}_{n=1}^N$ and I want to perform ordinary linear regression by minimizing

$$ L_{OLS, N}(w) = ||Y_N - X_N w||_2^2$$

where $Y_N$ is the matrix formed by stacking $y_n$ as row vectors and $X_N$ is the matrix formed by stacking $x_n$ as row vectors. I use the subscript $N$ to remind us that we used all the data to compute the parameter estimates. Alternatively, I might want to perform ridge linear regression by minimizing

$$ L_{Ridge, N}(w) = ||Y_N - X_N w||_2^2 + c ||w||_2^2$$

We know that the parameters that minimize the above losses are given by

$$w_{OLS, N} = (X_N^T X_N)^{-1} X_N^T Y_N$$

$$w_{Ridge, N} = (X_N^T X_N + c I)^{-1} X_N^T Y_N$$

What I'm curious to know is: if we're forced to choose a subset of only $K < N$ data $D_K := \{(x_k, y_k)\}_{k=1}^K \subset D_N$ and we fit parameters

$$w_{OLS, K} = (X_K^T X_K)^{-1} X_K^T Y_K$$

$$w_{Ridge, K} = (X_K^T X_K + c I)^{-1} X_K^T Y_K$$

what subset of $K$ data results in parameters $w_{OLS, K}$ and $w_{Ridge, K}$ such that $L_{OLS, N}(w)$ and $L_{Ridge, N}(w)$ (respectively) are minimized?


1 Answer 1


the squared error of the full data set are: $$SSE=\varepsilon'\varepsilon$$where $\varepsilon=Y-X\hat\beta_K$ and $\hat\beta_K=(X_K'X_K)^{-1}X'_KY_K$

You want to minimize SSE wrt a subset K. Unfortunately the only way to do it is through trying all combinations of K-subsets. It's $\frac{N!}{K!(N-K)!}$, which is a lot of work to say the least.

  • $\begingroup$ One place to watch out when you try this is if two observations have the same $x$-values but different $y$-values. $\endgroup$
    – Dave
    Nov 18, 2021 at 21:36
  • $\begingroup$ In my setup, I don't get to choose the number of observations. That's a given parameter, and it could be less than the number of effective parameters. $\endgroup$ Nov 18, 2021 at 21:37
  • 1
    $\begingroup$ No, not true. You'll get zero errors on those $K$ points, but I want to know about the errors on the full dataset. $\endgroup$ Nov 18, 2021 at 21:38
  • $\begingroup$ Now that I think about it more, I think the above answer isn't correct even when there are more observations than effective number of parameters. $\endgroup$ Nov 18, 2021 at 21:40
  • 1
    $\begingroup$ I found Mahoney 2011's "Randomized algorithms for matrices and data" which gives a randomized algorithm with high probability of recovering the correct answer $\endgroup$ Nov 22, 2021 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.